On Wednesday, 14 May 2014 at 09:47:56 UTC, Marc Schütz wrote:
I wouldn't say never, because optimizers have become damn good.
Well, "never" without a proof is of course a too strong claim.
:-) I agree with that, but I don't think optimizers are that good
yet even though some of my troubles have been solved.
I believe the additional overhead of lazy initialization is
mostly optimized away where it matters, i.e. inner loops,
because the compiler can see that the initialization has
already been performed in the first iteration. All it requires
is unrolling the first iteration of the loop and treating it
specially.
You can do this for some generators/iterators, but you have
different ways to construct loops and generators and consumers
that affect what is most efficient and how many registers you use
etc.
Abstractions hide what is going on, so the consumer might miss
more efficient way of structuring the algorithm.
Example: if you know that the end comes after 0, then you only
need to test empty() after you read 0. You don't need to test for
0, you just branch up to the start of the loop if the zero-flag
is set. Quasi ASM:
loop:
write(x)
start:
x = generate_next()
branch_if_not_zero loop
test( empty() )
branch_if_zero loop
write(0)
It is easy to construct examples where naive ranges will be
suboptimal.
For more complex iterators you also need to deal with sparse
datastructures, skiplists, run length encoded data, SIMD
alignment, guard protected stream ends… Meta information you
exploit when you need faster algorithms.
