generator expressions: performance anomaly?

[bearophileHUGS at lycos.com]

Nick Coghlan:
>There's a similar performance glitch associated with constructing a
tuple from a generator expression (with vanilla 2.4, detouring via list
is actually faster)

You look right:

.from time import clock
.print "[x for x in l], list(x for x in l), aux = list(x for x in l);
tuple(aux), tuple(x for x in l):"
.for np in range(13, 21):
.    n = 1*2**np
.    print "n:", n, " s:",
.    l = xrange(n)
.    t1 = clock()
.    [x for x in l]
.    t2 = clock()
.    print round(t2-t1,3),
.
.    t1 = clock()
.    list(x for x in l)
.    t2 = clock()
.    print round(t2-t1,3),
.
.    t1 = clock()
.    aux = list(x for x in l)
.    tuple(aux)
.    t2 = clock()
.    print round(t2-t1,3),
.
.    #l = tuple(l) useless
.    t1 = clock()
.    tuple(x for x in l)
.    t2 = clock()
.    print round(t2-t1,3)


Output:
[x for x in l], list(x for x in l), aux = list(x for x in l);
tuple(aux), tuple(x for x in l):
n: 8192  s: 0.01 0.007 0.01 0.013
n: 16384  s: 0.024 0.019 0.021 0.032
n: 32768  s: 0.054 0.042 0.049 0.113
n: 65536  s: 0.111 0.078 0.101 0.088
n: 131072  s: 0.196 0.155 0.183 0.177
n: 262144  s: 0.436 0.385 0.429 1.832
n: 524288  s: 0.921 0.744 0.877 8.271
n: 1048576  s: 1.86 1.546 1.866 33.154

The timings for tuple(x for x in l) seem to grow as len(n)**2.
Bear hugs,
Bearophile