6
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ I'd share it under the premature optimization anti-pattern. Memory nowadays is a lot cheaper than in the early days of computing when most of these tricks were invented. I know of two examples: the XOR swap (en.wikipedia.org/wiki/…) and maybe Complex numbers (as they can be represented by both two real parts and a magnitude+angle) $\endgroup$
    – dtech
    Jan 30, 2013 at 0:22
  • 2
    $\begingroup$ While memory capacity in PCs and servers is relatively vast, there is still interest in dense representations because of bandwidth and cache capacity. Computation vs. communication (and storage) tradeoffs increasingly favor computation. Also some embedded systems and some hardware data structures (like branch predictors) can be more capacity constrained. While XOR linked lists may now be almost entirely a historical footnote, the general mechanism may have significant albeit highly constrained application within the broad field of computing. $\endgroup$
    – Paul A. Clayton
    Jan 30, 2013 at 17:24
  • $\begingroup$ While true, I think that in most cases you mention general or special purpose compression does a better job. The only valid use case I can think of the very hardware-limited ones you mentioned. For bandwith and cache capacity I'd bet that a gzip'ed serialisation of a generic DLL (e.g.) is smaller than the uncompressed/gzipped serialisation of a XOR DLL. $\endgroup$
    – dtech
    Jan 30, 2013 at 19:02
  • 1
    $\begingroup$ “Is there a term for the general mechanism?” I think that it is called XOR. $\endgroup$
    – Tsuyoshi Ito
    Jan 30, 2013 at 19:07
  • $\begingroup$ @TsuyoshiIto I think this question can be reworded as "is there a generalization of the xor technique in xor linked lists". $\endgroup$
    – Realz Slaw
    Nov 22, 2013 at 16:18

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\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.