search

mdedetrich / linked-map

Provides an implementation for an immutable map that maintains key ordering
BSD 3-Clause "New" or "Revised" License
3 stars 0 forks source link

Use specialization higher than 4 #2

Open mdedetrich opened 6 years ago

mdedetrich commented 6 years ago

The current VectorMap implementation copies the same method of specialization as HashMap which specializes up until arity 4.

As can be seen by the basic jmh benchmarks, LinkedMap is a non trivial amount slower than a HashMap when we are no longer specialized (~30%) so it may be useful to increase the specialisation (just for LinkedMap) to be a bit higher, maybe up to 8 or even 10?

I am not completely aware of the downsides of this, @Ichoran would you be able to comment?

Ichoran commented 6 years ago

The downside is multiple dispatch to the different implementations. It's very unlikely that you want to have 10 different classes "for performance" because in a case with mixed sizes, it will probably make everything quite a bit slower. It may be good to have a single class that handles more than one fixed size to partially get around the dispatch penalty. (You still effectively have to pay it within that class as you dispatch to the different sizes there, but at least you keep that from impacting the performance of larger sizes.)

mdedetrich commented 6 years ago

Would using final get around the multiple dispatch issue? I actually think I already hit this issue (when I noticed a performance difference between from Map specialized vs VectorMap specialized which was fixed in this commit here https://github.com/mdedetrich/linked-map/commit/37026492c3e2a3a85bd00638e4c626a475e20f16). I also suspect that since VectorMap is slow due its implementation, it would be faster even when considering multiple dispatch penalty.

Also do you know if there is any theory as to why 4 was selected as a specialization size for Map?

Ichoran commented 6 years ago

final doesn't much help because it actually has to dispatch to several different targets. (The JIT compiler is pretty good about figuring out what is "effectively final".)

I'm assuming that 4 was selected due to benchmarking, but I wasn't involved in that.

mdedetrich commented 6 years ago

Okay thanks, I will see what I can do to improve the specialization more now that I have something basic for regression tests. I am guessing that https://github.com/scala/collection-strawman/tree/master/benchmarks/time/src/main/scala/strawman/collection/immutable is a good reference on the type of benchmarks I should be writing?

Ichoran commented 6 years ago

In general, yes, but they're not always designed to explore the performance penalty of multiple dispatch. In that case you have to test operations on a set of small collections of different sizes.