Heap for tracking least used page

I have been working on code for tracking least the used page in a cache of pages, and this is the result: Heap in rustdb::pstore - Rust ( source: pstore.rs - source ).

It is a heap where the sorting key (the number of times a page has been used) can be modified efficiently, and when the cache is full ( reaches a configured limit ), the copy of the least used page is removed from the cache.

It took me quite a while to reach this solution (a lot of trial and error), so I would be interested in what you think of it, also suggestions for improvement. Previously I was using a BTreeSet, (see here: pstore.rs - source ) but I think my new solution should be significantly more efficient.

I'm confused as to how this can work without the modify method needing a callback to communicate when it's modifying the index of existing pages. Sorry if I'm misinterpreting--I didn't read all the code in detail. But when I implemented a similar "heap with ability to change element value" structure before, when you change the value of an element, and it repeatedly swaps it with its parent / child until the heap invariants are satisfied again, that results in it changing the indexes of those elements. And so I had to add to the method a "on element index changed" callback of trait FnMut(&T, usize, usize) (element, old index, and new index) which the caller would use to update the indexes it's storing in its own data structures.

1 Like

Well that is the cunning part. I have an extra level of indirection, the heap nodes do not move (which allows modification), instead the position of the node in the heap is stored in the node (pos), and also the index of the node for a given heap position is stored (x). Modify does call either move_up or move_down which restores the heap invariant.

Oh yeah that makes sense. Well I mean yeah the data structure makes sense to me. There's a couple things you could do if you wanted to optimize it even more I suppose but not without a cost to complexity.

Do say if you have any ideas! I have one minor idea, to pass cx and px into move_up and move-down to avoid some vec index operations.

Ok! Well, removing the additional layer of indirection, and thus requiring the caller to be able to update their own indexes into it, like I mentioned earlier, would of course remove a layer of indirection which could improve performance in some memory bound cases. Changing the u64 to something smaller could also improve performance in some memory bound cases. If you wanted to get fancy you could possibly store a logarithm of the actual usage number so that you get decent approximate relative comparisons in a more scale invariant way while using a small number of bits, similar to how floats work. As for further memory bound optimizations, I wonder if there's some funny way to introduce some concept of blocks into a max heap to improve cache locality in cases with large quantities of values. Something abstractly analogous to the jump from a naive binary search tree to a b-tree perhaps. It could be something worth thinking about.

The caller page is shared between threads, so access is relatively expensive requiring a Mutex lock, so I think the layer of indirection is needed.

The usage numbers, I had thought about that, I think I could put a limit on them and use just 16 bit unsigned integers, when the limit is reached, it is simply not increased any more. I don't see how logarithms could work though.

Also, the heap size (and indexes into it) could probably be limited to 16 bits, since cache pages are ~16kb, and 64k x 16kb = ~1GB, which is a reasonable upper limit for cache size. A cache limit of (say) 10MB would be typical and reasonable.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.