[Haskell-beginners] Re: [Haskell-begin] Maximum of a List?

[Niels Aan de Brugh]

Daniel Fischer wrote:
> Using -O2, GHC produces the same core with or without strictness annotations, 
> the 'acc' parameter of f is an unboxed Int, so the optimiser indeed sees it 
> is needed. The Integer parameter unfortunately can't be unboxed. A native 
> 64-bit integer type might gain something.
>   
Right. For this puzzle (n up to 1000000) it's quite safe to say an Int64 
will never overflow. :-)

I was wondering how the Integer type is implemented. If I were to 
implement such a type my first approach would be to keep a list of 
digits (and perform calculation like I do by hand). But operations on 
Integers are very fast, even on very big numbers, so I guess that's not 
the approach taken by the GHC developers. (For example, calculating the 
faculties of [1..1000] takes a little under 300ms to perform on my Intel 
PC; if I don't pipe to /dev/null it takes about 10s because of all the 
digits being printed.)

Having a type like Integer on board makes many of the puzzles on Project 
Euler a shoo-in. One of the questions is indeed to calculate the last n 
digits of 1000!.
> Using a Map, though easier to code, doesn't buy you much here, indeed less 
> than a few easy considerations where the maximal length cannot occur. The 
> problem is that you have to update the Map often, which is rather costly, 
> also the Map takes a lot of memory. Using an array is more convoluted, but 
> much faster (if done right).
>   
The problem with an array is finding a good upper limit. One could of 
course copy the whole array if a new upper bound is found, the costs 
would amortize over the whole run. Having a really big and sparse array 
is no good either (no/bad locality of reference).

Oh well, the puzzle itself definitely isn't worth the effort, but maybe 
some custom made heap structure would perform best.
> At least, it would take far longer to get the solution.
>   
Yes, but sometimes the difference is several days vs. a couple of minutes.
> Nowadays, the native code generator is not necessarily slower than -fvia-C, 
> often faster. So the best should be to test both, -O2 and -O2 -fvia-C 
> -optc-On, for some medium sized inputs and see which actually is faster.
>   
Interesting. In which release has the back-end been reworked? Does it 
work equally well for architectures other than Intel?

Niels