memory allocation/deallocation (malloc experts needed)

[Charlie Root]

On Thu, May 20, 2004 at 01:42:00AM -0500, Dan Nelson wrote:
> In the last episode (May 20), Till Plewe said:
> > My problem is essentially that freeing large numbers of small chunks
> > of memory can be very slow. I have run into this problem twice so
> > far.
> 
> Do you have a testcase?  The attached program mallocs 1 million
> 128-byte blocks, then frees them.  With MALLOC_OPTIONS set to jz (i.e.
> no filling of freed memory), it takes .184 seconds to free them all. 
> With it set to J, it takes 1 second.
> 
> CPU: Intel Pentium III (909.96-MHz 686-class CPU)
>  

...

I get 

NUM		SIZE		MALLOC_OPTIONS		time
1058576		128		jz			0.044
1058576		128		JZ			0.13

128*1048576	8		jz			5.28
128*1048576	8		JZ			7.70

200*1048576	8		jz			8.25
200*1048576	8		JZ			13.17		

with CPU: AMD Opteron(tm) Processor 248 (2205.02-MHz K8-class CPU)

but with NUM 255*1048576 I run out of memory (although I have 6GB and
your test program should only use about
(sizeof(void*)+SIZE)*NUM=(8+8)*255*1048576=4GB)

Using NUM 256*1048576, SIZE 8 I get 

# gcc -o test test.c
/var/tmp//ccLxywz6.s: Assembler messages:
/var/tmp//ccLxywz6.s:95: Error: .COMMon length (-2147483648.) <0! Ignored.
/var/tmp//ccLxywz6.s:95: Warning: rest of line ignored; first ignored character is `,'

In any case since I have the pointers in a hash table (Judy array)
rather than an array I need extra time for look-up/deleting the entry
in the hash table as well. If I could get malloc to use a fixed memory
region for the part I want to delete (both for the hash table and the
information pointed to) deletion should take no time at all.

In my program I get times like this 

	DATA 6.553015 sec 
	JUDY 7.593997 sec
	deleted 1272062 hash entries, freed 28542840(Judy) + 15264744(data) bytes 
	
where judy translates hash values to pointers pointing to simple structs. 
Since I want to delete up to 10^8 entries the times get quite bad.
 
I guess quite a bit of the extra time is spent jumping around in
memory. Your test program frees memory in the order it was allocated which
should be a quite regular pattern. 

I will test some more and then post some more details.
Thanks for your answer.

- Till