Skip to main content

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [List Home]
Re: [jgit-dev] Improving ObjectIdSubclassMap performance


On Wed, 9 Mar 2011, Shawn Pearce wrote:

> On Wed, Mar 9, 2011 at 09:59, Aliaksandr Radzivanovich
> <aradzivanovich@xxxxxxxxx> wrote:
> > I took this as an opportunity to practice in implementing Cuckoo
> > hashing[1].
> ...
> > My Cuckoo hash tables work slower than the original map. The one that
> > uses four hash functions inserts objects significantly slower. Both
> > maps retrieve objects significantly slower, which is very surprising
> > for me. My guess it is because of randomized access to memory. The
> > good news, however, is that these new maps waste less space --  1,4
> > array elements per each object versus 2,8 of the original map.
> This is an interesting result, thanks for sharing it
> Unfortunately the slowdown is too great over the current code to
> justify switching in the name of saving memory.

It would be interesting to find out where the time is spent. OProfile has 
gained the ability to profile even JITted Java code with a low overhead, 
so if you're on Linux, you might want to analyze the difference between 
cuckoo vs non-cuckoo.

My guess is that the hash calculation makes for the overhead. If that is 
the case, you might want to use several parts of the SHA-1 as 
different hashes (interpreting the 20-byte as 5 32-bit integers gives you 
five hash functions for the price of one), because the SHA-1 has been 
calculated anyway.


Back to the top