Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The bigger problem with this approach is that you can't remove/erase something from the list just by knowing it's address. This is a key mechanism for most use cases. However, if you're fine with limiting yourself to erasing only during iteration, it's pretty nifty.

I've also done some benchmarks in the past and found it interior iteration performance due to what I'm assuming to be inability to prefetch the next address. However, linked list iteration is already relatively slow so I suppose it's not a big downside.



It's not obvious how prefetching the next address would make things run that much faster - you don't know a given address until you execute the load. That said, there is definitely an extra cycle in your dependency chain to do the XOR, which you might well notice if your linked list is in cache (that extra cycle will show up).

We had a discussion on Twitter about some sort of superfast magic prefetcher that may well have been on the M1 which arguably could shave some cycles off list traversal, and there was a theory that an XOR-list would have been a good negative benchmark to prove/disprove this, but nothing came of it.

The limitation is worse than you say; you can't even navigate from an item just by knowing its address (not just remove/erase something). So any given iterator into this list has to have 2 pointers (say, the item and its predecessor).

It's a weird structure. There's probably almost certainly some peculiar use case for it somewhere, but I've never encountered such a case.


Also, I think this may be the only data structure I have heard of that has an O(1) reverse ordering operation?


Wouldn’t this be achieved by an array and a Boolean flag just as well?


Technically, but I'm not quite sure that's in the spirit of things.


Ha, very nice!

To clarify: to reverse the list, one would only have to swap the HEAD and TAIL pointers of the base structure.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: