Managing data structures: lists

[sinsi]

Just let Windows worry about the heap?

[NoCforMe]

I think by that you mean "just waste it", as I described above, is that right?

That's certainly a valid choice. You can always allocate more if you run out of space.

[sinsi]

New string - HeapAlloc
Delete string - HeapFree
Resize string - HeapReAlloc

Windows uses a low-fragmentation heap, so it will take care of coalescing free blocks etc.
The downside is that there are a few bytes of overhead, so many small allocations might not work so well.

[jj2007]

many small allocations might not work so well

The Windows heap is optimised for many small allocations (there is VirtualAlloc for bigger ones, although it never makes a difference, speed-wise). Still, there is overhead that slows things down.

There are two faster options:
1. the stack (by default, up to around 800kBytes, more if you use linker option /stack:nnnnh)
2. a ring buffer; used in MB e.g. for Print Str$(number1), "<>", Str$(number2)

Both have the advantage that no *Free is needed.

Speed-wise, all three options are most of the time sufficient: you rarely use HeapAlloc in a speed-critical innermost loop. Tests with StackBuffer() show that it has an advantage over HeapAlloc for about 0-500kBytes; above that value, HeapAlloc is equally fast or slightly faster (YMMV).

[NoCforMe]

I have successfully incorporated my LM (list management) module into my editor, the latest version of which is available in this post.

[NoCforMe]

The Windows heap is optimised for many small allocations (there is VirtualAlloc for bigger ones, although it never makes a difference, speed-wise). Still, there is overhead that slows things down.

There are two faster options:
1. the stack (by default, up to around 800kBytes, more if you use linker option /stack:nnnnh)
2. a ring buffer; used in MB e.g. for Print Str$(number1), "<>", Str$(number2)

I just don't get it.

What is it with your obsession with speed here? To me, that's the last thing I'd be looking at when it comes to memory allocation. What I would want out of a memory allocator is

• Efficiency of allocation; minimal memory wasted
• Reliability and good error handling

[jj2007]

What is it with your obsession with speed here?

many small allocations might not work so well

I wouldn't accuse Sinsi of being obsessed with speed, but his only argument against using the heap was, indeed, speed. Do you get it now?

Efficiency of allocation; minimal memory wasted

Why are you so obsessed with memory? I have 16GB of it.

[NoCforMe]

Efficiency of allocation; minimal memory wasted

Why are you so obsessed with memory? I have 16GB of it.

Sure; I've got 5Gb, which ain't chicken feed either.

However, someone else who has some gigantic memory-intensive application would be quite concerned with efficient usage of memory. Not me, but others. Speed, probably not so much.

[jj2007]

Somebody with a "gigantic memory-intensive application" would be extremely concerned with speed, for obvious reasons.

[sinsi]

Actually, my point was about memory - if you allocate lots of 4-byte blocks, there is at least an 8-byte overhead associated with it, so every 4 bytes you allocate actually uses 12. Of course, this is an extreme case

[jj2007]

if you allocate lots of 4-byte blocks, there is at least an 8-byte overhead

Point taken