These are chat archives for symengine/symengine

4th
Dec 2015
Ralf Stephan
@rwst
Dec 04 2015 08:36
I'm wondering if this might be interesting for symengine and/or piranha polynomials: http://stackoverflow.com/questions/3300525/super-high-performance-c-c-hash-map-table-dictionary esp. the Google and Judy links.
Ondřej Čertík
@certik
Dec 04 2015 15:49
@rwst See also #117 which has several links to hash table implementations that I found.
Francesco Biscani
@bluescarni
Dec 04 2015 19:53
@rwst I did a lot of experiments in Piranha regarding data structures. Earlier versions could use a binary tree instead of the hash table, then I became convinced that a hashed structure would offer better performance. Initially I tested a few ready-made implementations: GCC's ext/hash_table (this was pre-C++11), Boost's hash table and multi-index container, unordered_set/map
then I started thinking about implementing my own version of a hash table, when it became clear that this could offer substantial benefits performance-wise
I experimented with implementations based on classic open-addressing and chaining, then experimented a bit more with things like cuckoo hashing (https://en.wikipedia.org/wiki/Cuckoo_hashing) and hopscotch hashing (https://en.wikipedia.org/wiki/Hopscotch_hashing)
Francesco Biscani
@bluescarni
Dec 04 2015 20:06
In the end I settled on the current design, which is basically a classical chaining hash table in which the first element of each bucket is stored inline
there are a lot of different and sometimes conflicting design decision that one can make, what ultimately mattered to me was that 1) the implementation supported parallel operations (at least under certain restricted circumstances) 2) and the implementation was cache-friendly
Francesco Biscani
@bluescarni
Dec 04 2015 20:18
the good thing is that it is relatively easy to write a poly manipulation benchmark using a new hash table implementation
@Sumith1896 did it during the last GSOC if I recall correctly