Message5846

Author jendrik
Recipients andrew.coles, erez, florian, jendrik, malte, silvia
Date 2016-12-05.01:01:48
Content
Minor remark: the task tested in msg5843 is actually elevators-opt11-strips:p04.pddl. In 
revision issue213-base it uses 102 MB in a 32-bit build and 152 MB in a 64-bit build.

I have implemented a new hash table class using open addressing instead of chaining. It 
decreases peak memory usage to 80 MB in 32-bit builds and to 82 MB in 64-bit builds. 

A critical ingredient was a new hash function. The old hash function 
(utils/hash.h:hash_sequence()) produced too many collisions, resulting in a final load 
factor of 0.05 and using ~400 MB (peak memory). Switching to Jenkins' one-at-a-time hash 
function (https://en.wikipedia.org/wiki/Jenkins_hash_function) increased the final load 
factor to 0.79.

Since coming up with his one-at-a-time hash function, Jenkins has released multiple 
improved hash functions under the public domain. I will try hashword() from
http://www.burtleburtle.net/bob/c/lookup3.c tomorrow. This seems to be one of the best 
non-cryptographic hash functions for variable-length integer sequences. He has also 
released SpookyHash, but it only works for 64-bit builds.

It would be great if someone could have a look at the implementation of IntHashMap. I 
opened a pull request at https://bitbucket.org/jendrikseipp/downward/pull-requests/63 .
History
Date User Action Args
2016-12-05 01:01:48jendriksetmessageid: <1480896108.2.0.647416652937.issue213@unibas.ch>
2016-12-05 01:01:48jendriksetrecipients: + jendrik, malte, erez, andrew.coles, silvia, florian
2016-12-05 01:01:48jendriklinkissue213 messages
2016-12-05 01:01:48jendrikcreate