ElementCostInDataStructures

This is the cost per element in major data structures offered by Java and Guava (r11)].
Featured

Updated May 22 (5 days ago) by jim.andreou

Cost per element/entry in various well-known Java/Guava data structures

Ever wondered what's the cost of adding each entry to a HashMap? Or one new element in a TreeSet? Here are the answers: the cost per-entry for each well-known structure in Java and Guava. You can use this to estimate the cost of a structure, like this: if the per-entry cost of a structure is 32 bytes, and your structure contains 1024 elements, the structure's footprint will be around 32 kilobytes.

The data was computed just for a 32bit VM for now ( on a 64bit machine). On a 64bit VM, expect to have roughly double the cost. There is a blog post about this data as well.

Since the most interesting and analyzed structure here is [Loading]Cache, here is a short cheat-sheet to help you memorize the cost of each feature:

If you use ConcurrentHashMap, you pay 8 words (32 bytes) for each entry.
If you switch to Cache, add 4 words (16 bytes) for each entry
If you add expiration of any kind (after write, or after access, or both), add 4 words (16 bytes) for each entry
If you use maximumSize(), add 4 words (16 bytes) for each entry
If you use weakKeys(), add 4 words (16 bytes) for each entry
If you use weakValues() or softValues(), add 4 words (16 bytes) for each entry

To put this in perspective: For every two features you pick (expiration, maxSize, weakKeys, weak/softValues), you could have bought a whole new ConcurrentHashMap (with the same entries) for the same cost.

==========================================     32-bit architecture    ==========================================

==========================================     Primitive Wrappers     ==========================================

                       java.lang.Boolean :: Bytes =     16, Objects =     1 Refs =     0 Primitives = [boolean]
                          java.lang.Byte :: Bytes =     16, Objects =     1 Refs =     0 Primitives = [byte]
                         java.lang.Short :: Bytes =     16, Objects =     1 Refs =     0 Primitives = [short]
                     java.lang.Character :: Bytes =     16, Objects =     1 Refs =     0 Primitives = [char]
                       java.lang.Integer :: Bytes =     16, Objects =     1 Refs =     0 Primitives = [int]
                          java.lang.Long :: Bytes =     16, Objects =     1 Refs =     0 Primitives = [long]
                         java.lang.Float :: Bytes =     16, Objects =     1 Refs =     0 Primitives = [float]
                        java.lang.Double :: Bytes =     16, Objects =     1 Refs =     0 Primitives = [double]

==========================================   Basic Lists, Sets, Maps  ==========================================

                               ArrayList :: Bytes =   5.85, Objects =  0.00 Refs =  1.46 Primitives = {}
                           ImmutableList :: Bytes =   4.00, Objects =  0.00 Refs =  1.00 Primitives = {}
                                 HashSet :: Bytes =  32.24, Objects =  1.00 Refs =  5.06 Primitives = {int=1.0}
                            ImmutableSet :: Bytes =  12.24, Objects =  0.00 Refs =  3.06 Primitives = {}
                           LinkedHashSet :: Bytes =  40.24, Objects =  1.00 Refs =  7.06 Primitives = {int=1.0}
          newSetFromMap(IdentityHashMap) :: Bytes =  16.48, Objects =  0.00 Refs =  4.12 Primitives = {}
                                 TreeSet :: Bytes =  32.00, Objects =  1.00 Refs =  5.00 Primitives = {boolean=1.0}
                      ImmutableSortedSet :: Bytes =   4.02, Objects =  0.00 Refs =  1.00 Primitives = {int=5.040322580645161E-4}
                                 HashMap :: Bytes =  32.24, Objects =  1.00 Refs =  5.06 Primitives = {int=1.0}
                            ImmutableMap :: Bytes =  27.43, Objects =  1.00 Refs =  4.54 Primitives = {}
                           LinkedHashMap :: Bytes =  40.24, Objects =  1.00 Refs =  7.06 Primitives = {int=1.0}
                         IdentityHashMap :: Bytes =  16.48, Objects =  0.00 Refs =  4.12 Primitives = {}
                                 TreeMap :: Bytes =  32.00, Objects =  1.00 Refs =  5.00 Primitives = {boolean=1.0}
                      ImmutableSortedMap :: Bytes =  20.03, Objects =  1.00 Refs =  3.00 Primitives = {long=-1.2600806451612903E-4, int=0.0010080645161290322}

========================================== ConcurrentHashMap/MapMaker/Cache ==========================================

                       ConcurrentHashMap :: Bytes =  32.26, Objects =  1.00 Refs =  5.06 Primitives = {int=1.0}
                                MapMaker :: Bytes =  32.25, Objects =  1.00 Refs =  5.06 Primitives = {int=1.0}
                      MapMaker_Computing :: Bytes =  48.24, Objects =  2.00 Refs =  6.06 Primitives = {int=1.0}
                                   Cache :: Bytes =  48.24, Objects =  2.00 Refs =  6.06 Primitives = {int=1.0}
                        MapMaker_Expires :: Bytes =  64.25, Objects =  2.00 Refs =  8.06 Primitives = {long=1.0, int=1.0}
                           Cache_Expires :: Bytes =  64.24, Objects =  2.00 Refs =  8.06 Primitives = {long=1.0, int=1.0}
                        MapMaker_MaxSize :: Bytes =  56.25, Objects =  2.00 Refs =  8.06 Primitives = {int=1.0}
                           Cache_MaxSize :: Bytes =  64.24, Objects =  2.00 Refs =  8.06 Primitives = {long=1.0, int=1.0}
                MapMaker_Expires_MaxSize :: Bytes =  72.24, Objects =  2.00 Refs = 10.06 Primitives = {long=1.0, int=1.0}
                   Cache_Expires_MaxSize :: Bytes =  80.24, Objects =  2.00 Refs = 10.06 Primitives = {long=2.0, int=1.0}
                       MapMaker_WeakKeys :: Bytes =  64.24, Objects =  2.00 Refs =  9.06 Primitives = {int=1.0}
                          Cache_WeakKeys :: Bytes =  64.25, Objects =  2.00 Refs =  9.06 Primitives = {int=1.0}
                     MapMaker_WeakValues :: Bytes =  64.24, Objects =  2.00 Refs = 10.06 Primitives = {int=1.0}
                        Cache_WeakValues :: Bytes =  64.24, Objects =  2.00 Refs = 10.06 Primitives = {int=1.0}
                 MapMaker_WeakKeysValues :: Bytes =  80.24, Objects =  2.00 Refs = 13.06 Primitives = {int=1.0}
                    Cache_WeakKeysValues :: Bytes =  80.24, Objects =  2.00 Refs = 13.06 Primitives = {int=1.0}
               MapMaker_MaxSize_WeakKeys :: Bytes =  72.25, Objects =  2.00 Refs = 11.06 Primitives = {int=1.0}
                  Cache_MaxSize_WeakKeys :: Bytes =  80.25, Objects =  2.00 Refs = 11.06 Primitives = {long=1.0, int=1.0}
             MapMaker_MaxSize_WeakValues :: Bytes =  72.24, Objects =  2.00 Refs = 12.06 Primitives = {int=1.0}
                Cache_MaxSize_WeakValues :: Bytes =  80.24, Objects =  2.00 Refs = 12.06 Primitives = {long=1.0, int=1.0}
         MapMaker_MaxSize_WeakKeysValues :: Bytes =  88.24, Objects =  2.00 Refs = 15.06 Primitives = {int=1.0}
            Cache_MaxSize_WeakKeysValues :: Bytes =  96.24, Objects =  2.00 Refs = 15.06 Primitives = {long=1.0, int=1.0}
               MapMaker_Expires_WeakKeys :: Bytes =  80.25, Objects =  2.00 Refs = 11.06 Primitives = {long=1.0, int=1.0}
                  Cache_Expires_WeakKeys :: Bytes =  80.24, Objects =  2.00 Refs = 11.06 Primitives = {long=1.0, int=1.0}
             MapMaker_Expires_WeakValues :: Bytes =  80.24, Objects =  2.00 Refs = 12.06 Primitives = {long=1.0, int=1.0}
                Cache_Expires_WeakValues :: Bytes =  80.24, Objects =  2.00 Refs = 12.06 Primitives = {long=1.0, int=1.0}
         MapMaker_Expires_WeakKeysValues :: Bytes =  96.24, Objects =  2.00 Refs = 15.06 Primitives = {long=1.0, int=1.0}
            Cache_Expires_WeakKeysValues :: Bytes =  96.25, Objects =  2.00 Refs = 15.06 Primitives = {long=1.0, int=1.0}
       MapMaker_Expires_MaxSize_WeakKeys :: Bytes =  88.24, Objects =  2.00 Refs = 13.06 Primitives = {long=1.0, int=1.0}
          Cache_Expires_MaxSize_WeakKeys :: Bytes =  96.25, Objects =  2.00 Refs = 13.06 Primitives = {long=2.0, int=1.0}
     MapMaker_Expires_MaxSize_WeakValues :: Bytes =  88.24, Objects =  2.00 Refs = 14.06 Primitives = {long=1.0, int=1.0}
        Cache_Expires_MaxSize_WeakValues :: Bytes =  96.25, Objects =  2.00 Refs = 14.06 Primitives = {long=2.0, int=1.0}
 MapMaker_Expires_MaxSize_WeakKeysValues :: Bytes = 104.24, Objects =  2.00 Refs = 17.06 Primitives = {long=1.0, int=1.0}
    Cache_Expires_MaxSize_WeakKeysValues :: Bytes = 112.24, Objects =  2.00 Refs = 17.06 Primitives = {long=2.0, int=1.0}

==========================================         Multisets          ==========================================

                      HashMultiset_Worst :: Bytes =  48.24, Objects =  2.00 Refs =  5.06 Primitives = {int=2.0}
                LinkedHashMultiset_Worst :: Bytes =  56.24, Objects =  2.00 Refs =  7.06 Primitives = {int=2.0}
                      TreeMultiset_Worst :: Bytes =  48.00, Objects =  1.00 Refs =  5.00 Primitives = {long=1.0, int=3.0}
            ConcurrentHashMultiset_Worst :: Bytes =  48.25, Objects =  2.00 Refs =  5.06 Primitives = {int=2.0}
        ImmutableMultisetPopulator_Worst :: Bytes =  26.96, Objects =  1.00 Refs =  4.39 Primitives = {}
  ImmutableSortedMultisetPopulator_Worst :: Bytes =  16.02, Objects =  0.00 Refs =  1.00 Primitives = {long=1.0, int=1.0005040322580645}

                      HashMultiset_Best  :: Bytes =   0.00, Objects =  0.00 Refs =  0.00 Primitives = {}
                LinkedHashMultiset_Best  :: Bytes =   0.00, Objects =  0.00 Refs =  0.00 Primitives = {}
                      TreeMultiset_Best  :: Bytes =   0.00, Objects =  0.00 Refs =  0.00 Primitives = {}
            ConcurrentHashMultiset_Best  :: Bytes =   0.00, Objects =  0.00 Refs =  0.00 Primitives = {}
        ImmutableMultisetPopulator_Best  :: Bytes =   0.00, Objects =  0.00 Refs =  0.00 Primitives = {}
  ImmutableSortedMultisetPopulator_Best  :: Bytes =   0.00, Objects =  0.00 Refs =  0.00 Primitives = {}

==========================================         Multimaps          ==========================================

                      HashMultimap_Worst :: Bytes = 144.24, Objects =  5.00 Refs = 17.06 Primitives = {int=5.0, float=1.0}
                LinkedHashMultimap_Worst :: Bytes = 328.48, Objects =  9.00 Refs = 51.12 Primitives = {boolean=1.0, int=7.0, float=1.0}
                      TreeMultimap_Worst :: Bytes = 128.00, Objects =  4.00 Refs = 18.00 Primitives = {boolean=2.0, int=2.0}
                 ArrayListMultimap_Worst :: Bytes =  80.24, Objects =  3.00 Refs =  9.06 Primitives = {int=3.0}
                LinkedListMultimap_Worst :: Bytes = 152.73, Objects =  5.00 Refs = 23.18 Primitives = {int=4.0}
                 ImmutableMultimap_Worst :: Bytes =  43.04, Objects =  2.00 Refs =  6.40 Primitives = {}
             ImmutableListMultimap_Worst :: Bytes =  42.99, Objects =  2.00 Refs =  6.39 Primitives = {}
              ImmutableSetMultimap_Worst :: Bytes =  51.03, Objects =  2.00 Refs =  6.39 Primitives = {int=1.0}

                      HashMultimap_Best  :: Bytes =  32.24, Objects =  1.00 Refs =  5.06 Primitives = {int=1.0}
                LinkedHashMultimap_Best  :: Bytes =  96.48, Objects =  3.00 Refs = 16.12 Primitives = {int=2.0}
                      TreeMultimap_Best  :: Bytes =  32.00, Objects =  1.00 Refs =  5.00 Primitives = {boolean=1.0}
                 ArrayListMultimap_Best  :: Bytes =   4.71, Objects =  0.00 Refs =  1.18 Primitives = {}
                LinkedListMultimap_Best  :: Bytes =  32.00, Objects =  1.00 Refs =  6.00 Primitives = {}
                 ImmutableMultimap_Best  :: Bytes =   4.00, Objects =  0.00 Refs =  1.00 Primitives = {}
             ImmutableListMultimap_Best  :: Bytes =   4.00, Objects =  0.00 Refs =  1.00 Primitives = {}
              ImmutableSetMultimap_Best  :: Bytes =  12.24, Objects =  0.00 Refs =  3.06 Primitives = {}

Note: we now use the default static factories for each multimap. Older versions used #create(1, 1) factory where applicable, thus smaller numbers were reported. E.g. now HashMultimap_Worst is 144, with the default create(), but:

with create(x, 1), the cost is ~136 bytes
with create(x, 8), the old default (<= Guava 12) the cost was ~192

==========================================           Tables           ==========================================

                   HashBasedTable_Square :: Bytes =  30.61, Objects =  1.03 Refs =  4.51 Primitives = {int=1.0428427419354838, float=0.010710685483870967}
                   ImmutableTable_Square :: Bytes =  41.33, Objects =  1.04 Refs =  7.18 Primitives = {int=0.032132056451612906}
                   TreeBasedTable_Square :: Bytes =  32.86, Objects =  1.02 Refs =  5.13 Primitives = {boolean=1.010710685483871, int=0.021421370967741934}
                 HashBasedTable_Diagonal :: Bytes = 120.24, Objects =  4.00 Refs = 14.06 Primitives = {int=5.0, float=1.0}
                 ImmutableTable_Diagonal :: Bytes = 186.21, Objects =  7.00 Refs = 30.84 Primitives = {}
                 TreeBasedTable_Diagonal :: Bytes = 112.00, Objects =  3.00 Refs = 17.00 Primitives = {boolean=2.0, int=2.0}
                HashBasedTable_SingleRow :: Bytes =  32.24, Objects =  1.00 Refs =  5.06 Primitives = {int=1.0}
                ImmutableTable_SingleRow :: Bytes =  87.24, Objects =  3.00 Refs = 11.45 Primitives = {int=2.0}
                TreeBasedTable_SingleRow :: Bytes =  32.00, Objects =  1.00 Refs =  5.00 Primitives = {boolean=1.0}
             HashBasedTable_SingleColumn :: Bytes = 120.24, Objects =  4.00 Refs = 14.06 Primitives = {int=5.0, float=1.0}
             ImmutableTable_SingleColumn :: Bytes = 103.26, Objects =  4.00 Refs = 12.45 Primitives = {int=2.0}
             TreeBasedTable_SingleColumn :: Bytes = 112.00, Objects =  3.00 Refs = 17.00 Primitives = {boolean=2.0, int=2.0}

For a Table of N elements:

'Square' means that we have about sqrt(N) rows and sqrt(N) columns.
'Diagonal' means N rows and N columns
'SingleRow', 1 row, N columns
'SingleColumn', N rows, 1 column

==========================================           BiMaps           ==========================================

                               HashBiMap :: Bytes =  64.48, Objects =  2.00 Refs = 10.12 Primitives = {int=2.0}
                          ImmutableBiMap :: Bytes =  54.06, Objects =  2.00 Refs =  8.79 Primitives = {}

==========================================            Misc            ==========================================

                             WeakHashMap :: Bytes =  48.24, Objects =  1.00 Refs =  8.06 Primitives = {int=1.0}
                              LinkedList :: Bytes =  24.00, Objects =  1.00 Refs =  3.00 Primitives = {}
                              ArrayDeque :: Bytes =   4.11, Objects =  0.00 Refs =  1.03 Primitives = {}
                           PriorityQueue :: Bytes =   4.40, Objects =  0.00 Refs =  1.10 Primitives = {}
                   PriorityBlockingQueue :: Bytes =   4.40, Objects =  0.00 Refs =  1.10 Primitives = {}
                   ConcurrentSkipListSet :: Bytes =  35.82, Objects =  1.49 Refs =  4.48 Primitives = {int=0.0010080645161290322}
                    CopyOnWriteArrayList :: Bytes =   4.00, Objects =  0.00 Refs =  1.00 Primitives = {}
                     CopyOnWriteArraySet :: Bytes =   4.00, Objects =  0.00 Refs =  1.00 Primitives = {}
                              DelayQueue :: Bytes =   4.40, Objects =  0.00 Refs =  1.10 Primitives = {}
                     LinkedBlockingQueue :: Bytes =  16.00, Objects =  1.00 Refs =  2.00 Primitives = {}
                     LinkedBlockingDeque :: Bytes =  24.00, Objects =  1.00 Refs =  3.00 Primitives = {}

==========================================   Synchronization Structures ==========================================

                           ReentrantLock :: Bytes =     40, Objects =     2 Refs =     4 Primitives = [int]
                               Semaphore :: Bytes =     40, Objects =     2 Refs =     4 Primitives = [int]
                           ReadWriteLock :: Bytes =    112, Objects =     5 Refs =    11 Primitives = [int x 3]

A few more clarifications and observations:

HashMultimap_Worst means that every key only maps to a single value. The huge memory cost you see is because by default a big hashtable is allocated per key - you can fine-tune this size though. Conversely, the "best" case is where a single key maps to all values - there, the per-entry cost degenerates to the per-entry cost of a regular HashMap, for obvious reasons. The per-entry cost of a realistic HashMultimap will be somewhere (depending on the distribution of values in keys) between these two limits. Similarly, it should be obvious why HashMultiset_Best reports zero cost in everything.

Comment by wasserman.louis, Feb 7, 2012

Could we get ImmutableTable? in here?

Comment by fry@google.com, Feb 9, 2012

Jim, in the case of Loading?Cache you fail to distinguish between expire-after-write and expire-after-access. Specifically, expire-after-access and maximum-size reuse the same internal data structure.

Comment by andr...@google.com, Feb 9, 2012

Charles, perhaps this phrase is confusing?

"If you add expiration of any kind (after write, or after access, or both), add 4 words (16 bytes) for each entry"

What I mean by this, is that "even if you use both expiration kinds together, you still just pay 4 words". (Not 8!). The reason the table below just says "Expires" without discrimination is because I tried both (separately and in combination), I got the same results, so I simplified the presentation to make it easier to read (it would be a lot bigger otherwise).

Comment by project member jim.andreou, Mar 4, 2012

Added ImmutableTable?. Feeling a bit underwhelmed by the result, but then... that's the result of the choice made that immutable structures should have a predictable element order. In two dimensions, the extra overhead due to that becomes more apparent. Oh well.

Charles, if you're reading: should we link this page from guava somewhere?

Comment by wasserman.louis, Apr 3, 2012

Notably omitted: ImmutableMultiset?, ImmutableSortedMultiset?? Also, has this been updated for Guava 12?

Comment by fry@google.com, Apr 7, 2012

That's odd, because http://code.google.com/p/guava-libraries/source/detail?r=2f345c3c276773d555938699f467f722ade40441 changed Cache to use separate data structures for expireAfterWrite and expireAfterAccess. (Before that I agree that they were the same.)

Comment by fry@google.com, Apr 9, 2012

That said, expireAfterAccess and maximumSize/Weight use the same access queue for ordering.

Comment by project member jim.andreou, May 22 (5 days ago)

Updated with the types Louis mentioned. I haven't checked whether the theory/formulas (in the header) about CacheBuilder? still hold.

Can't remember if this was the case earlier, entries in Cache apparently use one field more than entries in MapMaker?. Unfortunately google code seems to turned off a feature to see earlier revisions of a wiki page, so I can't see when this started to happen :-/

Comment by knut.wan...@gmail.com, May 24 (3 days ago)

I think you can inspect the changes to the wiki page under Source > Changes: http://code.google.com/p/memory-measurer/source/list.

► Sign in to add a comment