Double Linked Dynamic Lists Vs Unrolled Linked Lists

Hi all,

I wrote an array based connection tracker in c, but I'm looking to move it to either dynamic lists or maybe unrolled linked lists. Double linked dynamic lists are simple enough, but this code is intended for an embedded system where resources are a constraint.

Which method do you suggest for high-performance? primarily use consists of reads and searches, and secondarily (while not as numerous) adding and updating nodes.

If anyone has seen example c code for unrolled linked lists - I'd be very grateful.

If you are aiming for high-performance then use Unrolled Linked Lists. It stores multiple elements in a single node which greatly improves cache usage and lesser memory usage when all nodes are full or half-full (Depends on the size of the elements).

You can implement a doubly linked list in an array, very space efficient, and maybe a bit easier to code than the unrolled linked list. Basically it's the array part inside an unrolled linked list No next/prev pointers at all, you just go to the next array index or increment/decrement a pointer that points to the current node in the array. And it has minimal mallocs/reallocs, which is good if this runs "forever" or for very long times, as is common in embedded applications. All those little mallocs and frees of individual nodes can end up fragmenting your heap pretty bad since C has no garbage collection, meaning you may see malloc fail for larger chunks. It's easy enough to delete from the middle of the array by doing a lazy delete -- just marking a node as deleted and skipping over it in any traversal. Inserting in the middle is a little trickier and bit more time consuming, but also doable. You can size up and down as needed by using realloc

What's the embedded system look like? What OS/platform are you running on?

System is running on an xscale 455 Mhz and 32 mb ram free after OS.

I'm looking at a doubly linked list vs xor vs skiplist. Each collection has 60,000 elements and I insert then traverse and search for an item in the center. The doubly linked list is a bit faster than a my xor program.

Make an array of lists, and split your search time by N where N is the number of elements in your array. It's simple, and works fairly well.


Quzah.

It's rather unfortunate you mentioned the skip-list. I am passionately against that data structure.
It's such a clumsy thing that has no significant strengths over other things, and all up is of little practical use. That's why you pretty much never see it used.

The xor linked-list has largely outgrown it's usefulness in modern programming, but may still be useful on very embedded systems.

I can't quite be sure, but one near-optimal solution for circumstance that may match yours is to use a container consisting of partially sorted and partially unsorted array.
Basically you maintain counts of the number of sorted and unsorted items. New items are added at the end in the unsorted portion. When the number of items in the unsorted portion exceeds a certain threshold you sort that portion and merge it with the sorted portion. For optimality the size cutoff for the unsorted portion should be somewhere between log(n) or sqrt(n), depending on the frequency of inserts vs lookups and what sorting algorithm you use.
To find an item you first try a binary search on the sorted portion, and if that fails you perform a linear search on the remaining portion.
The strengths are minimal memory overhead with good lookup and good amortised insertion times.
The weaknesses are that removals are O(n) from the sorted portion (but still O(1) from the unsorted portion using swap and pop-back), and also insertion time is amortised rather than fixed. Removals can sometimes be improved by finding a reasonably close replacement from the unsorted portion.

Unrolled linked lists are good too. These can be especially good if you sort each unrolled part, or even the list itself as well.

Hmm, well both of those suggestions assume ordering is not important. Perhaps you could give more info that might lead to me making fewer possibly incorrect assumptions.

Edit: The above poster gave me another thought, a B-Tree could be pretty well ideal.

Ahh sorry to get back to you so late - essentially here is what happening:

As new connections come in, the connections are compared to this maintained list (for lack of a better word) from end to start. If it isn't known, a new one is added to the end with a specific state. If it is known and is a response, that tupple gets updated. Old connections are forgotten in some sense (but still exist for later use) and so it is partially sorted. I should sort by protocol though since a lan could create many tupples over time.