need help optimizing a function

[Alastair Reid]

Hal Daume <hdaume@ISI.EDU> writes:

> p.s., I sense your next question is going to be something like "why
> can't the compiler detect that the array can be updated in place
> instead of copied" and the answer, from what i can tell, is simply
> that it doesn't try.

And one might argue that it should not try since the result would be
incredibly fragile with small, semantics preserving changes to the
program confusing the analysis and causing changes in the big-O
complexity of your program and, since the analysis would undoubtedly
be pretty darn cunning, it'd also be virtually impossible to
understand why it did or did not manage to detect the
single-threadedness of your code.

I think one of the reasons that approaches based on types (monads,
MADTs, linear types, etc.) are so popular is that they make the
programmers assertion (X is used in a single-threaded manner)
sufficiently explicit that the compiler can complain when it disagrees
and, since parts of the analysis show through in the typesystem, they
make the analysis less of a black box.

--
Alastair Reid                 alastair@reid-consulting-uk.ltd.uk  
Reid Consulting (UK) Limited  http://www.reid-consulting-uk.ltd.uk/alastair/


ps The opening paragraphs of Paul Hudak's MADT paper
(http://www.haskell.org/papers/madt.ps) have a more coherent
explanation of why smarter compilers are not the answer.