Skip to main content

Performance improvements in core classes

3 replies [Last post]
swpalmer
Offline
Joined: 2003-06-10
Points: 0

In a recent thread on that Mac java-dev list I learned that some very basic operations such as ArrayList get() set(), add() cannot be inlined with the current HotSpot compiler because of the way in which they handle bounds checks.

Sean Luke wrote there:
I think we are far too reliant on the assumption that Sun's got such good classes that we don't need to bother writing our own at the outset.

Case in point: ArrayList. Imagine if you had public access to ArrayList's internal array, called say objs, and an integer saying how many objects are presently in the array, called numObjs. So which do you think is faster:

<br />
if (x >= numObjs) throw new IndexOutOfBoundsException("You Dolt!");<br />
list.objs[x] = "Yo";<br />

or
<br />
list.set(x,"Yo");<br />

Let's presume the method looks like this internally:
<br />
public void set(int x, Object obj)<br />
	{<br />
	if (x >= numObjs) throw new IndexOutOfBoundsException("You Dolt!");<br />
	list.objs[x] = obj;<br />
	}<br />

Well, you might surmise, set is gonna get inlined, so just call set. Think again. The bounds check makes set uninlinable. The second example is 3-4 times slower than the top example. Better than Vector's version of course, which is 5 times slower due to the synchronization overhead. But holy cow, 3-4 times slower.

Not so fast, you say, that's not what Sun actually wrote. They wrote something along these lines:

<br />
void doBoundsCheck(x)<br />
	{<br />
	if (x >= numObjs) throw new IndexOutOfBoundsException("You Dolt!");<br />
	}</p>
<p>public void set(int x, Object obj)<br />
	{<br />
	doBoundsCheck(x);<br />
	list.objs[x] = obj;<br />
	}<br />

So by moving the exception out, now set can be inlined. Clever, no? No. Not clever. Set still has to call doBoundsCheck, which doesn't get inlined. So we're inlining part of the method, but we still have an entire function call overhead, which is no difference at all. Still 3-4 times slower. This is what Sun actually has in their code right now, believe it or not. It's STILL in Java 1.5. ArrayList!

...
A fixed version looks thusly:

<br />
void throwException()<br />
	{<br />
	throw new IndexOutOfBoundsException("You Dolt!");<br />
	}</p>
<p>public void set(int x, Object obj)<br />
	{<br />
	if (x >= numObjs) throwException();<br />
	list.objs[x] = obj;<br />
	}<br />

... but in fact, this version STILL is slower than raw code by a little bit, even if the exception case never occurs. Why? I don't know. There appears to be some overhead in inlining.

----------

It seems that some very simple changes can be made to get significant gains in some very fundamental classes. Let's not drag these into Mustang if it can be avoided.

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
timbell
Offline
Joined: 2003-06-10
Points: 0

See also:

Bug Id: 5103956
Synopsis: (coll) Suggested improvement to speed up ArrayList get and set calls

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=5103956

Alternatives to consider:

1) Use the "-server" runtime compiler instead of "-client". The Server compiler will inline get(), set(), and others. If you have a debug VM (libjvm_g.so), you can confirm this via:
-XX:+PrintCompilation -XX:+PrintInlining

2) Increase the maximum size used by the runtime compiler when considering when to inline. EG: add "-XX:MaxInlineSize=128" to the command line.

(Standard disclaimer on -XX flag usage; many other methods will be inlined, which would bear additional investigation...)

kcpeppe
Offline
Joined: 2003-06-15
Points: 0

> Alternatives to consider:
>
> 1) Use the "-server" runtime compiler instead of
> "-client". The Server compiler will inline get(),
> set(), and others. If you have a debug VM
> (libjvm_g.so), you can confirm this via:
> -XX:+PrintCompilation -XX:+PrintInlining
>
> 2) Increase the maximum size used by the runtime
> compiler when considering when to inline. EG: add
> "-XX:MaxInlineSize=128" to the command line.
>
> (Standard disclaimer on -XX flag usage; many other
> her methods will be inlined, which would bear
> additional investigation...)

As developers, we don't always that an option to set these. These are options that should only be applied during the technical tuning phase (ie after deployment).

tsinger
Offline
Joined: 2003-06-10
Points: 0

Although I haven't used assertions yet, but since they can be deactivated, maybe they can be inlined?

[code]assert x < numObjs;
list.obj[x] = "Yo";[/code]

Tom

PS: I don't care the slower speed, just wanted to show a [i]possible[/i] alternative.