If I have a rather large

Map<String, String>

(keyed labels of UI elements), which is created dynamically via fetching the labels from api -- so not statically with string literals. Does it make sense to implement a

Trie

or is this somehow optimized under the hood in jvm since

String

is so special? I remember faintly about string interning, but that only applies to string literals and deals with copies, right? It might be more memory efficient, however what about lookup? I believe there are native implementations of this inside when simply matching

Strings

, no? Also, turning unicode strings to char arrays won't work all that great?

how large is "rather large"?

okay its not really really large, about 600 keys, hwoever they mostly looked like this

"usage_weekly": "/ týždeň",
"used_1_data": "použitý",
"used_1_min": "prevolaná minúta",
"used_1_sms": "odoslaná správa",
"used_24_data": "použité",
"used_24_min": "prevolané minúty",
"used_24_sms": "odoslané správy",
"used_x_data": "použitých",
"used_x_min": "prevolaných minút",
"used_x_sms": "odoslaných správ",

so, trie could optimize the size

i don't know the answer to your questions but I think if your map is <10k entries, or even 100k I wouldn't worry. definitely measure before you optimize

@ursus Hi! Everything is an object in Kotlin. This does not mean they are not handled as primitives under the hood on the JVM. For instance,

Char

is handled under the hood as

char

on the JVM. However, there are cases where the JVM uses boxes around those primitives. For instance,

List<Char>

boxes the characters but

CharArray

does not. Also,

String

are interned on the JVM. I can't say about the performance however. In general, the JVM is very good at optimizing standard patterns. You should not try to prematurely and manually optimize things.

yes but interning is for literals, isnt it?

JVM string constants are automatically in the intern pool. strings can be manually interned, and there are some cases where it may make sense - e.g. if you expect to be re-constructing the same string repeatedly - but in practice the string pool is a fixed size hashmap, so make sure to have a realistic system benchmark before you consider interning strings (it may affect other code unexpectedly due to contention or eviction)

Yea I was worried about that node representation, even though hashmap has those entry objects, but this would require object per char; guess value types cant come soon enough

even if there were value types, an uncompressed trie is very wasteful. 12-byte object header + 16-bit char key + 32- or 64-bit pointer to data + padding = 32 or 40 bytes per character, while modern JVM String uses compact strings and can usually be 1 byte per character

yes that was kind of the reason i posted here, i expected jvm string to be heavily optimized, unless there is some trick with primitive arrays to store not pointer but index of next one etc btw whats a compressed trie? compressed where, memory? disc?

for a set {"abc1", "abc2"}, a compressed trie is {"abc" => {"1", "2"}} instead of {'a' => {'b' => {'c' => {'1', '2'}}}}

I see, thanks!