7 ms·

Strings Just Got Faster

• gavinray 2y ago
  This post makes mention of a new JEP I hadn't heard of before: "Stable Values" https://openjdk.org/jeps/502 https://openjdk.org/jeps/502 https://cr.openjdk.org/~pminborg/stable-values2/api/java.base/java/lang/StableValue.html https://cr.openjdk.org/~pminborg/stable-values2/api/java.bas... I don't understand the functional difference between the suggested StableValue and Records, or Value Classes. They define a StableValue as: > "A stable value is a holder of contents that can be set at most once." Records were defined as: > "... classes that act as transparent carriers for immutable data. Records can be thought of as nominal tuples." And Value Objects/Classes as: > "... value objects, class instances that have only final fields and lack object identity." Both Records and Value Objects are immutable, and hence can only have their contents set upon creation or static initalization.
  • deleted 2y ago
    [deleted]
  • sagacity 2y ago
    Handwavy explanation: A stable value is used as a static constant, with the difference being that you can initialize it at runtime. Once initialized it is treated as fully constant by the JVM. It's similar to something like lateinit in Kotlin, except on the JVM level. Records are also immutable, but you can create them and delete them throughout your application like you would a regular class.
    • gavinray 2y ago
      But this is also achievable with static init methods on records and value classes, right? record Rational(int num, int denom) { Rational { int gcd = gcd(num, denom); num /= gcd; denom /= gcd; } }
      • sagacity 2y ago
        How would you do the same thing with the late initialization of, say, a HashMap where you don't control the constructor?
        • gavinray 2y ago
          Hmm, I see what you're saying -- yeah, this seems to be semantically identical to Kotlin's `lateinit` then
          • sagacity 2y ago
            Exactly. AFAICT this will be optimized at the JVM level though, so once you've initialized the constant the JIT compiler can take full advantage of that fact.
    • pkulak 2y ago
      So every time you take the hash of a string you leak 4 bytes of memory??? I assume it's static in the context of it's containing object. So, it will be collected when it's string is collected.
      • nimrody 2y ago
        No. The string hash is stored as part of the String object. It is initialized to 0 but gets set to the real hash of the string on first call to hashCode() (which is why it will be computed over and over again if your special string happens to hash to 0)
    • leksak 2y ago
      > It's similar to something like lateinit in Kotlin, except on the JVM level. What level are you suggesting lateinit happens at if not on the JVM?
      • Tmpod 2y ago
        I assume they mean this feature is built into the JVM itself, whereas Kotlin's lateinit more or less "just" desugars into code you could otherwise write yourself.
    • w10-1 2y ago
      > used as a static constant Yes, but remind people it's not static in the sense of being associated with the class, nor constant for compile-time purposes. Perhaps better to say: A stable value is lazy, set on first use, resulting in pre- and post- initialization states. The data being set once means you cannot observe a data change (i.e., appears to be immutable), but you could observe reduction in resource utilization when comparing instances with pre-set or un-set values -- less memory or time or other side-effects of value initialization. So even if data-immutable, a class with a stable value ends up with behavior combinations of two states for each stable value. Immutable records or classes without stable values have no such behavior changes. But, writ large, we've always had this with the JVM's hotspot optimizations. For String, it becomes significant whether hashcode is used when calculating equals (as a fast path to negative result). If not, one would have two equal instances that will behave differently (though producing the same data), at least for one hashcode-dependent operation.
      • owlstuffing 2y ago
        Right. Oracle should reconsider the naming here: stable -> lazy
  • whartung 2y ago
    I don't know, these are mostly uninformed guesses, but the distinction between Records and Value objects is that the contents lack object identity. Which, to me, means, potentially, two things. One, that the JVM can de-dup "anything", like, in theory, it can with Strings now. VOs that are equal are the same, rather than relying on object identity. But, also, two, it can copy the contents of the VO to consolidate them into a single unit. Typically, Java Objects and records are blobs of pointers. Each field pointing to something else. With Value Objects that may not be the case. Instead of acting as a collection of pointers, a VO with VOs in it may more be like a C struct containing structs itself -- a single, continuous block of memory. So, an Object is a collection of pointers. A Record is a collection of immutable pointers. A Value Object is (may be) a cohesive, contiguous block of memory to represent its contents.
  • blacklion 2y ago
    Records can be changed via reflection and thus doesn't participate in constant-folding in JIT phases, as this could break, for example, some serialization libraries and other nasty and dirty code. It will work in interpreter mode and eventually has heisenbugs after JIT. Not good. `@Stable` annotation (only internal for now) and `StableValue<>` (for user code in future) says JIT that programmer guarantee (swear by his life!) that no dirty tricks are played with these values in whole codebase and JIT can constant-fold these values as soon as they are initialized.
    • _old_dude_ 2y ago
      I've just tried to change a field of an instance of a record using reflection, and it's not possible, even with setAccessible(true).
      • blacklion 2y ago
        ooops, my bad. I remember, that Aleksey Shipilëv explained why even `final static` fields are not constant-folded by JIT, and thought that record classes which were introduced later, is the same. It means, that `StableValue<>` can be used in simple classes (where `final` fields are still not constant-folded) and, additionally, supports late initialization.
        • cempaka 2y ago
          Yeah the Java team took the opportunity while introducing the new record feature to explicitly forbid mutating their final fields. Their intention is to eventually enforce the same invariants across all Java fields unless the JVM is passed an explicit opt-out flag. And if you're not reliant on any frameworks using reflection to modify final fields, there's already a flag you can use today which will instruct the JVM to "trust" and apply optimizations to `final`.
  • _old_dude_ 2y ago
    In Java, constants are declared as static final. static final Complex CONSTANT = new Complex(1, 2); If you want a lazy initialized constant, you want a stable value static final StableValue<Complex> STABLE_VALUE = StableValue.of(); Complex getLazyConstant() { return STABLE_VALUE.orElseGet(() -> new Complex(1, 2)) } If you want the fields of a constant to be constant too, Complex has to be declared has a record.
  • drob518 2y ago
    A stable value, as I understand it, is either not-yet-computed or is constant. In other words, once computed it’s constant and the JIT can therefore treat it as constant.
  • layer8 2y ago
    Record fields cannot be lazily initialized. The point of StableValue is lazy initialization, meaning that their value is stable if and only if they carry a non-default value (i.e. after initialization). If you don’t need lazy initialization, you can just use a regular final field. For a non-final field, without StableValue the JIT optimizer can’t tell if it is stable or not. The implementation of a value object will be able to use StableValue internally for lazy computation and/or caching of derived values.
  • elric 2y ago
    - StableValue is about defining when and how to lazily initialy a field, with strong "exactly-once" semantics. The kinds of things we would do with safe double-checked locking before, but more convenient. Using a record doesn't address that, though you could certainly put a record in a StableValue. Additionally, having to define a record FooHolder(Foo foo) simply to hold a Foo would be a lot more cumbersome than just saying StableValue<Foo> fooHolder = StableValue.of(); There's no need for an extra type. - Value classes have no identity, which means they can't have synchronized methods and don't have an object monitor. While it would be possible to store a value object inside a StableValue, there are plenty of use cases for an identity object inside a StableValue, such as the Logger example inside the JEP: one could easily imagine a fictional logger having a synchronized method to preserve ordering of logs. I wouldn't say these are all entirely orthogonal concerns, but they are different concepts with different purposes.
  • ajkjk 2y ago
    It's a much-needed idea but... such an awkward way to do it. Only Java would be okay with an actual language feature using words like "orElseGet". And personally I suspect there's an inverse correlation between feature usage and how semantically awkward it is... it just feels like a mistake to even consider using an inelegant feature unless it's out of complete necessity. It should really be something like public stable logger = () -> new Logger(/* .. */). Where the JDK hides the details of making sure the value is only created once, basically like the classholder idiom but under the hood. I'm sure there are reasons why they're not doing it that way, but ... it's definitely what the language needs to be able to do. Incidentally, I've always appreciated for python PEPs how they list all of the obvious complaints about an issue and explain methodically why each was determined not to work. The JEPs don't seem to reach quite the same candor.
• Traubenfuchs 2y ago
  This all sounds very hard to grasp for me. Does this only work with Map.of? Would it also work with map.put? What would be the performance improvement in average java services? Are there specific types of applications that would benefit a lot? Does this make string.intern() more valueable? String caches?
  • amiga386 2y ago
    > Does this only work with Map.of? Would it also work with map.put? It would be faster but not as blindingly fast. Combined with an immutable map, what it means is that the JVM can directly replace your key with its value, like the map is not even there. Because the key's hashcode won't ever change, and the map won't ever change. > Does this make string.intern() more valueable? No, String.intern() does a different job, it's there to save you memory - if you know a string (e.g. an attribute name in an XML document) is used billions of times, and parsed out of a stream, but you know you only want one copy of it and not a billion copies). The downside is that it puts the string into PermGen, which means if you start interning normal strings, you'll run out of memory quickly.
    • Traubenfuchs 2y ago
      How does the jvm know the map is immutable? But interned strings can also reuse their hashcode forever.
      • amiga386 2y ago
        Map.of() promises to return an immutable map. new HashMap<>() does not. 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... How it tells the JVM this? It uses the internal annotation @jdk.internal.ValueBased https://github.com/openjdk/jdk/blob/jdk-17-ga/src/java.base/share/classes/java/util/ImmutableCollections.java#L144 https://github.com/openjdk/jdk/blob/jdk-17-ga/src/java.base/...
    • daxfohl 2y ago
      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.
• daxfohl 2y ago
  Cool that we're still seeing perf improvements after all these years! I'm confused by some of the details in the example. Like, would we see similar 8x improvement in a simpler example like a string hashset lookup? Is there something special about MethodHandle or immutable maps here that accentuates the improvement? > Computing the hash code of the String “malloc” (which is always -1081483544) Makes sense. Very cool. > Probing the immutable Map (i.e., compute the internal array index which is always the same for the malloc hashcode) How would this work? "Compute" seems like something that would be unaffected by the new attribute. Unless it's stably memoizing, but then I don't quite see what it would be memoizing here: it's already a hash map. > Retrieving the associated MethodHandle (which always resides on said computed index) Has this changed? Returning the value in a hash map once you've identified the index has always been zero overhead, no? > Resolving the actual native call (which is always the native malloc() call) Was this previously "lazyinit" also? If so, makes sense, though would be nice if this was explained in the article.
  • twic 2y ago
    > How would this work? "Compute" seems like something that would be unaffected by the new attribute. The index is computed from the hashcode and the size of the array. Now that the hash code can be treated as a constant, and the size of the array is already a constant, the index can be worked out at compile time. The JVM can basically inline all the methods involved in creating and probing the map, and eliminate it entirely.
    • daxfohl 2y ago
      The bucket is computed from the hash code and the size of the array, but that's not necessarily the index. If there are no bucket collisions, then index==bucket and this works out. But if there are bucket collisions then the index will be different from the bucket. So you still need some computation IIUC. And there's no way to memoize that result, since memoization would require a hashmap that has the exact same characteristics as the original hashmap. I guess a @Stable attribute on the array underlying the map would allow for the elimination of one redirection: in a mutable map the underlying array can get resized so its pointer isn't stable. With an annotated immutable map it could be (though IDK whether that'd work with GC defrag etc). But that seems like relatively small potatoes? I don't see a way to "pretend the map isn't even there".
• esafak 2y ago
  Will Kotlin and Scala benefit?
  • daxfohl 2y ago
    They should. It's a JVM feature on core JDK classes.
    • taeric 2y ago
      This implies they have their own String implementations? I wouldn't be shocked to find out that is the case, but it would surprise me.
      • daxfohl 2y ago
        Why? IIUC it implies that they _don't_ have their own string implementations. They get the benefit of Java JDK's string implementation (and JVM optimization thereof) for free. If they had their own string implementations, they'd be unable to use this optimization until it's publicly available.
        • taeric 2y ago
          Ha! My apologies, I misread that as "they shouldn't." Not sure why.
      • xxs 2y ago
        Java strings enjoy heavy optimizations, including SSE4.2 and AVX intrinsics. Implementing your own byte[] wrappers (which Strings are) might be useful however it won't replace the built-in Strings. In short: a general purpose String substitute in Java would be an extremely poor idea.
  • jillesvangurp 2y ago
    If you use Kotlin/Scala on the JVM, yes. You can also use Kotlin on native (ios, win32, linux, etc), wasm, or on top of javascript. Scala has at least a js compiler and maybe some other ones as well. You won't see any improvements on these other platforms.
• _tom_ 2y ago
  Off-the-cuff thought: Could you solve the empty string hashes to zero problem by just adding one when computing hash codes?
  • layer8 2y ago
    You could, but that would break backwards compatibility.
  • Karellen 2y ago
    But then strings with the hash code HASH_MAX would wrap to 0 instead.
  • deleted 2y ago
    [deleted]
• deleted 2y ago
  [deleted]
• Bootvis 2y ago
  Is @Stable a generalization of the final keyword or is there more to it that I'm missing?
  • selkin 2y ago
    Final is an access modifier. It controls who can change a value (in this case, no one). And like other access modifiers, you can use reflection to remove or change those modifier. It is a security barrier the developer asks the system to uphold. The Stable annotation is an optimization mechanism: a promise the developer makes to the compiler. It is on the developer to uphold.
• vault 2y ago
  why is a website about programming not writing code blocks in ASCII? I'm referring to quotes and other undesirable symbols
  • VWWHFSfQ 2y ago
    Java supports non-ASCII source code since forever. A lot of languages do.
    • dullcrisp 2y ago
      But it doesn't support using fancy unicode quotes as string delimiters.
• int_19h 2y ago
  I'm rather surprised that string hashes aren't randomized in JVM - or at least that's what the article implies. These days, it's a fairly common mitigation for DDoS attacks based on hash collisions. Does Java not do it to preserve backwards compatibility because too much existing code relies on a specific hashing algorithm?
  • sedatk 2y ago
    Java uses a tree instead of a linked list for collided items, so the search performance degrades more gracefully (e.g. O(N) vs O(logN)).
    • 77 2y ago
      To be more precise, Java initially uses a linked list for nodes within a bin. If the number of items inside the bin crosses TREEIFY_THRESHOLD (which is 8), then that specific bin is converted into a RB tree. This is detailed in implementation notes comment here: https://github.com/openjdk/jdk/blob/56468c42bef8524e53a929dc2ae603cff05b55e3/src/java.base/share/classes/java/util/HashMap.java#L146 https://github.com/openjdk/jdk/blob/56468c42bef8524e53a929dc...
    • jillesvangurp 2y ago
      Depends on which Map / Set implementation you use. There are multiple, each with different and interesting properties.
  • yxhuvud 2y ago
    Nothing stops the jvm from caching hashes even if the hashes are unique per process invocation.
    • PaulHoule 2y ago
      They aren’t and it’s quite unfortunate that the empty string hashes to 0 so it will have to recompute every time although presumably it is quick to compute the hash of the empty string.
  • 2y ago
• stevoski 2y ago
  I find the entire history of improvements to Java’s String class enjoyable to read about. Over the years, the implementation of Java’s String class has been improved again and again, offering performance improvements and memory usage reduction. And us Java developers get these improvements with no work required other than updating the JRE we use. All the low-hanging fruit was taken years ago, of course. These days, I’m sure most Java apps would barely get any noticeable improvement from further String improvements, such as the one in the article we’re discussing.
  • niuzeta 2y ago
    I love hearing more about this, especially the historical context, but don't have a good java writeups/articles on this. Would you mind sharing some suggestions/pointers? I'd very much appreciate it.
    • stevoski 2y ago
      A good starting point is Joshua Bloch’s Effective Java. He shares some stories there from Java’s early days, and - at least in passing - mentions some aspects of the String class’s history.
      • niuzeta 2y ago
        Ah, I certainly remember these anecdotes! What other resources would you recommend(even the tidbits) could there be for more modern Java? The original article like this one should be treasured.
    • DaiPlusPlus 2y ago
      > Would you mind sharing some suggestions/pointers? I would, but unfortunately I got a NullPointerException. I suggest you try Rust instead; its borrow checker will ensure you can't share pointers in an unsafe manner.
      • gf000 2y ago
        I know it's a tongue in cheek reply but.. You can't share "pointers" in an unsafe manner in Java. Even data races are completely memory safe.
• spoonsort 2y ago
  Having a @Stable annotation which the standard library can use to signal things to the compiler like that is very smart. I wonder how many standard libraries are missing out on optimizations like this.
• delusional 2y ago
  The example is entirely unconvincing. Why would you store those calls in a map and not just a variable? Even if the map is crucial for some reason, why not have the map take a simple value (like a unint64) and require the caller to convert their string into a slot before looking up the function pointer. That way the cost to exchange the string becomes obvious to the reader of the code. I struggle to find a use case where this would optimize good code. I can think of plenty of bad code usecases, but are we really optimizing for bad code?
  • koolba 2y ago
    > I struggle to find a use case where this would optimize good code. I can think of plenty of bad code usecases, but are we really optimizing for bad code? The most common such usage in modern web programming is storing and retrieving a map of HTTP headers, parsed query parameters, or deserialized POST bodies. Every single web app, which arguably is most apps, would take advantage of this.
    • delusional 2y ago
      > storing and retrieving a map of HTTP headers. I dont have the profiling data for this, so this is pure theoretical speculation. At the time you're shoving http headers, which is dynamic data that will have to be read at runtime, into a heap allocated datastructures inside the request handling. It kinda feel like doing a little xor on your characters is a trivial computation. I don't envision this making any meaningful difference to those HTTP handlers, because they were written without regard for perfomance in the first place.
  • f33d5173 2y ago
    >but are we really optimizing for bad code? Yes
  • gf000 2y ago
    I think it's a pretty myopic view - this exact case might not appear as is, but might readily appear in completely sane and common code after inlining a few things and other optimisations.
• ashvardanian 2y ago
  Has anyone done/shared a recent benchmark comparing JNI call latency across Java runtimes? I’m exploring the idea of bringing my strings library to the JVM ecosystem, but in the past, JNI overhead has made this impractical.
  • throwaway2037 2y ago
    Can you share a link to your "strings library"? I am curious about what it can do that a Java String cannot.
    • ashvardanian 2y ago
      At this point, it doesn’t provide much novel functionality, but it should be faster than the standard libraries of most (or maybe all) programming languages. https://github.com/ashvardanian/StringZilla https://github.com/ashvardanian/StringZilla
  • cempaka 2y ago
    Java has replaced JNI with the Project Panama FFM, which depending on your use case might perform quite a bit better than JNI used to. The Vector API is stuck in incubator and still a bit rough around the edges though, so SIMD might be a bit trickier.
• kazinator 2y ago
  I experimented with hash codes in strings in TXR Lisp, but took it out after several days: commit a136f37015cc2513878f75afcf8ba49fa61a88e5 Author: Kaz Kylheku <kaz@kylheku.com> Date: Sat Oct 8 20:54:05 2022 -0700 strings: revert caching of hash value. Research indicates that this is something useful in languages that abuse strings for implementing symbols. We have interned symbols. * lib.h (struct string): Remove hash member. * lib.c (string_own, string, string_utf8, mkustring, string_extend, replace_str, chr_str_set): Remove all initializations and updates of the removed hash member. * hash.c (equal_hash): Do not cache string hash value. > This improvement will benefit any immutable Map<String, V> with Strings as keys and where values (of arbitrary type V) are looked up via constant Strings. Wait, what? But, that's inherently constant foldable without reasoning about string hash codes; we don't need them at all. We examine the expression [h "a"]: lookup the key "a" in hash table h, where h is a hash literal object, that we write as #H(() ("a" "b)). It contains the key "a", mapping it to "b": 1> (compile-toplevel '[#H(() ("a" "b")) "a"]) #<sys:vm-desc: 8eaa130> What's the code look like? 2> (disassemble *1) data: 0: "b" syms: code: 0: 10000400 end d0 instruction count: 1 #<sys:vm-desc: 8eaa130> One instruction: just return "b" from the static data register d0. The hash table is completely gone. The keys don't even have to be strings; that's a red herring.
  • josefx 2y ago
    > Wait, what? But, that's inherently constant foldable without reasoning about string hash codes; we don't need them at all. Their goal wasn't to improve key lookups in hash tables, that is more or less just an example.It was to improve optimization of variables with lazy initialisation overall and the hash of String uses lazy initialisation.
• jbverschoor 2y ago
  So strings don’t get hash code at compile time? At first I thought the article was describing something similar to Ruby’s symbols
  • chii 2y ago
    > So strings don’t get hash code at compile time? only strings that are known at compile time could possibly be compile-time hashed? But the article is talking about strings in a running program. The performance improvements can apply to strings that are constants, but is created at run time.
• layer8 2y ago
  It’s a bit unfortunate that the user code equivalent (JEP 502) comes at the cost of an extra object per “stable” field. Lazy initialization is often motivated by avoiding creating an object up-front, but with this new pattern you’ll have to create one anyway.
  • elric 2y ago
    Well, no. The JVM makes the wrapper object disappear. One of the design drivers for StableValue was performance. I mean the developer has to create the StableValue field, but its access is optimized away.
    • layer8 2y ago
      After JIT compilation, yes (presumably), but for interpreted byte code I assume that a regular object is still allocated.
      • cempaka 2y ago
        The general thinking around this is that if you're still in interpreted code, you're not in the kind of context where the cost of an extra object allocation is worth worrying about.
      • elric 2y ago
        This is addressed in the JEP: > There is, furthermore, mechanical sympathy between stable values and the Java runtime. Under the hood, the content of a stable value is stored in a non-final field annotated with the JDK-internal @Stable annotation. This annotation is a common feature of low-level JDK code. It asserts that, even though the field is non-final, the JVM can trust that the field’s value will not change after the field’s initial and only update. This allows the JVM to treat the content of a stable value as a constant, provided that the field which refers to the stable value is final. Thus the JVM can perform constant-folding optimizations for code that accesses immutable data through multiple levels of stable values, e.g., Application.orders().getLogger(). > Consequently, developers no longer have to choose between flexible initialization and peak performance.
• rf15 2y ago
  Strange to make an entire piece on String specifically - it seems like this is just based on the work done for the @Stable annotation and the many effects it can have on classes during runtime.
  • vanderZwan 2y ago
    I can understand the choice as an example for @Stable: it highlights that this addition even comes with "free" upgrades for (some) existing code out there, and it immediately shows a concrete use case. But yes, they could have gone further into generalizing from there. If you mean the headline, Strings are a universal data type across programming, so claims of improving their performance gets more clicks than "this annotation that you have never heard about before makes some specific code faster", especially when it comes to getting the attention of non-Java programmers.
• theanonymousone 2y ago
  It seems string typing is not as bad an anti-pattern as it used to be :) It will be a very impactful work; I'm excited to see. Probably even a 1% improvement in String::hashCode will have an impact on global carbon footprint or so.
• Karellen 2y ago
  Um, malloc() is not a system call?
  • xxs 2y ago
    no, mmap is a system call; the memory allocators tend not to use syscalls (often at all) as objection instantiation is very common; also it has to be concurrent and what not.
• koliber 2y ago
  Is this a correct summary: we memoized the hashCode() function?
  • matsemann 2y ago
    Not only that. By making it guaranteed constant after first invocation, they can fold the constant and basically avoid the map lookup in runtime and instead do it compile-time. In practice avoiding the map entirely.
  • nimrody 2y ago
    No. String.hashCode() was already memoized. So after the first call to hashCode(), future calls just retrieved the data from the hash field of the string object. This optimization is about avoiding even calling the method because the jvm knows that the value returned will be the same.
• smcin 2y ago
  Notwithstanding HN's guidline to preserve original title and not editorialize in any way, this would be less misleading if it had been titled 'Java Strings Just Got Faster in JDK 25'