Memory leak with cursors and data structures

10 Messages Forum Options Options
Embed this topic
Permalink
Paul Bates [ES]-2
Memory leak with cursors and data structures
Reply Threaded MoreMore options
Print post
Permalink
We've detected a memory leak when using gobo data structure cursors that
do not run to the end, and currently there is no way to clean them up
nicely.

Take the following code

f (a_list: !DS_LINEAR [?ANY])
   local
     l_cursor: DS_LINEAR_CURSOR [?ANY]
     l_stop: BOOLEAN
   do
     l_cursor := a_list.cursor
     from l_cursor.start until l_cursor.after or l_stop loop
       l_stop := l_cursor.item = Void
       if not l_stop then
         l_cursor.forth
       end
     end
   end

Passing a linear structure to 'f' where any item is Void will cause the
leak because the list never goes 'off'. We cannot call
DS_TRAVERSABLE.remove_traversing_cursor and it is not a good idea to do
so because it may have not been added the the managed list or cursors,
given the current lazy-eval implementation.

The current solution is to run out the cursor in another loop or run out
the cursor in the original loop but conditionally process the loop's
functional body. Neither of which look that nice.

Best,
Paul.


-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Paul Bates [ES]-2
Re: Memory leak with cursors and data structures
Reply Threaded MoreMore options
Print post
Permalink
I did subscribe but I didn't search the entire newsgroup, my apologies.

The reason I do not code a loop as suggested is because with heavy
loaded list this would be inefficient because the whole loop has to be
processed.

Paul.

On Tue, 2008-08-12 at 08:40 +0200, Eric Bezault wrote:

> Paul Bates wrote:
> > We've detected a memory leak when using gobo data structure cursors that
> > do not run to the end, and currently there is no way to clean them up
> > nicely.
> >
> > Take the following code
> >
> > f (a_list: !DS_LINEAR [?ANY])
> >    local
> >      l_cursor: DS_LINEAR_CURSOR [?ANY]
> >      l_stop: BOOLEAN
> >    do
> >      l_cursor := a_list.cursor
> >      from l_cursor.start until l_cursor.after or l_stop loop
> >        l_stop := l_cursor.item = Void
> >        if not l_stop then
> >          l_cursor.forth
> >        end
> >      end
> >    end
> >
> > Passing a linear structure to 'f' where any item is Void will cause the
> > leak because the list never goes 'off'. We cannot call
> > DS_TRAVERSABLE.remove_traversing_cursor and it is not a good idea to do
> > so because it may have not been added the the managed list or cursors,
> > given the current lazy-eval implementation.
> >
> > The current solution is to run out the cursor in another loop or run out
> > the cursor in the original loop but conditionally process the loop's
> > functional body. Neither of which look that nice.
>
> You "discovered" something that is not new:
>
>    http://www.gobosoft.com/eiffel/gobo/structure/traversal.html
>
> Look at the red comment. Why don't you write your code like this:
>
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~
> f (a_list: !DS_LINEAR [?ANY])
>     local
>       l_cursor: DS_LINEAR_CURSOR [?ANY]
>     do
>       l_cursor := a_list.cursor
>       from l_cursor.start until l_cursor.after loop
>         if l_cursor.item = Void then
>           ... do something interesting here ...
>           l_cursor.go_after
>         else
>           l_cursor.forth
>         end
>       end
>     end
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~
>
> as suggested in the doc? Note that `go_after' is a routine that
> I miss very much in the EiffelBase containers.
>
>
> PS: Please subscribe to the mailing list before posting.
>
--
------------------------------------------------------------------------  
Eiffel Software
805-685-1006 ext. 107
http://www.eiffel.com

Blog: http://www.eiffelroom.com/blog/paulbates
Wiki: http://dev.eiffel.com
------------------------------------------------------------------------  



-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Bernd Schoeller-3
Re: Memory leak with cursors and data structures
Reply Threaded MoreMore options
Print post
Permalink
In reply to this post by Paul Bates [ES]-2
Hi Paul,

it is indeed a "know issue" that GOBO cursors can produce these memory  
leaks. The "solution" is to make sure that the cursor is always off after  
an iteration. That way it is not referenced by the data structure anymore  
and will get garbage collected.

The proper solution would be to introduce weak references into the Eiffel  
language. I am not sure if there is any work on this as part of ECMA.

Bernd

On Mon, 11 Aug 2008 20:41:31 +0200, Paul Bates <paulb@...> wrote:

> We've detected a memory leak when using gobo data structure cursors that
> do not run to the end, and currently there is no way to clean them up
> nicely.
>
> Take the following code
>
> f (a_list: !DS_LINEAR [?ANY])
>    local
>      l_cursor: DS_LINEAR_CURSOR [?ANY]
>      l_stop: BOOLEAN
>    do
>      l_cursor := a_list.cursor
>      from l_cursor.start until l_cursor.after or l_stop loop
>        l_stop := l_cursor.item = Void
>        if not l_stop then
>          l_cursor.forth
>        end
>      end
>    end
>
> Passing a linear structure to 'f' where any item is Void will cause the
> leak because the list never goes 'off'. We cannot call
> DS_TRAVERSABLE.remove_traversing_cursor and it is not a good idea to do
> so because it may have not been added the the managed list or cursors,
> given the current lazy-eval implementation.
>
> The current solution is to run out the cursor in another loop or run out
> the cursor in the original loop but conditionally process the loop's
> functional body. Neither of which look that nice.
>
> Best,
> Paul.
>
>
> -------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's  
> challenge
> Build the coolest Linux based applications with Moblin SDK & win great  
> prizes
> Grand prize is a trip for two to an Open Source event anywhere in the  
> world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> gobo-eiffel-develop mailing list
> gobo-eiffel-develop@...
> https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop



--
Bernd Schoeller, PhD, CTO
Comerge AG, Technoparkstrasse 1, CH-8005 Zurich, Switzerland

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Paul Bates [ES]-2
Re: Memory leak with cursors and data structures
Reply Threaded MoreMore options
Print post
Permalink
Weak references is something I have been asking for, for a while now. I
remember Manu telling me it would be possible to implement that now with
support from existing classes, but it would be far better if there was
ECMA specification support. Another way would be to perform automatic,
safe clean up via language support:

using {f: RAW_FILE} create {RAW_FILE}.make_open_write (fn)
        f.put ("hello world")
end

On completion of the code block f.dispose is called, even if there was
an exception. That way the file is close during both normal and abnormal
operations. Then if the Gobo cursor structures implemented DISPOSABLE to
perform the clean up, then it would be simple:

using (c: DS_LINEAR_CURSOR [STRING]} list.new_cursor
        ...
end

But I digress, this is not the place for language ideas. I should write
a wiki page on the idea.

Paul.

Bernd Schoeller wrote:

> Hi Paul,
>
> it is indeed a "know issue" that GOBO cursors can produce these memory  
> leaks. The "solution" is to make sure that the cursor is always off after  
> an iteration. That way it is not referenced by the data structure anymore  
> and will get garbage collected.
>
> The proper solution would be to introduce weak references into the Eiffel  
> language. I am not sure if there is any work on this as part of ECMA.
>
> Bernd
>
> On Mon, 11 Aug 2008 20:41:31 +0200, Paul Bates <paulb@...> wrote:
>
>> We've detected a memory leak when using gobo data structure cursors that
>> do not run to the end, and currently there is no way to clean them up
>> nicely.
>>
>> Take the following code
>>
>> f (a_list: !DS_LINEAR [?ANY])
>>    local
>>      l_cursor: DS_LINEAR_CURSOR [?ANY]
>>      l_stop: BOOLEAN
>>    do
>>      l_cursor := a_list.cursor
>>      from l_cursor.start until l_cursor.after or l_stop loop
>>        l_stop := l_cursor.item = Void
>>        if not l_stop then
>>          l_cursor.forth
>>        end
>>      end
>>    end
>>
>> Passing a linear structure to 'f' where any item is Void will cause the
>> leak because the list never goes 'off'. We cannot call
>> DS_TRAVERSABLE.remove_traversing_cursor and it is not a good idea to do
>> so because it may have not been added the the managed list or cursors,
>> given the current lazy-eval implementation.
>>
>> The current solution is to run out the cursor in another loop or run out
>> the cursor in the original loop but conditionally process the loop's
>> functional body. Neither of which look that nice.
>>
>> Best,
>> Paul.
>>
>>
>> -------------------------------------------------------------------------
>> This SF.Net email is sponsored by the Moblin Your Move Developer's  
>> challenge
>> Build the coolest Linux based applications with Moblin SDK & win great  
>> prizes
>> Grand prize is a trip for two to an Open Source event anywhere in the  
>> world
>> http://moblin-contest.org/redirect.php?banner_id=100&url=/
>> _______________________________________________
>> gobo-eiffel-develop mailing list
>> gobo-eiffel-develop@...
>> https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
>
>
>


-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Franck Arnaud
Re: Memory leak with cursors and data structures
Reply Threaded MoreMore options
Print post
Permalink
> But I digress, this is not the place for language ideas. I should write
> a wiki page on the idea.

Are they good ideas in the first place? Both the "file" and the "cursor"
problems can be dealt with by using the existing language constructs.

For cursors, CONTAINER.do_all captures most cases where you used to use
cursors directly in the past, and we could add a do_until if you're
worried about having to prefix your do_all agent with a "if not stopped"
for partial traversals. It manages the cursor for you, no leak possible,
plus termination guarantee and it makes the code more amenable to
automatic code analysis.

The legacy construct "loop" is rarely needed in day to day programming
nowadays, and when it is, it's often because the appropriate container
is missing the right agent API.

For files, I think our files API may not have been updated yet, but you
can trivially devise an agent-based API that handles file closure
nicely, e.g.

  read_file (a_filename: STRING; a_line_processor: PROCEDURE [ANY, TUPLE
  [STRING]])

I don't think you should add more clutter to the language when the
existing features cope with the problem very nicely.

I think I'll go and write a wiki page on my proposal to remove "loop"
from the language :-).

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Colin Adams-3
Re: Memory leak with cursors and data structures
Reply Threaded MoreMore options
Print post
Permalink
Are you going to remove "from" and "until" as well?

How do you intend to implement {G}.do_all (where G is ARRAY, etc.)?

2008/8/14 Franck Arnaud <franck@...>:

>> But I digress, this is not the place for language ideas. I should write
>> a wiki page on the idea.
>
> Are they good ideas in the first place? Both the "file" and the "cursor"
> problems can be dealt with by using the existing language constructs.
>
> For cursors, CONTAINER.do_all captures most cases where you used to use
> cursors directly in the past, and we could add a do_until if you're
> worried about having to prefix your do_all agent with a "if not stopped"
> for partial traversals. It manages the cursor for you, no leak possible,
> plus termination guarantee and it makes the code more amenable to
> automatic code analysis.
>
> The legacy construct "loop" is rarely needed in day to day programming
> nowadays, and when it is, it's often because the appropriate container
> is missing the right agent API.
>
> For files, I think our files API may not have been updated yet, but you
> can trivially devise an agent-based API that handles file closure
> nicely, e.g.
>
>  read_file (a_filename: STRING; a_line_processor: PROCEDURE [ANY, TUPLE
>  [STRING]])
>
> I don't think you should add more clutter to the language when the
> existing features cope with the problem very nicely.
>
> I think I'll go and write a wiki page on my proposal to remove "loop"
> from the language :-).
>
> -------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
> Build the coolest Linux based applications with Moblin SDK & win great prizes
> Grand prize is a trip for two to an Open Source event anywhere in the world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> gobo-eiffel-develop mailing list
> gobo-eiffel-develop@...
> https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
>

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Franck Arnaud
Re: Memory leak with cursors and data structures
Reply Threaded MoreMore options
Print post
Permalink

> Are you going to remove "from" and "until" as well?

it goes without saying.

> How do you intend to implement {G}.do_all (where G is ARRAY, etc.)?

 do_all (a_agent: PROCEDURE[ANY, TUPLE[G]])
   do
     (lower |..| upper).do_all (agent do_one (a_agent, ?))
   end

 do_one (a_agent: PROCEDURE[ANY, TUPLE[G]; a_index: INTEGER)
   do
     a_agent.call ([item (a_index)])
   end

I feel you're going to ask how I implement INTEGER_INTERVAL.do_all, I'd
use recursion, it would help if the compiler recognises it in some way
so that the generated code does not use stack space, but it's the only
place where you need a slight implementation-level cheat.

as for loops which are open ended and not index-based, (1 |..|
Maximum_integer).do_until should be OK, and again if all else fails you
can always fallback on recursion but you shouldn't have to. I think all
loops I have written in the past few years are either straightforward
container loops or fit well within the Maximum_integer boundary.

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Colin Paul Adams
Re: Memory leak with cursors and data structures
Reply Threaded MoreMore options
Print post
Permalink
>>>>> "Franck" == Franck Arnaud <franck@...> writes:

    >> Are you going to remove "from" and "until" as well?

    Franck> it goes without saying.

No it doesn't. What about variant and invariant? Does it go without
saying that you are going to remove invariant? And until might want to
be re-used.

    Franck> INTEGER_INTERVAL.do_all, I'd use recursion, it would help
    Franck> if the compiler recognises it in some way so that the
    Franck> generated code does not use stack space, but it's the only
    Franck> place where you need a slight implementation-level cheat.

If the compiler can implement tail recursion, why can't you?

    Franck> as for loops which are open ended and not index-based, (1
    Franck> |..| Maximum_integer).do_until should be OK, and again if

Not for network servers which implement do forever until shutdown
request.
This might well exceed Maximum_integer.

    Franck> all else fails you can always fallback on recursion but

Oh no you can't!
--
Colin Adams
Preston Lancashire

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Franck Arnaud
Re: Memory leak with cursors and data structures
Reply Threaded MoreMore options
Print post
Permalink

> No it doesn't. What about variant and invariant? Does it go without
> saying that you are going to remove invariant?

It goes without saying for variant, and it goes without saying that the
non-loop invariant stays.

> And until might want to be re-used.

yes, I'm only talking of the looping construct, it might indeed be an
opportunity to reuse the keywords, keyword reuse would require some
saying.
 
>     Franck> INTEGER_INTERVAL.do_all, I'd use recursion, it would help
>     Franck> if the compiler recognises it in some way so that the
>     Franck> generated code does not use stack space, but it's the only
>     Franck> place where you need a slight implementation-level cheat.
>
> If the compiler can implement tail recursion, why can't you?

well you can actually:

class INTEGER_INTERVAL
...
  do_all (a_agent: PROCEDURE [ANY, TUPLE[INTEGER])
     -- Apply to all integers between 'lower' and 'upper'.
    local
      i: INTEGER
    do
       if i <= count then
         a_agent.call ([i + lower])
         i := i + 1
         raise ("forth")
       end -- else exit loop
    rescue
       retry
    end
end

arguably that's a bit sick. but it also confirms that we have too many
looping constructs as we stand. also a drawback is that when I will
suggest removing "retry" you're going to argue that we need it to
implement INTEGER_INTERVAL :-).

>     Franck> as for loops which are open ended and not index-based, (1
>     Franck> |..| Maximum_integer).do_until should be OK, and again if
>
> Not for network servers which implement do forever until shutdown
> request. This might well exceed Maximum_integer.

that's debatable. with 64 bit integers you can do_forever 1 billion
times a second for 100 years, which is a hell of an uptime for a network
server, and a hell of a lot of transaction throughput. for 32 bit it is
perhaps slightly more debatable but then you can implement 64 bit one on
top of 2 32 bits ones.

>     Franck> all else fails you can always fallback on recursion but
> Oh no you can't!

in what way?

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Colin Adams-3
Re: Memory leak with cursors and data structures
Reply Threaded MoreMore options
Print post
Permalink
2008/8/19 Franck Arnaud <franck@...>:

>> If the compiler can implement tail recursion, why can't you?
>
> well you can actually:

Me?? I was asking about you!

>>     Franck> all else fails you can always fallback on recursion but
>> Oh no you can't!
>
> in what way?

You will run out of stack space.

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop