Strings Just Got Faster

the mind blowing moment for me with Java came about 5 years into using it, when I encountered the idea - via some smart colleagues - that none of the extra 'stuff' is intrinsic to the language but rather is self-imposed.

Turns out you can write java without the stuff. No getters and setters, no interfaces or dependency injection, no separate application server (just embed one in your jar). No inheritence. Indeed no OOP (just data classes and static methods).

Just simple, c-like code with the amazing ecosystem of libraries and the incredibly fast marvel that is the JVM and (though this is less of a deal now with LLM autocomplete) a simple built in type system that makes the code practically write itself with autocomplete.

It's truly an awesome dev experience if you just have the power / culture to ignore the forces pressuring you to use the 'stuff'.

I've seen Java described as made for companies to be able to rotate out mediocre programmers as efficiently as possible without letting them mess things up easily, and it makes a lot of sense from that perspective. Barebones semantics to the point of being Spartan (can't even define your own operator overloads), easy to take another class and copy it with small modifications but not mess it up for anyone else (inheritance)..

Then there's C# which most anyone who's enthusiastic about software dev will find far nicer to work with, but it's probably harder for bargain basement offshore sweatshops to bang their head against.

Did you actually started to appreciate the same OOP that made class situations impossible to understand or did you gradually switched to a simplier OOP, made up of mostly interfaces and classes that implement them (as opposed to extending other classes)?

In my experience OOP is actually pretty pleasant to work with if you avoid extending classes as much as possible.

> These kinds of niche optimizations are still significant. The OOP model allows them to be implemented with much less fanfare.

If you're referring to the optimization in the article posted then I would argue an OOP model is not needed for it, just having encapsulation is enough.

You can use the JVM without needing to use OOP e.g. Scala, Clojure, Python, Javascript, Ruby etc.

Then you can get to benefit from Java's unparalleled ecosystem of enterprise hardened libraries, monitoring etc.

Yes. I moved a few repository from java 8 up to Java 21.

Java 8 -> 9 is the largest source of annoyances, past that it's essentially painless.

You just change a line (the version of the JRE) and you get a faster JVM with better GC.

And with ZGC nowadays garbage collection is essentially a solved problem.

I worked on a piece of software serving almost 5 million requests per second on a single (albeit fairly large) box off a single JVM and I was still seeing GC pauses below the single millisecond (~800 usec p99 stop the world pauses) despite the very high allocation rate (~60gb/sec).

The JVM is a marvel of software engineering.

I have done it multiple times for different versions of Java with nominal effort. Of course, difficulty may vary depending on a project.

With projects like OpenRewrite [1] and good LLMs, things are a lot easier these days.

[1]: https://docs.openrewrite.org

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.

String compression was one. tl;dr: the JVM supports Unicode for strings, but uses 1-byte chars for strings where possible (previously it was UTF-16), even though it's not actually doing UTF-8.

Depending on what sort of document you're looking for, you might like either the JEP: https://openjdk.org/jeps/254

or Shipilev's slides (pdf warning): https://shipilev.net/talks/jfokus-Feb2016-lord-of-the-string...

Shipilev's website (https://shipilev.net/#lord-of-the-strings), and links from the JEP above to other JEPS, are both good places to find further reading.

(I think I saw a feature article about the implementation of the string compression feature, but I'm not sure who wrote it or where it was, or if I'm thinking about something else. Actually I think it might've been https://shipilev.net/blog/2015/black-magic-method-dispatch/, despite the title.)

This is a good video that goes over a ton of the optimizations, especially around concatenation: https://youtu.be/z3yu1kjtcok?si=mOdZ5sh5rp8LNyap

> 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.

> 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.

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;
      }
  }

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.

> 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?

So, the problem here is that you're thinking of "cryptographic properties" as only the "cryptographic hashes" such as those built with the Merkle–Damgård construction (SHA-512/256 being the one you might reasonably pick today)

But, it's actually desirable to have some cryptographic properties in a faster one way function for making hash tables. Read about SipHash to see why.

Because Java didn't (and as others have discussed, now can't) choose otherwise the hash table structures provided must resist sabotage via collision, which isn't necessary if your attacker can't collide the hash you use.

Even in collections, an unstable hash is desirable -- to avoid denial of service attacks caused by attacker-controlled hash collisions.

For example, Python back in 2012: https://nvd.nist.gov/vuln/detail/cve-2012-1150.

The thing is, even it being used just in collections can lead to DOS, if the attacker can control the string contents, and selectively choose strings that your hash table stops being a hash table and turns into a linked list.

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/56468c42bef8524e53a929dc...

Depends on which Map / Set implementation you use. There are multiple, each with different and interesting properties.

Languages that choose to fix this problem at the hash code level have hash codes that are still deterministic within a given program execution. They are not deterministic between executions, cf

https://docs.python.org/3/reference/datamodel.html#object.__...

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.

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".

But it doesn't support using fancy unicode quotes as string delimiters.

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

> 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.

After JIT compilation, yes (presumably), but for interpreted byte code I assume that a regular object is still allocated.

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.

How does the jvm know the map is immutable?

But interned strings can also reuse their hashcode forever.