Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #8274 > unrolled thread

Bulk Array Element Allocation, is it faster?

Back to article view | Back to comp.lang.java.programmer

Contents

  Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-25 03:17 +0200
    Re: Bulk Array Element Allocation, is it faster? Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-24 21:37 -0400
      Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-25 10:39 +0200
    Re: Bulk Array Element Allocation, is it faster? Patricia Shanahan <pats@acm.org> - 2011-09-24 18:41 -0700
      Re: Bulk Array Element Allocation, is it faster? Robert Klemme <shortcutter@googlemail.com> - 2011-09-25 12:57 +0200
        Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-25 13:38 +0200
          Re: Bulk Array Element Allocation, is it faster? Robert Klemme <shortcutter@googlemail.com> - 2011-09-25 14:16 +0200
            Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-25 16:04 +0200
              Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-25 16:11 +0200
                Re: Bulk Array Element Allocation, is it faster? Patricia Shanahan <pats@acm.org> - 2011-09-25 09:30 -0700
              Re: Bulk Array Element Allocation, is it faster? Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-25 10:59 -0400
                Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-25 17:14 +0200
                  Re: Bulk Array Element Allocation, is it faster? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-09-25 15:26 +0000
                  Re: Bulk Array Element Allocation, is it faster? Lew <lewbloch@gmail.com> - 2011-09-25 11:02 -0700
                    Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-25 20:19 +0200
                      Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-25 20:21 +0200
                  Re: Bulk Array Element Allocation, is it faster? Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-25 17:48 -0400
                    Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-26 00:10 +0200
    Re: Bulk Array Element Allocation, is it faster? Roedy Green <see_website@mindprod.com.invalid> - 2011-09-24 19:05 -0700
      Re: Bulk Array Element Allocation, is it faster? Lew <lewbloch@gmail.com> - 2011-09-24 23:22 -0700
        Re: Bulk Array Element Allocation, is it faster? Roedy Green <see_website@mindprod.com.invalid> - 2011-09-25 00:23 -0700
          Re: Bulk Array Element Allocation, is it faster? Lew <lewbloch@gmail.com> - 2011-09-25 11:17 -0700
          Re: Bulk Array Element Allocation, is it faster? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-09-25 14:00 -0500
      Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-25 10:47 +0200
        Re: Bulk Array Element Allocation, is it faster? Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-25 08:07 -0400
          Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-25 19:21 +0200
            Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-25 19:41 +0200
            Re: Bulk Array Element Allocation, is it faster? Lew <lewbloch@gmail.com> - 2011-09-25 11:28 -0700
              Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-25 21:25 +0200
                Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-25 23:50 +0200
                Re: Bulk Array Element Allocation, is it faster? Lew <lewbloch@gmail.com> - 2011-09-25 15:43 -0700
                  Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-26 01:06 +0200
                    Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-26 01:21 +0200
                      Re: Bulk Array Element Allocation, is it faster? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-09-26 06:00 +0000
                        Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-26 14:52 +0200
                          Re: Bulk Array Element Allocation, is it faster? Jan Burse <janburse@fastmail.fm> - 2011-09-26 15:02 +0200

Page 2 of 2 — ← Prev page 1 [2]

#8282

On Sat, 24 Sep 2011 23:22:45 -0700 (PDT), Lew <lewbloch@gmail.com>
wrote, quoted or indirectly quoted someone who said :

>Foo#bar will be cleared to 'null' upon first construction, then initialized to 'null' by the explicit initialization. 
> Both steps happen.  Both steps are required to happen, and they're required to happen separately.

I doubt that. The JLS never says exactly how something works, just
what the net effect must be.  It is part of what makes it so difficult
to follow.  A JLS for programmers rather than implementors might
describe a simple reference implementation, and say, "As a programmer
you can presume it works like this, but actual implementations will be
more sophisticated and may not give exactly the same behaviour as this
simple explanation. For those fine points, see the implementors JLS."

So for example it could describe how a simple GC works. 

In most cases the second init to null could be dropped by a clever
optimiser because it would have the same net effect.

Of course I defer to you and Patricia on divining the meaning of the
JLS.
-- 
Roedy Green Canadian Mind Products
http://mindprod.com
It should not be considered an error when the user starts something
already started or stops something already stopped. This applies
to browsers, services, editors... It is inexcusable to 
punish the user by requiring some elaborate sequence to atone,
e.g. open the task editor, find and kill some processes.

[toc] | [prev] | [next] | [standalone]

#8304

Roedy Green wrote:
>  Lew wrote, quoted or indirectly quoted someone who said :
>> Foo#bar will be cleared to 'null' upon first construction, then initialized to 'null' by the explicit initialization. 
>> Both steps happen.  Both steps are required to happen, and they're required to happen separately.
> 
> I doubt that. The JLS never says exactly how something works, just

> what the net effect must be.  It is part of what makes it so difficult

Let me settle your doubt, then, because the JLS does say exactly that.

JLS §12.5:
http://java.sun.com/docs/books/jls/third_edition/html/execution.html#12.5
"Whenever a new class instance is created, memory space is allocated for it with room for all the instance variables declared in the class type and all the instance variables declared in each superclass of the class type, including all the instance variables that may be hidden (§8.3). If there is not sufficient space available to allocate memory for the object, then creation of the class instance completes abruptly with an OutOfMemoryError. Otherwise, all the instance variables in the new object, including those declared in superclasses, are initialized to their default values (§4.12.5).
"Just before a reference to the newly created object is returned as the result, the indicated constructor is processed to initialize the new object using the following procedure:
"...
"4. Execute the instance initializers and instance variable initializers for this class, assigning the values of instance variable initializers to the corresponding instance variables, in the left-to-right order in which they appear textually in the source code for the class. If execution of any of these initializers results in an exception, then no further initializers are processed and this procedure completes abruptly with that same exception. Otherwise, continue with step 5. (In some early implementations, the compiler incorrectly omitted the code to initialize a field if the field initializer expression was a constant expression whose value was equal to the default initialization value for its type.)"


> to follow.  A JLS for programmers rather than implementors might
> describe a simple reference implementation, and say, "As a programmer
> you can presume it works like this, but actual implementations will be
> more sophisticated and may not give exactly the same behaviour as this
> simple explanation. For those fine points, see the implementors JLS."

The JLS is extremely explicit about the order and result of steps to load, allocate and initialize classes and instances.  In this particular, non-hypothetical case, it requires members to get their default values, then separately to process explicit initializers, even (and especially) if the initialization is to the same default value.


> So for example it could describe how a simple GC works. 
> 
> In most cases the second init to null could be dropped by a clever
> optimiser because it would have the same net effect.

Except that that is, as you see from the cited passage, explicitly forbidden.

> Of course I defer to you and Patricia on divining the meaning of the
> JLS.

You don't need to.  Just read the cited passage for yourself.

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#8309

On 9/25/2011 2:23 AM, Roedy Green wrote:
> On Sat, 24 Sep 2011 23:22:45 -0700 (PDT), Lew<lewbloch@gmail.com>
> wrote, quoted or indirectly quoted someone who said :
>
>> Foo#bar will be cleared to 'null' upon first construction, then initialized to 'null' by the explicit initialization.
>> Both steps happen.  Both steps are required to happen, and they're required to happen separately.
>
> I doubt that. The JLS never says exactly how something works, just
> what the net effect must be.

The JLS clearly states the full observational effects of any action, 
particularly in the realm of object initialization and the memory model.

> It is part of what makes it so difficult to follow.

The JLS is not difficult to follow. ISO C++11 is difficult to follow. 
Well, the section on generic type inference could use a few more 
examples to be easier to follow, but even that is relatively 
straightforward.

 > A JLS for programmers rather than implementors might
> describe a simple reference implementation, and say, "As a programmer
> you can presume it works like this, but actual implementations will be
> more sophisticated and may not give exactly the same behaviour as this
> simple explanation. For those fine points, see the implementors JLS."

As I stated earlier, the JLS states full observational effects. If the 
underlying behavior is not the same (e.g., using escape analysis to 
change heap allocations to stack allocations), it would require advanced 
introspective techniques to observe this which are well beyond the 
semantics of Java itself.

-- 
Beware of bugs in the above code; I have only proved it correct, not 
tried it. -- Donald E. Knuth

[toc] | [prev] | [next] | [standalone]

#8284

Roedy Green schrieb:
> new does two things:
> 1. allocates X bytes of space
> 2. initialises that block of space to a pattern.

So a dumb translation of the loop would be:

   1. for each i between 0 and n-1
        1.1 allocates X bytes of space
        1.2 call the initializer

Then I was more thinking that the loop does the
following, i.e. is cleverly compiled to:

   1. allocates n*X bytes of space
   2. for each i between 0 and n-1
        2.1 call the initializer for location X*i

At least I would hand assembler it like this.
Saving n-1 calls to the heap allocator.

But maybe positive effect is not based on such
a clever allocation and only on what Patricia said.

I was already googling a little bit about the
compilation techniques found for JIT today, but
did not yet hit any evidence for clever loop
allocation, but it is so obvious I really it
must be done. But maybe it is not done because
of multi-threading or GC, who knows...

Bye

[toc] | [prev] | [next] | [standalone]

#8290

On 9/25/2011 4:47 AM, Jan Burse wrote:
> Roedy Green schrieb:
>> new does two things:
>> 1. allocates X bytes of space
>> 2. initialises that block of space to a pattern.
>
> So a dumb translation of the loop would be:
>
> 1. for each i between 0 and n-1
> 1.1 allocates X bytes of space
> 1.2 call the initializer
>
> Then I was more thinking that the loop does the
> following, i.e. is cleverly compiled to:
>
> 1. allocates n*X bytes of space
> 2. for each i between 0 and n-1
> 2.1 call the initializer for location X*i
>
> At least I would hand assembler it like this.
> Saving n-1 calls to the heap allocator.

     Since the heap allocator probably consists of one compare-and-
branch ("Is there enough room?") and one addition ("Advance the
nextFreeAddress pointer"), the savings are unlikely to be large.
This isn't malloc(), you know.

> I was already googling a little bit about the
> compilation techniques found for JIT today, but
> did not yet hit any evidence for clever loop
> allocation, but it is so obvious I really it
> must be done. But maybe it is not done because
> of multi-threading or GC, who knows...

     Note that the semantics of the bulk and lazy allocations
in your original example are quite different.  An "optimization"
that changes the meaning of the code is only a benefit if the
code was wrong to begin with. ;-)

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#8299

Eric Sosman schrieb:
>      Note that the semantics of the bulk and lazy allocations
> in your original example are quite different.  An "optimization"
> that changes the meaning of the code is only a benefit if the
> code was wrong to begin with. ;-)

What I do in the code has nothing to do with my question. My
question circles only around the following code fragment:

     Bla[] bla = new Bla[n];
     for (int i=0; i<n; i++) {
         bla[i] = new Bla();
     }

And what the JIT does. And not what I am doing in a comparison
with lazy. That is why I started my post with:

"I just wonder wether modern JIT do optimize
Code of the following form:"

Please focus on that.

Bye

[toc] | [prev] | [next] | [standalone]

#8300

Jan Burse schrieb:
> "I just wonder wether modern JIT do optimize
> Code of the following form:"
>
> Please focus on that.

Focus is also on JIT and not on JVM. So more
on compilation techniques than on execution
techniques (where draw the line?). Answer
could be balantly that JIT does nothing, and
then it must be something in the JVM.

Andreas Leitgreb;
 > I understand perfectly well, that you *were* resorting
 > to those assumptions when you first noticed the effect,
 > but after Patricia's and others' answers I wouldn't
 > expect those assumptions to be still necessary to
 > explain your observations.

But when the JIT would do something, then it
is not necessary that the JVM does something,
and would be a technique that also works on
old CPUs without pipelining super cache
whatever. I did not not yet have time to test
the phaenomen on old CPU.

Probably when I switch to old CPUs and also
old JDKs I will also end up with old JITs.
Anyway would be interested into JIT insights
old and new.

Bye

[toc] | [prev] | [next] | [standalone]

#8306

On Sunday, September 25, 2011 10:21:42 AM UTC-7, Jan Burse wrote:
> Eric Sosman schrieb:
> >      Note that the semantics of the bulk and lazy allocations
> > in your original example are quite different.  An "optimization"
> > that changes the meaning of the code is only a benefit if the
> > code was wrong to begin with. ;-)
> 
> What I do in the code has nothing to do with my question. My

It has a great deal to do with your question.

> question circles only around the following code fragment:
> 
>      Bla[] bla = new Bla[n];

Here the system does allocate, as you plaintively request, "n*X bytes of space", where "X" is the size of a pointer.

>      for (int i=0; i<n; i++) {
>          bla[i] = new Bla();
>      }

How would you imagine the JIT would optimize this without taking semantics into account?  Each 'Bla' is required to be independently GC-able, you know.  The semantics of 'Bla[]' is not a block of instances; it's a block of references.

How would you bulk allocate a block of references each to a different reference?  About the only way is to add a fixed offset to the value pushed into each successive array element, but that's already what you are doing with 'new' anyway, so you aren't "optimizing" by doing the same thing. 

If the 'Bla' constructor is heavyweight, the construction of your n 'Bla' instances will far outweigh any slight overhead in calculating that offset increase for each array element.

I just don't see how you expect to bulk-load n different pointers into that array.  Could you explain that in more detail, please?

> And what the JIT does. And not what I am doing in a comparison
> with lazy. That is why I started my post with:
> 
> "I just wonder wether [sic] modern JIT [sic] do optimize
> Code [sic] of the following form:"
> 
> Please focus on that.

Aye, aye, focusing on that, Captain!

The answer is "nothing", because the semantics of the operation are such that the current mechanism is already quite close to optimal.  This is what people have been explaining to you, that you dismissed as irrelevant.

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#8311

Lew schrieb:
> How would you imagine the JIT would optimize this
 > without taking semantics into account?  Each 'Bla'
 > is required to be independently GC-able, you know.

In my posts I mentioned two possible optimizations.
Optimization 1: Moveing the locking outside of the
loop, Optimization 2: Allocating at once n*X where
X is the space for the Bla record, not the space
for the Bla point.

Since after allocation, we have the assignment
bla[i] = new Bla(), the object cannot escape as
long as bla does not escape, so there should be
not much problem with GC, but I am not 100% sure
what the problems with GC should be.

But anyway, let speak the figures, and lets stop
musing too much. I did some testing and it shows
that the 64bit can do the "speed up" whereby the
32bit cannot do it:

OS	JDK	Arch	Bulk	Lazy	Delta %
Win 	1.6 	64bit	8'771	9'805	11.8%
Win 	1.6 	32bit	14'587	14'744	1.1%
Win	1.5 	32bit	17'139	17'405	1.6%
Mac	1.6	64bit	11'003	12'363	12.4%
Unix	1.6	32bit	26'517	26'858	1.3%

Still this leaves open the question whether the
64-bit JIT is clever or the 64-bit JVM is clever
or the 64-bit CPU is clever.

Definitely it seems that the 32-bit is not clever,
there we all see a small overhead for the lazy,
which I interpret as the additional checks, eventually
done repeatedly, for the lazy.

 > The answer is "nothing", because the semantics
 > of the operation are such that the current
 > mechanism is already quite close to optimal.
 > This is what people have been explaining to you,
 > that you dismissed as irrelevant.

Where do you see "nothing" in the above figures?

Bye

[toc] | [prev] | [next] | [standalone]

#8314

Jan Burse schrieb:
>
> OS    JDK    Arch    Bulk    Lazy    Delta %
> Win     1.6     64bit    8'771    9'805    11.8%
> Win     1.6     32bit    14'587    14'744    1.1%
> Win    1.5     32bit    17'139    17'405    1.6%
> Mac    1.6    64bit    11'003    12'363    12.4%
> Unix    1.6    32bit    26'517    26'858    1.3%

Update:

Win	1.7	64bit	8'159	8'975	10.0%

Same machine like 1.6 64bit testing was done,
just another JDK, the newer 1.7. Advantage of
bulk over lazy slightly less pronounced.

But application itself 10% faster again (sic!).

Bye

[toc] | [prev] | [next] | [standalone]

#8316

On Sunday, September 25, 2011 12:25:18 PM UTC-7, Jan Burse wrote:
> Lew schrieb:
> > How would you imagine the JIT would optimize this
>  > without taking semantics into account?  Each 'Bla'
>  > is required to be independently GC-able, you know.
> 
> In my posts I mentioned two possible optimizations.
> Optimization 1: Moveing the locking outside of the
> loop, Optimization 2: Allocating at once n*X where

That's not an optimization because things might need to happen in between loop cycles, so you can't "lock the heap" that long and call it an "optimization".

Semantically an array of n references is an array of n separate references.  You can't count on the memory allocations to be contiguous, shouldn't have to count on that, and you certainly can't count on each reference becoming eligible for GC at the same time.  GC in turn moves things around anyway, so any "benefit" of contiguous allocation will be gone quite quickly, if it ever existed in the first place.

And the point you ignore is that the "benefit" of contiguous allocation is questionable, let alone of your rather bizarre suggestion to move the "locking of the heap" outside the loop.  Each 'new' just bumps up the heap pointer, so it's not much faster to bump it once than n times, in the grand scheme of things.  Not when your tiny advantage is quickly eaten up by circumstances immediately afterward anyway.


> X is the space for the Bla record, not the space
> for the Bla point.
> 

But that's the thing that's semantically different!

You can't "optimize" allocation of n references to also create a block of n instances.  The optimizer cannot know that that is the intended use of the array.  You can't "optimize" the allocation of n instances consecutively either, because you have to know a whole lot about what those n constructors will try to do, including possibly allocate heap themselves or except out prematurely.  For the few cases where block allocation *might* provide negligible speedup, it's not worth the analysis effort to determine that this one time is one of those rare exceptions when allocation might be sped up enough for anyone to notice.

As people keep pointing out in this conversation.

> Since after allocation, we have the assignment
> bla[i] = new Bla(), the object cannot escape as
> long as bla does not escape, so there should be
> not much problem with GC, but I am not 100% sure
> what the problems with GC should be.

What do you even mean by this?  What do you mean by the object "escaping"?

I don't know about "problems" with GC, but you cannot be sure that the individual instances pointed to by the 'bla[i]' pointers will be descoped at the same time.  Ergo you cannot know ahead of time when they will be eligible for GC.  Instances that survive GC will be moved to contiguous memory blocks, but not their original ones.  Whatever negligible benefit you might have gotten, but more likely did not, from contiguous allocation of the 'Bla' instances will be wiped out.

> But anyway, let speak the figures, and lets stop
> musing too much. I did some testing and it shows
> that the 64bit can do the "speed up" whereby the
> 32bit cannot do it:
> 
> OS	JDK	Arch	Bulk	Lazy	Delta %
> Win 	1.6 	64bit	8'771	9'805	11.8%
> Win 	1.6 	32bit	14'587	14'744	1.1%
> Win	1.5 	32bit	17'139	17'405	1.6%
> Mac	1.6	64bit	11'003	12'363	12.4%
> Unix	1.6	32bit	26'517	26'858	1.3%
> 
> Still this leaves open the question whether the
> 64-bit JIT is clever or the 64-bit JVM is clever
> or the 64-bit CPU is clever.
> 
> Definitely it seems that the 32-bit is not clever,
> there we all see a small overhead for the lazy,
> which I interpret as the additional checks, eventually
> done repeatedly, for the lazy.
> 
>> The answer is "nothing", because the semantics
>> of the operation are such that the current
>> mechanism is already quite close to optimal.
>> This is what people have been explaining to you,
>> that you dismissed as irrelevant.
> 
> Where do you see "nothing" in the above figures?

Everywhere.  You have some questionable method of timing something that you do not describe, let alone with any precision, using doubtful methodology and suspect reasoning without reference to experimental error or confidence analysis.  Your numbers literally tell me nothing.

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#8317

Lew schrieb:
> You can't "optimize" allocation of n references
> to also create a block of n instances.  The optimizer
 > cannot know that that is the intended use of the array.

The following optimization works independent of
the use of the array. You can even nullify an
array element or set it to a newly created object.
So going from an unoptimized code:

     for (int i=0; i<n; i++) {
        lock heap
        bla[i] = new Bla(i);
        unlock heap
     }

To the following:


     lock heap
     p = allocate size n*X
     unlock heap
     for (int i=0; i<n; i++) {
        bla[i] = init p;
        p += x;
     }

Shouldn't be a problem for a decent compilers.
Various compilers do much more with loops. Why
do you doubt that this optimization is possible.

 > For the few cases where block allocation
 > *might* provide negligible speedup.

Oh, you don't really doubt that it is possible.
You rather doubt that it is worth. Well I
can tell you, in my application, the allocation
of small arrays with preallocated empty constructor
less initialized objects is done over and over.

I have recently run visual vm. It is really
what is mostly happening in the app during
the process of solving a problem.

And it seems that since it is so dominant any
changes in the way this is done are directly
seen in the timings. Here are the timings
again:

OS    JDK    Arch    Bulk    Lazy    Delta %
Win    1.7    64bit    8'159    8'975    10.0%
Win     1.6     64bit    8'771    9'805    11.8%
Win     1.6     32bit    14'587    14'744    1.1%
Win    1.5     32bit    17'139    17'405    1.6%
Mac    1.6    64bit    11'003    12'363    12.4%
Unix    1.6    32bit    26'517    26'858    1.3%

On 64bit the bulk is 10% faster for the
present application that makes heavy use
of allocating these objects and arrays.

 > As people keep pointing out in this conversation.

I know, it is logical that if it were that
the application would not make heavy use
of allocating these objects and arrays, then
nothing would be seen. But if nothing would
be seen at all, I wouldn't post here and
asking what is going on. But something is
seen, the 10%. It is not "nothing".

So what is going on in the 64bit?

Bye




Bye

[toc] | [prev] | [next] | [standalone]

#8318

Jan Burse schrieb:
> So what is going on in the 64bit?

Problem resolved! Thanks all for your attention and
good advise. Especially persisting in look at the
application, there was a bottleneck somewhere else.
Dunno why it wasn't seen for 32-bit, but anyway,
everything is fine now. Will revert to the lazy
version since it uses less memory...

Best Regards

[toc] | [prev] | [next] | [standalone]

#8324

Jan Burse <janburse@fastmail.fm> wrote:
> Jan Burse schrieb:
>> So what is going on in the 64bit?
> Problem resolved! Thanks all for your attention and
> good advise. Especially persisting in look at the
> application, there was a bottleneck somewhere else.

If it can be demonstrated within the context of:
   bulk instanciation in a loop
versus
   on-demand instanciation  ("lazy")
then I'd be curious about where/what that extra bottleneck
was.

> Dunno why it wasn't seen for 32-bit, ...

[toc] | [prev] | [next] | [standalone]

#8329

Andreas Leitgeb schrieb:
> Jan Burse<janburse@fastmail.fm>  wrote:
>> Jan Burse schrieb:
>>> So what is going on in the 64bit?
>> Problem resolved! Thanks all for your attention and
>> good advise. Especially persisting in look at the
>> application, there was a bottleneck somewhere else.
>
> If it can be demonstrated within the context of:
>     bulk instanciation in a loop
> versus
>     on-demand instanciation  ("lazy")
> then I'd be curious about where/what that extra bottleneck
> was.
>
>> Dunno why it wasn't seen for 32-bit, ...

Lets assume the following simplified lazy code:

     bla = new Bla[n];
     ..
     if (bla[i]==null)      /* the null test */
        bla[i]=new Bla();   /* the new call */
     ..

I thought that in the lazy version, bla[i] was
maximally n times tested for null. It was
based on the figures I obtained, namely
counting the new calls in bulk and in lazy:

    Bulk: 84'393'262
    Lazy: 81'662'843
    http://www.facebook.com/photo.php?fbid=199117193490169

But the number of new calls is not the
same as the number of null tests, since
a new call is only performed when the null
test succeeds.

So it turned out that there were much more
null tests than new calls. In certain sub
test cases the number can arbirarily go up, so
instead of n tests one might have m*n tests
where m depends on the sub test case, and
is not related to n.

Since my null test is in practice a little
bit more complex in my application and since
m is much above 1 in many of my sub test
cases, the overhead became recognizable.

Meanwhile I could reduce the complexity and
subsequently the frequency of the null test
in my application and the overhead for lazy
has dimished.

There is a little guard which is called like
m times. And then the null test is maximally
n times done. Since the guard is cheap and
since it guards a couple of null tests, the
overhead is now small.

Bye

[toc] | [prev] | [next] | [standalone]

#8330

Jan Burse schrieb:
> There is a little guard which is called like
> m times. And then the null test is maximally
> n times done. Since the guard is cheap and
> since it guards a couple of null tests, the
> overhead is now small.

This could be transformed to other problems.
Like for example an uninitialized matrice.
Just put the guard on the rows of a matrice,
and intialize rows in a bulk instead of the
elements of the matrice. Clearly this gives
a speed-up.

Why is still null test on elements needed?
Well the guard is reset from time to time.
At least this happens in my application.
Because otherwise one could object, the
guard is enough, why should there be
additional null tests on elements?

Bye

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.java.programmer

csiph-web