Question regarding the int32_t obj_md_size variable inside the cache_t struct.

[laustam]

Inside of cache.h, the struct cache_t is defined with some important variables descriptive of the specific cache eviction algorithm used. One of these variables is the int32_t obj_md_size.

My first question would be, (Q1) what does the obj_md_size variable exactly represent? I suppose its value represents the number of bytes that the cache uses for metadata stored.

A follow-up question would be, (Q2) is obj_md_size correctly initialized in Sieve_init() and LRU_init()? The current implementation does the following: If an object's metadata should be considered, Sieve's initialisation function sets obj_md_size to 1, although Sieve_params_t consists of three separate cache_obj_t pointers. On the other hand, LRU's initialisation function sets this value to 8 * 2; (Q3) does this represent the two pointers for the queue's head and tail?

[1a1a11a]

Hi @laustam ,
Thank you for the excellent questions!

• Yes you are right, obj_md_size is the metadata size a cache uses for an object. This is important for workloads with small objects, e.g., many of the KV-cache workloads
• Good catch, both SIEVE and LRU should use two pointers. The SIEVE implementation was based on FIFO-Reinsertion, and I forgot to change it.
• The two pointers are used to connect prev and next objects in the doubly linked-list; the head and tail are not considered because the large number of objects amortizes it.

[laustam]

Thanks, this clarifies some of my confusion! I initially thought that the obj_md_size expressed the size of the structs for Sieve_params_t and LRU_params_t, but from what I understand, it instead describes the size of a single object in the cache. I also noticed that each object in a Sieve cache contains a bool visited. Should this be considered part of the obj_md_size as well, aside from two pointers for prev and next? Additionally, it might be a good idea to initialise the obj_md_size using sizeof(queue) for better clarity. Please let me know your thoughts.

[1a1a11a]

The one-bit counter can piggyback on pointers or flags in many implementations, so I did not include it in the byte count.
I agree that we should make it more clear, but what is queue here?

[laustam]

I should have specified what I mean by queue. In cacheObj.h, the struct cache_obj_t is defined, with an internal struct [queue](

libCacheSim/libCacheSim/include/libCacheSim/cacheObj.h

Lines 157 to 160 in 6305dbf

	struct {
	struct cache_obj *prev;
	struct cache_obj *next;
	} queue; // for LRU, FIFO, etc.

) which holds two pointers to prev and next. I believe this must be the metadata that is accounted for? If so, something like sizeof((cache_obj_t *)0)->queue) might be a good clarification for the reader.

A small correction on my part, the Sieve implementation does not contain a bool visited inside its Sieve_obj_params_t, but instead an int32_t freq... I am not quite sure why this is not a boolean value, as the implementation of Sieve in the paper itself implies that it only requires a single bit representing the visited state.

[1a1a11a]

1. the metadata size is not tied to libCacheSim, but rather try to capture the metadata size needed for a real system, from this perspective, using queue is not necessary and can cause an issue if the user uses a 32-bit computer (not sure whether they are still available today...). I agree that better documentation is needed, so I am okay with changing it to sizeof(((cache_obj_t *)0)->queue), or adding some comments.
2. We explored using multiple bits, which is why we use int32_t. Since the goal is to capture the metadata needed for a real system, we did not change it to a boolean variable here.