Faster HashMap implementation (original) (raw)
Alex Yakovlev alex14n at gmail.com
Wed Jul 1 12:50:49 UTC 2009
- Previous message: Faster HashMap implementation
- Next message: Faster HashMap implementation
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Doug,
Checking key reference equality before hashcode looks like a big win.
Have you considered using balancing tree instead of bit trie? This could decrease look depth from number of hash bits to log2(tree size).
Also, there could be a sence in using adjacent table cell for key/value if it's not used. Maybe also without a hashcode check for less cache misses. In practice this gives ~4-5% performance for get(). In theory, when 70% of gets are resolved at first try, 23% on second, assuming that adjacent cell is empty in 50% cases, and in best case (referential equality) we'll have 1 cache miss instead of 3, thus .23*.5*(2/3) = 7.67% in worst case (2 cache misses instead of 4 with hashcode check) +5.75%
On Wed, Jul 1, 2009 at 2:09 AM, Doug Lea<dl at cs.oswego.edu> wrote:
Inspired by the combination of Alex's efforts and ongoing work on concurrent caches, I put together a version of HashMap (called HashMapV2 for now) with a snapshot at http://gee.cs.oswego.edu/dl/wwwtmp/HashMapV2.java (This retains the openjdk GPL header etc.)
- Previous message: Faster HashMap implementation
- Next message: Faster HashMap implementation
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]