8000 [backport] Hash table getOrElseUpdate and indexing by adriaanm · Pull Request #5626 · scala/scala · GitHub
[go: up one dir, main page]
Skip to content

[backport] Hash table getOrElseUpdate and indexing #5626

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 7 commits into from
Jan 6, 2017
Merged

[backport] Hash table getOrElseUpdate and indexing #5626

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
7 commits
Select commit Hold shift + click to select a range
cb7192c
Restarr on 2.11.8-18269ea
adriaanm Jan 5, 2017
f31745a
SI-8774 Null link fields in mutable hash maps on removal.
Jul 21, 2016
5fd422b
Optimized HashTable.index
l0rinc Nov 22, 2016
26ad9cc
Changed modulo to bitwise AND in hash calculation
l0rinc Nov 22, 2016
276db03
Changed hashing bit rotation to use Integer.rotateRight
l0rinc Dec 6, 2016
02c30a1
Changed HashMap.getOrElseUpdate to only calculate the index once
l0rinc Nov 16, 2016
1e82a92
Simplify HashTable.index further
l0rinc Dec 6, 2016
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Changed hashing bit rotation to use Integer.rotateRight 
(cherry picked from commit bc91223)
  • Loading branch information
@l0rinc @adriaanm
l0rinc authored and adriaanm committed Jan 5, 2017
commit 276db03285e25e54acbe004070ea9853193ab73f
18 changes: 4 additions & 14 deletions src/library/scala/collection/mutable/FlatHashTable.scala
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -10,6 +10,9 @@ package scala
package collection
package mutable

import java.lang.Integer.rotateRight
import scala.util.hashing.byteswap32

/** An implementation class backing a `HashSet`.
*
* This trait is used internally. It can be mixed in with various collections relying on
Expand Down Expand Up @@ -415,20 +418,7 @@ private[collection] object FlatHashTable {
// so that:
protected final def sizeMapBucketSize = 1 << sizeMapBucketBitSize

protected final def improve(hcode: Int, seed: Int) = {
//var h: Int = hcode + ~(hcode << 9)
//h = h ^ (h >>> 14)
//h = h + (h << 4)
//h ^ (h >>> 10)

val improved= scala.util.hashing.byteswap32(hcode)

// for the remainder, see SI-5293
// to ensure that different bits are used for different hash tables, we have to rotate based on the seed
val rotation = seed % 32
val rotated = (improved >>> rotation) | (improved << (32 - rotation))
rotated
}
protected final def improve(hcode: Int, seed: Int) = rotateRight(byteswap32(hcode), seed)

/**
* Elems have type A, but we store AnyRef in the table. Plus we need to deal with
Expand Down
9 changes: 4 additions & 5 deletions src/library/scala/collection/mutable/HashTable.scala
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -12,6 +12,9 @@ package scala
package collection
package mutable

import java.lang.Integer.rotateRight
import scala.util.hashing.byteswap32

/** This class can be used to construct data structures that are based
* on hashtables. Class `HashTable[A]` implements a hashtable
* that maps keys of type `A` to values of the fully abstract
Expand Down Expand Up @@ -424,11 +427,7 @@ private[collection] object HashTable {
* }}}
* the rest of the computation is due to SI-5293
*/
protected final def improve(hcode: Int, seed: Int): Int = {
val hash = scala.util.hashing.byteswap32(hcode)
val shift = seed & ((1 << 5) - 1)
(hash >>> shift) | (hash << (32 - shift))
}
protected final def improve(hcode: Int, seed: Int): Int = rotateRight(byteswap32(hcode), seed)
}

/**
Expand Down
0