[cs631apue] Data structure implementations in <sys/queue.h>

Benjamin Iofel biofel at stevens.edu
Tue Sep 4 17:32:39 EDT 2018


On Mon, Sep 3, 2018 at 10:42 PM, Jan Schaumann <jschauma at stevens.edu> wrote:

> Ramana Nagasamudram <rnagasam at stevens.edu> wrote:
>
> > Could anyone help me understand exactly how this can be more efficient
> > than the alternative?
>
> I have never looked at this in detail, but my guess is:
>
> By not including a reference to the object, you can more easily allocate
> the data structures and align them at compile time.  Note: the
> implementation is (almost?) entirely  in macros, so the code is inserted
> as is at compile time.  By not including a pointer to the object, and
> instead requiring the object to contain the list head struct, you also
> yield branchless insertion/deletion in the list: any object can
> dereference the next item in the list without having to check the
> reference on the object.


How is it branchless? You still have to check whether the next pointer is
null.


> The lack of pointers to the object within the list structure ought to
> make memory allocation more efficient, which for the purposes of the
> slist per the header comments and queue(3) description is desirable.
>
>
I think this is the only advantage. Instead of 2 memory allocations (the
sl_node and the datum), you just need 1.

-- Ben Iofel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.stevens.edu/pipermail/cs631apue/attachments/20180904/552dd6ec/attachment.html>


More information about the cs631apue mailing list