Message5872

Author jendrik
Recipients andrew.coles, erez, florian, jendrik, malte, silvia
Date 2016-12-14.01:33:41
Content
I analyzed and tweaked the code a bit and was able to speed it up while preserving the same memory 
usage. The most important change was to not sort the old buckets during a resize. Previously, I 
was trying to be smart about this to achieve a better layout, but the extra effort didn't pay off. 
In fact, experiments showed that the order in which buckets are reinserted, doesn't affect memory 
usage or runtime.

The resulting code version is tagged revision v5. Here are the results comparing v5 to v1, the 
version using std::unordered_map:

http://ai.cs.unibas.ch/_tmp_files/seipp/issue213-issue213-v1-vs-issue213-v5-release32.html
http://ai.cs.unibas.ch/_tmp_files/seipp/issue213-issue213-v1-vs-issue213-v5-release64.html

-> Memory usage and runtime decrease for both 32- and 64-bit mode. The effect is more pronounced 
for memory. Coverage goes up by 7 and 18 tasks.

http://ai.cs.unibas.ch/_tmp_files/seipp/issue213-release32-vs-release64-issue213-v1.html

-> With std::unordered_set, m64 solves 11 fewer tasks than m32. As we know, this is due to m64 
using much more memory than m32 in v1.

http://ai.cs.unibas.ch/_tmp_files/seipp/issue213-release32-vs-release64-issue213-v5.html

-> m64 still uses more memory than m32, but this can't be due to the hash set since it should uses 
the same amount of memory in both settings. The runtimes are about the same on average. Both build 
types solve the same number of tasks.

In light of these results, I suggest we polish and merge this hash table implementation, before we 
try to come up with fancier versions :-) What do you think?
History
Date User Action Args
2016-12-14 01:33:41jendriksetmessageid: <1481675621.79.0.146482392213.issue213@unibas.ch>
2016-12-14 01:33:41jendriksetrecipients: + jendrik, malte, erez, andrew.coles, silvia, florian
2016-12-14 01:33:41jendriklinkissue213 messages
2016-12-14 01:33:41jendrikcreate