Memory allocation overhead

38 Messages Forum Options Options
Embed this topic
Permalink
1 2
Eric Bezault
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
In reply to this post by Colin Paul Adams
Colin Paul Adams wrote:

>>>>>> "Eric" == Eric Bezault <ericb@...> writes:
>
>     Eric> technique that I use is to try to reuse objects, rather than
>     Eric> giving them back to the GC and creating new ones right
>     Eric> after. In gec, I have AST visitor classes to implement the
>     Eric> different Eiffel "Degree" compilation passes. They all try
>     Eric> to keep the intermediary objects that they need to process a
>     Eric> given imput class. They reuse these intermediary objects
>     Eric> when processing the next input class, and so forth.
>
> Can you point me to a specific example?

Instead of having iterator objects, I use the visitor pattern.
See the descendants of ET_AST_PROCESSOR. And for a given task
I use the same visitor object on all classes, instead of having
a different object each time. This object can then keep some
context that will be reinitialized each time (without necessarily
having to create new objects). For example in
ET_FEATURE_ADAPTATION_RESOLVER, this visitor uses hash-tables
in order to make sense out of the inheritance clause feature
adaptation of the class being processed. This visitor object
is reused for all input classes, without having to create a new
set of hash-tables each time.

> I am currently trying this with the iterators used to evaluate XPath
> sequences. I am retaining copies on a once DS_ARRAYED_STACK. So far,
> this is actually increasing the runtime (but it appears sensitive to
> the size of the stack, so I am currently trying with just a DS_CELL to
> see if this is better).

I didn't mean to implement yourself a memory management system
by hand. It's not obvious that the time spent doing this manual
memory management, with a pool of objects, will be more efficient
than the GC itself.

--
Eric Bezault
mailto:ericb@...
http://www.gobosoft.com

-------------------------------------------------------------------------
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Eric Bezault
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
In reply to this post by Colin Paul Adams
Colin Paul Adams wrote:

> But I am now wondering about code inlining. It appears that gec does
> not inline all three routines new_child_tree_iterator, release_iterator
> and new_descendant_tree_iterator in the code below. (Note that the bulk of
> the class is commented out. The test program then runs in 21 minutes
> and 8 seconds, as opposed to 20 minutes and 28 seconds (+- 3 seconds)
> with the creations inlined, and no call to release_iterator (there is
> an extra assignment to Void of the iterator passed to release_iterator
> following the call to release_iterator, but I hardly think that can
> account for the difference). With all the commented-out code restored,
> (and assignemt of 4 default values to attributes in the creation
> procedures, which costs about 6 seconds) the time rises to 21 minutes
> and 52 seconds.

I would surprise me that the level of inlining currently implemented
in gec has anything to do with the time actually spent in the GC that
was shown in your profiling results.

--
Eric Bezault
mailto:ericb@...
http://www.gobosoft.com

-------------------------------------------------------------------------
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Eric Bezault
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
In reply to this post by Eric Bezault
Eric Bezault wrote:
> Colin Paul Adams wrote:
>> Do you use free at all? Obviously that won't reduce the number of
>> allocations, but it will reduce the number of objects the GC has to
>> deal with. Does it give any advantage over assigning Void to the
>> reference?
>
> I don't use free.

I just saw that in your last check-in you used MEMORY.free.
This is a bad idea in my opinion. And it won't help anyway
when using gec+boehm (it's currently implemented as a no-op).

I talked about reducing the amount of garbage generated,
not about manually managing the memory.

--
Eric Bezault
mailto:ericb@...
http://www.gobosoft.com

-------------------------------------------------------------------------
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Emmanuel Stapf
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
> I just saw that in your last check-in you used MEMORY.free.
> This is a bad idea in my opinion. And it won't help anyway
> when using gec+boehm (it's currently implemented as a no-op).

And this is actually very dangerous because even if you think there are no
references to the object, the generated C code might still have a reference
or two. So at the next GC cycle it could basically cause a problem (be a
segmentation violation or something else). I'm not sure why it was added in
MEMORY at the first place, but I would not use it.

Manu


-------------------------------------------------------------------------
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
------------------------------------------------------------------------  
Eiffel Software
805-685-1006
http://www.eiffel.com       
Customer support: http://support.eiffel.com       
User group: http://groups.eiffel.com/join       
------------------------------------------------------------------------  
Colin Paul Adams
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
>>>>> "Emmanuel" == Emmanuel Stapf [ES] <manus@...> writes:

    Emmanuel> think there are no references to the object, the
    Emmanuel> generated C code might still have a reference or two. So
    Emmanuel> at the next GC cycle it could basically cause a problem
    Emmanuel> (be a segmentation violation or something else). I'm not
    Emmanuel> sure why it was added in MEMORY at the first place, but
    Emmanuel> I would not use it.

In that case it had better be marked obsolete.
--
Colin Adams
Preston Lancashire

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Colin Paul Adams
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
In reply to this post by Eric Bezault
>>>>> "Eric" == Eric Bezault <ericb@...> writes:

    Eric> I just saw that in your last check-in you used MEMORY.free.
I've removed it now.

--
Colin Adams
Preston Lancashire

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Colin Paul Adams
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
In reply to this post by Eric Bezault
>>>>> "Eric" == Eric Bezault <ericb@...> writes:

    Eric> I would surprise me that the level of inlining currently
    Eric> implemented in gec has anything to do with the time actually
    Eric> spent in the GC that was shown in your profiling results.

I later checked in the gestalt.h file, and there was no trace of these
routines. So I guess they were optimized away (in one case) and
inlined in the others.
I don't understand how the runtime increase could have occured, but I
have abandoned that approach now.
--
Colin Adams
Preston Lancashire

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Colin Paul Adams
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
In reply to this post by Eric Bezault
>>>>> "Eric" == Eric Bezault <ericb@...> writes:

    Eric> I just saw that in your last check-in you used MEMORY.free.
    Eric> This is a bad idea in my opinion. And it won't help anyway
    Eric> when using gec+boehm (it's currently implemented as a
    Eric> no-op).

Are other features of MEMORY (such as allocate_fast and
set_memory_threshold) implemented?
--
Colin Adams
Preston Lancashire

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Colin Paul Adams
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
In reply to this post by Eric Bezault
>>>>> "Eric" == Eric Bezault <ericb@...> writes:

    Eric> I would surprise me that the level of inlining currently
    Eric> implemented in gec has anything to do with the time actually
    Eric> spent in the GC that was shown in your profiling results.

That may be the case, but there is some (doubtful) evidence to the
contrary.

Since currently my execution time is approaching 4 times faster than
when I previously profiled, I thought I would profile again to confirm
that GC problems are still predominant (I was fairly sure they were,
as top shows 200-300% CPU utilization still, which can only come from
parallel marking).

The new profile confirms this is the case, but there is the suggestion
that a failure to inline will be significant if the GC overhead could
be largely eliminated (I have named the top three calls - I'm assuming
the comment in the .h file immediately precedes the extern
declaration.):

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total          
 time   seconds   seconds    calls   s/call   s/call  name    
 31.55    675.04   675.04                             GC_mark_from
 16.24   1022.55   347.51                             GC_steal_mark_stack
 16.17   1368.49   345.94                             GC_header_cache_miss
  8.08   1541.30   172.81                             GC_mark_local
  1.44   1572.07    30.77                             GC_reclaim_clear
  1.27   1599.21    27.14 530952040     0.00     0.00  T131f10 DS_ARRAYED_LIST [INTEGER_32].item
  1.19   1624.57    25.36                             GC_push_marked
  0.84   1642.47    17.90                             GC_generic_malloc_many
  0.81   1659.80    17.34 128695782     0.00     0.00  T171x16745 XM_XPATH_NODE.as_tree_node
  0.77   1676.37    16.57 262642848     0.00     0.00  T515f29 XM_XPATH_ATTRIBUTE_COLLECTION.is_attribute_index_valid
  0.64   1690.09    13.72                             GC_do_local_mark
  0.58   1702.48    12.39 181451145     0.00     0.00  T17x34
  0.52   1713.50    11.02 181905247     0.00     0.00  T15f4
  0.50   1724.23    10.73                             GC_malloc
  0.50   1734.90    10.67                             GC_block_was_dirty
  0.47   1745.00    10.10                             GC_apply_to_all_blocks
  0.34   1752.22     7.22
  GC_install_header

So we can see that the second highest Eiffel routine is
XM_XPATH_NODE.as_tree_node. Since the definition of this is:

        as_tree_node: XM_XPATH_TREE_NODE is
                        -- `Current' seen as a tree node
                do
                        Result := Current
                end

I would expect this to be a no-op. Is it not a call that provides
typing information only to the compiler, so that at run-time there is
not need for it?
--
Colin Adams
Preston Lancashire

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Eric Bezault
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
In reply to this post by Colin Paul Adams
Colin Paul Adams wrote:
>>>>>> "Eric" == Eric Bezault <ericb@...> writes:
>
>     Eric> I just saw that in your last check-in you used MEMORY.free.
>     Eric> This is a bad idea in my opinion. And it won't help anyway
>     Eric> when using gec+boehm (it's currently implemented as a
>     Eric> no-op).
>
> Are other features of MEMORY (such as allocate_fast and
> set_memory_threshold) implemented?

Not yet in gec. And I haven't studied yet whether the
Boehm GC would provide such functionality.

--
Eric Bezault
mailto:ericb@...
http://www.gobosoft.com

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Eric Bezault
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
In reply to this post by Colin Paul Adams
Colin Paul Adams wrote:
> I would expect this to be a no-op. Is it not a call that provides
> typing information only to the compiler, so that at run-time there is
> not need for it?

As I claimed many times in the past, no effort has been
made yet to improve the performance of the generated C
code. IN particular in term of inlining or dynamic
binding.

My priority is to be fully compliant with ECMA and ISE
before tackling performance issues. And from what I can
see, spending time on this issue now will not significantly
improve your figures as long as most of the time is still
spent in the GC.

--
Eric Bezault
mailto:ericb@...
http://www.gobosoft.com

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Colin Paul Adams
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
In reply to this post by Eric Bezault
>>>>> "Eric" == Eric Bezault <ericb@...> writes:

    >> Are other features of MEMORY (such as allocate_fast and
    >> set_memory_threshold) implemented?

    Eric> Not yet in gec. And I haven't studied yet whether the Boehm
    Eric> GC would provide such functionality.

OK.

But in any case, I am fairly confident that I know what the basic
problem I have is. Fixing it is another matter.

XSLT is largely concerned with manipulating strings. So I think the
lack of read-only strings, enabling substring to avoid copying the
string contents, is likely a very major factor.

I have some evidence in support of this.

1) The runtime of my program is non-linear wrt the size of the input
data set.
2) If I use the tiny tree implementation for the input data set, the
runtime increases by more than 4 times.

The tiny tree implementation is an application of
the flyweight pattern, designed to reduce the number of objects
created. I copied the idea from Saxon (the contents of all text and
comment nodes is held as a single STRING object within the document,
and access to it is by substring, avoiding creating text and comment
node objects for this purpose), but I overlooked that substring copies
the data in Eiffel.

Accordingly, I think I shall abandon my efforts for now, and pursue
Manu's suggestion in FreeELKS for an aliased substring feature (I
think full copy-on-write semantics will need to be available for
STRINGs).
I don't doubt that there are opportunities to improve my use of
STRINGs in the code (a review would help), but I think this needs
tackling first.
--
Colin Adams
Preston Lancashire

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Lothar Scholz
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
In reply to this post by Eric Bezault
Hello Eric,

Friday, April 4, 2008, 11:55:10 PM, you wrote:

EB> Eric Bezault wrote:
>> Colin Paul Adams wrote:
>>> Do you use free at all? Obviously that won't reduce the number of
>>> allocations, but it will reduce the number of objects the GC has to
>>> deal with. Does it give any advantage over assigning Void to the
>>> reference?
>>
>> I don't use free.

EB> I just saw that in your last check-in you used MEMORY.free.
EB> This is a bad idea in my opinion. And it won't help anyway
EB> when using gec+boehm (it's currently implemented as a no-op).

Which GC version are you using? GC_free is implemented in "malloc.c"
and it works fine. I used it starting with 6.7 upto the latest
7.1.beta3-snapshot it was never a no-op.

I'm using it a lot to free large buffers and it helps to keep
memory footprint small. Waiting for a 500 KByte memory chunk to
get freed by a conservative GC is just extremely risky.

Remember if you using double and real values you might have a lot
of false positives.


--
Best regards,
 Lothar                            mailto:llothar@...


-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Colin Paul Adams
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
>>>>> "Lothar" == Lothar Scholz <llothar@...> writes:


    EB> I just saw that in your last check-in you used MEMORY.free.
    EB> This is a bad idea in my opinion.

Why? I was only using it in places where I could guarantee that the
object wouldn't be used again (not a frequent case).
It can cut down the amount of work needed by the next mark cycle.

    EB> And it won't help anyway
    EB> when using gec+boehm (it's currently implemented as a no-op).

    Lothar> Which GC version are you using? GC_free is implemented in
    Lothar> "malloc.c" and it works fine. I used it starting with 6.7
    Lothar> upto the latest 7.1.beta3-snapshot it was never a no-op.

    Lothar> I'm using it a lot to free large buffers and it helps to
    Lothar> keep memory footprint small. Waiting for a 500 KByte
    Lothar> memory chunk to get freed by a conservative GC is just
    Lothar> extremely risky.

    Lothar> Remember if you using double and real values you might
    Lothar> have a lot of false positives.

But Gobo code has to work with ISE as well as GEC. And Manu warned
that it might fail with ISE, as the C code might continue to hold a
reference to the object. That's why I removed the calls to free.
--
Colin Adams
Preston Lancashire

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Eric Bezault
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
In reply to this post by Lothar Scholz
Lothar Scholz wrote:
> EB> I just saw that in your last check-in you used MEMORY.free.
> EB> This is a bad idea in my opinion. And it won't help anyway
> EB> when using gec+boehm (it's currently implemented as a no-op).
>
> Which GC version are you using? GC_free is implemented in "malloc.c"
> and it works fine. I used it starting with 6.7 upto the latest
> 7.1.beta3-snapshot it was never a no-op.

I didn't say that GC_free was a no-op. MEMORY.free is.

--
Eric Bezault
mailto:ericb@...
http://www.gobosoft.com

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Eric Bezault
Re: Memory allocation overhead
Reply Threaded MoreMore options
Print post
Permalink
In reply to this post by Colin Paul Adams
Colin Paul Adams wrote:
>     EB> I just saw that in your last check-in you used MEMORY.free.
>     EB> This is a bad idea in my opinion.
>
> Why? I was only using it in places where I could guarantee that the
> object wouldn't be used again (not a frequent case).

It's a bad idea for two reasons. If GC have been invented,
it's because we cannot trust humans, including you. You
can guarantee that the object would not be used again
today. But what about in two years from now, after several
iterations of refactoring? And I usually don't trust
features/constructs that nobody else (except Lothar) used
despite the fact that it has been available for more
than a decade, and even more when it is related to a
so complex thing as a GC. You can use it at your own
risk in gestalt or other developments, but if possible
it would be nice if we could refrain from using it in
the Gobo package.

--
Eric Bezault
mailto:ericb@...
http://www.gobosoft.com

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Register now and save $200. Hurry, offer ends at 11:59 p.m.,
Monday, April 7! Use priority code J8TLD2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
gobo-eiffel-develop mailing list
gobo-eiffel-develop@...
https://lists.sourceforge.net/lists/listinfo/gobo-eiffel-develop
Colin Paul Adams