iteration over open type arguments is superlinear

[maxteufel]

$ fz -c -e "say ($(seq -s , 250))"

$ time ./universe 
(1, 2, 3, [...], 248, 249, 250)

real	0m5,616s
user	0m5,572s
sys	0m0,010s

$ fz -c -e "say ($(seq -s , 500))"

$ time ./universe 
(1, 2, 3, [...], 498, 499, 500)

real	0m45,940s
user	0m45,667s
sys	0m0,015s

$ fz -c -e "say ($(seq -s , 1000))"

$ time ./universe 
(1, 2, 3, [...], 998, 999, 1000)

real	6m29,264s
user	6m26,291s
sys	0m0,066s

I would intuitively expect that this is a problem that can be solved in linear time at worst. Note that I use the C backend here. The JVM backend supports tuples with at most 2^8 entries.

[michaellilltokiwa]

Nice find, agree that this should be in O(n)

[michaellilltokiwa]

Is this the same with the jvm backend?

[maxteufel]

As mentioned above, we need to use lower n due to limitations of the JVM. Then we have:

$ fz -classes -e "say ($(seq -s , 10))"

$ time ./universe 
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

real	0m0,311s
user	0m0,490s
sys	0m0,097s

$ fz -classes -e "say ($(seq -s , 50))"

$ time ./universe 
(1, 2, 3, [...], 48, 49, 50)

real	0m0,459s
user	0m1,129s
sys	0m0,159s

$ fz -classes -e "say ($(seq -s , 100))"

$ time ./universe 
(1, 2, 3, [...], 98, 99, 100)

real	0m0,583s
user	0m2,257s
sys	0m0,325s

$ fz -classes -e "say ($(seq -s , 200))"

$ time ./universe 
(1, 2, 3, [...], 198, 199, 200)

real	0m1,010s
user	0m2,871s
sys	0m0,415s

$ fz -classes -e "say ($(seq -s , 250))"

$ time ./universe 
(1, 2, 3, [...], 248, 249, 250)

real	0m1,427s
user	0m3,323s
sys	0m0,488s

The jump between 10, 50, and 100 looks less than linear, the jump between 100 and 200 is approximately linear, and then 200 to 250 seems to be a bit worse again. But this was just a one off test.

[michaellilltokiwa]

@maxteufel Ah sorry, did not read the original issue thoroughly enough.