HPPC-RT v0.6.5 stable released on Maven

[Vincent Sonnier]

Hello everyone,

It's here.

I've finally decided to release on Maven a stable version, labelled v0.6.5. Compared to the previous snapshot v0.6.0
there is not so much novelties in API but rather refactorings and internal changes :

A) Some repackaging was done to use com.carrotsearch.hpprt.[sets|lists|maps|heaps|strategies..] for the sake of housekeeping,

B) Strategies were extracted from the Hash containers to create their own CustomHash classes, (à la fastutil) so that we keep the maximum perfomance
for the most frequently used containers.

C) Much experiments this summer as lead to adopt Robin Hood hashing as self-reorganizing algorithm for the containers using either Objects or CustomHashs.
First, I heard of it from Cliff Moon, who submitted a pull request to the regular HPPC,
then I read this http://sebastiansylvan.com/2013/05/08/robin-hood-hashing-should-be-your-default-hash-table-implementation/ which is indeed
the best consise explanation I've found about Robin Hood hashing,
Then I stumbled upon a very deep analysis by Emmanuel Goossaert (http://codecapsule.com/tag/robin-hood/) which demonstrate experimentally
the very low variance in various access patterns of this design. (lots of drawings, graphics, great series of articles in my opinion)
Then of course, I've benchmarked my own implementation adding over Cliff Moon's a caching of hash values.

Someone said once "there are lies, damn lies, and benchmarks" but still  Robin Hood proved usefull showing its expected consistent behaviour even
in poor hash qualities and most of all in case of lookups on absent keys where traditional linear lookup times skyrocket, but where by construction RH
has a fast bailout test before actually reaching an empty slot.

All of this have a cost, in such that put() is slower than before but the overrall operations looks smoother (if a fraction slower) which is actually what counts in a realtime environnement.
 
However, due to the pure raw power of CPU caching and prefetching in a brute force search, RH is not so intresting for pure primitive containers and wasn't enabled for them in v0.6.5.

D) As optimization, I removed the perturbation of hash containers (introdued to fix HPPC-80) replacing them by an iterator going "in reverse" of the buffer.
Once again benchmarks (a.k.a lies) showed that we actually re-gain the performance of the non-perturbated containers in the general case, still keeping the putAll() as fast as it was with the perturbated version.
The strange thing is that the self-resizing methods of the hash containers expandAndXXX() actually already did traverse the buffer in reverse to rebuild the expanded container, showing that it was probably found interesting to do so...

And yes I finally get into the trouble of releasing it on Maven for everybody: <dependency> <groupId>com.github.vsonnier</groupId> <artifactId>hppcrt</artifactId> <version>0.6.5</version> </dependency>

Regards,

Vincent

 

[Dawid Weiss]

Thanks for the update, Vincent! You're stealing my thunder, man! :)

As for perturbation of hash containers; you see part of the motivation to introduce it was that folks may not be aware of the consequences of a linear scan/ copying to another hash container. So if they're not using putAll, but are looping manually or are using any other iteration method (forEach, etc.) then they'll still observe the nasty consequences that happen when the allocation in every hash container is the same.  Looping backwards is a clever trick to work around the problem, but overall I think I'll keep the perturbations in HPPC for "safety" reasons. By the way -- the existing code used it only because I used to write a lot of assembly and it seems more natural there; it wasn't an intentional workaround for the collisions issue.

Dawid

--
You received this message because you are subscribed to the Google Groups "High Performance Primitive Collections for Java" group.
To unsubscribe from this group and stop receiving emails from it, send an email to java-high-performance-primi...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Vincent Sonnier]

Thank you for your input, Dawid.

I think I'll add "reverse" iteration for the forEach() then and add a big warning in Javadoc buffer[] for direct iteration dangers.

I'll probably also enhanced the iteration and putAll()  benchmarks to show the differences in forward vs. backward direct iterations and such.

Vincent

To unsubscribe from this group and stop receiving emails from it, send an email to java-high-performance-primitive-collections+unsub...@googlegroups.com.

[Roman Leventov]

I don't know how do you measure, but I haven't found robin-hood better than simple linear. You can see my comments to this article: http://codecapsule.com/2014/05/07/implementing-a-key-value-store-part-6-open-addressing-hash-tables

четверг, 21 августа 2014 г., 12:38:52 UTC+4 пользователь Vincent Sonnier написал:

[Vincent Sonnier]

Hello Roman,

Indeed RH performance is not visible in case of primitives (or "inlined" structs in memory like in your OpenHFT implem ?) , where cache locality prevail. When keys are objects, from the moment the hash() is non trivial and heavy to compute (remember my implem cache the hashes) on objects all around the place in memory, some advange appears even if the put() is quite slower.

The most visible case is when the get() == false, where the test chain on linear depends on the first free bucket, which overshoots rapidly.

As described on the first post, the "Realtime" goal is the search of the most consistent execution time even in worst case inputs, not raw power in some favorable cases. Besides, not everybody is on Oracle JDK with nice inlining and optimizations, so that it is a clear win to reduce the number of total calls of equals() and hashCode()  operations on objects.

As for the "damn lie" benchamark, here is the particular benchmark I made: (pure JDK, no dep)

 https://github.com/vsonnier/hppc/blob/0.65.x-RT-release/hppcrt-benchmarks/src/main/java/com/carrotsearch/hppcrt/misc/HppcMapSyntheticBench.java

The goal is to work with various inputs, on a big enough sample that especially DO NOT fit in the cache.

Voilà

Vincent