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 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#31333

On Monday, 9 June 2014 16:24:23 UTC+1, Anton Ertl  wrote:
> But for RESIZE it's not entirely clear how that should work in
> combination with the current region.  The memory to be RESIZEd might
> come from another region or may not be region-allocated at all.

Why might it come from another region? Why should that be allowed?
If a region has been requested and granted, surely another region
cannot be allowed to encroach into the space "owned" by another
region?

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

#31375

Mark Wills <markwills1970@gmail.com> writes:
>On Monday, 9 June 2014 16:24:23 UTC+1, Anton Ertl  wrote:
>> But for RESIZE it's not entirely clear how that should work in
>> combination with the current region.  The memory to be RESIZEd might
>> come from another region or may not be region-allocated at all.
>
>Why might it come from another region?

new-region [: bla new-region [: blub ;] do-region ;] do-region

Let's call the region created by the first new-region A, and the one
from the second do-region B.  If BLA ALLOCATEs some memory (from
region A), and BLUB calls RESIZE on that memory (while the current
region is B), then the region that is RESIZEd comes from a different
region than the current region.

> Why should that be allowed?

The context is that we have programs that were written with
ALLOCATE/FREE/RESIZE, and we want them to be useful in context with
regions (and regions in context with them). The question is not
whether we allow it, but whether it is conceivable that this occurs,
and what we should do in that case.

>If a region has been requested and granted, surely another region
>cannot be allowed to encroach into the space "owned" by another
>region?

I cannot follow you here.

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

#31544

On Tuesday, June 10, 2014 12:09:54 PM UTC-4, Anton Ertl wrote:

> The context is that we have programs that were written with
> ALLOCATE/FREE/RESIZE, and we want them to be useful in context with
> regions (and regions in context with them). The question is not
> whether we allow it, but whether it is conceivable that this occurs,
> and what we should do in that case.

One way to manage it is:
(1) Once you set-up the regions, the visible ALLOCATE is always from the current region if one is in context.
(1a) If the region space is contained within non-region space, which is most management to start with when trialing the approach, then allocations are outside of region space if the current region is null or points outside of the allowed region area. That follows directly if the entire region space is allocated using the underlying system ALLOCATE.

(2) FREE is always space made available in the original region of the allocation, so only matters for new allocations if that region is brought into focus as the current region.
(2a) FREE of an allocation outside region space calls the original underlying FREE.

(3) RESIZE stays within its original region when there is sufficient free space available in that region, otherwise a new daughter region is created for that allocation alone.
(3a) RESIZE of an allocation outside of region space calls the original underlying ALLOCATE, which will not touch the region space if the entirety of region space is ALLOCATEd with the system ALLOCATE when initialized.

Set up the region master list as a vector of n-tuples that contain the relevant information ~ base address, end address, space above, next daughter region, etc. ~ and sorted in memory order, with the region the base address of the region, so you can scan the list from end to front to find any region record by id, and scan the master list from end to front to find the first region base address that is less than the allocated memory address.

The region space is then describe by three cells: a double of the bottom and top allowed region address and a variable for the first open slot in the region master list.

The region space double is what the region-aware FREE and RESIZE check to see whether to use the underlying system FREE and RESIZE or the region-FREE and region-RESIZE should be used.

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

#31336

> The only reason why I am implementing RESIZE at all is so that people
> 
> can use code written for ALLOCATE/FREE/RESIZE in combination with
> 
> region-based allocation.
> 

I don't think you can.  Those words work on the assumption that memory can be moved around, and if you want regions to be more convenient than conventional memory managers and not be overly complicated, you must not move regions around.  Your solution was to force the user to pass handles around.  It's these handles that are tripping you up.

Here's an idea: allocate a single region specifically for ALLOCATE et al and implement a special memory management system that uses the memory supplied by the region.  That way, you can design regions themselves to work the most convenient way.  

Also, your STR+ must use ALLOCATE if you want STR+ to work the way you want.  It's that, or let the user provide a destination address for the concatenated string.  Using regions for a general purpose STR+ doesn't make a lot of sense.  You could have one region per string, but that would be hugely wasteful.  There are better solutions for strings.

For large data structures, as you mentioned, though, sure.  

In my plan, by "externalized strings" I meant a single region specifically for allocating strings statically to collect into arrays of string-pointers more conveniently.  I wouldn't even be freeing that region.  I think I might even add a flavor of region that cannot be freed by design.  Or not, since the region would be totally encapsulated anyway.

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

#31337

It just occurred to me; if you do want semi-transparent string allocation based on regions, you could let the user create their own heaps-in-regions using the same underpinnings that the overloaded ALLOCATE would.  Then you could implement dynamic strings in that heap using a hybrid approach.  Memory management is still up to the user unless you have some form of GC.  Otherwise, it's totally unclear when and where they are supposed to be freeing the region, which is by design supposed to be a slate-cleaning operation, from my understanding.  That's incompatible with modularity.  One module would clear the region and break another module.  So the onus is still on the user to free their strings when they are done with them.
  

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

#31373

Roger Levy <roger.levy@gmail.com> writes:
> Othe=
>rwise, it's totally unclear when and where they are supposed to be freeing =
>the region, which is by design supposed to be a slate-cleaning operation, f=
>rom my understanding.

The idea is that you define regions for things where you know that you
no longer need them after a certain time.

E.g., in a compiler, you may have some work on a per-basic-block
basis, and some work on a per-definition basis, and some work for the
whole program.  So you may create regions for basic blocks and regions
for definitions, and a region for the whole program.  If you know that
some data is no longer used after we are finished with the current
basic block, you allocate it in the current basic block region.  When
you are done with the basic block, you free the basic block region and
create a new basic block region.  Likewise for definitions.  And for
stuff that lives longer than a definition, you may put it in the
program region and it may not be deallocated until the process ends.

>  That's incompatible with modularity.  One module wou=
>ld clear the region and break another module.  So the onus is still on the =
>user to free their strings when they are done with them.

Yes, it's not garbage collection, so the user does have to deal with
freeing.

But I think it's compatible with modularity and actually supports it.
The programmer of the allocating word does not have to think about the
freeing, nor necessarily the programmer of its immediate caller.
Instead, these decisions are made at a higher level based on
application needs rather than distributing these decisions throughout
the whole code base.  Sounds like modularity to me.

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

#31543

On Tuesday, June 10, 2014 11:31:24 AM UTC-4, Anton Ertl wrote:
> But I think it's compatible with modularity and actually supports it. 
> The programmer of the allocating word does not have to think about the
> freeing, nor necessarily the programmer of its immediate caller.
> Instead, these decisions are made at a higher level based on
> application needs rather than distributing these decisions throughout
> the whole code base.  Sounds like modularity to me.

This points to a particular type of modularity which has a lot of appeal to me. Simple tasks on simple systems don't have to account for complications which are not problems for them because the complications involve things they don't even try to do. The same simple tasks can be called by more complex systems in a way that effectively manages the additional complications which arise from operating in a system where a lot of other things may be going on at the same time.

(1) Simplest level: I'm just working with buffers you've handed to me.

(2) Here, (1), let me grab some buffers for you to work with. Hang around, I'll call you when I need you.

(3) Here, (1) let me organize the use of some buffers for you. If I know for sure I'm not going to need any of them any more, I'll give the buffers back to the system.

(4) Here, (3), let me set up a section of memory for you to do that in. When I don't need you anymore, I'll toss everything I haven't stored for my own use.

If I have an, eg, 4K sub-ANS Forth system, I likely can just use ALLOT and PAD, because to do some other task which would conflict, I load that up as a separate 4K Forth system (either on top or over in another process thread) and do it in that other image. There often isn't space in the image for the Forth words to do both tasks anyway.

If I have a full featured desktop Forth, stepping from (2) to (3) to (4) can be part of a RAD process. PAD in that context is great for debugging processes to make sure you are doing what you want to be doing as you learn its memory management requirements, but it may be that you have no words in any finished modules that ever use PAD.

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

#31374

Roger Levy <roger.levy@gmail.com> writes:
>
>> The only reason why I am implementing RESIZE at all is so that people
>>=20
>> can use code written for ALLOCATE/FREE/RESIZE in combination with
>>=20
>> region-based allocation.
>>=20
>
>I don't think you can.  Those words work on the assumption that memory can =
>be moved around, and if you want regions to be more convenient than convent=
>ional memory managers and not be overly complicated, you must not move regi=
>ons around.

No, ALLOCATE does not work on that assumption; RESIZE may return the
resized memory elsewhere, which is not nice, but is the problem of the
programmer who uses RESIZE.  

>Your solution was to force the user to pass handles around.

The region ids (or handles, as you call them) are not there to allow
moving memory around (the way that handles in MacOS used to work).
They are just there to identify the region, so that you can have
several regions, and let the allocation go to the region with the
appropriate lifetime.

>Also, your STR+ must use ALLOCATE if you want STR+ to work the way you want=
>.  It's that, or let the user provide a destination address for the concate=
>nated string.  Using regions for a general purpose STR+ doesn't make a lot =
>of sense.

I think it does: The immediate caller of STR+ does not have to keep
track of the string for later freeing.  Instead, the application knows
at a higher level how long the strings constructed in some called word
will live (e.g., in a web application, these strings may be guaranteed
to be dead after the web page is sent out), and use regions
appropriately.

It loses some of the simplicity if some strings constructed in a word
live only for some time, and others for a different time.  Then you
have to deal more explicitly with regions, but I think it is still
better than having to keep track of every item to be freed
individually (or most workarounds for such situations).

As for a region that ALLOTs instead of some other basic memory
reservation stuff, that's certainly an interesting idea, but not the
focus of what I have in mind (i.e., my first implementation won't do
it).

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

#31532

On Monday, June 9, 2014 11:24:23 AM UTC-4, Anton Ertl wrote:
> The only reason why I am implementing RESIZE at all is so that people 
> can use code written for ALLOCATE/FREE/RESIZE in combination with
> region-based allocation.
> 
> But for RESIZE it's not entirely clear how that should work in
> combination with the current region.  The memory to be RESIZEd might 
> come from another region or may not be region-allocated at all.  And
> many uses of RESIZE are for things that live for the rest of the
> process.  But others do not.  So I had to make some assumptions, and
> they will be wrong for some uses, and I am unhappy about that.

What are the common uses for the RESIZE in the persistent data?

(1) Something that is being resized because its space that's being re-used and RESIZEd whenever its prior size was too small, eg, a "current filename" in a text editor. Allocate one per tab, free when the tab is closed ... but if you always have one tab open, to receive "New Document" if all files have been closed, you have one "current filename" that hangs around for the life of the editor process.

(2) Something persistent that grows to meet the requirement of that iteration of the current data, and then its right.

(3) And there is a persistent data space resource that is rightsized (or oversized enough so resize is not needed) from the start, so no RESIZE is needed.

Should the target be that the region handles the easy cases with low overhead, and tries to turn hard cases into easy cases?

The easy case is RESIZE when you are working on the last memory ALLOCATEd, and the RESIZE fits within the current region. Then you are just shifting the free pointer out a bit.

If its not the last memory ALLOCATEd but is in the current region, that's a little more overhead, but you know the memory range of the current region, so you can find out that its the current region directly, and then in the current region you have the list of memory spaces allocated in the current region, so you can find it. But what to do with it?

If its not the current region, you can first step back the chain and find which region contains that address, then in that region find that allocation. Which can be merged with the previous case, which are both in the class of "stuff was allocated after this stuff.

But if INSIDE an earlier region, its the top allocation in that region, and there is enough free space, that's also low cost, just push up the top free space pointer.

The fact that something is RESIZEd implies it is at risk to be RESIZEd again, so one strategy is to convert it to an easy case whenever it is done as a hard case. Create a daughter region of its original region, using an appropriate amount of buffer size rounding up for the current system, and its the only contents of the daughter region. This is the expensive operation, since its guaranteed to be a MOVE. But once its done, its a relatively low cost case. Link it into the list of regions just below the current region (eg, a two variable, ->first ->list linked list design pattern). For sanity, maintain the list in memory order.

For infrequently resized persistent data, that may well be good enough. But there is at least one scenario for frequently resized data that to my mind seems to merit special attention.

If a daughter region is RESIZEd beyond its current limit, and its the high region in currently ALLOCATEd memory, you can just push the bounder to the next size threshold, so that's a low cost operation. So for the case of an inner loop frequently having to resize a single piece of allocated memory will therefore only get the expensive RESIZE once and from there on be OK.

But a second inner loop scenario is when two or more ALLOCATEd memory regions are being RESIZEd. Consider a matrix operation where one ALLOCATEd region is an intermediate result matrix and a second is a result matrix. The operation asks for two memory spaces of adequate size and so the calling operation sets up two of "reasonable" size, and with RESIZE if needed to rightsize then the intermediate result and result buffers to the size of the original matrices passed to it. Now the calling operation is used on a data set that contains a number of entries that are bigger than "reasonable" size.

Now you can run into a leapfrog, since you resize IMResult and it needs more space so the original memory freed in the parent region and a new daughter region created for that "overflow resized" content, then you resize MResult and it needs more space and does the same thing. Now that's enough for three iterations and you are OK ~ maybe some RESIZE, but inside the space of the daughter regions ~ then you get a bigger pair of input matrices that overstep the daughter regions, so the region handler RESIZEs a new daughter region for IMResult, freeing the prior daughter region, and then it creates a new daughter region for MResult. And if it happens again, you are getting a progressively larger bubble below the pair of daughter regions, but never large enough to fit an entire new daughter region.

If you need more space and in "submerged" region has had space freed above it, it can first grow into that free space. So that is one cheaper RESIZE to aim for if you HAVE to do an expensive RESIZE.

So when freeing regions that are not the top region in the region-list, record the amount of free space available in that bubble in the next region region below, as part of its internal data. Now every region can know whether it has free space above and, by checking the next region linked below on the region list, free space below.

And so the cheap RESIZE is now any region that has sufficient free space above. When doing an expensive resize of a daughter region (and daughter regions only ever contain one ALLOCATION), first check if there is sufficient free space below so that the free space plus the current region is sufficient, and if so, move the current region into the bottom of that free space and give it the required size.

Now in the "leapfrog" scenario, IMResult is below MResult and packed, so on space-overflow RESIZE gets a new daughter region at the end of regionspace. And now, MResult when it has the space-overflow RESIZE coming up is most likely resized into the space left behind by IMResult, and there is no prospect of a progressively growing bubble.

So that gives a hierarchy of RESIZE costs, from cheapest to most expensive:

(1) RESIZE most recently allocated space in current region, which has sufficient free space.

(2) RESIZE "submerged" allocation in current region to a size smaller than its original allocation.

(3) RESIZE region and then most recently allocated space within region into available free regionspace.

(4)-(6) are (1)-(3) on a prior region, with additional overhead of locating the region containing an allocation.

~~~~~~~~ MOVE required below this level

(7) RESIZE a daughter region into space immediately below it if region plus free space accommodates the move, to the end of regionspace otherwise.

(8) RESIZE an allocation in a parent region, without sufficient space in its original allocation, freeing its space in the parent region and creating a new daughter region.

There's an advantage here to having the region data structures in its own dedicated region, since it allows the region handle to be an address into a region data structures, which never need resizing so are always where they were created. If the number of region records hits the last space for a region structure, you can create a new region of the same size, put the extension region information in the last slot, and the newest region being created in that new region.

The advantage is that if the allocation space of a region ends up completely emptied out by spinning off daughter regions, that allocation space can be recovered as free region space, and the first daughter region in the daughter region list promoted to the parent region by replacing the parent region in the record. That means that the region-id is stable even if the original parent region is all freed and returned to free region space.

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

#31535

On Saturday, June 14, 2014 6:09:24 PM UTC+2, bruce.m...@gmail.com wrote:
> On Monday, June 9, 2014 11:24:23 AM UTC-4, Anton Ertl wrote:
> 
> > The only reason why I am implementing RESIZE at all is so that people 
> > can use code written for ALLOCATE/FREE/RESIZE in combination with
> > region-based allocation.

I counted -- RESIZE is used in 11 of my 35,500 Forth files.
On top of that, I am pretty sure that if RESIZE was a performance
bottleneck, it would receive special treatment.

OTOH, I have been looking at the SPICE source code (C) recently,
and there resize and friends are used on practically every line,
including one place where it decreased performance by a factor
of 4 to 6 times.

-marcel

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

#31538

On Saturday, June 14, 2014 12:49:23 PM UTC-4, m...@iae.nl wrote:
> On Saturday, June 14, 2014 6:09:24 PM UTC+2, bruce.m...@gmail.com wrote:

> > On Monday, June 9, 2014 11:24:23 AM UTC-4, Anton Ertl wrote:
 
> >  
> > > The only reason why I am implementing RESIZE at all is so that people 
> > > can use code written for ALLOCATE/FREE/RESIZE in combination with
> > > region-based allocation.

> I counted -- RESIZE is used in 11 of my 35,500 Forth files. 
> On top of that, I am pretty sure that if RESIZE was a performance
> bottleneck, it would receive special treatment.

> OTOH, I have been looking at the SPICE source code (C) recently, 
> and there resize and friends are used on practically every line,
> including one place where it decreased performance by a factor
> of 4 to 6 times.

I must confess that in the hypothetical example I came up with for relatively frequent RESIZE, I wouldn't myself use RESIZE at all, I'd use FREE of the old buffers and allocate news buffers.

The only thing I have done where I can imagined myself using resize are edit buffers and the token stack on token stack overflow ... I normally use that for parsing WORD sized tokens out of a S$ buffer and not for result strings longer than 80 chars, so if it were to overflow in testing I'd likely change the process to make it more parsimonious with the token stack. But I could see using a tested filename handling word for a messy filename setting, creating a token stack that is big enough for my test case, and using RESIZE on overflow to not have to start the token stack out as ginormous.

And edit buffers and web page buffers sometimes accumulate more text than you at first expected, and having a functioning RESIZE do the move if needed is better than often less prone to error than having to re-invent that wheel.

But in neither case does speed of execution of the RESIZE matter all that much, since however long it takes for the first it is saving the time of rewriting the source for the new case, and in the second case its either somebody typing, or its downloading a string of http packets, which is patient about making the next packet request, and in either case a modest allotted buffer in the input process can buy quite a bit of time for RESIZE to work.

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

#31540

In article <c0807f9b-04ec-4eb7-b490-362a42ec6be2@googlegroups.com>,
 <mhx@iae.nl> wrote:
>On Saturday, June 14, 2014 6:09:24 PM UTC+2, bruce.m...@gmail.com wrote:
>> On Monday, June 9, 2014 11:24:23 AM UTC-4, Anton Ertl wrote:
>>
>> > The only reason why I am implementing RESIZE at all is so that people
>> > can use code written for ALLOCATE/FREE/RESIZE in combination with
>> > region-based allocation.
>
>I counted -- RESIZE is used in 11 of my 35,500 Forth files.
>On top of that, I am pretty sure that if RESIZE was a performance
>bottleneck, it would receive special treatment.
>
>OTOH, I have been looking at the SPICE source code (C) recently,
>and there resize and friends are used on practically every line,
>including one place where it decreased performance by a factor
>of 4 to 6 times.

The interesting thing you could tell us, if you where to rewrite
SPICE in Forth (I know you won't), how often would RESIZE be
used?

I've a pretty powerful editor here (I use it all the time, as in
right now ), and the source contains 17 malloc's, no resize.

>
>-marcel

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#31548

On Saturday, June 14, 2014 9:36:37 PM UTC+2, Albert van der Horst wrote:
> In article <c0807f9b-04ec-4eb7-b490-362a42ec6be2@googlegroups.com>,
>  <mhx@iae.nl> wrote:
> >OTOH, I have been looking at the SPICE source code (C) recently,
> >and there resize and friends are used on practically every line,
> >including one place where it decreased performance by a factor
> >of 4 to 6 times.
[..]
> The interesting thing you could tell us, if you where to rewrite
> SPICE in Forth (I know you won't), how often would RESIZE be
> used?

The NGSPICE sources use TREALLOC and 6 redefinitions or variants
of it about 172 times, always to increase the size of an existing
allocation. This was probably done to minimize memory use as much as
possible (SPICE output on disk or in memory can easily reach several
GBytes).

I would probably use RESIZE to increase existing allocations by a
factor of 2 or more (Knuth will know what the optimum constant is),
or use a fixed increment of say 4096 elements, and RESIZE the final
result downwards when necessary. I can do this because I am not
interested in GByte-size simulations, and would use memmap
somewhere.

The final redefinition of SPICE's malloc, realloc etc. links to the
Boehm allocator, but unfortunately this one is not ported to Windows
(CYGWIN64) yet. Also, the Boehm allocator would still be called
millions of times (even for my relatively small simulations).

> I've a pretty powerful editor here (I use it all the time, as in
> right now ), and the source contains 17 malloc's, no resize.

Let me guess: it handles realloc on its own by allocating large fixed
size buffers (with an intelligent guess about the size) as discussed
above?

-marcel

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

#31554

In article <90f3ce97-f238-423b-8ecb-d5283b3ffebd@googlegroups.com>,
 <mhx@iae.nl> wrote:
>On Saturday, June 14, 2014 9:36:37 PM UTC+2, Albert van der Horst wrote:
>> In article <c0807f9b-04ec-4eb7-b490-362a42ec6be2@googlegroups.com>,
>>  <mhx@iae.nl> wrote:
>> >OTOH, I have been looking at the SPICE source code (C) recently,
>> >and there resize and friends are used on practically every line,
>> >including one place where it decreased performance by a factor
>> >of 4 to 6 times.
>[..]
>> The interesting thing you could tell us, if you where to rewrite
>> SPICE in Forth (I know you won't), how often would RESIZE be
>> used?
>
>The NGSPICE sources use TREALLOC and 6 redefinitions or variants
>of it about 172 times, always to increase the size of an existing
>allocation. This was probably done to minimize memory use as much as
>possible (SPICE output on disk or in memory can easily reach several
>GBytes).
>
>I would probably use RESIZE to increase existing allocations by a
>factor of 2 or more (Knuth will know what the optimum constant is),
>or use a fixed increment of say 4096 elements, and RESIZE the final
>result downwards when necessary. I can do this because I am not
>interested in GByte-size simulations, and would use memmap
>somewhere.
>
>The final redefinition of SPICE's malloc, realloc etc. links to the
>Boehm allocator, but unfortunately this one is not ported to Windows
>(CYGWIN64) yet. Also, the Boehm allocator would still be called
>millions of times (even for my relatively small simulations).
>
>> I've a pretty powerful editor here (I use it all the time, as in
>> right now ), and the source contains 17 malloc's, no resize.
>
>Let me guess: it handles realloc on its own by allocating large fixed
>size buffers (with an intelligent guess about the size) as discussed
>above?

As far as I can tell no. Except for one place where a lot of 4 byte
items are allocated, each line seems to be allocated by itself. With
unlimited undelete, not much freeing is going on. This was
written by one of the most brilliant programmers I've ever known, and he
just relied on malloc to be any good. This 80's program handles Gbyte
files on my 64 bit machine gracefully. I merely recompiled.

To be fair in an editor if a line buffer is to be resized, that is
because the line has changed. So it make sense to just malloc a new
buffer of the correct size and build up the new line there.
So that is the reason realloc isn't much used, probably.

>
>-marcel
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#31562

On Sunday, June 15, 2014 8:33:39 AM UTC-4, Albert van der Horst wrote:
> In article <90f3ce97-f238-423b-8ecb-d5283b3ffebd@googlegroups.com>,
>  <mhx@iae.nl> wrote:

>>On Saturday, June 14, 2014 9:36:37 PM UTC+2, Albert van der Horst wrote:
>>> I've a pretty powerful editor here (I use it all the time, as in 
>>> right now ), and the source contains 17 malloc's, no resize.

>>Let me guess: it handles realloc on its own by allocating large fixed 
>>size buffers (with an intelligent guess about the size) as discussed 
>>above?
 
> As far as I can tell no. Except for one place where a lot of 4 byte 
> items are allocated, each line seems to be allocated by itself. With
> unlimited undelete, not much freeing is going on. This was
> written by one of the most brilliant programmers I've ever known, and he
> just relied on malloc to be any good. This 80's program handles Gbyte
> files on my 64 bit machine gracefully. I merely recompiled.

It likely didn't handle Gbyte files on systems commonly used in the 80's, since even virtual memory needs the storage space to hold the information ... but by the same token there would be a quite distinct shortage of GByte files to edit on those systems.

Still, the first place for an "allocate a line at a time" editor to turn if it was in a more constrained memory space system and the memory space began to be a problem (especially given unlimited undo) would be to write to an undo file as you go and recover space from the earliest deleted lines when needed ... and that wouldn't use RESIZE, it would use FREE.

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

#31566

In article <63f5406e-eeef-4174-a15f-fe220396c95c@googlegroups.com>,
BruceMcF  <agila61@netscape.net> wrote:
>On Sunday, June 15, 2014 8:33:39 AM UTC-4, Albert van der Horst wrote:
>> In article <90f3ce97-f238-423b-8ecb-d5283b3ffebd@googlegroups.com>,
>>  <mhx@iae.nl> wrote:
>
>>>On Saturday, June 14, 2014 9:36:37 PM UTC+2, Albert van der Horst wrote:
>>>> I've a pretty powerful editor here (I use it all the time, as in
>>>> right now ), and the source contains 17 malloc's, no resize.
>
>>>Let me guess: it handles realloc on its own by allocating large fixed
>>>size buffers (with an intelligent guess about the size) as discussed
>>>above?
>
>> As far as I can tell no. Except for one place where a lot of 4 byte
>> items are allocated, each line seems to be allocated by itself. With
>> unlimited undelete, not much freeing is going on. This was
>> written by one of the most brilliant programmers I've ever known, and he
>> just relied on malloc to be any good. This 80's program handles Gbyte
>> files on my 64 bit machine gracefully. I merely recompiled.
>
>It likely didn't handle Gbyte files on systems commonly used in the
>80's, since even virtual memory needs the storage space to hold the
>information ... but by the same token there would be a quite distinct
>shortage of GByte files to edit on those systems.
>
>Still, the first place for an "allocate a line at a time" editor to turn
>if it was in a more constrained memory space system and the memory space
>began to be a problem (especially given unlimited undo) would be to
>write to an undo file as you go and recover space from the earliest
>deleted lines when needed ... and that wouldn't use RESIZE, it would use
>FREE.

One of the very wise decisions in this editor was not to jump through
this kind of hoops. If you're on MSDOS (where it runs too!) your files
cannot be more than 64 kbyte in total. That adds to your suffering on
MSDOS, but the pain is so severe already, that it hardly matters.
Very Forthlike trade offs, I suppose.

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#31304

On Sunday, June 8, 2014 2:35:49 AM UTC-4, Roger Levy wrote:

> \ Regions consist of subregions allocated in 16k blocks. 

I am not familiar with memory allocation, but I have a question:
Can this stuff been done using blocks - with the size changed from 1k to 16k - as virtual memory? 

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

#31332

visualforth@rocketmail.com writes:
>On Sunday, June 8, 2014 2:35:49 AM UTC-4, Roger Levy wrote:
>
>> \ Regions consist of subregions allocated in 16k blocks. 
>
>I am not familiar with memory allocation, but I have a question:
>Can this stuff been done using blocks - with the size changed from 1k to 16k - as virtual memory? 

Blocks as virtual memory has always been a catchy phrase that held no
water.  You had to access this memory with block words, unlike true
virtual memory, where just @ and ! are enough.

Anyway, if that's good enough for you, sure, you can combine this idea
with the region idea in some way.  I don't really see a point these
days, though.

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

#31542

On Sunday, June 8, 2014 8:42:14 PM UTC-4, visua...@rocketmail.com wrote:
> I am not familiar with memory allocation, but I have a question:
 
> Can this stuff been done using blocks - with the size changed from 1k to 16k - as virtual memory?

What blocks did in classic Forth on 8-bit machines with 16 bit addresses is expand their effective address space, since you could have 64K distinct BLOCKS, each with 1K of RAM, for up to 64M of randomly accessible data in a two-stage access system.

But since Blocks were first and foremost to hold and maintain source, it wasn't common for Blocks to be treated as a pool of two-stage-access heap to be drawn on and released ... it was more common for specific Blocks to be given assigned roles, so that if a range of blocks was being used as de facto virtual memory, that range was reserved up front.

The simplest data block allocation was just to store the block number being used in some variable "and remember". After all, if you have that block number stored in a variable, you can just fetch and print out the variable to remember which block is being used for that. Better practice was to have Block 0 as a comment block which said which blocks were being used for what, and sometimes Block 1 for the normal blocks to load up for that disk (since these were often removable floppy disks).

Another simple approach is to slice off a set of blocks at the top, store their first and end block in a double variable, and update the block editor words to give you a warning and a y/n to proceed when editing in the data black range.

If you wanted to use 4K or 16K superblocks, and you want to reuse existing facilities, its a lot more robust to start out by just accepting the overhead of the double moves and write words to copy 4K or 16K of data to or from a range of blocks that you have allocated to data. If the approach proves useful, that is the time to copy the BLOCK word definitions and write a set of parallel SBLOCK word definitions, with buffer updating built to follow the scheme.

But you've got all the overhead of any other two-tier access system ~ you've got to set up where the window into the other data space is located, and manage how you make sure you have that window focused on the part you need at the time that you need it.

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

#31545

On 6/14/14 10:08 AM, BruceMcF wrote:
> On Sunday, June 8, 2014 8:42:14 PM UTC-4, visua...@rocketmail.com wrote:
>> I am not familiar with memory allocation, but I have a question:
>
>> Can this stuff been done using blocks - with the size changed from 1k to 16k - as virtual memory?

Forth blocks are traditionally units of mass storage (disk, tape, ...), 
not memory. 1K was the most useful unit of modularity (often 2 or 4 disk 
sectors, for example). Early native Forths mapped block numbers to disk 
sectors computationally, with no directory. This was a real reliability 
boon in the early 70's, when directory wipe-outs in DOS and MacOS were 
common.

> What blocks did in classic Forth on 8-bit machines with 16 bit addresses is expand their effective address space, since you could have 64K distinct BLOCKS, each with 1K of RAM, for up to 64M of randomly accessible data in a two-stage access system.
>
> But since Blocks were first and foremost to hold and maintain source, it wasn't common for Blocks to be treated as a pool of two-stage-access heap to be drawn on and released ... it was more common for specific Blocks to be given assigned roles, so that if a range of blocks was being used as de facto virtual memory, that range was reserved up front.

Well, starting in the earliest systems (1970-72) they held both source 
and data. By the late 70's we had a very powerful data base management 
system based on disk blocks, with files mapped to regions of disk.

> The simplest data block allocation was just to store the block number being used in some variable "and remember". After all, if you have that block number stored in a variable, you can just fetch and print out the variable to remember which block is being used for that. Better practice was to have Block 0 as a comment block which said which blocks were being used for what, and sometimes Block 1 for the normal blocks to load up for that disk (since these were often removable floppy disks).

Here's the way FORTH, Inc. and other traditional systems did it: A 
system configured some number of block buffers (at least 2, sometimes up 
to 32). Each had a status cell that recorded what block was in that 
buffer. Its sign was set if the block had been changed since being read 
from disk. Each user had a "current block" which was the default 
accessed either by the text editor (if source) or data base system if 
data. If you requested a different block, the system would first check 
the current buffers to see if it was in memory; if so, no disk access 
was required. If it had to be read, the "oldest" buffer would be 
selected. If its block had been changed, it was written, and then the 
requested block would be read. This method minimized the number of disk 
accesses, since that was the slowest thing that could happen.

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 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

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

csiph-web