4
\$\begingroup\$

I posted the same question at StackOverflow then I got an advice to post it here.

Original question: https://stackoverflow.com/questions/49998297/fast-insert-unique-container

I have to store elements (struct State) in a 2D vector container and each element must be unique.

I store the elements like this:

std::vector<std::vector<std::unique_ptr<State>>> m_container;

And I have an insert function

bool insert(State && value, std::size_t deepness);

Which should inset 'value' into m_container[deepness] if the value is unique or the new deepness is smaller then the previous in which case I have to remove the previous State (return true is inserted).

I have multiple threads inserting at the same time, I already have an implementation but I not sure if it is the best so I am interested in a better and faster way for the insert or some improvements.

My implementation is rather long so I try to shrink it down while keeping the logic behind it.

other than the container I have multimap:

std::multimap<std::size_t, std::pair<std::size_t, std::size_t>> m_multimap;

key: hash of the state

pair_1: deepness

pair_2: the position of the State in m_container[deepness]

I have a lockless_queue of struct Temp (lockless_queue m_queue) I insert here first then to the container.

template<typename T>
class lockless_queue {
public:
    // storeing the elements
    struct node;
    struct node_ptr;

    // insert element
    template<typename... Args>
    void produce(Args&&... args);
    void produce(T && data);
    void produce(const T & data);

    // consume all elements form queue
    node_ptr consume_all();

    // queue is not empty
    operator bool() const;
};

struct Temp {
    std::unique_ptr<State> value;
    std::size_t hash;
    std::size_t deepness;
    bool exist = false;

    Temp(State * v, std::size_t hash, std::size_t deepness, bool exist);
    Temp(State && v, std::size_t deepness);

    Temp move() {
        return Temp(value.release(), hash, deepness, exist);
    }

    bool is_equal(const State & state) const;
    bool is_equal(State * state) const;
    bool is_equal(const Temp & other) const;
    bool is_equal(Temp * other) const;

    void swap(State && v, std::size_t d) {
        deepness = d;
        value.reset(new State(std::move(v)));
    }
};

The following function is the insert function which inserts to the locless_queue

bool pre_emplace(State && value, std::size_t deepness) {
    Temp temp(std::move(value), deepness);
    const auto range = m_multimap.equal_range(temp.hash);
    if (range.first == range.second) {
        m_queue.produce(std::move(temp));
        return true;
    } else {
        const auto & container = m_container;
        const auto it = std::find_if(range.first, range.second, [&temp, &container](const auto & iter) {
            return temp.is_equal(container[iter.second.first][iter.second.second].get());
        });
        if (it == range.second || deepness < it->second.first) {
            temp.exist = true;
            m_queue.produce(std::move(temp));
            return true;
        }
    }
    return false;
}

(some case the return true is invalid because the queue is not unique but it is not a problem, I only use the return value for estimating the number of inserted elements)

this function consumes the elements from the queue into a temporary multimap of hash and Temp

void m_finalize_cycle(std::multimap<std::size_t, Temp> & multimap) {
    auto head = m_queue.consume_all();
    auto node = head.ptr;
    while (node) {
        if (!node->data.value) { node = node->next;  continue; }
        auto & temp = node->data;
        const auto range = multimap.equal_range(temp.hash);
        if (range.first == range.second) {
            multimap.emplace(temp.hash, temp.move());
        } else {
            const auto it = std::find_if(range.first, range.second, [&temp](const auto & pair) {
                return temp.is_equal(pair.second.value.get());
            });
            if (it == range.second) {
                multimap.emplace_hint(range.first, temp.hash, temp.move());
            } else if (temp.deepness < it->second.deepness) {
                it->second.value.reset(temp.value.release());
                it->second.deepness = temp.deepness;
            }
        }
        node = node->next;
    }
}

and this function load all Temp value from the previous multimap into m_container

void m_finalize_write(std::multimap<std::size_t, Temp> & multimap) {
    for (auto &[hash, temp] : multimap) {
        if (temp.exist) {
            const auto range = m_multimap.equal_range(temp.hash);
            auto & container = m_container;
            const auto it = std::find_if(range.first, range.second, [&temp, &container](const auto & iter) {
                return temp.is_equal(container[iter.second.first][iter.second.second].get());
            });
            if (it != range.second) {
                m_container.at(it->second.first).at(it->second.second).reset(nullptr);
                m_multimap.erase(it);
            }
        } else {
        }
        // extend m_container
        extend_if_needed(temp.deepness);
        m_container.at(temp.deepness).push_back(std::move(std::unique_ptr<State>(temp.value.release())));
        m_multimap.emplace(hash, std::make_pair(temp.deepness, m_container[temp.deepness].size() - 1));
    }
}

while I insert elements I run the m_finalize_cycle in every 10 microseconds then if I finished with the inserts I call the m_finalize_write.

This implementation works fine for me but unfortunately, it is the slowest part of my code so I am interested in better ways.

Edit:

I might skipped some important details:

struct Temp hold additional information which makes it a bit slower to create than the simplified version, this information is used in temp.is_equal() function so it slows down the comperation between Temps as well.

struct State {
    State * partent; // parent is not hashed    
    std::pair<int8_t, int8_t> data;
    std::array<std::pair<int8_t, int8_t>, N> more_data;
};

bool Temp::is_equal(const State & state) const {
    if (!value) return false;
    if (value->more_data != state.more_data) return false;
    if (value->data == state.data) return true;


    // this last line where I use the additional information 
    // field is a 2D array it can be generetad from State and is_reachable function compere the cell value with a const value 
    // (field[data.first][data.second]) >= X);
    return field->is_reachable(state.data);
}
\$\endgroup\$
1
\$\begingroup\$

more speed

You can find videos of Stroustrup explaining why std::multimap is so slow. See Why you shouldn't use set (and what you should use instead) by Matt Austern.

Use Boost.Container for flat_(multi)map which is a mature implementation based on Matt’s article, via Andrei Alexandrescu.

As a drop-in replacement, see what that does for your speed!


multimap.emplace_hint(range.first, std::make_pair(temp.hash, temp.move()));

That can (now) be written much more simply:

multimap.emplace_hint(range.first, { temp.hash, temp.move() } );

if (node->data.value == false)

Testing a bool against true/false is just strange. It is a bool; use it.

if (!node->data.value)

while (node != nullptr)

Don’t explicitly test against nullptr. Use the the truth value of the pointer’s value, which might (in the case of smart pointers) be an efficient operator bool in the class.

while (node)

addendum

A flat map wins for looking things up, which in my experience is the bulk of the run. The tree-based map will start beating flat-map for inserts and deletes at some size n and continue pulling ahead since the k1∙O(log n) is a better order than k2∙O(n) even when k2 is much smaller than k1.

\$\endgroup\$
  • \$\begingroup\$ boost::container::flat_multimap was slower than the std::multimap by a large margin, I insert elements in cycles with multimap I inserted 2 million elements in 65 seconds 40 cycles and with flat_multimap I inserted 600000 elements in 105 seconds 25 cycles (with std::mulimap the 25th cycle took 1.33 sec), I implemented the other small changes. \$\endgroup\$ – Sekkmer Apr 25 '18 at 12:20
  • \$\begingroup\$ @Sekkmer very interesting… what compiler and std library are you using? Hmm, the node version is good for inserting and deleting, which is what you tested, and gets stronger with larger count. The flat version is good for looking things up without incurring multiple cold cache hits. \$\endgroup\$ – JDługosz Apr 25 '18 at 17:10
  • \$\begingroup\$ @ JDługosz I use Visual Studio 2017 with std:c++latest and all optimization turned on, I here is a picture of CPU/RAM usage of my program the low CPU load is when I have to wait on "m_finalize_cycle" and at the end when some memory is freed "m_finalize_write" the high CPU load is when I generate new States with multiple threads, (m_finalize_cycle) is running at the whole operation \$\endgroup\$ – Sekkmer Apr 26 '18 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.