4 ms·

> So we've seen that this works, but why would anyone think to do this in the first place? The Power of Two Random Choices: A Survey of Techniques and Results b

> So we've seen that this works, but why would anyone think to do this in the first place? The Power of Two Random Choices: A Survey of Techniques and Results by Mitzenmacher, Richa, and Sitaraman has a great explanation. The mathematical intuition is that if we (randomly) throw n balls into n bins, the maximum number of balls in any bin is O(log n / log log n) with high probability, which is pretty much just O(log n). But if (instead of choosing randomly) we choose the least loaded of k random bins, the maximum is O(log log n / log k) with high probability, i.e., even with two random choices, it's basically O(log log n) and each additional choice only reduces the load by a constant factor. This sounds very powerful! And intuitively doesn't make any sense to me. So, say I have n choices, I do not know which choice is better. Does this result say that it's more efficient to randomly choose k and find the best among them (even for k=2), instead of randomly choosing a single choice? Could someone point me in the right direction?

aidenn0 3y ago
> This sounds very powerful! And intuitively doesn't make any sense to me. So, say I have n choices, I do not know which choice is better. Does this result say that it's more efficient to randomly choose k and find the best among them (even for k=2), instead of randomly choosing a single choice? Could someone point me in the right direction? Yes, let's consider the k=2 vs selecting a random item from a set of N items: Selecting one item uniformly randomly from a set of N is identical to selecting two distinct items and then picking one of those two uniformly randomly. So if you select items A and B, then pick the best item, you end up with an item of MAX(A,B) utility instead of MEAN(A,B) utility. MAX(A,B) >= MEAN(A,B) should hopefully be obvious.
- girvo 3y ago
  You've explained that wonderfully, thank you! I'm not the original commenter, but was also confused by my intuition here. That makes a lot more sense now :)
  - waynesonfire 3y ago
    It didnt make any sense to me. I think an intuitive perspective is that if you pick one item randomly, you cant use the LRU signal. So, you pick two items. Now you get to also use LRU. Notice that it doesnt add any value to pick three random items and then apply LRU.
    - aidenn0 3y ago
      > Notice that it doesnt add any value to pick three random items and then apply LRU. It actually does. The more items you pick, the better it works, because at the ultimate stage of k=N you will always be picking the best item. For a lot of real-world distributions, there are rapidly diminishing returns with higher k, but the returns are still there. [edit] The same example as above works for k=3, observing that discarding one of the 3 chosen uniformly randomly devolves to the k=2 form. k=3: MAX(A,B,C) k=2: MEAN(MAX(A,B),MAX(B,C),MAX(A,C)) k=1:
      - waynesonfire 3y ago
        If you think you need a better K, because you have insight into your distribtution, then don't use uniform, instead, use something more appropriate. When k=N you degrade to LRU. Your MAX / MEAN logic is completely flawed. If k=N then you'd have MAX(0..N), wouldn't this be optimal? But, this is LRU and it's not optimal. All this is hand-waving. The proper response is to use the language of mathematics to prove how this algorithm behaves. Perhaps there is an optimal k.
        aidenn0 3y ago
        I didn't realize we had moved on to talking about cache-replacement rather than putting balls in buckets. For putting balls in buckets (or any case where it is possible to compare options and come out with a "best" then k=N is optimal. For cache-replacement strategies, you can prove very little for the general case, since for any two reasonable replacement strategies, there is usually an access pattern that favors one over the other. When TFA says "Random and FIFO are both strictly worse than either LRU or 2-random" the context is in running SPEC CPU with an 8-way associative cache. It's not hard to come up with artificial benchmarks that invert that relationship. Also TFA contradicts your earlier assertion that k=3 is not better than k=2, at least when used with a pseudo-LRU: "Also, we can see that pseudo 3-random is substantially better than pseudo 2-random, which indicates that k-random is probably an improvement over 2-random for the k."
- mjevans 3y ago
  Random numbers sound possibly expensive for 'small' caches. Though I /offhand/ I guess if there's a hardware RNG source it doesn't need to be cryptographically secure or trusted as long as it's fast for this task. Similarly if updates are bursty an idle cull could use a bitvector to mark free slots within a fixed array for rather low overhead and a burst of speedy inserts when load picks up. Something close is probably already necessary overhead for when the cache isn't yet populated.

aidenn0 3y ago

> This sounds very powerful! And intuitively doesn't make any sense to me. So, say I have n choices, I do not know which choice is better. Does this result say that it's more efficient to randomly choose k and find the best among them (even for k=2), instead of randomly choosing a single choice? Could someone point me in the right direction? Yes, let's consider the k=2 vs selecting a random item from a set of N items: Selecting one item uniformly randomly from a set of N is identical to selecting two distinct items and then picking one of those two uniformly randomly. So if you select items A and B, then pick the best item, you end up with an item of MAX(A,B) utility instead of MEAN(A,B) utility. MAX(A,B) >= MEAN(A,B) should hopefully be obvious.

girvo 3y ago
You've explained that wonderfully, thank you! I'm not the original commenter, but was also confused by my intuition here. That makes a lot more sense now :)
- waynesonfire 3y ago
  It didnt make any sense to me. I think an intuitive perspective is that if you pick one item randomly, you cant use the LRU signal. So, you pick two items. Now you get to also use LRU. Notice that it doesnt add any value to pick three random items and then apply LRU.
  - aidenn0 3y ago
    > Notice that it doesnt add any value to pick three random items and then apply LRU. It actually does. The more items you pick, the better it works, because at the ultimate stage of k=N you will always be picking the best item. For a lot of real-world distributions, there are rapidly diminishing returns with higher k, but the returns are still there. [edit] The same example as above works for k=3, observing that discarding one of the 3 chosen uniformly randomly devolves to the k=2 form. k=3: MAX(A,B,C) k=2: MEAN(MAX(A,B),MAX(B,C),MAX(A,C)) k=1:
    - waynesonfire 3y ago
      If you think you need a better K, because you have insight into your distribtution, then don't use uniform, instead, use something more appropriate. When k=N you degrade to LRU. Your MAX / MEAN logic is completely flawed. If k=N then you'd have MAX(0..N), wouldn't this be optimal? But, this is LRU and it's not optimal. All this is hand-waving. The proper response is to use the language of mathematics to prove how this algorithm behaves. Perhaps there is an optimal k.
      - aidenn0 3y ago
        I didn't realize we had moved on to talking about cache-replacement rather than putting balls in buckets. For putting balls in buckets (or any case where it is possible to compare options and come out with a "best" then k=N is optimal. For cache-replacement strategies, you can prove very little for the general case, since for any two reasonable replacement strategies, there is usually an access pattern that favors one over the other. When TFA says "Random and FIFO are both strictly worse than either LRU or 2-random" the context is in running SPEC CPU with an 8-way associative cache. It's not hard to come up with artificial benchmarks that invert that relationship. Also TFA contradicts your earlier assertion that k=3 is not better than k=2, at least when used with a pseudo-LRU: "Also, we can see that pseudo 3-random is substantially better than pseudo 2-random, which indicates that k-random is probably an improvement over 2-random for the k."
mjevans 3y ago
Random numbers sound possibly expensive for 'small' caches. Though I /offhand/ I guess if there's a hardware RNG source it doesn't need to be cryptographically secure or trusted as long as it's fast for this task. Similarly if updates are bursty an idle cull could use a bitvector to mark free slots within a fixed array for rather low overhead and a burst of speedy inserts when load picks up. Something close is probably already necessary overhead for when the cache isn't yet populated.