JavaOne Talk: Performance Comparisons of Dynamic Languages on the Java Virtual Machine

Below are the sldies. Major thanks to Charlie Nutter for great feedback and advice on the Ruby code and tuning JRuby performance. Thanks to Chouser and Timothy Pratley for help with the Clojure code. And major thanks to Brian Frank for help with the Fan code.

Performance Comparisons of Dynamic Languages on the Java Virtual Machine

View more PDF documents from michael.galpin.

JavaOne Talk: Scala Reversible Numbers

See this post about why this code is being shown. See this post for the Java version to compare against.

class ScalaReversible(max:Int){
  import java.lang.Character._
  lazy val numReversible = (11 to max).filter(reversible(_)).size
  private
  def reverse(n:Int)=n + parseInt(n.toString.reverse)
  def allOdd(n:Int) = n.toString.map(digit(_,10)).forall(_ % 2 == 1)
  def reversible(n:Int) = allOdd(reverse(n))
}

JavaOne Talk: Python Reversible Numbers

See this post about why this code is being shown. See this post for the Java version to compare against.

class PyReversible(object):
    __slots__ = ['max','numReversible']

    def __init__(self, max):
        self.max = max
        self.numReversible = self.countReversible()

    def countReversible(self):
        return  len([i for i in xrange(11,self.max+1) if self.reversible(i)])

    def allOdd(self,n):
        for ch in str(n):
            if int(ch) % 2 != 1:
                return False
        return True

    def reverse(self,n):
        return n + int(str(n)[::-1])

    def reversible(self,n):
        return self.allOdd(self.reverse(n))

JavaOne Talk: Ruby Reversible Numbers

See this post about why this code is being shown. See this post for the Java version to compare against.

class RubyReversible
  def initialize(max)
    @max = max
    @numReversible = nil
  end

  def allOdd(n)
    digits = n.to_s.split(//)
    digits.length == digits.map{|c| c.to_i}.select{|i| 
        i % 2 == 1}.length
  end

  def reverse(n)
    n + n.to_s.reverse.to_i
  end

  def reversible(n)
    allOdd(reverse(n))
  end

  def countReversible()
    @numReversible ||= (11..@max).select{|i| 
        reversible(i)}.length
    @numReversible 
  end
end

JavaOne Talk: Groovy Reversible Numbers

See this post about why this code is being shown. See this post for the Java version to compare against.

public class GroovyReversible {
  final Integer max
  final Integer numReversible = 0
  public GroovyReversible(max){
    this.max = max
    this.numReversible = this.countReversible()
  }

  def countReversible(){
    numReversible ?: (11..max).findAll{reversible(it)}.size()
  }

  def reversible(n){
    allOdd(reverse(n))
  }

  def allOdd(n){
    n.toString().toList().collect {it.toInteger()}.every{it % 2 == 1}
  }

  def reverse(n){
    n + n.toString().toList().reverse().join().toInteger()
  }
}

JavaOne Talk: Reversible Numbers

See this post about why this code is being shown. This is a different algorithm, it is a brute force solution to Project Euler problem #145. Here is the Java "reference" implementation.

public class Reversible {
    final int max;
    final int numReversible;

    public Reversible(int max){
        this.max = max;
        this.numReversible = this.countReversible();
    }

    private int countReversible(){
        if (numReversible > 0){
            return numReversible;
        }
        int cnt = 0;
        for (int i=11;i<=max;i++){
            if (reversible(i)) {
                cnt++;
            }
        }
        return cnt;
    }

    private boolean reversible(int n){
        return allOdd(reverse(n));
    }

    private boolean allOdd(int n){
        while (n > 0){
            int remainder = n % 2;
            if (remainder == 0) return false;
            n = n / 10;
        }
        return true;
    }
    
    private int reverse(Integer n){
        char[] digits = n.toString().toCharArray();
        char[] rev = new char[digits.length];
        for (int i=digits.length-1;i>=0;i--){
            rev[i] = digits[digits.length -i-1];
        }
        return n + Integer.parseInt(String.valueOf(rev));
    }
}

JavaOne Talk: Scala Word Sort

See this post about why this code is being shown. See this post for the Java version to compare against.

class ScalaWordSort(fileName:String){
  lazy val sortedWords = {
    Source.fromFile(dataFile).getLines.foreach(_.split(" ").foreach(words ::= _))
    words.sort(_.toLowerCase < _.toLowerCase)
  }
  private
  val dataFile = new File(fileName)
  var words:List[String] = Nil
}

JavaOne Talk: Python Word Sort

See this post about why this code is being shown. See this post for the Java version to compare against.

class PyWordSort(object):
    def __init__(self, fileName):
        print "init " + fileName
        self.dataFile = open(fileName)
        self.words = []
    def sortedWords(self):
        if len(self.words) == 0:
            for line in self.dataFile:
                for word in line.split():
                    self.words.append(word)
            self.words.sort(lambda w,w1: cmp(w.lower(), w1.lower()))
        return self.words

JavaOne Talk: Ruby Word Sort

See this post about why this code is being shown. See this post for the Java version to compare against.

class RubyWordSort
  def initialize(fileName)
    @dataFile = File.new(fileName)
    @words = Array.new
  end
  def sortedWorts
    if (@words.length == 0)
      @dataFile.each_line{ |line| line.split(' ').each{ |word| @words << word}}
      @words = @words.sort{ |w,w1| w.upcase <=> w1.upcase }
    end
    @words
  end
end

JavaOne Talk: Groovy Word Sort

See this post about why this code is being shown. See this post for the Java version to compare against.

public class GroovyWordSort {
  File dataFile
  List words = []
  public GroovyWordSort(fileName){
    dataFile = new File(fileName)
  }

  def sortedWords(){
    if (!words){
      dataFile.eachLine{it.tokenize().each {words.add(it) }}
      words = words.sort{w,w1 -> w.toLowerCase() <=> w1.toLowerCase()}
    }
    words
  }
}

JavaOne Talk: Word Sort

See this post about why this code is being shown. This is a different algorithm than the previous examples, so once again I will start with the Java version. The program takes a file name, and reads the file into memory. The file contains a list of randomly generated words, separated by spaces. The program does a case-insensitive sort of all of the words. Here is the Java "reference" implementation:

import java.io.*;
import java.util.*;

public class WordSort {
    private final File dataFile;
    private final List<String> words;
    public WordSort(String fileName){
        dataFile = new File(fileName);
        words = new ArrayList<String>();
    }

    public List<String> getSortedWords(){
        if (words.size() > 0){
            return words;
        }
        try {
            BufferedReader reader = new BufferedReader(new FileReader(dataFile));
            try{
                String line;
                while ( (line = reader.readLine()) != null){
                    for (String string : line.split(" ")){
                        words.add(string);
                    }
                }
            } finally {
                reader.close();
            }
            Collections.sort(words, new Comparator<String>(){
                public int compare(String s, String s1) {
                    return s.toLowerCase().compareTo(s1.toLowerCase());
                }
            });
            return words;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
}

JavaOne Talk: Fan Prime Sieve

See this post for an explanation on why this code is being shown and what kind of responses would be useful. See this post for the Java algorithm to compare against.

Note: This solution is courtesy of Mr. Fan himself, Brian Frank. Thanks Brian!

class Primes {
  Int[] primes := Int[,]
  Int size

  new make(Int n) {
    size = n
    primes.capacity = n
    init
  }

  private Void init() {
    i := 2
    max := calcSize
    nums := Bool[,]
    nums.fill(true, max)
    while (i < max && primes.size < size) {
      p := i
      if (nums[i])
      {
        primes.add(p)
        j := 2*p;
        while (j < max - p) {
          nums[j] = false
          j += p;
        }
      }
      i += 1;
    }
  }

   Int last() { primes.last }

   private Int calcSize() {
     max := 2
     while ((max.toFloat/max.toFloat.log).toInt < size && max < 0x7fff_ffff && max > 0) {
        max *=2; // memory inefficient, but fast
     }
     return max;
  }
}

JavaOne Talk: Scala Prime Sieve

See this post for an explanation on why this code is being shown and what kind of responses would be useful. See this post for the Java algorithm to compare against.

import java.lang.Integer._
import java.lang.Math._
import scala.collection.mutable.ArrayBuffer

class ScalaPrimes(val size:Int){
  val primes = new ArrayBuffer[Int]
  var cnt = 0
  init
  def last = primes(primes.size - 1)

  private
  def init {
    var i = 2
    val max = calcSize
    val nums = new ArrayBuffer[Boolean]
    for (i<-0 until max) nums += true
    while (i < max && cnt < size){
      val p = i
      if (nums(i)){
        primes += p
        cnt += 1
        (p until max/p).foreach((j) => nums.update(p*j,false))
      }
      i += 1
    }
  }
  def calcSize = {
    var max = 2
    while ( (max/log(max)) < size && max < MAX_VALUE && max > 0) {
      max *= 2
    }
    max
  }
}

JavaOne Talk: Python Prime Sieve

See this post for an explanation on why this code is being shown and what kind of responses would be useful. See this post for the Java algorithm to compare against.

from math import log
import sys

class PyPrimes(object):
    __slots__ = ['cnt','primes','size']

    def __init__(self,n):
        self.primes = n*[0]
        self.cnt = 0
        self.size = n
        i = 2
        max = self.calcSize()
        nums = max*[True]
        while i < max and self.cnt < self.size:
            p = i
            if nums[i]:
                self.primes[self.cnt] = p
                self.cnt += 1
                for j in xrange(p, max/p):
                    nums[p*j] = False
            i+= 1

    def calcSize(self):
        max = 2
        while max/log(max) < self.size:
            max = max *2 # this makes the sieve too big, but fast
        return max

    def last(self):
        return self.primes[self.cnt - 1]

JavaOne Talk: Ruby Prime Sieve

See this post for an explanation on why this code is being shown and what kind of responses would be useful. See this post for the Java algorithm to compare against.

class RubyPrimes
  attr_accessor :cnt, :primes
  def initialize(n)
    @primes = Array.new(n,0)
    @cnt = 0
    i = 2
    max = calcSize
    nums = Array.new(max,true)
    while (i < max && @cnt < @primes.length)
      p = i
      if (nums[i])
        @primes[@cnt] = p
        @cnt += 1
        (p .. (max/p)).each{ |j| nums[p*j] = false }
      end
      i += 1
    end
  end
  def calcSize
    max = 2
    max = max * 2 while ( max/Math.log(max) < @primes.length)
    max
  end
  def last
    @primes[@cnt -1]
  end
end

JavaOne Talk: Groovy Prime Sieve

See this post for an explanation on why this code is being shown and what kind of responses would be useful. See this post for the Java algorithm to compare against.

public class GroovyPrimes {
  int cnt = 0
  final def primes = []
  final int size

  public GroovyPrimes(int n){
    size = n
    init()
  }

  int last() {
    primes[cnt-1]
  }
  
  private void init(){
    int i = 2
    int max = calcSize()
    def nums = [true]*max
    
    while (i < max && primes.size() < size) {
      int p = i
      if (nums[i]) {
        primes << p
        (p..(max/p)).each{ j-> if (p*j < max) nums[p*j] = false}
      }
      i += 1
    }
  }

  private int calcSize(){
    int max = 2
    while ((max / Math.log(max)) < size && 
        max < Integer.MAX_VALUE && max > 0) {
      max *= 2
    }
    max
  }
}

JavaOne Talk: Being Less Efficient

See previous post if you have not already. I was getting ready to post some of implementations of the prime sieve in other languages, when I realized I had probably unfairly over-optimized the Java solution by using arrays. This kind of optimization is available in some languages, but not others. So it would be hard to do a fair comparison if this optimization was used at all. So here is the Java prime sieve, but using resizable lists instead of primitive arrays:

import java.util.List;
import java.util.ArrayList;

public class Primes {
    final private List<Integer> primes;
    private final int size;
    
    public Primes(int n){
        size = n;
        primes = new ArrayList<Integer>(n);
        init();
    }

    private void init(){
        int i=2;
        int max = calcSize();
        List<Boolean> nums = 
            new ArrayList<Boolean>(max);
        for (int j=0;j<max;j++){
            nums.add(true);
        }
        while (i < max && primes.size() < size){
            int p = i;
            if (nums.get(i)){
                primes.add(p);
                int j = 2*p;
                while (j < max - p){
                    nums.set(j,false);
                    j += p;
                }
            }
            i += 1;
        }
    }

    public int last(){
        return primes.get(primes.size()-1);
    }

    private int calcSize(){
        int max = 2;
        while ((max/Math.log(max)) < size && 
            max < Integer.MAX_VALUE && max > 0){
            max *=2;
        }
        return max;
    }
}

JavaOne Talk: Prime Sieve

Next month I am speaking at JavaOne on the performance of various programming languages running on the JVM. For the talk, I am taking several algorithm/programming problems solved in each of the various languages, and comparing the relative performance and tuning tips. For each problem, I am using "native Java" as a reference point. This is the first of many blog posts that show these various programming problems solved in the various languages. I am posting these programs as a way for other folks to let me know where I've screwed up, i.e. done something that will negatively affect performance, etc.

I am not too interested in significantly different ways to solve these problems. For example, the first algorithm is a prime sieve. So I would not be interested in somebody letting me know that there are other ways to generate primes besides a sieve. However, I am interested in finding mistakes in my implementations. I will not claim to be an expert in any of these languages -- in fact I have been learning two of the languages, Fan and Clojure, specifically for this talk -- so there is a good chance that I did screw something up. Even in the languages that I'd like to think I am pretty good at (including Java), I figure there is always a good chance of me doing something screwy there too. So without further ado, here is my prime sieve in Java.

import java.util.Arrays;

// calculates the first n primes
public class Primes {
    final private int[] primes;
    private int cnt = 0;
    
    public Primes(int n){
        primes = new int[n];
        init();
    }

    private void init(){
        int i=2;
        int max = calcSize();
        boolean[] nums = new boolean[max];
        Arrays.fill(nums, true);
        while (i < max && cnt < primes.length){
            int p = i;
            if (nums[i]){
                // add it to the list of primes
                primes[cnt++] = p;
                int j = 2*p;
                // remove all the multiples of the prime
                while (j < max - p){
                    nums[j] = false;
                    j += p;
                }
            }
            i += 1;
        }
    }

    public int last(){
        return primes[cnt-1];
    }

    // calculates number of integers needed to find n primes
    private int calcSize(){
        int max = 2;
        while ((max/Math.log(max)) < primes.length && max < Integer.MAX_VALUE && max > 0){
            max *=2; // memory inefficient, but fast
        }
        return max;
    }
}

JavaFX Performance

Recently I did a comparison of JavaFX performance vs. Scala. I did this mostly for kicks, and because some people thought that Mr. JavaFX was picking on other, non-Java languages that run on the VM. James Iry duly pointed out that JavaFX should be benchmarked against the likes of Ruby, Groovy, or Scala. It is meant to be a client-side technology, so it should go up against client-side technologies. So I re-did the little performance comparison to match JavaFX against JavaScript, ActionScript (Flash), and C# (Silverlight).

A comparison like this really becomes a comparison of Virtual Machines. For JavaScript there are a lot of choices. I decided to go with some that are supposed to be fast: Google Chrome, Firefox 3.1 (beta 2), and Safari 4 (developer preview.) Because I wanted Chrome involved, I had to go Windows. So I ran everything under Windows XP, running under Parallels on my MacBook. Here is the pretty graph:

I was just a little surprised by these results. JavaFX is indeed the fastest, but just barely. I was somewhat shocked to see Chrome's V8 JS engine right behind. In fact the difference is negligible for small iterations (shown above.) At larger iterations, JavaFX maintained 20-40% margin. As you can see from the graph, Flash and Silverlight were kneck-and-kneck as well, but was always about 7-10x slower than Chrome/JavaFX. Safari and Firefox were very underwhelming.

Of course this was just a micro-benchmark. The code just does a series of recursive calls. So what were are really measuring is the ability of the VMs to unwind these recursive calls. It is not suprising that HotSpot handles this easily. Actually, the same code in straight Java is much faster than the JavaFX version. It is surprising to see how well V8 handles this.

Now does the ability to unwind recursion translate into performance that a web application user would notice? Maybe. It certainly points to JavaFX's or V8's ability to make optimizations to application code. It is probably a more meaningful test than some raw number crunching.

JavaFX vs. Scala

Chris Oliver post a nice little performance comparison of JavaFX vs. Groovy and JRuby. He concluded that JavaFX was 25x faster than these other two languages running on the JVM. Of course I had to see how this compared to Scala. First here's the direct translation to Scala I did of the code:

object Tak{
 def tak(x:Int, y:Int,z:Int):Int = if (y >= x) z else tak(tak(x-1, y, z),tak(y-1, z, x),tak(z-1, x, y))
 def main(args:Array[String]) = {
  0 until 1000 foreach ((i) => tak(24,16,8)) 
 }
}

Here are the results for JavaFX on my MacBook:

$ time javafx -server -cp . tak

real 0m12.847s
user 0m11.926s
sys 0m0.338s

So my system is a little slower than Chris Oliver's. That's why I had to run his bench on my MacBook first, to make a fair comparison to the Scala version. Here are those results.

$ time scala Tak

real 0m9.690s
user 0m9.122s
sys 0m0.261s

Scala not only beat out JavaFX on my system, but was also faster than JavaFX running on Chris Oliver's faster system. The guys at Sun should have never let Odersky go!