[containers] Addition of a dense map implementation

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

[containers] Addition of a dense map implementation

Boost - Dev mailing list
Hi,

While working on different projects in which performance is key, I came to realize that the efficiency of the
associative containers that are available in the STL can be improved.

For instance, it is well know that neither std::unordered_map nor std::map are cache-friendly.

It isn't that hard to find implementations that are faster, for instance flat_map, already in Boost.Containers.
However, I would be interested in another implementation, a "Dense Map", similar to the one we can find in SparseHash
(https://github.com/sparsehash/sparsehash) or in LLVM's ADT (https://llvm.org/doxygen/DenseMap_8h.html).
For sure I am not the only one attracted to such implementation, as we can find several ones in the internet, although,
it really lacks of "one true generic implementation". SparseHash doesn't seem that maintained anymore and, well, LLVM is
LLVM.

Hence, instead of having yet another implementation of my own, I would rather have one in Boost, to ensure long-term
maintainability.

I know that this particular subject was kind of already discussed in this thread from 2016
(https://lists.boost.org/Archives/boost//2016/01/227076.php) and some very good points were made.
But in the end, years have passed, and we still don't have an alternative, so in my opinion an implementation in Boost
would actually be something to consider.

Please let me know what you think about that.
I am open to any other ideas, and in case we agree on the addition of a new implementation, I would actually be pleased
to contribute.

Best regards,
Jeremy Junac

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [containers] Addition of a dense map implementation

Boost - Dev mailing list
I have little to comment except to suggest you should track your
performance compared to abseil flat_hash_*

On Mon, Jun 29, 2020 at 10:39 PM Jeremy Junac via Boost <
[hidden email]> wrote:

> Hi,
>
> While working on different projects in which performance is key, I came to
> realize that the efficiency of the
> associative containers that are available in the STL can be improved.
>
> For instance, it is well know that neither std::unordered_map nor std::map
> are cache-friendly.
>
> It isn't that hard to find implementations that are faster, for instance
> flat_map, already in Boost.Containers.
> However, I would be interested in another implementation, a "Dense Map",
> similar to the one we can find in SparseHash
> (https://github.com/sparsehash/sparsehash) or in LLVM's ADT (
> https://llvm.org/doxygen/DenseMap_8h.html).
> For sure I am not the only one attracted to such implementation, as we can
> find several ones in the internet, although,
> it really lacks of "one true generic implementation". SparseHash doesn't
> seem that maintained anymore and, well, LLVM is
> LLVM.
>
> Hence, instead of having yet another implementation of my own, I would
> rather have one in Boost, to ensure long-term
> maintainability.
>
> I know that this particular subject was kind of already discussed in this
> thread from 2016
> (https://lists.boost.org/Archives/boost//2016/01/227076.php) and some
> very good points were made.
> But in the end, years have passed, and we still don't have an alternative,
> so in my opinion an implementation in Boost
> would actually be something to consider.
>
> Please let me know what you think about that.
> I am open to any other ideas, and in case we agree on the addition of a
> new implementation, I would actually be pleased
> to contribute.
>
> Best regards,
> Jeremy Junac
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost