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.
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...
