Re: in which we present an ugly hack to make sys/queue.h CIRCLEQ work

[Dennis Ferguson <dennis.c.ferguson%gmail.com@localhost>]

On 20 Nov, 2013, at 16:01 , Ken Hornstein <kenh%cmf.nrl.navy.mil@localhost> 
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