High Performance Primitive Collections for Java

We have intergrated hppc and made good success after setting a constant HashOrderMixing as we really need iteration to be deterministic. Now I think we had a chat where you recommended against such a solution, unfortunately I cannot find it anymore.

But we found some more explanation here.

There are still a few things that I do not understand and maybe you can help us :) ?

Why is this (partial) copying into the same implementation such a big problem that the design of the collection is heavily influenced? It seems you even plan to introduce an iterationSeed in 0.9?

Is the deterministic iteration really the problem and not something "good"? Wouldn't it be better to solve the problem when adding many elements e.g. a special "addAll" method that takes the collection and the element count or some kind of an "Acceptor" or "Filter"? Then it can internally handle the cluster problem when copying into other collections and you can still maintain deterministic iteration.

We probably have too seldom uses where we (partially) copy maps into other maps, but when exactly are those clusters created? Because as soon as the map has a different size the hashing should be different and the clustering should be less of a problem (?)

WormMap implements the same interfaces as HashMap. But not all of the methods function in the same way.

1. Currently, there is no key distribution visualization, so visualizeKeyDistribution() throws an exception if called.
2. WormMap doesn't have a constant load factor, this is why the ensureCapacity() method is not 100% accurate.

Some of the methods that don't exist in hppc HashMap:

1. remove(KType key, VType value)
2. removeValue(VType value)
3. containsValue(VType value)
4. trimToSize()
5. getLoad()

A read-only view with sorted-iteration on a delegate KTypeVTypeHashMap.

• The template generation works. I added Intrinsics.compare.
• The assertion to verify the delegate map didn't change is minimal.
• Minimal set of tests. Will put more tests after the first discussion on this sorted-iteration view.
• I refactored a bit KTypeVTypeXyzMapTest by introducing AbstractKTypeVTypeTest to move duplicated helper methods there.

I don't expect this PR to be merged as such, since I'm pretty sure it's not in the direct goals of this library. However, I would really love some pointers and possibly a review of some sort if possible. Thanks!

The goal is to make the hash map thread safe, for most use cases. So far, I've been able to work through the puts, gets, removals, updates, and other point based operations.

One caveat that I can think of is the iteration. My goal was to provide a lock free iteration, which may or may not have the latest values. The idea is to capture the state as of the moment that the iteration starts (keys, values, and mask). Doing so allows me to allow for all other point based map operations to work without waiting for the iteration to complete. Apart from having stale entries, there is one other and potentially more concerning:

• When the remove operation invokes shiftConflictingKeys, the position of entries would jump, making the iteration less reliable

Apart from that caveat mentioned above, are there any other worth considering?

My larger goal is to make the iteration "eventually consistent".

Thank you!

In the case of SortedIterationKTypeVTypeHashMap, we want to sort the key set of a delegate hash map. We know there are no duplicate keys, and they are randomly distributed, and we don't need to have a stable sort. Hence it is a good case to use an in-place Quick sort instead of IndirectSort merge sort (which needs a copy of the source array).

So with this change, SortedIterationKTypeVTypeHashMap sorts with in-place quick sort. It is faster and does not require a clone of the indices array anymore.

This new QuickSort implementation, with 3-way partitioning, works on a provided comparator and also a provided swapper.

• The comparator is different than the one in IndirectSort because it receives the indices of the elements to compare (not the value of the indirect indices-array). So it can be used for both direct and indirect sorting. (It is used for indirect sorting in SortedIterationKTypeVTypeHashMap, and for direct sorting in SortTest)
• The swapper interface has two benefits. It allows the sort implementation to not depend on the array type anymore. And it also allows the caller to provide a custom swapper, able for example to swap the elements of two arrays at the same time. (Useful when we have two simple arrays for keys and values and we sort the keys while the values follow, then we can do a binary search on the keys, very compact)

I extracted the sort certification code from IndirectSortTest to move it to a new SortTest, which now tests both IndirectSort and QuickSort.

There are cases where we want a HashMap with iteration in sorted order. In those cases we can use the JDK TreeMap, but it uses more memory and provides slower O(log(N)) #get as well as slower iteration (2x slower than JDK HashMap in my benchmark). Often the TreeMap is built once and is not modified afterward, in this case TreeMap is not really advantageous.

There could be an opportunity to have a SortedHashMap based on HPPC HashMap (open-addressing). It would require to extend HPPC HashMap and have a int[] orderArray sorted using HPPC IndirectSort (it could even sort on values). If the orderArray is built once and reused (for example discarded only if the map is modified, which does not happen in the use-case I describe), then such a map requires much less memory and provides O(1) #get and fast iteration.

But such a map has a fixed iteration order! So we get into big perf issue if we iterate it to add to another HPPC HashMap.

So here is my question: Would it fit into HPPC with a warning that it must not be used to copy to another map (the same warning as ScatterMap had), or is it too dangerous or too exotic to fit?

Summary

• This is a micro optimisation for when equals is called with a reference to the same object
• This is to avoid having consumers of equals performing this check themselves

Outstanding Concerns

Not sure how sensitive this code path will be to the extra branch. I would guess that it's fairly branch predictor friendly.

I implemented robin hood hashing using the existing open hash map and the algorithm discussed here: http://sebastiansylvan.com/2013/05/08/robin-hood-hashing-should-be-your-default-hash-table-implementation/.

Removes are still done via the shiftConflicingKeys method. As discussed here http://sebastiansylvan.com/2013/08/05/more-on-robin-hood-hashing-2/ doing tombstones leads to long probe lengths when there are many removes and inserts of the same key. This shows up pretty well in the test suite. The existing shift scheme seems to be correct so I simply reused that.

Would like to do some performance testing and some comparison of probe length variance between this and the open hash map implementation.

Hi!

We notice that you use the loop structure in your test cases. For example, testPutWithExpansions() in KTypeVTypeWormMapTest.java

However, using the loop in test cases is not a good test practice. We analyzed the relevant Stack Overflow posts and summarized four potential negatives it brings:

1. Loops make the test case more complex.
2. In most cases, a loop can be replaced with a data-driven test that is more readable.
3. Loops break the assert-for-one-thing thumb rule. I don't mean a single assert statement.
4. When a test fails, knowing the reason is more complicated. Solution: To avoid using the loop in the test, JUnit provides an annotation (i.e., @ParameteredTest), enabling a test case to run multiple times with different parameters. We provide a usage example here:

New API method KTypeVTypeMap.indexRemove() + implementation in KTypeVTypeHashMap and KTypeVTypeWormMap.

New public method indexRemove() in KTypeHashSet and KTypeWormSet.

• tests

To add a test, I modified HppcExample_004_IteratingOverMaps to also use a WormMap. I don't know if it is too specific for a simple high-level example. Maybe there is another test to verify the public visibility?

This would make the API nicer, as it allow lambda notation, as well as method handles. Feel free to squash this pull into one commit, but I edited the files in github, and that committed one file at a time.

E.g. instead of

list.forEach(new IntProcedure() {
	@Override
	public void apply(int value) {
		blackhole.consume(value);
	}
});

one could then write

list.forEach(blackhole::consume);

or

list.forEach(x -> blackhole.consume(x));