why recursive factorial is faster than fold in ceylon

Question

I have this ceylon code :

Integer fact(Integer n)
{
    return (n<=1)then 1 else n*fact(n-1);
}
Integer? factorial(Integer|String|Null n)
{
    Integer? num;
    if(is String n)
    {
        num=parseInteger(n);
    }
    else if(is Integer n)
    {
        num=n;      
    }   
    else
    {
        num=null;
    }
    if(exists num)
    {
        if(num<0)
        {
            return null;
        }
        if(num==0)
        {
            return 1;
        }
        return (2..num).fold(1)((x,y)=>x*y);//line 1
    }
    else
    {
        return null;        
    }       
}
shared void main() 
{
    print("enter a number");
    value input=process.readLine()?.trimmed;
    value starttime=system.milliseconds;
    value fact=factorial(input);
    value elapsedtime=(system.milliseconds-starttime).float/1000;
    if(exists fact)
    {
        print("(!n)=``fact``");
        print(elapsedtime);
    }
    else
    {
        print("Error, either you gave a negative number or you didn't enter an integer(or did you left the input blank ?)");
    }   
}

On line 1 I'm using fold to calculate the factorial, I get performance between 0.08 and 0.06 seconds.

Now if I replace line 1 with this :

return fact(num);

I get performance between 0.021 and 0.012, why is that ?

The number I tried was 10 in this case.

score 5 · Accepted Answer · edited May 23 '17 at 11:53

a couple of remarks first:

don't use system.milliseconds for small measurements, it's notoriously imprecise (it's max resolution is 1/60th of a second or about 16ms), use system.nanoTime instead
for the Java VM this is too small of a benchmark to be able to say anything worthwhile, the VM needs to "warm up" before it does any optimizations. See How do I write a correct micro-benchmark in Java? for more information

But besides that one reason the fact() might be faster is because its code gets optimized internally to use Java primitive types while the fold() is a generic function which might mean that a lot of boxing is taking place.

Right now Ceylon is not so good yet at optimizing functions having generic parameters or return types when dealing with basic types like Integer and Float and such. Hopefully in a future version we'll be able to remedy that somewhat.

why recursive factorial is faster than fold in ceylon

1 Answers1