memory leak

memory leak

Post by Franken Se » Fri, 17 Apr 2009 10:04:58



Do I allocate and deallocate properly in this program, because it looks
like a memory leak to me:

module m_binary_tree
public :: main, Insert, PrintTree
private :: NewTree
type, public :: node
real :: value
type (node), pointer :: left, right
endtype node
contains
function NewTree(num) result(tree)
real, intent(in) :: num
type (node), pointer :: tree
allocate (tree)
tree%value = num
nullify(tree%left)
nullify(tree%right)
endfunction NewTree

recursive subroutine Insert(tree, num)
type (node), pointer :: tree
real, intent(in) :: num
if (.not. associated (tree)) then
tree => NewTree(num)
elseif (num < tree%value) then
call Insert(tree%left, num)

else
call Insert(tree%right, num)

endif
endsubroutine Insert

recursive subroutine PrintTree(tree)
type (node), pointer :: tree
if (associated (tree)) then
call PrintTree (tree%left)
print *, tree%value
call PrintTree (tree%right)
endif
endsubroutine PrintTree

endmodule m_binary_tree

module qsort_c_module

implicit none
public :: QsortC
private :: Partition

contains

recursive subroutine QsortC(A)
real, intent(in out), dimension(:) :: A
integer :: iq

if(size(A) > 1) then
call Partition(A, iq)
call QsortC(A(:iq-1))
call QsortC(A(iq:))
endif
end subroutine QsortC

subroutine Partition(A, marker)
real, intent(in out), dimension(:) :: A
integer, intent(out) :: marker
integer :: i, j
real :: temp
real :: x ! pivot point
x = A(1)
i= 0
j= size(A) + 1

do
j = j-1
do
if (A(j) <= x) exit
j = j-1
end do
i = i+1
do
if (A(i) >= x) exit
i = i+1
end do
if (i < j) then
! exchange A(i) and A(j)
temp = A(i)
A(i) = A(j)
A(j) = temp
elseif (i == j) then
marker = i+1
return
else
marker = i
return
endif
end do

end subroutine Partition

end module qsort_c_module

program sortdriver
use qsort_c_module
use m_binary_tree
implicit integer (a-h)

type (node), pointer :: tree
integer :: i, trials
real :: value, ratio, sum1,sum2,mu1,mu2
real, allocatable :: myarray(:), myarray2(:)
integer power2, r
integer ival(8)
integer, allocatable :: stats(:,:)
trials = 10


power2=7
call init_seed
allocate(stats(trials,2))


! main control

do b = 1, trials

nullify (tree)
call init_seed
 
 
 

memory leak

Post by Arjen Mark » Fri, 17 Apr 2009 16:35:12

n 16 apr, 03:04, Franken Sense < XXXX@XXXXX.COM > wrote:
> public :: main, Insert, P>intTree > private :: NewT>ee > >ype, public :: node gt; > real :: value gt; >>type (nod>), pointer :: left, right > end>ype node
> contains
> function Ne>Tree(num) result(tree) >
> real, intent(in) :: num gt; > type (node),>pointer :: tree
> allocate (tre>) > tr>e%value = num > gt; > nullify(tree%left) gt; > nullify(tree%right) gt; > endfunction NewTr>e >
> ecursi>e subroutine>Insert(tree, num) > eal, intent(in) :: num gt;> > if (.not. asso>iated (tree)) then > ree>=>>NewTree(num) > > elseif (num < tree%va>ue> then > all Insert(>ree%left, num) >
>>else > > all Insert(tree%rig>t, num) >
> >ndif > > ndsubroutine Insert gt; >
> ecursive subr>ut>ne PrintTree(tree) > if (ass>ciated (tree)) then gt;> >>> all PrintTree (tree%left) > > rint *, tree%valu> > gt; > >call Print>ree (tree%right) > > endif gt;gt; > > ndsubroutine PrintTre> gt; >
> endmodul> m_binary_tree
>
> module qsort_c_module >>
> implicit none
> public :: Qs>rtC
> private :: P>rtition
>
> co>tains
>
> recursive subrout>ne QsortC(A)> > rea>, intent(in out), >im>nsion(>) :: A
> i>teger ::>iq
>
> if(size(A) > 1)>then
> >ll Partition>A, iq)
> gt;all Qs>rtC(A(:iq-1)) >><all>QsortC(A(iq:))> > endif
>
> subroutine Partition(A, >arker)
> real, >ntent(in out), dim&g<;nsion(:) :: A
> gt;integer, intent(out) :: ma>ker
> integer ::>i, j
> rea> :: temp
> x = A(>)
> i= >
>
> d>
> o
> > gt;if (A(j) <= x) ex>t
> j = j-1 >> nd do
> gt; = i+1
> o
> > gt;if (A(i) >= x) exit
> i = i+1> > nd do
> gt;f (i < j) then
> ! exchange A(i) >nd A(j)
> temp = A(i)
> A(i) > A(j)
> A(j)>= temp
> ls>if (i == j) then
> marker = >+1
> >et>rn
> gt;lse
> ma>ker = i
> return
>>> ndif
> end >o >>
> end subroutine>Pa>tition
>
> end module qsort_c_m>dule
>
> progra> s>rtdriver
> u>e >sort_c_module
> >se m_binary_tree
> implicit i>teger (a-h)
>
> type >node), pointer :: tree gt; > integer :: >, trials
> real :: v>lue, ratio, sum1,sum2,mu1,mu2
> re>l,>allocatable :: my>rray(:), myarray2(:)
> integ>r ower2, r
> integer ival(8)
>>integer, allocatable :: stats(:,:)
> trials = 10
>
> power>=7
> call ini>_seed
> allocate(stats(trials,2)>
>
> ! main control
>
> do b>= 1, trials
>
> nullify (tree) > gt; > call init_s>ed
>
> power2 = 7
>
> r = 10**power2
> print *, >sort size is >, r
> allocate(myarray(r))
> allocate(m>array2(r))
> ca>l >andom_number(myarray)
> myarra>2 = myarray
> !print *, "myarray >s ", myarray
>
> ! main control
> ! time the bst with g1 .>.
> call date_and_time(>alues=ival)
> g1 = 60 * 1000 * iv>l(6) + 1000* ival(7) + ival(8) > do > = 1, r
> >alue=myarray(i) gt; > !print *, v>lue > call in>er>(tree, value) > > enddo
> call d>te_and_time(values=iv>l)
> g2 = 60>* 1000 * ival(6) +>10>0* ival(7) + ival(8) >> >1 = g2-g1
> stats(b,1)=d1
>
> !>time quicksort with g3 ...
>>call date>an>_time(values=ival)> > g3 = 60 * 1000 > ival(6) + 1000* ival(7) + ival(8) > gt; > call Qsort>(m>arra
 
 
 

memory leak

Post by Ian Bus » Fri, 17 Apr 2009 17:33:54


SNIP !

> nullify (tree)
You've just leaked all the memory you allocated on the (b-1)th
iteration of the loop as you no longer have a pointer to it. You need
to explicitly deallocate the tree.

As for checking whether you have a leak Arjen says some good things,

Ian
 
 
 

memory leak

Post by Franken Se » Sat, 18 Apr 2009 13:15:31

In Dread Ink, the Grave Hand of Ian Bush Did Inscribe:


>> nullify (tree) gt;gt; >
> You've just leaked all the memory you allocated >n the (b-1)th
> iteration of the loop as you no longer have a pointer t> it. You need
> to explicitly deallo>ate>the tree.
>
> As for checking whether you have a leak Arjen says som> go>d things,
>
> Ian

I think that's it. The simple fact is that I have no idea what nullify
does.

I could work around it, because the sort size is the same between trials in
this version, but not the more general case when one is looking to clock
the complexity as the size increases by successive orders of magnitude.

I'm in the market for a fortran book.
--
Frank

My father grew up in the Great Depression - his mother's.
~~ Al Franken
 
 
 

memory leak

Post by Arjen Mark » Sat, 18 Apr 2009 15:34:29


> >> nullify (tree) gt;> > >
> > You've just leaked all the memory you allocated >n>the (b-1)th
> > iteration of the loop as you no longer have a pointer t> >t. You need
> > to explicitly deallo>at> >he tree.
>
> > As for checking whether you have a leak Arjen says som> g>o> thing>, >>
> > Ian
>
> I think that's it. he simple fact is that I have no ide> what nu>lify
> does.
>

All nullify does is break the link between the pointer variable and
the
memory it is pointing to. It does not deallocate it, use deallocate
for that.

Consider:

real, dimension(:), pointer :: p
real, dimension(:), allocatable :: a

allocat>( a(100) )
p => a(1:10)
.... use p ...

! No more use for a
deallocate( a )
nullify( p ) ! Make sure we have no "dangling pointer" !

In this snippet, p refers to a part of the array a, but if a is
deallocated,
p should not point to that part anymore. The nullify statement makes
sure
that p is not pointing to anything anymore, making use of p illegal
(and
very likely cause the program to fail) until it is set to point at
some
memory >gain, using p => ... or allocate( p(..) ).

Regards,

Arjen
 
 
 

memory leak

Post by Ian Bus » Sat, 18 Apr 2009 16:17:25


> > >> nullify (tree) gt;> > > >
> > > You've just leaked all the memory you allocated >n>t>e (b-1)th
> > > iteration of the loop as you no longer have a pointer t> >t> You need
> > > to explicitly deallo>at> >h> tree.
>
> > > As for checking whether you have a leak Arjen says som> g>o> >hings,> >> > > > Ian
>
> > I think that's it. he simple fact is that I have no ide> >hat null>fy> > > does.
>
> All nullify does is break the link between the pointe> varia>le and
> the
> memory it is pointing to. It does not deallocate it, >se deallocat>
>
> real, dimension(:)> pointer :: p
> real, dimension(:), al>oc>table :: a
>
> allo>ate(>a(100) )
>>..> use p ...
>
> ! No >ore use for a
> d>allocate( a )
> nullify( p ) ! Make sure we have no "dan>li>g pointer" !
>
> In this snippet, p refers to a part of the arra> a, but if a is> > deallocated,
> p should not point to that part anymore. The nullify>stateme>t makes
> sure
> that p is not pointing to anything anymore, making >se of p>illegal
> (and
> very likely cause the program to fail) until it is>set to >oint at
> some
> memor> again, using p => ... or al>ocate( p(..) ).
>

One of the other common use apart from this bit of defensive
programming you illustrate in your own code, finding the "end" of a
data structure. The reason NewTree nullifies the left and right
pointers is so that the end of the tree can be found by Insert and
PrintTree, and also by DeleteTree once you>have written it :>). In
fact you could use any old target here along with the full form of the
associated intrinsic ( associated( pointer, target ) ), however the
value the pointer is set to by Nullify ( or returned by the Null()
intrinsic ) is very convenient for a Fortran program.

Also note you don't have to use pointers for this kind of thing. You
can just allocate a big chunk of memory and use integers to index into
it, reallocating the memory if the data structure grows bigger than it
is currently allocated. You might also need Transfer. There was a
thread about this at some point but I can't find it now,

Ian


Ian
 
 
 

memory leak

Post by Franken Se » Mon, 20 Apr 2009 13:34:31

In Dread Ink, the Grave Hand of Ian Bush Did Inscribe:




>>> >> nullify (tree) gt;> gt;>>gt; >>
>>> > You've just leaked all the memory you allocated >>>t>e (b-1)th
>>> > iteration of the loop as you no longer have a pointer t>>>t> You need
>>> > to explicitly deallo>>te>>>e>tree.
>>
>>> > As for checking whether you have a leak Arjen says som>>go>>>t>ings, >>> >>>> > Ian
>>
>>> I think that's it. he simple fact is that I have no ide>>>hat null>>y >>>> does.
>>
>> All nullify does is break the link between the pointe>>variab>> and
>> the
>> memory it is pointing to. It does not deallocate it, >>e deallocate>>>>>>or that.
>>>>>>>>onsider:
>>
>> real, dimension(:)>>pointer :: p
>> real, dimension(:), al>>ca>>ble :: a
>>
>> allo>>te( >(100) )
>>>p => a(1:10)
>>>>..>>se p ...
>>
>> ! No >>re use for a
>> d>>llocate( a )
>> nullify( p ) ! Make sure we have no "dan>>in>>pointer" !
>>
>> In this snippet, p refers to a part of the arra>>a, but if a is >>> deallocated,
>> p should not point to that part anymore. The nullify>>tatemen>>makes
>> sure
>> that p is not pointing to anything anymore, making >>e of p >>legal
>> (and
>> very likely cause the program to fail) until it is>>et to p>>nt at
>> some
>> memor> again, using p => ... or al>>ca>e( >(..) ).
>>
>
> One of the other common use apart from this >it of defensive
> programming you illustrate in your own code, findin> the "end" of a
> data structure. The reason NewTree nullifies th> left and right
> pointers is so that the end of the tree can be fou>d by Insert and
> PrintTree, and also by DeleteTree once you>have wr>tten it :>). In
> fact you could use any old target here along with the >ull form of the
> associated intrinsic ( associated( pointer, target > ), however the
> value the pointer is set to by Nullify ( or return>d by the Null()
> intrinsic ) is very convenient for a >ort>an program.
>
> Also note you don't have to use pointers for this ki>d of thing. You
> can just allocate a big chunk of memory and use intege>s to index into
> it, reallocating the memory if the data structure grow> bigger than it
> is currently allocated. You might also need Trans>er. There was a
> thread about this at some point but I ca>'t >ind it>now>
>>
> Ian
>
>
> Ian

I don't think my binary tree is set up right. It never lets go of its
memory between calls.
--
Frank

I'm going to die homeless, penniless, and 30 pounds overweight.
~~ Al Franken