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.
When I started my career in software development, SDE, and soon advanced to SRE, I hated Java. The extreme OOP paradigm made enterprise class situations impossible to understand. But after a few short years, I began to appreciate it as a real, battle hardened ecology. Now, I consider it much better than modern trends such as Rust and Python.
These kinds of niche optimizations are still significant. The OOP model allows them to be implemented with much less fanfare. This is in the context of billion-dollar platforms. With some basic performance testing and API replays, we're saving thousands of dollars a day. Nobody gets a pat on the back. Maybe some pizza on Friday.
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'.
The over engineering creeps in anywhere there is collaboration. It’s not a Java thing, it’s a corporate thing. The new teammate who refactors the perfectly working sql pipeline; the teammate who makes story points a required field on your trouble ticket system, the teammate who just saw a conference talk on rust and wants to apply it etc. Most engineers are not zen masters seeking out simplicity; they are lost with poor grasp of desired business outcomes so they procrastinate by adding complexity and indirection and focusing on tech as if it were the destination not the journey.
> lost with a poor grasp of desired business outcomes so they procrastinate by adding complexity
I have come to see this as a mix of business people and developers not doing their jobs to protect thier paycheck. Business people, if they want to succeed, need to be converging on a strategy that makes money. Developers need to have a strategy for removing technical barriers to realizing that strategy. The lack of a business strategy often makes an overly general technical platform look attractive.
> focusing on the tech as if it were the destination
So common. Complexity should be considered the enemy, not an old friend.
True, but there's also the bored engineers who just can't force themselves to write enterprise code unless they make it fun for themselves. I'm absolutely convinced this is why Clojure even exists and is so widely used in fintech.
The extreme focus on multiple layers of patterns, where actually a simple function would have sufficed IS a Java ecosystem and culture thing. Just way too many people doing Java, who have never learned another language or ecosystem, let alone paradigm, thinking "I learned Java, Java can do everything, I don't need to learn anything else!" and now feeling they need to solve every problem by applying design patterns mindlessly.
Well, not by talking about AbstractFactoryProxy, that much is for sure. Rather by talking about which parts of the system are modular and what kind of flexibility the system allows for, what capabilities it has. Nowhere in that picture does a low level implementation detail like an AbstractBlaBlubFooBar enter the the conversation.
There is more to computer programming than the OOP clutter.
Yes and: Mocks (mocking?) is a code stench. Just flip the ownership relationship(s). As Riel, and surely many others, have laboriously explained, to a mostly uncaring world.
Prefer inheritance if the first thing you're gonna have to do under composition is to crank out a bunch of delegate methods from the parent object to the contained child, to make the parent substitutable for the child, and the child won't be replaced at run time.
Probably. I personally haven't done anything like that. Though I'm not sure I follow.
I've mostly done ASTs and (scene) graphs. I prefer dumb objects, stuffing most behavior and logic in an Interpreter (design pattern) implementation. Being a very simple bear, my working memory can't keep track of all the smarts scattered all about.
My current example is processing SQL statements; think expression evaluator (subset) for a very specific use case. I tend to use so called "External" Iterators for walking trees, to keeping all the logic in one place. Versus Visitor, Listeners, or even Active Objects. Which is feasible for this use case, because its bounded and unlikely to change (eg extension points).
YMMV of course. Now I'm just babbling, apologies, and probably went too far off topic.
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.
I really don't think this stance aged well, even if it was closer to true way back when. IMO the spartan language is now Go, and Java has ended up the boring open source workhorse. The jvm is very performant compared to many stacks these days (python Ruby node) while still having a very compelling concurrent programming story, and has a lot of nice language feature things ever since 8 and onwards. Lambdas and streams are the big 8's, but I think virtual threads growing up and even new things like scoped variables are really compelling reasons to build a new thing in java right now.
You need just the right amount of expressivity in a language, so that it is hard to abuse, but still allows writing easy to use libraries.
Java has went over this evolution, implemented generics, lambdas, etc and I believe it strikes a very good balance in not being overly complex (just look at the spec - it's still a very small language, compared to its age, unlike C++ or C#).
Go tried to re-invent this evolution, without having learnt Java's lessons. They will add more and more features until their "simple" will stop applying (though I personally believe that their simple was always just simplistic), simply because you need some expressivity for better libraries, which will later on actually simplify user code.
The problem with the JVM, compared to Go, is the GC; it requires a lot of reserved memory. Go programs use far less.
And the SDK is bulky, which can be a problem for container images - although arguably it should be considered irrelevant, as you only download base images once, if done correctly.
You're not supposed to use the runtime directly these days. jlink allows you to strip unnecessary things (like documentation for the runtime itself), extract only those parts of the runtime you need (though your project must use modules to support that), and then aggressively compress it all getting a pretty small package that runs on an empty OS with no dependencies other than libc. It's still a bunch of files, so for good user experience you would have to ship it as a container (or something like .exe or appimage), but it's really close to Go in terms of size.
It's a configurable property, and Java has a bunch of GCs to begin with.
Also, not using as much memory in these types of GCs is a direct hit to performance. And this actually shows splendidly on GC-heavy applications/benchmarks.
We were paying a million a month for a custom high performance GC for a little bit but we were able to get off that with a lot of development effort and get our five 9's latency under control.
I tried and gave up on getting Keycloak to use less memory. 500-1500 MB for a server with less than 10 concurrent users is ridiculous. And that's even using an external database.
Much less of a problem in .NET (its GC tuning sits somewhere in between the two, especially when SRV GC + DATAS is in use, like in container scenarios, where Go is funnily unaware of limits set by cgroups and needs an external package to fix it). It does pre-allocate more memory than Go per se but in return yields much, much higher allocation throughput out of box. Java allows for even higher allocation throughput, having multiple more sophisticated GC implementations but as you said is not very good at reducing sustained RSS used by an application.
Off the top of my head? Bazel is the Java program I use the most. Hadoop/hive and similar stuff also heavily Java but I'm not sure how much that's in use anymore
I'm not saying there's no Java in open source. And I'm aware of the projects you mention. I don't run them though. And they definitely don't qualify as "the boring open source workhorse".
There are a couple of Java projects, and even one or two kind of successful ones. But Java in open source is very rare, not the boring workhorse.
If I worked on a project that used Bazel, then sure, I'd use Bazel every day.
But which is "the boring workhorse" of open source, if I gave you the option of Java, Make, Linux, gcc, llvm, .deb, would Java really be "the" one?
Sure, maybe you could exclude most of those as not being "boring", like llvm. But "make" wins by any measure. And of course, it's almost by definition hard to think about the boring workhorse, because the nature of it is that you don't think about it.
Checking now, the only reason I can find java even being installed on my dev machines is for Arduino IDE and my Android development environment. Pretty niche stuff, in the open source space.
Most Java applications nowadays are based 100% on open source stack with hundreds of libraries and frameworks and Java dominates enterprise space, so it is a huge open source workhorse, just more obscure than Linux, gcc etc.
Ok, we clearly have an extremely different definition of the word "the" workhorse of open source.
It doesn't mean "more than zero projects are Java based". Nor does it mean "most (opensource?) Java applications are based on open source". That latter is borderline circular, only Oracle legal shenanigans makes it not circular.
> and Java dominates enterprise space
I said nothing about enterprise. Clearly Java is HUGE in enterprise.
> so it is a huge open source workhorse
That sentence took a strange turn. Enterprise, and then back to open source?
> just more obscure than Linux, gcc etc.
Obscure? I'd expect Java to be about as strong a brand as Linux. Among developers in general I'd expect gcc to be orders of magnitude more obscure. There's no programmer out there who has not heard of Java, but many have never heard of gcc.
> Ok, we clearly have an extremely different definition of the word "the" workhorse of open source.
You said what it is not, but forgot to share your own definition.
>That sentence took a strange turn. Enterprise, and then back to open source?
What makes you so surprised? One does not exclude another, enterprise users are users too. Most of things in Java world aren’t client-side, so many users won’t observe them directly, but open source Java technology is doing a lot of work for them, constituting significant share of the code base.
Half of the internet is literally running that.. like unless you deliberately avoid Java stacks, you will come across it. It's one of the top 3 ecosystems in size, with JS and python being the other 2 contenders.
The lack of operator overloading is a bit annoying but in practice seldom a real problem. An operator is just a funny looking method. So what.
There are worse fundamental problems in Java. For example the lack of a proper numeric tower. Or the need to rely on annotations to indicate something as basic as nullabilty.
It’s a massive annoyance when working with any sort of numeric code. Or custom collections. Or whatever else the standard library enjoys that nobody else gets to use.
I remember the times on one of professional forums, where there was lots of questions about architecture in C# sections and almost none in Java section. Abundance of tools creates abundance of possibilities to get confused about what’s right. In Java many design decisions converged to some dominant design long time ago, so you no longer think about it and focus on business. It’s sometimes as bad as getter verbosity (thankfully record style is getting traction), but in most cases it’s just fine.
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.
Also note that the OP said “avoid extending classes”, but didn’t say “avoid implementing interfaces”, so they don’t disallow inheritance in a wide sense of the word.
I think “avoid extending classes” is there because it is as good as impossible to design classes that can be extended easily in ways you do not foresee, and if you do foresee how your classes could be extended, it often is easier for your users if you made your classes more flexible, to start with.
You can get Encapsulation, abstraction, and polymorphism any number of other ways. Inheritance is the only defining property of OOP.
If you removed all the stuff related to inheritance and trying to fix the leaky abstraction that is objects, the language would be a fraction of the size (compare with Go or StandardML for how small a language without inheritance can be).
I'd say that the 'poor man's closures' aspect of OOP - that is, being able to package some context along with behaviour is the most useful part for day to day code. Only occasionally is inheritance of anything other than an interface valuable.
Whether or not this is an endorsement of OOP or a criticism is open to interpretation.
> 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)?
My thoughts exactly. Give me more classes with shallower inheritance hierarchies. Here is where I think go’s approach makes sense.
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).
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.
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.
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.
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
(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.)
Absolutely love it. Thanks a lot. A fancy hit me yesterday and I've been looking through JDK's String commit history to see little tidbits that I could grab.
Shipilev's website looks like a fascinating resource. I appreciate the pointer!
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.
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.
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.
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.
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.
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)
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.
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.
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.
- 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.
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.
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.
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`.
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?
Java hashCode contract is to optimize calculation of hash for performance not for collision search resistance. Its sole purpose is to use it in collections. It must not be used in situations where you need cryptographic properties.
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.
The point is that since the hash is known and predictable, an attacker who can choose what keys get added to the map can choose them so every key collides, resulting in a DoS.
I assume Java has to add some other layer to avoid this, rather than using a collision resistant hash scheme.
There are specialized collections in external libraries for these kinds of situations to be used when you need them (and are ready to pay for them in terms of performance).
I don't imagine it was ivan_gammel's intention, but his mention of the original CCC/tomcat issue I think makes the point quite clear: have you ever had a hashmap of HTTP header to values? I hope it used one of those external libraries, because otherwise that's now a vector for DoS'ing any app that has one.
User influenced/controlled input happens way more than we expect, I think the more sensible approach would be for the map to be safe by default, and to reach for a high performance external map for those times when that particular data structure is the bottleneck.
>I think makes the point quite clear: have you ever had a hashmap of HTTP header to values?
Number of headers is limited by default to a relatively small value (10k), which in the worst case of hash collisions results in relatively fast lookup time due to tree-like implementation of HashMap.
Exactly, this data structure has to provide counter-measures to cope with the fallout from this other poor choice.
The fast data structures for this work don't need a tree here, they're open addressed instead, but this would mean they can't cope if your attacker can arbitrarily collide input, so, too bad.
This data structure has tree-like fallback for hash collisions in general, which do happen regardless of hash algorithm by definition of what is hash. It is not a coping mechanism for a poor choice, it’s elegant design allowing better performance for Comparable keys. By coincidence it mitigates the DoS attack too.
All the closed addressing strategies mean more allocator burden. In this case, each of these trees needs to grow separately. But with open addressing we can avoid that.
Suppose we have 10'000 key->value pairs to store. A Swiss Table (a popular open addressed hash table design) will need space for 16384 contiguous pairs plus metadata†. So it'll do that allocation once, but with the closed addressing and trees you're paying to grow trees during insertion, you can't know which trees will grow and which are unused.
You're correct that the Swiss Table will see collisions, but an attacker can't choose them, so they're rare. Each collision costs us a search step, but because the Java design incurs a pointer chase (to find the tree) for every lookup that's actually the same price [one memory fetch] as a single collision for the Swiss Table, yet most of the time the Swiss Table sees less than 1.0 collisions per lookup.
† It's ensuring no more than 87.5% of the storage is used and then rounding up to a power of two because that means less work for each look-up step. 11429 would be enough space, but 16384 is the next largest power of two.
In risk management there exist several different approaches: accept, mitigate, transfer, avoid. What makes you think that this design must avoid certain risks? The developers of standard libraries like Java usually base their decisions on industry feedback, IIRC, Oracle team did have a lot of telemetry data and they are good engineers. Do you have any insights proving that their approach is wrong?
> IIRC, Oracle team did have a lot of telemetry data and they are good engineers. Do you have any insights proving that their approach is wrong?
Time's arrow
Java is a Sun (Microsystems) language, Oracle just bought the entire company much later. So one problem here is that you're imagining this like it's a decision somebody made this century but it isn't, it's a decision from the early 1990s.
Computer Science is a young discipline. In the early 1990s the Open Addressed hash tables do exist but it's very usual to write the simple chained hash table with Closed Addressing and as I understand it that's exactly what is provided in Java 1.0. This data structure is today known to be a bad idea, and I've criticised the choice in say C++ to standardize the exact same data structure (as std::unordered_map) in 2011. But that's twenty years later.
At some point (I believe this century?) Java engineers went back and improved their hash table to use trees not chains, but they were constrained by the baked in hash, so they could not have picked radically modern data structures which require a different hash strategy without significant disruption.
When I got a CS degree the Introspective sort was so new I'd have to have read bleeding edge research papers to know about it. Today it's very silly if you claim you provide a standard library sort and it's not at least as good as Introsort.
The Swiss Table is from the 2010s, it's new enough that there's a Youtube video of them introducing this data structure, not because they did that specifically on purpose but because they're giving a talk and obviously all talks are filmed and uploaded to Youtube these days. Hopskotch hashing - another popular Open Addressing strategy - is from 2008.
So, the question isn't "Is this the best idea today?" but only "Given what they knew 30+ years ago, was this reasonable back then?" and yeah, of course it was reasonable back then but that doesn't magically mean it's the best choice now.
Edited: Added paragraph about the later choice to use trees.
The standard library design choices are influenced not only by algorithm performance, but also by the use cases, existing contracts etc. You did not answer my question. Why do you think choosing alternative algorithm and breaking existing hash contract would be better?
> You did not answer my question. Why do you think choosing alternative algorithm and breaking existing hash contract would be better?
But I don't think Java should go break all this stuff. I'm just explaining why - in fact - we might want some cryptographic properties for hash algorithms. It can be true both that Java made reasonable tradeoffs at the time (in the 1990s) and that you shouldn't copy those choices today.
There's a long list of things Java picked that in hindsight weren't a good idea and in many cases it would have been really hard to guess that when Java was invented - however today you should not choose what Java did. Biggest example: 16-bit char. Java was invented when UCS-2 might happen, and in that light a 16-bit char makes sense. A few years later it's obvious UCS-2 is not possible and so you're choosing UTF-8 or UTF-16 and that's easy, pick UTF-8. People who'd already bought into the 16-bit char, such as Microsoft and Sun's Java team, were stuck with UTF-16 as a booby prize.
I think I lost you here actually. Hash by definition is just a mapping of arbitrary sets to large integers. Cryptographic hash adds computational complexity requirement so that it is prohibitively hard to find collisions (i.e. slow by design - bad choice for collections, which need fast hashing). Unstable hash is simply the one that is not guaranteed to persist between two different executions of a program (but it obviously has to be the same for equal objects in the same execution). Neither of collision resolution techniques requires cryptographic or even unstable hash. Collections only need hash to be sufficiently random on typical datasets for optimal performance. I would even question if unstable hash can mitigate the hash flooding attacks at all or it is possible to determine the hashing parameters of a black box somehow. Limit on number of parameters and efficiency at high load factors/high collisions is more important for security.
Many programming languages do not use open addressing and prefer chaining (Java, C#, Golang, std::unordered_map in C++) for simplicity and flexibility. There are certain trade offs to be considered, it is not a simple choice of absolutely the best known algorithms. I don't think Java made the wrong choice here. Notably, there was always a possibility to introduce a specific collection with some modern algorithm as an alternative to HashMap. It did not happen not least because it was not considered that important. I'm sure that in cases where open addressing offers substantial benefits, developers make conscious choice and use the appropriate data structures.
Regarding strings, since Java 9 (released long time ago) they can be stored in byte arrays if they contain only Latin-1 characters and core team is open for further enhancements.
No, the cryptographic hash functions are not slow by design. This is a nasty misunderstanding which leads to stuff like MD5(password) in PHP [not the PHK MD5 crypt() algorithm used in Unix systems in the 1990s, this was literally MD5(password) and it's a bad idea, do not do]
The cryptographic hash functions such as the SHA-2 family resist construction of a second pre-image, given N and H(N) there's no way for me to make M such that H(M) == H(N) but M != N that'll be faster than brute force trying all possible values for M. So far everything we have which achieves this is markedly slower than say FNV-1 which would once have been the most likely hashing algorithm for a hash table.
The one way password hashes, some of which are based on the cryptographic hashes, are slow by design. You should not use passwords, but on HN this seems like a lost cause so, assuming you insist on using passwords these algorithms are specifically what you need. Fighting about which one to use ("oh no, PBKDF2 isn't memory hard, blah blah blah") is also a bottomless hole of HN nonsnse, so, fine, pick whichever of them you're certain is the only correct one.
But we do ideally want some cryptographic properties for a hash to be used in a hash table and your instinct that just using a random factor and hoping won't work was correct. You need a correctly designed function, which is what SipHash is. What you want is some keyed function with a key K such that if I know N and H(K,N) but not K, I can't guess an M such that H(K,M) = H(K,N) but M != N except by brute force.
> Many programming languages do not use open addressing and prefer chaining (Java, C#, Golang, std::unordered_map in C++) for simplicity
This was true in Golang but today the map in Go is a modified Swiss Table which of course delivers improved performance. We've seen why Java is stuck where it is. The C++ std::unordered_map is known to have poor performance, C++ programmers have many alternatives [including of course Swiss Tables], such as a really nice modern offering from Boost.
I'm actually not sure about the guts of the C# hash tables at all, it's a complicated beast full of conditionally defined elements because it's reused by CLR internals as well as provided as a type for us users. It's not a conventional design of any sort, there seems to have been (which is common for Microsoft) some degree of Not Invented Here - just make it up as we go along. It's storing pre-calculated hashes with each key->value pair, it's tracking how many collisions it has, I dunno, I wouldn't do this, don't copy it without seeing hard numbers for why this is good.
There’s no reason to add extra properties and associated complexity to hash used in collections because of one exotic use case. To be able to execute hash flooding, the server must accumulate arbitrary user inputs in a hash map, which is problematic design anyway. Even if that would make sense, what kind of function could work as 32 bit gash? You mention SipHash as an example: it is poor example anyway, because this function requires a secret key - meaning Java would have to do the key management behind the scene (just for strings? For Number subclasses?) or impose key management on API users. What’s the point? The case is so rare that it’s easier for developers of vulnerable applications to use a wrapper with desired hash properties.
It is not at all an exotic use case, though. It is very common to add external strings as keys to collections. This is precisely why that attack was effective in the first place, and why so many languages these days do hash randomization. E.g. .NET does that.
The alternative is to never key a hash map from user input. Which is a choice to make, but that seems much harder to achieve (over every program?), vs have the implementation be safe in case someone does key off user input.
The original report from CCC demonstrated an attack on HTTP servers with a lot of request parameters that had hash collisions. That vulnerability was fixed by verifying and limiting user inputs (eg Tomcat 7.0.23 limited number of parameters to 10000 by default among other improvements). You cannot have unconstrained collection for user inputs anyway, otherwise memory based DoS attack becomes possible. So yes, any program that handles user inputs must take care of such scenarios. The best defense perimeter are the parsers of inputs, not just HTTP parameters and headers, but also JSON and XML deserializers, which must be hardened against various types of attacks anyway. Many scenarios where vulnerability may theoretically exist in application code are unpractical for execution of attack, e.g. when inputs are processed after user authentication or rate limit filter.
Or the hash table implementation should be resistant to collisions, falling back to another data structure in that case (as described below, using trees instead of lists in buckets with sufficiently many occupants.)
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.
That’s clear and that is not a reason to have it in general purpose collections or String::hashCode. If your app is vulnerable to this sort of attack, just use a wrapper for keys and specialized collection (you may want to limit the maximum size of it too).
This sounds a great deal like all the C++ devs who say "well just don't write code with buffer overflow bugs then".
The reason why this kind of thing should be the default is because it's unreasonable to expect this level of understanding from your average coder, yet most software is written by the later. That's why PL and framework design has been moving towards safety-by-default for quite some time now - because nothing else works, as proven by experience.
You are misunderstanding and exaggerating this particular risk and assuming there’s only one way to handle it. First of all, it concerns unchecked user inputs: it is not enough just to fix the hash code, the entire HashMap is not great for storing it regardless of hash algorithms. Hash may be ok, but HashMap has no size constraints, so there may exist a vulnerability related to DoS attack exhausting server memory. Developers must always validate inputs as early as possible. Even the dumb ones.
Second, this risk was reliably mitigated in Java as soon as it was discovered. Just because hash collisions may exist, it doesn’t mean they are exploitable. CVE for JDK was not fixed, because it has been taken care of elsewhere, in Tomcat etc, where meaningful validation could take place.
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.
No, it would break the semantics of equals and hash which dictate that two objects that are equal should also have the same hash code. So hash codes for objects must be deterministic. Which in turn is an important property for sets, hash tables, etc. It's unlikely to be ever changed because it would break an enormous amount of stuff.
For things that need to be secure, there are dedicated libraries, standard APIs, etc. that you probably should be using. For everything else, this is pretty much a non issue that just isn't worth ripping up this contract for. It's not much of an issue in practice and easily mitigated by just picking things that are intended for whatever it is you are trying to do.
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
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.
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.
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.
> 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.
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".
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.
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.
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.
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?
> 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.
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.
Isn't the entire point of an optimizer to convert "bad code" into "good code"?
Your proposed solution is to have the user manually implement a hash table, but if you have a good optimizer, users can focus on writing clear code without bugs or logic errors and let the machine turn that into efficient code.
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.
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.
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.
> 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.
> Under the hood, the content of a stable value is stored in a non-final field annotated with the JDK-internal @Stable annotation.
This is saying that the StableValue instance will have a non-final field annotated that way, not that there is no StableValue instance allocated. Note that the user-code-level field is final, so that's not the field being referred to here. In fact, this description is what makes me think that the StableValue object might exist even after JITting.
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.
> 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.
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 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.
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... -- 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
Probably depends on the use case, though I'm having trouble thinking of such a use case. If you were dynamically creating a ton of different sets that had different instances of the same strings, then, maybe? But then the overhead of calling `.intern` on all of them would presumably outweigh the overhead of calling `.hash` anyway. In fact, now that `.hash` is faster, that could ostensibly make `.intern` less valuable. I guess.
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'
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.
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.
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.
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.
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.
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.
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.
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.
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":
> 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.
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.
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.
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.
When I started my career in software development, SDE, and soon advanced to SRE, I hated Java. The extreme OOP paradigm made enterprise class situations impossible to understand. But after a few short years, I began to appreciate it as a real, battle hardened ecology. Now, I consider it much better than modern trends such as Rust and Python.
These kinds of niche optimizations are still significant. The OOP model allows them to be implemented with much less fanfare. This is in the context of billion-dollar platforms. With some basic performance testing and API replays, we're saving thousands of dollars a day. Nobody gets a pat on the back. Maybe some pizza on Friday.
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 love Java in the same way.
But that free-thinking definition of Java clashes with the mainstream beliefs in the Java ecosystem, and you'll get a lot opposition at workplaces.
So I gave up on Java, not because of the language, but because of the people, and the forced culture around it.
The over engineering creeps in anywhere there is collaboration. It’s not a Java thing, it’s a corporate thing. The new teammate who refactors the perfectly working sql pipeline; the teammate who makes story points a required field on your trouble ticket system, the teammate who just saw a conference talk on rust and wants to apply it etc. Most engineers are not zen masters seeking out simplicity; they are lost with poor grasp of desired business outcomes so they procrastinate by adding complexity and indirection and focusing on tech as if it were the destination not the journey.
> lost with a poor grasp of desired business outcomes so they procrastinate by adding complexity
I have come to see this as a mix of business people and developers not doing their jobs to protect thier paycheck. Business people, if they want to succeed, need to be converging on a strategy that makes money. Developers need to have a strategy for removing technical barriers to realizing that strategy. The lack of a business strategy often makes an overly general technical platform look attractive.
> focusing on the tech as if it were the destination
So common. Complexity should be considered the enemy, not an old friend.
True, but there's also the bored engineers who just can't force themselves to write enterprise code unless they make it fun for themselves. I'm absolutely convinced this is why Clojure even exists and is so widely used in fintech.
The extreme focus on multiple layers of patterns, where actually a simple function would have sufficed IS a Java ecosystem and culture thing. Just way too many people doing Java, who have never learned another language or ecosystem, let alone paradigm, thinking "I learned Java, Java can do everything, I don't need to learn anything else!" and now feeling they need to solve every problem by applying design patterns mindlessly.
So how do you explain.. every other piece of software written by 5+ people?
Well, not by talking about AbstractFactoryProxy, that much is for sure. Rather by talking about which parts of the system are modular and what kind of flexibility the system allows for, what capabilities it has. Nowhere in that picture does a low level implementation detail like an AbstractBlaBlubFooBar enter the the conversation.
There is more to computer programming than the OOP clutter.
Someone's tweet from about 15 years ago (paraphrased from memory):
"We rewrote 200k line Java codebase in only 50k lines. Guess what language we used?"
The follow-up tweet a day later:
"It was Java."
> No inheritence.
Yup. Prefer composition over inheritance.
Such a hard sell during the heyday of OOAD. UML, Fusion, RUP, blahblahblah.
Having previous experience with LISP, it just seemed obvious, barely worth mentioning. Definitely set me apart from my colleagues.
FWIW: Our local design pattern study group tackled Arthur J. Riel's Object-Oriented Design Heuristics [1996] https://archive.org/details/objectorientedde0000riel https://www.amazon.com/Object-Oriented-Design-Heuristics-Art... Which might be the earliest published pushback against all that overwrought enterprisey ThoughtWorks-style brainrot.
> No ... dependency injection
Yes and: Mocks (mocking?) is a code stench. Just flip the ownership relationship(s). As Riel, and surely many others, have laboriously explained, to a mostly uncaring world.
Prefer inheritance if the first thing you're gonna have to do under composition is to crank out a bunch of delegate methods from the parent object to the contained child, to make the parent substitutable for the child, and the child won't be replaced at run time.
Probably. I personally haven't done anything like that. Though I'm not sure I follow.
I've mostly done ASTs and (scene) graphs. I prefer dumb objects, stuffing most behavior and logic in an Interpreter (design pattern) implementation. Being a very simple bear, my working memory can't keep track of all the smarts scattered all about.
My current example is processing SQL statements; think expression evaluator (subset) for a very specific use case. I tend to use so called "External" Iterators for walking trees, to keeping all the logic in one place. Versus Visitor, Listeners, or even Active Objects. Which is feasible for this use case, because its bounded and unlikely to change (eg extension points).
YMMV of course. Now I'm just babbling, apologies, and probably went too far off topic.
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.
I really don't think this stance aged well, even if it was closer to true way back when. IMO the spartan language is now Go, and Java has ended up the boring open source workhorse. The jvm is very performant compared to many stacks these days (python Ruby node) while still having a very compelling concurrent programming story, and has a lot of nice language feature things ever since 8 and onwards. Lambdas and streams are the big 8's, but I think virtual threads growing up and even new things like scoped variables are really compelling reasons to build a new thing in java right now.
You need just the right amount of expressivity in a language, so that it is hard to abuse, but still allows writing easy to use libraries.
Java has went over this evolution, implemented generics, lambdas, etc and I believe it strikes a very good balance in not being overly complex (just look at the spec - it's still a very small language, compared to its age, unlike C++ or C#).
Go tried to re-invent this evolution, without having learnt Java's lessons. They will add more and more features until their "simple" will stop applying (though I personally believe that their simple was always just simplistic), simply because you need some expressivity for better libraries, which will later on actually simplify user code.
Also relevant: https://www.tedinski.com/2018/01/30/the-one-ring-problem-abs...
The problem with the JVM, compared to Go, is the GC; it requires a lot of reserved memory. Go programs use far less. And the SDK is bulky, which can be a problem for container images - although arguably it should be considered irrelevant, as you only download base images once, if done correctly.
You're not supposed to use the runtime directly these days. jlink allows you to strip unnecessary things (like documentation for the runtime itself), extract only those parts of the runtime you need (though your project must use modules to support that), and then aggressively compress it all getting a pretty small package that runs on an empty OS with no dependencies other than libc. It's still a bunch of files, so for good user experience you would have to ship it as a container (or something like .exe or appimage), but it's really close to Go in terms of size.
https://www.baeldung.com/jlink
It's a configurable property, and Java has a bunch of GCs to begin with.
Also, not using as much memory in these types of GCs is a direct hit to performance. And this actually shows splendidly on GC-heavy applications/benchmarks.
We were paying a million a month for a custom high performance GC for a little bit but we were able to get off that with a lot of development effort and get our five 9's latency under control.
I tried and gave up on getting Keycloak to use less memory. 500-1500 MB for a server with less than 10 concurrent users is ridiculous. And that's even using an external database.
What did you try? As a last attempt you can just check visualvm to see the actual memory use, add a few percent headroom and set that as heap size.
Much less of a problem in .NET (its GC tuning sits somewhere in between the two, especially when SRV GC + DATAS is in use, like in container scenarios, where Go is funnily unaware of limits set by cgroups and needs an external package to fix it). It does pre-allocate more memory than Go per se but in return yields much, much higher allocation throughput out of box. Java allows for even higher allocation throughput, having multiple more sophisticated GC implementations but as you said is not very good at reducing sustained RSS used by an application.
> Java has ended up the boring open source workhorse.
This statement surprised me. I can't even remember last time I ran any opensource Java.
Off the top of my head? Bazel is the Java program I use the most. Hadoop/hive and similar stuff also heavily Java but I'm not sure how much that's in use anymore
I'm not saying there's no Java in open source. And I'm aware of the projects you mention. I don't run them though. And they definitely don't qualify as "the boring open source workhorse".
There are a couple of Java projects, and even one or two kind of successful ones. But Java in open source is very rare, not the boring workhorse.
If I worked on a project that used Bazel, then sure, I'd use Bazel every day.
But which is "the boring workhorse" of open source, if I gave you the option of Java, Make, Linux, gcc, llvm, .deb, would Java really be "the" one?
Sure, maybe you could exclude most of those as not being "boring", like llvm. But "make" wins by any measure. And of course, it's almost by definition hard to think about the boring workhorse, because the nature of it is that you don't think about it.
Checking now, the only reason I can find java even being installed on my dev machines is for Arduino IDE and my Android development environment. Pretty niche stuff, in the open source space.
Most Java applications nowadays are based 100% on open source stack with hundreds of libraries and frameworks and Java dominates enterprise space, so it is a huge open source workhorse, just more obscure than Linux, gcc etc.
Ok, we clearly have an extremely different definition of the word "the" workhorse of open source.
It doesn't mean "more than zero projects are Java based". Nor does it mean "most (opensource?) Java applications are based on open source". That latter is borderline circular, only Oracle legal shenanigans makes it not circular.
> and Java dominates enterprise space
I said nothing about enterprise. Clearly Java is HUGE in enterprise.
> so it is a huge open source workhorse
That sentence took a strange turn. Enterprise, and then back to open source?
> just more obscure than Linux, gcc etc.
Obscure? I'd expect Java to be about as strong a brand as Linux. Among developers in general I'd expect gcc to be orders of magnitude more obscure. There's no programmer out there who has not heard of Java, but many have never heard of gcc.
> Ok, we clearly have an extremely different definition of the word "the" workhorse of open source.
You said what it is not, but forgot to share your own definition.
>That sentence took a strange turn. Enterprise, and then back to open source?
What makes you so surprised? One does not exclude another, enterprise users are users too. Most of things in Java world aren’t client-side, so many users won’t observe them directly, but open source Java technology is doing a lot of work for them, constituting significant share of the code base.
Ghidra also
Half of the internet is literally running that.. like unless you deliberately avoid Java stacks, you will come across it. It's one of the top 3 ecosystems in size, with JS and python being the other 2 contenders.
Internet? Yes. But that was not the topic at hand.
The lack of operator overloading is a bit annoying but in practice seldom a real problem. An operator is just a funny looking method. So what.
There are worse fundamental problems in Java. For example the lack of a proper numeric tower. Or the need to rely on annotations to indicate something as basic as nullabilty.
It’s a massive annoyance when working with any sort of numeric code. Or custom collections. Or whatever else the standard library enjoys that nobody else gets to use.
> easy to take another class and copy it with small modifications but not mess it up for anyone else (inheritance)
That sounds like a recipe for disaster though, as it generally makes code much harder to read.
Agree, inheritance tends to be overused when programmers try to get too clever. The flatter the class hierarchy the better
I remember the times on one of professional forums, where there was lots of questions about architecture in C# sections and almost none in Java section. Abundance of tools creates abundance of possibilities to get confused about what’s right. In Java many design decisions converged to some dominant design long time ago, so you no longer think about it and focus on business. It’s sometimes as bad as getter verbosity (thankfully record style is getting traction), but in most cases it’s just fine.
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.
I'm not sure if the argument that OOP is pleasant so long as you avoid any OOP is a very sturdy one.
OOP is the combination of encapsulation, abstraction, inheritance, and polymorphism. Ignoring inheritance does not mean avoiding OOP altogether.
Also note that the OP said “avoid extending classes”, but didn’t say “avoid implementing interfaces”, so they don’t disallow inheritance in a wide sense of the word.
I think “avoid extending classes” is there because it is as good as impossible to design classes that can be extended easily in ways you do not foresee, and if you do foresee how your classes could be extended, it often is easier for your users if you made your classes more flexible, to start with.
You can get Encapsulation, abstraction, and polymorphism any number of other ways. Inheritance is the only defining property of OOP.
If you removed all the stuff related to inheritance and trying to fix the leaky abstraction that is objects, the language would be a fraction of the size (compare with Go or StandardML for how small a language without inheritance can be).
And as for inheritance: Composition over inheritance. So .... just don't do OOP, I guess?
I'd say that the 'poor man's closures' aspect of OOP - that is, being able to package some context along with behaviour is the most useful part for day to day code. Only occasionally is inheritance of anything other than an interface valuable.
Whether or not this is an endorsement of OOP or a criticism is open to interpretation.
OOP is great for libraries but leads to overly complex codes for applications.
For a long time, Java was like, every classes is a library, i do not think it's a failure of OOP, it's a failure of Java.
But I'm optimistic, I choose to see recent additions like records and pattern matching has a step in the right direction.
> 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)?
My thoughts exactly. Give me more classes with shallower inheritance hierarchies. Here is where I think go’s approach makes sense.
No. Things only get more complicated with more technical debt. The best you can do is manage it with yet another abstraction.
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.
It's hot really your decision in a corporate environment.
> no work required other than updating the JRE we use
Have you tried updating production usage of a JRE before??
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
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.
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.
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.
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.)
Absolutely love it. Thanks a lot. A fancy hit me yesterday and I've been looking through JDK's String commit history to see little tidbits that I could grab.
Shipilev's website looks like a fascinating resource. I appreciate the pointer!
This is a good video that goes over a ton of the optimizations, especially around concatenation: https://youtu.be/z3yu1kjtcok?si=mOdZ5sh5rp8LNyap
I appreciate it! I will take a look this weekend,
> 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.
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.
I did laugh, so there is that.
The flip side is that for years Java developers have been dealing with suboptimal strings with nothing to do about it.
[dead]
This post makes mention of a new JEP I hadn't heard of before: "Stable Values"
https://openjdk.org/jeps/502
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:
Records were defined as: And Value Objects/Classes as: Both Records and Value Objects are immutable, and hence can only have their contents set upon creation or static initalization.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.
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.
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.
> 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.
Right. Oracle should reconsider the naming here: stable -> lazy
But this is also achievable with static init methods on records and value classes, right?
How would you do the same thing with the late initialization of, say, a HashMap where you don't control the constructor?
Hmm, I see what you're saying -- yeah, this seems to be semantically identical to Kotlin's `lateinit` then
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.
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.
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)
> 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?
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.
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.
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
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.
In Java, constants are declared as static final.
If you want a lazy initialized constant, you want a stable value If you want the fields of a constant to be constant too, Complex has to be declared has a record.- 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.
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.
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).
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.
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`.
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?
The hashing algorithm is specified in the docs:
Per Hyrum's law, there's no changing it now.https://docs.oracle.com/javase/8/docs/api/java/lang/String.h...
Java hashCode contract is to optimize calculation of hash for performance not for collision search resistance. Its sole purpose is to use it in collections. It must not be used in situations where you need cryptographic properties.
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.
java hashcodes are just 4 bytes, there will always be collisions
The point is that since the hash is known and predictable, an attacker who can choose what keys get added to the map can choose them so every key collides, resulting in a DoS.
I assume Java has to add some other layer to avoid this, rather than using a collision resistant hash scheme.
> added to the map can choose them so every key collides, resulting in a DoS
the application creator needed to have anticipated this threat model, and they can prepare for it (for example, salt the keys).
But to put onto every user a hash that is collision resistent, but costs performance, is unjustified because not every user needs it.
There are specialized collections in external libraries for these kinds of situations to be used when you need them (and are ready to pay for them in terms of performance).
I don't imagine it was ivan_gammel's intention, but his mention of the original CCC/tomcat issue I think makes the point quite clear: have you ever had a hashmap of HTTP header to values? I hope it used one of those external libraries, because otherwise that's now a vector for DoS'ing any app that has one.
User influenced/controlled input happens way more than we expect, I think the more sensible approach would be for the map to be safe by default, and to reach for a high performance external map for those times when that particular data structure is the bottleneck.
>I think makes the point quite clear: have you ever had a hashmap of HTTP header to values?
Number of headers is limited by default to a relatively small value (10k), which in the worst case of hash collisions results in relatively fast lookup time due to tree-like implementation of HashMap.
> due to tree-like implementation of HashMap.
Exactly, this data structure has to provide counter-measures to cope with the fallout from this other poor choice.
The fast data structures for this work don't need a tree here, they're open addressed instead, but this would mean they can't cope if your attacker can arbitrarily collide input, so, too bad.
This data structure has tree-like fallback for hash collisions in general, which do happen regardless of hash algorithm by definition of what is hash. It is not a coping mechanism for a poor choice, it’s elegant design allowing better performance for Comparable keys. By coincidence it mitigates the DoS attack too.
All the closed addressing strategies mean more allocator burden. In this case, each of these trees needs to grow separately. But with open addressing we can avoid that.
Suppose we have 10'000 key->value pairs to store. A Swiss Table (a popular open addressed hash table design) will need space for 16384 contiguous pairs plus metadata†. So it'll do that allocation once, but with the closed addressing and trees you're paying to grow trees during insertion, you can't know which trees will grow and which are unused.
You're correct that the Swiss Table will see collisions, but an attacker can't choose them, so they're rare. Each collision costs us a search step, but because the Java design incurs a pointer chase (to find the tree) for every lookup that's actually the same price [one memory fetch] as a single collision for the Swiss Table, yet most of the time the Swiss Table sees less than 1.0 collisions per lookup.
† It's ensuring no more than 87.5% of the storage is used and then rounding up to a power of two because that means less work for each look-up step. 11429 would be enough space, but 16384 is the next largest power of two.
> But with open addressing we can avoid that.
In risk management there exist several different approaches: accept, mitigate, transfer, avoid. What makes you think that this design must avoid certain risks? The developers of standard libraries like Java usually base their decisions on industry feedback, IIRC, Oracle team did have a lot of telemetry data and they are good engineers. Do you have any insights proving that their approach is wrong?
> IIRC, Oracle team did have a lot of telemetry data and they are good engineers. Do you have any insights proving that their approach is wrong?
Time's arrow
Java is a Sun (Microsystems) language, Oracle just bought the entire company much later. So one problem here is that you're imagining this like it's a decision somebody made this century but it isn't, it's a decision from the early 1990s.
Computer Science is a young discipline. In the early 1990s the Open Addressed hash tables do exist but it's very usual to write the simple chained hash table with Closed Addressing and as I understand it that's exactly what is provided in Java 1.0. This data structure is today known to be a bad idea, and I've criticised the choice in say C++ to standardize the exact same data structure (as std::unordered_map) in 2011. But that's twenty years later.
At some point (I believe this century?) Java engineers went back and improved their hash table to use trees not chains, but they were constrained by the baked in hash, so they could not have picked radically modern data structures which require a different hash strategy without significant disruption.
When I got a CS degree the Introspective sort was so new I'd have to have read bleeding edge research papers to know about it. Today it's very silly if you claim you provide a standard library sort and it's not at least as good as Introsort.
The Swiss Table is from the 2010s, it's new enough that there's a Youtube video of them introducing this data structure, not because they did that specifically on purpose but because they're giving a talk and obviously all talks are filmed and uploaded to Youtube these days. Hopskotch hashing - another popular Open Addressing strategy - is from 2008.
So, the question isn't "Is this the best idea today?" but only "Given what they knew 30+ years ago, was this reasonable back then?" and yeah, of course it was reasonable back then but that doesn't magically mean it's the best choice now.
Edited: Added paragraph about the later choice to use trees.
The standard library design choices are influenced not only by algorithm performance, but also by the use cases, existing contracts etc. You did not answer my question. Why do you think choosing alternative algorithm and breaking existing hash contract would be better?
> You did not answer my question. Why do you think choosing alternative algorithm and breaking existing hash contract would be better?
But I don't think Java should go break all this stuff. I'm just explaining why - in fact - we might want some cryptographic properties for hash algorithms. It can be true both that Java made reasonable tradeoffs at the time (in the 1990s) and that you shouldn't copy those choices today.
There's a long list of things Java picked that in hindsight weren't a good idea and in many cases it would have been really hard to guess that when Java was invented - however today you should not choose what Java did. Biggest example: 16-bit char. Java was invented when UCS-2 might happen, and in that light a 16-bit char makes sense. A few years later it's obvious UCS-2 is not possible and so you're choosing UTF-8 or UTF-16 and that's easy, pick UTF-8. People who'd already bought into the 16-bit char, such as Microsoft and Sun's Java team, were stuck with UTF-16 as a booby prize.
I think I lost you here actually. Hash by definition is just a mapping of arbitrary sets to large integers. Cryptographic hash adds computational complexity requirement so that it is prohibitively hard to find collisions (i.e. slow by design - bad choice for collections, which need fast hashing). Unstable hash is simply the one that is not guaranteed to persist between two different executions of a program (but it obviously has to be the same for equal objects in the same execution). Neither of collision resolution techniques requires cryptographic or even unstable hash. Collections only need hash to be sufficiently random on typical datasets for optimal performance. I would even question if unstable hash can mitigate the hash flooding attacks at all or it is possible to determine the hashing parameters of a black box somehow. Limit on number of parameters and efficiency at high load factors/high collisions is more important for security.
Many programming languages do not use open addressing and prefer chaining (Java, C#, Golang, std::unordered_map in C++) for simplicity and flexibility. There are certain trade offs to be considered, it is not a simple choice of absolutely the best known algorithms. I don't think Java made the wrong choice here. Notably, there was always a possibility to introduce a specific collection with some modern algorithm as an alternative to HashMap. It did not happen not least because it was not considered that important. I'm sure that in cases where open addressing offers substantial benefits, developers make conscious choice and use the appropriate data structures.
Regarding strings, since Java 9 (released long time ago) they can be stored in byte arrays if they contain only Latin-1 characters and core team is open for further enhancements.
See https://openjdk.org/jeps/254
No, the cryptographic hash functions are not slow by design. This is a nasty misunderstanding which leads to stuff like MD5(password) in PHP [not the PHK MD5 crypt() algorithm used in Unix systems in the 1990s, this was literally MD5(password) and it's a bad idea, do not do]
The cryptographic hash functions such as the SHA-2 family resist construction of a second pre-image, given N and H(N) there's no way for me to make M such that H(M) == H(N) but M != N that'll be faster than brute force trying all possible values for M. So far everything we have which achieves this is markedly slower than say FNV-1 which would once have been the most likely hashing algorithm for a hash table.
The one way password hashes, some of which are based on the cryptographic hashes, are slow by design. You should not use passwords, but on HN this seems like a lost cause so, assuming you insist on using passwords these algorithms are specifically what you need. Fighting about which one to use ("oh no, PBKDF2 isn't memory hard, blah blah blah") is also a bottomless hole of HN nonsnse, so, fine, pick whichever of them you're certain is the only correct one.
But we do ideally want some cryptographic properties for a hash to be used in a hash table and your instinct that just using a random factor and hoping won't work was correct. You need a correctly designed function, which is what SipHash is. What you want is some keyed function with a key K such that if I know N and H(K,N) but not K, I can't guess an M such that H(K,M) = H(K,N) but M != N except by brute force.
> Many programming languages do not use open addressing and prefer chaining (Java, C#, Golang, std::unordered_map in C++) for simplicity
This was true in Golang but today the map in Go is a modified Swiss Table which of course delivers improved performance. We've seen why Java is stuck where it is. The C++ std::unordered_map is known to have poor performance, C++ programmers have many alternatives [including of course Swiss Tables], such as a really nice modern offering from Boost.
I'm actually not sure about the guts of the C# hash tables at all, it's a complicated beast full of conditionally defined elements because it's reused by CLR internals as well as provided as a type for us users. It's not a conventional design of any sort, there seems to have been (which is common for Microsoft) some degree of Not Invented Here - just make it up as we go along. It's storing pre-calculated hashes with each key->value pair, it's tracking how many collisions it has, I dunno, I wouldn't do this, don't copy it without seeing hard numbers for why this is good.
There’s no reason to add extra properties and associated complexity to hash used in collections because of one exotic use case. To be able to execute hash flooding, the server must accumulate arbitrary user inputs in a hash map, which is problematic design anyway. Even if that would make sense, what kind of function could work as 32 bit gash? You mention SipHash as an example: it is poor example anyway, because this function requires a secret key - meaning Java would have to do the key management behind the scene (just for strings? For Number subclasses?) or impose key management on API users. What’s the point? The case is so rare that it’s easier for developers of vulnerable applications to use a wrapper with desired hash properties.
It is not at all an exotic use case, though. It is very common to add external strings as keys to collections. This is precisely why that attack was effective in the first place, and why so many languages these days do hash randomization. E.g. .NET does that.
Unconstrained user input in a hash map big enough to produce observable effect is not an exotic use case compared to everything else?
The alternative is to never key a hash map from user input. Which is a choice to make, but that seems much harder to achieve (over every program?), vs have the implementation be safe in case someone does key off user input.
The original report from CCC demonstrated an attack on HTTP servers with a lot of request parameters that had hash collisions. That vulnerability was fixed by verifying and limiting user inputs (eg Tomcat 7.0.23 limited number of parameters to 10000 by default among other improvements). You cannot have unconstrained collection for user inputs anyway, otherwise memory based DoS attack becomes possible. So yes, any program that handles user inputs must take care of such scenarios. The best defense perimeter are the parsers of inputs, not just HTTP parameters and headers, but also JSON and XML deserializers, which must be hardened against various types of attacks anyway. Many scenarios where vulnerability may theoretically exist in application code are unpractical for execution of attack, e.g. when inputs are processed after user authentication or rate limit filter.
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.
Or the hash table implementation should be resistant to collisions, falling back to another data structure in that case (as described below, using trees instead of lists in buckets with sufficiently many occupants.)
There exists CVE-2012-5373 for Java and it is not fixed because it is not a risk worth taking care of.
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.
That’s clear and that is not a reason to have it in general purpose collections or String::hashCode. If your app is vulnerable to this sort of attack, just use a wrapper for keys and specialized collection (you may want to limit the maximum size of it too).
This sounds a great deal like all the C++ devs who say "well just don't write code with buffer overflow bugs then".
The reason why this kind of thing should be the default is because it's unreasonable to expect this level of understanding from your average coder, yet most software is written by the later. That's why PL and framework design has been moving towards safety-by-default for quite some time now - because nothing else works, as proven by experience.
You are misunderstanding and exaggerating this particular risk and assuming there’s only one way to handle it. First of all, it concerns unchecked user inputs: it is not enough just to fix the hash code, the entire HashMap is not great for storing it regardless of hash algorithms. Hash may be ok, but HashMap has no size constraints, so there may exist a vulnerability related to DoS attack exhausting server memory. Developers must always validate inputs as early as possible. Even the dumb ones.
Second, this risk was reliably mitigated in Java as soon as it was discovered. Just because hash collisions may exist, it doesn’t mean they are exploitable. CVE for JDK was not fixed, because it has been taken care of elsewhere, in Tomcat etc, where meaningful validation could take place.
Context matters.
And yet literally everybody else started doing hash randomization. Why?
The vulnerability was reported and addressed in a reasonable way. Why other platforms should matter here? Do you believe they were smarter?
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)).
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.
No, it would break the semantics of equals and hash which dictate that two objects that are equal should also have the same hash code. So hash codes for objects must be deterministic. Which in turn is an important property for sets, hash tables, etc. It's unlikely to be ever changed because it would break an enormous amount of stuff.
For things that need to be secure, there are dedicated libraries, standard APIs, etc. that you probably should be using. For everything else, this is pretty much a non issue that just isn't worth ripping up this contract for. It's not much of an issue in practice and easily mitigated by just picking things that are intended for whatever it is you are trying to do.
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.__...
Nothing stops the jvm from caching hashes even if the hashes are unique per process invocation.
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.
[dead]
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.
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.
> 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.
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".
why is a website about programming not writing code blocks in ASCII? I'm referring to quotes and other undesirable symbols
Java supports non-ASCII source code since forever. A lot of languages do.
But it doesn't support using fancy unicode quotes as string delimiters.
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.
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.
Can you share a link to your "strings library"? I am curious about what it can do that a Java String cannot.
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
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?
> 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.
> 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.
Isn't the entire point of an optimizer to convert "bad code" into "good code"?
Your proposed solution is to have the user manually implement a hash table, but if you have a good optimizer, users can focus on writing clear code without bugs or logic errors and let the machine turn that into efficient code.
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.
>but are we really optimizing for bad code?
Yes
So strings don’t get hash code at compile time?
At first I thought the article was describing something similar to Ruby’s symbols
> 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.
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.
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.
After JIT compilation, yes (presumably), but for interpreted byte code I assume that a regular object is still allocated.
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.
> Under the hood, the content of a stable value is stored in a non-final field annotated with the JDK-internal @Stable annotation.
This is saying that the StableValue instance will have a non-final field annotated that way, not that there is no StableValue instance allocated. Note that the user-code-level field is final, so that's not the field being referred to here. In fact, this description is what makes me think that the StableValue object might exist even after JITting.
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.
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?
> 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.
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 would it directly replace your key with its value?
In the same way that if you wrote this C code:
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...
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... -- 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
How does the jvm know the map is immutable?
But interned strings can also reuse their hashcode forever.
Map.of() promises to return an immutable map. new HashMap<>() does not.
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/...
> Does this make string.intern() more valuable?
Probably depends on the use case, though I'm having trouble thinking of such a use case. If you were dynamically creating a ton of different sets that had different instances of the same strings, then, maybe? But then the overhead of calling `.intern` on all of them would presumably outweigh the overhead of calling `.hash` anyway. In fact, now that `.hash` is faster, that could ostensibly make `.intern` less valuable. I guess.
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'
Will Kotlin and Scala benefit?
They should. It's a JVM feature on core JDK classes.
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.
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.
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.
Ha! My apologies, I misread that as "they shouldn't." Not sure why.
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.
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.
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.
Is @Stable a generalization of the final keyword or is there more to it that I'm missing?
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.
Is this a correct summary: we memoized the hashCode() function?
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.
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.
I experimented with hash codes in strings in TXR Lisp, but took it out after several days:
> 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":
What's the code look like? 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.
> 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.
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.
Um, malloc() is not a system call?
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.
Off-the-cuff thought:
Could you solve the empty string hashes to zero problem by just adding one when computing hash codes?
But then strings with the hash code HASH_MAX would wrap to 0 instead.
You could, but that would break backwards compatibility.