Re: [Chicken-hackers] [PATCH][5] numbers integration

[Peter Bex]

On Wed, Feb 11, 2015 at 01:09:23PM +0100, Felix Winkelmann wrote:
> Micro-optimizations won't give much, as Peter said: the CPS calls are
> what's expensive and there is no fast path that one could take. If, for
> example one would implement "optimistic inlining" (as in the Feeley paper),
> where one would rewrite 
> 
>   (+ x y)
> 
> into
> 
>   (let* ((tmp1 x)
>          (tmp2 y)
>          (tmp3 (##sys#fast-fixnum-+-that-checks-for-overflow x y)))
>     (or tmp3 (##sys#slow-generic-+ x y)))
> 
> then the slow-call will be a CPS call, and the code transformed
> accordingly, so nothing is won, because the speed advantage of fixnum
> math is that we can avoid the CPS calls and cram more numerical
> operations into a single CPS-converted function.

One way that might work (but it is a little ugly) is to pre-allocate
the maximum number size that could possibly result from the operators
used in a procedure.  For example, assuming integers, a procedure that
contains one addition and one subtraction of two numbers would allocate
the size of the largest of the two numbers plus one limb, times two
(naive approach).  This can be calculated up front by a stub procedure
or prelude which allocates the needed space and then invokes the actual
procedure.  Calculating the needed space will of course also take a little
extra time (but is trivial, for integers at least).

This would require substantial hacking of the compiler and make things
a lot trickier.  Also, it would probably raise the frequency of GCs in
many cases, and due to pessimistic allocation might allocate way too
much data.

Also, it would require moving the allocation of complex numbers and
rational numbers into C, with all the complexity that entails.
I'd have to seriously think about this and whether it's feasible at all.
It may not be worth it, due to the disadvantages I mentioned.

> Personally, I find the performance impact Peter reported unacceptable,
> and something has to be done about it before we commit on
> numbers-integration. But that's just _my_ opinion.

So far it looks like a small majority is for this change, but I agree
with you that the performance impact is rather too high.

Does anyone on the list know whether there's a way to reduce stack space
from C function calls?  If we can compress the stack more tightly, the
performance impact will be a lot smaller.  Perhaps getting rid of some
of the intermediate stub/trampoline functions?

Cheers,
Peter

signature.asc
Description: Digital signature