3 ms·

The article advises against applying this change everywhere, but I think this actually sounds like a good argument that the Java standard library should adjust

The article advises against applying this change everywhere, but I think this actually sounds like a good argument that the Java standard library should adjust the default constructor for Set. I am going to guess that Sets usually contain a small number of members. Paying memory allocation costs [amortized constant time] for large sets sounds a lot better than requiring memory to fit the possible range of values for small ones.

nradov 7y ago
What you're really asking for is to change the backing HashMap.DEFAULT_INITIAL_CAPACITY field. https://hg.openjdk.java.net/jdk/jdk14/file/f77e9e27b68d/src/java.base/share/classes/java/util/HashMap.java#l237 https://hg.openjdk.java.net/jdk/jdk14/file/f77e9e27b68d/src/... There's no hard data to show that a smaller value would give better performance for typical Java workloads. Resizing operations are quite expensive.
- stygiansonic 7y ago
  What's weird about the original article is that my understanding of HashMap (which as you pointed out, is the backing data structure of for HashSet) does not initialize the underlying hash table until first use - so if a bunch of new HashSets were created but never added to, the memory impact should be minimal irregardless of what the initial capacity was set to. (So there should not have been much of a difference between "new HashSet()" and "new HashSet(0)" if no items were ever added) See this comment, and also the implementation of putVal()/resize(): https://hg.openjdk.java.net/jdk/jdk14/file/f77e9e27b68d/src/java.base/share/classes/java/util/HashMap.java#l387 https://hg.openjdk.java.net/jdk/jdk14/file/f77e9e27b68d/src/... Perhaps things were different back in Java 1.3. EDIT: Apologies, I completely missed this in the article, where it's explicitly called out. This particular trick also no longer works. As I found out while writing this article, modern JDKs do not allocate any space in a HashSet until something is added. If I had kept applying this trick pre-emptively I would have been wasting my time.
- asveikau 7y ago
  It sounds like you are squeezing my suggestion into a very specific solution. If there was a fix not tweaking current knobs but that made low numbers of elements cheap, while subsequently minimizing resizes when some reasonable heuristic for "mid-size to large" hash tables kicks in, you would oppose it universally? Resizing a small number of elements is not going to be bad.
Ididntdothis 7y ago
The standard library shouldn’t optimize for the case that somebody is using a lot of empty sets. This more indicates to me that there is a design problem.
- asveikau 7y ago
  I didn't have Java figured for this much, but I know there are a lot of languages where it's idiomatic to have lots of small hash tables. It is reasonable for a standard library to not make that case suffer too much.
  - Ididntdothis 7y ago
    Small is fine but empty would be a bad default in my view.
    - asveikau 7y ago
      But isn't resizing from 0 to n pretty much the same as allocating a fresh one of size n? (Not talking about the typical "resizing for n inserts one-at-a-time" approach, just going from zero to something.) I mean, you have conditionals in the insert instead of unconditional allocation at the start, so maybe a little worse for things like branch predictors, but ...
      - Ididntdothis 7y ago
        You have a point there. In sum you would probably get the same performance. The only difference would be that the first insert would be slower vs the constructor as it is now.

nradov 7y ago

What you're really asking for is to change the backing HashMap.DEFAULT_INITIAL_CAPACITY field. https://hg.openjdk.java.net/jdk/jdk14/file/f77e9e27b68d/src/java.base/share/classes/java/util/HashMap.java#l237 https://hg.openjdk.java.net/jdk/jdk14/file/f77e9e27b68d/src/... There's no hard data to show that a smaller value would give better performance for typical Java workloads. Resizing operations are quite expensive.

stygiansonic 7y ago
What's weird about the original article is that my understanding of HashMap (which as you pointed out, is the backing data structure of for HashSet) does not initialize the underlying hash table until first use - so if a bunch of new HashSets were created but never added to, the memory impact should be minimal irregardless of what the initial capacity was set to. (So there should not have been much of a difference between "new HashSet()" and "new HashSet(0)" if no items were ever added) See this comment, and also the implementation of putVal()/resize(): https://hg.openjdk.java.net/jdk/jdk14/file/f77e9e27b68d/src/java.base/share/classes/java/util/HashMap.java#l387 https://hg.openjdk.java.net/jdk/jdk14/file/f77e9e27b68d/src/... Perhaps things were different back in Java 1.3. EDIT: Apologies, I completely missed this in the article, where it's explicitly called out. This particular trick also no longer works. As I found out while writing this article, modern JDKs do not allocate any space in a HashSet until something is added. If I had kept applying this trick pre-emptively I would have been wasting my time.
asveikau 7y ago
It sounds like you are squeezing my suggestion into a very specific solution. If there was a fix not tweaking current knobs but that made low numbers of elements cheap, while subsequently minimizing resizes when some reasonable heuristic for "mid-size to large" hash tables kicks in, you would oppose it universally? Resizing a small number of elements is not going to be bad.

Ididntdothis 7y ago

The standard library shouldn’t optimize for the case that somebody is using a lot of empty sets. This more indicates to me that there is a design problem.

asveikau 7y ago
I didn't have Java figured for this much, but I know there are a lot of languages where it's idiomatic to have lots of small hash tables. It is reasonable for a standard library to not make that case suffer too much.
- Ididntdothis 7y ago
  Small is fine but empty would be a bad default in my view.
  - asveikau 7y ago
    But isn't resizing from 0 to n pretty much the same as allocating a fresh one of size n? (Not talking about the typical "resizing for n inserts one-at-a-time" approach, just going from zero to something.) I mean, you have conditionals in the insert instead of unconditional allocation at the start, so maybe a little worse for things like branch predictors, but ...
    - Ididntdothis 7y ago
      You have a point there. In sum you would probably get the same performance. The only difference would be that the first insert would be slower vs the constructor as it is now.