Overview Features Instructions Performance Forum Downloads Products OrderV4 Reseller Contact

Welcome to the Apollo Forum

This forum is for people interested in the APOLLO CPU.
Please read the forum usage manual.
VISIT APOLLO IRC CHANNEL



All TopicsNewsPerformanceGamesDemosApolloVampireAROSWorkbenchATARIReleases
Running Games and Apps.

[Development] Stack Vs Heap Memory Allocationpage  1 2 

Olle Haerstedt

Posts 102
17 Mar 2020 21:28


Again, sorry for spamming the forum. Does anyone know about memory management in classic Amiga games? The reason I'm asking is because the performance gain of PHP  7 compared to previous versions was to a large degree caused by moving heap allocations to stack if possible. If I understand correctly, stack allocation is also common in embedded programming - you allocate what you need at startup and don't use algorithms that need dynamic allocation etc. It's also possible to use your own memory management technique, by using the stack allocated memory as a pool. And there's a bunch of different ways to do dynamic allocation too - how is AmigaOS doing it? Anyone has any clue? Does this matter at all for performance, or is the bottleneck in the rendering?


Matthew J Fletcher

Posts 8
18 Mar 2020 21:44


Hi Olle,

Fundamentally both stack and heap are the same memory, so the speed of access is the same, stacks are typically created by doing an allocation from heap and then passing it into the task.

Heap memory allocators will always have an overhead of finding the right size block for you. By using stack or just a chunk of heap and index into it yourself and can make some small gains, but really your reinvesting the wheel and will probably just introduce bugs.

Remember 99% of code is not performance critical, the best way to write performant code is to understand where to spend your time on improving it and design the alogrithum well.



Olle Haerstedt

Posts 102
18 Mar 2020 22:33


Matthew J Fletcher wrote:

Hi Olle,
 
  Fundamentally both stack and heap are the same memory, so the speed of access is the same, stacks are typically created by doing an allocation from heap and then passing it into the task.
 
  Heap memory allocators will always have an overhead of finding the right size block for you. By using stack or just a chunk of heap and index into it yourself and can make some small gains, but really your reinvesting the wheel and will probably just introduce bugs.
 
  Remember 99% of code is not performance critical, the best way to write performant code is to understand where to spend your time on improving it and design the alogrithum well.
 

So after googling around a bit (yes, I know I'm supposed to do it *before* I post), there's actually a lot of discussion about this already, e.g. here: EXTERNAL LINK 
Lots of people advice against using "new" (dynamic memory allocation) inside a game loop, but instead pre-allocating before a level starts. It's interesting. Yes, of course it also introduces the risk of bugs in your own memory management system.

About "99% of code is not performance critical", I don't think that's true for games. :)


Olle Haerstedt

Posts 102
18 Mar 2020 22:33


That also makes me wonder how the heck AMOS and BlitzBASIC deal with this stuff.


Philippe Flype
(Apollo Team Member)
Posts 280
19 Mar 2020 07:04


There is clearly lots of way to handle memory. However, on AmigaOS, if you need lots of dynamic memory allocation, one method is to allocate a large buffer called a pool, and then pick mem blocks from that buffer. Big interest is about not fragmenting the OS memory, and accelerate the process.
 
  See Exec CreatePool(), AllocPooled().
 
  API docs :
  EXTERNAL LINK  EXTERNAL LINK  EXTERNAL LINK 


Gunnar von Boehn
(Apollo Team Member)
Posts 4731
19 Mar 2020 07:42


Olle Haerstedt wrote:

  The reason I'm asking is because the performance gain of PHP  7
 

PHP is interpretive language might allocate and free all the time memory... So here allocation speed might matter.
Of course no real Amiga coder will program like this.
Real programs will allocate at start some memory, use it during execution, and free it at end.
No one with sane mind will Alloc and free memory all the time.
Memory allocation speed is fast on AMIGA, but making it even faster will have zero effect on most Amiga programs.
 
 


Olle Haerstedt

Posts 102
19 Mar 2020 09:41


Philippe Flype wrote:

There is clearly lots of way to handle memory. However, on AmigaOS, if you need lots of dynamic memory allocation, one method is to allocate a large buffer called a pool, and then pick mem blocks from that buffer. Big interest is about not fragmenting the OS memory, and accelerate the process.
 
  See Exec CreatePool(), AllocPooled().
 
  API docs :
  EXTERNAL LINK    EXTERNAL LINK    EXTERNAL LINK   

Cool, but also pools can be done both on the stack and the heap, right? On the stack of you know the size before the program runs.


John Hankinson

Posts 6
19 Mar 2020 09:42


There are a number of different levels to consider here with regard to memory allocation:

1) You should never by allocating/free'ing memory in any time critical code full-stop, so no new/malloc etc.

2) If you use something like .NET you'll find NEW is actually a very fast operation as it manages it's own memory and new'ing up objects is basically just a sub/add from it's own heap manager.

3) Always try to allocate large blocks and re-use the same memory if you can. The basic concept of Pools, which follows on from Flypes info. For example if you had entities in a game engine, instead of malloc'ing a new one every time you need, keep a pool of say 50 and mark which ones are available.

4) Prefer local variables over globals, the stack is a smart place to keep data, as the cache should be well primed against the area that (sp) is pointing at.. This isn't directly related to the question, but since you mentioned stacks.


Olle Haerstedt

Posts 102
19 Mar 2020 09:43


And also, if anyone has experience, how do you deal with memory management in assembler? Same as in C?


Olle Haerstedt

Posts 102
19 Mar 2020 10:17


John Hankinson wrote:

There are a number of different levels to consider here with regard to memory allocation:
 
  1) You should never by allocating/free'ing memory in any time critical code full-stop, so no new/malloc etc.
 
  2) If you use something like .NET you'll find NEW is actually a very fast operation as it manages it's own memory and new'ing up objects is basically just a sub/add from it's own heap manager.
 
  3) Always try to allocate large blocks and re-use the same memory if you can. The basic concept of Pools, which follows on from Flypes info. For example if you had entities in a game engine, instead of malloc'ing a new one every time you need, keep a pool of say 50 and mark which ones are available.
 
  4) Prefer local variables over globals, the stack is a smart place to keep data, as the cache should be well primed against the area that (sp) is pointing at.. This isn't directly related to the question, but since you mentioned stacks.

1) What's "critical" in a game? The actual game loop?

2) .NET is garbage collected so yeah, totally different beast.

3) Sounds good.

4) Sure.


Philippe Flype
(Apollo Team Member)
Posts 280
19 Mar 2020 11:16


Olle Haerstedt wrote:

Philippe Flype wrote:

  There is clearly lots of way to handle memory. However, on AmigaOS, if you need lots of dynamic memory allocation, one method is to allocate a large buffer called a pool, and then pick mem blocks from that buffer. Big interest is about not fragmenting the OS memory, and accelerate the process.
   
    See Exec CreatePool(), AllocPooled().
   
    API docs :
    EXTERNAL LINK    EXTERNAL LINK    EXTERNAL LINK   
 

 
  Cool, but also pools can be done both on the stack and the heap, right? On the stack of you know the size before the program runs.

Not using the Exec Pool functions. The master pool mem must be allocated using the links i pointed. If you want do this on your own (whatever stack or heap) you 'eed your own handling. I do not advise to trust the stack since it is controled by the user. You, as coder, you know how much mem you' ll need. Whereas stack can be very low if the user let the default (4096 bytes) or if he reduce it. Personally i'd not trust stack.


Philippe Flype
(Apollo Team Member)
Posts 280
19 Mar 2020 11:28


Olle Haerstedt wrote:

  And also, if anyone has experience, how do you deal with memory management in assembler? Same as in C?
 

   
  In assembler, like said before, there is plenty of ways to do whatever you want. But one important thing to know is about BSS hunks. A program when compiled contains a bunch of hunks of different types. There are hunks of code, hunks of data, also hunks of BSS which are automatically allocated memory on the fly at launch of the program. It saves you the need to allocate yourself the memory using OS functions (eg. Exec AllocMem or AllocVec or CreatePool/AllocPool), and no need to de-allocate it by hand (it will be freed at end of program).
   
  Basic Example:
   
 

  Main:
   
      Lea mymem,a0
      Blabla
      Rts
   
      SECTION mymem,BSS
   
    mymem:
   
      ds.b 4096
 
 
   
   
   
  Interest of BSS hunks is that your program wont be bigger once compiled. All is handled by Exec launcher. In opposite, there is SECTION mymem,DATA_C or DATA_F (Chip, or Fast mem) which will be appended to your program (growing final exe size - but have other advantages like proximity of the memory to allow PC relative access, eventually).
 
 
 
  One other thing to look at in assembly is the RSRESET (vasm, or devpac knows this command) to create structured fields/members for your own HEAP, or any allocated memory, it comes handy.
 
  Example :
 
 
 
      RSRESET
  f_field1 RS.L 1 ; one long
  f_field2 RS.W 2 ; two words
  f_field3 RS.L 1 ; one long
  f_field4 RS.L 1 ; one long
  f_SIZEOF RS.L 0 ; sizeof struct
 
  MAIN:
      lea    mystruct1(pc),a0
      move.l #1234,f_field1(a0)
      move.w #1234,f_field2(a0)
      move.w #1234,f_field3(a0)
      move.l #1234,f_field4(a0)
      blabla
      rts
 
      SECTION s0,DATA_F
 
  mystruct1:
      dc.b f_SIZEOF
 
  mystruct2:
      dc.b f_SIZEOF
 



Philippe Flype
(Apollo Team Member)
Posts 280
19 Mar 2020 11:50


Personally i'd not use stack mem for anything else than intrinsic stack use when push/pop registers.

In assembly, you generally push/pop your regs in your subroutines.

MAIN:
  bsr sub1
  bsr sub2
  rts

sub1:
  movem.l d2-d7/a2-a6,-(sp)
  blabla
  movem.l (sp)+,d2-d7/a2-a6
  rts

SP is Stack memory, here.
It is typically used for such cases.
Also, if there are subroutines which are used recursively, it will mechanically need more stack memory size. (beware).

Let's use Stack only for that, imho.
Own mem should be better own allocated mem (either section data, or section bss, or OS Allocs).


Samuel Devulder

Posts 246
19 Mar 2020 12:02


Olle Haerstedt wrote:

  Cool, but also pools can be done both on the stack and the heap, right?

  Nope! Generally speaking, stack is reserved for local variables or short-time lived objects. Once you return from the function, the stack frame is destroyeed and all pointers pointing back into one of the old stack-frames is dead. Generally speaking, stack allocation is used in a very restricted way when programming. Most memory allocation is either done statically via static arrays in C code (or BSS when doing asm), or dynamically with the help of the os.
 
Moreover, on amigaos the stack is small and not dynamic (not exactly true, but no need to be picky here), so better not allocate data on stack and forget alloca( EXTERNAL LINK ) if you are doing C.
 
For information, to work around slowness of OS AllocXXX() functions, it is possible to use malloc() replacement algorithms that performs much better than the original ones provided by the compiler. For instance, in Diablo (DevolutionX), I've managed to replace GCC's malloc() & friends functions by the ones of Doug Lea ( EXTERNAL LINK ) with positive impact on speed (yes C++ games kind of abuse dynamic allocation IMHO).


Olle Haerstedt

Posts 102
19 Mar 2020 12:13


Nope? What about buffer[1000] in main function, then pass it around as a pool?

What does that mean, stack is not dynamic on Amiga? There's great need to be picky! :D

dlalloc? I read about different algorithms on Wikipedia.


Olle Haerstedt

Posts 102
19 Mar 2020 12:14


Philippe Flype wrote:

Olle Haerstedt wrote:

 
Philippe Flype wrote:

  There is clearly lots of way to handle memory. However, on AmigaOS, if you need lots of dynamic memory allocation, one method is to allocate a large buffer called a pool, and then pick mem blocks from that buffer. Big interest is about not fragmenting the OS memory, and accelerate the process.
   
    See Exec CreatePool(), AllocPooled().
   
    API docs :
    EXTERNAL LINK      EXTERNAL LINK      EXTERNAL LINK     
 

 
  Cool, but also pools can be done both on the stack and the heap, right? On the stack of you know the size before the program runs.
 

 
  Not using the Exec Pool functions. The master pool mem must be allocated using the links i pointed. If you want do this on your own (whatever stack or heap) you 'eed your own handling. I do not advise to trust the stack since it is controled by the user. You, as coder, you know how much mem you' ll need. Whereas stack can be very low if the user let the default (4096 bytes) or if he reduce it. Personally i'd not trust stack.

Stack controlled by user? Where? System default? So no recursion then, I take it? ;)


Olle Haerstedt

Posts 102
19 Mar 2020 12:21


Philippe Flype wrote:

Olle Haerstedt wrote:

  And also, if anyone has experience, how do you deal with memory management in assembler? Same as in C?
 

   
  In assembler, like said before, there is plenty of ways to do whatever you want. But one important thing to know is about BSS hunks. A program when compiled contains a bunch of hunks of different types. There are hunks of code, hunks of data, also hunks of BSS which are automatically allocated memory on the fly at launch of the program. It saves you the need to allocate yourself the memory using OS functions (eg. Exec AllocMem or AllocVec or CreatePool/AllocPool), and no need to de-allocate it by hand (it will be freed at end of program).
   
  Basic Example:
   
 

  Main:
   
        Lea mymem,a0
        Blabla
        Rts
   
        SECTION mymem,BSS
   
    mymem:
   
        ds.b 4096
 
 
   
   
   
  Interest of BSS hunks is that your program wont be bigger once compiled. All is handled by Exec launcher. In opposite, there is SECTION mymem,DATA_C or DATA_F (Chip, or Fast mem) which will be appended to your program (growing final exe size - but have other advantages like proximity of the memory to allow PC relative access, eventually).
   
 
 
  One other thing to look at in assembly is the RSRESET (vasm, or devpac knows this command) to create structured fields/members for your own HEAP, or any allocated memory, it comes handy.
   
  Example :
 
 
 
      RSRESET
    f_field1 RS.L 1 ; one long
    f_field2 RS.W 2 ; two words
    f_field3 RS.L 1 ; one long
    f_field4 RS.L 1 ; one long
    f_SIZEOF RS.L 0 ; sizeof struct
   
    MAIN:
      lea    mystruct1(pc),a0
      move.l #1234,f_field1(a0)
      move.w #1234,f_field2(a0)
      move.w #1234,f_field3(a0)
      move.l #1234,f_field4(a0)
      blabla
      rts
   
      SECTION s0,DATA_F
   
    mystruct1:
      dc.b f_SIZEOF
   
    mystruct2:
      dc.b f_SIZEOF
 

Thanks! Gotta get my emulator up and running, maybe tonight. Trying it out on my RockPro64 (Pine64) ARM system. ^^


Philippe Flype
(Apollo Team Member)
Posts 280
19 Mar 2020 18:09


Olle Haerstedt wrote:

Philippe Flype wrote:

 
Olle Haerstedt wrote:

 
Philippe Flype wrote:

    There is clearly lots of way to handle memory. However, on AmigaOS, if you need lots of dynamic memory allocation, one method is to allocate a large buffer called a pool, and then pick mem blocks from that buffer. Big interest is about not fragmenting the OS memory, and accelerate the process.
     
      See Exec CreatePool(), AllocPooled().
     
      API docs :
      EXTERNAL LINK      EXTERNAL LINK      EXTERNAL LINK     
   

   
    Cool, but also pools can be done both on the stack and the heap, right? On the stack of you know the size before the program runs.
 

 
  Not using the Exec Pool functions. The master pool mem must be allocated using the links i pointed. If you want do this on your own (whatever stack or heap) you 'eed your own handling. I do not advise to trust the stack since it is controled by the user. You, as coder, you know how much mem you' ll need. Whereas stack can be very low if the user let the default (4096 bytes) or if he reduce it. Personally i'd not trust stack.
 

 
  Stack controlled by user? Where? System default? So no recursion then, I take it? ;)

Sure, the user can change the stack size inside the program icon. Or globally when launching from commandline.



Samuel Devulder

Posts 246
19 Mar 2020 20:50


Olle Haerstedt wrote:

Nope? What about buffer[1000] in main function, then pass it around as a pool?

This is bad coding. Especially for embedded systems. If you want permanent storage for your program, you don't need stack but BSS segment.

  What does that mean, stack is not dynamic on Amiga?

As written above, the stack is mainly set when a program is launched, so it isn't dynamic. Amiga has other similarities with embedded systems (small stack-sizes, lightweight task scheduler, no resource tracking, no memory protection, shared memory spaces betwwen all programs & os, etc.)

There's great need to be picky! :D

On amiga you can't approximate. You better be a good programmer and know what you are doing if you don't want your app to crash or make other apps crash randomly. That's the deal with OSes from the 80ies.


Olle Haerstedt

Posts 102
19 Mar 2020 21:34


Samuel Devulder wrote:

Olle Haerstedt wrote:

  Nope? What about buffer[1000] in main function, then pass it around as a pool?

  This is bad coding. Especially for embedded systems. If you want permanent storage for your program, you don't need stack but BSS segment.
 
 
  What does that mean, stack is not dynamic on Amiga?

  As written above, the stack is mainly set when a program is launched, so it isn't dynamic. Amiga has other similarities with embedded systems (small stack-sizes, lightweight task scheduler, no resource tracking, no memory protection, shared memory spaces betwwen all programs & os, etc.)
 
 
There's great need to be picky! :D

  On amiga you can't approximate. You better be a good programmer and know what you are doing if you don't want your app to crash or make other apps crash randomly. That's the deal with OSes from the 80ies.

Got it. Didn't hear about BSS before, so that's where I need to read up. Thanks for the feedback!



posts 31page  1 2