The last time Hackerfall tried to access this page, it returned a not found error. A cached version of the page is below, or clickhereto continue anyway

Yet Another Language Speed Test: Counting Primes (C, C++, Java, JavaScript, PHP, Python and Ruby) | BJ Pelc

After recently reading about just how quick JavaScript is when run on the Node platform I thought I would take a look for myself and compare the speed against a number of other widely used languages, both compiled and scripted.

The following languages were used:

  1. C (GNU GCC 4.9.2, GCC with -O2 -std=c11 and -lm flags)
  2. C++ (GNU GCC 4.9.2, G++ with -O2 and -std=c++11 flags)
  3. Java (Java 8 OpenJDK)
  4. JavaScript (run on Node v 0.10.35)
  5. PHP 5.6.4
  6. Python 2.7.9 (and PyPy 2.4.0)
  7. Python 3.4.2
  8. Ruby 2.2.0

To benchmark the various languages I have used a pretty common mathematical function, the prime counting function, (x). (x) returns the number of prime numbers up to and including x. As it is the speed of the various languages that is of interest here and not the efficiency of the particular algorithm, a very basic algorithm was implemented. To check if a number, n is prime the function isPrime(n) implements the following algorithm:

  1. If n < two: return false.
  2. If number is equal to two: return true.
  3. If n (>2) is even: return false
  4. For all odd numbers, i, greater than equal to three and up to and including n, return true if n is divisible by i.
  5. If none of the above conditions are met: return true

The only optimisations in the algorithm are that for numbers, n > 2, even numbers are instantly flagged as not prime and the divisibility of odd numbers is only checked against odd numbers in the range 3 to n (since all factors of a number n which are greater than n are multiples of a lesser factor). Using this algorithm, (x) is calculated by checking each number from 0 to x for primality, if the current number, n is prime, the count is incremented by one.

Of course, more efficient algorithms exist (such as the sieve of Eratosthenes) but that is beyond the scope of the current benchmark. The aim here is to apply the above algorithm, as close as possible, in the various languages using the best features of each language (using as few imported functions/libraries as possible) to minimise the time taken to calculate (x).

C was used as the baseline as it is fastest of all the selected languages, (I could have used FORTRAN, but since leaving academia I do not wish to see FORTRAN ever again). Below is the C code that was used (naturally C does not play with boolean values without loading another library so true and false are replaced with the values 1 and 0 respectively):


#include <stdio.h>
#include <math.h> /* For sqrt */

/* Check if the number n is prime */
int isPrime(int n) {
	if (n < 2)
		return 0;
	else if (n == 2)
		return 1;
	else if (n % 2 == 0)
		return 0;

	int upperLimit = sqrt(n);
	int i = 3;
	while (i <= upperLimit) {
		if (n % i == 0)
			return 0;
		i += 2;
	}
	return 1;
}

/* count the number of primes up to and including limit */
int main() {
	int noPrimes = 0, limit = 67108864;
	for (int n = 0; n <= limit; n++) {
		if (isPrime(n))
			noPrimes ++;
	}
	printf("pi(%d) = %d\n", limit, noPrimes);
	return 0;
}

The code for the other languages can be found at the end of this post.

In order to get a good comparison of the time taken to compute (x), x was taken over a range of powers of two from 212 to 226. This range was selected as anything below (212) is either too quick to time or does not decrease further and anything greater than (226) just takes too long for me to be bothered with.

For the compiled languages (C, C++ and Java), the code was recompiled for each limit over which primes are to be counted, x, this was decided as I did not want the time taken for the calculation to run to include having to interpret a command line argument. For the scripted languages, x is simply altered before running the script. The time taken to run the calculation for each upper limit, x, was calculated using bash’s inbuilt time function and taking the real time (ie wall clock time) e.g. :


time ruby ruby_primes.rb

The calculation was ran five times for each value of x and the average time taken. The chart below shows the absolute time, in seconds to calculate (x), where the upper limit x = 2n.

Number of seconds taken to count the number of primes up to and including 2n

No major surprises in that C is the fastest, with C++ approximately the same for (218) and above. The bash time function only measure to millisecond accuracy, here for C in the case (214) and below it can be assumed the measurement time is inaccurate and is showing a rounded value at 1ms.

Java runs very favourably at higher values and is only a fraction behind C and C++, the poor performance at lower values of (x) can be attributed to the time taken to load the Java environment. The really interesting result here is just how quick JavaScript runs, for higher values of (x), the time taken is approximately only four times that of C which makes it approximately 6 time faster than the next nearest non-compiled language, Ruby. There is precious little to choose between PHP and Ruby apart from at low levels of (x).

Python is the slowest of the languages by quite some margin, with Python 2 taking more than three times as long as Ruby, yet more, Python 3 is slower than Python 2, this has been noticed by others, for me, this seems pretty ridiculous, why would people want to move to Python 3 when it is slower than 2? True, the Pythonistas will say “don’t use Python if it is speed you are after”, but with the use of Python as a web language growing, and the ever increasing data driven nature of the web, speed should not be overlooked. Granted though, the Python code does run very impressively when run with PyPy, running at approximately 12 times quicker than Python 2.

To give Ruby the same chance as I did Python, the Ruby code was run on JRuby, this was a non-starter, the code took approximately 5 times longer than then when executed with standard Ruby.

Notably, it should be mentioned that writing idiomatic Python and Ruby results in much slower code than that used here. Ranges bad. While loops good. For example, in Ruby, the following while loop:


upper_lim = (Math.sqrt n.to_f).to_i
i = 3
while i <= upper_lim
  return false if n % i == 0
  i += 2
end

runs 40% faster than the following idiomatic Ruby way of using the each method on a range:


(3..(Math.sqrt n.to_f).to_i).step(2).each { |i| return false if n % i == 0 }

The reason for this, as far as I can guess, is that in creating a range memory has to be allocated to store each value in that range before the each method can be applied to it and when the range contains millions of values, this can be rather time consuming.

Similar results were also achieved by switching to while loops in Python. In the remaining languages, slight improvements were made when switching from for loops to while loops.

I do not claim to be an expert in any of these languages so I may well have missed some tricks, there may well be faster ways of implementing this algorithm in the various languages, if anybody can highlight where any of the code could be further optimised, please go ahead and inform me.

Feel free to add any recommendations for other languages, or the code to implement the algorithm in another language to the comments section.

So, in conclusion, as expected, it is pretty hard to beat the usual compiled suspects, namely C, C++ and Java at this type of iterative numerical calculation but if care is taken to optimize the implementation of algorithms scripted languages such as PHP and Ruby are quite capable of delivering adequate performance. But it seems if you are after a scripting language to quickly carry out this type of numerical analysis then JavaScript is by far the fastest option.

Code Used

C++


#include <iostream>
#include <cmath> 		/* for sqrt */ 

/* is n prime? Return true if so, false if not */
bool isPrime(int n) {
	if (n < 2)
		return false;
	else if (n == 2)
		return true;
	else if (n % 2 == 0)
		return false;

	int upperLimit = (int) std::sqrt(n);
	int i = 3;
	while (i <= upperLimit) {
		if (n % i == 0)
			return false;
		i += 2;
	}
	return true;
}

/* count the number of primes up to limit */
int main() {
	int noPrimes = 0, limit = 16777216;
	for (int n = 0; n <= limit; n++) {
		if (isPrime(n))
			noPrimes++;
	}
	printf("pi(%d) = %d\n",
		limit,
		noPrimes);
	return 0;
}

Java


class java_12 {
	public static boolean isPrime(int n) {
		if (n < 2)
			return false;
		else if (n == 2)
			return true;
		else if (n % 2 == 0)
			return false;
		int uL = (int) Math.sqrt(n);
		int i = 3;
		while (i <= uL) {
			if (n % i == 0)
				return false;
			i += 2;
		}
		return true;
	}

	public static void main(String[] args) {
		int limit = 4096, noPrimes = 0;
		for (int i = 0; i <= limit; i++) {
			if (isPrime(i))
				noPrimes++;
		}
		System.out.println("Number of primes in the interval [0," + limit + "]: " + noPrimes);
	}
}

JavaScript


function isPrime(n) {
	if (n < 2)
		return false;
	else if (n == 2)
		return true;
	else if (n % 2 == 0)
		return false;
	var uL = Math.sqrt(n) | 0, i = 3;
	while (i <= uL) {
		if (n % i == 0)
			return false;
		i += 2;
	}
	return true;
}

// Find the primes
var noPrimes = 0,
	limit = 67108864;

for (var i = 0; i <= limit; i++) {
	if (isPrime(i))
		noPrimes++;
}

console.log("Number of primes in the interval [0," + limit + "]: " + noPrimes);

PHP


<?php
function isPrime($n) {
	if ($n < 2)
		return false;
	elseif ($n == 2)
		return true;
	elseif ($n % 2 == 0)
		return false;
	$ul = sqrt($n);
	$i = 3;
	// huge savings made on taking sqrt out of the loop condition and
	// replacing for loop with while
	while ($i <= $ul) {
		if ($n % $i == 0)
			return false;
		$i+=2;
	}
	return true;
}

$noPrimes = $i = 0;
$limit = 67108864;

while ($i <= $limit) {
	if (isPrime($i))
		$noPrimes++;
	$i++;
}

printf("Number of primes in the interval [0,%d]: %d\n", $limit, $noPrimes);

Python


#!/usr/bin/env python
from math import sqrt

def isPrime(n):
    if (n < 2): return False
    elif (n == 2): return True
    elif (n % 2 == 0): return False

    upper_limit = int(sqrt(n))
    i = 3
    while (i <= upper_limit):
    	if (n % i == 0): return False
    	i += 2

    return True

lim = 67108864
no_primes = 0
n = 0

while (n <= lim):
    if (isPrime(n)): no_primes += 1
    n += 1

print ("Number of primes in the interval [0,%d]: %d" % (lim, no_primes))

Ruby


#!/usr/bin/env ruby

def isPrime n
	return false if n < 2
	return true if n == 2
	return false if n % 2 == 0

	upper_lim = (Math.sqrt n.to_f).to_i
  i = 3
  while i<= upper_lim
    return false if n % i == 0
    i+=2
  end

  true		
end

lim=67108864
no_primes = 0

i = 0
while i<= lim
  no_primes += 1 if isPrime i
  i+=1
end
puts "Number of primes in the interval [0,#{lim}]: #{no_primes}"

Like this:

Like Loading...

Continue reading on bjpelc.wordpress.com