Hacker News Reader

Comment by kabdib | Hacker News Reader

The "two star" solution looks like it generates more memory traffic in the case of many deletions, and may run afoul of load-hit-store performance problems on some platforms, since the write to '*curr' in the remove case may still be in flight on its subsequent read and cause a pipeline stall.

Then again, the 'rm' predicate may dominate, or removes may be infrequent, and then who cares? Or your CPU may not care about LHS stalls (by virtue of being very whizzy, or just so terrible that the optimization doesn't matter).

Which is to say, measure and be prepared to be flexible rather than statically clever.

View on HN

Yup, potential performance issues were the first things that came to my mind on seeing that code too. Plus, it's just silly to say that someone that just wrote a linked list doesn't understand pointers - pretty much by definition they do understand pointers, otherwise their linked list isn't going to work.

My personal rule of thumb concerning pointers is that two-stars should never be seen except in the case where you want a function to be able to modify a pointer that was passed in as a parameter. That's it. If I get handled a module that has two-stars in it under any other circumstance, I refactor it. I do this because:

a) lots of people find it difficult to thing about pointers to pointers (although I've never understood why empirically I note that this is the case).

b) Having to dereference two pointers to get to the information that you want is not just slow because of extra work needing to be done, but also because you've just increased the need for doing a page change in memory, which on some architectures can be surprisingly expensive.

Where does the double dereference come from in the second case? curr->next and (* curr) both perform a dereference. (If anything, (* curr) will be at least as efficient, if not more, because there's guaranteed to be no offset.)

(Does anybody know how you type an asterisk?)

Most CPU architectures offer special optimised instructions for grabbing data in a structure - it's done as an offset from the base pointer. A double star dereference can not benefit from this optimisation.

I think there are the same number of dereferences in both cases? One to fetch the next pointer, and one to update the previous next pointer if a removal is required.

You could probably make the second bit of code worse by not holding the value of star curr in entry.

* * curr

Unfortunately the spaces seem to be unavoidable.

> 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.

If you're using a linked list you've already lost the battle against lhs.

Reply on news.ycombinator.com