Thread: Double Linked Dynamic Lists Vs Unrolled Linked Lists

  1. #1
    Registered User lantzvillian's Avatar
    Join Date
    Sep 2010
    Posts
    44

    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.

  2. #2
    Registered User
    Join Date
    Nov 2011
    Posts
    52
    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).
    The price of reliability is the pursuit of the utmost simplicity. - Sir Charles Antony Richard Hoare,

  3. #3
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    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?

  4. #4
    Registered User lantzvillian's Avatar
    Join Date
    Sep 2010
    Posts
    44
    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.

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    Last edited by iMalc; 02-03-2012 at 08:36 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User lantzvillian's Avatar
    Join Date
    Sep 2010
    Posts
    44
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double pointers and linked lists.
    By simo_r in forum C Programming
    Replies: 2
    Last Post: 05-06-2008, 04:25 AM
  2. Double linked lists
    By JFonseka in forum C Programming
    Replies: 19
    Last Post: 03-13-2008, 06:05 AM
  3. c++ double linked lists searching
    By payling in forum C++ Programming
    Replies: 8
    Last Post: 04-26-2007, 02:03 PM
  4. Double Linked lists
    By Jamsan in forum C++ Programming
    Replies: 1
    Last Post: 03-11-2003, 09:46 AM
  5. double linked lists
    By susyb in forum C++ Programming
    Replies: 3
    Last Post: 11-29-2001, 06:09 AM