8000 HashMap and HashTable related optimizations [2.12.x backport] · scala/scala@04259f5 · GitHub
[go: up one dir, main page]
Skip to content

Commit 04259f5

Browse files
l0rincl0rinc
committed
HashMap and HashTable related optimizations [2.12.x backport]
1 parent 23548c4 commit 04259f5

File tree

5 files changed

+65
-77
lines changed

5 files changed

+65
-77
lines changed

‎src/library/scala/collection/mutable/FlatHashTable.scala

Lines changed: 4 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,9 @@ package scala
1010
package collection
1111
package mutable
1212

13+
import java.lang.Integer.rotateRight
14+
import scala.util.hashing.byteswap32
15+
1316
/** An implementation class backing a `HashSet`.
1417
*
1518
* This trait is used internally. It can be mixed in with various collections relying on
@@ -415,20 +418,7 @@ private[collection] object FlatHashTable {
415418
// so that:
416419
protected final def sizeMapBucketSize = 1 << sizeMapBucketBitSize
417420

418-
protected final def improve(hcode: Int, seed: Int) = {
419-
//var h: Int = hcode + ~(hcode << 9)
420-
//h = h ^ (h >>> 14)
421-
//h = h + (h << 4)
422-
//h ^ (h >>> 10)
423-
424-
val improved= scala.util.hashing.byteswap32(hcode)
425-
426-
// for the remainder, see SI-5293
427-
// to ensure that different bits are used for different hash tables, we have to rotate based on the seed
428-
val rotation = seed % 32
429-
val rotated = (improved >>> rotation) | (improved << (32 - rotation))
430-
rotated
431-
}
421+
protected final def improve(hcode: Int, seed: Int) = rotateRight(byteswap32(hcode), seed)
432422

433423
/**
434424
* Elems have type A, but we store AnyRef in the table. Plus we need to deal with

‎src/library/scala/collection/mutable/HashMap.scala

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -72,6 +72,37 @@ extends AbstractMap[A, B]
7272
else Some(e.value)
7373
}
7474

75+
override def getOrElseUpdate(key: A, defaultValue: => B): B = {
76+
val i = index(elemHashCode(key))
77+
val entry = findEntry(key, i)
78+
if (entry != null) entry.value
79+
else addEntry(createNewEntry(key, defaultValue), i)
80+
}
81+
82+
/* inlined HashTable.findEntry0 to preserve its visibility */
83+
private[this] def findEntry(key: A, h: Int): Entry = {
84+
var e = table(h).asInstanceOf[Entry]
85+
while (notFound(key, e))
86+
e = e.next
87+
e
88+
}
89+
private[this] def notFound(key: A, e: Entry): Boolean = (e != null) && !elemEquals(e.key, key)
90+
91+
/* inlined HashTable.addEntry0 to preserve its visibility */
92+
private[this] def addEntry(e: Entry, h: Int): B = {
93+
if (tableSize >= threshold) addEntry(e)
94+
else addEntry0(e, h)
95+
e.value
96+
}
97+
98+
/* extracted to make addEntry inlinable */
99+
private[this] def addEntry0(e: Entry, h: Int) {
100+
e.next = table(h).asInstanceOf[Entry]
101+
table(h) = e
102+
tableSize += 1
103+
nnSizeMapAdd(h)
104+
}
105+
75106
override def put(key: A, value: B): Option[B] = {
76107
val e = findOrAddEntry(key, value)
77108
if (e eq null) None

‎src/library/scala/collection/mutable/HashTable.scala

Lines changed: 26 additions & 63 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,9 @@ package scala
1212
package collection
1313
package mutable
1414

15+
import java.lang.Integer.{numberOfLeadingZeros, rotateRight}
16+
import scala.util.hashing.byteswap32
17+
1518
/** This class can be used to construct data structures that are based
1619
* on hashtables. Class `HashTable[A]` implements a hashtable
1720
* that maps keys of type `A` to values of the fully abstract
@@ -183,6 +186,7 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
183186
table(h) = e.next
184187
tableSize = tableSize - 1
185188
nnSizeMapRemove(h)
189+
e.next = null
186190
return e
187191
} else {
188192
var e1 = e.next
@@ -194,6 +198,7 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
194198
e.next = e1.next
195199
tableSize = tableSize - 1
196200
nnSizeMapRemove(h)
201+
e1.next = null
197202
return e1
198203
}
199204
}
@@ -227,8 +232,9 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
227232
var es = iterTable(idx)
228233

229234
while (es != null) {
235+
val next = es.next // Cache next in case f removes es.
230236
f(es.asInstanceOf[Entry])
231-
es = es.next
237+
es = next
232238

233239
while (es == null && idx > 0) {
234240
idx -= 1
@@ -357,15 +363,11 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
357363

358364
protected def elemEquals(key1: A, key2: A): Boolean = (key1 == key2)
359365

360-
// Note:
361-
// we take the most significant bits of the hashcode, not the lower ones
362-
// this is of crucial importance when populating the table in parallel
363-
protected final def index(hcode: Int) = {
364-
val ones = table.length - 1
365-
val improved = improve(hcode, seedvalue)
366-
val shifted = (improved >> (32 - java.lang.Integer.bitCount(ones))) & ones
367-
shifted
368-
}
366+
/**
367+
* Note: we take the most significant bits of the hashcode, not the lower ones
368+
* this is of crucial importance when populating the table in parallel
369+
*/
370+
protected final def index(hcode: Int): Int = if (table.length == 1) 0 else improve(hcode, seedvalue) >>> numberOfLeadingZeros(table.length - 1)
369371

370372
protected def initWithContents(c: HashTable.Contents[A, Entry]) = {
371373
if (c != null) {
@@ -408,59 +410,20 @@ private[collection] object HashTable {
408410

409411
protected def elemHashCode(key: KeyType) = key.##
410412

411-
protected final def improve(hcode: Int, seed: Int) = {
412-
/* Murmur hash
413-
* m = 0x5bd1e995
414-
* r = 24
415-
* note: h = seed = 0 in mmix
416-
* mmix(h,k) = k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; */
417-
// var k = hcode * 0x5bd1e995
418-
// k ^= k >> 24
419-
// k *= 0x5bd1e995
420-
// k
421-
422-
/* Another fast multiplicative hash
423-
* by Phil Bagwell
424-
*
425-
* Comment:
426-
* Multiplication doesn't affect all the bits in the same way, so we want to
427-
* multiply twice, "once from each side".
428-
* It would be ideal to reverse all the bits after the first multiplication,
429-
* however, this is more costly. We therefore restrict ourselves only to
430-
* reversing the bytes before final multiplication. This yields a slightly
431-
* worse entropy in the lower 8 bits, but that can be improved by adding:
432-
*
433-
* `i ^= i >> 6`
434-
*
435-
* For performance reasons, we avoid this improvement.
436-
* */
437-
val i= scala.util.hashing.byteswap32(hcode)
438-
439-
/* Jenkins hash
440-
* for range 0-10000, output has the msb set to zero */
441-
// var h = hcode + (hcode << 12)
442-
// h ^= (h >> 22)
443-
// h += (h << 4)
444-
// h ^= (h >> 9)
445-
// h += (h << 10)
446-
// h ^= (h >> 2)
447-
// h += (h << 7)
448-
// h ^= (h >> 12)
449-
// h
450-
451-
/* OLD VERSION
452-
* quick, but bad for sequence 0-10000 - little entropy in higher bits
453-
* since 2003 */
454-
// var h: Int = hcode + ~(hcode << 9)
455-
// h = h ^ (h >>> 14)
456-
// h = h + (h << 4)
457-
// h ^ (h >>> 10)
458-
459-
// the rest of the computation is due to SI-5293
460-
val rotation = seed % 32
461-
val rotated = (i >>> rotation) | (i << (32 - rotation))
462-
rotated
463-
}
413+
/**
414+
* Defer to a high-quality hash in [[scala.util.hashing]].
415+
* The goal is to distribute across bins as well as possible even if a hash code has low entropy at some bits.
416+
* <p/>
417+
* OLD VERSION - quick, but bad for sequence 0-10000 - little entropy in higher bits - since 2003
418+
* {{{
419+
* var h: Int = hcode + ~(hcode << 9)
420+
* h = h ^ (h >>> 14)
421+
* h = h + (h << 4)
422+
* h ^ (h >>> 10)
423+
* }}}
424+
* the rest of the computation is due to SI-5293
425+
*/
426+
protected final def improve(hcode: Int, seed: Int): Int = rotateRight(byteswap32(hcode), seed)
464427
}
465428

466429
/**

‎src/library/scala/collection/mutable/LinkedHashMap.scala

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -81,6 +81,8 @@ class LinkedHashMap[A, B] extends AbstractMap[A, B]
8181
else e.earlier.later = e.later
8282
if (e.later eq null) lastEntry = e.earlier
8383
else e.later.earlier = e.earlier
84+
e.earlier = null // Null references to prevent nepotism
85+
e.later = null
8486
Some(e.value)
8587
}
8688
}

‎src/library/scala/collection/mutable/LinkedHashSet.scala

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -73,6 +73,8 @@ class LinkedHashSet[A] extends AbstractSet[A]
7373
else e.earlier.later = e.later
7474
if (e.later eq null) lastEntry = e.earlier
7575
else e.later.earlier = e.earlier
76+
e.earlier = null // Null references to prevent nepotism
77+
e.later = null
7678
true
7779
}
7880
}

0 commit comments

Comments
 (0)
0