High level memory programming paradigm

General discussion for topics related to the FreeBASIC project or its community.
Lost Zergling
Posts: 532
Joined: Dec 02, 2011 22:51
Location: France

High level memory programming paradigm

Post by Lost Zergling »

By curiosite, I am looking on the net the notion of programmable 'garbage collector', I mean a real simple simple instruction set that would be dedicated to garbage collector. Because half way between managing the memory with allocate / deallocate and an automatic garbage collector, there is functional gap. For what I know, the idea of a manual and simple but effective instruction set on a garbage collector (ie snatch, garbagesnatch, recycle, .. in lzle), as part of a medium/hight level langage seems to me inedite, but I'm not sure at all about that. I have nevertheless found something perhaps a bit approaching (in the idea of programming the substitution / reutilization of compatible objects, at the functional level): the patterned filtering in Ruby, but still avoiding the paradigm of directly programming the problematic of memory fragmentation. Has someone got other examples ?
marcov
Posts: 3452
Joined: Jun 16, 2005 9:45
Location: Netherlands
Contact:

Re: High level memory programming paradigm

Post by marcov »

Do you mean old dos style mark/sweep ?
Lost Zergling
Posts: 532
Joined: Dec 02, 2011 22:51
Location: France

Re: High level memory programming paradigm

Post by Lost Zergling »

Interesting. Found this link : https://www.educative.io/courses/a-quic ... ithms/jy6v
This one also (French) : https://fr.wikipedia.org/wiki/Ramasse-m ... ormatique) or that one https://en.wikipedia.org/wiki/Tracing_g ... collection
But what I was talking about is not a 'true' GC.. because it is purely manual.
gCollector is just a list instance (Dim shated gCollector as list), just a list of dead references that must be handled by programmer using some kind of syntactic sugar.
Reason why I don't know if this could be qualified 'mark and sweep'.
Not a GC algo in an academic definition. It is mostly 'semantic' (from prog point of view), just providing facilities to manage dead references.
It is non-copying without some disavantages of non copying, or some advantages of weak references but reducing logical leak risk via syntax.
Thus, the recursive inconvenience (stack overload) are reduced because it can behave recursively while not being.
caseih
Posts: 2157
Joined: Feb 26, 2007 5:32

Re: High level memory programming paradigm

Post by caseih »

I'd say 80% of all memory allocations can be adequately dealt with using the resource acquisition is initialization model, which is supported by FB's object-oriented facilities. Basically if you clean up in your destructor, scope automatically manages memory for you. Of course there will always be instances of circular references (cycles) which RAII won't detect, which are the kinds of the things a garbage collection systems are designed to deal with. How you'd implement that in FB I'm not sure. C++ tends to use special smart pointers and other template-based containers to help deal with this issue. Smart pointers let you do dynamic memory allocations for objects and still have RAII semantics. A pretty neat idea and it works quite well.
Lost Zergling
Posts: 532
Joined: Dec 02, 2011 22:51
Location: France

Re: High level memory programming paradigm

Post by Lost Zergling »

Actually, no implemntation is required. It'd be from hight to low, as an optionnal over implementation of an alternate coding style same time alternative and complementary to C++ like way of doing, thanks to FB, just using it onto the required objects. For what I can understand about them, Boehm and Boost (C++ non com GC) are going low to hight meaning they rather consider feature doing automatic mem backend management as transparently as possible (like truely (automated) GC) wich is main feature, not a manual 'GC' where the responsability of the mem cleaníg strategy remains in a large part in the hands of the programmer.
caseih
Posts: 2157
Joined: Feb 26, 2007 5:32

Re: High level memory programming paradigm

Post by caseih »

I mean you have to tell the garbage collection system about the allocations. Since FB has no template classes, you can't use fancy wrappers to do that. You have to do it manually.
Lost Zergling
Posts: 532
Joined: Dec 02, 2011 22:51
Location: France

Re: High level memory programming paradigm

Post by Lost Zergling »

Well, didn't test nor think a lot about feature using New/Delete for a declaration/instanciation from inside a listnode or a listcontainer type. Maybe it would be more simple just to adapt listnode or listcontainer adding var, sub, properties, etc.. so as to get the specific required object behaviour, ie at listnode level, then to wrap via list object properties related to current node (like rwtag and so on). There is not so much differences between allocated and instanciated datas. Thus, the raii in this context (reuse mem slots to reduce fragmentation issues), might not be a desired feature. Another issue is that what is declared with New shall be free with Delete, not with a procptr hack. Listnode shall remain substitutable (in size), this point is a condition to the efficiency. So, perhaps better to adapt objects that requires special persistency feature that to go full object. This what i mean by 'mixing' coding style.
Added : purpose is not to deal with class hierarchy exception wich would be the role of a true GC, but to manage direct reallocation so as to solicit low level as little as possible.
caseih
Posts: 2157
Joined: Feb 26, 2007 5:32

Re: High level memory programming paradigm

Post by caseih »

Most data structures work well with a class hierarchy and RAII for managing memory.
Lost Zergling
Posts: 532
Joined: Dec 02, 2011 22:51
Location: France

Re: High level memory programming paradigm

Post by Lost Zergling »

Yes, I fully agree, most. I needed indexed processing on several Go variadic datas plus very readable and versatile rad code.
Added : interesting link : https://www.toptal.com/software/elimina ... -collector
Powerfull semantic notion owner/borrowing in rust.
'owner' look likes pretty similar to hierarchy into hierarchy, sounds complex.
RAII does not just manage memory, it also enforce a model (object model) which one of its purpose is to make your code 'naturally' compliant with UML or related, but this is not necessarily the guidelines you are expecting.

One precision : in lzle substitutable (in size) doesn't mean necessarily equal (in size), if a (re used) listnode is too small, it is reallocated, if too large, it is re used as is, and will be availabla as is next re use, or other mechanism, depending mode.

Added 29/06
If I had to do a little (very presumptuous and one point of view) sort of comparison between lzle and Rust (for memory management), ..
The notion of borrower reminds me a little of an idea of ​​"BranchConsider" a few years ago: a process temporarily blocks a sub-tree for its use, then gives up control later. I then substituted "Snatch", which I considered both more intuitive and more powerful.
To find out if a node (object) has no more dependencies (children), Rust increments and decrements a counter. In lzle, a dependency counter is implemented (BranchCountDown), but it is not necessary to use it to manage the revocation of a node without dependencies: this is accomplished by the contextualized recursive or pseudo-recursive tree traversal. syntax kinematic, and by the NFMethod settings. This saves a "vector" (vertical) and BranchCountDown is available as an additional pointer for tracking or whatever. On the other hand, "lzle" is strictly hierarchical.
Rust does not have a GarbageCollector because memory is managed at compilation time. In lzle, memory is managed at compile time, but there is a semantic GarbageCollector which behaves like a token (in Rust, the "semantic GarbageCollector" seems to be "deeply embedded" in the object syntax).
Finally, at the conceptual level, Rust is part of the raii approach, the concept in lzle would rather be "allocation is (virtual) instantiation".
I only really discovered Rust's approach today, by searching around "RAII" to answer caseih.
Finally, it was quite constructive as a discussion thread, it did not take me at all to where I thought I would go at the start, it gives me an idea around "workflow of virtual instances", to see if it is relevant or not..
Lost Zergling
Posts: 532
Joined: Dec 02, 2011 22:51
Location: France

Re: High level memory programming paradigm

Post by Lost Zergling »

I come back to the mark and sweep: it is possible and easy to make a custom mark and sweep: ie using check / while or holdback / track to mark then iterate and use 'nodeflat' to send to the private 'garbage', and then do gCollector.GarbageSnatch to retrieve the deferenced elements in a shareable list. The interest is that it's childish, no pointer, no memory management other than intuitive, we can make mark and no sweep, adapt the marking method (check or track) to the data list by list , and so on.
(added : it is also possible to effectively deallocate, creating a tmplist, tmplist.garbagesnatch(gCollector), then tmplist.destroy).
Modern languages tend to become more and more multi-paradigm.
Constantly creating new things is a necessity.
dodicat
Posts: 7967
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: High level memory programming paradigm

Post by dodicat »

Interesting stuff.
To add a bit of colour to this thread and a failsafe way to manage memory:
(restless but happy pointers)

Code: Select all


Screen 20,32,,64
Dim Shared As Integer xres,yres
Dim Shared As Any Ptr row:row=Screenptr
Dim Shared As Integer pitch
Screeninfo xres,yres,,,pitch

Type V2
      As Single x,y,dx,dy
      As Long  radius
      As Ulong c 'colour
      As Ulong m 'mass
      As Single gravity
End Type
#define map(a,b,_x_,c,d) ((d)-(c))*((_x_)-(a))/((b)-(a))+(c)
#macro incircleA(cx,cy,r,mx,my,a,result)
If (a)<=1 Then
      result=(a)*((cx)-(mx))*(a)*((cx)-(mx)) +((cy)-(my))*((cy)-(my))<= (r)*(r)*(a)*(a)
Else
      result=(a)*((cx)-(mx))*(a)*((cx)-(mx)) +((cy)-(my))*((cy)-(my))<= (r)*(r)
End If
#endmacro

'optimize detection to save cpu.
Function DetectBallCollisions(Byref b1 As V2 Ptr,b2 As V2 Ptr) As Single
      Dim As Single xdiff = b2->x-b1->x
      Dim As Single ydiff = b2->y-b1->y
      If Abs(xdiff) > b2->radius*2 Then Return 0
      If Abs(ydiff) > b2->radius*2 Then Return 0
      Var L=Sqr(xdiff*xdiff+ydiff*ydiff)
      If L<=(b2->radius+b1->radius) Then Function=L
End Function

Sub Check_BallCollisions(b() As v2 Ptr,energy As Single)
      For n1 As Long=Lbound(b) To Ubound(b)-1
            For n2 As Long=n1+1 To Ubound(b)
                  Dim As Single  L= DetectBallCollisions(b(n1),b(n2))
                  If L Then
                        Dim As Single  impulsex=(b(n1)->x-b(n2)->x)
                        Dim As Single  impulsey=(b(n1)->y-b(n2)->y)
                        Dim As Single ln=Sqr(impulsex*impulsex+impulsey*impulsey)
                        impulsex/=ln'normalize the impulse
                        impulsey/=ln
                        'set one ball to nearest non overlap position
                        b(n1)->x=b(n2)->x+(b(n2)->radius+b(n1)->radius)*impulsex
                        b(n1)->y=b(n2)->y+(b(n2)->radius+b(n1)->radius)*impulsey
                        
                        Dim As Single  impactx=b(n1)->dx-b(n2)->dx
                        Dim As Single  impacty=b(n1)->dy-b(n2)->dy
                        Dim As Single  dot=impactx*impulsex+impacty*impulsey
                        'handle mass
                        
                        Dim As Single  mn2=b(n1)->m/(b(n1)->m+b(n2)->m),mn1=b(n2)->m/(b(n1)->m+b(n2)->m)
                        b(n1)->dx-=dot*impulsex*2*mn1
                        b(n1)->dy-=dot*impulsey*2*mn1
                        b(n2)->dx+=dot*impulsex*2*mn2
                        b(n2)->dy+=dot*impulsey*2*mn2
                        
                  End If
                  
            Next n2
      Next n1
End Sub

Function Regulate(Byval MyFps As Long,Byref fps As Long) As Long
      Static As Double timervalue,_lastsleeptime,t3,frames
      Var t=Timer
      frames+=1
      If (t-t3)>=1 Then t3=t:fps=frames:frames=0
      Var sleeptime=_lastsleeptime+((1/myfps)-T+timervalue)*1000
      If sleeptime<1 Then sleeptime=1
      _lastsleeptime=sleeptime
      timervalue=T
      Return sleeptime
End Function



Sub moveballs(b() As v2 Ptr,Byref e As Long)
      e=0
      For z As Long=1 To Ubound(b)
            b(z)->x+=b(z)->dx
            b(z)->y+=b(z)->dy+b(z)->gravity
            e+=.5*b(z)->m*(b(z)->dx*b(z)->dx + b(z)->dy*b(z)->dy)
      Next z
End Sub

Sub _circle(b As v2 Ptr)
      #define incircle(cx,cy,radius,x,y) (cx-x)*(cx-x) +(cy-y)*(cy-y)<= radius*radius
      #define onscreen x>=0 And x<xres And y>.0 And y<yres
      #define putpixel(_x,_y,colour)    *Cptr(Ulong Ptr,row+ (_y)*pitch+ (_x) Shl 2)  =(colour)
      Dim As Ulong tc
      For x As Long=b->x-b->radius To b->x+b->radius
            For y As Long=b->y-b->radius To b->y+b->radius
                  If incircle(b->x,b->y,b->radius,x,y) Andalso onscreen Then
                        putpixel(x,y,b->c)
                  End If
            Next
      Next
End Sub

Sub boundaries(b() As v2 Ptr,energy As Single)
      Dim As Single delta=.000001
      static as single D=1
      If d>1 Then
            D+=delta
      Else
            D-=delta
      End If
      For n As Long=Lbound(b) To Ubound(b)
            b(n)->dx=B(n)->dx*D
            b(n)->dy=b(n)->dy*D
            If b(n)->x<b(n)->radius Then b(n)->x=b(n)->radius:b(n)->dx=-b(n)->dx
            If b(n)->x>xres-b(n)->radius Then b(n)->x=xres-b(n)->radius:b(n)->dx=-b(n)->dx
            
            If b(n)->y<b(n)->radius Then b(n)->y=b(n)->radius:b(n)->dy=-b(n)->dy/2
            If b(n)->y>yres-b(n)->radius Then b(n)->y=yres-b(n)->radius:b(n)->dy=-2*b(n)->dy
            
      Next n
End Sub

Sub drawballs(b() As v2 Ptr)
      For z As Integer=1 To Ubound(b)
            _circle(b(z))
      Next z
End Sub

Sub setupballs(b() As v2 Ptr,MEMORY() As v2)
      Dim As Long flag,condition,ct
      For x As Long=40 To xres-40 Step 30
            For y As Long=40 To yres-40 Step 30
                  ct+=1
                  Redim Preserve b(1 To ct)
                  b(ct)=@MEMORY(ct)
                  b(1)->c=Rgb(200,0,0)
                  b(ct)->x=x:b(ct)->y=y
                  b(ct)->radius=(4+Rnd*3)*1
                  b(ct)->m=b(ct)->radius^2
                  b(ct)->gravity=1
                  Do
                        b(ct)->dx=(Rnd-Rnd)/2
                        b(ct)->dy=(Rnd-Rnd)/2
                  Loop Until Abs(b(ct)->dx)>.1 And Abs(b(ct)->dy)>.1
                  Dim As Long result
                  incircleA(500,300,300,x,y,.5,result)
                  If result Then  b(ct)->c=Rgb(255,255,255) Else If b(ct)->c<>Rgb(200,0,0) Then b(ct)->c=Rgb(0,200,0)  
            Next y
      Next x
End Sub

Function start As Long
      Dim As v2 MEMORY(2000)
      Redim As v2 Ptr b()
      setupballs(b(),MEMORY())
      
      Dim As Long fps,energy
      dim as double t=timer
      Do
            Check_BallCollisions(b(),energy)
            boundaries(b(),energy)
            moveballs(b(),energy)
            Screenlock
            Line(0,0)-(xres,yres),Rgba(0,0,0,40),bf
            if(timer-t)<60 then
                  draw string(50,5),"Settling down",rgb(0,200,0)
                  line(50,20)-(map(0,60, (timer-t),50,900),40),rgb(0,100,255),bf
                  line(50,20)-(900,40),rgb(200,0,0),b
                   Draw String(30,90),"Number of  balls " &ubound(b)
                  end if
            drawballs(b())
            Draw String(30,50),"FPS = " &fps
            Draw String(30,70),"Energy " &energy
            Screenunlock
            Sleep regulate(60,fps),1
      Loop Until Len(Inkey)
      Sleep
      Erase MEMORY   '' not needed
      Return 0
End Function

End start


 
Lost Zergling
Posts: 532
Joined: Dec 02, 2011 22:51
Location: France

Re: High level memory programming paradigm

Post by Lost Zergling »

Thx for colours :-)
marcov
Posts: 3452
Joined: Jun 16, 2005 9:45
Location: Netherlands
Contact:

Re: High level memory programming paradigm

Post by marcov »

caseih wrote:I'd say 80% of all memory allocations can be adequately dealt with using the resource acquisition is initialization model, which is supported by FB's object-oriented facilities. Basically if you clean up in your destructor, scope automatically manages memory for you. Of course there will always be instances of circular references (cycles) which RAII won't detect, which are the kinds of the things a garbage collection systems are designed to deal with.
Which is quite fun if all if you do is defining your own struct with operators for complex numbers or so, and/or you only do batch operations, where a scope wraps the whole piece of code.

Now apply this to a simple calculator where such type is done via GUI. (set A, Set B, and then select the operator +). Then lexical scope goes out of the window.

RAII works, but is limited to the trivial.
How you'd implement that in FB I'm not sure. C++ tends to use special smart pointers and other template-based containers to help deal with this issue. Smart pointers let you do dynamic memory allocations for objects and still have RAII semantics. A pretty neat idea and it works quite well.
smart pointers are more or less just a template form of applying an existing reference counting template to various types. IOW a generic (library) form of refcounting rather than in language as some languages have.

But yeah, ref counting is the way between manual and automated, but also has certain limitations (like no support for mutual references/cycles). I was lucky to get some base explanations of GC during FOSDEM lectures on certain interpreters internals, but it is a complex field. If you are serious about it, you have quite some literature to read.
caseih
Posts: 2157
Joined: Feb 26, 2007 5:32

Re: High level memory programming paradigm

Post by caseih »

marcov wrote:Now apply this to a simple calculator where such type is done via GUI. (set A, Set B, and then select the operator +). Then lexical scope goes out of the window.

RAII works, but is limited to the trivial.
No it's really not limited to the trivial. I use RAII with Qt in C++ and it works very well. I've never encountered issues like you describe. Maybe because of the structure that GUI frameworks employ, such as storing state in a class instance and deriving from a GUI widget class. In fact, GUI development RAII really shines. Smart pointers aren't just about reference counting. They are fantastic tools for applying the RAII paradigm to dynamically-allocated objects. And everything does work quite well in C++. Like I said, RAII covers about 80% of your use cases in C++. Period. Only a few things require some thought and manual tracking, where a GC system would be useful.

Not sure if you've done a lot with GUI development in a language that strongly supports RAII such as C++. It really does work very well.
marcov
Posts: 3452
Joined: Jun 16, 2005 9:45
Location: Netherlands
Contact:

Re: High level memory programming paradigm

Post by marcov »

caseih wrote: Not sure if you've done a lot with GUI development in a language that strongly supports RAII such as C++. It really does work very well.
IMHO that is a very wide interpretation of RAII. RAII only gives you the ability to run epilogue and prologue code to hook your ref counting (or smart pointer, if you want to be fancy) system into. It is not RAII itself that keeps it memory safe.
Post Reply