[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Re: in which we present an ugly hack to make sys/queue.h CIRCLEQ work
On 20 Nov, 2013, at 16:01 , Ken Hornstein <kenh%cmf.nrl.navy.mil@localhost>
>> 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
> #define CIRCLEQ_PREV(elm,field) ((elm)->field.cqe_prev)
> #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
> 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.
Main Index |
Thread Index |