Optimize ImmutableSetMultimap.Builder with sorted values

[PhilippWendler]

Currently ImmutableSetMultimap.Builder stores the values in linked hash sets in order to keep insertion order:

guava/guava/src/com/google/common/collect/ImmutableSetMultimap.java

Lines 254 to 256 in ea4e950

	Collection<V> newMutableValueCollection() {
	return Platform.preservesInsertionOrderOnAddsSet();
	}

However, after orderValuesBy is called, it is known that the insertion order is irrelevant. So I suggest to optimize the builder by letting newMutableValueCollection return regular hash sets if valueComparator is not null.

As far as I see this is safe even if orderValuesBy is called only after some entries have been added. The builderMap will then contain a mixture of linked hash sets and regular hash sets, but this will not change anything.

Note that once a value comparator is set, it can never be unset (only replaced). Furthermore, the insertion order is not even relevant if duplicate (according to the comparator) values are added for one key, because when the ImmutableSortedSets for values are created during build these get deduplicated anyway.

Side note: When ImmutableSetMultimap.Builder.orderValuesBy is used, the values get deduplicated (per key) according to both equals and the comparator. This is different from both TreeMultimap and ImmutableListMultimap.Builder.oderValuesBy and could be unexpected. I suggest to add a note to orderValuesBy that requires that the comparator must be consistent with equals.

The same kind of optimization could be done with orderKeysBy and builderMap, the latter of which could be replaced by a regular hash map if it is still empty while orderKeysBy is called (for all kinds of ImmutableMultimaps). But the benefit is smaller here, of course.

[souradeepmajumdar05]

i would like to work on this @netdpb

[netdpb]

I don't think we're ready for any implementation work. Do you have a sense of how much time or space this optimization might save?