New linked list

[Dave]

Sean Kelly wrote:
> You know, this whole sequence optimization business seems to be linked 
> to mutability: if no mutating operations are performed then optimize 
> away!  Unfortunately, I haven't seen a high-level construct for method 
> classification that can't be violated by the user.  And while this may 
> be irritating in some cases, it could lead to nasty bugs in the face of 
> such optimizations.  In some respects, it would be nice if each 
> operation in the language could be labeled as mutating or non-mutating 
> and then functions could be analyzed for atomicity during compilation, 
> so a function would considered atomic if it does not perform a mutating 
> operation on non-local data.  But this may be overly restrictive.  For 
> example, the body of a foreach loop must be able to perform some 
> mutating operations, but different categorites would impose different 
> restrictions on optimization:
> 
>     int sum = 0;
>     foreach( int val; values ) {
>         sum += val;
>     }
> 
> Here, the code could be heavily parallelized because the result doesn't 
> depend on the sequence in which operations are performed.  However:
> 
>     foreach( int val; values ) {
>         printf( "val: %d\n", val );
>     }
> 
> Here, the code could be optimized somewhat but must still be executed 
> sequentially.  By comparison:
> 
>     void fn() {
>         values ~= 5;
>     }
> 
>     foreach( int val; values ) {
>         if( val > 10 ) fn();
>     }
> 
> No optimizations may be performed here because the iteration sequence is 
> being modified during processing.  To make matters worse, this could 
> occur through an untraceable sequence of pointers and such that the 
> compiler can't make sense of.  What would be wonderful is if there were 
> a way to distinguish these three categories of code somehow.  I know, 
> that's the million dollar question, but I harbor a secret hope that if 
> it's asked frequently enough then perhaps someone will think of an answer.
> 
> 
> Sean

Maybe I'm taking this out of context because I just jumped into this 
thread, but...

I think a D compiler (because foreach is built-in) could safely optimize 
those three w/o a lot of magic right now.

For #1, neither sum nor val are references and there isn't a call 
outside of the loop scope. So I think a compiler could determine that 
and fully optimize w/ parallelization or whatever.

The 2nd one calls outside of the loop scope, so the compiler could keep 
track of that to determine that it can't safely do any optimization 
where the elements may be unordered. Even if it is a call to something 
like putc which is then inlined, it must eventually make a call and/or 
write a value to a hardware reference, either of which - call or 
dereference - the optimizer could flag as "can't use an unordered 
optimization".

IIRC, the 3rd one is undefined behavior because the aggregate is 
modified inside the loop. But even if it wasn't, the same restrictions 
for #2 could be put on it because it calls outside of the loop scope.