Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.

concurrent_lru_cache question

Suresh_R_
Beginner
542 Views

According to the example  in the concurrent_lru_cache, the handle_object operator[] is used to populate the cache on a cache-miss.   Can this be made optional (or a noop) and the cache be not populated on a miss?  I could not see how to in the documentation or example.

Thanks

Suresh

0 Kudos
9 Replies
Anton_P_Intel
Employee
542 Views

Unfortunately it is not possible at the moment.

Could you, please, describe you scenario in order to better understan what exactly you trying to acheve ?

0 Kudos
Suresh_R_
Beginner
542 Views

I would like to use the LRU cache to be populated on writes and not on reads/cache misses.   So to be clear, I would like to do something like this:

LRU = val;   (or LRU = std::move(val))

Is this possible?  

Thanks

Suresh

0 Kudos
jimdempseyatthecove
Honored Contributor III
542 Views

You should be able to adapt the class yourself.

In an LRU cache implimentation what would you expect "LRU = val;" to mean?
Wouldn't you want a push_front(val)?
If the cache were full, this would drop the least least recently used entry.
If the new entry is a duplicate, and duplicates not permitted, then this could delete/squish the duplicate out then push_front.

Jim Dempsey

0 Kudos
MLema2
New Contributor I
542 Views

I can understand his need.  We have cache classes that perform the same (but is not lock free)

Typically, we lookup in a cache to see if an item is already found. If not, construct it and add it to the cache. 

Also, we keep an upper bound on the size of items stored in the cache (not only a number of items).  Each time we insert an intem in the cache, we also increment used memory size and decrement as we pop LRU items. This way, cache does not grows out of control with very large objects.

0 Kudos
jimdempseyatthecove
Honored Contributor III
542 Views

Michael,

Assuming the cache contains large objects. When a push into the cache exceeds capacity, you pop the LRU item. The item:

a) might not be referenced by other threads
b) might be referenced by other threads.
c) all reads from cache implicitly pops item out of cache, therefore it cannot be referenced by other threads.

There are untold requirements of your design:

a) can multiple threads can concurrently access the same item in the LRU cache?
b) does read access reposition item to MRU position in cache?
c) does read/reference item remove item from cache
d) can there be duplicates? if so how do you handle

Assume only 1 thread can access any single item in cache, assume when access finishes, the node is reinserted as MRU. To impliment this I would create a ring buffer of node pointers. NULL == empty cell, != NULL == pointer to arbitrary node. The ring buffer has a fill pointer only.

Find() snapshots the fill pointer, and runs the copy of the pointer around to at max to its modulus position. When (if) node found that contains key of interest perform CAS on pointer with found pointer and  NULL (fail if pointer changed, restart search). Prior to assuming found pointer returned by CAS is the one sought, and additional test is made for the key match. If key match now fails, the node is pushed back into the ring buffer, and search restarts.

push_front performs XCHGADD(&fillPointer, 1) and mod's the return value with the ring buffer size, performs XCHG at location and obtains value from ring buffer. The object could be deleted here or otherwise disposed of according to your pop removal requirements. (may get pushed into slower secondary LRU cache).

No locks are used.

Jim Dempsey

0 Kudos
MLema2
New Contributor I
542 Views

To answer your points:

  1. All objects are refcounted (with threadsafe counters). This solves the case where an object might be removed from the cache while still in use.
  2. Cached objects are read-only and multiple threads can access them simultaneously.
  3. Finding an object in the cache updates it's last used timestamp.
  4. Cached objects are uniques.
0 Kudos
jimdempseyatthecove
Honored Contributor III
542 Views

>>Finding an object in the cache updates it's last used timestamp.

So the location in the cache is not the determining factor for LRU-ed-ness. This will require the eviction to scan the list. It also has the benefit that if you store {timestamp, node*} that you can use DCAS to assure that the LRU entry you find on search, is indeed the entry you evict from the cache (multiple threads perform insert and find the same entry to evict).

I imagine that the "find candidate for eviction" also checks the refcounter and avoids eviction of entry with referenced entry.

Jim Dempsey

0 Kudos
MLema2
New Contributor I
542 Views

Indeed..  Our structure has two maps.  one for forward lookups (find) and one for backward lookups (eviction based on time stamp).  For this reason only, we cannot implement it using lock free CAS.  Unless you have a better ides ;)

Mike

0 Kudos
jimdempseyatthecove
Honored Contributor III
542 Views

I suggest you use one map, a circular buffer, search one way for lookups, the other way for eviction.

Assume a vector of {timestamp, node*}

Search vector for empty or oldest keeping timestamp found (or 0)
Obtain atomic copy of that {timestamp,node*}
if(timestamp of copy != what you found in your search for oldest (or 0 for empty)) cycle
if( !DCAS(&yourVector[iFound], {now(),newNode}, copyOfPriorOldest)) cycle
// insert success

For updating timestamp if( !DCAS(&yourVector[iFound], {now(),oldNode}, copyOfPriorOldNodeEntry)) cycle

Avoid lock (mutex) if at all possible. A premption of the holding thread at an inappropriate time would block subsequent threads through preemption time.

Jim Dempsey

0 Kudos
Reply