[container] locking for compact map
Hi, I'm locking for a map<std::size_t, T> implemented as array<optional<T>, N>. When the key is on the range 0..N-1 and the map is dense enough, the advantages are * the whole data is much more compact, avoiding allocations and deallocations, and should reduce the cash misses. * the access insertion/removal/get is direct O(k) instead of O(logN). The liabilities, are the same as array. * iterating is not O(k), but O(N) (When the number of elements is not too high or when there is no too much holes, this should not be a problem) * The move constructor is not noexcept. An implementation using vector<optional<T>> should avoid this last issue. You could ask your self why I don't use directly array<optional<T>> or vector<optional<T>>. The answer is that I don't want the user manage the holes. I'm aware of/flat_(multi)map/set/ associative containers. The difference here is that as the key is the position on the array which make things perform even better for this particular case. Is there something similar in Boost already that I'm missing? Do you see other liabilities I have missed? Best, Vicente
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
Hi,
I'm locking for a map<std::size_t, T> implemented as array<optional<T>, N>.
When the key is on the range 0..N-1 and the map is dense enough, the advantages are * the whole data is much more compact, avoiding allocations and deallocations, and should reduce the cash misses. * the access insertion/removal/get is direct O(k) instead of O(logN).
You mean O(1), right?
The liabilities, are the same as array. * iterating is not O(k), but O(N) (When the number of elements is not too high or when there is no too much holes, this should not be a problem)
This can pose problems on erasure, as discussed (for unordered associative containers, but the situation is the same) at http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2023.pdf
* The move constructor is not noexcept.
An implementation using vector<optional<T>> should avoid this last issue.
Or just a pointer to array, which is somewhat more efficient.
You could ask your self why I don't use directly array<optional<T>> or vector<optional<T>>. The answer is that I don't want the user manage the holes.
I'm aware of/flat_(multi)map/set/ associative containers. The difference here is that as the key is the position on the array which make things perform even better for this particular case.
Is there something similar in Boost already that I'm missing? Do you see other liabilities I have missed?
I think the O(n) erasure problem mentioned above can be an issue. Joaquín M López Muñoz Telefónica
Le 09/12/14 09:41, Joaquin M Lopez Munoz a écrit :
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
Hi,
I'm locking for a map<std::size_t, T> implemented as array<optional<T>, N>.
When the key is on the range 0..N-1 and the map is dense enough, the advantages are * the whole data is much more compact, avoiding allocations and deallocations, and should reduce the cash misses. * the access insertion/removal/get is direct O(k) instead of O(logN). You mean O(1), right? yes :)
The liabilities, are the same as array. * iterating is not O(k), but O(N) (When the number of elements is not too high or when there is no too much holes, this should not be a problem) This can pose problems on erasure, as discussed (for unordered associative containers, but the situation is the same) at
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2023.pdf I agree for erase with a pointer. However erase with a key is O(1). I agree with you having a specific erase function that don't returns the iterator avoid this problem, but I would add specific overload.
* The move constructor is not noexcept.
An implementation using vector<optional<T>> should avoid this last issue. Or just a pointer to array, which is somewhat more efficient. Why not.
You could ask your self why I don't use directly array<optional<T>> or vector<optional<T>>. The answer is that I don't want the user manage the holes.
I'm aware of/flat_(multi)map/set/ associative containers. The difference here is that as the key is the position on the array which make things perform even better for this particular case.
Is there something similar in Boost already that I'm missing? Do you see other liabilities I have missed? I think the O(n) erasure problem mentioned above can be an issue.
Agreed this is an issue with the functions returning iterators. However, as the performances should be better on a lot of other functions, I'm wondering if this class could have a wider interest. Adding other erase overload would help also. Best, Vicente
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
Le 09/12/14 09:41, Joaquin M Lopez Munoz a écrit :
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
* The move constructor is not noexcept.
An implementation using vector<optional<T>> should avoid this last issue.
Or just a pointer to array, which is somewhat more efficient. Why not.
Well, on second thought this is not that easy. Moving from a to b must leave a in a *valid* position, which here means that either you must allocate a new array for a (which makes moving non-noexcept) or assign it a null pointer and deal with the situation in the rest of the interface, which is a kind of a bummer --for instance, as having size()==N is an invariant of the class, even const functions such as cbegin() or cend() need to check for null pointer and allocate accordingly, becoming non-nonexcept, thread unsafe and whatnot. So, I think your deign shouldn't try to be move-aware, much as std::array is not either. Joaquín M López Muñoz Telefónica
Le 09/12/14 20:59, Joaquin M Lopez Munoz a écrit :
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
Le 09/12/14 09:41, Joaquin M Lopez Munoz a écrit :
Vicente J. Botet Escriba <vicente.botet <at> wanadoo.fr> writes:
* The move constructor is not noexcept.
An implementation using vector<optional<T>> should avoid this last issue. Or just a pointer to array, which is somewhat more efficient. Why not. Well, on second thought this is not that easy. Moving from a to b must leave a in a *valid* position, which here means that either you must allocate a new array for a (which makes moving non-noexcept) or assign it a null pointer and deal with the situation in the rest of the interface, which is a kind of a bummer --for instance, as having size()==N is an invariant of the class, even const functions such as cbegin() or cend() need to check for null pointer and allocate accordingly, becoming non-nonexcept, thread unsafe and whatnot.
So, I think your deign shouldn't try to be move-aware, much as std::array is not either.
I'm one of those that think that the single things we are able to do with a moved variable is reassigning and destroying :(. Vicente
participants (2)
-
Joaquin M Lopez Munoz -
Vicente J. Botet Escriba