Re: Stack based allocation vs. Dynamic allocation

[gisle@struts.ii.uib.no (Gisle S�lensminde)]

In article <m33dmz9otb.fsf@ns49.infomatch.bc.ca>, Ray Blaak wrote:
>dale <dale@cs.rmit.edu.au> writes:
>> A discussion at work left me claiming that stack based allocation
>> was quicker than heap based allocation. 
>> 
>> A person wrote up a demonstration program that proved that this
>> wasn't the case (at least for the experiment).
>[...]
>> procedure Stack is
>>    N : constant := 500;
>>    Big : constant := 1024 ** 2;
>>    type ints is array (0 .. Big) of Integer;
>[...]
>> procedure Heap is
>>    N : constant := 500;
>>    Big : constant := 1024 ** 2;
>>    type ints is array (0 .. N - 1) of integer;
>>
>> Does anyone know what the factors are that would cause stack
>> allocation to be so slow?
>
>Well the code you posted has the heap version working with much smaller arrays
>(500 vs 1 million), so of course it will be faster. 
>
>Fix the Heap version to have the same array type as in the Stack version and
>try again. I am interested in the answer.


I changed the heap program to allocate exactly the same number of bytes
as the stack program. More precisly I changed the type ints in the heap
program to be identical to that of the stack program:

type ints is array (0 .. Big) of Integer;

I compiled with gnat 3.12 on Linux, with option -O2:

gisle@gekko:116> time heap
Time: 0:53.92 real   31.250 user   12.190 sys   80.5%

gisle@gekko:120> time stack
Time: 0:11.02 real   10.490 user   0.030 sys   95.4%

The stack program was 3 times faster if you consider user times.
In my tests the system time used was always at least 11 seconds,
while the stack program never used more than 0.05 seconds. The 
system have to work harder when using heap allocation, which makes
the heap program run in only 1/4th of the time of the stack program.

The timing will be different on other platforms, but it would surprise 
me if heap allocation is faster anywhere. With more realistic 
memory usage, the heap allocation will probably be even worse. 
The only exception is probably the JVM target, where nearly everything 
is on the heap. 

--
Gisle S�lensminde ( gisle@ii.uib.no )   

ln -s /dev/null ~/.netscape/cookies