6

I made a patch to a programming language run-time to cache the results of hashing a string in the string object, so that it is just retrieved the next time it is required.

However, I'm not convinced there is any worthwhile benefit, and the feature comes at an opportunity cost. Heap objects have only four pointer-sized words of storage available, so dedicating a word for a hash code is a big deal. The patch includes some changes to make this word available in the first place; that part of the patch could be retained while the newly available storage word is put to a more beneficial use than storing a hash code.

I know Java runtimes store hash codes in strings, but I've never worked in Java. Searching around, there are plenty of explanations about how it works, and the obvious benefit of not having to calculate a hash twice on the same object, but a rationale for doing it is elusive: what is it that Java programs do with strings that makes it important to dedicate a word to caching the hash value?

It seems to me that if the same string object (not the same string) is asked for its hash value a large number of times, there is something wrong with the program's approach.

Improve this question
7
  • 2
    Can you edit to clarify that you are not looking for feedback on how stupid is to make changes that you don't think are useful?
    – Alexei Levenkov
    Commented Oct 7, 2022 at 20:01
  • 1
    This is a really good question, but some people here (which voted to close this as "opinionated") are too dumb to see that such a design decision must have been made deliberately. For Java strings, I am sure there was nothing just done by chance in their internal implementation.
    – Doc Brown
    Commented Oct 7, 2022 at 20:02
  • 1
    @AlexeiLevenkov I'm a language maintainer. Obviously, I coded this thing due to the suspicion it might be useful and has precedent in other people's projects. It's code complete and all; tests pass, and it's in an unpublished commit. But now, I don't see how to demonstrate how it is worthwhile; why have others done this. Expert programmers using languages which have this should know this sort of thing.
    – Kaz
    Commented Oct 7, 2022 at 23:30
  • Speaking of Java specifically: is there some internal reason for this feature? Maybe the JVM uses strings for some purposes where it helps? If I don't have a similar scenario, then that would be a point against doing this.
    – Kaz
    Commented Oct 8, 2022 at 18:47
  • 1
    @Kaz: @casablanca's answer seems to give a likely answer, i.e. that the JVM makes heavier use of hashes to support features like that compress/reduce strings.
    – Nat
    Commented Oct 8, 2022 at 23:04

3 Answers 3

Reset to default
7

I'm not convinced there is any worthwhile benefit, and the feature comes at an opportunity cost.

It would be wise to run benchmarks against real-world applications written in your language before making a change that will likely increase the memory footprint of those applications. The benefit of such optimizations is highly dependent on many factors including language, compiler/VM, target hardware as well as the kind of workload that is being run (this last piece is why the JVM, for example, has a client and a server mode that utilize different optimizations).

What is it that Java programs do with strings that makes it important to dedicate a word to caching the hash value?

This is not a definitive answer, but besides the "obvious" use of hash codes in application code (hash maps etc.), the JVM internally makes use of string interning to dedupe identical string literals across all loaded classes. Recent JVMs also support string deduplication within the application heap, and I imagine having a cached hash value makes it much quicker for the GC to identify duplicate strings.

The proposal for string deduplication specifically talks about the motivation for this change:

Many large-scale Java applications are currently bottlenecked on memory. Measurements have shown that roughly 25% of the Java heap live data set in these types of applications is consumed by String objects. Further, roughly half of those String objects are duplicates.

It seems to me that if the same string object (not the same string) is asked for its hash value a large number of times, there is something wrong with the program's approach.

As a language designer/maintainer, you don't really get to choose how other people use your language. There's a lot of "ugly" code in real-world software that we use every single day. If caching the hash code results in a noticeable boost, that may be the "right" decision from a language maintainer's perspective because it's much cheaper than getting everyone to rewrite their code.

It's important to note that just because this made sense for Java doesn't mean that it necessarily makes sense for your language, and the only way to know for sure is to run your own benchmarks.

Improve this answer
1
  • Thanks for the great answer! The language I'm working on is Lisp, which has interned symbols, and idiomatic applications are expected to exploit them. That's why I can't think of a good use case. A program that keeps looking up the same string in a hash table wants to be using a symbol. A symbol's hash is just a quick bit manipulation of its address in memory; you'd never need to store it.
    – Kaz
    Commented Oct 9, 2022 at 3:16
0

This isn’t about hashing, it is about caching. If an object has a property that is expensive to calculate, and you can completely detect all the situations where that property would change, and it is needed often, then you can think about caching the value.

For immutable string objects, you would know when the object and therefore the hash code changes (never), and calculating the hash can be expensive. If your strings use unicode correctly then checking that two strings with different bytes are equal and therefore need the same hash code is expensive.

For mutable string objects you have the added cost that you need to invalidate the cached hash code whenever the value changes.

Improve this answer
1
  • 1
    When are these situations, in relation to the property being the hash code on strings? In a tight bytecode loop calling the hash function on a string object, I found it's not even twice as expensive to calculate the hash. If the loop (hundreds of millions of iters) does nothing it takes 2s. If it there is a function call which retrieves the hash, 3.5s, so the call costs around 1.5s of that time. If the hash calculated each time, the loop takes 4.7s: the real hash costs 2.7s. The string used was "supercalifragilistic", so more than just a few chars, but not huge.
    – Kaz
    Commented Oct 7, 2022 at 23:34
-3

what is it that Java programs do with strings that makes it important to dedicate a word to caching the hash value?

Store them in HashMaps.

Improve this answer
3
  • Sorry, that is obvious and not what my question is about; I now regret having edited the remarks around hash tables from my question.
    – Kaz
    Commented Oct 7, 2022 at 19:17
  • The context is that we take it for granted that the biggest, perhaps only consumer of hash values is the hash table implementation. Why is it worth doing? There is no benefit if the keys being looked up are strings arriving from the environment, being constructed into new string objects.
    – Kaz
    Commented Oct 7, 2022 at 19:19
  • 1
    I've not seen any improvement in the test suite run time, or recompilation of the language's compiler and library. A contrived benchmark which hashes the same string in a loop shows a big difference, of course.
    – Kaz
    Commented Oct 7, 2022 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.