Rusty Russell's Coding Blog | Stealing From Smart People

Dec/10

12

On C Linked Lists

There are two basic styles of double-linked lists in C; I’ll call them ring style and linear style.

The Linux kernel has ring-style, defined in include/linux/list.h.  You declare a ‘struct list_head’ and everyone who wants to be in the list puts a ‘struct list_head list’ in their structure (struct list_node in CCAN’s version).  This forms a ring of pointers in both the forward and reverse directions.

SAMBA uses linear-style, defined in lib/util/dlinklist.h.  You simply declare a ‘struct foo *’ as your list, and everyone who wants to be in the list puts a ‘struct foo *prev, *next’ in their structure.  This forms a NULL-terminated list in the forward direction (the reverse direction became a ring recently to facilitate tail access).  (Linux’s hlist.h datastructure is similar, only done in list.h style).

Points in favor of ring-style lists:

  1. Insertion and deletion are branchless, as the elements and head are homogeneous:
     head->next->prev = new;
     new->next = head->next;
     new->prev = head;
     head->next = new;

    vs:

    if (!head) {
        new->prev = head = new;
        new->next = NULL;
    } else {
        new->prev = head->prev;
        head->prev = new;
        new->next = head;
        head = new;
    }
  2. list_add, list_del are inline functions, not macros, since the types are known.

Points in favor of linear-style lists:

  1. They’re typesafe, since the head pointer and internal pointers are all the correct type.
  2. Forward iteration is simpler, since the list ends at NULL rather than back at the head. In theory this could free a register, but the bigger difference is that it’s often useful to have NULL in your iterator once the loop is done.
  3. As a corollary, iteration, initialization and emptiness testing don’t need some tricky macros:
      struct foo *head = NULL;
      if (head == NULL) ...
      for (i = head; i; i = i->next) ...
    

    vs

      LIST_HEAD(head);
      if (list_empty(&head)) ...
      list_for_each(i, head, list) ...
    
  4. Uses slightly less space for the head pointer (one pointer, vs two).

So how important is efficiency of insert and delete in a real project?  To provide some data on this, I first annotate the linux kernel so each list.h operation would increment a counter which I could dump out every so often.  Then I booted the kernel on my laptop and ran as normal for three days.

Operation Frequency
Empty Test 45%
Delete 25%
Add 23%
Iterate Start 3.5%
Iterate Next 2.5%
Replace 0.76%
Other Manipulation 0.0072%

Firstly, I was surprised that we add and remove from lists much more than we look through them. On reflection, this makes sense: if lookups are really common we don’t use a linked list. And note how often we check for whether the list is empty: this looks like a “list as a slow path” pattern. I wonder if SAMBA (or other projects) list usage looks the same… anyone?

Secondly, we delete more than we add, but we could be “deleting” initialized-but-unadded elements. I didn’t chase this beyond re-reading and enhancing my patch to measure “other manipulations” to see if they could explain it (no).

Thirdly, when we iterate it’s short: the list is empty or we break out on the first element 28% of the time (I didn’t differentiate). I wonder if a single-linked list would be an interesting micro-space-optimization for many of these lists.

Summary: I like the safety of SAMBA’s lists, but there’s clearly real merit in eliminating those branches for add and delete.  It’s a genuine performance-usability trade-off, so I I think we’ll still have both in CCAN…

RSS Feed

10 Comments for On C Linked Lists

Marko | December 12, 2010 at 9:14 pm

What should we use if lookups are most common? Hash tables?

Author comment by rusty | December 12, 2010 at 9:19 pm

Or some kind of tree … see Judy Arrays, too

startupgrrl | December 13, 2010 at 1:10 am

It’s a kernel– those lists are probably being used as queues, which would explain the high proportion of adds and deletes.

Vegard | December 13, 2010 at 5:40 am

You can get something that is almost type safe with more macro tricks. For example (I hope this shows up right):

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

/* Linux list interface: */

struct list_head {
    struct list_head *next, *prev;
};

static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

static inline void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif

#define container_of(ptr, type, member) ({          \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr – offsetof(type,member) );})

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

/* The type-safe interface (defined in terms of the Linux list interface): */

#define define_list(name, type) \
    struct name##_head { \
        struct list_head _private; \
    }; \
    \
    static inline type *name##_head_first(struct name##_head *head) { \
        return list_entry(head->_private.next, type, name); \
    } \
    \
    static inline type *name##_next(const type *node) { \
        return list_entry(node->name.next, type, name); \
    } \
    \
    static inline bool name##_is_last(struct name##_head *head, const type *node) { \
        return &head->_private == &node->name; \
    } \
    \
    static inline void name##_init(struct name##_head *head) { \
        INIT_LIST_HEAD(&head->_private); \
    } \
    \
    static inline void name##_add_tail(struct name##_head *head, type *new) { \
        list_add_tail(&new->name, &head->_private); \
    }

/* This is a custom structure */

struct node {
    struct list_head node_list;

    char *string;
};

define_list(node_list, struct node);

struct node *new_node(const char *string)
{
    struct node *ret = malloc(sizeof struct node);
    ret->string = string;
    return ret;
}

int main(int argc, char *argv[])
{
    struct node_list_head head;
    node_list_init(&head);

    node_list_add_tail(&head, new_node("Vegard"));
    node_list_add_tail(&head, new_node("Rusty"));

    /* The for loop is a bit contrived, but macros can’t define new
     * macros, and the only way to introduce a new for-loop in C is
     * by using macros. It is of course also possible to use the
     * "standard" Linux list_for_each/list_for_each_entry. */
    for (struct node *i = node_list_head_first(&head);
        !node_list_is_last(&head, i); i = node_list_next(i))
    {
        printf("node: %s\n", i->string);
    }

    return 0;
}

The point is to use the define_list() macro, which takes two arguments: the name of the list, and the type of objects that the list contains. The macro defines a number of static-inline functions which are type checked by the compiler.

I didn’t check to see what the generated code looks like, but at least in Linux the list functions are inlined anyway, so this shouldn’t increase text size.

Author comment by rusty | December 17, 2010 at 8:46 am

Very good point, thanks! Especially since skb (network packet) queues switched to using these lists; they used to be open-coded.

Pavel Pisa | January 7, 2011 at 9:09 pm

Hello Rusty,

I have been in a depressed mood years ago when I have wirtten different next, prev, parent etc construct again and again in C, all without type safety. The I have written something wich is a little parody on C++ STL and I am happy since then. This is set of macros and generic code which builds inline type safe manipulation functions for lists, AVL trees, sorted arrays of pointers, hash tables etc. The library is

uLUt Library – uLan/Universal Light Utilities Library

Contains

Double linked lists, Generalized AVL trees (GAVL), hierarchical timers framework (HTIMER), Dynamic buffer(DBUFF), Event connectors infrastructure (EVC) etc.

and much more. Some documentation can be found there

http://ulan.sourceforge.net/pdf/ulut.pdf

http://cmp.felk.cvut.cz/~pisa/ulan/gavl.pdf

http://ulan.git.sourceforge.net/git/gitweb.cgi?p=ulan/ulut

Because library can be used not only on POSIX/Windows userspace and our enbedded bare metal systems but has been intended for use in Linux kernel (mainly for OCERA RT-Linux CAN framework support), I have used base defines for list from Linux kernel to can vrap even existing kernel lists with type safety.

http://ulan.git.sourceforge.net/git/gitweb.cgi?p=ulan/ulut;a=blob;f=ulut/ul_list.h

The AVL trees with special property of fast cut of the firs element without rebalance provides same type safe interface with its custom version with embedded nodes or can be used with generic void * nodes with embedded or allocated node structures.

http://ulan.git.sourceforge.net/git/gitweb.cgi?p=ulan/ulut;a=blob;f=ulut/ul_gavlchk.c

The code is quite portable. I have helped to enhance inline support in SDCC 3.0 to the point, that core of uLUt library can be compiled and works on 8-bit 8051 target.

The cocumentaion is not in the best condition, but code is quite stable and no bug has been notices for many years. Code is used in uLan, OrtCAN , OCERA, ORTE, FRSH-FORB, our embedded motion controllers etc for core data structures.

Best wishes,

Pavel

Kevin Bowling | January 28, 2011 at 9:02 am

What about sys/queue.h? It is available on many POSIX systems and uses macros. Why do people continually reinvent list ADTs?

Author comment by rusty | January 28, 2011 at 10:10 am

In my case, ignorance. I shall do penance by creating a thorough blog post on it.

Thanks!
Rusty.

Kevin Bowling | January 28, 2011 at 3:19 pm

Also related to sys/queue.h, the BSDs include some fairly nice tree implementations in sys/tree.h.

For higher order stuff, here is some absolutely beautiful [ab]use of the C preprocessor to get generics and minimize indirection with C — https://github.com/attractivechaos/klib

Pavel Pisa | February 11, 2011 at 11:45 pm

Good to learn something new but there are missing features in sys/queue.h . There has to be used special variant for tail access (STAILQ, TAILQ). Insert and remove has conditional operations in them (i.e. 100 ticks penalty for Pentium IV for misspredict), no ability to remove element from list if you do not know list in which it belongs to (I have use for such operation in more cases). On the other hand it has advantege on iteration – no need to keep poiter to list head during use of NEXT.

The usage is macro based, no ability to wrap all knowledge about list and structures internals into some functions set.

So yes, I take that as my shame, that I have not known about
it (thanks for pointer). But it would not solve my original
need to wrapup already existing lists in Linux kernel and without this need the implementation and usage has its drawbacks.

KLIB seems interesting, but in case of its list implementation, it is single linked list. If non trivial data are included directly in nodes, next field location would be push out of initial cache line. Use of external nodes requires extra malloc.

uLUt GAVL and lists can be used with prealocated elements without malloc or need for some size configured nodes poll which is specially helpfull for some of our embedded use.

But yes, there are many disadvantages in my design as well and yes, it would be better to have one reasonably fitting structures compatible over all our and third-party libraries.

Leave a comment!

«

»

Find it!

Theme Design by devolux.org

Tag Cloud