> On 23 Oct , Simon Marlow wrote:
> > [EMAIL PROTECTED] (S.D.Mechveliani) writes:
> >=20
> >> Observation:
> >>=20
> >> In ghc-2.08 (linux, PC-486), -O compilation
> >>=20
> >> "Integer is 5 times slower than Int" - even when the numbers
> >> are small ( < 2^20 ).
> >=20
> > This is reasonable, considering that each integer operation involves a
> > function call to the arbitrary precision arithmetic library, whereas
> > Int operations are inlined.
>
> I have a feeling that it is possible to do better than this, at least
> partly by using Int internally for numbers less than 2^30 or so, and
> caching intermediate results. Any pointers, Mark?
>
OK, there are two distinct issues here, I think.
Firstly it pays off well to inline the common case (to use the Lisp
parlance - FIXNUMs, immediate tagged integers). You are typically
going to have to pay for tag-testing before the operation and overflow
checking afterwards, but some architectures allow you do these quite
cheaply [Sparc's tagged-add instruction, for instance] If you only
call out-of-line for actual BIGNUMs, then you save a lot of
(micro-)context switching. The tag tests for binary operations are
usually combined into one by ORing the tags together, and you avoid
tag-correction in the common cases of addition and subtraction by
assigning a zero tag to FIXnums - multiply and divide need only a
single shift to correct.
Secondly you can apply compile-time analysis to determine which
(intermediate) values/operations can or can't be/overflow to BIGNUMs.
Sometimes the range of a value is known within that representatable as
a FIXNUM (the lengths of vectors and strings, iteration variables used
over such bounded datatypes, results of modulus by a constant, etc.
Thus tag-tests and overflow-checks can be optimized away where
appropriate.
A more aggressive optimization is to duplicate the code and do a test
at the top to choose between FIXNUM only and generic versions -
probably worthwhile for small inner loops.
Of course a lazy language gives one less scope for compile-time
knowledge of data-structure size limits (or indeed of recognizing
enough strictness to find the inner loops...)
__Mark
[ [EMAIL PROTECTED] | http://www.harlequin.co.uk/ | +44(0)1954 785433 ]
