On 20 Nov, 2013, at 16:01 , Ken Hornstein <[email protected]> wrote: >> This functionally works, but the TAILQ data structure is not the same as >> the CIRCLEQ data structure (i.e. no ABI compatibility, if that matters; >> I'm not quite sure why it does) and unnecessarily penalizes applications >> which need to traverse the list in the tail->head direction. > > I know the data structures aren't the same, but if you're using the macros > you don't ever notice this. As for the penalty ... you're talking > about: > > #define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev) > > versus > > #define TAILQ_PREV(elm, headname, field) \ > (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) > > One extra pointer dereference is what we're talking about; I have to > believe that for 99% of applications it wouldn't matter.
I think it is actually 2 extra pointer deferences, but the important bit is that one of the pointers is fetched from memory you might not need to read from at all with a CIRCLEQ. On modern processors one cache miss is worth a whole big pile of extra instructions, so doing reads from memory you don't strictly need to touch is about the easiest way to make things go slower. > Also, I see that CIRCLEQ has more complicated logic if you want to > insert elements at the end of it. So obviously there are tradeoffs (but > again, I don't really think it matters to nearly everybody). I don't think an extra instruction or two matters nearly as much as extra reads from unrelated memory. I was unable to measure any difference between the speed of adding something to the end of a TAILQ and adding something to the end of a CIRCLEQ, but I was able to measure a difference between TAILQ_LAST() and CIRCLEQ_LAST() for a list that multiple processors were adding things to. Dennis Ferguson
