Freeing large linked lists

[sparhawk]

Depends on your datastructure. We were using an array, so we just run from the back. As always with performance tuning, you have to measure the effect, to see if it really makes a difference in your case.

[pink^abyss]

Originally Posted by carls

I don't remember actually but it was significant. Like, 10 seconds or something for maybe 1000 items.

Anyway, I rewrote the whole thing to read the entire file into a large char and then do tokenization on that, it's now almost instant instead.

PS.
Coda is a wonderful intro, one I keep returning to.

Thanks for your Coda comment It was big fun to create.


Regarding removing a 1000 items from LinkedList heap: there will be (1000-n) x (1000-n) comparisons if freeing is done in the reverse order you allocated them. If the heap is already filled with other items it will take even more comparisons. So this can take quite some time (tho 10s sounds too much to me).

[carls]

Originally Posted by pink^abyss

So this can take quite some time (tho 10s sounds too much to me).

It was a singly linked list of arbitrarliy-sized malloc'd chars. I freed it by iterating from the head.


Granted, this was 6 months ago or more and I tested with many different list sizes, so my recollection of the exact performance is a bit hazy. It was at least unacceptably slow in my book.

[Thomas Richter]

Memory you allocated by malloc() is automatically released when the program terminates, but it is not the operating system which does that (unfortunately) but by the compiler library that provides malloc() and free(). In that sense, "you are safe" memory wise.

The reason why that works is that the compiler library implements a memory pool, and instead of releasing each memory segment individually, it just returns the entire pool to the system.

An Os-based lookalike is AllocPooled()/FreePooled() , and CreatePool()/DeletePool() to create and dispose such pools. The compiler library may not use exactly these functions, but some lookalikes.

[carls]

Originally Posted by Thomas Richter

An Os-based lookalike is AllocPooled()/FreePooled() , and CreatePool()/DeletePool() to create and dispose such pools. The compiler library may not use exactly these functions, but some lookalikes.

Thanks, reading about those now. I was wondering how that worked with the heap but I see that the pool manager allocates puddles.