Disclaimer
I know that artificial benchmarks are evil. They can show results only for very specific narrow situation. I don't assume that one language is better than the other because of the some stupid bench. However I wonder why results is so different. Please see my questions at the bottom.
Math benchmark description
Benchmark is simple math calculations to find pairs of prime numbers which differs by 6 (so called sexy primes)
E.g. sexy primes below 100 would be: (5 11) (7 13) (11 17) (13 19) (17 23) (23 29) (31 37) (37 43) (41 47) (47 53) (53 59) (61 67) (67 73) (73 79) (83 89) (97 103)
Results table
In table: calculation time in seconds Running: all except Factor was running in VirtualBox (Debian unstable amd64 guest, Windows 7 x64 host) CPU: AMD A4-3305M
Sexy primes up to: 10k 20k 30k 100k
Bash 58.00 200.00 [*1] [*1]
C 0.20 0.65 1.42 15.00
Clojure1.4 4.12 8.32 16.00 137.93
Clojure1.4 (optimized) 0.95 1.82 2.30 16.00
Factor n/a n/a 15.00 180.00
Python2.7 1.49 5.20 11.00 119
Ruby1.8 5.10 18.32 40.48 377.00
Ruby1.9.3 1.36 5.73 10.48 106.00
Scala2.9.2 0.93 1.41 2.73 20.84
Scala2.9.2 (optimized) 0.32 0.79 1.46 12.01
[*1] - I'm afraid to imagine how much time will it take
Code listings
C:
int isprime(int x) {
int i;
for (i = 2; i < x; ++i)
if (x%i == 0) return 0;
return 1;
}
void findprimes(int m) {
int i;
for ( i = 11; i < m; ++i)
if (isprime(i) && isprime(i-6))
printf("%d %d\n", i-6, i);
}
main() {
findprimes(10*1000);
}
Ruby:
def is_prime?(n)
(2...n).all?{|m| n%m != 0 }
end
def sexy_primes(x)
(9..x).map do |i|
[i-6, i]
end.select do |j|
j.all?{|j| is_prime? j}
end
end
a = Time.now
p sexy_primes(10*1000)
b = Time.now
puts "#{(b-a)*1000} mils"
Scala:
def isPrime(n: Int) =
(2 until n) forall { n % _ != 0 }
def sexyPrimes(n: Int) =
(11 to n) map { i => List(i-6, i) } filter { _ forall(isPrime(_)) }
val a = System.currentTimeMillis()
println(sexyPrimes(100*1000))
val b = System.currentTimeMillis()
println((b-a).toString + " mils")
Scala opimized isPrime (the same idea like in Clojure optimization):
import scala.annotation.tailrec
@tailrec // Not required, but will warn if optimization doesn't work
def isPrime(n: Int, i: Int = 2): Boolean =
if (i == n) true
else if (n % i != 0) isPrime(n, i + 1)
else false
Clojure:
(defn is-prime? [n]
(every? #(> (mod n %) 0)
(range 2 n)))
(defn sexy-primes [m]
(for [x (range 11 (inc m))
:let [z (list (- x 6) x)]
:when (every? #(is-prime? %) z)]
z))
(let [a (System/currentTimeMillis)]
(println (sexy-primes (* 10 1000)))
(let [b (System/currentTimeMillis)]
(println (- b a) "mils")))
Clojure optimized is-prime?:
(defn ^:static is-prime? [^long n]
(loop [i (long 2)]
(if (= (rem n i) 0)
false
(if (>= (inc i) n) true (recur (inc i))))))
Python
import time as time_
def is_prime(n):
return all((n%j > 0) for j in xrange(2, n))
def primes_below(x):
return [[j-6, j] for j in xrange(9, x+1) if is_prime(j) and is_prime(j-6)]
a = int(round(time_.time() * 1000))
print(primes_below(10*1000))
b = int(round(time_.time() * 1000))
print(str((b-a)) + " mils")
Factor
MEMO:: prime? ( n -- ? )
n 1 - 2 [a,b] [ n swap mod 0 > ] all? ;
MEMO: sexyprimes ( n n -- r r )
[a,b] [ prime? ] filter [ 6 + ] map [ prime? ] filter dup [ 6 - ] map ;
5 10 1000 * sexyprimes . .
Bash(zsh):
#!/usr/bin/zsh
function prime {
for (( i = 2; i < $1; i++ )); do
if [[ $[$1%i] == 0 ]]; then
echo 1
exit
fi
done
echo 0
}
function sexy-primes {
for (( i = 9; i <= $1; i++ )); do
j=$[i-6]
if [[ $(prime $i) == 0 && $(prime $j) == 0 ]]; then
echo $j $i
fi
done
}
sexy-primes 10000
Questions
- Why Scala is so fast? Is it because of static typing? Or it is just using JVM very efficiently?
Why such a huge difference between Ruby and Python? I thought these two are not somewhat totally different. Maybe my code is wrong. Please enlighten me! Thanks.UPD Yes, that was error in my code. Python and Ruby 1.9 are pretty equal.- Really impressive jump in productivity between Ruby versions.
- Can I optimize Clojure code by adding type declarations? Will it help?
n/2to know if it's prime or not (although it probably won't make a huge difference). – Speakersqrt(n)but that can take some time to compute. Also your C code prints out the primes as it finds them, whereas your other languages compute them into lists and then prints them out. While C is unsurprisingly the fastest, you might be able to get it faster. – Exterritorialsqrt(n)? I guess that makes sense ... Awesome. I wish I could favorite that comment so I would always remember it (or at least be able to find it). I was just thinking naively which is why I saidn/2(which is just a bit-shift, so that should be fast to compute). – SpeakerC: 2.723sGo: 2.743s. – ImplacableC: 3m35.458sGo: 3m36.259s– ImplacablePHP: 1m3.766sReally slow compared to C and Go. – Implacablesqrt()is usually a well-optimized library function. I think the cost of a singlesqrt()on a single float value will be much cheaper than doing repeated modulus operations that are not needed, and the bigger the numbers being checked get, the bigger the savings. I just tried the code from my answer, and changed the check forsqrt()to justn - 1and execution time more than doubled (to 19 seconds). – Coumaronemath.primesvocabulary. It already has a very well optimizedprime?word. – Encompasssqrtfor this check. You can compute the square ofias infor (i = 2; i * i <= x; ++i) ...– MagnetronisPrimewith@tailrec, to ensure you are using tail recursion. It is easy to mistakenly do something that prevents tail recursion, and this annotation should warn you if that happens. – Alexandriaimport scala.annotation.tailrec– Hellenistic0.03seconds (30milliseconds) for100Ki.e.,500times faster than the C version above. – Cupp: Booleantype annotation from theisPrimemethod (required on recursive methods due to limitations in type inference). The call site{ _ forall isPrime }should be OK with any Scala version – Engineer@cython.locals(n=int, j=int)decorator that tells Cython about static types i.e., it is similar to optimized Clojure code in that regard (but faster). – Cupp