Imported From: https://issues.scala-lang.org/browse/SI-2512?orig=1
Reporter: Eric Willigers (ewilligers)
Attachments:

• QuickHashSet.scala (created on Oct 26, 2009 8:02:08 AM UTC, 2274 bytes)
• Test.scala (created on Nov 26, 2009 9:34:29 PM UTC, 1378 bytes)

@paulp said:
That's a pretty titanic bug. Look at what it did to the statistics -- uniquetypes is reporting size, I added uniquetypes2 to count what's really in there.

[scalacfork] *** Cumulative statistics at phase cleanup
[...]
[scalacfork] #uniquetypes : 2242323
[scalacfork] #uniquetypes2: 962323

Sadly no performance improvement that I can see, but maybe that's because I'm nowhere near memory bound.

I'll fix it shortly.

@paulp said:
Fixed in r19265.

Eric Willigers (ewilligers) said:
Possibly faster HashSet, with identical allocation behaviour to r19265

@paulp said:
FYI I stumbled across this (adding attachments to a closed ticket is not a good way to make sure they're seen) and gave it a whirl, but my extremely unscientific test showed zero speed difference from what's there, so no dice unless you would like to assemble some convincing performance metrics.

Eric Willigers (ewilligers) said:
Benchmark

Eric Willigers (ewilligers) said:
(reopening for extempore to consider my benchmark, which uses uniformly distributed hashCode values)

Running my attached benchmark, my suggested hashset takes 30% to 40% less time.

I used Scala 2.8.0.r19890-b20091126020351 and Java 1.7.0-ea-b76 on XP
JAVA_OPTS="-Xms1024M -Xmx1024M -XX:+PrintCompilation -server -Xbatch -XX:CICompilerCount=1"

@ijuma said:
Using uniformly distributed hashCodes on their own is not enough unless one expects that to be true for the structure in question though.

@paulp said:
Replying to [comment:5 ijuma]:

Using uniformly distributed hashCodes on their own is not enough unless one expects that to be true for the structure in question though.

If I finish up #2537 then it will be true, because for the big cases in the compiler what is being stored in HashSet are case classes.

@ijuma said:
I have it on my todo list to do a bunch of testing when it comes to maps, sets and case classes with and without jenkins hash. My hope is to do it in the next few weeks, but we'll see.

Interesting that the compiler uses case classes that much. For maps in Java, the statistics I've seen say that over 50% uses a String key.

@paulp said:
Unable to witness a performance difference and unwilling to go crazy looking for it, I choose option C, assign to scala community.

@Ichoran said:
The new AnyRefMap is hugely faster than this for large HashSets, but equally much slower for small HashSets. That indicates that there is significant potential for improvement, but it's not as simple as just dropping in AnyRefMap.

@kanielc said:
This ticket is over 5 years old, should it be closed with some sort of resolution?

@Ichoran said:
@kanielc - No, because it's not resolved yet.

@SethTisue the initial bug was fixed, hashes improved, no definitive reproducible demonstration of an issue with 2.13 collections. No one is crying "my small AnyRefMap is slow". Suggest closing with your friendly, Happy to re-open if someone discovers an issue.

Alternatively, transfer the issue to collections-next for dotty to inherit after the thaw.