8000 Hash table getOrElseUpdate and indexing 2.12 backport [ci: last-only] by l0rinc · Pull Request #5566 · scala/scala · GitHub
[go: up one dir, main page]
Skip to content

Hash table getOrElseUpdate and indexing 2.12 backport [ci: last-only] #5566

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

Closed
wants to merge 6 commits into from
Closed

Hash table getOrElseUpdate and indexing 2.12 backport [ci: last-only] #5566

Changes from 1 commit
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
78b0914
SI-8774 Null link fields in mutable hash maps on removal.
Jul 21, 2016
02c89c2
Optimized HashTable.index
l0rinc Nov 22, 2016
3a3a4ff
Changed modulo to bitwise AND in hash calculation
l0rinc Nov 22, 2016
c7ddb41
Changed hashing bit rotation to use Integer.rotateRight
l0rinc Dec 6, 2016
5257158
Changed HashMap.getOrElseUpdate to only calculate the index once
l0rinc Nov 16, 2016
1ee7d21
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
Simplify HashTable.index further 
(cherry picked from commit 26c87f1)
  • Loading branch information
@l0rinc
l0rinc committed Dec 19, 2016
commit 1ee7d215cf97400cffdf13da970a20ae8630e7f4
8 changes: 2 additions & 6 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,7 +12,7 @@ package scala
package collection
package mutable

import java.lang.Integer.rotateRight
import java.lang.Integer.{numberOfLeadingZeros, rotateRight}
import scala.util.hashing.byteswap32

/** This class can be used to construct data structures that are based
Expand Down Expand Up @@ -367,11 +367,7 @@ trait HashTable[A, Entry >: Null <: HashEntry[A, Entry]] extends HashTable.HashU
* Note: we take the most significant bits of the hashcode, not the lower ones
* this is of crucial importance when populating the table in parallel
*/
protected final def index(hcode: Int): Int = {
val ones = table.length - 1
val exponent = Integer.numberOfLeadingZeros(ones)
(improve(hcode, seedvalue) >>> exponent) & ones
}
protected final def index(hcode: Int): Int = if (table.length == 1) 0 else improve(hcode, seedvalue) >>> numberOfLeadingZeros(table.length - 1)
Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@sjrd, thanks for the comments, is this too awkward?
Branch prediction should eliminate this fork.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't know. At this point we're past my understanding of JVM performance. I would expect & ones (one CPU cycle with operands already loaded in registers so no stalling due to memory) to always be faster than a branch, even if correctly predicted and/or using a conditional move, but I cannot assert that.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Instruction Level Parallelism can achieve > 1 instruction/clock (IPC), so a predictable branch guarding an operation might in fact be faster than a branchless algorithm with a data dependency.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks @retronym, and also, the JVM can detect that the first branch is never taken and eliminate it completely :)


protected def initWithContents(c: HashTable.Contents[A, Entry]) = {
if (c != null) {
Expand Down
0