OT (partially): about promotion of integers

[Timon Gehr]

On 12/12/2012 10:35 PM, Walter Bright wrote:
> On 12/12/2012 12:01 PM, Timon Gehr wrote:
>> That is certainly fixable. It is a mere QOI issue.
>
> When you have a language that fundamentally disallows mutation,

It does not.

> some algorithms are doomed to be slower.

Here's a (real) quicksort:
http://stackoverflow.com/questions/5268156/how-do-you-do-an-in-place-quicksort-in-haskell

> I asked Erik Maijer, one of the developers of
> Haskell, if the implementation does mutation "under the hood" to make
> things go faster.

"under the hood", obviously there must be mutation as this is how the 
machine works.

>  He assured me that it does not, that it follows the
> "no mutation" all the way.
>

Maybe he misunderstood. i.e. DMD does not do this to immutable data 
either. eg. Control.Monad.ST allows in-place state mutation of data 
types eg. from Data.STRef and Data.Array.ST. Such operations are 
sequenced and crosstalk between multiple such 'threads' is excluded by 
the type system, as long as only safe operations are used.

It is somewhat similar to (the still quite broken) 'pure' in D, but 
stronger. (e.g. it is possible to pass mutable references into the rough 
equivalent of 'strongly pure' code, but that code won't be able to read 
their values, the references can appear as part of the return type, and 
the caller will be able to access them again -- Done using basically 
nothing but parametric polymorphism, which D lacks.)


Eg:

 > runST $ do           -- ()pure{
     x <- newSTRef 0    -- auto x = 0;
     writeSTRef x 2     -- x = 2; // mutate x
     y <- readSTRef x   -- auto y = x;
     writeSTRef x 3     -- x = 3; // mutate x
     z <- readSTRef x   -- auto z = x;
     return (y,z)       -- return tuple(y,z);}();
(2,3)                  -- tuple(2,3)


This paper describes how this is implemented in GHC (in-place mutation)
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.3299

The only reason I can see why this is not as fast as D is implementation 
simplicity on the compiler side.

Here is some of the library code. It makes use of primitives (intrinsics):
http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/GHC-ST.html#ST

>
>> I think the factor GHC/DMD cannot be more than about 2 or 3 for roughly
>> equivalently written imperative code.
>
> A factor of 2 or 3 is make or break for a large class of programs.
>
> Consider running a server farm. If you can make your code 5% faster, you
> need 5% fewer servers. That translates into millions of dollars.

Provided the code is correct.