The performance of creating new datetime formats can be improved

[dkhalanskyjb]

See

kotlinx-datetime/core/common/src/internal/format/parser/Parser.kt

Lines 44 to 45 in 20e523a

	// TODO: O(size of the resulting parser ^ 2), but can be O(size of the resulting parser)
	internal fun <T> List<ParserStructure<T>>.concat(): ParserStructure<T> {

. When joining together several parsers each of which has several branching possibilities, we do it almost naively, by concatenating each parser to each of the tails of the preceding parsers and then traversing the whole branching parser to normalize it. If we perform normalization immediately while joining the parsers instead, we can avoid the O(|number of joined parsers|^2) traversal. Benchmarks show that this call takes a huge portion of the runtime, so this is not just a theoretical concern.