The Tower of Weakenings: Memory Models for Everyone

Re:The Tower of Weakenings: Memory Models for Everyone by tialaramex on Wednesday April 06, 2022 @02:40PM (#30935868)

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.

[ Parent | on HN ]

Re:The Tower of Weakenings: Memory Models for Everyone by ATsch on Wednesday April 06, 2022 @03:17PM (#30936347)

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.

[ Parent | on HN ]