an_ko
mananaysiempre
One thing this loses relatively to a conventional doubly linked list is the ability to remove an item while only having its address (or any other iterator pointing to it that is stable across other items being inserted or deleted). And unfortunately that’s often why you’re using a doubly linked list in the first place.
(A less intrinsic flaw is that coding an XOR linked list in strictly conformant C is exceedingly annoying. The standard does not guarantee that equal pointers turn into equal integers upon casting, so you’re forced to make everything into an uintptr_t to, essentially, maintain a canonical integer-cast version.)
AceJohnny2
> The standard does not guarantee that equal pointers turn into equal integers upon casting, so you’re forced to make everything into an uintptr_t to, essentially, maintain a canonical integer-cast version.
Of course! The standard does not guarantee that the size of an int is the same as the size of a pointer, i.e. `sizeof(int) =/= sizeof(int*)`. IIRC, this was the case on some of the PowerPCs I worked on decades ago. Now with x86-64 & Aarch64 having taken over the world (and with saner 32bit on the embedded end) we've almost forgotten the Cambrian explosion of "interesting" word-size machines.
The whole point of the C standard is that it allows implementers flexibility in the sizing of the basic data types, to match a given machine's architecture, with the standard only defining relationships between types (e.g. char <= short <= int <= long). The only surprise is that it took so long for fixed-width types to be standardized (C99).
mananaysiempre
I meant integers in general, not ints specifically. That is to say, the standard does not guarantee that, if p and q are (say) void pointers and p == q, then (uintptr_t)p == (uintptr_t)q. (Neither does it guarantee that, if p == NULL, then (uintptr_t)p == 0, but I digress.) Mere size shenanigans are not enough for things to get that bad. What you need is for there to be multiple ways to represent a pointer to the same place in memory, like on real-mode x86 in the large memory model.
The practical result is, you need to write XOR-linked-list operations something like this:
struct node { uintptr_t link; };
void prepend(uintptr_t head, struct node *n) {
struct node *h = (void *)head;
uintptr_t node = (uintptr_t)(void *)n;
n->link = head ^ h->link;
((struct node *)(void *)h->link)->link ^= head ^ node;
h->link = node;
}
tomsmeding
On modern 64-bit machines, sizeof(int) != sizeof(int*) is very true. But there's probably a significant amount of code that assumes it's equal to sizeof(uint64_t) or sizeof(long). :)
akoboldfrying
True, but if you always keep a pair of adjacent pointers where before you would have kept just the first, efficient deletion and insertion come back. (You could even go the whole hog and encapsulate this pair as a new WidePointer type, with operator++() and operator--() internally operating on both, etc.)
This will likely be a small constant factor slower for some operations, of course, but if you need bidi traversal and node values are small compared to pointers, it's a solid space savings -- and the lower cache utilisation resulting from that savings may even make it a speed win overall.
giovannibonetti
Storage can be further reduced if we think that, with a 64-bit processor, probably a 32-bit address space is enough for most applications (that require less than 4 GB of RAM).
Maybe we can go even deeper with 16-bit near/relative pointers. Perhaps data-oriented design fits well in this situation? With blocks of 64k elements and uint16 indices to address elements inside of them.
nayuki
> with a 64-bit processor, probably a 32-bit address space is enough for most applications
This is related to the Java virtual machine's use of 32-bit "compressed ordinary object pointers (OOPs)" on a 64-bit platform. The pointer is 8-byte-aligned though, so it can address 32 GiB of memory. There is also a non-compressed-OOPs mode that can address more than 32 GiB.
Dylan16807
I see that you're being silly, but the problem is conflating pointers and indices. 16 bit indices are fine. 16 bit pointers are terrible.
Separately, 32 bit pointers are a good optimization in many situations. Java will save lots of space by using 32 bit pointers until you go above 32GB or 64GB or more (depending on what you set as minimum object alignment).
eru
16 bit relative pointers are about as useful/terrible as 16 bit indices.
GuB-42
So essentially, you are using indices rather than pointers.
Indices have advantages: they can be more compact, and they are position-independent. But you need a base pointer, and a bit more computation. It also requires you to have your own allocator, as your typical heap allocator will just give you an arbitrary pointer to your object.
wfn
Re: data-oriented data structures... random (not XOR)...
I have been running multiple iterations of entire ipv4 space port scan. As of now only scanning top 25 used ports (nmap, masscan have toplists). I wanted to be able to do simple data analysis _very_ efficiently time-wise, being OK to sacrifice memory for that.
If you want (time-wise) O(1) item insert (into SORTED btw), fetch, lookup, and port status check to simply be a matter of bitshifting (similarly with counting), then:
1. Bitfield array to store status of up to 32 ports (1 bit for state (open/closed) => 32 bit bitfield)
2. ...that's it. Each scan result is to be found at `bitfields[(unsigned int) ipv4_address]`
In C:
``` // bitfield for port status, for each IP
struct port_field {
bool p1:1;
bool p2:1;
bool p3:1;
bool p4:1;
bool p5:1;
// in C, gotta write it out - of course we could use a macro to generate this
...
bool p32:1;
};This will use 16 GiB of memory for the whole mapped space:
```
#define NUM_IPV4 (unsigned long) 4294967296L
// ...
// sizeof(struct port_field) => 4 bytes
struct port_field *ip_space = calloc(NUM_IPV4, sizeof(struct When scanning (or reading in scan results):
```
in_addr_t u32_ip; // unsigned 32 bit int
struct port_field *p_target_bitfield;
int *p_target_int;
// ... to insert:
if (!(u32_ip = inet_addr(token))) { // `token` is string with actual ip (e.g. from text file)
printf("line %lu: IPv4 address not valid: %s\n", line_count, s_ip);
} else {
p_target_bitfield = &(ip_space[u32_ip]); // unsigned int ipv4 as 'index'
p_target_int = (int *) ((void *) p_target_bitfield); // cast bitfield* to int\*
// set bit at port_index:
*p_target_int = ((1 << port_index) | *p_target_int);
// now, port identified by `port_index` is at `(1 << port_index) | *p_target_int)`
// where `p_target_int` is pointer to port status bitfield cast into signed int32It works - pretty nifty :) i'm sure i could make it much more pretty tho.
But a kind of 'columnar-bitfieldish' in-memory O(1) for everything:)*
Dylan16807
Wouldn't a columnar store be 25 512MB arrays? And that's probably a better layout for doing analysis with.
Also you might as well set the number of addresses to 224<<24.
kjs3
So an 8086 with 64 address pins? Or did I miss the /s?
ted_dunning
If you do this, your garbage collector will hate you.
Or, at least it will decide your data structure is garbage.
DeathArrow
Why would I want to use this trick?
ben-schaaf
To cut down the storage overhead of the linked list. You're saving 8 bytes per element on 64-bit systems.
lmm
> Instead of each node storing the next- and previous-pointers separately, store a single pointer which is the XOR of the two. Which is obviously an invalid pointer. But when iterating, XOR the previous node's pointer with the combined pointer to get the next node's pointer, and so on. You can iterate this way in both directions. Feels illegal. :)
Meh, it's not a pointer, it's not really any different from storing the difference between the two pointers, which obviously would let you iterate in both directions.
timerol
Yes, but as mentioned in TFA, storing the difference would require an extra bit. The difference between two 32 bit numbers is in the range [-2^32 -1, 2^32-1], needing 33 bits to store. The XOR is the same size as the original pointer, simplifying data flow.
But even so, storing a doubly linked list with only pointer differences and no absolute pointers (other than head and tail) feels illegal too
mananaysiempre
> storing the difference [of prev and next pointers] would require an extra [sign] bit [relative to XOR]
No it wouldn’t. Just let wraparound happen normally and things will work out.
Effectively what you need are functions
pair : ptr × ptr → uintptr
left : uintptr × ptr → ptr
right : ptr × uintptr → ptr
left(pair(x, y), y) ≡ x
right(x, pair(x, y)) ≡ y
pair(x, y) = (x + y) mod 2^(width of ptr)
left(p, y) = (p - y) mod 2^(width of ptr)
right(x, p) = (p - x) mod 2^(width of ptr)
atq2119
Uh, no. Assuming 32-bit pointers, you'd add or subtract them using normal unsigned arithmetic which is modulo 2^32. Essentially the same trick definitely works because all these operations (adding/subtracting/xoring a number) are invertible.
The neat thing about xoring with a number is simply that that operation is its own inverse.
Findecanor
One difference between XOR and difference is that because of the symmetry of XOR, you could use the same code for walking the list forwards and backwards.
esafak
Feels like the kind of tricks we pulled in the "640K ought to be enough for anyone" era. I would reserve them for severely constrained devices today.
zero_k
But you forgot! It's also a 3-wise independent linear hashing function! Which means it can be used for probabilistically approximately uniform sampling and counting of solutions to boolean functions. This is super-duper useful. We use it to build counters that give probabilistic, but proven, counts. I explained the idea here in more understandable terms [1].
Basically, it halves the solution space approximately correctly each time. So you keep on adding them, until you have say, 10 solutions. Then you multiply the 10 with 2^k, where k is the number of XORs you added. That's it! So cool, no? And it's super-scalable, because it haves it each time, so you'll get to, say, 10 pretty quick!
Some research papers are here [2,3]. I work on this, the tools are here [4,5]. In the last model counting competition, it dominated all other competitors, when combined with an exact counter, slides of the competition here [6].
[1] https://www.msoos.org/2018/12/how-approximate-model-counting... [2] https://arxiv.org/abs/1306.5726 [3] https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf [4] https://github.com/meelgroup/approxmc [5] https://github.com/meelgroup/unigen [6] https://mccompetition.org/assets/files/2024/MC2024_awards.pd...
wfn
Goddamn, that's just the most sexy use of XOR ever :O omg.
jjice
One of my favorite XOR stories is from Bryan Cantrill (of Oxide, Joyent, and Sun) in this presentation [0] and this video [1].
To avoid clicking a link: When he was at Sun, he was chatting with a coworker (Roger Faulkner) about the lack of logical XOR in C. Faulkner said it was because you couldn't short circuit it, and Brian thought that was wild. Then Roger emailed Dennis Ritchie to ask and he confirmed it was what Faulkner had said.
That stories gets me every time! First of all, it's very funny and well delivered by Cantrill, but it's also just so incredible that they could ask the man himself.
[0] https://speakerdeck.com/bcantrill/oral-tradition-in-software...
wat10000
C does have a logical XOR, it's the `!=` operator. Unlike other logical operators, it requires the arguments to be normalized to a single truth value. It plays nicely with C's convert-to-boolean operator `!!`.
Findecanor
I once failed a a test at a job interview because I hadn't realised that (even after having been programming for twenty years).
penguin_booze
> Faulkner said it was because you couldn't short circuit it
I don't get it. Why is that an impediment to adding an operator? Can some one elaborate?
gblargg
There wouldn't be any advantage to adding a boolean exclusive or operator, unlike with || and &&.
kjs3
DMR was remarkably kind, helpful and accessible. As an undergrad in the mid 80s I read about 'the first' port of Unix (v6) to something other than a PDP-11, the Interdata 8/32. On a whim, I sent an email to dmr@research.att.com (might have even been back as far as research!dmr or dmr@alice.UUCP) asking if there was more info about the architecture as 1) no google and 2) nothing in the uni library. A couple of days later he responded and asked for my (physical) address. A few weeks later, a copy of the instruction set summary manual showed up in my (physical) mailbox. It's IBM 360-ish. Still have it.
snvsn
Topic starts at 37:18
SteveDavis88
[dead]
adrian_b
I strongly dislike the ubiquitous use of the name XOR a.k.a. "exclusive or" for this logical function, because almost always what is meant is "sum modulo 2" a.k.a. "parity", and not "exclusive or".
"Sum modulo 2" a.k.a. "parity" and "exclusive or" are 2 distinct logical functions, which happen to coincide only for the case of 2 input operands (because there exists only a single odd number less than or equal to 2).
For 3 or more input operands, what most people call XOR is actually parity, i.e. the logical function whose value is "1" when an odd number of input operands are "1".
For 3 or more input operands, "exclusive or" is the logical function whose value is "1" only if there exists only a single input operand whose value is "1", while all the other input operands are "0".
For computer hardware, parity is a much more important logical function than "exclusive or" (mainly because addition modulo 2 is used as a building block for implementing addition modulo greater numbers).
On the other hand, in mathematics "exclusive or" is a much more important logical function than parity.
For example, the quantifiers that express that some predicate is true for some elements of a set, for all elements of a set, or for a unique element of a set (like saying that an equation has solutions, or it has no solutions, or it has a unique solution), are based on the logical functions "or", "and" and "exclusive or".
In natural language, "or" always means either "inclusive or" or "exclusive or". It never means parity, i.e. what many programmers call "exclusive or" a.k.a. XOR.
While in programming the "exclusive or" logical function is a function whose computation is seldom needed, it is very frequently used for describing the behavior of a program, e.g. when saying that in a select/case/switch compound statement of some programming language either the 1st statement or the 2nd statement or the 3rd statement or ..., is executed, or when describing the types that the current value of a union/sum typed variable can have.
danbruc
IEC 60617, the standard for electrotechnical symbols, gets that one right - the XOR gate gets labeled with =1, the parity gate with 2k + 1. But when you use circuit design software for PCBs or FPGAs you can still sometimes get bitten because you are getting something different than what you expected.
Tainnor
> On the other hand, in mathematics "exclusive or" is a much more important logical function than parity.
This is called uniqueness quantification and has its own symbol, ∃!
JohnKemeny
> For 3 or more input operands, "exclusive or" is the logical function whose value is "1" only if there exists only a single input operand whose value is "1", while all the other input operands are "0".
Citation needed.
adrian_b
One could easily find quotations in plenty of logic and grammar texts from hundreds of years or even of millennia ago, wherever the meaning of the various words used for "or" is discussed and where the distinction between words expressing "inclusive or" and word expressing "exclusive or" is discussed.
However there is no need for quotations if you know English. English does not have distinct words for "inclusive or" and for "exclusive or", but the context usually allows to differentiate between the 2 meanings and "or" never means parity. Without enough context, "or" more frequently means "exclusive or", which is why people sometimes feel the need to say "and/or" instead of "or", to clearly signal that they mean "inclusive or".
When someone says to you: "This belongs either to Alice or to Bob or to Charlie", do you consider that this sentence would be true if you know that "This belongs to Alice and to Bob and to Charlie" is a true sentence?
That implication would be correct if English "or", when used with the meaning of "exclusive or", would mean the same as what "exclusive or" = XOR means for programmers.
Moreover, even if you accepted that implication, would you be able to claim that in this case your understanding is compatible with "or" having been used to mean "exclusive or" in that sentence? If you believed that implication to be true, what would "inclusive or" mean for you?
I am too lazy to give longer examples, but if you would not understand what "exclusive or" means in a natural language, but you would think that it means the same as in programming, then when someone would utter a compound of e.g. 6 sentences connected by "exclusive or", you would consider the compound to be true when any 3 or any 5 of the component sentences would be true, which is not the intended meaning of "exclusive or", which is that only one of the component sentences is true. Parity is neither "inclusive or" nor "exclusive or", because when "or" is taken to be "inclusive or", any even subset of component sentences may also be true, not only the odd subsets, like for parity.
Tainnor
Mathematics isn't English. You don't wear the ring of integers on your finger, and you can't play football on the field of real numbers.
You're the first person I ever see that pretends to be confused by what XOR means. It means what it means, what is this semantic debate going to do for you?
timdiggerm
This interpretation is covered in the essay.
grahamlee
My handy real-world analogy for XOR is the light over a staircase in a home. There's a switch at the bottom, and another switch at the top, and both control the same light. Initially, they're both in the off position. You set the bottom switch, and the light turns on. You climb the stairs, set the top switch, and the light turns off although both switches are now in the "on" position. As long as one switch is in the "on" position and one switch in the "off" position, the light is on; otherwise, it's off.
jihadjihad
Huh, maybe my electrician wired it up wrong in my office then. I’ve got two switches in the room but come to think of it they perform more like an AND gate than an XOR. In the living room there are two switches and those are definitely like an XOR.
mdnahas
The XOR light switch is a trick. And, even if you know it is possible, it is hard to figure it out without someone telling you. My uncle and cousin were doing their own electrical work and couldn’t figure it out.
I had seen the trick as a young kid and remembered it 30 years later: install the one of the switches backwards.
One switch takes in power and puts it on one of two wires running to the second switch. The second switch connects one of the two wires to the power wire going to the bulb.
If you don’t know the trick, you get an AND switch.
ipython
Ha. TIL that if you XOR the car emoji with 0x20 (ie. you make it "lower case"), you get the "no pedestrian" emoji. It probably won't encode below but this was copied and pasted from tfa. It seems too coincidental to be an accident - anyone who has insight to know whether this was done on purpose?
If you take this too far, you might get strange ideas, like the lower-case version of the car emoji being a ‘no pedestrians’ sign:
>>> chr(ord('') ^ 32)
''mananaysiempre
To satisfy HN’s emoji-stripping comment mangler:
>>> from unicodedata import lookup, name
>>> name(chr(ord(lookup('AUTOMOBILE')) ^ 0x20))
'NO PEDESTRIANS'rzzzt
:tada: → :tophat:
:rocket: → :mountain_cableway:
IncreasePosts
I would think the lowercase of a car would be a go kart
sigbottle
There's also the [kademlia distributed hash table](https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia...). The high level idea is that each node gets a random bit in the range [0, 2^m), and we define the distance to be XOR. We want to find a distributed algorithm to quickly get some information from X to Y, without knowing the whole network.
You can just look at the math and prove that it works, but my pet favorite visual interpretation of the algorithm is this:
Suppose you have a start node X, and it wants to find node k. Define the "X-distance tree" to be a binary tree, with leaf indices 0, 1, 2... But you put labels of X^leaf_index in each node, to represent the distance from a certain label to X. E.g. dist(x, x) = x^x = 0, so the label "X" (the original node) is put at the leftmost leaf (0).
The interval [2^i, 2^(i+1)) is some subtree of the X-distance tree. Let's say you know k's distance belongs in that interval, so you query some node Y in there as an approximate neighbor.
No matter what node Y you pick, the resulting prefix in the Y-distance tree will always be some permutation of the [2^i ,2^(i+1)) subtree we picked from the X-distance tree!
More specifically, my claim is that at the sets labels_of_leaves_of_X( [2^i, 2^(i+1)) ) == labels_of_leaves_of_Y( [0, 2^i) ). (recall that we index by distance, but the labels might be different).
There are far more rigorous comparisons to other DHT's like Chord, both mathematically and empircally. But to me, this visual intuition tells me what the "symmetry" of Kademlia means - sort of everybody's in their own local neighborhood, their own subtrees.
Whereas Chord, even if you implement it bi-directionally (which costs 2x memory! and seems even more treacherous to implement...), can't get this level of 'isolation' in some sense. The neighborhood sliding window of size S is always shifting: per bit, there's always 2^m distinct neighborhoods. Yea, even though most neighborhoods "look the same", it's just not pretty.
Kademlia has 1 + 2 + 4 ... + 2^m-1 neighborhoods, and it's all neat and tidy.
OuterVale
If anyone is wondering, this is the same Simon Tatham as in Simon Tatham's Portable Puzzle Collection. If you're unfamiliar and ever find yourself offline and bored, they're worth checking out.
I know I burnt many hours in high school playing them.
eminence32
And also the same Simon Tatham who wrote PuTTY
dlcarrier
The best part is that the minesweeper algorithm creates games that never requrie guessing.
mdnahas
I emailed the author to correct the section on XOR swap:
Once upon a time, when I was an aggressive young programmer, I tried to show off by replacing this swap:
void swap(int a, int b) { int c = a; a = b; b = c; }
with xor swap:
void swap(int a, int b) { a ^= b; b ^= a; a ^= b; }
and the program broke!
They’re not identical. The program was calling swap on array elements:
swap(&(array[i]), &(array[j]))
The original swap called on a single location did not modify the value. So, my XOR-swap show off introduced a huge bug!
acjohnson55
When I learned Z80 assembly to program my TI-83, every byte of machine code counted, because the whole calculator only had 24k of storage. To initialize the main accumulator register, `a`, to zero, you would do `XOR a` instead of `LD a, 0`. For the math instructions, `a` is an automatic operand, so `XOR a` XORs `a` with itself, and the entire instruction is only 1 byte. To explicitly load 0 into `a` requires the literal 0 to be represented in the opcode, so `LD a, 0` is a 2 byte instruction.
inasio
A lot of custom optimization solvers (e.g. Ising Machines) these days benchmark on XOR problems. It's a bit useless in practice because solving a bunch of XOR clauses can be done in polynomial time with Gaussian elimination, yet the solvers all show exponential scaling, but it works as a good way to gauge performance.
A second interesting implementation concerns the McEliece system. It's a public key cryptocipher from the 70s that is enjoying a renaissance these days due to being quantum-resistant. The decoding attack involves finding a solution to a set of XOR equations (again, polynomial), but where the Hamming distance is equal to some number (given, part of the public key).
antirez
Among binary quantized vectors, similarity is just popcount(XOR of the two vectors) / num_bits. Can be linearly translated to cosine similarity / distance range just multiplying and centering.
My favourite cursed XOR trick that I think wasn't mentioned is XOR doubly-linked lists. https://en.m.wikipedia.org/wiki/XOR_linked_list
Instead of each node storing the next- and previous-pointers separately, store a single pointer which is the XOR of the two. Which is obviously an invalid pointer. But when iterating, XOR the previous node's pointer with the combined pointer to get the next node's pointer, and so on. You can iterate this way in both directions. Feels illegal. :)