List vs. LinkedList

[Max Berger <ma...@berger.name>]

Dear Fop-Devs,

as far as I can tell, there where two issues with my cleanups  
yesterday: Readablility and Performance.

I've just submitted a patch which adds a "ListUtil" class, to make the  
code more readable again. I've replaced (hopefully) all occurrences of  
size() - 1 with the call to these utils. Since they are static the  
hotspot engine will pick them up and inline them very nicely, so there  
should be no performance overhead.

I hope this addresses the readability issue.

Performance  of list.get(list.size()-1). In the default implementation  
of LinkedList ( sun jdk), there is no performance penalty for this  
call. The list is linked from both ends, and all calls to an element >  
size()/2 are searched from the back. There is a small overhead, since  
we now have two virtual method calls instead of one, again something  
that hotspot can iron out very nicely.

Also: Calls to interface methods are not slower than calls to the  
class directly: In both cases the virtual method table is consulted,  
as class methods are overridable. The only exception is if the class  
method or the class is declared final: Then the compiler may optimize  
the calls.

I've also noted:

There are a lot of list.size() > 0 calls. I've replaced the ones in  
the touched files with .isEmpty(), which is more performant.

Max

Re: List vs. LinkedList

[Andreas Delmelle <an...@telenet.be>]

On Jun 10, 2008, at 09:54, Max Berger wrote:

> as far as I can tell, there where two issues with my cleanups  
> yesterday: Readablility and Performance.
>
> I've just submitted a patch which adds a "ListUtil" class, to make  
> the code more readable again. I've replaced (hopefully) all  
> occurrences of size() - 1 with the call to these utils. Since they  
> are static the hotspot engine will pick them up and inline them  
> very nicely, so there should be no performance overhead.
>
> I hope this addresses the readability issue.
>
> Performance  of list.get(list.size()-1). In the default  
> implementation of LinkedList ( sun jdk), there is no performance  
> penalty for this call. The list is linked from both ends, and all  
> calls to an element > size()/2 are searched from the back. There is  
> a small overhead, since we now have two virtual method calls  
> instead of one, again something that hotspot can iron out very nicely.
>
> Also: Calls to interface methods are not slower than calls to the  
> class directly: In both cases the virtual method table is  
> consulted, as class methods are overridable. The only exception is  
> if the class method or the class is declared final: Then the  
> compiler may optimize the calls.

OK, that takes care of that. Seems I'm still stuck with some ideas on  
pre-HotSpot VMs... Thanks for investigating this!

> I've also noted:
>
> There are a lot of list.size() > 0 calls. I've replaced the ones in  
> the touched files with .isEmpty(), which is more performant.

That's one I usually replace myself too, if I encounter it.  
Definitely no argument from me there.


Cheers

Andreas