TreeJsonDecoder with `useAlternativeNames=true` is slow even if no alternative names exist

[Snipesy]

Describe the bug

While working on ohs-foundation/kotlin-fhir#83 I discovered using TreeJsonDecoder (which is used when polymorphic serialization fails the hot path) the performance of kotlinx serialization is extremely poor (roughly 2x to 4x slower than useAlternativeNames=false)

To Reproduce

@Serializable
data class WideClass(
  val f00: String? = null,
  val f01: String? = null,
  val f02: String? = null,
  val f03: String? = null,
  val f04: String? = null,
  val f05: String? = null,
  val f06: String? = null,
  val f07: String? = null,
  val f08: String? = null,
  val f09: String? = null,
  val f10: String? = null,
  val f11: String? = null,
  val f12: String? = null,
  val f13: String? = null,
  val f14: String? = null,
  val f15: String? = null,
  val f16: String? = null,
  val f17: String? = null,
  val f18: String? = null,
  val f19: String? = null,
  val f20: String? = null,
  val f21: String? = null,
  val f22: String? = null,
  val f23: String? = null,
  val f24: String? = null,
  val f25: String? = null,
  val f26: String? = null,
  val f27: String? = null,
  val f28: String? = null,
  val f29: String? = null,
)

fun main() {
  // 5 of 30 fields populated. JSON has 5 keys; descriptor has 30 slots; 25 absent → 25 slow-path
  // invocations per decode under default `useAlternativeNames = true`.
  val sample =
    """
    {"f00":"a","f01":"b","f02":"c","f03":"d","f04":"e"}
    """
      .trimIndent()

  val withAlternates = Json { useAlternativeNames = true }
  val withoutAlternates = Json { useAlternativeNames = false }

  val element = withAlternates.parseToJsonElement(sample)
  val iterations = 5_000_000

  // Warm both Json instances + JIT.
  repeat(50_000) {
    withAlternates.decodeFromJsonElement(WideClass.serializer(), element)
    withoutAlternates.decodeFromJsonElement(WideClass.serializer(), element)
  }

  val withTime = measureTime {
    repeat(iterations) {
      withAlternates.decodeFromJsonElement(WideClass.serializer(), element)
    }
  }
  val withoutTime = measureTime {
    repeat(iterations) {
      withoutAlternates.decodeFromJsonElement(WideClass.serializer(), element)
    }
  }

  println()
  println("════════════════════════════════════════════════════════")
  println(" JsonTreeDecoder slow-path reproducer")
  println("════════════════════════════════════════════════════════")
  println("  Class:              WideClass (30 nullable String fields, 0 @JsonNames)")
  println("  JSON input:         5 keys present, 25 slots absent")
  println("  Iterations:         $iterations")
  println()
  println("  useAlternativeNames=true  (default):  ${withTime} = ${withTime.inWholeNanoseconds / iterations} ns/op")
  println("  useAlternativeNames=false (skip slow): ${withoutTime} = ${withoutTime.inWholeNanoseconds / iterations} ns/op")
  println()
  val ratio = withTime.inWholeNanoseconds.toDouble() / withoutTime.inWholeNanoseconds.toDouble()
  println("  Slowdown factor:    %.2fx".format(ratio))
  println("════════════════════════════════════════════════════════")
}

Expected behavior

Serialization should be fast :)

Actual behavior

Serialization is slow! :(

On my M3 Max Macbook pro useAlternativeNames = true is 3x slower than useAlternativeNames = false. Almost the entire time is spent doing O(n*m) lookups here:

kotlinx.serialization/formats/json/commonMain/src/kotlinx/serialization/json/internal/TreeJsonDecoder.kt

Line 254 in 6956af2

value.keys.find { deserializationNamesMap[it] == index }?.let {

Even though the model declares no alternative names. While it is easy to set useAlternativeNames=false, the default in Kotlin is true... And I think this is something that can easilly be cached.

[pdvrieze]

The code path is needed because treeDecoder serializes based on the element order in the descriptor, rather than iterating the key/value pairs in the value. As such, if alternative names are used, it must find which key belongs to the serial name descriptor index which it does by looking at all keys that have a name that would be an alternate to the serial name of the element (from the descriptor).
As long as the amount of alternates is smaller than the amount of keys in the object it would be of lower complexity to get the alternates defined on the element and iterate over those.

The solution might be to add this alternative path (possibly with size check), or redesign the decoder to iterate entries rather than descriptor elements (but this would be quite more work and may change semantics or observed behaviour in some subtle way - it might also create other issues).

[vsartiushkin]

Thank you for the report and the reproducer!
I have created a benchmark project for the comparison, and got similar results for 5 present and 25 absent keys:

main summary:
Benchmark                         Mode  Cnt    Score    Error  Units
BenchmarkClass.withAlternates     avgt    5  911.394 ± 29.088  ns/op
BenchmarkClass.withoutAlternates  avgt    5  176.826 ±  0.803  ns/op

kotlinx.serialization_gh_3193_benchmark.zip

[fzhinkin]

I was nerd sniped, so here are some observations:

• profile: flame-cpu-forward.html
• JsonTreeDecoder.endStructure concatenates two sets every single time, even if one of them is empty
• JsonTreeDecoder.decodeElementIndex invokes SerialDescriptor.getTag for each and every descriptor's element; getTag performs a relatively costly lookup; perhaps, we should add a SerialDescriptor.getTagS to perform a bulk request
• PluginGeneratedSerialDescriptor.hashCode could probably relax the way hash code is cached and use a regular Int field with some particular value (like 0) treated as "hash code is not cached".

[pdvrieze]

• PluginGeneratedSerialDescriptor.hashCode could probably relax the way hash code is cached and use a regular Int field with some particular value (like 0) treated as "hash code is not cached".

For this case an other option is to store it in a long and use a value outside of the Int range as "not set" value (e.g. Long.MAX_VALUE)

[mwaddo]

Hi, I investigated, two things make it slow and both only matter when a class actually declares alternative names (@JsonNames). useAlternativeNames does default to true so this is the path most decodes hit:

1. The more expensive one: endStructure builds a brand new set on every decode to check for unknown keys, even when there are no alternative names. That's most of the extra allocation.
2. The scan at L254 is smaller, and like pdvrieze said, it's needed when alternative names exist so it has to stay.

The fix would be, when a class has no alternative names, just do what useAlternativeNames = false does, use the field's own name in elementName instead of searching the keys for another spelling and reuse the set it already has in endStructure instead of building a new one each time. Classes that actually use alternative names are unaffected.

This is the same 30 field class with only 5 of the 30 fields filled in, decoded from a JsonElement (benchmark + raw output + before/after graph and logs attached):

	memory per decode
useAlternativeNames = false	336 bytes
useAlternativeNames = true (before)	1872 bytes
useAlternativeNames = true (with fix)	336 bytes

So its back to using the same memory as the false and runs 2-3x faster. The existing alternative name tests still pass and I added one for the no alternative names case. I'll put out a PR with the fix + benchmark.

Some other notes:

• The streaming decoder doesn't have this problem. It looks up each key by name directly so missing fields cost nothing. The tree decoder goes field by field in class order instead, which is why only it needs this fix.
• The last bit of extra memory turned out to be a small throwaway object created every time it looked up the alternative name info, even when the answer was already cached. Reading the cache directly avoids creating it and that brings memory down to the false number exactly.

---

flame-alloc-after.html
flame-alloc-before.html
jmh-after-fix.log
jmh-before-fix.log

[qwwdfsad]

There are two things that are unreasonable slow and two fixes for each:

1. Check for unknown keys and set allocation
   • The easy fix is to avoid that: c951f39. It yields 50-60% improvement for alternative names, trivial to upstream
   • A harder fix would be to stop doing an extra-linear scan in endStructure. I assume we can incrementally keep track of all the keys the decoder consumed and in the end check the cardinalities. Yield the result for all code paths (including no alternative names as well). A bit harder to reason about (because of the alternative names, optional fields and name clashes). This one I'll consider after 2, they are in direct conflcit
2. Quadratic complexity in decodeElementIndex, namely

   kotlinx.serialization/formats/json/commonMain/src/kotlinx/serialization/json/internal/TreeJsonDecoder.kt

   Line 262 in 84ff6af

   val deserializationNamesMap = json.deserializationNamesMap(descriptor)

   -- linear check for mapping existing names to a potential alternative name
   • Easy fix: inverted index once per descriptor (maybe even cached format-wise) from keys to their respective indices
   • Hard fix: rewrite the whole TreeJsonDecoder :) The problem itself appears because the tree decoder operates on indices of the serial descriptor itself (so the logic is "get i-th descriptor element -> match it against JsonObject") instead of existing keys ("get the current key of JsonObject -> match against serial descriptor"). The former requires much more bookkeeping, and all code paths will benefit from it

Taking alternate keys is enabled by default, I'll investigate harder options

[qwwdfsad]

The rewrite was much easier than it seemed and yielded much more benefits than I expected.
Copying TL;DR from the PR: much faster, less code, one implementation instead of two, behaviour that replicates streaming decoder