SmallMap is not so "small"

[stokito]

You can test a size with JOL library. To do that add this dependency:

        <dependency>
            <groupId>org.openjdk.jol</groupId>
            <artifactId>jol-core</artifactId>
            <version>0.9</version>
        </dependency>

Then write a test like:

    public static void main(String[] args) throws Exception {
        out.println(VM.current().details());
        HashMap hashMap = new HashMap(16, 1.0F);
        for (int i = 0; i < 16; i++) {
            hashMap.put(i, i);
        }
        out.println(ClassLayout.parseInstance(hashMap).toPrintable());
        out.println(GraphLayout.parseInstance(hashMap).toFootprint());

        Map<Integer, Integer> arraysMap = new SmallMap<>();
        for (int i = 0; i < 16; i++) {
            arraysMap.put(i, i);
        }
        out.println(ClassLayout.parseInstance(arraysMap).toPrintable());
        out.println(GraphLayout.parseInstance(arraysMap).toFootprint());
    }

Output:

# Running 64-bit HotSpot VM.
# Using compressed oop with 0-bit shift.
# Using compressed klass with 3-bit shift.
# Objects are 8 bytes aligned.
# Field sizes by type: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]
# Array element sizes: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]

java.util.HashMap object internals:
 OFFSET  SIZE                       TYPE DESCRIPTION                               VALUE
      0    12                            (object header)                           N/A
     12     4              java.util.Set AbstractMap.keySet                        N/A
     16     4       java.util.Collection AbstractMap.values                        N/A
     20     4                        int HashMap.size                              N/A
     24     4                        int HashMap.modCount                          N/A
     28     4                        int HashMap.threshold                         N/A
     32     4                      float HashMap.loadFactor                        N/A
     36     4   java.util.HashMap.Node[] HashMap.table                             N/A
     40     4              java.util.Set HashMap.entrySet                          N/A
     44     4                            (loss due to the next object alignment)
Instance size: 48 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

java.util.HashMap@1ee0005d footprint:
     COUNT       AVG       SUM   DESCRIPTION
         1        48        48   [Ljava.util.HashMap$Node;
         8        16       128   java.lang.Integer
         1        48        48   java.util.HashMap
         8        32       256   java.util.HashMap$Node
        18                 480   (total)

com.github.zteve.smallcollections.SmallMap object internals:
 OFFSET  SIZE                   TYPE DESCRIPTION                               VALUE
      0    12                        (object header)                           N/A
     12     4          java.util.Set AbstractMap.keySet                        N/A
     16     4   java.util.Collection AbstractMap.values                        N/A
     20     4    java.util.ArrayList SmallMap.keyArray                         N/A
     24     4    java.util.ArrayList SmallMap.valueArray                       N/A
     28     4                        (loss due to the next object alignment)
Instance size: 32 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

com.github.zteve.smallcollections.SmallMap@67f89fa3d footprint:
     COUNT       AVG       SUM   DESCRIPTION
         2        56       112   [Ljava.lang.Object;
         1        32        32   com.github.zteve.smallcollections.SmallMap
         8        16       128   java.lang.Integer
         2        24        48   java.util.ArrayList
        13                 320   (total)

Now let's try to interpret results:

• Instance of the HashMap itself takes 48 bytes while the SmallMap 32 and most of them spent for cached AbstractMap.keySet and AbstractMap.values.
• SM contains two ArrayLists and both have default capacity 10 items, that's why I putted 8 entries in both maps to make comparison more fair.
• So 8 entries in hash map took 480 bytes and 128 bytes of them are integer objects i.e. 480 - 128 = 352 bytes for hash map and it's entries.
• 8 entries in SM took 320 bytes - 128 of integers = 192 bytes.

My notes:

1. Actually you can make a single array for both keys and values. E.g. Map.MapN class in JDK9 uses one array.
2. Having two arrays can lead to cache line misses.
3. Instead of extending of AbstractMap it may be useful to copy it's methods and reuse keySet and values.

Hope this is useful for you