Are array-based Tuples better than linked list-based Tuples?

ConsTuple-sample-output.txt

warmup
------
iteration
385.97869ms	100 size	1000000 iterations
4950000000
indexedAccess
7936.174072ms	100 size	1000000 iterations
4950000000

size=10, iterations=10000000
------------------------
iteration
491.335662ms	10 size	10000000 iterations
450000000
indexedAccess
829.517428ms	10 size	10000000 iterations
450000000

size=100, iterations=10000000
------------------------
iteration
2823.504679ms	100 size	10000000 iterations
49500000000
indexedAccess
78092.770659ms	100 size	10000000 iterations
49500000000

size=1000, iterations=1000000
------------------------
iteration
5339.326323ms	1000 size	1000000 iterations
499500000000
indexedAccess
******* termintated program because it was taking forever ********

ConsTuple.java

package ceylon.language;

import ceylon.language.impl.BaseSequence;

import com.redhat.ceylon.compiler.java.runtime.model.ReifiedType;
import com.redhat.ceylon.compiler.java.runtime.model.TypeDescriptor;

public class ConsTuple<Element, First extends Element, Rest extends Sequential<? extends Element>>
    extends BaseSequence<Element>
    implements Sequence<Element>, ReifiedType {

    private final First first;
    private final Rest rest;

    public ConsTuple(TypeDescriptor reifiedElement,
            TypeDescriptor reifiedFirst,
            TypeDescriptor reifiedRest,
            First first, Rest rest) {
        super(reifiedElement);
        this.first = first;
        this.rest = rest;
    }

    @Override
    public Element getFromFirst(long arg0) {
        if (arg0 == 0) {
            return getFirst();
        } else {
            arg0--;
            Sequential<? extends Element> r = rest;
            while (r instanceof ConsTuple && arg0 > 0) {
                r = ((ConsTuple)r).rest;
                arg0--;
            }
            return r.getFromFirst(arg0);
        }
        
    }

    @Override
    public Iterator<? extends Element> iterator() {
        return new Iterator<Element>() {

            Iterator i = null;
            ConsTuple t = ConsTuple.this;
            
            @Override
            public java.lang.Object next() {
                if (i != null) {
                    return i.next();
                } else {
                    java.lang.Object result = t.first;
                    if (t.rest instanceof ConsTuple) {
                        t = (ConsTuple)t.rest;
                    } else {
                        i = t.rest.iterator();
                        t = null;
                    }
                    return result;
                }
            }
            
        };
    }

    @Override
    public Element getFirst() {
        return first;
    }

    @Override
    public Element getLast() {
        if (rest.getEmpty()) {
            return getFirst();
        }
        Sequential<? extends Element> r = getRest();
        while (r instanceof ConsTuple) {
            r = ((ConsTuple)r).rest;
        }
        return r.getLast();
    }

    @Override
    public Sequential<? extends Element> getRest() {
        return rest;
    }

    @Override
    public long getSize() {
        long size = 1;
        Sequential<? extends Element> r = getRest();
        while (r instanceof ConsTuple) {
            size++;
            r = ((ConsTuple)r).rest;
        }
        return size + r.getSize();
    }
    
    // TODO getType() method without having to keep the reified shit around
    @Override
    public TypeDescriptor $getType$() {
        return null;//TypeDescriptor.klass(ConsTuple.class, reifiedElement);
    }
    
    public static void main(java.lang.String[] args) {
        //test();
        int size = 100;
        int iterations = 1_000_000;
        System.out.println("warmup");
        System.out.println("------");
        iteration(size, iterations);
        indexedAccess(size, iterations);
        
        size = 10; iterations=10_000_000;
        System.out.println();
        System.out.println("size="+size+", iterations="+iterations+"");
        System.out.println("------------------------");
        iteration(size, iterations);
        indexedAccess(size, iterations);
        
        size = 100; iterations=10_000_000;
        System.out.println();
        System.out.println("size="+size+", iterations="+iterations+"");
        System.out.println("------------------------");
        iteration(size, iterations);
        indexedAccess(size, iterations);
        
        size = 1000; iterations=1_000_000;
        System.out.println();
        System.out.println("size="+size+", iterations="+iterations+"");
        System.out.println("------------------------");
        iteration(size, iterations);
        indexedAccess(size, iterations);
    }

    private static void test() {
        TypeDescriptor itd = Integer.$TypeDescriptor$;
        ConsTuple zero = new ConsTuple(itd, itd, itd, Integer.instance(0), empty_.get_());
        ConsTuple one_zero = new ConsTuple(itd, itd, itd, Integer.instance(1), zero);
        ConsTuple ten_six = new ConsTuple(itd, itd, itd, Integer.instance(10), span_.span(itd, Integer.instance(9), Integer.instance(6)));
        System.out.println("getFromFirst()");
        System.out.println(zero.getFromFirst(0));
        System.out.println(zero.getFromFirst(1));
        System.out.println(one_zero.getFromFirst(0));
        System.out.println(one_zero.getFromFirst(1));
        System.out.println(one_zero.getFromFirst(2));
        System.out.println(ten_six.getFromFirst(0));
        System.out.println(ten_six.getFromFirst(1));
        System.out.println(ten_six.getFromFirst(2));
        System.out.println(ten_six.getFromFirst(3));
        System.out.println(ten_six.getFromFirst(4));
        System.out.println(ten_six.getFromFirst(5));
        
        System.out.println("iterator()");
        Iterator iterator = one_zero.iterator();
        System.out.println(iterator.next());
        System.out.println(iterator.next());
        System.out.println(iterator.next());
        
        iterator = ten_six.iterator();
        System.out.println(iterator.next());
        System.out.println(iterator.next());
        System.out.println(iterator.next());
        System.out.println(iterator.next());
        System.out.println(iterator.next());
        System.out.println(iterator.next());
        
        System.out.println("size()");
        System.out.println(zero.getSize());
        System.out.println(one_zero.getSize());
        System.out.println(ten_six.getSize());
    }
    /** sum a tuple containing 0..tupleSize-1, iterations times get accessing each element via the iterator() */
    private static void iteration(int tupleSize, int iterations) {
        TypeDescriptor itd = Integer.$TypeDescriptor$;
        Sequential<Integer> tail = (Sequential)empty_.get_();
        for (int ii = 0; ii < tupleSize; ii++) {
            tail = new ConsTuple(itd, itd, itd, Integer.instance(ii), tail);
        }
        //System.out.println(tail);
        System.out.println("iteration");
        long sum = 0;
        long t0 = System.nanoTime();
        for (int ii = 0; ii < iterations; ii++) {
            Iterator iter = tail.iterator();
            java.lang.Object o;
            while (!((o = iter.next()) instanceof Finished)) {
                sum += ((Integer)o).value;
            }
        }
        System.out.println((System.nanoTime()-t0)/1_000_000.0+"ms\t"+tupleSize+" size\t"+iterations+" iterations");
        System.out.println(sum);
    }
    /** sum a tuple containing 0..tupleSize-1, iterations times get accessing each element via getFromFirst*/
    private static void indexedAccess(int tupleSize, int iterations) {
        TypeDescriptor itd = Integer.$TypeDescriptor$;
        Sequential<Integer> tail = (Sequential)empty_.get_();
        for (int ii = 0; ii < tupleSize; ii++) {
            tail = new ConsTuple(itd, itd, itd, Integer.instance(ii), tail);
        }
        //System.out.println(tail);
        System.out.println("indexedAccess");
        long sum = 0;
        long t0 = System.nanoTime();
        for (int ii = 0; ii < iterations; ii++) {
            for (int jj = tupleSize-1; jj >= 0; jj--) {
                sum += tail.getFromFirst(jj).value;
            }
        }
        System.out.println((System.nanoTime()-t0)/1_000_000.0+"ms\t"+tupleSize+" size\t"+iterations+" iterations");
        System.out.println(sum);
    }
}

small-tuples.txt

array-based

size=3, iterations=10000000
------------------------
iteration
122.126328ms	3 size	10000000 iterations
60000006
indexedAccess
192.555048ms	3 size	10000000 iterations
60000006


linked-list

size=3, iterations=10000000
------------------------
iteration
221.910546ms	3 size	10000000 iterations
30000000
indexedAccess
120.997621ms	3 size	10000000 iterations
30000000

TupleBench-sample-output.txt

warmup
------
iteration
132.065592ms	100 size	1000000 iterations
5050005050
indexedAccess
451.457805ms	100 size	1000000 iterations
5050005050

size=10, iterations=10000000
------------------------
iteration
242.990074ms	10 size	10000000 iterations
550000055
indexedAccess
517.626582ms	10 size	10000000 iterations
550000055

size=100, iterations=10000000
------------------------
iteration
1947.83587ms	100 size	10000000 iterations
50500005050
indexedAccess
3919.124024ms	100 size	10000000 iterations
50500005050

size=1000, iterations=1000000
------------------------
iteration
2842.928396ms	1000 size	1000000 iterations
500500500500
indexedAccess
4644.400989ms	1000 size	1000000 iterations
500500500500

TupleBench.ceylon

"sum a tuple containing 0..tupleSize-1, iterations times get accessing each element via the iterator()."
void iteration(Integer tupleSize, Integer iterations) {
    
    variable Integer[] tail = empty;
    for (ii in 0..tupleSize) {
        tail = Tuple(ii, tail);
    }
    //print(tail);
    print("iteration");
    variable Integer sum = 0;
    Integer t0 = system.nanoseconds;
    for (ii in 0..iterations) {
        for (o in tail) {
            sum += o;
        }
    }
    print("``(system.nanoseconds-t0)/1_000_000.0``ms\t``tupleSize`` size\t``iterations`` iterations");
    print(sum);
}
"sum a tuple containing 0..tupleSize-1, iterations times get accessing each element via getFromFirst"
void indexedAccess(Integer tupleSize, Integer iterations) {
    variable Integer[] tail = empty;
    for (ii in 0..tupleSize) {
        tail = Tuple(ii, tail);
    }
    //print(tail);
    print("indexedAccess");
    variable Integer sum = 0;
    variable Integer t0 = system.nanoseconds;
    for (ii in 0..iterations) {
        for (jj in (tupleSize-1)..0) {
            sum += tail.getFromFirst(jj) else 0;
        }
    }
    print("``(system.nanoseconds-t0)/1_000_000.0``ms\t``tupleSize`` size\t``iterations`` iterations");
    print(sum);
}
void run() {
    variable value size = 100;
    variable value iterations = 1M;
    print("warmup
           ------");
    iteration(size, iterations);
    indexedAccess(size, iterations);
    
    size = 10; iterations = 10M;
    print("
           size=``size``, iterations=``iterations``
           ------------------------");
    iteration(size, iterations);
    indexedAccess(size, iterations);
    
    size = 100; iterations = 10M;
    print("
           size=``size``, iterations=``iterations``
           ------------------------");
    iteration(size, iterations);
    indexedAccess(size, iterations);
    
    size = 1000; iterations = 1M;
    print("
           size=``size``, iterations=``iterations``
           ------------------------");
    iteration(size, iterations);
    indexedAccess(size, iterations);
}