I feel for Vika, listening to boring meaningless fashion talks must be really painful. I wish her to find better friends, with whom she could enjoy fun and exciting conversations about strings, arrays, stacks and graphs, so that she doesn't need to hide from them anymore.

I did a few experiments running a loop for $$$10^9$$$ iterations, looks like performance depends on compiler optimizations. If no optimizations used at all, then ranges perform quite slow, however if you turn on some optimizations, then the difference with regular loop becomes really insignificant.

No optimizations (-O0):

for loop regular: 2023ms
for loop views::iota: 6070ms
for loop views::iota | views::reverse: 18875ms

Using -O2 optimizations:

for loop regular: 449ms
for loop views::iota: 451ms
for loop views::iota | views::reverse: 468ms

Using -O3 optimizations:

for loop regular: 247ms
for loop views::iota: 246ms
for loop views::iota | views::reverse: 299ms

Using C++20:

#include <ranges>

vector v = {1, 2, 3, 4};
for (int x: v | views::reverse) 
  cout << x << ' ';

// or
for (int x: views::iota(1, 5) | views::reverse) 
  cout << x << ' ';

I would call them also "chains", basically just a sequence of connected nodes a — b — c — d ...

I don’t know how to generate, but you can use some real workload traces (for example see list of them here https://github.com/sylab/cacheus)

kinda-persistent wrapper of set and vector

Sounds a bit magical ) You still need to reorder all current items in set when switching, don't you?

Thanks for explanation )

I haven't thought about having only one real strategy and rebuilding it when switching. Though in worst case, if switching strategies on every request, it could perform worse than if keeping real copies for each strategy, but in reality you probably don't need to switch them so often. So it could be faster... depending how often you switch.

And thanks a lot for sharing the code, I'll look into it more deeply a bit later. (from the first look it looks less messy than mine ))

For LRU, where you can insert items only to the end, I know that you can use just double linked list + hashtable. So all operations will be in O(1). But for other ordering criteria you need something more complicated/slow.

Hmm, well as you can see from my color, I have very vague understanding of segment trees for now )) Is it really faster than a regular set? You can get minimal element from it in O(1) and delete/reinsert it back in O(logN). Considering priority_queue — I'm not sure, why you might need same page multiple times there, but the main disadvantage of it for me (at least standard implementation) was that it seems impossible to delete an item from the middle from it (correct me if I'm wrong).

Updated: Ahhh, probably understood, you meant instead of deleting item from pq, just inserting same page multiple times there.... okay. So will it be faster than a set?

why not both

Well, in my case because, I was limited by only 2-3 different strategies because of probably not very optimal implementation. Can you share how many strategies you had running concurrently in total (assuming there should 2 copies of each, right?)?

Basically the LFU question arose because people are using freely the same term LFU, that in fact could mean quite different things for different people. And often implementation details could separate top 10 from top 100.

Another half of them is quite uplifting though )

I wonder which data structures did you use for keeping LRU/LFU/… items ordered? I used regular STL set, though probably my solution was not very optimized, I felt like having more than 2-3 strategies running concurrently could risk in exceeding allowed time limit. As I understand for each strategy there should be 2 copies of it: 1st — simulated/virtual/shadow, which runs as if it was the only one strategy used, 2nd — real/actual copy, that has same shared items among all real strategies. So introducing an additional strategy would require 2x additional time. (Please, correct me if I’m wrong and only one copy of a strategy is enough)

Another small question is about LFU, which is often mentioned. Did you calculate frequencies only while item was in cache or even after it was evicted (total frequencies)? And if you ordered items first by frequency and second by time accessed, as there could be multiple items having similar frequencies, especially low ones. In that case seems like a better name would be like LFRU not just LFU.

Taking the best one for each test case is enough

Just to clarify, did you select the best one for each test case per tenant or used same strategy for all tenants in that TC? And did you decide which one is best once at some point or did you continuously/periodically adjust which one is the best along the way?

It depends not only on your number of page faults, but also on number of faults in the base solution (LRU). So if your SLA matches base answer, which is most likely also 10, you’ll get Cost=0 and Score=500

I'm a bit confused with score calculation. A quote from description:

The value $$$SLA_t^{base}$$$ indicates the number of page faults obtained by using the LRU algorithm when the buffer size of tenant $$$t$$$ is $$$Q_t^{base}$$$

Doesn't this mean that if I will use LRU with buffer of size $$$Q_t^{base}$$$ I should get $$$Cost_j=0$$$ and as a result $$$Score_j=500$$$ for all tests? Or $$$\sum Q_t^{base} \gt Q$$$ and it is impossible to have buffer of size $$$Q_t^{base}$$$ for all tenants? But then, if there is no upper bound on $$$\sum Q_t^{base}$$$, they could be arbitrary large to fit whole database for every tenant and then LRU or any other cache eviction strategy just doesn't make sense.

Try testcase:

1
3
0 0
0 0
1 1

Correct answer should be 1

А что с Preventing Alzheimer's делать? Кроме перебора, что-то ничего не придумалось (( Но это долго...