Message3882

Author andrew.coles
Recipients andrew.coles, erez, florian, jendrik, malte, silvia
Date 2014-10-27.14:01:11
Content
(Background:

The standard hash_set implementation is a hashtable.  The hashtable is stored as
a std::vector, where each index contains a singly-linked list: an item of data,
and a 'next' pointer to the next item in the list. )

It's also possible to represent the lists in each bucket of a hash set by moving
the next pointer into the state.  Normally this wouldn't be done -- we can only
have one hash set implemented in this way -- but the state registry is special.
 In implementation terms, this can be done by making the PackedStateBin one int
larger, and instead of storing the 'next' entry as a pointer, store it as the
StateID of the next state.  The hash bucket themselves are then StateIDs: -1 if
empty, or the StateID of the first state on the list of states in that bucket.

Storing 'next' as part of the PackedStateBin gives a 25% reduction in memory
usage on 32-bit builds - see attached state_registry_low_memory.tar.gz.  The
downside is a drop in performance: blind search is a factor of 2 to 3 slower. 
(This surprised me, and might be improvable with some profiling.)  The % time
overhead would of course be lower with something other than blind search.
Files
File name Uploaded
state_registry_low_memory.tar.gz andrew.coles, 2014-10-27.14:01:11
History
Date User Action Args
2014-10-27 14:01:11andrew.colessetmessageid: <1414414871.33.0.153528807071.issue213@unibas.ch>
2014-10-27 14:01:11andrew.colessetrecipients: + andrew.coles, malte, erez, silvia, jendrik, florian
2014-10-27 14:01:11andrew.coleslinkissue213 messages
2014-10-27 14:01:11andrew.colescreate