> The "two star" solution looks like it generates more memory traffic in the case of many deletions.
It certainly shouldn't. There's no difference at an architectural level between keeping track of prev and keeping track of &prev->next (as should be obvious, because they differ by a constant offset): advancing in the list is just a pointer update via a load either way, and removing a link is just a store.
Since they do the same thing, the opportunity for an LHS stall may be avoided in either approach with a little care.
Before posting the above, I compiled both pieces of code and looked at the assembly output.
Load-hit-stores are one of those pernicious things that bite you a couple times, then you start noticing them. They are indeed "architectural" to a number of processors common in video game consoles, where cycle stealers get a lot of sunlight.
The specific code given in the blog post might encounter a LHS, but it's not endemic to that approach of doing linked-list manipulations via double pointers. They can be avoided just as easily using either approach.
The point I am attempting to make is that the double-pointer is very nearly just syntactic sugar that allows the programmer to avoid special-case handling. Semantically there is very little difference between the two approaches; if they are properly implemented, they perform the same memory operations in the same order, and there is no architectural hazard that is specific to one but not the other.
It certainly shouldn't. There's no difference at an architectural level between keeping track of prev and keeping track of &prev->next (as should be obvious, because they differ by a constant offset): advancing in the list is just a pointer update via a load either way, and removing a link is just a store.
Since they do the same thing, the opportunity for an LHS stall may be avoided in either approach with a little care.