Optimization: Specialized memory-efficient layout for tiny ImmutableSet (n=2 to 4)

[salvino080-coder]

1. What are you trying to do?

Summary:

This contribution introduces SmallImmutableSet, a specialized implementation for sets containing 2, 3, or 4 elements. By replacing the standard hash table with a simple linear-scan array, we significantly reduce the memory footprint and improve CPU cache locality.

​Key Improvements:

​Memory Efficiency: Eliminates the int[] hash table array, saving ~32–48 bytes per instance. ​Performance: For n \le 4, linear search outperforms hashing by avoiding hashCode() computations and hash table probing. ​Reduced GC Pressure: Reduces the object count per set creation from two arrays to one. ​L1 Cache Locality: Small arrays stay entirely within a single CPU cache line, making contains() operations faster.

​Impact:

This is particularly beneficial for high-scale applications (e.g., dependency graphs, metadata mapping) where millions of small sets are held in memory.

Code:
package com.google.common.collect;

import com.google.common.annotations.GwtCompatible;
import java.util.Spliterator;
import java.util.Spliterators;
import javax.annotation.CheckForNull;

/**

• Optimized implementation of {@code ImmutableSet} for 2 to 4 elements.
• Uses linear scan to avoid hash table overhead, improving memory footprint
• and L1 cache locality for small collections.
  */
  @GwtCompatible(serializable = true, emulated = true)
  final class SmallImmutableSet extends ImmutableSet {
  private final transient Object[] elements;

SmallImmutableSet(Object[] elements) {
this.elements = elements;
}

@OverRide
public int size() {
return elements.length;
}

@OverRide
public boolean contains(@checkfornull Object target) {
if (target == null) return false;
// Linear scan is faster than hashing for n <= 4
for (Object element : elements) {
if (element.equals(target)) {
return true;
}
}
return false;
}

@OverRide
public UnmodifiableIterator iterator() {
return (UnmodifiableIterator) Iterators.forArray(elements);
}

@OverRide
public Spliterator spliterator() {
return Spliterators.spliterator(elements, SPLITERATOR_CHARACTERISTICS);
}

@OverRide
boolean isPartialView() {
return false;
}

@OverRide
int copyIntoArray(Object[] dst, int offset) {
System.arraycopy(elements, 0, dst, offset, elements.length);
return offset + elements.length;
}

@OverRide
ImmutableList createAsList() {
return ImmutableList.asImmutableList(elements);
}
}

Integration point:
private static ImmutableSet construct(int n, Object... elements) {
switch (n) {
case 0:
return of();
case 1:
@SuppressWarnings("unchecked")
E elem = (E) elements[0];
return of(elem);
case 2:
case 3:
case 4:
// NEW: Memory and CPU optimization for tiny sets
return new SmallImmutableSet(elements);
default:
return RegularImmutableSet.create(n, elements);
}
}

2. What's the best code you can write to accomplish that without the new feature?

Possible i try to optimized this idea if is a good idea for the project

3. What would that same code look like if we added your feature?

If the specialized engeneer can do best for this code implement the engeneer contribution

(Optional) What would the method signatures for your feature look like?

Concrete Use Cases

Memory, calculated ecc

Packages

No response

Checklist

• I agree to follow the code of conduct.

• I have read and understood the contribution guidelines.

• I have read and understood Guava's philosophy, and I strongly believe that this proposal aligns with it.

• I have visited the idea graveyard, and did not see anything similar to this idea.

[lowasser]

The major tradeoff here is in the significant difference in overhead calls to polymorphic methods when there are two versus three or more probable or possible implementations of the type. See e.g. https://shipilev.net/blog/2015/black-magic-method-dispatch/. Keeping the number of "usual" implementations of ImmutableSet to at most two provides nontrivial performance benefit.

[cpovirk edit: JDK-8180450]

[salvino080-coder]

Technical Response (for the Issue/PR)
Title: Refined Proposal: Internalizing linear-scan optimization within RegularImmutableSet to preserve bimorphism.
Description:
"I appreciate the feedback regarding the JIT dispatch overhead. To avoid pushing ImmutableSet into megamorphic dispatch, I have refined the implementation. Instead of a new class, I am proposing to modify RegularImmutableSet to support a 'table-less' mode for small collections (n=2 to 4).
Improvements:

• Preserves Bimorphism: We keep only two implementations (Singleton and Regular), ensuring the JVM can still optimize method dispatch effectively.
• Conditional Memory Savings: For n \le 4, the table array is not allocated (remains null), saving significant heap space.
• Branch-Friendly Lookup: The contains method checks for a null table. Modern branch predictors handle this extremely well, and the subsequent linear scan avoids the overhead of hashing.
  Impact:
  We get the memory benefits of the previous proposal without the global performance penalty of megamorphism."
  The Optimized Code
  File: guava/src/com/google/common/collect/RegularImmutableSet.java
  @GwtCompatible(serializable = true, emulated = true)
  final class RegularImmutableSet extends ImmutableSet {
  static final RegularImmutableSet EMPTY =
  new RegularImmutableSet<>(new Object[0], 0, null, 0);

  private final transient Object[] elements;
  // Non-final to allow for potential future internal optimizations
  @checkfornull private final transient Object[] table;
  private final transient int mask;
  private final transient int hashCode;

  RegularImmutableSet(Object[] elements, int hashCode, @checkfornull Object[] table, int mask) {
  this.elements = elements;
  this.table = table; // Table is null for n=2-4
  this.mask = mask;
  this.hashCode = hashCode;
  }

  @OverRide
  public boolean contains(@checkfornull Object target) {
  Object[] table = this.table;
  if (target == null) {
  return false;
  }

  // Optimized: If table is null, perform linear scan (preserves bimorphism)
  if (table == null) {
    for (Object element : elements) {
      if (element.equals(target)) {
        return true;
      }
    }
    return false;
  }
  
  // Standard Hashing logic
  for (int i = Hashing.smear(target.hashCode()); ; i++) {
    i &= mask;
    Object candidate = table[i];
    if (candidate == null) {
      return false;
    } else if (candidate.equals(target)) {
      return true;
    }
  }
  

  }

  @OverRide
  public int size() {
  return elements.length;
  }

  // ... rest of the implementation
  }

  File: guava/src/com/google/common/collect/ImmutableSet.java
  (Updating the factory logic)
  private static ImmutableSet construct(int n, Object... elements) {
  switch (n) {
  case 0:
  return of();
  case 1:
  return of((E) elements[0]);
  case 2:
  case 3:
  case 4:
  // Create a RegularImmutableSet WITHOUT a hash table
  int hashCode = 0;
  for (Object e : elements) hashCode += e.hashCode();
  return new RegularImmutableSet(elements, hashCode, null, 0);
  default:
  // Standard creation with hash table for n > 4
  return RegularImmutableSet.create(n, elements);
  }
  }

[salvino080-coder]

Optimization for my last comment:

if (table == null) {
for (int i = 0; i < elements.length; i++) {
if (elements[i].equals(target)) return true;
}
return false;
}