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

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

Reclaiming Allocated Memory

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

Contents

  Reclaiming Allocated Memory Doug Hoffman <glidedog@gmail.com> - 2013-11-25 07:41 -0500
    Re: Reclaiming Allocated Memory Paul Rubin <no.email@nospam.invalid> - 2013-11-25 07:04 -0800
      Re: Reclaiming Allocated Memory albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-25 16:16 +0000
        Re: Reclaiming Allocated Memory Paul Rubin <no.email@nospam.invalid> - 2013-11-25 09:03 -0800
          Re: Reclaiming Allocated Memory Doug Hoffman <glidedog@gmail.com> - 2013-11-26 06:30 -0500
            Re: Reclaiming Allocated Memory AKK <akk@nospam.org> - 2013-11-26 13:07 +0100
      Re: Reclaiming Allocated Memory Doug Hoffman <glidedog@gmail.com> - 2013-11-26 05:11 -0500
    Re: Reclaiming Allocated Memory anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-04 16:46 +0000
      Re: Reclaiming Allocated Memory Doug Hoffman <glidedog@gmail.com> - 2013-12-05 06:43 -0500
        Re: Reclaiming Allocated Memory Paul Rubin <no.email@nospam.invalid> - 2013-12-05 06:30 -0800
          Re: Reclaiming Allocated Memory albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-05 14:37 +0000
            Re: Reclaiming Allocated Memory Paul Rubin <no.email@nospam.invalid> - 2013-12-05 07:21 -0800
          Re: Reclaiming Allocated Memory Doug Hoffman <glidedog@gmail.com> - 2013-12-06 04:57 -0500
            Re: Reclaiming Allocated Memory Paul Rubin <no.email@nospam.invalid> - 2013-12-06 07:38 -0800
              Re: Reclaiming Allocated Memory Doug Hoffman <glidedog@gmail.com> - 2013-12-07 06:14 -0500
        Re: Reclaiming Allocated Memory anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-05 18:14 +0000
          Re: Reclaiming Allocated Memory Doug Hoffman <glidedog@gmail.com> - 2013-12-06 04:58 -0500
            Re: Reclaiming Allocated Memory Bernd Paysan <bernd.paysan@gmx.de> - 2013-12-06 17:30 +0100
              Re: Reclaiming Allocated Memory Doug Hoffman <glidedog@gmail.com> - 2013-12-07 05:59 -0500
                Re: Reclaiming Allocated Memory anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-07 11:57 +0000
                  Re: Reclaiming Allocated Memory albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-07 17:48 +0000
                    Re: Reclaiming Allocated Memory Bernd Paysan <bernd.paysan@gmx.de> - 2013-12-07 19:15 +0100
                      Re: Reclaiming Allocated Memory anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-09 13:45 +0000
            Re: Reclaiming Allocated Memory anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-06 17:42 +0000

Page 1 of 2  [1] 2  Next page →

#26940 — Reclaiming Allocated Memory

The potential problems with using allocate/resize/free are well known. 
However, while it would be great to have garbage collection (GC) the 
problems of having an acceptable Forth GC seem difficult or not possible 
to solve.

I have settled on staying with the allocate/resize/free model.  Perhaps 
analogous to type-checking, which most Forths also don't have, when 
using manual memory reclamation one simply has to be careful and to 
thoroughly test.  I find it helps greatly to use a simple tool during 
development to check for memory leaks.  It works well.  One can have a 
Forth GC or even a region based memory utility, but from what I have 
seen the use of these are not at all straightforward and add a possibly 
significant burden to the programmer.

By using a Forth object system with the above manual memory reclamation 
scheme we can have, for example, an easy to use string package that 
integrates well with the rest of Forth, does not use GC, a region-based 
memory management scheme, reference counting, or string stacks.  Note 
how objects can keep the number of stack items small.  We can keep 
RESIZE and easily test for memory leaks.  Of course the object system is 
general purpose and can be used for many other things as well.


A string example:

0 [if]
\ general object creation/destruction
 >heap ( "class-name" -- obj ) \ create object using ALLOCATE
<free ( obj -- ) \ destroy object using FREE, thus reclaiming memory

\ possible string messages
s+: ( ... n -- obj c-a u ) \ concatenate n strings
@:  ( -- c-a u ) \ leave entire string on stack
size: ( -- n ) \ size of string
[then]

: dir  ( -- c-a u ) s" my-folder/" ;
: file ( -- c-a u ) s" my-file" ;

\ Case 1) reclaim memory immediately
: (open-path) ( ... n obj -- fileid obj )
   s+: r/o open-file throw swap ;
: open-path ( ... n -- fileid obj )
   heap> string (open-path) ;

file dir s" /" 3 open-path \ uses: /my-folder/my-file
<free \ => fileid


\ Case 2) reclaim memory later
: sdir  ( -- c-a u ) s" my-sub-folder/" ;

file sdir dir s" /" 4 open-path \ uses: /my-folder/my-sub-folder/my-file
value path2 \ => fileid
...
path2 <free \ performed anytime later

-Doug

[toc] | [next] | [standalone]

#26942

Doug Hoffman <glidedog@gmail.com> writes:
> ..., while it would be great to have garbage collection
> (GC) the problems of having an acceptable Forth GC seem difficult or
> not possible to solve.

I think you mentioned trying this:

  http://www.complang.tuwien.ac.at/forth/garbage-collection.zip

What are the main problems it faces?  I haven't tried it myself, but it
looks really nice, and the method it uses was originally implemented for
C, where it has had some success.

> By using a Forth object system with the above manual memory
> reclamation scheme we can have, for example, an easy to use string
> package that integrates well with the rest of Forth,

I'm having trouble believing such a system can be easy to use, if the
object references can be freely shared around the program.  C++ has
evolved towards dealing with this by explicitly invoked automatic
reference counting (the STL shared_ptr template) and other languages do
everything through pervasive refcounting (Python) or GC.  I think Forth
and C these days simply work best in applications where there's not much
use of dynamically managed memory.

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

#26943

In article <7x1u24o749.fsf@ruckus.brouhaha.com>,
Paul Rubin  <no.email@nospam.invalid> wrote:
>Doug Hoffman <glidedog@gmail.com> writes:
>> ..., while it would be great to have garbage collection
>> (GC) the problems of having an acceptable Forth GC seem difficult or
>> not possible to solve.
>
>I think you mentioned trying this:
>
>  http://www.complang.tuwien.ac.at/forth/garbage-collection.zip
>
>What are the main problems it faces?  I haven't tried it myself, but it
>looks really nice, and the method it uses was originally implemented for
>C, where it has had some success.
>
>> By using a Forth object system with the above manual memory
>> reclamation scheme we can have, for example, an easy to use string
>> package that integrates well with the rest of Forth,
>
>I'm having trouble believing such a system can be easy to use, if the
>object references can be freely shared around the program.  C++ has
>evolved towards dealing with this by explicitly invoked automatic
>reference counting (the STL shared_ptr template) and other languages do
>everything through pervasive refcounting (Python) or GC.  I think Forth
>and C these days simply work best in applications where there's not much
>use of dynamically managed memory.

Forth can do better than C++ IMO for a very principal reason.
C++ has this dynamic memory allocation built in. It must be there
and it must work in all C++ ever to be invented.

Forth extends the language and adapt the garbage collection for
strings to the application.

Let me try to sketch it in an Elisa program. Part of the strings are
temporary and are there to build a response. As soon as there is no
reference on the stack their storage can be collected. Then there is but
one input line buffer, and it is reused all the time.
Some strings are more permanent, such as a subject brought up by
the patient:
P: I'm sad because I wasn't nice to my mother
...
C: last time we were talking about your mother.
At some place "mother" was allocate at HERE.

The discipline about using strings is not a complicated one-size-fits-all
but it is part of the application. In the above there where three
different classes of strings.

This may also be the reason that general string packages have not
caught on in Forth. It is not Forth like to use 10 features of
a 100 feature package, then the next time use some other 10 features.
Investment in learning time which caveats are imposed by 90 non-used
features is not easily earned back.

Instead we reprogram the 10 features.

Compare this to the explanation of Elizabeth Rather about arrays.

: ARRAY CREATE CELLS ALLOT DOES> SWAP CELLS + ;

This is what is mostly needed. Now I typed this in with less effort
than needed to attach to a namespace in Java.

If I need an array of objects in my style of oo:

( ...) class object
...
endclass
5 CELLS CONSTANT |object|   \ Normally: replace 5 with a HERE trick.
: objects |object| * ;
: ARRAY CREATE objects ALLOT DOES> SWAP objects + ( ...) ;
Quite the same!

Now if I work with current objects I can fill in
   ^object !
at the dots.

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]

#26944

albert@spenarnc.xs4all.nl (Albert van der Horst) writes:
>>C++ ...automatic reference counting (the STL shared_ptr template)
> Forth can do better than C++ IMO for a very principal reason.
> C++ has this dynamic memory allocation built in. It must be there
> and it must work in all C++ ever to be invented.

I don't understand what you mean there.  shared_ptr is a template
defined in a library.  It's not part of the underlying C++ language.
C++ itself has an operator loading feature which means an object can
have some code that gets called when any given operation (including
assigment like a=b) gets called on the object, and a "~" operation
that gets called when an object goes out of scope.  So you can say

  int func(shared_ptr<Foo> x) {
     shared_ptr<Foo> y = x;
     ...
     otherfunc(y); ...
  }

The assignment "y = x" makes y and x point to the same object, and
increments the reference count in the object.  y gets passed to
otherfunc, which might or might not create further references to the
object.  Then func finishes, and y goes out of scope, automatically
decrementing the reference.  Or if func throws an exception, the
exception unwinding also decrements the reference.  Finally, if the
refcount goes to 0, the object is freed.  The programmer doesn't have to
track stuff at all, other than avoiding reference cycles.  It's almost
like GC.

I don't see how to do that in Forth, which doesn't have any notion of
types or scopes.  It takes a fair amount of compiler hair.

> The discipline about using strings is not a complicated one-size-fits-all
> but it is part of the application. In the above there where three
> different classes of strings.

Sure, fair enough, you can get a bit more performance by not gc'ing
everything.

> This may also be the reason that general string packages have not
> caught on in Forth.

It could also just be that Forth applications tend to not do much with
strings.

> Now if I work with current objects I can fill in
>    ^object !
> at the dots.

One of these days I'd like to figure out how to use a Forth object
package.  But, that still doesn't address the storage reclamation issue.

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

#26967

On 11/25/13 12:03 PM, Paul Rubin wrote:

> One of these days I'd like to figure out how to use a Forth object
> package.

One nice thing about OOP is the concepts transcend the language.  So if 
you understand OOP in one programming language you shouldn't have much 
trouble understanding it in Forth.  Perhaps you have heard of Python? 
Here is a Python class definition followed by the equivalent definition 
written Forth:

reference:
http://www.tutorialspoint.com/python/python_classes_objects.htm

\ *** begin Python ***
class Employee:
    empCount = 0

    def __init__(self, name, salary):
       self.name = name
       self.salary = salary
       Employee.empCount += 1

    def displayCount(self):
      print "Total Employee %d" % Employee.empCount

    def displayEmployee(self):
       print "Name : ", self.name,  ", Salary: ", self.salary

emp1 = Employee("Zara", 2000)
emp2 = Employee("Manni", 5000)
emp1.displayEmployee()
emp2.displayEmployee()
print "Total Employee %d" % Employee.empCount
\ *** end Python ***

\ *** begin Forth (FMS) ***
\ reference: http://soton.mpeforth.com/flag/fms/index.html
\ download: FMS-SI.zip Package
:class Employee
  priv
   variable empCount  0 empCount !
  pub
   string+ name \ embedded object-as-instance-variable
   ivar salary  \ instance variable primitive

   :m init: 1 empCount +! ;m
   :m set: ( c-addr len salary -- )
      salary !  name !: ;m
   :m displayCount
      cr ." Total Employee " empCount @ . ;m
   :m displayEmployee
      cr ." Name : " name p: ." , Salary: "
      salary @ . ;m
;class

Employee emp1
s" Zara" 2000 emp1 set:
emp1 displayEmployee
\ => Name : Zara, Salary: 2000

Employee emp2
s" Manni" 5000 emp2 set:
emp2 displayEmployee
\ => Name : Manni, Salary: 5000

emp1 displayCount
\ => Total Employee 2
emp2 displayCount
\ => Total Employee 2

empCount  \ error: undefined word
name      \ error: undefined word
salary    \ error: undefined word
\ *** end Forth ***

-Doug

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

#26968

Thank you for these examples.

However they also show that - at least to me - OOP does not "feel right" 
in Forth. IMO the major reason is the clumsiness of handling dynamic 
strings. In standard Forth they do net even exist as data primitive.

It is no counter-argument that the given example uses one string 
parameter for creating a fixed-length dictionary entry.

Andreas



On 26.11.2013 12:30, Doug Hoffman wrote:
> On 11/25/13 12:03 PM, Paul Rubin wrote:
>
>> One of these days I'd like to figure out how to use a Forth object
>> package.
>
> One nice thing about OOP is the concepts transcend the language.  So if
> you understand OOP in one programming language you shouldn't have much
> trouble understanding it in Forth.  Perhaps you have heard of Python?
> Here is a Python class definition followed by the equivalent definition
> written Forth:
>
> reference:
> http://www.tutorialspoint.com/python/python_classes_objects.htm
>
> \ *** begin Python ***
> class Employee:
>     empCount = 0
>
>     def __init__(self, name, salary):
>        self.name = name
>        self.salary = salary
>        Employee.empCount += 1
>
>     def displayCount(self):
>       print "Total Employee %d" % Employee.empCount
>
>     def displayEmployee(self):
>        print "Name : ", self.name,  ", Salary: ", self.salary
>
> emp1 = Employee("Zara", 2000)
> emp2 = Employee("Manni", 5000)
> emp1.displayEmployee()
> emp2.displayEmployee()
> print "Total Employee %d" % Employee.empCount
> \ *** end Python ***
>
> \ *** begin Forth (FMS) ***
> \ reference: http://soton.mpeforth.com/flag/fms/index.html
> \ download: FMS-SI.zip Package
> :class Employee
>   priv
>    variable empCount  0 empCount !
>   pub
>    string+ name \ embedded object-as-instance-variable
>    ivar salary  \ instance variable primitive
>
>    :m init: 1 empCount +! ;m
>    :m set: ( c-addr len salary -- )
>       salary !  name !: ;m
>    :m displayCount
>       cr ." Total Employee " empCount @ . ;m
>    :m displayEmployee
>       cr ." Name : " name p: ." , Salary: "
>       salary @ . ;m
> ;class
>
> Employee emp1
> s" Zara" 2000 emp1 set:
> emp1 displayEmployee
> \ => Name : Zara, Salary: 2000
>
> Employee emp2
> s" Manni" 5000 emp2 set:
> emp2 displayEmployee
> \ => Name : Manni, Salary: 5000
>
> emp1 displayCount
> \ => Total Employee 2
> emp2 displayCount
> \ => Total Employee 2
>
> empCount  \ error: undefined word
> name      \ error: undefined word
> salary    \ error: undefined word
> \ *** end Forth ***
>
> -Doug

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

#26965

On 11/25/13 10:04 AM, Paul Rubin wrote:
> Doug Hoffman <glidedog@gmail.com> writes:
>> ..., while it would be great to have garbage collection
>> (GC) the problems of having an acceptable Forth GC seem difficult or
>> not possible to solve.
>
> I think you mentioned trying this:
>
>    http://www.complang.tuwien.ac.at/forth/garbage-collection.zip
>
> What are the main problems it faces?

Albert van der Horst gives a good answer.  I would add that the 
mentioned GC extension imposes important restrictions on where the 
memory reference must reside.  Memory resizing is not supported.  I 
don't mean to criticize the author's code because it is very well done, 
but there are problems inherent to designing an add-on GC for Forth.


>> By using a Forth object system with the above manual memory
>> reclamation scheme we can have, for example, an easy to use string
>> package that integrates well with the rest of Forth,
>
> I'm having trouble believing such a system can be easy to use, if the
> object references can be freely shared around the program.

There is no free lunch.  One just has to be careful.  Some think it 
would also be nice if there were type checking in Forth.  Actually there 
is with StrongForth.  But there is pain involved and type checking and 
GC have not caught on in Forth for a reason.


> I think Forth
> and C these days simply work best in applications where there's not much
> use of dynamically managed memory.

Define "not much use".  On a desktop application, such as MacForth's 
built in editor, the application can be highly dynamic.

-Doug

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

#27139

Doug Hoffman <glidedog@gmail.com> writes:
>I have settled on staying with the allocate/resize/free model.  Perhaps 
>analogous to type-checking, which most Forths also don't have, when 
>using manual memory reclamation one simply has to be careful and to 
>thoroughly test.  I find it helps greatly to use a simple tool during 
>development to check for memory leaks.  It works well.

What tool do you use and how simple is it?  If you can detect a memory
leak, you can also collect garbage, so a memory leak detector is just
as complex.  If you can build a simple one, you can also build a
simple gargabe collector.

>One can have a 
>Forth GC or even a region based memory utility, but from what I have 
>seen the use of these are not at all straightforward and add a possibly 
>significant burden to the programmer.

The whole point of both garbage collection and region-based memory
allocation is to reduce the burden on the application programmer, in
particular the burden of keeping track of ALLOCATEd things, and when
they can be FREEd.

In particular, with garbage collection you ALLOCATE at will, and never
have to FREE.

Region-based allocation is between garbage collection and FREE: You
allocate things in particular regions, and then free the whole region.

>0 [if]
>\ general object creation/destruction
> >heap ( "class-name" -- obj ) \ create object using ALLOCATE
><free ( obj -- ) \ destroy object using FREE, thus reclaiming memory
>
>\ possible string messages
>s+: ( ... n -- obj c-a u ) \ concatenate n strings
>@:  ( -- c-a u ) \ leave entire string on stack
>size: ( -- n ) \ size of string
>[then]
>
>: dir  ( -- c-a u ) s" my-folder/" ;
>: file ( -- c-a u ) s" my-file" ;
>
>\ Case 1) reclaim memory immediately
>: (open-path) ( ... n obj -- fileid obj )
>   s+: r/o open-file throw swap ;
>: open-path ( ... n -- fileid obj )
>   heap> string (open-path) ;
>
>file dir s" /" 3 open-path \ uses: /my-folder/my-file
><free \ => fileid
>
>
>\ Case 2) reclaim memory later
>: sdir  ( -- c-a u ) s" my-sub-folder/" ;
>
>file sdir dir s" /" 4 open-path \ uses: /my-folder/my-sub-folder/my-file
>value path2 \ => fileid
>...
>path2 <free \ performed anytime later

I don't see any advantage from using an object here.  These examples
could be done just as easily with FREE.  I also don't see how this
makes freeing easier in other cases.  It seems to me that you have to
keep the object around until you want to free the memory, which does
not seem easier than just keeping the address to be freed around, on
the contrary: S+: returns an object in addition to the address; with
classical FREE you don't need to maintain the object.

- 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 2013: http://www.euroforth.org/ef13/

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

#27152

On 12/4/13 11:46 AM, Anton Ertl wrote:
> Doug Hoffman <glidedog@gmail.com> writes:
>> I have settled on staying with the allocate/resize/free model.  Perhaps
>> analogous to type-checking, which most Forths also don't have, when
>> using manual memory reclamation one simply has to be careful and to
>> thoroughly test.  I find it helps greatly to use a simple tool during
>> development to check for memory leaks.  It works well.
>
> What tool do you use and how simple is it?

\ *** begin mem tool
50000 constant mem-size \ choose a large enough size

create mem-list mem-size cells allot
mem-list mem-size cells erase

: list-bounds ( -- end beg ) mem-list mem-size cells +  mem-list ;

: store-ptr ( ptr -- )
   list-bounds do i @ 0= if i ! unloop exit then cell +loop
   true abort" no room left in mem-list" ;

: allocate ( n -- ptr ior )
   allocate
   2dup 0=
   if store-ptr
   else drop
   then ;

: free-ptr ( ptr -- )
   list-bounds do dup i @ = if 0 i ! drop unloop exit then
              cell +loop ;

: free ( ptr -- ior )
   dup free dup 0=
   if
     swap
     ( ior ptr ) free-ptr
   then ;

: resize-mem ( ptr2 ptr1 -- )
   list-bounds do dup i @ = if drop i ! unloop exit then
              cell +loop ;

: resize ( ptr1 n -- ptr2 ior | ptr1 ior )
   over >r
   resize
   dup 0=
   if ( ptr2 ior  )
     swap dup ( ior ptr2 ptr2 ) r@ =
        if r> drop ( ior ptr1 ) swap exit
        else
        ( ior ptr2 ) r@ ( ior ptr2 ptr1 ) over >r resize-mem r>
        ( ior ptr2)
        then
   then r> drop swap ;

: .mem 0 locals| cnt |
   list-bounds do i @ if cr cnt . i @ . cnt 1+ to cnt then
              cell +loop cr cnt . ." unFREEd pointers " ;

: clr-mem
   list-bounds do i @ if  i @ free throw 0 i ! then
              cell +loop ;
\ *** end mem tool

The tool is inefficient and only meant for use during development 
(analogous to an array index check).  Run the program and execute .MEM 
to see if all pointers have been freed.  Example:

: foo ( -- obj )
   heap> string { s }
   s" some" s !:
   s" text" s add: s
   ;

foo dup @: type \ => sometext
.mem
0 13965088
1 13734992
2 unFREEd pointers
<free .mem
0 unFREEd pointers



> If you can detect a memory
> leak, you can also collect garbage, so a memory leak detector is just
> as complex.  If you can build a simple one, you can also build a
> simple gargabe collector.

I don't think the above tool would work for that, but I could be wrong.


> The whole point of both garbage collection and region-based memory
> allocation is to reduce the burden on the application programmer, in
> particular the burden of keeping track of ALLOCATEd things, and when
> they can be FREEd.
>
> In particular, with garbage collection you ALLOCATE at will, and never
> have to FREE.

It would be wonderful if such a GC could work in Forth without extra 
effort by and restrictions for the programmer.  But from what I've seen 
the extra effort and restrictions that don't fit my programming style.


> Region-based allocation is between garbage collection and FREE: You
> allocate things in particular regions, and then free the whole region.
>
>> 0 [if]
>> \ general object creation/destruction
>>> heap ( "class-name" -- obj ) \ create object using ALLOCATE
>> <free ( obj -- ) \ destroy object using FREE, thus reclaiming memory
>>
>> \ possible string messages
>> s+: ( ... n -- obj c-a u ) \ concatenate n strings
>> @:  ( -- c-a u ) \ leave entire string on stack
>> size: ( -- n ) \ size of string
>> [then]
>>
>> : dir  ( -- c-a u ) s" my-folder/" ;
>> : file ( -- c-a u ) s" my-file" ;
>>
>> \ Case 1) reclaim memory immediately
>> : (open-path) ( ... n obj -- fileid obj )
>>    s+: r/o open-file throw swap ;
>> : open-path ( ... n -- fileid obj )
>>    heap> string (open-path) ;
>>
>> file dir s" /" 3 open-path \ uses: /my-folder/my-file
>> <free \ => fileid
>>
>>
>> \ Case 2) reclaim memory later
>> : sdir  ( -- c-a u ) s" my-sub-folder/" ;
>>
>> file sdir dir s" /" 4 open-path \ uses: /my-folder/my-sub-folder/my-file
>> value path2 \ => fileid
>> ...
>> path2 <free \ performed anytime later
>
> I don't see any advantage from using an object here.  These examples
> could be done just as easily with FREE.  I also don't see how this
> makes freeing easier in other cases.

The definition of <FREE is:

: <free  ( obj -- ) dup free: free throw ;

So the free: message is first sent to the object before the object 
itself is FREEd.  This gives the object the ability to first FREE any 
memory allocated within the object, nested to any level.  All objects 
are designed to do the right thing in response to free:.  In the foo 
example above one can see that <free resulted in two calls to FREE. 
Granted, not much saving of effort there.  But if the object were an 
array or list of allocated objects then a single <free could result in 
thousands of calls to free.

-Doug

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

#27156

Doug Hoffman <glidedog@gmail.com> writes:
> So the free: message is first sent to the object before the object
> itself is FREEd.  This gives the object the ability to first FREE any
> memory allocated within the object, nested to any level.

How does it know that it should do that, if there might be other
pointers around to the internal objects?  Also you mentioned a desire to
resize objects.  How do you do that, if the resize might relocate the
object, and there are shared pointers?  How do you go about tracking
them all?

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

#27158

In article <7xr49rpdz0.fsf@ruckus.brouhaha.com>,
Paul Rubin  <no.email@nospam.invalid> wrote:
>Doug Hoffman <glidedog@gmail.com> writes:
>> So the free: message is first sent to the object before the object
>> itself is FREEd.  This gives the object the ability to first FREE any
>> memory allocated within the object, nested to any level.
>
>How does it know that it should do that, if there might be other
>pointers around to the internal objects?  Also you mentioned a desire to
>resize objects.  How do you do that, if the resize might relocate the
>object, and there are shared pointers?  How do you go about tracking
>them all?

This hits the nail on the head. The main problem with garbage collection
is:"what is garbage". This may be answered in the general context of
Java programming, but in the general context of Forth it is not.
In a special context of Forth garbage, we need a special collector,
probably order of magnitude simpler than Java's.

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]

#27159

albert@spenarnc.xs4all.nl (Albert van der Horst) writes:
> In a special context of Forth garbage, we need a special collector,
> probably order of magnitude simpler than Java's.

Anton's implementation is probably the only practical approach for
Forth: the Boehm algorithm basically scans all reachable objects for
anything that might be a pointer to a GC'd object, and treats those
locations as non-garbage.  This is called an imprecise or conservative
collector, because it can mistake data for pointers and therefore
occasionally fail to free something that is actually garbage.  While
that may sound scary, it is indeed relatively simple, and it works
pretty well in practice.  It was originally written for C and is not
unique to Forth:

   http://www.hpl.hp.com/personal/Hans_Boehm/gc/

Java's GC (Oracle version) is very complicated and highly optimized,
works with parallel processes, etc.  Java could use a simpler GC,
including the Boehm GC, at a cost in performance.  GCJ in fact uses the
Boehm GC.

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

#27164

On 12/5/13 9:30 AM, Paul Rubin wrote:
> Doug Hoffman <glidedog@gmail.com> writes:
>> So the free: message is first sent to the object before the object
>> itself is FREEd.  This gives the object the ability to first FREE any
>> memory allocated within the object, nested to any level.
>
> How does it know that it should do that, if there might be other
> pointers around to the internal objects?

The programmer is responsible for keeping track of things.

> Also you mentioned a desire to
> resize objects.   How do you do that, if the resize might relocate the
> object, and there are shared pointers?

I don't do something that will corrupt an allocated memory pointer.

> How do you go about tracking them all?

The programmer is responsible for keeping track of things, just like the 
programmer is responsible for keeping track of everything else.

Maybe it depends on the complexity and type of program.  If one is 
writing something that is highly dynamic and in a style where memory 
pointers can become so intertwined that keeping track is too difficult, 
then a language other than Forth should be used.  I don't write such 
programs.

-Doug

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

#27166

Doug Hoffman <glidedog@gmail.com> writes:
>>> This gives the object the ability to first FREE any
>>> memory allocated within the object, nested to any level.
>> How does it know that it should do that,
> The programmer is responsible for keeping track of things.

You mean when you free an object, you have to tell the object exactly
which of its internal objects it should also free, and so on
recursively?  That sounds painful.

>> if the resize might relocate the object,
> I don't do something that will corrupt an allocated memory pointer.

I don't understand what resizing is supposed to do then, unless it's a
pure ALLOT-like allocator and you haven't allocated any further objects
between the original allocation and the resize.

> If one is writing something that is highly dynamic and in a style
> where memory pointers can become so intertwined that keeping track is
> too difficult, then a language other than Forth should be used.

I haven't tried Anton's GC but it really does sound pretty workable,
especially with some implementation-specific hacks to deal with stuff
like scanning the locals.  It even be worth writing something into the
next standard about it.

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

#27171

On 12/6/13 10:38 AM, Paul Rubin wrote:
> Doug Hoffman <glidedog@gmail.com> writes:
>>>> This gives the object the ability to first FREE any
>>>> memory allocated within the object, nested to any level.
>>> How does it know that it should do that,
>> The programmer is responsible for keeping track of things.
>
> You mean when you free an object, you have to tell the object exactly
> which of its internal objects it should also free, and so on
> recursively?  That sounds painful.

I suppose one could design an object that works that way but I wouldn't 
recommend it.  I've always designed objects such that the correct 
FREEing behavior is built in in response to a <free.


>>> if the resize might relocate the object,
>> I don't do something that will corrupt an allocated memory pointer.
>
> I don't understand what resizing is supposed to do then,

I think we have miss-communicated somewhere because I don't follow what 
you aren't understanding.


>> If one is writing something that is highly dynamic and in a style
>> where memory pointers can become so intertwined that keeping track is
>> too difficult, then a language other than Forth should be used.
>
> I haven't tried Anton's GC but it really does sound pretty workable,
> especially with some implementation-specific hacks to deal with stuff
> like scanning the locals.  It even be worth writing something into the
> next standard about it.

Anyone can submit an Rfd.

-Doug

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

#27160

Doug Hoffman <glidedog@gmail.com> writes:
>On 12/4/13 11:46 AM, Anton Ertl wrote:
>> Doug Hoffman <glidedog@gmail.com> writes:
>>> I find it helps greatly to use a simple tool during
>>> development to check for memory leaks.  It works well.
>>
>> What tool do you use and how simple is it?
[code snipped]
>The tool is inefficient and only meant for use during development 
>(analogous to an array index check).  Run the program and execute .MEM 
>to see if all pointers have been freed.  Example:
>
>: foo ( -- obj )
>   heap> string { s }
>   s" some" s !:
>   s" text" s add: s
>   ;
>
>foo dup @: type \ => sometext
>.mem
>0 13965088
>1 13734992
>2 unFREEd pointers
><free .mem
>0 unFREEd pointers

Ok, so this just lists all the unfreed memory, and you would use it at
the end of the program.  But right at the end of the program it just
costs (sometimes dearly, see below) to free memory, so you should not
free the memory reported by that tool, unless it should have been
freed earlier.  Unfortunately the use of such tools encourages
programmers to free everything at the end.

As for costing dearly: Mozilla used to consume huge amounts of memory
with some usage patterns, much of which was swapped out to disk.  When
I wanted to quit Mozilla, it took many minutes of disk activity
(making the rest of the computer sluggish) before it finally exited.
Apparently it went through all that memory it had allocated and freed
it (and paged it in in the process) and only then it exited (which
unmaps all the memory automatically without paging it in).

>> The whole point of both garbage collection and region-based memory
>> allocation is to reduce the burden on the application programmer, in
>> particular the burden of keeping track of ALLOCATEd things, and when
>> they can be FREEd.
>>
>> In particular, with garbage collection you ALLOCATE at will, and never
>> have to FREE.
>
>It would be wonderful if such a GC could work in Forth without extra 
>effort by and restrictions for the programmer.  But from what I've seen 
>the extra effort and restrictions that don't fit my programming style.

Yes, there are some restrictions on the way you keep the addresses of
allocated memory:

a) Such addresses must not reside (exclusively) on the return stack or
in a local.  That's because the garbage collector is a standard
program, and standard programs cannot access all of the return stack
and all locals.  With system-specific changes this restriction can be
lifted.

b) Such addresses in the dictionary must reside in places declared as
root-addresses.  Again, there is no standard way to access all of the
dictionary, but with system-specific changes one could use all of the
dictionary as potential roots; besides being non-standard, this would
lead to longer garbage collection times and possibly to more garbage
being kept around (from spurious pointers).

c) In the allocated memory the addresses must reside at naturally
aligned boundaries.  That's also a portability requirement (there is
hardware that requires this), but one could make it configurable (so
one could also treat unaligned cells as potential addresses on
hardware that supports this).  Dropping this requirement would again
slow the garbage collector down and possibly increase the garbage that
is kept around.

d) An allocated object is only kept alive by a pointer to the start of
the object.  This requirement could be dropped, again at a cost in
garbage collection time and at a potential increase in garbage that is
kept around.

Which of these restrictions don't fit your programming style?

>> I don't see any advantage from using an object here.  These examples
>> could be done just as easily with FREE.  I also don't see how this
>> makes freeing easier in other cases.
>
>The definition of <FREE is:
>
>: <free  ( obj -- ) dup free: free throw ;
>
>So the free: message is first sent to the object before the object 
>itself is FREEd.  This gives the object the ability to first FREE any 
>memory allocated within the object, nested to any level.  All objects 
>are designed to do the right thing in response to free:.  In the foo 
>example above one can see that <free resulted in two calls to FREE. 
>Granted, not much saving of effort there.  But if the object were an 
>array or list of allocated objects then a single <free could result in 
>thousands of calls to free.

Ok, so you are doing region-based allocation here, but use an object
as a region handle.

- 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 2013: http://www.euroforth.org/ef13/

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

#27165

On 12/5/13 1:14 PM, Anton Ertl wrote:
> Doug Hoffman <glidedog@gmail.com> writes:

> Unfortunately the use of such tools encourages
> programmers to free everything at the end.

Agreed.  Probably one should test and if that is a problem redesign so 
more freeing is done sooner if possible.


>> It would be wonderful if such a GC could work in Forth without extra
>> effort by and restrictions for the programmer.  But from what I've seen
>> the extra effort and restrictions don't fit my programming style.
>
> Yes, there are some restrictions on the way you keep the addresses of
> allocated memory:
>
> a) Such addresses must not reside (exclusively) on the return stack or
> in a local.  That's because the garbage collector is a standard
> program, and standard programs cannot access all of the return stack
> and all locals.  With system-specific changes this restriction can be
> lifted.
>
> b) Such addresses in the dictionary must reside in places declared as
> root-addresses.  Again, there is no standard way to access all of the
> dictionary, but with system-specific changes one could use all of the
> dictionary as potential roots; besides being non-standard, this would
> lead to longer garbage collection times and possibly to more garbage
> being kept around (from spurious pointers).
>
> c) In the allocated memory the addresses must reside at naturally
> aligned boundaries.  That's also a portability requirement (there is
> hardware that requires this), but one could make it configurable (so
> one could also treat unaligned cells as potential addresses on
> hardware that supports this).  Dropping this requirement would again
> slow the garbage collector down and possibly increase the garbage that
> is kept around.
>
> d) An allocated object is only kept alive by a pointer to the start of
> the object.  This requirement could be dropped, again at a cost in
> garbage collection time and at a potential increase in garbage that is
> kept around.

e) RESIZE may not be not available without even more effort (extra 
indirection?  manual copying of contents from old to new?).


> Which of these restrictions don't fit your programming style?

a), b), and e) would be a problem for me.


>> : <free  ( obj -- ) dup free: free throw ;

> Ok, so you are doing region-based allocation here, but use an object
> as a region handle.

Yes.  Except a true region-based scheme has the advantage of fast 
freeing compared to the above even after a large number of allocations, 
if I understand correctly.  The lack of a resize may be a disadvantage.

-Doug

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

#27167

Doug Hoffman wrote:
> e) RESIZE may not be not available without even more effort (extra
> indirection?  manual copying of contents from old to new?).

In a simple allocater like the one for region based memory, you can shrink 
all objects in place, and to grow them, you need to copy them to a new 
location, unless they are the last allocated object (in which case growing 
them is almost for free).

Of course if you want to access objects that can resize, you need a pointer 
for that, and you need to adjust that pointer with the return value of 
resize (the new location).

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

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

#27170

On 12/6/13 11:30 AM, Bernd Paysan wrote:
> Doug Hoffman wrote:
>> e) RESIZE may not be not available without even more effort (extra
>> indirection?  manual copying of contents from old to new?).
>
> In a simple allocater like the one for region based memory, you can shrink
> all objects in place, and to grow them, you need to copy them to a new
> location, unless they are the last allocated object (in which case growing
> them is almost for free).

That last point is a good one.  Thanks.

> Of course if you want to access objects that can resize, you need a pointer
> for that, and you need to adjust that pointer with the return value of
> resize (the new location).

Yes.  That's the way a pointer object (class PTR) works in the provided 
FMS example classes.

-Doug

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

#27172

Doug Hoffman <glidedog@gmail.com> writes:
>On 12/6/13 11:30 AM, Bernd Paysan wrote:
>> In a simple allocater like the one for region based memory, you can shrink
>> all objects in place, and to grow them, you need to copy them to a new
>> location, unless they are the last allocated object (in which case growing
>> them is almost for free).
>
>That last point is a good one.  Thanks.

Yes, if you RESIZE the last allocated thing, and the result fits in
the current block, then it's cheap.  But with my current
implementation, every other RESIZE, even if it shrinks, is expensive:
I don't know the old size of the resized thing, so I always allocate
new memory, and the amount of memory I copy there is usually bigger
(possibly much bigger) than the old size.

I have been thinking about a different implementation for resized
stuff, but if RESIZE is not going to be used much in combination with
region-based memory allocation, the benefit is not worth the effort.
That kind of implementation would put each resized thing in its own
block, plus some meta-data.

- 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 2013: http://www.euroforth.org/ef13/

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web