Prime number performance difference ACF vs. Lucee

Question

The following code to find prime numbers greatly differs between Adobe ColdFusion (10) and Lucee (4.5) regarding performance. Tested on the same machine (6C i7 3930k @ 4 GHz, Windows 10 64 Bit, JVM memory settings equal on both CFML engines: JDK7 -Xms512m -Xmx2048m -XX:MaxPermSize=512m):

<cfscript>
    ticks = getTickCount();
    stopIndex   = 10000;
    primes      = [];
    divisions   = 0;
    primes.add(2);
    primes.add(3);
    n = 5;
    for (n; n < stopIndex; n += 2) {
        isPrime = true;
        d = 3;
        for (d; d < n; d++) {
            divisions++;
            if (n % d == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime) {
            primes.add(n);
        }
    }
    ticks = (getTickCount() - ticks);
</cfscript>

<cfoutput>
    <p>
        #numberFormat(divisions)# divisions in #ticks# ms.
    </p>
    <p>
        #numberFormat(arrayLen(primes))# prime numbers found below #numberFormat(stopIndex)#.
    </p>
</cfoutput>

stopIndex @ 10k

ACF: 280 ms
LUC: 1300 ms

stopIndex @ 20k

ACF: 1000 ms
LUC: 4800 ms

stopIndex @ 30k

ACF: 2200 ms
LUC: 10500 ms

trycf.com and cflive.net show a similar gap.

I checked if cfscript (vs. tags) has impact on the time, it doesn't. CFML engine related server settings do not seem to have any noticable impact either.

What could be the reason for the performance difference?
And how could I possibly resolve this?

Background: I'm running heavy math ops (geometry, image rendering)) on a production server, which happens to be running Lucee, and noticed the sluggish performance.

Take stack traces during the execution and see what code is running the most. Also, profile the memory usage on the VM to see if it's different. — Brad Wood, May 04 '16 at 20:29
@alex Thanks for raising this. I've been discussing this with the Lucee team and we are going to take a deeper look and see why there is this performance difference between ACF and Lucee and see if there are any performance gains we can make in Lucee to improve this. — andrewdixon, May 04 '16 at 21:32

score 2 · Answer 1 · answered Oct 09 '17 at 01:04

Integer maths is slower than floating point maths, so this runs slower because of the way that Lucee stores variables as types. if you force the n to be non integer Lucee runs 4x faster

if ((n+1.0) % d == 0) {

This tweak also more than doubles the speed in ACF too

https://luceeserver.atlassian.net/browse/LDEV-1541

score 0 · Answer 2 · answered May 09 '16 at 22:09

I think the performance issue side of things is down to Lucee to fix, rather than you and your code.

However from the perspective of overall performance of this particular algorithm, they best economy you can make is to loop to sqr(n)+1 rather than all the way to n. You're doing way more work than you need to be, and that's a bigger contributor to the performance of this code than the platform differences.

Also you only need to loop over the preceding primes, not every (second) number. That'd improve your performance further.

I realise the algorithm is just an example, but in all honesty the rest of it isn't something yer likely to be able to fix. Raise a ticket with Lucee and wait for it to be fixed (or DIY, if you have the time / Java knowledge).

score 0 · Answer 3 · answered Apr 24 '21 at 23:33

I know this is not answering the question, but taking Adam's comment further, it doesn't even have to be up to the square root. Once you realize a number isn't divisible by 3, you can limit your top to the results of the division by 3. Tracking previous prime numbers takes memory when your n becomes large. If you can afford that, that's great. If you can't, then incrementing the denominator by 2 would speed it up by 2 since you're skipping even numbers. This code is about 50 times faster:

<cfscript>
    ticks = getTickCount();
    stopIndex   = 10000;
    primes      = [];
    divisions   = 0;
    primes.add(2);
    primes.add(3);
    n = 5;
    for (n; n < stopIndex; n += 2) {
        isPrime = true;
        d=3;
        n2=n;
        for (d; d < n2; ) {
            divisions++;
            Result=n/d;
            if (Result eq Int(Result)) {
                isPrime = false;
                break;
            } else {
              d+=2;
              n2=Result;
            }
        }
        if (isPrime) {
            primes.add(n);
        }
    }
    ticks = (getTickCount() - ticks);
</cfscript>

56,570 divisions in 32 ms (vs. 1500 before on my machine)

1,229 prime numbers found below 10,000.

Prime number performance difference ACF vs. Lucee

3 Answers3