|
|
Boost : |
Subject: [boost] [gsoc16] Sparse hash table idea (was: Re: [gsoc16] Re: Potential contribution scenarios?)
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2016-01-06 06:13:43
On 5 Jan 2016 at 17:52, Miguel Coimbra wrote:
> > 1. A thing Boost really could do with is a decent (optionally
> > mmappable) dense hash map implementation, so the hash map could
> > contain billions of items and mostly reside on disk yet lookups would
> > still be very fast.
>
> I have some questions regarding this first idea. I believe a concept and
> implementation already exist and are actually in use at Google:
>
> http://goog-sparsehash.sourceforge.net/doc/dense_hash_map.html
>
> [snip]
>
> So what you want is something like this, but able to "contain billions
> of items and mostly reside on disk yet lookups would still be very fast"?
>
> I assume the "billions of items" is what is lacking from that
> dense_hash_map already in use by Google? Is this the difference between
> that and your idea?
Not exactly.
Google's dense hash map just happens to be at the top of the search
results which reveal many implementations of dense hash maps, but the
algorithm itself is much older and could even be considered widely
used. I've certainly written a few of them in my professional career,
and I would assume so have most people here because they are the
easiest quick and dirty map implementation.
The reason a dense hash map isn't already in Boost I would suggest is
probably due to lack of genericity, or rather, once you implement a
dense hash map of the form:
template<class Key, class T, class Hash, class Pred, class Allocator>
class dense_hash_map;
... where Key and T can be any type, you end up with something with
very similar characteristics to std::unordered_map<>, and therefore
adding it to Boost is not compelling compared to say a bitwise or
judy trie STL container which has at least a few compelling
differences in characteristics to a hash table.
Anyone can make a container which beats the STL containers for some
limited use case. Few can make a totally generic general purpose
container which clearly beats the STL containers in a majority of use
cases unless you radically rethink semantics (like say Eric is doing
in Ranges v3, or Boost.Intrusive).
> Assuming this is indeed what you were proposing, would the work
> encompass defining an API and also exploring mmap for lazy iteration for
> performance gains in the context of handling billions of items?
Personally speaking - and please anyone with an opinion reading can
chime in here - I don't find a straight swap of unordered_map for a
dense_hash_map compelling.
I *do* find the dense hash map algorithm applied to something it's
uniquely good at much more compelling. One idea is really, really
huge maps which greatly exceed physical RAM. Another idea is a
constexpr compile time generated static map which is also a dense
hash map generated via C++ 14 constexpr programming. There are other
interesting applications of the dense hash map algorithm which maybe
list members might suggest here.
Niall
---
Boost C++ Libraries Google Summer of Code 2016 admin
https://svn.boost.org/trac/boost/wiki/SoC2016
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk