REDIM PRESERVE does not destroy the right array elements of a multidimensional array -> memory leak

[dodicat]

From the help file
"If there are multiple dimensions, only the upper bound of only the first dimension may be changed safely. If the first dimension is reduced, the existing mappable data may be lost. If lower-order dimensions are resized at all, the effects can be hard to predict (because multidimensional arrays are stored in row-major order : values differing only in the last index are contiguous)."

I take from that -- don't bother with redim preserve in >=2D arrays.

So a few years ago I made up a cheesy method for preserving a 2D matrix of components which I want to expand or reduce.
I don't think anything in fbc-int/array.bi would be of help here.
Cheesy method:

Code: Select all

#macro redimpreserve(a,d1,d2)
Scope
    Redim As Typeof(a) copy(d1,d2)
    For x as long =d1
        For y as long =d2
            If x>=Lbound(a,1) And x<=Ubound(a,1) Then
                If y>=Lbound(a,2) And y<=Ubound(a,2) Then   
                    copy(x,y)=a(x,y)
                End If
            End If
        Next y
    Next x
    Redim a(d1,d2)
    For x as long= d1
        For y as long=d2
            a(x,y)=copy(x,y)
        Next y
    Next x
End Scope
#endmacro
'==================  helpers only for demo ====================
#macro printout(d)
scope
print "(";Lbound(d,2);" to";Ubound(d,2);" ,";Lbound(d,1);" to "; Ubound(d,1);")"+chr(10)
dim as long ct
For n As Long=Lbound(d,1) To Ubound(d,1)
    ct=0
    For m As Long=Lbound(d,2) To Ubound(d,2)
        ct+=5
        #if typeof(d)=string
       print "'";d(n,m);"'";tab(ct);
    #else
        Print d(n,m);tab(ct);
        #endif
    Next m
    Print
Next n 
Print
end scope
#endmacro

sub setstring(s() as string)
dim as long k,i,j
For i  = lbound(s,1) To ubound(s,1)
    For j  = lbound(s,2) To ubound(s,2)
        if s(i,j)="" then s(i, j) = chr(65+k)
        k+=1
    Next j
Next i
end sub

screen 21
Redim Shared As Double d(1 To 2,3)

d(1,0)=1:d(1,1)=2:d(1,2)=3:d(1,3)=4
d(2,0)=5:d(2,1)=6:d(2,2)=7:d(2,3)=8

printout(d)


redimpreserve(d,-2 To 5,-3 To 7)
printout(d)

redimpreserve(d,0 To 5,0 To 7)               
printout(d)




redim as string s(3,4)
setstring(s())
printout(s)

redimpreserve(s,0 to 5,0 to 6)
printout(s)
print "Fill the empties"

setstring(s())
printout(s)
redimpreserve(s,0 to 4,0 to 5)
printout(s)
print "done"

sleep


 

[Lost Zergling]

Another approach would be to ask as few redim and redim preserve as possible. As soon as myarray(8,2) is taking same mem space as myarray(2,8), it should be possible to substitute. Such operation may be 'logically' performed, by index translation, but a tool like lzae also provide a custom parser as well as an alternate solution for in memory var-size processing tasks around arrays. It should work till the global array is not fragmented in memory, my few tests did not show underlying fragmentation on an array.

[Lost Zergling]

I think, maybe the leak could find its source into string descriptors as soon as / only when (?) they need heavy memory processes (allocations and deallocations), or say, as soon as they are competing in speed against the main program/instance they are issued from. Then the reallocations of the descriptors seems to behaves as a fragmentation issue (link between speed & leaks). The reason why I switched from strings to zstrings inside lzle listnodes (define 'tagmode'), and then many leaks issues vanished. I think maybe a related issue.

[fxm]

In the examples I gave above, there are errors in both the number and the locations of elements to destroy.

Yet the rule is simple:

For a dynamic array, if the total number of elements required by REDIM PRESERVE is reduced by "N" elements compared to the total number of existing elements, the last "N" elements of the existing array must be destroyed before reallocating memory for the new array.

Then, the only difficulty is to correctly calculate the address zone of the elements to be destroyed:
- The address of the last element of the array (before resizing) is easy to calculate with the information in the array descriptor (any ptr: base_ptr, uinteger: size, uinteger: element_len).
Last element address: base_ptr + size - element_len
- So it suffices to destroy the "N" elements by going up:

Code: Select all

Dim As FBC.FBARRAY Ptr p = FBC.ArrayDescriptorPtr(array())
For X As Integer = 1 To N
    Cptr(Typeof(array) Ptr, p->base_ptr + p->size - p->element_len * X)->Destructor()
Next X

[fxm]

In the second example of my first post ('In this infinite loop, the used memory increases regularly until inducing an run-time error 4 (out of memory)'), if I manually destroy the last 5*6-4*5 strings before array size reduction (from 5*6 to 4*5 strings), there is no longer a memory leak:

Code: Select all

Declare Sub fillArray(array(Any, Any) As String)

Dim As String array(Any, Any)

Do
    Redim Preserve array(4, 5)
    fillArray(array())
    
    Dim As Integer N = (5 * 6) - (4 * 5)
    Dim As String Ptr ps = @array(0, 0)
    For I As Integer = (5 * 6 - 1) To (5 * 6 - 1) - (N - 1) Step -1  '' destroy the last 5*6-4*5 strings of the array
        ps[I] = ""
    Next I

    Redim Preserve array(3, 4)
    fillArray(array())
Loop

Sub fillArray(array(Any, Any) As String)
    For I As Integer = 0 To Ubound(array, 1)
        For J As Integer = 0 To Ubound(array, 2)
            array(I, J) = Str(10 * I + J)
        Next J
    Next I
End Sub

[fxm]

It should work till the global array is not fragmented in memory, my few tests did not show underlying fragmentation on an array.

The direct elements of an array are always consecutive in memory. However, they can address other data that can be disjoint in memory.
For example for an array of strings, the direct elements are the string descriptors which are consecutively well ordered in memory. But these address their string character data which are by cons generally disjoint blocks in memory.

[fxm]

Bug of element destruction for a 2D array (deduced from all my tests):
- The wrong number of destroyed elements "D" seems to be equal to the size of the second dimension (before resizing) multiplied by the size difference of the first dimension between before and after resizing.
- The wrong first element destroyed seems to be deduced from the first of the "D" last elements (of the array before resizing) but by dividing its absolute index (0-based) by the number of elements of the second dimension (before resizing).

[fxm]

@Jeff,

I just see your commit about this bug (https://github.com/freebasic/fbc/commit ... 8ed78d1bd0).
I have a remark about the add in changelog.txt:

- ./inc/fbc-int/array.bi - add fb.ArrayLen( array ) function to return total number of elements in an array (computed from size and element length)
- ./inc/fbc-int/array.bi - add fb.ArraySize( array ) function to return total size of an array in bytes (computed from dimensions and element length)

[coderJeff]

Your remarks are correct. I'll update the changelog next opportunity I get.

I had an earlier version I was testing that did compute the size from dimensions and element length to match the legacy code calculation. Unless I've missed some detail, we should be able to safely use size and element length from the descriptor.

ArrayLength = array->size / array->element_len
ArraySize = array->size

I'll update the changelog next opportunity I get.

[Lost Zergling]

I think maybe I get it, probably much more simpler than what I might have imaginated.
When writing :

Code: Select all

Type ListNode
    Public :
	Dim s as string
End Type

Dim As ListNode Ptr lp = CAllocate (Len(listNode))
lp->s="Titi"
Deallocate lp
? "Just descriptor deallocated, 'Titi' not deallocated ?"  'Because lp is just a pointer. 
sleep

What would be the correct way for deallocating the string itself ? (if any)
It might be usefull for me testing multi-mode allocation (strings vs zstrings), so having a 'reliable' string mode regarding leaks.

[fxm]

Your remarks are correct. I'll update the changelog next opportunity I get.

I had an earlier version I was testing that did compute the size from dimensions and element length to match the legacy code calculation. Unless I've missed some detail, we should be able to safely use size and element length from the descriptor.

ArrayLength = array->size / array->element_len
ArraySize = array->size

I'll update the changelog next opportunity I get.

OK.

You can even use an integer division:
ArrayLength = array->size \ array->element_len

[coderJeff]

What would be the correct way for deallocating the string itself ?

A newly created string descriptor must be initialized to zero, as is the case in your example using callocate().

Set the string to empty "" to release the string data allocation before deallocating the string descriptor.

Code: Select all

'' allocate a null string
dim x as string
print strptr(x)

'' allocate memory for a string
x = "hello"
print strptr(x)

'' set to null string to deallocate the string
x = ""
print strptr(x)

[Lost Zergling]

Ok, Thank you Jeff. Honestly, I hoped there was another solution, I though maybe I went wrong way.
I will do some more tests. Thanks.

[fxm]

I thought you wanted to recover the string character data memory after deallocating the descriptor memory!

Code: Select all

Type ListNode
    Public :
   Dim s as string
End Type

' allocate only memory for a ListNode instance (only a null string descriptor contained)
Dim As ListNode Ptr lp = CAllocate (Len(listNode))

' construct a string
lp->s="Titi"

' memorize a pointer to the string characters data (before deallocating the descriptor memory)
Dim As Zstring Ptr pz = Strptr(lp->s)

' deallocate the memory for the ListNode instance (for the descriptor)
Deallocate lp
? "Just descriptor deallocated, 'Titi' not deallocated ?"

' use the "Titi" zstring (but increase its len is forbidden)
Print *pz
*pz = "Toto"
Print *pz

' deallocate the memory for the zstring characters data
'(this work, but it's not a very safe method)
Deallocate pz
Sleep

[fxm]

Commit 'rtlib: sf.net # 950: REDIM PRESERVE does not destroy the correct array elements' tested with the last build from https://users.freebasic-portal.de/stw/builds/:
OK now fore REDIM PRESERVE.

Thanks Jeff.