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 1 of 2  [1] 2  Next page →

#8274 — Bulk Array Element Allocation, is it faster?

Dear All,

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

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

When I use the above in my code, my application
spends 8800 ms in the benchmark I have.

When I then change the code to:

     Bla[] bla = new Bla[n];

     ...

     if (bla[i]==null)
        bla[i] = new Bla();

     ..

So instead of allocating all elements at once,
I will allocate them on demand in the subsequent
flow of my application.

When I use the above in my code, my application
now suddently sends 9600 ms in the benchmark
I have.

So I wonder whether eventually the JIT has
a way to detect the bulk allocate of the first
version and transform it into something more
efficient than my lazy allocation.

Any clues?

Bye

[toc] | [next] | [standalone]

#8276

On 9/24/2011 9:17 PM, Jan Burse wrote:
> Dear All,
>
> I just wonder wether modern JIT do optimize
> Code of the following form:
>
> Bla[] bla = new Bla[n];
> for (int i=0; i<n; i++) {
> bla[i] = new Bla();
> }
>
> When I use the above in my code, my application
> spends 8800 ms in the benchmark I have.
>
> When I then change the code to:
>
> Bla[] bla = new Bla[n];
>
> ...
>
> if (bla[i]==null)
> bla[i] = new Bla();
>
> ..
>
> So instead of allocating all elements at once,
> I will allocate them on demand in the subsequent
> flow of my application.

     This could be a win if you will actually use only a few of
the array elements, and if constructing a Bla is expensive (for
example, if it involves I/O).  If Bla's are cheap to make, or if
you'll wind up using most of them anyhow, there's no obvious
reason to conditionalize.

> When I use the above in my code, my application
> now suddently sends 9600 ms in the benchmark
> I have.

     Nine percent longer.  But I'm highly suspicious of those nice,
round numbers: It seems an unlikely coincidence that two rather
different chunks of code should both execute in even tenths of
seconds.  Are you sure you've measured what you want to measure?
Are you sure that what you want to measure is the important thing?

> So I wonder whether eventually the JIT has
> a way to detect the bulk allocate of the first
> version and transform it into something more
> efficient than my lazy allocation.

     Based on your (suspect) timings, "just leave it be" would be
exactly the kind of improvement you ask for.  The JIT very likely
does something like that already :-)

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

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

#8283

Eric Sosman schrieb:
>      This could be a win if you will actually use only a few of
> the array elements, and if constructing a Bla is expensive (for
> example, if it involves I/O).  If Bla's are cheap to make, or if
> you'll wind up using most of them anyhow, there's no obvious
> reason to conditionalize.

The bla <init> does nothing. And yes it could
be that a bla is not needed, that is why I
invented the lazy scheme. But I see the slowdown
especially for when all the bla's are needed.

 >      Nine percent longer.  But I'm highly suspicious of those nice,
 > round numbers: It seems an unlikely coincidence that two rather
 > different chunks of code should both execute in even tenths of
 > seconds.

Repeated measurements give different figures,
which lead me to see an accuracy of measurement
of around 100ms, so instead of telling you that
the application needs one time 9538 ms and another
time 9622 ms etc.. I gave only the order of the
time spend rounded to hundreds.

Bye

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

#8277

On 9/24/2011 6:17 PM, Jan Burse wrote:
> Dear All,
>
> I just wonder wether modern JIT do optimize
> Code of the following form:
>
> Bla[] bla = new Bla[n];
> for (int i=0; i<n; i++) {
> bla[i] = new Bla();
> }
>
> When I use the above in my code, my application
> spends 8800 ms in the benchmark I have.
>
> When I then change the code to:
>
> Bla[] bla = new Bla[n];
>
> ...
>
> if (bla[i]==null)
> bla[i] = new Bla();
>
> ..
>
> So instead of allocating all elements at once,
> I will allocate them on demand in the subsequent
> flow of my application.
>
> When I use the above in my code, my application
> now suddently sends 9600 ms in the benchmark
> I have.
>
> So I wonder whether eventually the JIT has
> a way to detect the bulk allocate of the first
> version and transform it into something more
> efficient than my lazy allocation.
>
> Any clues?

You also need to consider the general optimization of processors in
favor of doing efficiently those things they have done in the recent past.

When you do the allocation all at once, the code and data for "new
Bla()" is in cache on the second and subsequent calls. There may be
cache conflicts between "new Bla()" and the actual work, leading to
many more cache misses when you interleave them.

Doing the initialization on demand may be adding an unpredictable
conditional branch to the subsequent flow.

Patricia

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

#8288

On 09/25/2011 03:41 AM, Patricia Shanahan wrote:
> On 9/24/2011 6:17 PM, Jan Burse wrote:
>> Dear All,
>>
>> I just wonder wether modern JIT do optimize
>> Code of the following form:
>>
>> Bla[] bla = new Bla[n];
>> for (int i=0; i<n; i++) {
>> bla[i] = new Bla();
>> }
>>
>> When I use the above in my code, my application
>> spends 8800 ms in the benchmark I have.
>>
>> When I then change the code to:
>>
>> Bla[] bla = new Bla[n];
>>
>> ...
>>
>> if (bla[i]==null)
>> bla[i] = new Bla();
>>
>> ..
>>
>> So instead of allocating all elements at once,
>> I will allocate them on demand in the subsequent
>> flow of my application.
>>
>> When I use the above in my code, my application
>> now suddently sends 9600 ms in the benchmark
>> I have.
>>
>> So I wonder whether eventually the JIT has
>> a way to detect the bulk allocate of the first
>> version and transform it into something more
>> efficient than my lazy allocation.
>>
>> Any clues?
>
> You also need to consider the general optimization of processors in
> favor of doing efficiently those things they have done in the recent past.
>
> When you do the allocation all at once, the code and data for "new
> Bla()" is in cache on the second and subsequent calls. There may be
> cache conflicts between "new Bla()" and the actual work, leading to
> many more cache misses when you interleave them.
>
> Doing the initialization on demand may be adding an unpredictable
> conditional branch to the subsequent flow.

This and the fact that lazy initialization has concurrency issues when 
used in a multi threading context (which e.g. final members do not have) 
has made me use this approach less frequently.  Also, for short lived 
objects in total it might be much more efficient to just allocate the 
object even if it is not used because it won't survive new generation 
anyway.  I think the lazy init idiom only really pays off if 
construction is expensive (e.g. because it involves IO or time consuming 
calculations).  In all other cases it's better to just unconditionally 
create and let GC work.  And because of improvements in JVM technology 
the balance has moved a lot away from the lazy side because allocation 
and deallocation overhead became smaller than in earlier Java versions.

Kind regards

	robert

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

#8289

Robert Klemme schrieb:
> On 09/25/2011 03:41 AM, Patricia Shanahan wrote:
>> On 9/24/2011 6:17 PM, Jan Burse wrote:
>>> Dear All,
>>>
>>> I just wonder wether modern JIT do optimize
>>> Code of the following form:
>>>
>>> Bla[] bla = new Bla[n];
>>> for (int i=0; i<n; i++) {
>>> bla[i] = new Bla();
>>> }
>>>
>>> When I use the above in my code, my application
>>> spends 8800 ms in the benchmark I have.
>>>
>>> When I then change the code to:
>>>
>>> Bla[] bla = new Bla[n];
>>>
>>> ...
>>>
>>> if (bla[i]==null)
>>> bla[i] = new Bla();
>>>
>>> ..
>>>
>>> So instead of allocating all elements at once,
>>> I will allocate them on demand in the subsequent
>>> flow of my application.
>>>
>>> When I use the above in my code, my application
>>> now suddently sends 9600 ms in the benchmark
>>> I have.
>>>
>>> So I wonder whether eventually the JIT has
>>> a way to detect the bulk allocate of the first
>>> version and transform it into something more
>>> efficient than my lazy allocation.
>>>
>>> Any clues?
>>
>> You also need to consider the general optimization of processors in
>> favor of doing efficiently those things they have done in the recent
>> past.
>>
>> When you do the allocation all at once, the code and data for "new
>> Bla()" is in cache on the second and subsequent calls. There may be
>> cache conflicts between "new Bla()" and the actual work, leading to
>> many more cache misses when you interleave them.
>>
>> Doing the initialization on demand may be adding an unpredictable
>> conditional branch to the subsequent flow.
>
> This and the fact that lazy initialization has concurrency issues when
> used in a multi threading context (which e.g. final members do not have)
> has made me use this approach less frequently. Also, for short lived
> objects in total it might be much more efficient to just allocate the
> object even if it is not used because it won't survive new generation
> anyway. I think the lazy init idiom only really pays off if construction
> is expensive (e.g. because it involves IO or time consuming
> calculations). In all other cases it's better to just unconditionally
> create and let GC work. And because of improvements in JVM technology
> the balance has moved a lot away from the lazy side because allocation
> and deallocation overhead became smaller than in earlier Java versions.
>
> Kind regards
>
> robert

Yes, really seems so. Looks that the infinite heap idea
works (notion borrowed from a talk by Cliff Click found
on the net, should indicate that we just do this, allocate
and don't care much).

I made some additional benchmarks, in the present case the lazy
does not so much good in that it saves allocates. I got the
following figures for the application at hand:

   Bulk:  84'393'262 allocates
   Lazy:  81'662'843 allocates

So the application does not have many exit points in the flow
following the array creation, except for the last exit point
when anyway all objects were needed.

But still I have some doubts! The array I allocate are only
4 elements long or so? Why is there still such a big
difference between allocating in bulk only 4 elements and
doing them one after the other?

Overhead by the lazy detection itself? I doubt this also
since the array is anyway accessed, and the lazy check
is a small null pointer check.

I am still puzzled.

Bye

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

#8291

On 09/25/2011 01:38 PM, Jan Burse wrote:
> Robert Klemme schrieb:
>> On 09/25/2011 03:41 AM, Patricia Shanahan wrote:
>>> On 9/24/2011 6:17 PM, Jan Burse wrote:
>>>> Dear All,
>>>>
>>>> I just wonder wether modern JIT do optimize
>>>> Code of the following form:
>>>>
>>>> Bla[] bla = new Bla[n];
>>>> for (int i=0; i<n; i++) {
>>>> bla[i] = new Bla();
>>>> }
>>>>
>>>> When I use the above in my code, my application
>>>> spends 8800 ms in the benchmark I have.
>>>>
>>>> When I then change the code to:
>>>>
>>>> Bla[] bla = new Bla[n];
>>>>
>>>> ...
>>>>
>>>> if (bla[i]==null)
>>>> bla[i] = new Bla();
>>>>
>>>> ..
>>>>
>>>> So instead of allocating all elements at once,
>>>> I will allocate them on demand in the subsequent
>>>> flow of my application.
>>>>
>>>> When I use the above in my code, my application
>>>> now suddently sends 9600 ms in the benchmark
>>>> I have.
>>>>
>>>> So I wonder whether eventually the JIT has
>>>> a way to detect the bulk allocate of the first
>>>> version and transform it into something more
>>>> efficient than my lazy allocation.
>>>>
>>>> Any clues?
>>>
>>> You also need to consider the general optimization of processors in
>>> favor of doing efficiently those things they have done in the recent
>>> past.
>>>
>>> When you do the allocation all at once, the code and data for "new
>>> Bla()" is in cache on the second and subsequent calls. There may be
>>> cache conflicts between "new Bla()" and the actual work, leading to
>>> many more cache misses when you interleave them.
>>>
>>> Doing the initialization on demand may be adding an unpredictable
>>> conditional branch to the subsequent flow.
>>
>> This and the fact that lazy initialization has concurrency issues when
>> used in a multi threading context (which e.g. final members do not have)
>> has made me use this approach less frequently. Also, for short lived
>> objects in total it might be much more efficient to just allocate the
>> object even if it is not used because it won't survive new generation
>> anyway. I think the lazy init idiom only really pays off if construction
>> is expensive (e.g. because it involves IO or time consuming
>> calculations). In all other cases it's better to just unconditionally
>> create and let GC work. And because of improvements in JVM technology
>> the balance has moved a lot away from the lazy side because allocation
>> and deallocation overhead became smaller than in earlier Java versions.
>>
>> Kind regards
>>
>> robert
>
> Yes, really seems so. Looks that the infinite heap idea
> works (notion borrowed from a talk by Cliff Click found
> on the net, should indicate that we just do this, allocate
> and don't care much).
>
> I made some additional benchmarks, in the present case the lazy
> does not so much good in that it saves allocates. I got the
> following figures for the application at hand:
>
> Bulk: 84'393'262 allocates
> Lazy: 81'662'843 allocates
>
> So the application does not have many exit points in the flow
> following the array creation, except for the last exit point
> when anyway all objects were needed.
>
> But still I have some doubts! The array I allocate are only
> 4 elements long or so? Why is there still such a big
> difference between allocating in bulk only 4 elements and
> doing them one after the other?
>
> Overhead by the lazy detection itself? I doubt this also
> since the array is anyway accessed, and the lazy check
> is a small null pointer check.

Yes, but the cost is not in the check but in the branching on processor 
level (see what Patricia wrote).

Kind regards

	robert

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

#8293

Robert Klemme schrieb:
> Yes, but the cost is not in the check but in the branching on processor
> level (see what Patricia wrote).

Depends on the processor and on the branch. If
new is just heap -= size, what some papers suggest,
then it might not be important.

But if new is much more, then sure the branch
interrupts the normal code flow so much that
instruction piplining gets out of sync. And
the speed gain by instruction overlapping
is lost.

But my hypothesis is more that something
algorithmically on a higher level happens than
something on the lower hardware level.

So I also found something about "Lock
coarsening"(*), so if the new needs some lock
this lock could be aquired before the initialization
loop and released after the initialization
loop. So that:

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

Would only need 1 locking instruction pair,
where as:

     Bla[] bla = new Bla[n];

     ...

     if (bla[i]==null)
        bla[i] = new Bla();

     ..

Would need n locking instruction pairs. But I
would still need some confirmation that JITs
are able to do such an optimization on a higher
level in the present case.

I am also not sure whether the bounded for
counts as a looping control flow, so that "Lock
coarsening" would not be applicable. But
I guess it can be deemed non looping, so that
the technique would be applicable.

Currently I am planning to change the loop
to something like that:

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

So that the JIT has less information on what
the loop is about, and to do some new
measurements. To be fair I would also use
createBla() in the lazy scenario. Lets see
what happens.

Best Regards

(*)
http://java.sun.com/performance/reference/whitepapers/6_performance.html#2.1.2

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

#8294

Jan Burse schrieb:
> Currently I am planning to change the loop
> to something like that:
>
>      Bla[] bla = new Bla[n];
>      for (int i=0; i<n; i++) {
>          bla[i] = createBla();
>      }
>
> So that the JIT has less information on what
> the loop is about, and to do some new
> measurements. To be fair I would also use
> createBla() in the lazy scenario. Lets see
> what happens.

Maybe there is a bug somewhere else in the
application that leads to the performance loss.
There are also points in the application where
some of the bla elements are forcefully set
to null so as to release Bla objects:

      ...
      bla[j] = null;
      ...

I am not sure whether these releases work
the same in the bulk and the lazy version of
the code. Need to check first.

So measurements have already shown that the
release gives some gain, measurements where
16000 ms vs. 9600 ms. The release condition
is more complicated than the lazy new
condition, but the overhead is compensated
the overall gain.

Lets see.

Best Regards

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

#8298

On 9/25/2011 7:11 AM, Jan Burse wrote:
> Jan Burse schrieb:
>> Currently I am planning to change the loop
>> to something like that:
>>
>> Bla[] bla = new Bla[n];
>> for (int i=0; i<n; i++) {
>> bla[i] = createBla();
>> }
>>
>> So that the JIT has less information on what
>> the loop is about, and to do some new
>> measurements. To be fair I would also use
>> createBla() in the lazy scenario. Lets see
>> what happens.
>
> Maybe there is a bug somewhere else in the
> application that leads to the performance loss.
> There are also points in the application where
> some of the bla elements are forcefully set
> to null so as to release Bla objects:
>
> ...
> bla[j] = null;
> ...
>
> I am not sure whether these releases work
> the same in the bulk and the lazy version of
> the code. Need to check first.
>
> So measurements have already shown that the
> release gives some gain, measurements where
> 16000 ms vs. 9600 ms. The release condition
> is more complicated than the lazy new
> condition, but the overhead is compensated
> the overall gain.

I don't think lazy initialization is at all a good idea, even if it made
performance better rather than worse, if there is any condition under
which an array element transitions from non-null to null.

Even if you can prove that the current design never causes
re-initialization, it would be a fragile design under subsequent changes.

Patricia

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

#8295

On 9/25/2011 10:04 AM, Jan Burse wrote:
> Robert Klemme schrieb:
>> Yes, but the cost is not in the check but in the branching on processor
>> level (see what Patricia wrote).
>
> Depends on the processor and on the branch. If
> new is just heap -= size, what some papers suggest,
> then it might not be important.
>
> But if new is much more, then sure the branch
> interrupts the normal code flow so much that
> instruction piplining gets out of sync. And
> the speed gain by instruction overlapping
> is lost.
>
> But my hypothesis is more that something
> algorithmically on a higher level happens than
> something on the lower hardware level.
>
> So I also found something about "Lock
> coarsening"(*), so if the new needs some lock
> this lock could be aquired before the initialization
> loop and released after the initialization
> loop. [...]

     I'm speculating almost as wildly as you are, but I strongly
doubt that a lock is acquired.  Object creation happens so often
that I'm sure the JVM implementors will use something like compare-
and-swap on any platform that provides it (which I think means "all"
nowadays).

     Even the check for "Should I wait for the garbage collector to
finish?" uses no lock, on at least some platforms.  Their JVM's
dedicate an entire memory page to serve as a flag, whose state is
not recorded in its content but in its MMU protection bits.  To see
if it's safe to allocate, an allocating thread just stores something
in the special page; if the store works allocation is safe.  If GC
has raised its STOP sign, the page is write-protected and the store
generates a hardware trap -- very high overhead, to be sure, but
extremely low (not even a conditional branch!) in the common case.

> Would need n locking instruction pairs. But I
> would still need some confirmation that JITs
> are able to do such an optimization on a higher
> level in the present case.

     Again, I point out that the bulk and lazy variants do not do
the same thing.  Consider, for example

	class Bla {
	    private static int master_seqno = 0;
	    public final int seqno = ++master_seqno;
	}

Observe that the value of bla[42].seqno differs between the two
variants; it would therefore be an error to "optimize" either by
transforming it into the other.

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

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

#8296

Eric Sosman schrieb:
>      Again, I point out that the bulk and lazy variants do not do
> the same thing.  Consider, for example
>
>      class Bla {
>          private static int master_seqno = 0;
>          public final int seqno = ++master_seqno;
>      }
>
> Observe that the value of bla[42].seqno differs between the two
> variants; it would therefore be an error to "optimize" either by
> transforming it into the other.

Not really. You could only see a difference in the order
that Bla() gets a number. Since in the bulk variant
the Bla() will be allocated from 0 .. n-1, but the lazy
might allocate in an arbitrary order, which is the case
in my application.

So if your application does not depend on the order
the seqno's are created there is no functional problem.
Main question I have here is not about relative
correctness of bulk versus lazy. But why bulk is
counterintuitively much faster?

Since the bulk is much faster I am assuming some
optimization is happening in this particular loop:

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

Actually this loop is something that shocked me
when I started working with Java many years ago.
What there is no way to make a "new" of an array
with all its elements?

This is not seen if one works with int[] or
double[] arrays. But as soon as you work with some
other array, either a higher dimensional of int[]
or double[] or an array of some class X. You are
responsible for populating the elements.

The advantage is that you can create diagonal
matrices, sparse arrays, polymorphic data in
arrays, etc.. But I have the feeling that a loop
as above is happening in many many applications
exactly because initializing the elements of an
array is left to the application programmer.

So I am really focusing on this array init, and
asking what it does under the hood, and the lazy
is only a reference for the performance. I am
not interessted in a general theory between going
from bulk to lazy and back and forth. Forget
about the lazy and explain the bulk!

Bye

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

#8297

Jan Burse <janburse@fastmail.fm> wrote:
> Main question I have here is not about relative
> correctness of bulk versus lazy. But why bulk is
> counterintuitively much faster?
>
> Since the bulk is much faster I am assuming ...

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.

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

#8301

Jan Burse wrote:
> Actually this loop is something that shocked me
> when I started working with Java many years ago.
> What there is no way to make a "new" of an array
> with all its elements?
> 
> This is not seen if one works with int[] or
> double[] arrays. But as soon as you work with some
> other array, either a higher dimensional of int[]
> or double[] or an array of some class X. You are
> responsible for populating the elements.

This is equally true of primitive arrays.  Why do you claim otherwise?

The JLS, §15.10.1, states, "... if a single DimExpr appears, a single-dimensional array is created of the specified length, and each component of the array is initialized to its default value (§4.12.5)."  This is true whether the array is of a primitive or reference type.

In either case, you are responsible for populating any non-default values.

-- 
Lew

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

#8302

Lew schrieb:
> This is equally true of primitive arrays.  Why do you claim otherwise?

No, I don't claim otherwise. new int[] and new double[]
would also need treatment when the values 0 and 0.0
are not appropriate.

But you never run into a null-pointer exception with
primitive arrays, so they are a little bit more ready
made than non-primitive arrays.

Bye

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

#8303

Jan Burse schrieb:
> Lew schrieb:
>> This is equally true of primitive arrays. Why do you claim otherwise?
>
> No, I don't claim otherwise. new int[] and new double[]
> would also need treatment when the values 0 and 0.0
> are not appropriate.
>
> But you never run into a null-pointer exception with
> primitive arrays, so they are a little bit more ready
> made than non-primitive arrays.
>
> Bye

Just compare with C array allocation of a bunch of
fixed size records. In C you get the records. In Java
you only get the array but no records in it.

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

#8313

On 9/25/2011 11:14 AM, Jan Burse wrote:
> Eric Sosman schrieb:
>> Again, I point out that the bulk and lazy variants do not do
>> the same thing. Consider, for example
>>
>> class Bla {
>> private static int master_seqno = 0;
>> public final int seqno = ++master_seqno;
>> }
>>
>> Observe that the value of bla[42].seqno differs between the two
>> variants; it would therefore be an error to "optimize" either by
>> transforming it into the other.
>
> Not really. You could only see a difference in the order
> that Bla() gets a number.

     You'll also see a difference in *which* number bla[42] gets.
In the bulk initialization, bla[42].seqno is 43, always.  With
lazy initialization, it can be anything at all between 1 and n
inclusive.  QED, and your "not really" makes no sense to me.

     There are lots of other effects Bla() construction might have
that would turn out differently in bulk or lazy initialization.
If the constructor writes a message to System.out, all the messages
will appear together in bulk initialization, but will be scattered
all over the place with lazy initialization.  If the constructor
throws an exception -- even a seldom-caught RuntimeException --
the exceptions will appear in a different order w.r.t. other actions
in the program.  The two code sequences are irreconcilably different.

> So if your application does not depend on the order
> the seqno's are created there is no functional problem.

     From the application's point of view perhaps not.  But Java and
the JVM can't possibly know that; they follow the orders you give.
You say "Assign this seqno (not that one) to the new Bla, and throw
(or don't throw) this exception, write (or don't write) this output,
and do (or don't do) all these things in their proper order w.r.t.
all my other commands."  Concrete example: In a sense you do not
care what value Math.random() returns, but Java is contractually
bound to deliver a specific value under specific circumstances, and
cannot violate its contract even if you are in a forgiving mood.

> Main question I have here is not about relative
> correctness of bulk versus lazy. But why bulk is
> counterintuitively much faster?

     Nobody knows, because you've shown no code.  My first guess
(already hinted at) is that your timing is faulty; it is notoriously
hard to get good timings even from statically-bound languages these
days, and even more difficult with dynamically-bound partially-
interpreted-partially-compiled garbage-collected multi-threaded
languages like Java.  I'm sticking with that guess until you show
some evidence to refute it.

> Since the bulk is much faster I am assuming [...]

     Yeah.

> Actually this loop is something that shocked me
> when I started working with Java many years ago.
> What there is no way to make a "new" of an array
> with all its elements?

     That's another topic, and one that's been hashed over several
times in other threads.  The principal reason, I think, is that
it would so seldom be useful to create an array of N objects *all*
created by the no-args constructor: Who needs N copies of "the
same" thing?  And what if the class has no no-args constructor?

     Okay, sure, it could happen occasionally.  But often enough
to justify a special feature in the language, with special rules
for "What if I want to pass arguments to the constructors?" or
"What if the constructor is inaccessible and I'm supposed to use
a factory method?" and "What if I *don't* want objects created
yet?" and so on, and so on?

     Challenge: Look through your own code, right now, and count
the number of times you have actually filled an array with references
to N identically-constructed-with-no-args objects.  In other words,
count the number of times your own actual code would have been able
to take advantage of such a feature if Java provided it.

> This is not seen if one works with int[] or
> double[] arrays. But as soon as you work with some
> other array, either a higher dimensional of int[]
> or double[] or an array of some class X. You are
> responsible for populating the elements.

     How often do you create an int[] and leave all its elements
alone, still holding their original zeroes?  (On purpose, I mean.)

     In any case, Java *does* populate the array for you: With
null references.  Do you have a prejudice against `null'?

> I am
> not interessted in a general theory between going
> from bulk to lazy and back and forth. Forget
> about the lazy and explain the bulk!

     Exhibit some actual code, so people can stop guessing about
what you've done.

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

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

#8315

Eric Sosman schrieb:
> Challenge: Look through your own code, right now, and count
> the number of times you have actually filled an array with references
> to N identically-constructed-with-no-args objects.

 > Exhibit some actual code, so people can stop guessing about
 > what you've done.

I am not asking people to guess what I have done. I
am asking about whether JIT can optimize loops with
new in it. The new in it needs not to be a argument
less constructor. It could be also a constructor
with arguments.

All the optimizations that came to my mind easily
work also with argument based constructors. For
example moving the lock outside of the loop should
also work with argument based constructors in most
cases:

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

Is the same as:

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

If <init> of bla does not much. And the other optimization
with the memory allocate is also not impacted much by
argument based constructors. And it can be combined with
the heap locking, and we can move the lock before
the loop, and will lock less time:

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

Is the same as:

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

I hope you see now what I am heading for. But I must
disappoint you, if a compiler would be able to optimize
constructors with arguments, maybe not in all situations
but to a great degree, I will not have use for it in
my application, since my current problem is argument
less.

But I would be of course also happy to hear something
about the more general problem of constructors with
arguments and what the JIT would do for loops. Since
it would then be very easy for me to specialize the
insight to my argument less problem.

I do not exclude that JITs can also deal with
constructors that have arguments in loops.

Bye

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

#8278

On Sun, 25 Sep 2011 03:17:19 +0200, Jan Burse <janburse@fastmail.fm>
wrote, quoted or indirectly quoted someone who said :

>Any clues

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

A clever jit may notice that some objects are simple, and always
generate the exact same pattern.  It can then replace the constructor
code with a block move.

A clever jit may notice that some objects are simple, except for a few
computed bytes. It might be able to compose a fast constructor that
does a block move then call the methods to compute the few computed
bytes.

Moving 0 to a group of bytes is even faster than a block move, since
the source is a register or the instruction itself.

So another idea is the jit could reorder the fields so that the ones
needing the same initialisation byte pattern live side by side, so you
can do it with a REP constant move.

The flat footed way to do a constructor is to zap the entire block to
0, then go field by field initialised to non-null not-0 and plop that
value in on top.

Because constructors are called so often, even a very minor
optimisation would pay off.
-- 
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]

#8280

Roedy Green wrote:
> The flat footed way to do a constructor is to zap the entire block to
> 0, then go field by field initialised to non-null not-0 and plop that
> value in on top.

This "flat footed [sic] way" is what Java constructors do, and must.

Member fields are set to their default values prior to any constructor assignment, even to the same value as the default.

 public class Foo
 {
   private Bar bar = null;
 }

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.

> Because constructors are called so often, even a very minor
> optimisation would pay off.

Perhaps, depending on what you mean by "pay off".  Some have argued that the optimization achieved by omitting explicit initialization to default values is not worth the supposed reduction in clarity.

Since we all know that member fields are constructed with their default values, I don't think it's any less clear to omit their explicit (and redundant) initialization to default values.

I guess it depends on whether that's your opinion, and whether omitting the redundant initialization is an optimization that would pay off.

-- 
Lew

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web