4 ms·

The only example I can think of I've seen released code is the "xor linked list" trick, where each node of a link list stores "neighbours = prev xor next" (rath

The only example I can think of I've seen released code is the "xor linked list" trick, where each node of a link list stores "neighbours = prev xor next" (rather than pointers to the 'next' and 'prev' thing in the list). The idea is this lets you iterate up and down the linked list, as if you have prev, you can do "neighbours xor prev" to get next, and "neighbours xor next" to get prev. However, while in that particular program that did create a notable speed improvement and memory saving, I think it's probably worth sacrificing to the greater good.

ATsch 5y ago
In general the primary reason for using doubly linked lists, despite their terrible cache behaviour, is that they are the only data structure that is very easy to write in C. So I'm not sure how much that is going to be an issue in Rust where it is much easier to use other data structures that perform significantly better in practice anyway.
- tialaramex 5y ago
  That "terrible" cache behaviour is what you actually wanted for some concurrency problems, because if code on several physical CPUs or cores all tries to access the same region of memory that's going to be very slow, while unrelated memory will get cached locally by each CPU/ core. That's not why Joe Junior's first C program has a linked list in it. But it might well be why Joe Senior's masterpiece Rust program has a linked list in it. On the other hand, depending on the algorithm being implemented, it may only be singly linked, and the XOR trick doesn't apply. Rust's alloc (the library you get if you have an allocator, but not necessarily the entire OS environment) does provide a linked list if you want one, and this would be a reasonable choice in this case whereas it warns you that you probably wanted Vec if you're not sure which data structure you need.
  - ATsch 5y ago
    This is true, but the concurrent work stealing queues and such that are commonly used for such purposes aren't usually textbook C-style linked lists. They (at least in the case of Crossbeam, don't have experience with others) allocate smaller contiguous blocks of items which are then linked together with pointers. This reduces overhead a lot more than the xor trick does while also improving cache behaviour. Also as you mentioned they're already only singly linked in the first place.
zozbot234 5y ago
I think this would work well with the model as described in the article, since for every list operation you're assumed to be starting from an actual pointer to some list element, which you can use to endow the recomputed addresses with the right provenance component.
- CJefferson 5y ago
  If each element of the linked list has a different provenance, then I think you are out of luck. I could allocate the whole list in a single giant block, but that feels like it defeats the purpose -- now I'm just allocating every object in my program in one giant allocation.
  - Gankra 5y ago
    Yeah "it's actually xoring array indices" is the standard solution Or you can go Deep on memory models and try to apply Ralf's Xor Provenance Hack and claim that, well, provenance is stored in bytes, but it doesn't have to be a pointer-sized range of bytes, so let me have some horrible way to express "the high half has provenance 1, the low half has provenance 2" and handwave magic problem solved. This is of course horrible and also not at all a portable notion to CHERI which tracks provenance at the granularity of "aligned pointer-sized region of memory". But hey, if it helps you sleep at night.
    - CJefferson 5y ago
      I'm personally excited by CHERI, and feel it is part of (sorry if these words annoy some people) computing "growing up". It's interesting (to me at least) that that is the only trick I can think of (along with general pointer compression tricks, like interpreters storing 63-bit integers when a pointers last bit is set to 1), where CHERI shouldn't be (fairly) trivial to support. I'm happy to sacrific xoring pointers, the same way I wouldn't use some "cunning trick" to build my house with half as many nails, at the risk that any minor mistake installing any of those nails would lead to my house failing over.
      - 5y ago

ATsch 5y ago

In general the primary reason for using doubly linked lists, despite their terrible cache behaviour, is that they are the only data structure that is very easy to write in C. So I'm not sure how much that is going to be an issue in Rust where it is much easier to use other data structures that perform significantly better in practice anyway.

tialaramex 5y ago
That "terrible" cache behaviour is what you actually wanted for some concurrency problems, because if code on several physical CPUs or cores all tries to access the same region of memory that's going to be very slow, while unrelated memory will get cached locally by each CPU/ core. That's not why Joe Junior's first C program has a linked list in it. But it might well be why Joe Senior's masterpiece Rust program has a linked list in it. On the other hand, depending on the algorithm being implemented, it may only be singly linked, and the XOR trick doesn't apply. Rust's alloc (the library you get if you have an allocator, but not necessarily the entire OS environment) does provide a linked list if you want one, and this would be a reasonable choice in this case whereas it warns you that you probably wanted Vec if you're not sure which data structure you need.
- ATsch 5y ago
  This is true, but the concurrent work stealing queues and such that are commonly used for such purposes aren't usually textbook C-style linked lists. They (at least in the case of Crossbeam, don't have experience with others) allocate smaller contiguous blocks of items which are then linked together with pointers. This reduces overhead a lot more than the xor trick does while also improving cache behaviour. Also as you mentioned they're already only singly linked in the first place.

zozbot234 5y ago

I think this would work well with the model as described in the article, since for every list operation you're assumed to be starting from an actual pointer to some list element, which you can use to endow the recomputed addresses with the right provenance component.

CJefferson 5y ago
If each element of the linked list has a different provenance, then I think you are out of luck. I could allocate the whole list in a single giant block, but that feels like it defeats the purpose -- now I'm just allocating every object in my program in one giant allocation.
- Gankra 5y ago
  Yeah "it's actually xoring array indices" is the standard solution Or you can go Deep on memory models and try to apply Ralf's Xor Provenance Hack and claim that, well, provenance is stored in bytes, but it doesn't have to be a pointer-sized range of bytes, so let me have some horrible way to express "the high half has provenance 1, the low half has provenance 2" and handwave magic problem solved. This is of course horrible and also not at all a portable notion to CHERI which tracks provenance at the granularity of "aligned pointer-sized region of memory". But hey, if it helps you sleep at night.
  - CJefferson 5y ago
    I'm personally excited by CHERI, and feel it is part of (sorry if these words annoy some people) computing "growing up". It's interesting (to me at least) that that is the only trick I can think of (along with general pointer compression tricks, like interpreters storing 63-bit integers when a pointers last bit is set to 1), where CHERI shouldn't be (fairly) trivial to support. I'm happy to sacrific xoring pointers, the same way I wouldn't use some "cunning trick" to build my house with half as many nails, at the risk that any minor mistake installing any of those nails would lead to my house failing over.
    - 5y ago