Databases
StackOverflow2013
Postsdbo
POcan array access be optimized?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POcan array access be optimized?
    text
    copied!<p>Maybe I'm being misled by my profiler (Netbeans), but I'm seeing some odd behavior, hoping maybe someone here can help me understand it.</p> <p>I am working on an application, which makes heavy use of rather large hash tables (keys are longs, values are objects). The performance with the built in java hash table (HashMap specifically) was very poor, and after trying some alternatives -- Trove, Fastutils, Colt, Carrot -- I started working on my own.</p> <p>The code is very basic using a double hashing strategy. This works fine and good and shows the best performance of all the other options I've tried thus far.</p> <p>The catch is, according to the profiler, lookups into the hash table are the single most expensive method in the entire application -- despite the fact that other methods are called <em>many</em> more times, and/or do <em>a lot</em> more logic.</p> <p>What really confuses me is the lookups are called only by one class; the calling method does the lookup and processes the results. Both are called nearly the same number of times, and the method that calls the lookup has a lot of logic in it to handle the result of the lookup, but is about 100x faster.</p> <p>Below is the code for the hash lookup. It's basically just two accesses into an array (the functions that compute the hash codes, according to profiling, are virtually free). I don't understand how this bit of code can be so slow since it is just array access, and I don't see any way of making it faster.</p> <p>Note that the code simply returns the bucket matching the key, the caller is expected to process the bucket. 'size' is the hash.length/2, hash1 does lookups in the first half of the hash table, hash2 does lookups in the second half. key_index is a final int field on the hash table passed into the constructor, and the values array on the Entry objects is a small array of longs usually of length 10 or less.</p> <p>Any thoughts people have on this are much appreciated.</p> <p>Thanks.</p> <pre><code>public final Entry get(final long theKey) { Entry aEntry = hash[hash1(theKey, size)]; if (aEntry != null &amp;&amp; aEntry.values[key_index] != theKey) { aEntry = hash[hash2(theKey, size)]; if (aEntry != null &amp;&amp; aEntry.values[key_index] != theKey) { return null; } } return aEntry; } </code></pre> <p>Edit, the code for hash1 &amp; hash2</p> <pre><code>private static int hash1(final long key, final int hashTableSize) { return (int)(key&amp;(hashTableSize-1)); } private static int hash2(final long key, final int hashTableSize) { return (int)(hashTableSize+((key^(key&gt;&gt;3))&amp;(hashTableSize-1))); } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload