3 ms·

How would it directly replace your key with its value? What if there are bucket collisions? Do immutable maps expand until there aren't any? Moreover, what if t

How would it directly replace your key with its value? What if there are bucket collisions? Do immutable maps expand until there aren't any? Moreover, what if there are hash key collisions? There needs to be some underlying mechanism to deal with these, I'd think. I don't see how replace-like-the-map-isn't-there could work. Or even how "@Stable" could be used to affect it. Would love to understand more deeply.

amiga386 1y ago
> How would it directly replace your key with its value? In the same way that if you wrote this C code: const int x[] = {20, 100, 42}; int addten(int idx) { return x[idx] + 10; } the C compiler would "just know" that anywhere you wrote x[2], it could substitute 42. Because you signalled with the "const" that these values will never change. It could even replace addten(2) with 52 and not even make the call to addten(), or do the addition. The same goes for Java's value-based classes: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/doc-files/ValueBased.html https://docs.oracle.com/en/java/javase/17/docs/api/java.base... But it's a bit more magical than C, because _some_ code runs, to initialise the value, and then once it's initialised, there can be further rounds of code compilation or optimisation, where the JVM can take advantage of knowing these objects are plain values and can participate in things like constant-folding, constant propagation, dead-code elimination, and so on. And with @Stable it knows it that if a function has been called once and didn't return zero, it can memoise it. > What if there are bucket collisions? Do immutable maps expand until there aren't any? Moreover, what if there are hash key collisions? I don't know the details, but you can't have an immutable map until it's constructed, and if there are problems with the keys or values, it can refuse to construct one by throwing a runtime exception instead. Immutable maps make a lot of promises -- https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Map.html#unmodifiable https://docs.oracle.com/en/java/javase/17/docs/api/java.base... -- but for the most part they're normal HashMaps that are just making semantic promises. They make enough semantic promises internally to the JVM that it can constant fold them, e.g. with x = Map.of(1, "hello", 2, "world") the JVM knows enough to replace x.get(1) with "hello" and x.get(2) with "world" without needing to invoke _any_ of the map internals more than once. What wasn't working until now was strings as keys, because the JVM didn't see the String.hash field as stable. Now it does, and it can constant fold _all_ the steps, meaning you can also have y = Map.of("hello", 1, "world", 2) and the JVM can replace y.get("hello") with 1

amiga386 1y ago

> How would it directly replace your key with its value? In the same way that if you wrote this C code: const int x[] = {20, 100, 42}; int addten(int idx) { return x[idx] + 10; } the C compiler would "just know" that anywhere you wrote x[2], it could substitute 42. Because you signalled with the "const" that these values will never change. It could even replace addten(2) with 52 and not even make the call to addten(), or do the addition. The same goes for Java's value-based classes: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/doc-files/ValueBased.html https://docs.oracle.com/en/java/javase/17/docs/api/java.base... But it's a bit more magical than C, because _some_ code runs, to initialise the value, and then once it's initialised, there can be further rounds of code compilation or optimisation, where the JVM can take advantage of knowing these objects are plain values and can participate in things like constant-folding, constant propagation, dead-code elimination, and so on. And with @Stable it knows it that if a function has been called once and didn't return zero, it can memoise it. > What if there are bucket collisions? Do immutable maps expand until there aren't any? Moreover, what if there are hash key collisions? I don't know the details, but you can't have an immutable map until it's constructed, and if there are problems with the keys or values, it can refuse to construct one by throwing a runtime exception instead. Immutable maps make a lot of promises -- https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Map.html#unmodifiable https://docs.oracle.com/en/java/javase/17/docs/api/java.base... -- but for the most part they're normal HashMaps that are just making semantic promises. They make enough semantic promises internally to the JVM that it can constant fold them, e.g. with x = Map.of(1, "hello", 2, "world") the JVM knows enough to replace x.get(1) with "hello" and x.get(2) with "world" without needing to invoke _any_ of the map internals more than once. What wasn't working until now was strings as keys, because the JVM didn't see the String.hash field as stable. Now it does, and it can constant fold _all_ the steps, meaning you can also have y = Map.of("hello", 1, "world", 2) and the JVM can replace y.get("hello") with 1