Something faster than linked lists

earlz · **Joined:** Thu Jul 07, 2005 11:00 pm **Posts:** 1546

I am trying to make my event system not use a huge array of function pointers and rather use something like a linked list. The only problem is that linked lists are so slow! Is there any other method of dynamic allocation that is any faster?
My best idea so far is to have a linked list of arrays, like rather than just having a linked list object hold only one element, have a linked list object have an array of 256 or so elements..which in my case would be allocating in 2k blocks..

Alboin · **Posted:** Sat Apr 21, 2007 6:28 pm

Yeah that works. It's called unrolled linked lists There's more info on the wikipedia page. You might find some better methods there as well.

Kevin McGuire · **Posted:** Sat Apr 21, 2007 7:07 pm

<edit>
I just realized you were talking about allocation being slow and not the linked list. Oops.
</edit>

A similar method is to periodically convert portions or as much as you like of the linked list into an array. You might use a unrolled linked list along side of something like this.

If you are finding you're self having too large of a linked list then you might try increasing the overall structure depth or/and grouping events so that when you need to perform a search or modification of certain entries you have decreased the number of entries.

So if you are keeping track of events for something, then you might only attach those events to that something instead of:

Shallow Overall Structure Depth

Code:

struct tEvent{
     struct tSomething *something;
     /// event information
     struct tEvent *next, *prev;
};

Increased Overall Structure Depth.

Code:

struct tEvent{
     /// event information
     struct tEvent *next, *prev;
};
struct tSomething{
     struct tEvent *events;
};

Grouping
Sometimes you can make one item become part of multiple lists.

Code:

struct tItem{
     u32 type;
     struct{
           struct tItem *next, *prev;
     } core, type1, type2, type3;
}; 

Where the core next and prev could repersent if you needed the entire linked list. The type1, type2, and type3 could represent linked list of entries corresponding to certain types. So if you needed to only search for a type1 then you would have eliminated the type2 and type3 needless searches.

Decrease Evaluation Time Of Items

You can sometimes decrease the evaluation time of the items in the linked list which will decrease the total time to search the linked list. If you are searching for strings try adding a hash value beside them. Then check the hash, then the string if the hash is correct.

Code:

unsigned int hash(unsigned char *string){
  u32 x, hash;
  for(x = 0, hash = 0; string[x] != 0; ++x){
    hash += string[x];
  }
  return hash;
}

You might even find a performance increase if you check multiple integer values. Where you check a, b, and c for va, vb, vc. Then a+b+c==va+vb+vc. Of course you take a penalty when you find the correct item; or for each correct item.

OSDev.org

Something faster than linked lists

Who is online