Re: Faster than link list?


"Splendor" <splender.dev@xxxxxxxxx> wrote in message
news:1193223262.296974.120170@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I am creating a device driver for some graphical operation, where in
I am storing most of data as link list. Here I found fetching the data
from a large set of link list is very slow in performance....
Is it any alternative way to store and retrieve data very
quickly....? Any suggestion?


I'd suggest something that has less addressing overhead: stack or array.
Even though a stack or array may have less overhead, IMO, extremely large
linked lists are still extremely fast. Therefore, I suspect your problem
may be that you are doing something else which is slow. Perhaps, you are
searching the linked list for the data you need. If so, then the linked
list isn't the problem, but the searching is the problem. In which case,
you may prefer a tree (binary, trinary, ...) or a different algorithm to
locate the data faster. With a tree, you can organize and/or sort the data
as it is placed into the tree to reduce the time needed to locate data.

I'm also wondering how much of the data in the linked list is used at any
point in time. If only part of the data is being used at any point in time,
you might want to create a smaller linked list which just contains the
active data and is updated from the larger list as necessary.

Unfortunately, the pointers needed to link the list (or tree) can add much
memory overhead. For a double linked list, 8 bytes for 32-bit pointers per
node or 16 bytes for 64-bit pointers per node. For many nodes, this can
really consume memory even if most of them are eventually deleted.

Have you determined _why_ you are using a linked list?

1) move forward or backward through the data
2) need to search for data
3) skip over deleted nodes (i.e., memory gap between active data)
4) insert new nodes
5) need to sort data

If you are only using 1), then you what you really need is a stack or array.
If you need 1) and 2) but not 3) and 4), you still might want to strive for
a array or stack or even multiple arrays or stacks to eliminate the linked
list. The goal is to have all stack or array items be a fixed size. E.g.,
if you have a union of three differently sized data items, you might want to
separate the union data onto three stacks or arrays. Another stack or array
can be used to store which of the three stacks each data item is located,
i.e, a master stack. If you need 2), you might want to figure out some
other method to locate the data that doesn't require searching - even if you
choose to stay with a linked list or switch to a tree. If you need 3) but
not 4), then you might be able to setup an array of flags which indicate
which stack items are in use or deleted. This will allow you to skip the
deleted nodes or reactivate them.


Rod Pemberton

.

Relevant Pages

  • Re: garbage collection problem in large linked lists
    ... Instead all buckets are allocated at once in an array. ... VG.net, which must be very scalable, but only for lists which would normally ... Linked lists require pointer dereferencing in order to traverse. ... When you run out of space, you allocate a new smaller array. ...
    (microsoft.public.dotnet.framework.performance)
  • pHone the language, draft spec.
    ... The language phone is designed from many influences. ... Logical elements can be nested as lists using ... This leads to the next word LIT meaning literal. ... as which does symbol recall from the top of the stack. ...
    (comp.lang.misc)
  • Re: What is the difference between a Ruby array and a list in Haskell or Lisps?
    ... Lists in Lisp-like languages tend to be implemented as linked lists. ... You can certainly implement linked lists in Ruby, ... would have some sort of array you can use when you need it. ... ArrayList or LinkedList almost as if they were Ruby arrays: ...
    (comp.lang.ruby)
  • Re: averages
    ... second parameter int count for example is 12, and 15 numbers are in the list ... doubly-linked array data structure would be ideal. ... average if you modify it to use doubly linked lists for your data ...
    (comp.lang.c)
  • Re: remove all occurence of list
    ... ;;; Recurse, where natural. ... Traversing lists tail-recursively is not only an ... it's about limiting your stack space requirements. ... of reverse, every frame would hold exactly one word plus a return point. ...
    (comp.lang.scheme)