Stack based allocation vs. Dynamic allocation
Author Message
Stack based allocation vs. Dynamic allocation

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).

The code (translated to Ada by me) is...

procedure Stack is

N : constant := 500;

Big : constant := 1024 ** 2;

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

begin
for i in 0 .. N - 1 loop
declare
a : Ints;

begin
for j in a'range loop
a(j) := j;
end loop;
end;
end loop;
end;

with unchecked_deallocation;

procedure Heap is
N : constant := 500;

Big : constant := 1024 ** 2;

type ints is array (0 .. N - 1) of integer;
type ints_ptr is access ints;

procedure free is new unchecked_deallocation (ints, ints_ptr);

begin

for i in 0 .. N - 1 loop
declare
a : ints_Ptr := new ints;

begin
for j in a'range loop
a(j) := j;
end loop;

free (a);
end;
end loop;
end;

The results show that the heap allocation is considerably faster
everytime (that i ran it).

Using gnat 3.12, -O2, Solaris consistently gives me the results
very similar to the following...

Quote:
> time ./heap

0.01u 0.02s 0:00.18 16.6%
Quote:
> time ./stack

17.72u 0.10s 0:19.86 89.7%

Does anyone know what the factors are that would cause stack
allocation to be so slow?

Dale

Sun, 17 Nov 2002 03:00:00 GMT
Stack based allocation vs. Dynamic allocation

Quote:

> 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.

--
Cheers,                                        The Rhythm is around me,
The Rhythm has control.
Ray Blaak                                      The Rhythm is inside me,

Sun, 17 Nov 2002 03:00:00 GMT
Stack based allocation vs. Dynamic allocation

Quote:
> 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).
> [...]
>    for i in 0 .. N - 1 loop
>       declare
>          a : ints_Ptr := new ints;

>       begin
>          for j in a'range loop
>             a(j) := j;
>          end loop;

>          free (a);
>       end;
>    end loop;
> end;

A wild guess:
Note that in this example, you immediately reallocate an array of the same size that has just been deallocated. This means that the
lookup which is often cause of slow heap allocation will immediately find a perfect fit. This is certainly not representative of a
real program. Try running your test with random array sizes, then tell us the results...

--
---------------------------------------------------------

Sun, 17 Nov 2002 03:00:00 GMT
Stack based allocation vs. Dynamic allocation

Quote:

> > time ./heap
> 0.01u 0.02s 0:00.18 16.6%
> > time ./stack
> 17.72u 0.10s 0:19.86 89.7%

> Does anyone know what the factors are that would cause stack
> allocation to be so slow?

The array sizes were not equal. In the stack version, the loop is
about 2000 times longer. A harsh calculation would indicate that the
stack allocation was actually quicker.

--

Sun, 17 Nov 2002 03:00:00 GMT
Stack based allocation vs. Dynamic allocation

Quote:

>> 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:

Time: 0:53.92 real   31.250 user   12.190 sys   80.5%

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.

--

Sun, 17 Nov 2002 03:00:00 GMT
Stack based allocation vs. Dynamic allocation

Quote:

>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 heap management causes this performance gap.

Quote:
>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.

There are a lot of 'single-address-space' OS around which do not have these
limitations. There heap allocation might be much faster than stack
allocation, simply because they have nothing to do on heap allocation but
to change the parameters of the stack and often rearrange it otherwise.

Sun, 17 Nov 2002 03:00:00 GMT
Stack based allocation vs. Dynamic allocation

Quote:

> 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.

Well Ray was very correct, and i was very wrong! I must apologise for

I've fixed the code, and added in a few extras. I have compared various
variations of the code (in C and in Ada), the results follow...

Ada Stack   -- allocating fixed size array

real       17.5
user       16.5
sys         0.0

C Stack     -- allocating fixed size array

real       17.0
user       16.2
sys         0.0

Ada Heap    -- allocating fixed size array

real       20.3
user       18.8
sys         0.0

C Heap   -- allocating fixed size array

real       30.6
user       28.1
sys         0.0

Ada Heap Unconstrained -- allocating fixed sized unconstrained array

real       35.4
user       34.1
sys         0.0

-- alternating b/w allocating 1E6/3, 1E6 *3 size arrays

real       56.0
user       52.3
sys         0.1

-- alternating b/w allocating 1E6/3, 1E6 *3 size arrays

real       28.2
user       26.3
sys         0.1

All compiled with gnat 3.12/gcc, on Solaris
Not quite sure why the unconstrained version should be so much more
expensive. Interesting to note of course that the Ada heap version
is -so- much cheaper than the C version. Presumably they are calling
different allocators.

Dale

Sun, 17 Nov 2002 03:00:00 GMT
Stack based allocation vs. Dynamic allocation

Quote:

> Time: 0:53.92 real   31.250 user   12.190 sys   80.5%

> 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 huge amount of used system time is interesting, since the
allocated data is always of the same size - there shouldn't be any
need for another system call after the first "new". Unless the "free"
releases the memory back to the operating system. (Most of C library
implementations I've seen do not usually shrunk the process' heap on
free()).

--

Sun, 17 Nov 2002 03:00:00 GMT
Stack based allocation vs. Dynamic allocation

Quote:

>>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.

>There are a lot of 'single-address-space' OS around which do not have these
>limitations. There heap allocation might be much faster than stack
>allocation, simply because they have nothing to do on heap allocation but
>to change the parameters of the stack and often rearrange it otherwise.

I was probably a bit narrow-minded, since only PCs/workstations came
to my mind. For other kinds of systems performance is a very different
matter.

--
--

Sun, 17 Nov 2002 03:00:00 GMT
Stack based allocation vs. Dynamic allocation

Quote:

> I've fixed the code, and added in a few extras. I have compared various
> variations of the code (in C and in Ada), the results follow... [...]

Note that the Ada versions is not really comparable with the C version
since you have array bound safety in Ada (I guess the compiler removed
the checks) and not in C.

I'm surprised the Ada heap version is faster than the C one since GNAT
calls the system malloc (hmmm it might be a GNU malloc vs Solaris
malloc issue if you're using FSU threads).

Also you can have more fun by having the size of the local array
variable being a function of i, since there is no C stack based
equivalent (GNU C has it as a language extension though).

The only problem with stack based allocation is in a 32 bits address
space multi threaded application context where you might have big
arrays, you have then an unsolvable problem with thread stack size.

On the software I'm working on, we had to move some stack based
(dynamic) array to the heap (with controlled types for automatic
deallocation) for this reason.

--

Sun, 17 Nov 2002 03:00:00 GMT
Stack based allocation vs. Dynamic allocation

Quote:

>Also you can have more fun by having the size of the local array
>variable being a function of i, since there is no C stack based
>equivalent (GNU C has it as a language extension though).

I believe this is one of the additions in the recently-adopted C
standard.

-M-

Mon, 18 Nov 2002 03:00:00 GMT
Stack based allocation vs. Dynamic allocation

Quote:

> >Also you can have more fun by having the size of the local array
> >variable being a function of i, since there is no C stack based
> >equivalent (GNU C has it as a language extension though).

> I believe this is one of the additions in the recently-adopted C
> standard.

Do you have a pointer to it (or a draft)? I'm curious about

--

Mon, 18 Nov 2002 03:00:00 GMT
Stack based allocation vs. Dynamic allocation

Quote:
> Interesting to note of course that the Ada heap version
> is -so- much cheaper than the C version. Presumably they are
> calling different allocators.

Just shows that the measurements are bogus, because in fact
GNAT uses normal malloc/free, just like C!

Sent via Deja.com http://www.deja.com/