Stack based allocation vs. Dynamic allocation

Stack based allocation vs. Dynamic allocation

[dale]

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

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


Dale

Re: Stack based allocation vs. Dynamic allocation

[Ray Blaak]

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.

-- 
Cheers,                                        The Rhythm is around me,
                                               The Rhythm has control.
Ray Blaak                                      The Rhythm is inside me,
blaak@infomatch.com                            The Rhythm has my soul.

Re: Stack based allocation vs. Dynamic allocation

[Dale Stanbrough]

Ray Blaak wrote:

> 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
submitting such obviously bad code.

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

Ada Heap Unconstrained Changing
  -- alternating b/w allocating 1E6/3, 1E6 *3 size arrays

real       56.0
user       52.3
sys         0.1

Ada Stack Unconstrained Changing
  -- 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

Re: Stack based allocation vs. Dynamic allocation

[Laurent Guerby]

Dale Stanbrough <dale@cs.rmit.edu.au> writes:
> 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.

-- 
Laurent Guerby <guerby@acm.org>

Re: Stack based allocation vs. Dynamic allocation

[Matthew Woodcraft]

In article <86og5m7aig.fsf@acm.org>, Laurent Guerby  <guerby@acm.org> wrote:
>Dale Stanbrough <dale@cs.rmit.edu.au> writes:
>
>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-

Re: Stack based allocation vs. Dynamic allocation

[Laurent Guerby]

Matthew Woodcraft <mattheww@chiark.greenend.org.uk> writes:
> In article <86og5m7aig.fsf@acm.org>, Laurent Guerby  <guerby@acm.org> wrote:
> >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
what got added.

-- 
Laurent Guerby <guerby@acm.org>

Re: Stack based allocation vs. Dynamic allocation

[Robert Dewar]

In article <dale-B8D55E.22230631052000@news.rmit.edu.au>,
  Dale Stanbrough <dale@cs.rmit.edu.au> wrote:
> 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/
Before you buy.

Re: Stack based allocation vs. Dynamic allocation

[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

Re: Stack based allocation vs. Dynamic allocation

[Lutz Donnerhacke]

* Gisle S�lensminde wrote:
>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.

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

Re: Stack based allocation vs. Dynamic allocation

[Gisle S�lensminde]

In article <slrn8j9pno.mk.lutz@taranis.iks-jena.de>, Lutz Donnerhacke wrote:
>* Gisle S�lensminde wrote:
>
>>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.

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

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

Re: Stack based allocation vs. Dynamic allocation

[Aaro Koskinen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 975 bytes --]

gisle@struts.ii.uib.no (Gisle S�lensminde) writes:
> 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 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()).

-- 
Aaro Koskinen, aaro@iki.fi, http://www.iki.fi/aaro

Re: Stack based allocation vs. Dynamic allocation

[Jean-Pierre Rosen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1113 bytes --]


dale <dale@cs.rmit.edu.au> a �crit dans le message : dale-D70BFC.16062031052000@news.rmit.edu.au...
> 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...

--
---------------------------------------------------------
           J-P. Rosen (Rosen.Adalog@wanadoo.fr)
Visit Adalog's web site at http://pro.wanadoo.fr/adalog

Re: Stack based allocation vs. Dynamic allocation

[Aaro Koskinen]

dale <dale@cs.rmit.edu.au> writes:
> > 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.

-- 
Aaro Koskinen, aaro@iki.fi, http://www.iki.fi/aaro