Improve performance of php on local server

Question

I have a XAMPP install, with pretty much the default config.

Performance isn't much of a problem in general as I use PHP mostly to run web pages and small web apps. Waiting a couple seconds for a page is not unusual.

However, I have recently taken up the problems from Project Euler and decided to do them in PHP.

Try as I may, I couldn't get my code to run in less than 1 minute 1 second (optimized down from almost 3 min) and I was getting pretty embarrassed, especially considering most posters on Pjt Euler reported times of 1-3 seconds. (#7, find the 10001th prime)

I ported my code to C#, and the same task completed in a blink. 0.4 seconds. Same algorithm, the only notable difference in the code is that I used a List in C# to replace the array I was using in PHP.

While I did expect C# to outperform php, this difference leads me to suspect a gross configuration problem, but I have no idea where to look.

What could be the cause of this poor performance?

---

Edit: Here is the code:

In PHP:

/*
  * Project Euler #7:
  * By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
  * What is the 10001st prime number?
  */

ini_set('max_execution_time', 300);  
echo "start time:" . date("i:s:u") . "<br />";
function isPrime($number, $prevPrimes)
{       
    foreach ($prevPrimes as $key =>$prime)
    {
        if ($prime == 1)
        {
            continue;
        }
        elseif ($number % $prime == 0)
        {
            return 0;
        }
    }
    // If we get to here, $number is prime
    return $number; 
}
$primes = array();
$i = 0;
$nbPrimes = 0;
while ($nbPrimes <10001)
{
    $i++;
    if ($i % 2 != 0)
    {
        $result = isPrime($i, $primes);

        if ($result != 0)
        {
            $primes[] = $i;
            $nbPrimes++;
        }
    }
}
echo "#$nbPrimes: $result<br>";

echo "End time:" . date("i:s:u") . "<br />";

In C#:

public static void RunSnippet()
{
    Stopwatch stopwatch = new Stopwatch();
    stopwatch.Start();

    List<int> primes = new List<int>();
    int i = 0;
    int nbPrimes = 0;
    int result =0;
    while (nbPrimes <10001)
    {
        i++;
        if (i % 2 != 0)
        {
            result = isPrime(i, primes);

            if (result != 0)
            {
                primes.Add(i);
                nbPrimes++;
            }
        }
    }
    stopwatch.Stop();
    Console.WriteLine("Time elapsed: {0}",
    stopwatch.Elapsed);
    Console.WriteLine ("#" + nbPrimes + ": " + result.ToString());
}
public static int isPrime(int number, List<int> prevPrimes)
{
    foreach (int prime in prevPrimes)
    {
        if (prime == 1)
        {
            continue;
        }
        else if (number % prime == 0)
        {
            return 0;
        }
    }
    // If we get to here, number is prime
    return number;  
}   

Answer 1

FINAL EDIT

Here is the PHP code from Bakudan's logic, which returns this result:

start time:44:25:000000
#10001: 104759
End time:44:26:000000

The Code:

<?php
echo "start time:" . date("i:s:u") . "\n";

function isPrime($number, &$primes)
{
    if ($number === 1) return false;
    elseif ($number %2 === 0) return false;
    elseif ($number < 4) return true;
    elseif ($number < 9) return true;
    elseif ($number %3 === 0) return false;
    else $r = floor(sqrt($number));

    $f = 5;
    while ($f <= $r) {
        if ($number % $f ===0) return false;
        if ($number % ($f+2) === 0) return false;
        $f = $f + 6;
    }

    return true;
}

$primes = array();
$nbPrimes = $i = 0;
while ($nbPrimes < 10001)
{
    $i++;
    if (isPrime($i, $primes) !== false)
    {
        $primes[] = $i;
        $nbPrimes++;
    }
}
echo "#$nbPrimes: " . end($primes) . "\n";
echo "End time:" . date("i:s:u") . "\n";

Bakudan gave me the pseudo code, I Just translated and wrote it out for the OP's script above.

---

EDIT 2

I cleaned up the code a bit, didn't improve anything, may enhance "readability". But yea, I think this is the best you will get with PHP, which on an i7 without apache yields 5 seconds.

    <?php
    echo "start time:" . date("i:s:u") . "\n";

    function isPrime($number, &$primes)
    {
        foreach($primes as $prime) {
            if ($number % $prime === 0 && $prime > 1)
                    return false;
        }
    }

    $primes = array();
    $nbPrimes = $i = 1;
    while ($nbPrimes <= 10001)
    {
        if ($i % 2 !== 0 && isPrime($i, $primes) !== false)
        {
            $primes[] = $i;
            $nbPrimes++;
        }
        $i++;
    }
    echo "#$nbPrimes: " . end($primes) . "\n";
    echo "End time:" . date("i:s:u") . "\n";

---

EDIT

Knocked another second off by moving the $prime === 1 to be after the $number % $prime check in the same if statement.

start time:29:40:000000
#10001: 104743
End time:29:45:000000

---

Taking Hannes suggestion of strict checking and passing the array as reference plus adding a few tweaks of my own (modifying the array inside the function):

ini_set('max_execution_time', 300);
echo "start time:" . date("i:s:u") . "\n";

function isPrime($number, &$prevPrimes)
{
   foreach ($prevPrimes as $prime) {
        if ($number % $prime === 0 && $prime !== 1)
        {
            return false;
        }
    }

    // If we get to here, $number is prime
    $prevPrimes[] = $number;
    return $number;
}

$primes = array();
$i = 0;
$nbPrimes = 0;
while ($nbPrimes < 10001)
{
    $i++;
    if ($i % 2 !== 0)
    {
        $result = isPrime($i, $primes);

        if ($result !== 0)
        {
            $nbPrimes++;
        }
    }
}
echo "#$nbPrimes: $result\n";

echo "End time:" . date("i:s:u") . "\n";

Which ended up being:

start time:52:08:000000
#10001: 104743
End time:52:15:000000

VS your code:

start time:50:44:000000
#10001: 104743
End time:51:17:000000

A good improvement there, but nothing like C#, just goes to show the power of a compiled language :)

Answer 2

"Use the force ..." of math! Just throwing some code pointless. Here are just a few points that can boost the performance.

• why you are using array to match the number against?

• the foreach function is thus ineffective - the cycle should end at floor(sqrt(number))

  example: sqrt(64) = 8 -> all prime dividers will be from 1 to 8. The others will be product of them( 32 = 4 x 8 = 2x2x2x2x2 )

• use formulas to jump to the next possibly prime number

  math:

  numbers divisable by 2 - 2, 4, 6, 8, 10, 12 -> 2k+1 = 2x1+1 = 3, 5, .....

  numbers divisable by 3 - 3, 6, 9, 12 -> we already have 6 and 12, so 3, 9, 15, 21 -> 3(2k-1) = 3(2x1-1) = 3, 9, ...

here is some pseudo code from hk admin at project euler

isPrime ( number )
{
    if ( number == 1 )      return false
    elseif ( number < 4 )       return true
    elseif ( number % 2 == 0 )  return false
    elseif ( number < 9 )       return true
    elseif ( number % 3 == 0 )  return false
    else
        r = floor ( sqrt ( number ) ) 
    f = 5
    while ( f <= r )
    {
        if ( number % f == 0 ) return false
        if ( number % ( f + 2 ) == 0 ) return false
        f = f + 6
    }
    return true
}

PS

About the difference in the speed of the execution - PHP is interpreted language, to view the result in browser you have 3 programs running - browser, server, php interpreter. You make a http request, the server calls php (and probably a bunch of other stuff, logging for example),php reads the script and executes it. There are much more steps than in C#.

In C# the compiled code is executed.

Answer 3

While I did expect C# to outperform php, this difference leads me to suspect a gross configuration problem, but I have no idea where to look.

Firing the PHP engine creates a little overhead for the webserver. The way PHP is loaded (e.g. loaded as a module on server startup or loaded on demand for every .php request) determines how much overhead is involved. Then on windows there are two variants of PHP available: thread-safe and non thread-safe, the latter one is claimed to be faster.

If its a XAMPP configuration problem, I think you can isolate it by running the test 3 times on your webserver and note down the average time. Then run the same script via PHP CLI 3 times and note down the average. If the difference is noticeable then you might blame XAMPP. You should be able to locate the PHP CLI binary somewhere inside the XAMPP installation folder.

On my system I get these results:

PHP-CLI:            #10001: 104743 -- Time taken: 30.25 second(s)
PHP on IIS/FastCGI: #10001: 104743 -- Time taken: 29.89 second(s)
PHP on Apache/CGI:  #10001: 104743 -- Time taken: 29.93 second(s)

Not much of a difference -- I would rather optimize the code.

EDIT

Same machine and everything but execution time brought down from ~30 seconds to ~5.85 seconds with this revised code. The only thing worth mentioning is that that I used a global array instead of passing it by value every time the isPrime function is called (104743 times to be precise). Passing the array by reference also results in similar execution time, give or take 1 second. The comparison operators shave off just a second or two but not much.

/*
 * Project Euler #7:
 * By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
 * What is the 10001st prime number?
 */
ini_set('max_execution_time', 300);  
$t0 = microtime(true);
$primes = array();
function isPrime($number)
{       
    global $primes;
    foreach ($primes as $prime)
    {
        if ($prime === 1)
        {
            continue;
        }
        elseif ($number % $prime === 0)
        {
            return 0;
        }
    }
    return $number; 
}
$i = 0;
$nbPrimes = 0;
while ($nbPrimes < 10001)
{
    $i++;
    if ($i % 2 !== 0)
    {
        $result = isPrime($i);
        if ($result !== 0)
        {
            $primes[] = $i;
            $nbPrimes++;
        }
    }
}
$t1 = microtime(true);
echo sprintf('#%d: %d -- Time taken: %.2f second(s)', $nbPrimes, $result, $t1 - $t0);