One of my friends (bwilliam) pointed out to me this webpage "Python vs PHP, Python runs slower?" It intrigued me since I already did something similar to this before here. It has been said that Python is faster than PHP, but why in this case, is Python clearly slower than PHP? I was hoping that the user comments on that page would have an answer, but most people just posted a better implementation of finding prime numbers. So I took a little bit of time out of my hectic schedule to find the cause.
Here are the two scripts written by Teifion in PHP and Python:
PHP:
$primeNumbers = array();
$output = ”;
for ($i = 2; $i < 100000; $i++)
{
$divisible = false;
foreach ($primeNumbers as $number)
{
if ($i % $number == 0)
{
$divisible = true;
}
}
if ($divisible == false)
{
$primeNumbers[] = $i;
$output .= $i;
}
}
echo $output;
?>
Python:
output = []
for i in xrange(2, 100000):
divisible = False
for number in primeNumbers:
if i % number == 0:
divisible = True
if divisible == False:
primeNumbers.append(i)
output.append(str(i))
print ”.join(output)
I did some benchmark on his code as well and I received similar numbers to his,
Python
real 2m11.903s
user 2m11.456s
sys 0m0.038s
real 2m11.141s
user 2m10.677s
sys 0m0.067s
real 2m11.612s
user 2m10.956s
sys 0m0.050s
PHP
real 1m12.626s
user 1m12.303s
sys 0m0.034s
real 1m16.523s
user 1m15.815s
sys 0m0.040s
real 1m12.982s
user 1m12.686s
sys 0m0.033s
It is clear from these numbers that PHP is faster than Python. It’s around 60 seconds faster, that’s nearly %50! So I looked at the code more carefully and realized that the two scripts weren’t equivalent to each other. To eliminate this difference would lend us a clearer picture of what is going on. Here are the lines of code I will be concentrating on,
PHP:
{
if ($i % $number == 0)
{
$divisible = true;
}
}
Python:
if i % number == 0:
divisible = True
I believe the reason behind this is that this portion of code is not equivalent to one another. The reason is that the Python’s for loop has more use than PHP’s. To clarify, Teifion’s use of Python’s for loop in this case can be used on lists, tuples, dictionaries, strings, enumerate, and who knows what else? That is,
has more than one use. The language itself needs to determine what type it’s working on and proceed from there. On the other hand, PHP’s foreach is strictly used for arrays only, it has no other purposes.
I don’t know Python’s exact implementation of its for loop, but I can imagine it to be quite a bit more complex compared to PHP’s foreach. To compare the two would be like comparing peelers to knives. So, to have the two scripts behave more similarly, I changed this portion of code to the following,
PHP:
{
$number = $primeNumbers[$j];
if ($i % $number == 0)
{
$divisible = true;
}
}
Python:
number = primeNumbers[j]
if i % number == 0:
divisible = True
The result? You’ll be pretty surpsied,
Python
real 3m49.961s
user 3m49.618s
sys 0m0.063s
real 3m40.732s
user 3m40.396s
sys 0m0.065s
real 3m40.552s
user 3m40.215s
sys 0m0.060s
PHP
real 3m48.447s
user 3m47.926s
sys 0m0.068s
real 3m48.048s
user 3m47.554s
sys 0m0.073s
real 3m52.343s
user 3m51.764s
sys 0m0.063s
Nearly identical! What do you think? Please don’t tell me that the script can be optimized, I know. That’s besides the point.
array · hectic schedule · implementation · little bit · prime numbers · primenumbers · python · scripts
bwilliam · February 10, 2009 at 1:35 am
Haha. This is great. AK FTW.
Antti Kaihola · February 10, 2009 at 2:57 am
I tried the following subtle changes to see how they affect the performance:
import array ; primeNumbers = array(‘L’)
-> almost twice as slow
if 0 == i % number:
-> no change
if not i % number:
-> slight speedup
divisible = [1 for number in primeNumbers if i % number == 0]
if not divisible:
-> no change
divisible = [1 for number in primeNumbers if not i % number]
if not divisible:
-> slight speedup
That’s all I could come up with without significantly changing what the code does.
Two interesting variations which superficially don’t change the algorithm but actually stop the loop at first match:
divisible = (1 for number in primeNumbers if i % number == 0)
try:
divisible.next()
except StopIteration:
primeNumbers.append(i)
A version using Python 2.5 any():
for i in xrange(2, 10000):
divisible = any(i % number == 0 for number in primeNumbers)
if not divisible:
primeNumbers.append(i)
These two of course are in fact changing the algorithm.
(by the way, you have no help for comment formatting so I don’t know if my code blocks will format correctly)
Admin comment by A.K. · February 10, 2009 at 5:59 pm
Brandon,
LOL, you are such a prick.
Antti,
Those are very interesting observations. I would expect the same results for the same modifications in PHP as well. Sorry about the formatting, I didn’t install a plugin for comment coding.