[boost] [gsoc16] Sparse hash table idea (was: Re: [gsoc16] Re: Potential contribution scenarios?)

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