[scala-internals] HashSet improvements

[Rüdiger Klaehn]

Hi all,

I have started implementing some structural sharing and performance improvements in HashSet. The basic contains/apply method is pretty good, but there is a lot of room for improvement for operations that take two sets as arguments, such as
union, intersection, diff, subsetOf. Filter can also be improved to reuse the original tree as much as possible.

Since this is a bigger change, I made a little toy project on github containing the new implementation of the HashSet operations as well as tests and caliper benchmarks.

Here it is:
https://github.com/rklaehn/hashset

Here are some results from the caliper benchmark. subsetOf is the only method I have fully optimized. Set.subsetOf is quite important since it is used for set equality.

As you can see the new implementation is orders of magnitude faster than the old one, which is not surprising if you consider that you sometimes just have to do a bitmap operation where the old method calls contains for every single element of the set!

The benchmark suite is quite comprehensive. It covers {subsetof, diff, intersection, union} for four different data types {int, string, collision and vector} and different overlap between the sets. An offset of 0 means that the two sets are identical, whereas an offset of 1 means that there is no overlap.

The types are to test different things you might want to put into a set:  Int has extremely fast hashcode and equals. String has fast hashcode but slow equals. collision is designed to produce a lot of hash code collisions, and vector has slow hashcode and slow equals.

In the benchmark result below I have disabled everything except int subsetof tests, because otherwise the benchmark takes hours. The other operations (union, intersection, diff and filter) are also already implemented, but they are sometimes slower than the current version, so obviously they still need some tweaking.

cheers,

Rüdiger

---

[info]
[info] offset size collectionType       ns linear runtime
[info]      0    2       hashset2    12.31 =
[info]      0    2        hashset    29.26 =
[info]      0   10       hashset2    46.67 =
[info]      0   10        hashset   102.80 =
[info]      0  100       hashset2  1208.46 =
[info]      0  100        hashset  2033.84 =
[info]      0 1000       hashset2 13869.10 ============
[info]      0 1000        hashset 32112.92 ==============================
[info]   0.33    2       hashset2    12.19 =
[info]   0.33    2        hashset    30.07 =
[info]   0.33   10       hashset2     1.41 =
[info]   0.33   10        hashset    17.29 =
[info]   0.33  100       hashset2    10.99 =
[info]   0.33  100        hashset    44.82 =
[info]   0.33 1000       hashset2    10.92 =
[info]   0.33 1000        hashset   116.69 =
[info]   0.66    2       hashset2     1.40 =
[info]   0.66    2        hashset    16.87 =
[info]   0.66   10       hashset2     1.43 =
[info]   0.66   10        hashset    16.93 =
[info]   0.66  100       hashset2     1.41 =
[info]   0.66  100        hashset    48.35 =
[info]   0.66 1000       hashset2    10.93 =
[info]   0.66 1000        hashset    42.11 =
[info]      1    2       hashset2     1.40 =
[info]      1    2        hashset    17.63 =
[info]      1   10       hashset2     1.40 =
[info]      1   10        hashset    16.97 =
[info]      1  100       hashset2    11.05 =
[info]      1  100        hashset    26.93 =
[info]      1 1000       hashset2    10.92 =
[info]      1 1000        hashset    31.88 =
[info]
[info] vm: java
[info] trial: 0
[info] benchmark: SubsetOf
[info] keyType: int
[info]
[info] View current and previous benchmark results online:
[info]   http://microbenchmarks.appspot.com/run/rkl...@gmail.com/SetBenchmark
[info]
[info] Writing results to /home/rklaehn/projects_git/rklaehn/hashset/caliper-results/SetBenchmark.2013

[Rex Kerr]

Are there plans to get mutable HashSet/Map up to speed also?  The 3x performance loss over mutable Java HashMap is not a particularly appealing feature of the current implementation.

  --Rex

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Rüdiger Klaehn]

Not that I know of. I have not looked at them yet. I am pretty sure that they do not implement Set/set operations either.

I just have a need for fast immutable HashSet and HashMap bulk operations for a project at work. And my personal goal is to get the immutable collections so fast that you never need to use mutable collections in the first place.

cheers,

Rüdiger

[Erik Osheim]

On Sat, Mar 30, 2013 at 12:46:05PM -0400, Rex Kerr wrote:
> Are there plans to get mutable HashSet/Map up to speed also? The 3x
> performance loss over mutable Java HashMap is not a particularly appealing
> feature of the current implementation.

Once I get this IntSet change going, I may see what I can do about
mutable HashSet/HashMap also. I strongly suspect I can improve on them.

-- Erik

[Rex Kerr]

You should probably benchmark against Java's mutable HashSet then, so you know when you're close enough to "never".  For small integer sets, Scala's immutable sets are about 2.5x slower than Java (which are in turn about 2.5x slower than Erik's full-range IntSet from the Symbol Set thread).

  --Rex

[Rex Kerr]

I certainly hope so!  I already did speed them up by ~2x, but it required interface changes in HashTable to help avoid breaking/remaking tuples all over the place, so I didn't pursue it.  (This was back in 2.8 days, IIRC.)  Actually making the performance-enhancing changes was the fast and easy part; chasing down the consequences in the rest of the library and benchmarking everything else was more than I had time for.

  --Rex

P.S. If you have adequate free time and motivation, and some indication that it'll make it into the 2.11 collections library, how about a high-performance mutable tree, also?  Nathan Bronson worked a bit on a fat-leafed tree that seemed very promising, though neither he nor I ever followed it up.  His code is at
  https://github.com/nbronson/mmt/blob/master/src/main/scala/mmt/FatLeafTree.scala

[Simon Ochsenreither]

I certainly hope so!  I already did speed them up by ~2x, but it required interface changes in HashTable to help avoid breaking/remaking tuples all over the place, so I didn't pursue it.  (This was back in 2.8 days, IIRC.)  Actually making the performance-enhancing changes was the fast and easy part; chasing down the consequences in the rest of the library and benchmarking everything else was more than I had time for.

P.S. If you have adequate free time and motivation, and some indication that it'll make it into the 2.11 collections library, how about a high-performance mutable tree, also?  Nathan Bronson worked a bit on a fat-leafed tree that seemed very promising, though neither he nor I ever followed it up.  His code is at
  https://github.com/nbronson/mmt/blob/master/src/main/scala/mmt/FatLeafTree.scala

Regarding the immutable Sets ... did anyone look into perfect hashing, which would enable O(1) search in the worst-case? Considering that the requirements for perfect hashing are pretty much fulfilled by the existing immutability guarantees already, this could improve performance in cases were the Sets change only rarely and lookups are performed often.

[Nils Kilden-Pedersen]

I don't know enough about the math behind perfect hashing to know if this is a general issue, but I've worked with one implementation a couple of years ago, and we found that hash calculation itself was prohibitively slow. It was about 6 times slower on lookup, but of course had great memory efficiency.
 

[Josh Suereth]

Yeah, don't knock hash computation time.   I know big companies that spend money investigating faster hash generation algorithms.

When it comes to collections, the best way to improve performance is a robust set of tests across a variety of architectures so we can get a notion of which variables are important.  O notation, usually being a suboptimal indicator these days.