Performance Enhancement: HashMap creates a Some object on every lookup, even if using apply

[scabug]

Every look-up in a HashMap (mutable or immutable) creates a Some object to wrap the result. Event when calling apply as:

map(key)

the Some is created and then immediately removed. This means doing lots of HashMap look-ups in a loop will lead to GC needing to run and a significant slowdown.

It would be great if the HashMap (and maybe others) could override apply to not do any object creation and only create a Some when using get.

If you run:

JAVA_OPTS="-Xaprof" scala

and then:

val b = scala.collection.immutable.HashMap.newBuilder[Int,Int]
b += 1 -> 2
val sihm = b.result
for (_ <- 1 to 1000000) {
  sihm(1)
}

And look at the output, you will see a huge number of totally unnecessary scala.Some objects being created.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-4469?orig=1
Reporter: nick
Attachments:

• hashmap.diff (created on Apr 27, 2011 12:12:29 PM UTC, 2698 bytes)

[scabug]

@magarciaEPFL said:
The example exercises one particular execution trace, whereas other traces make use of the Option object.

It would be great if you could provide details about an implementation of apply that benchmarks favorably on a range (ideally all) workloads.

[scabug]

@ijuma said:
Replying to [comment:3 magarcia]:

It would be great if you could provide details about an implementation of apply that benchmarks favorably on a range (ideally all) workloads.

I'm not the original reporter, but the usual way to do this is to have an internal method that returns null instead of None. Then get can wrap it and there is no allocation in apply. A bit ugly, but that's the price of efficiency in this case.

Of course, if you want to support null keys, then it becomes a bit more complicated. See java.util.HashMap for how they do that. I'd say that supporting null keys in Maps is a bad idea and ConcurrentHashMap in Java does not support them.

[scabug]

@paulp said:
I implemented this at some point for mutable maps, see attached. What gave me pause about committing it was that it was behavior changing; see also the change I had to make elsewhere in trunk. This is the achilles heel of inheritance: you can't change something like this without potentially breaking code.

[scabug]

Commit Message Bot (anonymous) said:
(extempore in r25147) Overrode contains and apply in mutable.HashMap to avoid allocating
an unnecessary Some on every call to either of them. Fruit looks a
little better defended in immutable.HashMap, so I deleted a bunch of old
debugging code instead. Closes #4469, no review.