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

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:

- C (GNU GCC 4.9.2, GCC with -O2 -std=c11 and -lm flags)
- C++ (GNU GCC 4.9.2, G++ with -O2 and -std=c++11 flags)
- Java (Java 8 OpenJDK)
- JavaScript (run on Node v 0.10.35)
- PHP 5.6.4
- Python 2.7.9 (and PyPy 2.4.0)
- Python 3.4.2
- 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:
*

- If
*n*< two: return*false*. - If number is equal to two: return
*true*. - If
*n*(*>2*) is even: return*false* - For all odd numbers,
*i*, greater than equal to three and up to and including*n*, return*true*if*n*is divisible by*i*. - 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 2*n*

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.

**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 Loading...