Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #31289 > unrolled thread

Region-based dynamic memory management idea

Back to article view | Back to comp.lang.forth

Contents

  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

Page 1 of 4  [1] 2 3 4  Next page →

#31289 — Region-based dynamic memory management idea

Hi all-

I discovered this old way of doing dynamic memory and think it could be made to be a big enhancement for Forth development.  In terms of dynamic memory management, something lightweight and non-intrusive, yet reasonably safe, and versatile enough to fulfill several duties without changing aspects of the Forth workflow negatively would be really nice.

With region-based memory management (for those of you who might not know) instead of allocating chunks piecemeal you request "regions" and then request memory from those, in a similar way to the dictionary.  Then when you are done, you free them, or reset them (but you don't necessarily have to.)  In a way it's like having a bunch of Forth dictionaries to compile data into instead of just one, but you can reclaim the memory in a non-LIFO fashion.  A dynamic memory system that exists in the dictionary would also be an advantage because it could yield a bunch of unique abilities and have fewer pitfalls than ALLOCATE & FREE.   

I've also been thinking that it'd be really helpful sometimes to have dynamic arrays, associative arrays and the option to grow, shrink, or reclaim memory buffers at run time - with a bonus that the buffers persist in turnkeys.  Thus the same words you write that use the memory manager could be used for static as well as dynamic allocation.  

Region-based memory management has the advantage of fairly efficient allocation and deallocation, and can/should be designed to not do any relocation of data - and for most uses I think it's actually not needed.  Also it's slightly safer than having handles for every object that can change location or otherwise become invalid; by being forced to group things into regions you allocate a lot more often than you deallocate, effectively creating a funnel to help you catch dangling pointers.  You can still run into dangling pointers a'course, but regions can help localize points of error.

Here are some cool capabilities that the scheme I'm about to provide a brief outline for would enable, make easier, or make more efficient in terms of memory use.  (Note that this is motivated toward game development.) 

\   dynamic arrays 
\   dictionaries (associative arrays) 
\   externalized string storage (for compiling arrays of strings) 
\   externalized code storage (for quotations) 
\   dynamic buffers (such as for building prototypes - though more than subregion probably won't be needed) 
\   preallocated object pools that can grow at runtime if needed 
\   file buffers that can shrink and grow during interactive development (interactive game development, in-game editors and other tools) 
\   log-keeping, gameplay recording 
\   multiple game stages, for instance for editor UI's, level building... 
\   store image and sound files in turnkey and reclaim the memory after loading them into the graphics driver (OpenGL or DirectX etc) at start of program 

Here's my proposed scheme. 

\ Regions consist of subregions allocated in 16k blocks. (configurable)  subregions are alloted as needed and are guaranteed consecutive memory regions, but regions as a whole are not.
\ subregion management array - 65536 subregions = 1MB = maximum 1GB of subregions (configurable)
\    in-use flag / size in # of blocks (0 = free)
\    link to next subregion
\    start address
\    next available offset

\ region handle -> first subregion
\ getting a handle -> circular search for a single free subregion.  when out of subregions create them at end of dictionary.
\ requesting memory -> circular search for needed consecutive free blocks.
\ freeing a region -> free all subregions by resetting flags
\ dictionary compilation within subregions [h 1 , 2 , 3 , h] (?)


And here are my ideas on how to implement a dynamic array and an associative array.  They make mention of a few words from my toolbelt.

\ dynamic array.
\    single region, many subregions
\    [] , EACH , <EACH  and SEEK use a hybrid approach to converting an index to an address, traversing linked subregions as needed.
\    as an array grows, more subregions are added after 16k is reached.  ( PUSH   TRIM )
\    SORT's implementation uses [] or address math depending on if the array is dynamic
\    when an array shrinks ( POP   TRIM ) a similar process happens freeing subregions in a stack-like fashion
\    supports any item size ... CELL is optimized.
\    perhaps uses a reserved region-pool for uninitialized arrays up to a certain small number of items



\ dictionary (associative array - key is string and value is a block of data of any size, or reference to another dictionary)
\    region: dynamic array of records
\       in-use flag
\       pointer to key
\       pointer to value
\       value pointer type: pointer to data, or pointer to another dictionary
\    region: dynamic array of keys
\       for simplicity keys are restricted to 31 characters max with 1 byte for the count
\       a simple circular search finds free key slots
\    region: data
\       a simple linked list:
\           size
\           next link / 0
\           in-use flag

I don't have a wordlist yet, these are just ideas intended to fuel discussion.

[toc] | [next] | [standalone]

#31293

On Sunday, 8 June 2014 07:35:49 UTC+1, Roger Levy  wrote:
> Hi all-
> 
> 
> 
> I discovered this old way of doing dynamic memory and think it could be made to be a big enhancement for Forth development.  In terms of dynamic memory management, something lightweight and non-intrusive, yet reasonably safe, and versatile enough to fulfill several duties without changing aspects of the Forth workflow negatively would be really nice.
> 
> 
> 
> With region-based memory management (for those of you who might not know) instead of allocating chunks piecemeal you request "regions" and then request memory from those, in a similar way to the dictionary.  Then when you are done, you free them, or reset them (but you don't necessarily have to.)  In a way it's like having a bunch of Forth dictionaries to compile data into instead of just one, but you can reclaim the memory in a non-LIFO fashion.  A dynamic memory system that exists in the dictionary would also be an advantage because it could yield a bunch of unique abilities and have fewer pitfalls than ALLOCATE & FREE.   
> 
> 
> 
> I've also been thinking that it'd be really helpful sometimes to have dynamic arrays, associative arrays and the option to grow, shrink, or reclaim memory buffers at run time - with a bonus that the buffers persist in turnkeys.  Thus the same words you write that use the memory manager could be used for static as well as dynamic allocation.  
> 
> 
> 
> Region-based memory management has the advantage of fairly efficient allocation and deallocation, and can/should be designed to not do any relocation of data - and for most uses I think it's actually not needed.  Also it's slightly safer than having handles for every object that can change location or otherwise become invalid; by being forced to group things into regions you allocate a lot more often than you deallocate, effectively creating a funnel to help you catch dangling pointers.  You can still run into dangling pointers a'course, but regions can help localize points of error.
> 
> 
> 
> Here are some cool capabilities that the scheme I'm about to provide a brief outline for would enable, make easier, or make more efficient in terms of memory use.  (Note that this is motivated toward game development.) 
> 
> 
> 
> \   dynamic arrays 
> 
> \   dictionaries (associative arrays) 
> 
> \   externalized string storage (for compiling arrays of strings) 
> 
> \   externalized code storage (for quotations) 
> 
> \   dynamic buffers (such as for building prototypes - though more than subregion probably won't be needed) 
> 
> \   preallocated object pools that can grow at runtime if needed 
> 
> \   file buffers that can shrink and grow during interactive development (interactive game development, in-game editors and other tools) 
> 
> \   log-keeping, gameplay recording 
> 
> \   multiple game stages, for instance for editor UI's, level building... 
> 
> \   store image and sound files in turnkey and reclaim the memory after loading them into the graphics driver (OpenGL or DirectX etc) at start of program 
> 
> 
> 
> Here's my proposed scheme. 
> 
> 
> 
> \ Regions consist of subregions allocated in 16k blocks. (configurable)  subregions are alloted as needed and are guaranteed consecutive memory regions, but regions as a whole are not.
> 
> \ subregion management array - 65536 subregions = 1MB = maximum 1GB of subregions (configurable)
> 
> \    in-use flag / size in # of blocks (0 = free)
> 
> \    link to next subregion
> 
> \    start address
> 
> \    next available offset
> 
> 
> 
> \ region handle -> first subregion
> 
> \ getting a handle -> circular search for a single free subregion.  when out of subregions create them at end of dictionary.
> 
> \ requesting memory -> circular search for needed consecutive free blocks.
> 
> \ freeing a region -> free all subregions by resetting flags
> 
> \ dictionary compilation within subregions [h 1 , 2 , 3 , h] (?)
> 
> 
> 
> 
> 
> And here are my ideas on how to implement a dynamic array and an associative array.  They make mention of a few words from my toolbelt.
> 
> 
> 
> \ dynamic array.
> 
> \    single region, many subregions
> 
> \    [] , EACH , <EACH  and SEEK use a hybrid approach to converting an index to an address, traversing linked subregions as needed.
> 
> \    as an array grows, more subregions are added after 16k is reached.  ( PUSH   TRIM )
> 
> \    SORT's implementation uses [] or address math depending on if the array is dynamic
> 
> \    when an array shrinks ( POP   TRIM ) a similar process happens freeing subregions in a stack-like fashion
> 
> \    supports any item size ... CELL is optimized.
> 
> \    perhaps uses a reserved region-pool for uninitialized arrays up to a certain small number of items
> 
> 
> 
> 
> 
> 
> 
> \ dictionary (associative array - key is string and value is a block of data of any size, or reference to another dictionary)
> 
> \    region: dynamic array of records
> 
> \       in-use flag
> 
> \       pointer to key
> 
> \       pointer to value
> 
> \       value pointer type: pointer to data, or pointer to another dictionary
> 
> \    region: dynamic array of keys
> 
> \       for simplicity keys are restricted to 31 characters max with 1 byte for the count
> 
> \       a simple circular search finds free key slots
> 
> \    region: data
> 
> \       a simple linked list:
> 
> \           size
> 
> \           next link / 0
> 
> \           in-use flag
> 
> 
> 
> I don't have a wordlist yet, these are just ideas intended to fuel discussion.

Bernd Paysan has done some work on this subject. He has
written a paper on it. Check out this google query:

https://www.google.com/search?q=region+based+memory+forth&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-GB:unofficial&client=seamonkey-a

There's also a video presentation by Anton Ertl, on YouTube, here:

http://www.youtube.com/watch?v=BpgmG--UD-Y

This link should take you to a paper on the subject:


http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0CCgQFjAB&url=http%3A%2F%2Fwww.complang.tuwien.ac.at%2Fanton%2Feuroforth%2Fef13%2Fpapers%2Fertl-regions.pdf&ei=zTiUU4mJG4XaOrXpgIgD&usg=AFQjCNFA5q4c5wtAFYdJNSrq7SkaW8eqMA&sig2=zolXkg5DxF5uLekuYfC09A&bvm=bv.68445247,d.ZWU

[toc] | [prev] | [next] | [standalone]

#31294

Correction. I think the paper was by Anton as well. 
My browser is giving me trouble. I'm using Seamonkey 
on a new Lubuntu installation and I don't have things
like PDF readers installed yet.

[toc] | [prev] | [next] | [standalone]

#31295

Roger Levy <roger.levy@gmail.com> writes:
>With region-based memory management (for those of you who might not know) i=
>nstead of allocating chunks piecemeal you request "regions" and then reques=
>t memory from those, in a similar way to the dictionary.  Then when you are=
> done, you free them, or reset them (but you don't necessarily have to.)  I=
>n a way it's like having a bunch of Forth dictionaries to compile data into=
> instead of just one, but you can reclaim the memory in a non-LIFO fashion.=

The main problem I see with this in Forth is that you have to pass the
region handle around.  But I think I have solved that by having a
current-region context-variable.  I.e.,

basic-block [: bla bla ;] with-region

where basic-block is a region handle, and bla bla can contain
ALLOCATEs (which now do region allocation).  The idea of using
ALLOCATE instead of, e.g., region-alloc is that people can use
existing source code with regions, and gain some advantages of using
regions without having to change the source code.  Also, people
writing source code don't have to commit to using regions.

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.

Anyway, I wanted to be finished with the implementation quite some
time ago, but there is always stuff that distracts me from it.  I
should be getting around to it this summer.

Mark Wills has already posted some links to my EuroForth talk: Here
are some others:

http://www.forth-ev.de/wiki/doku.php/en:events:euroforth-2013
(first talk).

http://www.complang.tuwien.ac.at/anton/euroforth/ef13/papers/
(second-to-last presentation).

Or direct:

Video: http://www.forth-ev.de/wiki/doku.php/events:euroforth-2013:rba
Slides: http://www.complang.tuwien.ac.at/anton/euroforth/ef13/papers/ertl-regions.pdf

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2014: http://www.euroforth.org/ef14/

[toc] | [prev] | [next] | [standalone]

#31296

Anton, actually I was intrigued to research into regions because of your talk. 

> The main problem I see with this in Forth is that you have to pass the
> region handle around.  But I think I have solved that by having a
> current-region context-variable.  I.e.,
> basic-block [: bla bla ;] with-region

Why does the handle need to be passed around?  Assuming that no data is moved around by the component, which is how I'd do it, handles should only be need to be stored in a variable or field.

Your context-based idea seems like a good one though.  

> ALLOCATEs (which now do region allocation).  The idea of using
> ALLOCATE instead of, e.g., region-alloc is that people can use
> existing source code with regions, and gain some advantages of using
> regions without having to change the source code.  

Right.  I guess that my idea of regions would be that they wouldn't map directly to traditional ALLOCATE.  The only justification I can provide for going that route is to avoid the complicated problems ...

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

Like this one.  I'm thinking that you'd be able to add or "drop" subregions to/from the end of the region and that's it.  I think that if you let go of the consecutive-area constraint you'll still have something quite useful.  To me the general idea is just to have similar functionality to the Forth dictionary,  like having several of them to allot memory from or comma into, so to speak.

> Anyway, I wanted to be finished with the implementation quite some
> time ago, but there is always stuff that distracts me from it.  I
> should be getting around to it this summer.

I'm tempted to give mine a go.  Since it's pretty clear in my mind.  I want to know more about the requirement to pass handles around though, could I be  overlooking something?

[toc] | [prev] | [next] | [standalone]

#31297

Roger Levy <roger.levy@gmail.com> writes:
>Anton, actually I was intrigued to research into regions because of your ta=
>lk.=20
>
>> The main problem I see with this in Forth is that you have to pass the
>> region handle around.  But I think I have solved that by having a
>> current-region context-variable.  I.e.,
>> basic-block [: bla bla ;] with-region
>
>Why does the handle need to be passed around?  Assuming that no data is mov=
>ed around by the component, which is how I'd do it, handles should only be =
>need to be stored in a variable or field.

Consider

str+ ( c-addr1 u1 c-addr2 u2 -- c-addr3 u3 )

It has to allocate memory for the result.  Which region handle should
it use?  Or should I pass a region-handle to it?

str+ ( c-addr1 u1 c-addr2 u2 region-id -- c-addr3 u3 )

And the same goes for any general-purpose word that allocates memory:
If you want to allocte memory from regions, you somehow have to tell
it which region to allocate from.  If you pass it explicitly, as in
the second str+, regions become cumbersome.  If you use global
variables (without managing them at a higher level), your code is only
useful for this one program (and even there changes might requires
changing the region handles in a number of places).

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2014: http://www.euroforth.org/ef14/

[toc] | [prev] | [next] | [standalone]

#31298

> Consider
> str+ ( c-addr1 u1 c-addr2 u2 -- c-addr3 u3 )
> 
> It has to allocate memory for the result.  Which region handle should
> it use?  Or should I pass a region-handle to it?
> 
> str+ ( c-addr1 u1 c-addr2 u2 region-id -- c-addr3 u3 )

I see.  That's a good example.  

It seems that if you like working this way (with spontaneous transparent dynamic allocation) but you don't like cleaning up after yourself, you simply need a garbage collector.  Seen from another angle, the problem arises because you want to force a square peg through a round hole.  Ask yourself what are regions getting you?  Since you neither want to have them be "transparent" to the task at hand nor do you want to acknowledge them explicitly by having to pass them around.

To illustrate my point, let's assume you don't even need regions for this problem.  Another solution to dynamic string manipulation say for the purpose of constructing file paths might be a large circular array of buffers.  This is basically what I do in my toolbelt and it works fine (with one caveat that I've been too lazy to solve) But it was very easy to implement and *does* work, which is the point.  That's what makes Forth amazing to me ;)

Diverging even more maybe, with regions, I could allocate the memory needed without having to name it, concatenate a bunch of strings (let's say because I need to pass a large array to an external DLL, or send a chunk of data over a network) and then free them all at once.  But I could use the same exact wordset that relies on regions in the dictionary to compile some strings  statically into a turnkey if I wanted/needed, which I just think is damn nifty :P

I guess what I'm saying is maybe regions aren't a replacement for ALL cases of dynamic memory management, just a uniquely useful, low footprint option?

> And the same goes for any general-purpose word that allocates memory:
> If you want to allocte memory from regions, you somehow have to tell
> it which region to allocate from.  If you pass it explicitly, as in
> the second str+, regions become cumbersome.  If you use global
> variables (without managing them at a higher level), your code is only
> useful for this one program (and even there changes might requires
> changing the region handles in a number of places).

Ah, I see.  I'll tell you, I think that the concept of regions is incompatible with the requirement to let people allocate strings in the way you described.  Regions must be managed in part by the user, from my understanding.  Indeed a "current region" setup seems the only way out at first glance but it leads to more problems.  Like for instance burdening the user with deciding when and where to put the "brackets", even though what they expect is total freedom.  My stance is that the restrictions with regions should be acknowledged and accepted.  The "invisible unlimited resource" is mythical.  It can't be done without tradeoffs somewhere.

[toc] | [prev] | [next] | [standalone]

#31299

BTW this what string concatenation looks like in my projects:

" Something" <$ " Some other thing" $+ " And another thing" $+ $> --> " Something Some other thing And another thing"

[toc] | [prev] | [next] | [standalone]

#31300

If you're interested in strings then have a look at my string library which uses a string stack:

http://turboforth.net/string_library.html

[toc] | [prev] | [next] | [standalone]

#31310

On Sunday, June 8, 2014 1:08:02 PM UTC-4, Mark Wills wrote:
> If you're interested in strings then have a look at my string library which uses a string stack:
> 
> 
> 
> http://turboforth.net/string_library.html

Good stuff, thank you for providing this!  I made it work in SwiftForth and intend to tweak it to my needs.  I have a feeling that it can be used for more than just strings, too.

I'm working on my region system now.  Turns out allocation is rather hairy if you want both good performance and good memory re-use e.g. not too much wasted memory and not too much fragmentation.  

[toc] | [prev] | [next] | [standalone]

#31327

On Monday, 9 June 2014 05:05:52 UTC+1, Roger Levy  wrote:
> Good stuff, thank you for providing this!  I made it work in 
> SwiftForth and intend to tweak it to my needs.  I have a feeling
> that it can be used for more than just strings, too.

Cool! That's why I published it, in the hope that someone would
find it useful. Note that the ANS version:

http://turboforth.net/downloads/docs/ANS_String_Lib.pdf

Should work in SwiftForth "out of the box". It's ANS Forth.
In order to ensure it works reliably on all ANS systems I only
used words from CORE , with just a few exceptions. Some words
come from CORE-EXT. The source is fully documented as to 
dependancies so if there is something that stops it working in 
SwiftForth then it should be easy to tweak.

Having said that, I did test it in SwiftForth, VFX, and GForth
and it worked fine in all of them; at least to the extent that I
tested it. When it has had some more "field testing" I'll publish
it on FLAG.

> 
> 
> 
> I'm working on my region system now.  Turns out allocation is 
> rather hairy if you want both good performance and good memory
> re-use e.g. not too much wasted memory and not too much
> fragmentation.

I'd be interested to see what you come up with. The next version
of the string library that I am planning to implement, when I have
a chance to sit down and design it, will feature an internal 
memory allocator/de-allocator and de-fragmenter. I might be able
to steal your code/ideas ;-) That's what libraries are for, 
which is why I like Hugh's library. Don't re-invent the wheel.

The current version of the string library doesn't require it, 
since it's a true string stack, so it grows/shrinks just the data
stack, but it doesn't fragment, just like the data stack. This is
of course a trade-off. It's slower that way, but (seems) very
robust. And the suite of commands, as you'll see from the docs is
quite extensive.

[toc] | [prev] | [next] | [standalone]

#31311

Mark Wills <markwills1970@gmail.com> writes:

> If you're interested in strings then have a look at my string library
> which uses a string stack:
>
> http://turboforth.net/string_library.html

That looks quite interesting, but could you please elaborate on what is
a reason for using a separate string stack? It seems that you could
implement all these string functions using just plain Forth stack,
couldn't you?

[toc] | [prev] | [next] | [standalone]

#31314

> That looks quite interesting, but could you please elaborate on what is
> 
> a reason for using a separate string stack? It seems that you could
> 
> implement all these string functions using just plain Forth stack,
> 
> couldn't you?

The data stack isn't intended for storing that data type.  It's for storing cell-width values and sometimes double-cells.

[toc] | [prev] | [next] | [standalone]

#31328

On Monday, 9 June 2014 05:27:31 UTC+1, Alexander Skobelev  wrote:
> That looks quite interesting, but could you please elaborate on
> what is a reason for using a separate string stack? It seems 
> that you could implement all these string functions using just 
> plain Forth stack, couldn't you?

Sure you could, but (IMO) it would be very awkward to use.

I assume you are talking about placing the contents of the string
on the stack? It's certainly possible (assuming your stack can 
go deep enough) but it means accessing data underneath the strings
is really difficult.

Perhaps you mean that only pointers are kept on the stack? That is
much more usable, but you then need to address the issue of 
storing the strings in a heap, and dealing with the fragmentation
that results from things like dropping strings. That's what I
plan to tackle next. More as an excersise for me than anything 
else... It's about the journey :-)

[toc] | [prev] | [next] | [standalone]

#31365

Mark Wills <markwills1970@gmail.com> writes:

> On Monday, 9 June 2014 05:27:31 UTC+1, Alexander Skobelev  wrote:
>> That looks quite interesting, but could you please elaborate on
>> what is a reason for using a separate string stack? It seems 
>> that you could implement all these string functions using just 
>> plain Forth stack, couldn't you?
>
> Sure you could, but (IMO) it would be very awkward to use.
>
> I assume you are talking about placing the contents of the string
> on the stack? It's certainly possible (assuming your stack can 
> go deep enough) but it means accessing data underneath the strings
> is really difficult.
>
> Perhaps you mean that only pointers are kept on the stack? That is
> much more usable, but you then need to address the issue of 
> storing the strings in a heap, and dealing with the fragmentation
> that results from things like dropping strings. That's what I
> plan to tackle next. More as an excersise for me than anything 
> else... It's about the journey :-)

Yes, I see now. I've mised the point you keep whole strings on the
stack, not just their pointers.

[toc] | [prev] | [next] | [standalone]

#31330

Roger Levy <roger.levy@gmail.com> writes:
>It seems that if you like working this way (with spontaneous transparent dy=
>namic allocation) but you don't like cleaning up after yourself, you simply=
> need a garbage collector.

Sure, GC offers the simplest interface.  However, garbage collection
with real-time requirements, multicores, and little type information
is still a research topic, and in any case, the implementation will be
very complex.

>To illustrate my point, let's assume you don't even need regions for this p=
>roblem.  Another solution to dynamic string manipulation say for the purpos=
>e of constructing file paths might be a large circular array of buffers.

Sure, we can always find special solutions for special problems.  And
that's part of the Forth philosophy.  But if we have a general
solution, and it's good enough, why not use it, at least at first.
You can devise the specialized solution later.

And STR+ was just an example.  I can make the same example with any
general-purpose word.  E.g., consider words for building linked lists
or trees.

>> And the same goes for any general-purpose word that allocates memory:
>> If you want to allocte memory from regions, you somehow have to tell
>> it which region to allocate from.  If you pass it explicitly, as in
>> the second str+, regions become cumbersome.  If you use global
>> variables (without managing them at a higher level), your code is only
>> useful for this one program (and even there changes might requires
>> changing the region handles in a number of places).
>
>Ah, I see.  I'll tell you, I think that the concept of regions is incompati=
>ble with the requirement to let people allocate strings in the way you desc=
>ribed.  Regions must be managed in part by the user, from my understanding.=
>  Indeed a "current region" setup seems the only way out at first glance bu=
>t it leads to more problems.  Like for instance burdening the user with dec=
>iding when and where to put the "brackets", even though what they expect is=
> total freedom.

Reads like a straw man argument to me.

>My stance is that the restrictions with regions should be =
>acknowledged and accepted.  The "invisible unlimited resource" is mythical.=
>  It can't be done without tradeoffs somewhere.

Sure there are tradeoffs.  And I think I have found a tradeoff that
makes region-based memory allocation usable in Forth.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2014: http://www.euroforth.org/ef14/

[toc] | [prev] | [next] | [standalone]

#31305

On Sun, 08 Jun 2014 11:05:36 -0400, Anton Ertl  
<anton@mips.complang.tuwien.ac.at> wrote:

> str+ ( c-addr1 u1 c-addr2 u2 -- c-addr3 u3 )
> It has to allocate memory for the result.

Wow, that really looks like the C way of string concatenation to me ...
Well, it's a Forth like attempt to do the same thing, anyway.

str+ would definately want to allocate new space from the sum of the
sizes for the prior space, instead of being passed a handle.  I'm not
sure how you'd go about freeing and re-using the space for the
original two strings.  I.e., str+ would seem to cause a memory leak in
the dictionary, but so does defining new definitions.  I quess it could
be argued as to whether it's truly a memory leak or just additional
allocation of dictionary space since the Forth dictionary is designed
as a heap.

Isn't the Forth way to leave both strings exactly where they already are?
I.e., if the strings are to be printed, you'd create a new word in Forth
to print both ...  Who needs string concatenation in Forth when you can
group things together with colon definitions?  I.e., if the strings aren't
useful separately, you'd create a new string in Forth.  Who needs string
concatenation in Forth when you can create a new colon definition?

Oh, you're trying to optimize Forth again aren't you?  Or, as Hugh
would say, you're trying to convert Forth into C, yet again.  I'm
beginning to think he's correct on that issue.  Everything of note
that you've discussed recently seems to be about converting Forth to C.
It makes me wonder if you're attempting to get Forth to compile on
a C compiler or at least it's optimizing backend.


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#31307

On 6/8/14 3:10 PM, Rod Pemberton wrote:
> On Sun, 08 Jun 2014 11:05:36 -0400, Anton Ertl
> <anton@mips.complang.tuwien.ac.at> wrote:
>
>> str+ ( c-addr1 u1 c-addr2 u2 -- c-addr3 u3 )
>> It has to allocate memory for the result.
>
> Wow, that really looks like the C way of string concatenation to me ...
> Well, it's a Forth like attempt to do the same thing, anyway.
>
> str+ would definately want to allocate new space from the sum of the
> sizes for the prior space, instead of being passed a handle.  I'm not
> sure how you'd go about freeing and re-using the space for the
> original two strings.  I.e., str+ would seem to cause a memory leak in
> the dictionary, but so does defining new definitions.  I quess it could
> be argued as to whether it's truly a memory leak or just additional
> allocation of dictionary space since the Forth dictionary is designed
> as a heap.
>
> Isn't the Forth way to leave both strings exactly where they already are?
> I.e., if the strings are to be printed, you'd create a new word in Forth
> to print both ...  Who needs string concatenation in Forth when you can
> group things together with colon definitions?  I.e., if the strings aren't
> useful separately, you'd create a new string in Forth.  Who needs string
> concatenation in Forth when you can create a new colon definition?

Well, it really depends on what you're trying to do with the strings. If 
you're displaying or printing them, doing first one then the next works 
just fine, no need to concatenate, just TYPE (or whatever) first one, 
then the next. If you're writing a text processing app, on the other 
hand, you really do need to be able to concatenate strings, and making 
colon definitions definitely will not help. In any case, IMO the "Forth 
way" is to do what the application/situation demands. It is certainly 
not traditional to dynamically allocate memory in such cases, but to 
work with defined buffers, although the ALLOCATION wordset can be 
helpful in some cases.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[toc] | [prev] | [next] | [standalone]

#31308

On Sunday, June 8, 2014 9:10:58 PM UTC-4, Rod Pemberton wrote:
 
>  ...  Who needs string concatenation in Forth when you can
> group things together with colon definitions?  I.e., if the strings aren't
> useful separately, you'd create a new string in Forth.  Who needs string
> concatenation in Forth when you can create a new colon definition?

I have used strings a lot in VisualFORTH, WebGen, and the 4E4th-IDE.

Since I didn't learn very much about Forth, if I need something, I look into Demos and other peoples work and use their definitions as input.

The definition for $+ which I use is this:

: $+      ( $1 n $2 n - pad n1+2 )
    temp$ place             \ Save old $2. It might be in pad.
    pad   place             \ Put $1 in place.
    temp$ count pad +place  \ Add old $2.
    pad count
;

This definition I got from Win32Forth\apps\Chess\TOOLSET.F - there it is called $concat, a long word. I prefer '$+' - this is somehow the Forth way of naming, I guess.

Normally strings have to be changed for different uses within the same word.
So I first allocate a dummy string, like this one:

create NewFolder     ," c:\temp\win32forth"  MAX-PATH allot 

This is the path to a dummy folder. To be used, I transfer the right folder to it:

: Folder>NewFolder      ( $ len -- )   \ needs path-string
   >r NewFolder 1+ r> dup >r NewFolder c! r> cmove 
;

When this is done, I can print this folder by writing

Newfolder count type

Handling of strings is easy this way, and it can't be done - or is very complicated - with colon definitions, because I cannot change the content of a colon definition. 
 
The only problem is the pad usage, because if different words use this $+ command, I need to save the string inside the word which uses $+

I heard so often that Forth lacks string command, but for me strings never have been a problem - since I found $concat at Win32Forth\apps\Chess\TOOLSET.F - it needs a little learning curve, but that's it.

Since I learned Forth by doing projects and not being a Forth guru, I may have missed the point. But if this is the thing what it is all about, I am glad and happy.

[toc] | [prev] | [next] | [standalone]

#31313

On 6/8/14 5:34 PM, visualforth@rocketmail.com wrote:
> On Sunday, June 8, 2014 9:10:58 PM UTC-4, Rod Pemberton wrote:
>
>>   ...  Who needs string concatenation in Forth when you can
>> group things together with colon definitions?  I.e., if the strings aren't
>> useful separately, you'd create a new string in Forth.  Who needs string
>> concatenation in Forth when you can create a new colon definition?
...
>
> Handling of strings is easy this way, and it can't be done - or is very complicated - with colon definitions, because I cannot change the content of a colon definition.

I agree. A string is inherently a data object, not a function. Colon 
definitions are really designed for functions. Forth is particularly 
good at letting you design and manage data objects as you wish, and it's 
best not to confuse the two.

> The only problem is the pad usage, because if different words use this $+ command, I need to save the string inside the word which uses $+

If this is your project, you control pad usage and can set rules 
according to your needs. If it's a group project, the group can :-) 
Systems aren't supposed to use PAD; it's a programmer convenience.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[toc] | [prev] | [next] | [standalone]

Page 1 of 4  [1] 2 3 4  Next page →

Back to top | Article view | comp.lang.forth

csiph-web