Maps speed comparisons

[Arthur Milchior]

Hi,

Is there any benchmark to figure out at which point hash map becomes faster than tree based map? I tried to move Map<Long, Long> to Long2LongOpenHashMap, and according to my profiler, so much time is spent hashing longs that it's not a huge time gain as I expected. So I'll try with AVLtrees and with custom hashing to see what improvement I can get. However, if there were already some common knowledge helping to figure out when each class is best, it would be quite useful. 

 

Thanks again for this library.  In particular for adding pairs so quickly !

Regards,

Arthur

[Sebastiano Vigna]

It's been a long time since I benchmarked the library, but what sizes are you considering? Each Map<Long, Long> entry needs three objects, whereas a Long2LongOpenHashMap needs none. The memory footprint is significantly smaller—an order of magnitude less space.

[Arthur Milchior]

Hi,

Sorry, I fear I was not clear. I wanted to compare LongOpenHashSet to
LongAVLTreeSet, LongRBTreeSet, and potentially LongOpenCustomHashSet,
where the strategy is to discard the most significant bits (assuming
values are really random).
My uses cases go for potentially hundred of thousands of sets and maps
with 10 to 100 elements each, up to maps with a million of element. To
be even more specific, I first create the set/map, then I look for
elements in it. I never delete.

Regards,
Arthur

> --
> You received this message because you are subscribed to the Google Groups "fastutil" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to fastutil+u...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/fastutil/71e680ad-1960-423e-9cc5-f3bfb344dcd6n%40googlegroups.com.

[Sebastiano Vigna]

With those numbers, you don't want maps with object entries for sure...

[Sebastiano Vigna]

FYI, this is a quick comparison between Map<Long,Long> and Long2LongOpenHashMap

java.util Put: 378.04ns Yes: 145.43ns No: 99.78ns Iter: 31.72ns RemNo: 104.39ns RemYes: 163.44K/s

fastutil  Put: 111.59ns Yes: 33.10ns No: 57.14ns Iter: 16.20ns RemNo: 76.42ns RemYes: 119.04ns

Yes/No are positive/negative contains(). I think 4-5 times faster and 5 times less space is acceptable...