Re: Fast linked list

From: Mark Randall (strike_at_rapiercom.freeserve.co.uk)
Date: 12/23/04 

Date: Thu, 23 Dec 2004 08:56:23 -0000

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

"Kim Gräsman" <kim@mvps.org> wrote in message
news:Ocq3bbM6EHA.2016@TK2MSFTNGP15.phx.gbl...
Mark,

> > Why don't you just use an array?
>
> Ever tried adding things to a static array?...

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. 

-- 
Best regards,
Kim Gräsman

Relevant Pages

  • Re: Fast linked list
    ... in my experience allocating large chunks of memory and copying the ... contents is a hidiously slow process compared to a linked list. ...
    (microsoft.public.vc.mfc)
  • Re: Fast linked list
    ... in my experience allocating large chunks of memory and copying the ... contents is a hidiously slow process compared to a linked list. ...
    (microsoft.public.dotnet.languages.vc)
  • Re: Fast linked list
    ... in my experience allocating large chunks of memory and copying the ... contents is a hidiously slow process compared to a linked list. ...
    (microsoft.public.win32.programmer.kernel)
  • Re: [Announce]: Target_Core_Mod/ConfigFS and LIO-Target v3.0 work
    ... allocations would help the performance of a storage target. ... A single codepath memory allocating *AND* mapping for: ... Allocating multiple contigious struct page from the memory allocator ... I never claimed that RDMA is only possible from user space -- that was ...
    (Linux-Kernel)
  • Re: Forcing a Large Object Heap allocation.
    ... you should be passing the recommended 60% memory limit. ... that point and you should be experiencing an unstable app IMO. ... > compacts the heap. ... > objects in the regular heap causes poorer performance than allocating many ...
    (microsoft.public.dotnet.framework.performance)