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.
