LinkedList facelift

[Martin Buchholz-3]

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

[Martin Buchholz-3]

On Mon, Nov 2, 2009 at 18:29, Martin Buchholz <martinrb@...> wrote:
> I would like to contribute an improvement to LinkedList
>
> Below is a stupid microbenchmark demonstrating app. a factor of 2 improvement in
> "throughput", and a 50% increase in memory footprint.

Of course, I meant "a 50% improvement in memory footprint".

Martin

[Remi Forax]

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

[Christopher Hegarty -Sun Microsystems Ireland]

Martin Buchholz wrote:

> 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?

Happy to do so.

CR 6897553: LinkedList facelift

-Chris.

>
> 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

[Martin Buchholz-3]

On Tue, Nov 3, 2009 at 01:06, Rémi Forax <forax@...> wrote:

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, thanks for the review.  I've added you as a reviewer.

I agree.  Although relying on such implementation details is a bad idea,
and implementations are very likely to differ, and the existing LinkedList
is a hodge-podge of differing styles of methods calling other public
methods, we should strive to maintain this kind of compatibility if
the price is not too high.

Also, I did some cosmetic touchups, and commented out the asserts.

Webrev regenerated.

Martin
 

[Remi Forax]

Le 03/11/2009 20:32, Martin Buchholz a écrit :

On Tue, Nov 3, 2009 at 01:06, Rémi Forax <forax@...> wrote:

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, thanks for the review.  I've added you as a reviewer.

I agree.  Although relying on such implementation details is a bad idea,
and implementations are very likely to differ, and the existing LinkedList
is a hodge-podge of differing styles of methods calling other public
methods, we should strive to maintain this kind of compatibility if
the price is not too high.

Also, I did some cosmetic touchups, and commented out the asserts.

Webrev regenerated.

Martin
 

Good for me if addFirst() calls linkFirst() and
addLast() calls linkLast().

Rémi

[Martin Buchholz-3]

On Wed, Nov 4, 2009 at 06:18, Rémi Forax <forax@...> wrote:

Good for me if addFirst() calls linkFirst() and
addLast() calls linkLast().

Sigh.  Of course, that's what I intended to do.  Done.

Also, renamed addBefore to linkBefore and moved
near to the other linkXXX methods.

Webrev regenerated.

Thanks again for the careful review.
 

Rémi

[Remi Forax]

Le 04/11/2009 19:25, Martin Buchholz a écrit :

On Wed, Nov 4, 2009 at 06:18, Rémi Forax <forax@...> wrote:

Good for me if addFirst() calls linkFirst() and
addLast() calls linkLast().

Sigh.  Of course, that's what I intended to do.  Done.

Also, renamed addBefore to linkBefore and moved
near to the other linkXXX methods.

Webrev regenerated.

Thanks again for the careful review.
 

Rémi

Ok, looks fine.

Rémi