It's a good thing that FIFO isn't the only Memory & Cache Replacement Strategy [0]. Way back when, I wrote a Cache Simulator in HTML+JS [1][2]. Hasn't aged well; you used to be able to drag and drop a list a file containing a list of addresses. I ought to clean it up and make it functional again.
I've sometimes wondered if a Cache Line Size-aware Strategy could significantly improve Garbage Collection. I've mentally toyed with the idea of a Linked List of bitmaps of Arenas (made of Cache Line Sized chunks) with a Reference Counter bitlist could improve GC performance. It could even be extended for use in non-OOP languages with the GCC RAII Cleanup Extension [3], even for primitive and other non-OOP types.
Maybe it's 4am and I ought to sleep, but I'm having trouble understanding this article.
Is this phenomenon the same reason some PC game engines render objects in alternating reverse order each frame, rather than something theoretically more optimal like depth-sorted? I understand that in the case of 3D graphics if the textures don't fit in the GPUs memory, FIFO ordering will cause ALL textures to be ejected every frame as you cycle through the same objects in the same order, whereas reversing the order every frame means just the same batch of overflow textures "at the end" will get ejected every other frame.
As I understand it, it is not the same phenomena. Because in your case increasing the number of texture that the GPU can hold won't increase the number of page faults. The number of texture to re-fetch will stay the same (i.e. all of them), or best case scenario the entire texture set now fits in the GPU memory and there is no page faults at all.
The anomaly descibed here is that there exist some access patterns that will increase the number of page faults if you increase the number of page the memory can hold (using a FIFO page replacement strategy). Very counter-intuitive, hence the term 'anomaly'.
Edit: thinking about it, I think what you describe is a clever trick to simulate an effective MRU policy when the actual hardware uses LRU (see oso2k first link for the definition of those acronyms).
I've sometimes wondered if a Cache Line Size-aware Strategy could significantly improve Garbage Collection. I've mentally toyed with the idea of a Linked List of bitmaps of Arenas (made of Cache Line Sized chunks) with a Reference Counter bitlist could improve GC performance. It could even be extended for use in non-OOP languages with the GCC RAII Cleanup Extension [3], even for primitive and other non-OOP types.
[0] https://en.m.wikipedia.org/wiki/Cache_replacement_policies
[1] https://github.com/lpsantil/CacheSimulator/blob/master/index...
[2] http://lpsantil.github.io/CacheSimulator/
[3] https://en.wikipedia.org/wiki/Resource_acquisition_is_initia...