Re: simplest dynamic memory manager / allocator
- From: "The Beez'" <hansoft@xxxxxxxxxxx>
- Date: 11 May 2006 04:42:40 -0700
Dmitry Ponyatov wrote:
does anybody can give simple memory manager (with or without garbageThis one is one of the smallest you can imagine. It SHOULD be portable,
collector) extension ?
although I must admit I never tested it.
Most words are pretty standard, except:
: ARRAY CREATE CELLS ALLOT ;
: STRING CREATE CHARS ALLOT ;
: [*] * ; IMMEDIATE
: -ROT ROT ROT ;
It behaves as ANS has defined.
Hans Bezemer
Here's the manual:
-- snip --
Tweaking dynamic memory
====================
You might find that 4tH doesn't reserve much memory for dynamic
allocation. Dynamic
memory is allocated at the heap, which is 16 kB. You can increase it,
but first you have
to know how dynamic memory works. You can determine how much memory has
been
allocated by using the word 'ALLOCATED':
[needs lib/ansmem.4th]
50 allocate
abort" Out of memory" >r \ First allocation
r@ . ." allocates "
r@ allocated . ." bytes." cr
r> free
abort" Cannot free memory" \ Now free it
And it will print something like:
768 allocates 64 bytes.
64 bytes? I thought we allocated 50 bytes! Let's try another one:
[needs lib/ansmem.4th]
500 allocate
abort" Out of memory" >r \ First allocation
r@ . ." allocates "
r@ allocated . ." bytes." cr
r> free
abort" Cannot free memory" \ Now free it
This time it prints something like:
768 allocates 512 bytes.
As a matter of fact, 'ALLOCATED' will always return multiples of 64
bytes. That is a
consequence of how 4tH handles dynamic memory. 4tH divides dynamic
memory into
fragments. When you allocate memory, 4tH allocates as much fragments as
it needs to
provide you with the memory you requested. Then these fragments are
marked as 'taken'.
This marking is done in the Heap Allocation Table, which is located in
the Integer Segment.
Every fragment is represented by a cell in the HAT.
You can fine-tune this mechanism by defining some constants before
including "ansmem.4th".
This will create a heap with 512 fragments of 256 bytes, which is 128
kB:
512 constant #heap \ 512 fragments
256 constant /heap \ each fragment is 256 bytes
[needs lib/ansmem.4th]
500 allocate
abort" Out of memory" >r \ First allocation
r@ . ." allocates "
r@ allocated . ." bytes." cr
r> free
abort" Cannot free memory" \ Now free it
Try to keep the number of fragments low. 1024 seems like a nice upper
limit. If you need
that much memory, it is much better to handle it in larger chunks. This
avoids fragmentation
and keeps the time to search the HAT within acceptable limits.
-- snip --
Here's the code:
-- snip --
\ 4tH library - ANS MEMORY - Copyright 2004 J.L. Bezemer
\ You can redistribute this file and/or modify it under
\ the terms of the GNU General Public License
[UNDEFINED] allocate [IF]
[UNDEFINED] /heap [IF]
64 constant /heap
[THEN]
[UNDEFINED] #heap [IF]
256 constant #heap
[THEN]
#heap array HAT
#heap /heap [*] string heap
\ set HAT to zero
:noname #heap 0 do 0 HAT i th ! loop ; execute
\ calculate addresses
: HAT# cells HAT + ; ( n -- h#)
: addr>HAT heap - /heap / dup 0< 0= over #heap < and ;
( a -- h# f)
: freespace? ( #b n -- #b n f f)
over over + over true -rot \ set up loop parameters
do i HAT# @ 0<> if 0= leave then loop dup
; \ check all blocks, DUP flag
\ allocate space on heap
: allocate ( n -- a f)
dup #heap /heap [*] 1 [+] < swap
/heap -1 [+] + /heap / dup 0> rot and
if \ is request within limits?
#heap 1 [+] over - dup dup 0 \ is there enough free space?
do drop drop i freespace? if leave then loop
over /heap * chars heap + swap \ if so, update HAT and exit
if -rot tuck + swap do dup i HAT# ! loop false exit
else drop drop \ else drop values
then
then true \ and signal error
;
\ free space on heap
: free ( a -- f)
true over addr>HAT \ convert address
if \ if within limits
#heap swap do \ check contents of HAT
over i HAT# tuck @ = \ if allocated space
if 0 swap ! drop false else drop leave then
loop \ then update HAT else quit
else drop \ clean up stack
then nip
;
\ return allocated memory size
: allocated ( a -- n)
dup addr>HAT \ convert address
if \ if a valid address
tuck begin \ save the offset
over over HAT# @ = dup >r \ is it a real address?
if 1+ then \ increase count
dup #heap = r> 0= or \ limit has been reached?
until
else drop drop 0 dup dup \ discard garbage
then nip swap - /heap * \ calculate size in bytes
;
\ resize an allocated memory
block
: resize ( a1 n1 -- a2 f)
over swap ( a1 a1 n1)
over allocated ( a1 a1 n1 n2)
over allocate ( a1 a1 n1 n2 a2 f)
if ( a1 a1 n1 n2 a2)
drop drop drop drop true ( a1 f)
else ( a1 a1 n1 n2 a2)
>r min r@ swap cmove ( a1)
free drop r> false ( a2 -f)
then
;
[DEFINED] debug-mem [IF]
: .HAT #heap 0 do i dup . HAT# ? cr loop ;
[THEN]
[DEFINED] 4TH# [IF]
hide HAT
hide heap
hide HAT#
hide addr>HAT
hide freespace?
[THEN]
[THEN]
-- snip --
.
- References:
- simplest dynamic memory manager / allocator
- From: Dmitry Ponyatov
- simplest dynamic memory manager / allocator
- Prev by Date: Re: Sea of Processors
- Next by Date: Small Forth in BBC Basic
- Previous by thread: Re: simplest dynamic memory manager / allocator
- Next by thread: the throttle
- Index(es):
Relevant Pages
|
Loading
