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);
}
