memory usage monitoring

[1a1a11a]

Currently the memory usage of cachesim is not predictable and causes OOM if there is not enough DRAM.
We would like to

1. perform a detailed memory profiling and see where we can save some DRAM;
2. stop allocating more memory if there is not enough DRAM left. For example, we can use the hash table at a higher load factor; or we can pause the execution and wait till there is enough resource.

[JasonGuo98]

Maybe we can use the massif tool to monitor the memory usage of cachesim. This tool helps us to get some useful statistics, such as memory usage over time, and the proportion of memory allocated by specific lines of code. Below is an example of my profiling results.

commands

# Compile in Debug mode to get line of code information
cmake .. -DCMAKE_BUILD_TYPE=Debug
make -j
valgrind --tool=massif --massif-out-file=massif.out ./bin/cachesim /path/to/wiki_2019t.oracleGeneral oracleGeneral s3fifo 1gb
ms_print ./massif.out > massif.result

results

The result file shows the peak memory usage is 519.4MB. 98.97% of memory is used for create_chained_hashtable_v2 (chainedHashTableV2.c:93). In the function S3FIFO_init(), there is one cache_struct_init() call and three FIFO_init() calls, each of which incurs another cache_struct_init(). In total, there are four cache_struct_init() calls, which create four hash tables. Each hash table occupies 24.74% of the allocated memory.

    MB
519.4^                                        :                               
     |#:::::::::::::@::::::::::::::::@::@@::::::::::::::::::::::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
     |#::: :: :: :::@: ::::: : ::: ::@::@ ::: :: : : ::::::: :::::@::@::@::@::
   0 +----------------------------------------------------------------------->Gi
     0                                                                   652.3



--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
  0              0                0                0             0            0
  1    174,738,746      542,473,864      541,412,480     1,061,384            0
99.80% (541,412,480B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->98.97% (536,870,912B) 0x483659: create_chained_hashtable_v2 (chainedHashTableV2.c:93)
| ->98.97% (536,870,912B) 0x48CCD6: cache_struct_init (cache.c:60)
|   ->74.23% (402,653,184B) 0x40FEB3: FIFO_init (FIFO.c:51)
|   | ->24.74% (134,217,728B) 0x423884: S3FIFO_init (S3FIFO.c:113)
|   | | ->24.74% (134,217,728B) 0x40880A: create_cache (cache_init.h:132)
|   | |   ->24.74% (134,217,728B) 0x40970B: parse_cmd (cli_parser.c:343)
|   | |     ->24.74% (134,217,728B) 0x406FFD: main (main.c:18)
|   | |       
|   | ->24.74% (134,217,728B) 0x4238C0: S3FIFO_init (S3FIFO.c:118)
|   | | ->24.74% (134,217,728B) 0x40880A: create_cache (cache_init.h:132)
|   | |   ->24.74% (134,217,728B) 0x40970B: parse_cmd (cli_parser.c:343)
|   | |     ->24.74% (134,217,728B) 0x406FFD: main (main.c:18)
|   | |       
|   | ->24.74% (134,217,728B) 0x423921: S3FIFO_init (S3FIFO.c:125)
|   |   ->24.74% (134,217,728B) 0x40880A: create_cache (cache_init.h:132)
|   |     ->24.74% (134,217,728B) 0x40970B: parse_cmd (cli_parser.c:343)
|   |       ->24.74% (134,217,728B) 0x406FFD: main (main.c:18)
|   |         
|   ->24.74% (134,217,728B) 0x4236BB: S3FIFO_init (S3FIFO.c:81)
|     ->24.74% (134,217,728B) 0x40880A: create_cache (cache_init.h:132)
|       ->24.74% (134,217,728B) 0x40970B: parse_cmd (cli_parser.c:343)
|         ->24.74% (134,217,728B) 0x406FFD: main (main.c:18)
|           
->00.84% (4,541,568B) in 1+ places, all below ms_print's threshold (01.00%)

[1a1a11a]

Awesome, can you add this as a doc on how to profile and optimize memory usage?
You can then create an issue and list a few optimization ideas.

[JasonGuo98]

I am testing the memory usage of different algorithms. I will write a document analyzing their current memory usage and try to optimize it by adjusting the initial size of hash tables and reducing redundant allocations.💪

[manishpaulish]

Hey, building on JasonGuo98's profiling, the numbers make sense once you look at config.h:

#define HASH_POWER_DEFAULT 23   // 2^23 = 8M buckets

S3FIFO creates 4 caches internally (one main + three FIFO sub-caches), each calling cache_struct_init() which allocates 8M * 8 bytes = 128MB for the pointer table upfront. That's where the 4 × 24.74% comes from in the massif output, all of it allocated before a single object is stored.
A few ideas for fixing this:

1. Derive initial hashpower from cache size
   Instead of always starting at 23, start smaller and grow. If the cache is configured for N bytes with average object size S, the max number of objects is roughly N/S, so the initial hashpower only needs to be ceil(log2(N/S)). For a 1GB cache with 1KB average objects that's about hashpower=20, cutting each table's initial allocation from 128MB to 16MB, 8× reduction.
2. Raise the expand threshold
   CHAINED_HASHTABLE_EXPAND_THRESHOLD = 2 means we expand at 200% load. Bumping this to 4 or 5 means we can start with a smaller table and still hold the same number of objects before needing to resize, at the cost of slightly longer chains. For simulation use cases where you care more about memory than lookup latency this seems like a reasonable tradeoff.
3. For multi-component algorithms like S3FIFO specifically
   The three FIFO sub-caches share the same default hashpower as the main cache even though they're much smaller (S3FIFO splits the cache into small/main/ghost queues). Each sub-cache could start with a hashpower proportional to its configured size fraction rather than the full default.
   Happy to open a PR for any of these. Option 1 or 3 seem like the highest-impact changes. Let me know which direction makes sense.

[haochengxia]

Thanks for the analysis. From my perspective, option 3 is good for the first step. It is local to S3FIFO, addresses a clear source of upfront memory waste.

For S3FIFO, each internal cache currently uses the same default HASH_POWER_DEFAULT, even though the sub-caches are much smaller than the full cache, e.g. the small queue is 10% and the main queue is 90% by default. We can derive each component’s initial hashpower from its configured size fraction instead.

Longer term, if this works well for S3FIFO, we can migrate the same idea into the global cache initialization path as a more general optimization for the fixed HASH_POWER_DEFAULT.

[manishpaulish]

Opened #316 implementing Option 3 as suggested by @haochengxia. Happy to extend to the global HASH_POWER_DEFAULT path if that direction makes sense after this lands.