Fast linked list

  • Thread starter Thread starter Guest
  • Start date Start date
G

Guest

Hi,

for my current application, I need a linked list in which I can access and
walk through at highest speed possible - adding/deleting/inserting elements
can be as slow as necessary. Now, which template out of the C/C++ standard
library should I use for this - std::list? Or is there a better
implementation out there?

thanks
Peter
 
Write your own... check CTypedPtrList if you need a little backup on it...
Its by far the best I have used without the need to bolt on extensions to
the classes.

- MR
 
Peter said:
Hi,

for my current application, I need a linked list in which I can
access and walk through at highest speed possible -
Click to expand...

By 'access' do you mean 'traverse' as in:

for( container::iterator lItr = c.begin() ; lItr != c.end() ; ++lItr )
{
// do something with *lItr
}

adding/deleting/inserting elements can be as slow as necessary. Now,
Click to expand...

These usage patterns do not require a linked list.
which template out of the C/C++ standard library should I use for
this - std::list? Or is there a better implementation out there?
Click to expand...

std::vector would be a better option given your usage patterns, with the
added benefit of less memory consumption and fragmentation.

Jeff Flinn
 
Exactly. In my program I have to walk the complete linked list, beginning at
the head, then moving on to the next item until I reach the last item
(there's no need for random access to any items). This 'walking' and
accessing the structure behind the items needs to be as fast as possible.


Merry Christmas
Peter
 
Peter Schmitz said:
Hi,

for my current application, I need a linked list in which I can access and
walk through at highest speed possible - adding/deleting/inserting elements
can be as slow as necessary. Now, which template out of the C/C++ standard
library should I use for this - std::list? Or is there a better
implementation out there?

thanks
Peter
Click to expand...

CTypedPtrArray.

You can append, insert, delete (which are slow) and of course append.

Storing data as pointers minimizing assignment time.

You can binary search if you keep it sorted and you feel that's necessary.

I would imagine iterating would be very fast, although I've never compared
it to, say, CTypedPtrList.

I'm sure there are equivalent standard template library types out there.
 
Mark,
Ever tried adding things to a static array?...
Click to expand...

Ever hear of dynamically allocated arrays?

I agree with Jeff F - if neither adding or removing elements have any speed requirements, why not just go with a vector? I don't think you can find any container with faster end-to-end traversal.
 
Of course,

However, in my experience allocating large chunks of memory and copying the
contents is a hidiously slow process compared to a linked list.

While I understand that end-to-end enumeration is speed critical, this leads
me to presume that there must be a large amount of data and as such, arrays
would be somewhat slow in the process of adding. While not an essential
requirement as stated it must be considered for over-all system performance.

Typically, with some form of LL | DLL implimentation you already have your
next location available from the last, or you must call a function
(CTypedPtrList).

I agree, vector would be quick, provided you allocated sufficent space
beforehand for all the elements because as you know, in such an event the
old array is deallocated and a new one is created each time.

While I understand LL's are my personal preference for situations like this,
as the processor (at least Intel) seems to work best allocating small
amounts of memory rather than huge chunks of it. But that is for the most
part irrelevant in this case.

As far as vector goes, yes, useful - its speed is in its pointer addition.
However, for end-to-end, you already know the next item of a Purely Linked
List as soon as you have the previous one, there is no need to recalculate
it from the base. Downside, an extra 4 bytes (LL) or 8 bytes (DLL).

- MR

Mark,
Ever tried adding things to a static array?...
Click to expand...

Ever hear of dynamically allocated arrays?

I agree with Jeff F - if neither adding or removing elements have any speed
requirements, why not just go with a vector? I don't think you can find any
container with faster end-to-end traversal.
 
Peter Schmitz said:
Hi,

for my current application, I need a linked list in which I can access and
walk through at highest speed possible - adding/deleting/inserting
elements can be as slow as necessary. Now, which template out of the C/C++
standard library should I use for this - std::list? Or is there a better
implementation out there?
Click to expand...

If your elements are bigger than a 32-bit word, then vectors and linked
lists will have about the same performance. Vectors will only be noticeably
faster if the elements are small, they are stored directly [i.e., not
through a pointer] and the operation on the element while traversing the
vector/list is very simple. Otherwise, they are equivalent and you should
consider other factors, such as the speed of insertion/deletion.

S
 
Mark Randall said:
However, in my experience allocating large chunks of memory and
copying the contents is a hidiously slow process compared to a linked
list.
Click to expand...

Adding to the end of std::vector is an amortized constant operation.
While the memory allocation and copying is slow, the vector does not
grow its storage one element at a time. Instead, it grows by some factor
(e.g., doubles its storage on every reallocation). Thus, for every
expensive add operation, there are many cheap ones - adding an element
when there's still space in the buffer does not involve any memory
allocation or any copying (besides the element itself), so it's faster
than adding an element to linked list where a node must be allocated on
the heap.

The large cost of occasional memory reallocation is spread, or
amortized, across many cheap operations. That's what "amortized
constant" means.
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925
 
If the O.P. doesn't know the maximum size it will ever get to or can't
determine it, then he could reallocate a whole new array -
"adding/deleting/inserting elements can be as slow as necessary" he said.
But it would be better to just put a finger on the maximum ever size at the
beginning. If the O.P. doesn't want to consume the maximum amount of memory
all of the time, then this is something he failed to point out.
 
for my current application, I need a linked list in which I can access and
walk through at highest speed possible -
Click to expand...

Highly-optmized read side peformance... Is your list accessed by multiple
threads? If so, it seems that your asking for an algorithm that provides a
method to achieve lock-free reads. Here is a rock-solid algorithm that can
be implmented in assembly language:

http://www.research.ibm.com/people/m/michael/spaa-2002.pdf

This actually works, and its fairly straight forward.
 
Semi-OT:

I must admit that this is the first time I have EVER seen so many coders
discussing implimentations, code developments and comparisons for a single
topic.

Rather nifty in my opinion,

- Mark R
 
Back
Top