Pretty much every piece of software I’ve seen uses a list of objects. When you need to easily grow and shrink this list easily you then need something like a Linked List. dhcpcd has used very popular and widely available BSD based queue(3), specifically a tailq. The main advantages of this type of list are:

  • Very low extra memory needed for it’s implementation
  • Fast at insertion and removal operation- both are O(1)

However, it’s just a list. And like any list, to find something we need to pick a starting point and then search in a single direction and match each item until we find it. This is described as O(N) and it’s performance roughly corrolates to the Number of objects in the list. If you need to insert at an arbitary point (for example to order the list) you need to search it, so this is O(N) also.

But is this slow?

Typically for dhcpcd, the answer is no because on a desktop, tablet, phone or SOHO router you only have a handful of objects in all the lists. However, someone ran dhcpcd on a switch with millions of routes and dhcpcd was taking minutes of CPU time for routing table modifications. So in this corner case … yes! dhcpcd is slow! A suggestion to improve matters was given in that report- use a Red-Black Tree instead of a Linked List. A RB tree guarantees O(log N) performance for searching. A patch was even submitted based on OpenBSD’s tree implementation! This reduced the dhcpcd runtime from minutes to seconds in his situation.

Now you can’t just swap in a RB Tree for a Linked List. Each object within an RB Tree has to have a unique key. Also, you need to have comparison function to define an order to the objects within the tree. Only then can you start to implement it. To find an object within the tree, you just need to know it’s key and off you go. I settled on using NetBSD’s rbtree(3) implementation instead of the initial suggestion to use the generic BSD tree(3). This mainly to reduce the binary size of dhcpcd because it’s in libc on NetBSD and on other systems it will creates a smaller binary due to the complexity of the tree(3) macros. Testing also showed it was slightly faster and also easier to actually develop with.

So should you replace all LinkedLists with RB Trees? No! That would be silly :) After all, sometimes you don’t actually need to search or order a list- a lot of the time, lists are used for push/pop operations and thus gain nothing from RB Tree.

You’ll get to see this in dhcpcd-8 which should be released later this year.