Re: Region-based dynamic memory management idea

From	Bernd Paysan <bernd.paysan@gmx.de>
Newsgroups	comp.lang.forth
Subject	Re: Region-based dynamic memory management idea
Date	2014-06-08 21:47 +0200
Organization	1&1 Internet AG
Message-ID	<ln2ekd$i1k$1@online.de> (permalink)
References	<c942c546-3cfd-41af-bfd2-dd7d3b6a8fd6@googlegroups.com> <2014Jun8.152357@mips.complang.tuwien.ac.at>

Show all headers | View raw

Anton Ertl wrote:
> The main problem I see with my current interface is how to deal with
> RESIZE.  I have chosen one approach, but I am not entirely happy
> with it.  RESIZE also costs quite a bit in the implementation.

I think the problem you have is that you are under the impression that you 
need to know how big the block was before.  Let's assume for readability you 
use the normal dictionary words as words underneath the region based 
allocater, and you store the size of the allocation in the cell before:

: allocate ( size -- addr ior )  dup , here swap allot align 0 ;
: free ( addr -- ior ) drop 0 ;
: resize ( addr size -- addr1 ior )
  over dup cell- @ + aligned here = IF  \ last block can grow or shrink
      2dup + here - allot align over cell- ! 0  EXIT  THEN
  over cell- @ over u>= IF \ every block can shrink
      over ! 0 EXIT  THEN  \ won't remember how much it might grow
  swap >r allocate over r@ swap r> cell- @ move ;

This is optimizing shrinks and copies only the necessary amount on grows, 
and allows to grow the most recent block, which e.g. in the typical string 
accumulation pattern is a good idea.

Let's assume we don't want to pay extra cost for RESIZE if we do just normal 
allocate, and we make sure that newer regions are always allocated right 
behind the previous region (e.g. by using sbrk() as region allocation 
primitive):

: allocate ( size -- addr ior )  here swap allot align 0 ;
: free ( addr -- ior ) drop 0 ;
: resize ( addr size -- addr1 ior )
  dup allocate >r >r r@ swap move r> r> ;

This doesn't have a cost on allocate, and has a much simpler resize, which 
however doesn't optimize on common cases.  Yes, it does leak information 
from the other blocks into the newly resized block, but that's not a 
security relevant allocator (Gforth git head provides allocation for 
security critical stuff like secret keys with ALLOC+LOCK in unix/mmap.fs - 
this stuff will not even get swapped out, and it has guard pages).

I probably would go with the first solution, and add a word for fixed-size 
allocations (the "ALLOT" from above) that doesn't have the overhead, but 
returns memory that can't be resized.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

Thread

Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-07 23:35 -0700
  Re: Region-based dynamic memory management idea Mark Wills <markwills1970@gmail.com> - 2014-06-08 03:20 -0700
    Re: Region-based dynamic memory management idea Mark Wills <markwills1970@gmail.com> - 2014-06-08 03:39 -0700
  Re: Region-based dynamic memory management idea anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-06-08 13:23 +0000
    Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-08 07:44 -0700
      Re: Region-based dynamic memory management idea anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-06-08 15:05 +0000
        Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-08 09:01 -0700
          Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-08 09:32 -0700
            Re: Region-based dynamic memory management idea Mark Wills <markwills1970@gmail.com> - 2014-06-08 10:08 -0700
              Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-08 21:05 -0700
                Re: Region-based dynamic memory management idea Mark Wills <markwills1970@gmail.com> - 2014-06-09 06:47 -0700
              Re: Region-based dynamic memory management idea Alexander Skobelev <al.skobelev@gmail.com> - 2014-06-09 08:27 +0400
                Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-08 22:42 -0700
                Re: Region-based dynamic memory management idea Mark Wills <markwills1970@gmail.com> - 2014-06-09 06:53 -0700
                Re: Region-based dynamic memory management idea Alexander Skobelev <al.skobelev@gmail.com> - 2014-06-10 09:24 +0400
          Re: Region-based dynamic memory management idea anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-06-09 14:55 +0000
        Re: Region-based dynamic memory management idea "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-06-08 21:10 -0400
          Re: Region-based dynamic memory management idea "Elizabeth D. Rather" <erather@forth.com> - 2014-06-08 16:55 -1000
          Re: Region-based dynamic memory management idea visualforth@rocketmail.com - 2014-06-08 20:34 -0700
            Re: Region-based dynamic memory management idea "Elizabeth D. Rather" <erather@forth.com> - 2014-06-08 18:55 -1000
              Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-08 22:50 -0700
                Re: Region-based dynamic memory management idea "Elizabeth D. Rather" <erather@forth.com> - 2014-06-09 12:54 -1000
                Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-09 17:33 -0700
                Re: Region-based dynamic memory management idea Andrew Haley <andrew29@littlepinkcloud.invalid> - 2014-06-10 04:37 -0500
                Re: Region-based dynamic memory management idea bruce.mcfarling@gmail.com - 2014-06-19 13:38 -0700
              Re: Region-based dynamic memory management idea albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-06-09 12:40 +0000
          Re: Region-based dynamic memory management idea Andrew Haley <andrew29@littlepinkcloud.invalid> - 2014-06-09 05:21 -0500
          Re: Region-based dynamic memory management idea anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-06-10 16:50 +0000
            Re: Region-based dynamic memory management idea "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-06-10 17:36 -0400
            Re: Region-based dynamic memory management idea bruce.mcfarling@gmail.com - 2014-06-14 09:52 -0700
        Re: Region-based dynamic memory management idea humptydumpty <ouatubi@gmail.com> - 2014-06-11 03:44 -0700
          Re: Region-based dynamic memory management idea anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-06-11 16:33 +0000
            Re: Region-based dynamic memory management idea humptydumpty <ouatubi@gmail.com> - 2014-06-12 14:01 -0700
              Re: Region-based dynamic memory management idea anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-06-13 16:42 +0000
                Re: Region-based dynamic memory management idea humptydumpty <ouatubi@gmail.com> - 2014-06-13 13:45 -0700
                Re: Region-based dynamic memory management idea anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-06-14 09:56 +0000
                Re: Region-based dynamic memory management idea humptydumpty <ouatubi@gmail.com> - 2014-06-14 06:29 -0700
                Re: Region-based dynamic memory management idea Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2014-06-16 00:19 +0100
    Re: Region-based dynamic memory management idea Bernd Paysan <bernd.paysan@gmx.de> - 2014-06-08 21:47 +0200
      Re: Region-based dynamic memory management idea anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-06-09 15:24 +0000
        Re: Region-based dynamic memory management idea Mark Wills <markwills1970@gmail.com> - 2014-06-09 09:10 -0700
          Re: Region-based dynamic memory management idea anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-06-10 16:09 +0000
            Re: Region-based dynamic memory management idea BruceMcF <agila61@netscape.net> - 2014-06-14 14:04 -0700
        Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-09 10:02 -0700
          Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-09 10:08 -0700
            Re: Region-based dynamic memory management idea anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-06-10 15:31 +0000
              Re: Region-based dynamic memory management idea BruceMcF <agila61@netscape.net> - 2014-06-14 13:27 -0700
          Re: Region-based dynamic memory management idea anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-06-10 15:51 +0000
        Re: Region-based dynamic memory management idea bruce.mcfarling@gmail.com - 2014-06-14 09:09 -0700
          Re: Region-based dynamic memory management idea mhx@iae.nl - 2014-06-14 09:49 -0700
            Re: Region-based dynamic memory management idea bruce.mcfarling@gmail.com - 2014-06-14 10:09 -0700
            Re: Region-based dynamic memory management idea albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-06-14 19:36 +0000
              Re: Region-based dynamic memory management idea mhx@iae.nl - 2014-06-14 23:06 -0700
                Re: Region-based dynamic memory management idea albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-06-15 12:33 +0000
                Re: Region-based dynamic memory management idea BruceMcF <agila61@netscape.net> - 2014-06-15 12:11 -0700
                Re: Region-based dynamic memory management idea albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-06-15 19:38 +0000
  Re: Region-based dynamic memory management idea visualforth@rocketmail.com - 2014-06-08 17:42 -0700
    Re: Region-based dynamic memory management idea anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2014-06-09 15:43 +0000
    Re: Region-based dynamic memory management idea BruceMcF <agila61@netscape.net> - 2014-06-14 13:08 -0700
      Re: Region-based dynamic memory management idea "Elizabeth D. Rather" <erather@forth.com> - 2014-06-14 11:54 -1000
        Re: Region-based dynamic memory management idea BruceMcF <agila61@netscape.net> - 2014-06-15 12:36 -0700
      Re: Region-based dynamic memory management idea albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-06-15 11:59 +0000
        Re: Region-based dynamic memory management idea BruceMcF <agila61@netscape.net> - 2014-06-15 12:55 -0700
          Re: Region-based dynamic memory management idea BruceMcF <agila61@netscape.net> - 2014-06-15 13:02 -0700
  Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-12 10:26 -0700
  Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-19 22:57 -0700
    Re: Region-based dynamic memory management idea Mark Wills <markwills1970@gmail.com> - 2014-06-20 07:40 +0100
      Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-20 00:14 -0700
        Re: Region-based dynamic memory management idea bruce.mcfarling@gmail.com - 2014-06-20 20:17 -0700
          Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-21 08:51 -0700
            Re: Region-based dynamic memory management idea bruce.mcfarling@gmail.com - 2014-06-21 10:07 -0700
              Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-21 11:10 -0700
                Re: Region-based dynamic memory management idea bruce.mcfarling@gmail.com - 2014-06-21 12:17 -0700
                Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-21 12:39 -0700
                Re: Region-based dynamic memory management idea bruce.mcfarling@gmail.com - 2014-06-21 13:54 -0700
                Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-21 14:53 -0700
                Re: Region-based dynamic memory management idea albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-06-22 13:58 +0000
                Re: Region-based dynamic memory management idea BruceMcF <agila61@netscape.net> - 2014-06-22 15:26 -0700
  Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-21 13:25 -0700
  Re: Region-based dynamic memory management idea Roger Levy <roger.levy@gmail.com> - 2014-06-25 14:55 -0700

csiph-web