CompactHashMap

This puts me in mind of trove:
http://trove4j.sourceforge.net/html/benchmarks.shtml

Aren't those issues being solved in 2.8 with an annotation?

On Mon, May 4, 2009 at 5:13 PM, Channing Walton <channingwalton@mac.com> wrote:

This puts me in mind of trove:
http://trove4j.sourceforge.net/html/benchmarks.shtml
--
View this message in context: http://www.nabble.com/CompactHashMap-tp23358808p23376791.html
Sent from the Scala - User mailing list archive at Nabble.com.

I've just tested trove on String-to-String map and in my tests it is ~twice
slower than both java.util.HashMap and my map. And java version of my map
(optimized for speed not memory footprint) is ~10% faster than
java.util.HashMap.

Channing Walton wrote:
>
> This puts me in mind of trove:
> http://trove4j.sourceforge.net/html/benchmarks.shtml
>

On Monday May 18 2009, Alex Yakovlev wrote:
> Channing Walton wrote:
> > This puts me in mind of trove:
> > http://trove4j.sourceforge.net/html/benchmarks.shtml
>
> I've just tested trove on String-to-String map and in my tests it is
> ~twice slower than both java.util.HashMap and my map. And java
> version of my map (optimized for speed not memory footprint) is ~10%
> faster than java.util.HashMap.

Well, a lot can be hidden behind "in my tests."

In my experience (*) if the sets in question are small and short-lived,
Java's stock implementation is distinctly faster. For larger and
longer-lived sets, Trove wins.

If you look at the Trove implementation, you'll see that the set-up for
a Trove hash table is considerably more involved than for a Java
standard library hash table. So in any given instance, those costs have
to be made up for before using a Trove collection is a net win.

That is, of course, moot for things like the primitive collections, for
which there is no counterpart in the standard library (outside of using
boxed primitives).

(*) Profiling a real, set-heavy, computationally intensive application
in which all set allocation was funneled through a utility that had a
switch to allow any given test to be run with different Set
implementations.

Randall Schulz

There are several reasons why Trove is slower.
The main is that both java.util.HashMap and my map stores object's hash
codes in it's data structures.
Before comparing keys we first compare saved hashcode, and only if they are
equal - compare real keys.
In most cases there is no need to access real key and call its equals
method.
Second point is that these saved hashcodes are used in rehashing when map is
resized.
Trove implementation have to re-compute it at every rehash by calling
object's hashCode method.
There are some smaller tricks but these two are the most important for
perfomance, imho

Randall Schulz wrote:
>
> In my experience (*) if the sets in question are small and short-lived,
> Java's stock implementation is distinctly faster. For larger and
> longer-lived sets, Trove wins.
>

On Tue, 2009-05-19 at 00:25 -0700, Alex Yakovlev wrote:
> The main is that both java.util.HashMap and my map stores object's hash
> codes in it's data structures.

To be fair, Trove is most interesting for the primitive collections. In
those cases, saving the hashCode just wastes memory.

Best,
Ismael

Well, CompactHash'es are also optimized for primitive types.
Trove uses load factor of 50% so half of its internal arrays are just waste.
CompactHash'es uses load factor of 100% so they can hold twice more objects.
But for efficiency it uses an array of indices that hold 'linked lists' of
objects with the same hash code.
Hence when searching for object it will never look for wrong 'hash busket'.

Since that indices are ints, there usually are free bits where hashcode bits
can be stored for free.
But CompactHash'es are optimized for memory footprint, and on tiny map it
uses byte index array, for medium sized - array of short.
Changing array size is slow operation that requires recomputing real
hashCodes.
In Java version always int indices are used, hence it is faster.

So the memory footprint of 50% loaded Trove and 100% loaded CompactHash'es
is the same, but CompactHash'es is faster.

Ismael Juma wrote:
>
> On Tue, 2009-05-19 at 00:25 -0700, Alex Yakovlev wrote:
>> The main is that both java.util.HashMap and my map stores object's hash
>> codes in it's data structures.
>
> To be fair, Trove is most interesting for the primitive collections. In
> those cases, saving the hashCode just wastes memory.
>

On Tue, 2009-05-19 at 01:49 -0700, Alex Yakovlev wrote:
> Well, CompactHash'es are also optimized for primitive types.

Are we talking about the following?

http://github.com/alex14n/CompactHashMap/blob/115ded4e64fbfde7e6315ab821...

Before I look at it in more depth, can you please provide us with some
numbers (both space and speed) and the code you used to get them?

I see a lot of statements, but very little information on how to
reproduce them. :)

Best,
Ismael

Ismael,

I did not want to include my benchmark since it could be biased and I wanted
for my classes to be tested independently.
But here is what I currently use for benchmarking:
http://github.com/alex14n/CompactHashMap/blob/1c06b1b6326df9eb66d0f9f486...

it is infinite loop now and it currently compares only java versions, I
should rewritten it to have a limited number of iterations on different data
types. Hope it is clear what to (un)comment to test different cases, sorry
for it.

I also have not tested newly rewritten collections in 2.8 yet - looking at
its code it must be faster.

Alex.

Ismael Juma wrote:
>
> On Tue, 2009-05-19 at 01:49 -0700, Alex Yakovlev wrote:
>> Well, CompactHash'es are also optimized for primitive types.
>
> Are we talking about the following?
>
> http://github.com/alex14n/CompactHashMap/blob/115ded4e64fbfde7e6315ab821...
>
> Before I look at it in more depth, can you please provide us with some
> numbers (both space and speed) and the code you used to get them?
>
> I see a lot of statements, but very little information on how to
> reproduce them. :)
>

Hi Alex,

On Tue, 2009-05-19 at 02:30 -0700, Alex Yakovlev wrote:
> Ismael,
>
> I did not want to include my benchmark since it could be biased and I wanted
> for my classes to be tested independently.
> But here is what I currently use for benchmarking:
> http://github.com/alex14n/CompactHashMap/blob/1c06b1b6326df9eb66d0f9f486...

As far as I can see, you don't use any of the Trove maps specialised for
primitives (e.g. TIntIntHashMap, etc.). That is the case where Trove
does well. It trades convenience for no boxing overhead (space or time).

Best,
Ismael

TIntIntHashMap is still slower, but its mem footprint is lower: 28Mb vs. 32Mb

http://github.com/alex14n/CompactHashMap/blob/411e443810a2e40198e43e1cd2...

Ismael Juma wrote:
>
> As far as I can see, you don't use any of the Trove maps specialised for
> primitives (e.g. TIntIntHashMap, etc.). That is the case where Trove
> does well. It trades convenience for no boxing overhead (space or time).
>

On Tue, 2009-05-19 at 03:00 -0700, Alex Yakovlev wrote:
> TIntIntHashMap is still slower, but its mem footprint is lower: 28Mb vs. 32Mb
>
> http://github.com/alex14n/CompactHashMap/blob/411e443810a2e40198e43e1cd2...

I didn't test the other maps, but I did test TIntIntHashMap versus
THashMap and my results are different from yours after a suitable
warm-up (I changed the times to be reported in ms):

troveWrite - 626; Mem: 105.77 Mb
troveReadFull - 72; Mem: 105.89 Mb
troveReadEmpty - 55; Mem: 12.20 Mb

troveIntWrite - 266; Mem: 39.98 Mb
troveIntReadFull - 99; Mem: 39.98 Mb
troveIntReadEmpty - 12; Mem: 11.72 Mb

So, THashMap is many times slower for writes and empty reads than
TIntIntHashMap. Also, the memory footprint is very different (I am using
a 64-bit JVM JDK6u14 on Linux). The likely reason for the slower reads
are that TIntIntHashMap needs to access a byte[] to check the state of
the bucket. This may be causing cache misses.

Still, the benchmark is currently very artificial as it does sequential
gets. Do the numbers remain the same if the keys are random instead of
sequential? What about with different map sizes ? What about a mixture
of gets and puts? And so forth.

Finally, it's worth pointing out that this method of measuring memory is
not particularly accurate in absolute terms as there are other objects
in the JVM heap.

Best,
Ismael

On Tue, May 19, 2009 at 5:00 AM, Alex Yakovlev <alex14n@gmail.com> wrote:

TIntIntHashMap is still slower, but its mem footprint is lower: 28Mb vs. 32Mb

http://github.com/alex14n/CompactHashMap/blob/411e443810a2e40198e43e1cd20c535c6334d4e8/test/Benchmark.scala

You should also look at FastUtil. I've found it to be faster than Trove in almost every case.

http://fastutil.dsi.unimi.it/

Thanks for link, looks very interesting.
It has the smallest memory footprint (18Mb vs. 32Mb CompactHashMap and 28Mb
Trove),
It is 2-3 times faster on normal read/write operations,
but it is *VERY* slooow on finding non-existing keys:

fastutilIntWrite - 0.296; Mem: 18.34 Mb
fastutilIntReadFull - 0.125; Mem: 18.34 Mb
fastutilIntReadEmpty - 2.125; Mem: 0.34 Mb
compactWrite - 0.875; Mem: 32.47 Mb
compactReadFull - 0.296; Mem: 32.47 Mb
compactReadEmpty - 0.078; Mem: 0.47 Mb
troveIntWrite - 0.703; Mem: 28.63 Mb
troveIntReadFull - 0.328; Mem: 28.63 Mb
troveIntReadEmpty - 0.063; Mem: 0.37 Mb

http://github.com/alex14n/CompactHashMap/blob/d0a2771043400915285b774bbe...

Nils Kilden-Pedersen wrote:
>
> You should also look at FastUtil. I've found it to be faster than Trove in
> almost every case.
>
> http://fastutil.dsi.unimi.it/
>

Well... if I use (x*123) as keys, situation changes:

fastutilIntWrite - 0.844; Mem: 18.34 Mb
fastutilIntReadFull - 0.421; Mem: 18.34 Mb
fastutilIntReadEmpty - 1.187; Mem: 0.34 Mb
compactWrite - 1.375; Mem: 32.47 Mb
compactReadFull - 0.703; Mem: 32.47 Mb
compactReadEmpty - 0.422; Mem: 0.47 Mb
troveIntWrite - 1.109; Mem: 28.63 Mb
troveIntReadFull - 0.453; Mem: 28.63 Mb
troveIntReadEmpty - 1.343; Mem: 0.37 Mb

CompactHashMap is fastest in finding non-existing keys, trove and fastutil
are close.

http://github.com/alex14n/CompactHashMap/blob/211f80999c64586f4e5808f8f7...

Nils Kilden-Pedersen wrote:
>
> You should also look at FastUtil. I've found it to be faster than Trove in
> almost every case.
>
> http://fastutil.dsi.unimi.it/
>

On Tuesday May 19 2009, Alex Yakovlev wrote:
> ... CompactHash'es uses load factor of 100% so they can hold twice
> more objects. But for efficiency it uses an array of indices that
> hold 'linked lists' of objects with the same hash code.

That is a memory cost that has to be included when you compute the true
load factor. All hashing (perfect hashing aside) is subject to
collisions. Open hashing's need to skip through the table at increments
of the hash code modulo the table size is no more expensive than
looking through a linked list or your array. The reason chained hashing
is inferior is that the storage cost of the link nodes is better used
in the hash table proper.

The one thing I wish Trove accommodated was the secondary hash function
used to compute the skip interval when the first slot didn't contain
the lookup target.

Also, Trove allows you to specify the load factor for initial sizing and
to compute the rehash threshold.

> ...

By the way, everything I know about hashing I learned from Sedgewick.

Randall Schulz

But index array allows for less random memory reads.
In one integer index we can pack:
1) real index of the element in key/values array,
2) some bits of its hashCode,
3) bit flag if it is the last element.

Standard HashMap implementation need to:
1) read 'next' pointer from hash table or 'next' HashEntry field,
2) access 'key' or stored hashCode field to check key equality,
3) access 'next' field to check if it is last.

Thus we can optimize number of random memory reads,
which gives significant speed bonus (~30%) on adding new element
or looking for non-existing key.

I've posted my benchmarking on sun forum:
http://forums.sun.com/thread.jspa?messageID=10716110

random new Object():

fastWrite - 0.953s; Mem: 60.91 Mb
fastReadFull - 0.985s; Mem: 60.91 Mb
fastReadEmpty - 0.297s; Mem: 34.91 Mb
javaWrite - 1.265s; Mem: 77.53 Mb
javaReadFull - 0.984s; Mem: 77.53 Mb
javaReadEmpty - 0.421s; Mem: 35.03 Mb

strings like "test"+x with x from 0 to 1.5 mln:

fastWrite - 0.484s; Mem: 234.95 Mb
fastReadFull - 0.828s; Mem: 234.95 Mb
fastReadEmpty - 0.109s; Mem: 195.95 Mb
javaWrite - 0.515s; Mem: 238.55 Mb
javaReadFull - 0.781s; Mem: 238.55 Mb
javaReadEmpty - 0.141s; Mem: 196.05 Mb

integers like 123*x:

fastWrite - 1.234s; Mem: 77.26 Mb
fastReadFull - 0.844s; Mem: 77.31 Mb
fastReadEmpty - 0.313s; Mem: 6.09 Mb
javaWrite - 1.625s; Mem: 89.11 Mb
javaReadFull - 0.906s; Mem: 96.62 Mb
javaReadEmpty - 0.406s; Mem: 0.63 Mb

Randall Schulz wrote:
>
> That is a memory cost that has to be included when you compute the true
> load factor. All hashing (perfect hashing aside) is subject to
> collisions. Open hashing's need to skip through the table at increments
> of the hash code modulo the table size is no more expensive than
> looking through a linked list or your array. The reason chained hashing
> is inferior is that the storage cost of the link nodes is better used
> in the hash table proper.

On Wednesday May 20 2009, Alex Yakovlev wrote:
> But index array allows for less random memory reads.

Perhaps, but be honest about how you compute the ratio of memory used to
items effectively stored as a true "load factor."

> ...

Randall Schulz

I agree with you, but it is simple when both indixes and values are int. When
keys and values are 64-bit Object pointers or just bytes it would look like
comparing apples to oranges. Or when hash array holds large HashEntry
objects with lot of fields including cached hashcode.

My point is that chained hash is generally faster than open. Open hash with
load factor over 50% usually have a lot of collisions hence looking for
non-existing key is very slow. And showed up in benchmark results I posted -
even as CompactHashMap has great speed penalty because of arrays, keys and
values boxing, it was faster in this particular test.

When load factor is <50%, using half of memory for complex indices (chained
hash) is generally faster since it never have to look in wrong hash busket.
Delete operation is open hash is also very sophisticated due to collisions
with other hash buskets. And when we pack both hash bits and real array
index there usually is no extra memory access (index and key vs. key only in
open hash) since comparing hash bits stored in index is usually enough. If
we also use 1 bit as 'this is a last entry' flag we always have 1 less
memory access - in open hash we'll need to read this last empty entry. Thus
the more collisions we have the faster chained hash with complex indices is.

But in practical uses FastUtil may be better for primitive types because of
great boxing penalty. But without boxing we can't use all sweet scala
methods like filter or map.

Randall Schulz wrote:
>
> Perhaps, but be honest about how you compute the ratio of memory used to
> items effectively stored as a true "load factor."
>

Randall,

Well, I've implemented unboxed accessors for Ints in CompactHashMap.
Also, I initialize FastUtil and Trove with less than default load factor for
better performance.
Test results are very strange for me:

compactIntWrite - 0.765s; Mem: 32.34 Mb
compactIntReadFull - 0.562s; Mem: 32.34 Mb
compactIntReadEmpty - 0.218s; Mem: 0.34 Mb
fastutilIntWrite - 1.047s; Mem: 36.33 Mb
fastutilIntReadFull - 0.453s; Mem: 36.33 Mb
fastutilIntReadEmpty - 0.157s; Mem: 0.34 Mb
troveIntWrite - 1.360s; Mem: 51.24 Mb
troveIntReadFull - 0.453s; Mem: 51.24 Mb
troveIntReadEmpty - 0.297s; Mem: 0.34 Mb

1 million elements:

compactIntWrite - 0.453s; Mem: 16.39 Mb
compactIntReadFull - 0.391s; Mem: 16.39 Mb
compactIntReadEmpty - 0.172s; Mem: 0.42 Mb
fastutilIntWrite - 0.641s; Mem: 18.36 Mb
fastutilIntReadFull - 0.313s; Mem: 18.36 Mb
fastutilIntReadEmpty - 0.094s; Mem: 0.36 Mb
troveIntWrite - 0.844s; Mem: 25.79 Mb
troveIntReadFull - 0.313s; Mem: 25.79 Mb
troveIntReadEmpty - 0.187s; Mem: 0.34 Mb

no resize:

compactIntWrite - 0.406s; Mem: 32.33 Mb
compactIntReadFull - 0.468s; Mem: 32.33 Mb
compactIntReadEmpty - 0.203s; Mem: 0.33 Mb
fastutilIntWrite - 0.704s; Mem: 28.13 Mb
fastutilIntReadFull - 0.437s; Mem: 28.13 Mb
fastutilIntReadEmpty - 0.140s; Mem: 0.37 Mb

In both read tests FastUtil is faster. Maybe you are right, and for
primitive types open hash is more effective. Maybe it is just some scala,
type check and type case penalties. But neither of there explains why in
write test CompactHashMap is faster. The only explanation I had is that my
resizing is faster because of arraycopy and almost linear rehashing. So I
did another test and initialzed both maps with full capacity. Still
CompactHashMap is faster in writing. But if my theory of chained hash and
collisions was right then in empty read test it should be faster too.

Regards,
Alex