patternMinor
Is there a term for the general method used in XORed linked list?
Viewed 0 times
themethodusedtermgeneralforxoredlisttherelinked
Problem
The XOR linked list is perhaps the most prominent example of storing a reversible hash of two values and using a known value and the stored hash value to derive the other value. Is there a term for the general mechanism (or a way to describe it very concisely)?
As a related question, are there other somewhat recognized examples of using this mechanism?
In informally studying computer architecture, I have encountered what I think are two or three examples. One was a suggestion for a MRU-based cache way predictor by XORing the MRU bit with a bit derived from the address; the derived bit is the "known" value. The other was a similar, XORing the hysteresis bit of a branch predictor with a bit derived from branch information. A possible third example might be the agree branch predictor which uses a (possibly static) per-branch prediction to bias entries in a dynamic predictor so that aliasing tends to be non-destructive. A confirmation that these actually should be recognized as the same general mechanism as used by the XOR linked list would also be helpful.
As a related question, are there other somewhat recognized examples of using this mechanism?
In informally studying computer architecture, I have encountered what I think are two or three examples. One was a suggestion for a MRU-based cache way predictor by XORing the MRU bit with a bit derived from the address; the derived bit is the "known" value. The other was a similar, XORing the hysteresis bit of a branch predictor with a bit derived from branch information. A possible third example might be the agree branch predictor which uses a (possibly static) per-branch prediction to bias entries in a dynamic predictor so that aliasing tends to be non-destructive. A confirmation that these actually should be recognized as the same general mechanism as used by the XOR linked list would also be helpful.
Solution
It is a typical example of a space-time tradeoff trading increased time (CPU instructions required) for decreased space (memory required). There are many examples of this.
In this particular case I'd say it is a (simple) form of lossless compression. This because the data is stored in a minified but unusable form and needs some computation (decompression) done to receive the original (and usable) form, but no information is lost.
In this particular case I'd say it is a (simple) form of lossless compression. This because the data is stored in a minified but unusable form and needs some computation (decompression) done to receive the original (and usable) form, but no information is lost.
Context
StackExchange Computer Science Q#9284, answer score: 3
Revisions (0)
No revisions yet.