LinkedList facelift
Rémi Forax
forax at univ-mlv.fr
Tue Nov 3 09:06:53 UTC 2009
Le 03/11/2009 03:29, Martin Buchholz a écrit :
> I would like to contribute an improvement to LinkedList
>
> webrev:
> http://cr.openjdk.java.net/~martin/webrevs/openjdk7/LinkedList/
>
> Josh, Bill and I have discussed this offline,
> and they have given their blessing.
> (i.e. I am not asking for reviewers)
>
> I apologize for this - there are so many more important things to work on,
> and no one is really using LinkedList
> in performance-sensitive production code, eh?
>
> Chris, could you file a bug?
>
> Synopsis: LinkedList facelift
>
> Description:
> - A list of size N should create only N+1 objects, not N+2.
> - Use of null as sentinel value instead of a sentinel (Null Object)
> is slightly less convenient, but is measurably faster, since hotspot
> has to insert null checks (with NPE throws) anyways.
> - generify
> - warning removal
> - gratuitous tests added.
> - cosmetic doc improvements
> - the original motivation for this was to have a O(1) clear,
> but we eventually decided against that
> - but we documented our decision.
>
> Below is a stupid microbenchmark demonstrating app. a factor of 2 improvement in
> "throughput", and a 50% increase in memory footprint.
>
> public class LinkedListBench {
> public static void main(String[] args) {
> LinkedList spine = new LinkedList();
> long i = 0;
> long t0 = System.nanoTime();
> try {
> for (i = 0; ; i++) {
> spine.add(new LinkedList());
> }
> } catch (OutOfMemoryError e) {
> spine.clear();
> System.out.printf("allocated = %d%n", i);
> System.out.printf("ns/object = %d%n", (System.nanoTime()-t0)/i);
> }
> }
> }
>
>
> Thanks,
>
> Martin
>
Hi Martin,
Your patch can break backward compat.
add(E) now delegates to a public method (an overridable one)
(addLast). So If I have a class that inherits from LinkedList
and overrides addLast() the current semantics of add(E) is not altered,
with your patch, add(E) semantics is also changed.
I think the code of addLast() should be in a private method and
addLast() and add(E) delegate to it.
Rémi
More information about the core-libs-dev
mailing list