News for hackers. Stuff that matters.
Re:XOR Linked List by exDM69 on Friday May 04, 2012 @02:33AM (#3927341)
Never say never. There's a time and place for dirty pointer tricks like the XOR linked list or tagged pointers (low 2-3 bits used for "tags"). Emphasis on words "dirty tricks" so you know that it's the rabbit you pull out of a hat, not something you do every day.

I almost needed XOR linked lists somewhere once, but I ended up doing the same thing with tagged pointers. I wish I remembered the occasion.

But imagine this situation: you're doing some high-perf code on x86's and doing a data structure (with next/prev links somewhere) and your node size is 136 bytes because of arbitrary reason X. You're running a few percent behind your worst competitor in performance figures. Now if you shave 8 bytes you'll fit one node per cache line and probably squeeze out a little pref just by having a cache-friendly alignment. Should you do it? Hell yeah.

Okay, I know many people don't write code with tight performance budgets, but some of us do.

Re:XOR Linked List by ajray on Friday May 04, 2012 @05:37AM (#3927688)
Yeah, there's going to be these trade-offs (complexity/efficiency), but I've seen this end up in fellow student's personal projects after learning it in class.

Aside from that though, I think if you're clever enough to come to this and implement it well, I hope you're clever enough to understand whether or not it's the RightWay(TM).