How do you cast to array?

C

Chris Uppal

NOBODY said:
(I cannot believe the % of coders forgetting that 'new' is expensive...)

The question is: /how/ expensive ?

Go on, take a guess. How many milliseconds ? Or is it measured in
microseconds ? Or even nanoseconds ? Take a guess, before you read on...

Here's some test code:

====================
public class Main
implements Runnable
{
private final int m_steps;

public static void
main(String[] args)
{
new Thread(new Main(100)).run();
}

Main(int steps)
{
m_steps = steps;
}

public void
run()
{
for (;;)
{
tick();
tock();
}
}

void
tick()
{
int steps = m_steps * 1000000;
int[] array = new int[0];
int totalSize = 0;

long start = System.currentTimeMillis();
for (int i = 0; i < steps; i++)
{
totalSize += array.length;
array = new int[0];
}
long end = System.currentTimeMillis();
double secs = (end - start) / 1000.0;

System.out.print(m_steps + "M arrays allocated in " + secs + " seconds");
System.out.println(", total size: " + totalSize);
}

void
tock()
{
int steps = m_steps * 1000000;
int[] array = new int[0];
int totalSize = 0;

long start = System.currentTimeMillis();
for (int i = 0; i < steps; i++)
totalSize += array.length;
long end = System.currentTimeMillis();
double secs = (end - start) / 1000.0;

System.out.print("zero arrays allocated in " + secs + " seconds");
System.out.println(", total size: " + totalSize);
}
}
====================

On my machine, a 1.5Gz laptop, it sits in a steady loop allocating 0-length
arrays at a rate of around 40M per second (about 25 nanoseconds a go). The
reported times scale with both 'm_steps' and the size of the allocated arrays
so I don't think the allocations are being optimised away. (I did try
with -server too, and that's marginally quicker as you'd expect, and that
/does/ optimise the empty comparison loop (tock()) out completely, but not the
allocations afaict.)

There are contexts where allocation is slower than that -- not everyone is
running code on desktop class or more machines. Also there are contexts where
25 nanosecs is a long time -- though I doubt if many people reading this are
working in such a context. So, while I don't entirely disagree with you that
"'new' is expensive", I think that a better way to express it (for general
purposes) is that 'new' is /cheap/.

-- chris
 
N

NOBODY

(I cannot believe the % of coders forgetting that 'new' is
And I cannot believe the number of people still believing this. It's a
thing of the past. Nowadays, object creation is highly optimized and
very fast in most cases.

I won't argue on low throughput system.
But on high throughput system (thousands/millions of processes per
seconds), sorry to be pedantic but you can't afford, for example:

-to trash memory with Long or Integer wrappers as keys to maps instead of
using intkeyhashmaps or longkeyhashmaps

-to create new stringbuffers everytime to return a string instead of
threadlocal-caching them.

-to keep using iterators even on an arraylist (iterator trashing)

-to not get that not using 'new' (and the GC that goes with it) is largely
faster (can't say infinity 'cause of object pool access time) than any
performance of any 'new' ever coded.

-to not get that realtime systems programming is not a matter of 'user
perception in seconds' and that every nanoseconds counts for good
throughput.


For a given code, when ALL known profilers point to some constant hotspot
(let's the constructor <init> of some object) and when you remove it by
using a pool and your throughput goes one or more magnitude faster, you
realize that 'new' IS expensive.

As long as you think in seconds, milliseconds, microseconds,
whateverseconds, in absolute time, and ignore the 'relative' performance
comparison, you can't realize that 'new' IS expensive.
 
N

NOBODY

The question is: /how/ expensive ?
Go on, take a guess. How many milliseconds ? Or is it measured in
microseconds ? Or even nanoseconds ? Take a guess, before you read
on... [...]
I don't entirely disagree with you that "'new' is expensive", I think
that a better way to express it (for general purposes) is that 'new'
is /cheap/.

The use of antonyms doesn't make it better: 'new' isn't cheap.

Your test:
100M arrays allocated in 3.515 seconds, total size: 0
zero arrays allocated in 0.204 seconds, total size: 0

You just prooved my point, one loop is 15 times faster than the other.
Hang on, see where I'm going now?

If you had another way to get an array to work with, other than a 'new'
one, the loop would be faster as long as your cache lookup isn't slow.

Allright. You want a test?
Go ahead: and fill and empty an hashmap with 'new' Integer keys from 1 to
1000 many times.
Canonicalize your integers and you get ~30% throughput increase.


(line #1 is the import)
-----------------------------------
import java.util.HashMap;

public class TestNewCost {

static final Integer[] INTEGERCACHE = new Integer[1000];
static {
for (int i = 0; i < 1000; i++) {
INTEGERCACHE = new Integer(i);
}
}

private static final double mem() {
Runtime r = Runtime.getRuntime();
return 0.000001* (r.totalMemory() - r.freeMemory());
}

static void relax() throws Exception {
System.out.println("relaxing...");
System.gc(); System.out.println(mem());
System.gc(); System.out.println(mem());
Thread.sleep(4000); //relax time
System.gc(); System.out.println(mem());
System.out.println("relaxing done.");
}

public static void main(String[] args) throws Exception {
relax();
int n = 30000;
TestNewCost t = new TestNewCost();

System.out.println("!");
t.test1(n);
t.test2(n);

System.out.println("!");
t.test1(n);
t.test2(n);

relax();
System.out.println("!");
t.test1(n);
t.test2(n);
}

//---------------------------------

HashMap map = new HashMap();


void test1(int n) {
map.clear();
long t, d;
Integer x;
t = System.currentTimeMillis();

for(int i=0; i<n; i++) {
for(int j=0; j<1000; j++) {
x = new Integer(j);
map.put(x, null);
}
for(int j=0; j<1000; j++) {
x = new Integer(j);
map.remove(x);
}
}
d = System.currentTimeMillis() - t;
System.out.println("test1: "+d+" ms, avg = "+(1000.0*d/n/2000)+" us");
}

void test2(int n) {
map.clear();
long t, d;
Integer x;
t = System.currentTimeMillis();
for(int i=0; i<n; i++) {
for(int j=0; j<1000; j++) {
x = INTEGERCACHE[j];
map.put(x, null);
}
for(int j=0; j<1000; j++) {
x = INTEGERCACHE[j];
map.remove(x);
}
}
d = System.currentTimeMillis() - t;
System.out.println("test2: "+d+" ms, avg = "+(1000.0*d/n/2000)+" us");
}
}
-----------------------------------------

(sampling mode profile, 1ms, last 2 tests only (after warmup))


Description of CPU usage for thread main
57.68% - 8437.0 ms - TestNewCost.main() (TestNewCost.java:41)
28.75% - 4206.0 ms - TestNewCost.test1() (TestNewCost.java:59)
16.23% - 2374.0 ms - TestNewCost.test1() (TestNewCost.java:63)
6.49% - 950.0 ms - TestNewCost.test1() (TestNewCost.java:62)
3.73% - 546.0 ms - TestNewCost.test1() (TestNewCost.java:58)
1.29% - 189.0 ms - TestNewCost.test1() (TestNewCost.java:57)
1.17% - 172.0 ms - TestNewCost.test1() (TestNewCost.java:61)
41.98% - 6141.0 ms - TestNewCost.main() (TestNewCost.java:42)
21.89% - 3202.0 ms - TestNewCost.test2() (TestNewCost.java:78)
16.12% - 2359.0 ms - TestNewCost.test2() (TestNewCost.java:82)
1.51% - 221.0 ms - TestNewCost.test2() (TestNewCost.java:80)
0.86% - 126.0 ms - TestNewCost.test2() (TestNewCost.java:76)
0.84% - 124.0 ms - TestNewCost.test2() (TestNewCost.java:77)
0.74% - 109.0 ms - TestNewCost.test2() (TestNewCost.java:81)
0.32% - 48.0 ms - TestNewCost.main() (TestNewCost.java:39)
0.21% - 32.0 ms - TestNewCost.relax() (TestNewCost.java:21)
0.1% - 16.0 ms - TestNewCost.relax() (TestNewCost.java:22)


Hot spots
---------

Name Percentage Time
--------------------------------------- ---------- ---------
TestNewCost.test1 (TestNewCost.java:59) 28.75 4206.0 ms
TestNewCost.test2 (TestNewCost.java:78) 21.89 3202.0 ms
TestNewCost.test1 (TestNewCost.java:63) 16.23 2374.0 ms
TestNewCost.test2 (TestNewCost.java:82) 16.12 2359.0 ms
TestNewCost.test1 (TestNewCost.java:62) 6.49 950.0 ms
TestNewCost.test1 (TestNewCost.java:58) 3.73 546.0 ms
TestNewCost.test2 (TestNewCost.java:80) 1.51 221.0 ms
TestNewCost.test1 (TestNewCost.java:57) 1.29 189.0 ms
TestNewCost.test1 (TestNewCost.java:61) 1.17 172.0 ms
TestNewCost.test2 (TestNewCost.java:76) 0.86 126.0 ms
TestNewCost.test2 (TestNewCost.java:77) 0.84 124.0 ms
TestNewCost.test2 (TestNewCost.java:81) 0.74 109.0 ms
TestNewCost.relax (TestNewCost.java:21) 0.21 32.0 ms
TestNewCost.relax (TestNewCost.java:22) 0.1 16.0 ms
 
C

Chris Uppal

NOBODY said:
You just prooved my point, one loop is 15 times faster than the other.
Hang on, see where I'm going now?

No, I don't. The important thing is not the relative speed of the loops. In
fact I was /trying/ to make the relative difference as high as I could
(infinite would be ideal), but there's a limit to how "empty" you can make the
empty comparison loop before the optimiser notices and removes it altogether.

The point is that -- in this specific case -- the sustained /absolute/ cost of
creating a 0-sized array was around 25 nanoseconds. Imagine that we are in the
context of some application which allocates arrays, and we are considering
whether we can optimise that. Assume that we hope to remove 25% of execution
time (which is not an unreasonable goal, though the specific figures are
obviously choosen for easy arithmetic). If we could get that by eliminating an
array creation from the inner loop, then the /rest/ of the inner loop must be
taking 75 nanoseconds. That isn't a lot of time, especially since the inner
loop must presumably do /something/ with the array, so the inner loop must be
pretty tight. I'm finding it hard to imagine a realistic scenario where
someone would allocate an unecessary array right in the middle of a
performance-critical tight loop.

Well, OK, I guess there /are/ programmers who would do that[*]. But even in
such cases the main problem would not be that "creating an object is
expensive", but simply that they were doing any unecessary work /at all/ in
such a context. Even if creating the object were free, there's still be the
unecessary assignment to a temporary variable.

([*] after all, if there are programmers who don't see anything wrong with
storing several million java.lang.Floats in an ArrayList.....)

In more realistic circumstances -- where an application actually /does/
something with its objects rather than just creating them all the time -- then
I can't see that the cost of creating objects (per se) can be called anything
other than trivial. Especially when you consider that neither object pooling
nor thread-local storage are free either (and the effect of unecessarily
long-lived objects on the GC is hard to anticipate). OTOH, "real" objects do
certainly cost more to create than 0-length arrays ;-) But still, if you are
going to think about performance at all (sometimes you have to, sometimes you
don't) then I'd say it's pointless to try to do it without a sense of what the
costs actaully /are/. In the case of object creation, unless your application
is creating (at least) millions of object per second when it's running
flat-out, object creation is simply not an issue (to the extent that my test is
representative, anyway).

-- chris
 
N

NOBODY

Boiled down, you finally make sense.
Thanks for the exhaustive explaination.

But whatever words I use, if avoiding 'new' give me a magnitude of
throughput increase, I won't forget the trick soon.

([*] after all, if there are programmers who don't see anything wrong
with storing several million java.lang.Floats in an ArrayList.....)

Can you imagine the upcoming nightmare with 1.5 autoboxing?!
This is the worst feature of 1.5. It is a serious mistake from a language
perspective. There is a limit to laziness in order to be a good programmer.

Juniors are gonna start using autoboxing like they know nothing better.
Same for the new 'for' loop, trashing iterators.

Damn it, we will have to develop another language again...
;)
 
M

Michael Borgwardt

NOBODY said:
But whatever words I use, if avoiding 'new' give me a magnitude of
throughput increase, I won't forget the trick soon.

It may have given you that increase in *one particular program*.
It's still a really bad idea to start prematurely optimizing it
everywhere.

There are certainly a lot of operations that are quicker than a 'new',
but far, far more that are orders of magnitude slower. It's just not
very likely that 'new' really turns out to be what slows down a program.

That's what profilers are for.
Can you imagine the upcoming nightmare with 1.5 autoboxing?!
This is the worst feature of 1.5. It is a serious mistake from a language
perspective.

I don't think so at all.
There is a limit to laziness in order to be a good programmer.
Juniors are gonna start using autoboxing like they know nothing better.

And most of the time it will be not problem at all, see above.

Same for the new 'for' loop, trashing iterators.

I really, *really* don't see how this could *ever* turn into a problem.
What circumstances do you imagine where the for(type object:iterable)
loop would now be used where what would have been used before
(*is* there anything beside while(iterator.hasNext())??) was in any
way faster?
 
C

Chris Uppal

NOBODY said:
But whatever words I use, if avoiding 'new' give me a magnitude of
throughput increase, I won't forget the trick soon.

You would be insane to do so. Never forget a trick that worked; but I would
warn against learning too much from such occasions.

There's a phrase from a book by R A Lafferty that I treasure:
"we must be careful not to learn too much from our mistakes"

Can you imagine the upcoming nightmare with 1.5 autoboxing?!
This is the worst feature of 1.5. It is a serious mistake from a language
perspective.

I agree that there is considerable scope for unwitting abuse. I'm not sure I'd
call it the /worst/ feature, though -- for instance it could be seem as no more
than a symptom of the underlying weakness in generics that they can't handle
primitive types.

Juniors are gonna start using autoboxing like they know nothing better.

Damn it, we will have to develop another language again...
;)

<nods sadly>

[...insert obligatory reference to Smalltalk here...]

-- chris
 
N

Neal Gafter

I really, *really* don't see how this could *ever* turn into a
problem.
What circumstances do you imagine where the for(type object:iterable)
loop would now be used where what would have been used before
(*is* there anything beside while(iterator.hasNext())??) was in any
way faster?

Iterating through a random access java.util.List using get(int) is
usually faster than using the iterator.
 
G

Gerbrand van Dieijen

Neal Gafter schreef:
Iterating through a random access java.util.List using get(int) is
usually faster than using the iterator.

Have you checked this? I really doubt this is true.
An iterator doesn't need to no it's current position, only the 'next'
element so it might as well be faster.

Anyway, an iterator is better because because it's much more readable.
 
M

Michael Borgwardt

Neal said:
Iterating through a random access java.util.List using get(int) is
usually faster than using the iterator.

But doesn't the new for loop just use the iterator anyway? It's based
on the Iterable interface, which returns an Iterator.
 
M

Michael Borgwardt

Gerbrand said:
Have you checked this? I really doubt this is true.

Look at the sourcecode of the iterator returned by AbstractList (which is
used unchanged by ArrayList). On top of returning the element (with an
additional method call) and incrementing the index, it checks for concurrent
modification (method call and integer comparison).

Not a big overhead, but it exists.
 
G

Gerbrand van Dieijen

Michael Borgwardt schreef:
Look at the sourcecode of the iterator returned by AbstractList (which is
used unchanged by ArrayList). On top of returning the element (with an
additional method call) and incrementing the index, it checks for
concurrent
modification (method call and integer comparison).

Not a big overhead, but it exists.

Yes, but that's a good thing and only a minor overhead. The 'overhead'
of having a bug when you would accidently modify it while using the loop
could bu much high.

Java is full of such checks. For example, when you lookup an array
element (myarray[index]), java will check if the array is initialized,
and if index isn't greater than the length of the array.

If you really want a faster iterator, you can just implement you're own
iterator and arraylist. Even better, you can code in C and later
optimize by hand the assembler code the compiler produces.

However, you should *never* in advance use constructs like get(i) just
because you thing it's more efficient because you looked in the source
code. This is a wrong approach which will quickly lead to inefficient -
or even worse, buggy- programs.
 
N

Neal Gafter

Yes, I checked this when I implemened the new foreach loop. We had
a debate as to whether we should do anything about it. We decided not
to,
but you can often recover the performance, and more, by doing
List.toArray
before iterating.
 
G

Gerbrand van Dieijen

Neal Gafter schreef:
Yes, I checked this when I implemened the new foreach loop. We had
a debate as to whether we should do anything about it. We decided not
to,
but you can often recover the performance, and more, by doing
List.toArray
before iterating.

List.toArray costs time to run to. When you add these to up (converting
to array and then running to a fixed-size array), you probably get the
same run-time or even a bigger one.

If you now in advance, your list isn't dynamic you could use an
fixed-size array:
in stead of
Object [] myobjects=new Object[length]

I can very well imagine that's faster than the the dynamic list.
 
N

Neal Gafter

List.toArray costs time to run to. When you add these to
up (converting
to array and then running to a fixed-size array), you
probably get the
same run-time or even a bigger one.

The way we measured the performance was by statically
allocating an array of the correct dynamic type and of
length 0:
Object[] zeroLengthArray = new Object[0];
and then using toArray like this
for (Object x : list.toArray(zeroLengthArray)) ...

Our measurements showed a significant performance
boost for all the cases we tried. However, unless this
is in the critical path of your program it's not worth
doing.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
474,432
Messages
2,571,682
Members
48,796
Latest member
Greg L.

Latest Threads

Top