LinkedList facelift

[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