[micro-opt] WeakHashSet can skip dereference if hash mismatch when traversing chains

[tanishiking]

When I look at the flamegraphs generated for scala3-benchmarks, I found AppliedUniques.linkedListLoop / WeakHashSet.linkedListLoop accounts for several % (4-5%) on some benchmarks.

linkedListLoop is traversing on the chain (of separate chaining), for looking up an entry from the chain.

One obvious optimization I realized is that, currently we always dereference WeakReference on the chain, and compare it with an entry we're looking up, but we should be able to compare hash and skip if they doesn't match.

scala3/compiler/src/dotty/tools/dotc/core/Uniques.scala

Lines 92 to 101 in 96cca47

	@tailrec
	def linkedListLoop(entry: Entry[AppliedType] | Null): AppliedType = entry match
	case null => addEntryAt(bucket, newType, h, oldHead)
	case _ =>
	val e = entry.get
	if e != null && (e.tycon eq tycon) && e.args.eqElements(args) then e
	else linkedListLoop(entry.tail)
	linkedListLoop(oldHead)
	end if

[SolalPirelli]

I wonder how much of WeakHashSet's calls is due to not so great hashing. See eg #26696

[tanishiking]

Yeah, I was also curious there might be bias in which buckets we distribute, because of bias in (the lower bits of) the hash.
I measured which bucket entries were added to in addEntryAt (when no existing entry is found in the Set and a new entry is added).

For scalaz and scala-steward, the results look something like this:

scalaz

	addEntryAt	mean	std	max	max/mean
Uniques	414,024	12.64	4.09	51	4.0
NamedTypeUniques	460,551	3.51	2.01	38	10.8
AppliedUniques	2,314,095	35.31	6.43	80	2.3

scalaSteward

	addEntryAt	mean	std	max	max/mean
Uniques	139,727	4.26	3.21	153	35.9
NamedTypeUniques	280,421	2.14	1.55	51	23.8
AppliedUniques	3,023,584	46.14	6.95	128	2.8

(Note that the denominator for the mean is initialCapacity, so if a resize happend, this number wouldn't be accurate though)

it seems the std isn't ... that bad?. However, for AppliedUniques, the average bucket length tends to be pretty large in both cases (though they actually cleaned up by removeStaleEntries), so it might be worth increasing initialCapacity.

(Currently NamedUniques uses Config.initialUniquesCapacity * 4 and AppliedUniques uses Config.initialUniquesCapacity * 2, but it seems it would make more sense with opposite)(it probably depends on the benchmark though) 🤔

scala3/compiler/src/dotty/tools/dotc/core/Uniques.scala

Line 38 in cfa6748

final class NamedTypeUniques extends WeakHashSet[NamedType](Config.initialUniquesCapacity * 4) with Hashable:

scala3/compiler/src/dotty/tools/dotc/core/Uniques.scala

Line 77 in cfa6748

final class AppliedUniques extends WeakHashSet[AppliedType](Config.initialUniquesCapacity * 2) with Hashable:

Maybe it's worth investigating other benchmark scenarios, and increase the initialize capacity of AppliedUniques.

[SolalPirelli]

One thing that may be interesting to measure if you have the time is whether we insert items in these sets that are equal to an existing item but have a different hash, which is a problem #26696 fixes for some operations on some types.

[tanishiking]

One thing that may be interesting to measure if you have the time is whether we insert items in these sets that are equal to an existing item but have a different hash, which is a problem #26696 fixes for some operations on some types.

Oh, that's something I didn't expect for CachedType, but if that's the case, it's definitely waste of chains, will check later 👍