www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - A few assiociative arrays measurements

reply Guillaume Piolat <first.name gmail.com> writes:
Lately, I got a large speed-up using a N-heap rather than a 
binary heap in a priority queue. But it's not the only binary 
trees I had, Phobos' Red-Black tree is like that.

Could we stuff more items per tree node?
As memory gets relatively more expensive than CPU, does that wins 
some precious cycles?

Looking at the Map I was using, I've compared a few different 
equivalent for string[int] / Map!(int, string) / associative 
arrays.
  - one is the regular builtin AA, a hashmap (druntime)
  - one is based upon Phobos red-black tree (rbtree.d), adapted to 
use manual allocation
  - one is based on a new Boost-licensed, B-tree implementation in 
Dplug (btree.d)
  - one is the TreeMap in emsi-container package, itself using a 
T-Tree (treemap.d, ttree.d)

The results are summed up in this presentation: 
https://dplug.org/tutorials/Dplug%20Tutorials%2018%20-%20The%20Case%20Against%20Binary%20Trees.pdf

Notes:
- For an in-memory collection, a B-Tree seems generally more 
performant than a Red-Black tree nowadays. In fact I believe any 
tree with more than 2 children will outperform a tree with only 2 
children per node.
- However Red-Black Tree are used because C++ std::map must be 
able to insert without invalidating existing iterators. It's 
possible with RB-Tree but not B-Tree.
- In my benchmarks I don't understand why `emsi_containers` 
T-Tree act like this at look-up; it looks slower than one could 
expect. Bug? So I wasn't able to rightfully compare T-Tree with 
B-Tree. It shouldn't be the GC, but possibly it's adding the GC 
roots that do this?
- builtin AA uses a lot of tricks in the book and, as a hashmap, 
can outperform the others who are instead sorted collections. But 
not necessarily at look-up.
Feb 08
parent Guillaume Piolat <first.name gmail.com> writes:
Benchmark sources:
https://u.pcloud.link/publink/show?code=XZces50ZpM2M8JbPyebvB5LqzspF2u2g4Jqk
Feb 08