Consider to remove sorting at MeterIdPrefix

[imasahiro]

Currently, we sort the micrometer tags at MeterIdPrefix to create Meter ID stably.
https://github.com/line/armeria/blob/master/core/src/main/java/com/linecorp/armeria/common/metric/MeterIdPrefix.java#L95-L101

Since I saw this stacktrace from our service’s flamegraph, I would like to consider whether it is avoidable or not. Since it doesn’t have many samples, we can be ignored but because it is not optimal, it would be happy if we can avoid this sort.

[trustin]

We can make use of the following characteristics:

• The number of tag names is very small (less than 10 usually)
• We always construct a new sorted tag list because MeterIdPrefix is immutable.
• A user may have specified tags in a sorted form already, i.e. sort could be done quickly if the input is sorted already.
• When merging two tag lists:
  • the first tag list is always sorted.
  • the second tag list is also very small.

[anuraaga]

I don't think this would be an issue if we sorted during metric export instead of when recording metrics.

Do you think it's possible to move sorting to a different layer that only occurs during export?

[trustin]

That's a good point. We could:

• Sort only when creating a meter.
• Make MeterIdPrefix.equals() and hashCode() order-independent.

[anuraaga]

I played with this a little and found

• Micrometer sorts before creating a meter anyways, so we don't need to worry about it. Removing sorting still allows prometheus integration test to pass even though it adds tags out-of-order

• We need to do order-independent hashcode/equals for the memoizing that happens in MicrometerUtil.register. However, I don't know if it's possible to do this faster than the current sort. I tried these three techniques, all slower than HEAD, and in this order of performance. Do you know of any other trick for unordered Equals that might be faster than the sort we do?

  • this.tags.containsAll(that.tags) && that.tags.containsAll(this.tags) (probably fast right now since by default we don't have that many tags)
  • Store field this.unorderedTags = ImmutableSet.copyOf(tags), this.unorderedTags.equals(that.unorderedTags)
  • ImmutableSet.copyOf(this.tags).equals(ImmutableSet.copyOf(that.tags));

Also of the optimizations in

#2150 (comment)

I guess the one that might have an affect is doing insertion sort for merging - TimSort already essentially skips sorted input so I don't know if we're able to beat it by taking already-sortedness into account.

Let me now if you have any thoughts.

[anuraaga]

By the way, @imasahiro are you using default MeterIdPrefixFunctionFactory.DEFAULT or do you add your own tags with MeterIdPrefixFunction.withTags? If latter, how many tags?

[imasahiro]

@anuraaga Yes, basically, I'm using armeria-spring's default MeterIdPrefixFunctionFactory.DEFAULT.

[trustin]

Wouldn't order-indepdendent hashCode() with memoization help a lot since it will make full comparison skip in many cases? i.e. order-independent equals() will be slower but hashCode() will cover the loss to some extent.

[anuraaga]

The benchmark in my PR does the prefix generation+register but I didn't see it cover the difference unfortunately. I guess it would require very slow sorting (adding largish number of tags in very random order) to see the difference so maybe we can live with it now since default function can be made to add the tags in order.