13
\$\begingroup\$

This is the followup challenge from this one, if you're confused please check that one out first.


First, let \$m(s, k)\$ be the number of cache misses a sequence \$s\$ of resource accesses would have assuming our cache has capacity \$k\$ and uses a first-in-first-out (FIFO) ejection scheme when it is full.

Then given a ratio \$r > 1\$, return a non-empty sequence of resources accesses \$s\$ such that there exists \$k > j\$ with \$m(s, k) \geq r \cdot m(s, j)\$.

In plain English, construct a sequence \$s\$ of resource accesses so that there's two cache sizes where the bigger cache has (at least) \$r\$ times more cache misses when used to resolve \$s\$.

An example for \$r = 1.1\$, a valid output is the sequence \$(3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4)\$, as it causes \$9\$ cache misses for a cache size of \$3\$, but \$10\$ misses for a cache size of \$4\$.

It doesn't matter what sequence you return, as long as it meets the requirements.


Shortest code in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Background reading: Bélády's anomaly \$\endgroup\$ – dylnan Jun 23 '18 at 22:26
  • \$\begingroup\$ Might just be the exhaustion, but this challenge isn't entirely clear to me; could you provide a worked example and a couple more test cases? \$\endgroup\$ – Shaggy Jun 23 '18 at 22:56
  • \$\begingroup\$ @Shaggy Go check out the other challenge, and the background reading from the other comment. The crux is that a FIFO cache can get worse as it becomes bigger for some series of requests. \$\endgroup\$ – orlp Jun 23 '18 at 23:08
7
\$\begingroup\$

Wolfram Language (Mathematica), 124 113 101 bytes

Flatten@{s=⌈2#⌉;q=Range[r=2s+1];g=Mod[q s-s,r];{Sort@g[[#+1;;]],g[[;;#]]}&~Array~r,Table[q,s^3]}&

Try it online!

NOTE: The TIO output is not the actual list because it would be very long. The wrapper function on TIO tells you the number of page faults for two cache capacities.

For the actual list: Try it online!

Related: arXiv:1003.1336

How?

Let's assume a situation where we have two cache capacities, 3 and 4.

Also, let's say the 3-cache has {4, 2, 5} paged, and 4-cache has {5, 4, 3, 2} paged. Then, let's try paging {1, 2, 3, 4, 5, 1, 2, 3, 4, 5}:

page  3-cache   4-cache
      {4,2,5}  {5,4,3,2}
  1   {1,4,2}  {1,5,4,3}
  2   {1,4,2}  {2,1,5,4}
  3   {3,1,4}  {3,2,1,5}
  4   {3,1,4}  {4,3,2,1}
  5   {5,3,1}  {5,4,3,2}
  1   {5,3,1}  {1,5,4,3}
  2   {2,5,3}  {2,1,5,4}
  3   {2,5,3}  {3,2,1,5}
  4   {4,2,5}  {4,3,2,1}
  5   {4,2,5}  {5,4,3,2}

The 3-cache had 5 page faults, while the 4-cache had 10. We also returned to our original state.

Here, if we repeat paging {1, 2, 3, 4, 5}, we would asymptotically reach the ratio of 2.

We can extend this phenomenon to higher cache capacities so that we can page {1, 2, 3, ... , 2n + 1} and end up with any ratio.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.