Passing on the Duby

Last week I had a fun conversation with Charles Nutter. It was about "java.next" and in particular, Charlie's requirements for a true replacement for Java. He stated his requirements slightly before that conversation, so let me recap:

1.) Pluggable compiler
2.) No runtime library
3.) Statically typed, but with inference
4.) Clean syntax
5.) Closures

I love this list. It is a short list, but just imagine if Java 7 was even close to this. Anyways, while I like the list as a whole, I strongly objected to #2 -- No runtime library. Now, I can certainly understand Charlie's objection to a runtime library. It is a lot of baggage to drag around. All of the JVM langs have this issue. JRuby for example, has an 8 MB jar. Groovy has a 4 MB jar. Clojure has two jars totaling 4.5 MB. Scala is also around 4 MB. These become a real issue if you want to use any of these languages for something like Android development. I've written about this issue as well.

However, there is a major problem with this requirement. The building blocks of any programming language includes primitives and built-in types. Those built-in types are part of the runtime library of the language. So if your JVM based language cannot have a runtime library, then you will have to make do with primitives and Java's built-in types. Why is this so bad? Java's types (mostly) make sense in the context of Java, its design principles and syntax. I don't think they would make sense in the java.next hypothetical language described above. The easiest example of this are collection classes. Don't you want a list that can make use of closures (#5 requirement above) for things like map, reduce, filter, etc. ? Similarly, if you static typing, you probably have generics, and wouldn't you like some of your collections to be covariant? You can go even further and start talking immutability and persistent data structures, and all of the benefits these things bring to concurrent programming. This is just collections (though obviously collections are quite fundamental to any language,) but similar arguments apply to things like IO, threading, XML processing, even graphics (I'd like my buttons to work with closures for event handling thank you very much.)

One argument against this is that you can just include the runtime library of your choice. Pick your own list, hash map, thread pool, and file handler implementations. This is what I'd like to call the C++ solution -- only worse. At least in C++ you can generally count on the STL being available. The thing that is so bad about this is that it really limits the higher-order libraries that can be built. Java, Ruby, and Python all have a plethora of higher order libraries that have been built and widely used. These libraries make extensive use of the built-in types of those languages. Imagine building ORMs like Hibernate or ActiveRecord if you did not have built-in types (especially collection classes) that were consistent with the language. You could not do it. If all you could rely on was the Java built-in types, then at best your libraries would have a very Java-ish feel to them, and doesn't that defeat the purpose?

Charlie gave an alternative to this -- leverage the compiler plugins. Now it is certainly true that with a pluggable compiler, you could do this like add a map method to the java.util.List interface, and all of the JDK classes that implement this interface. It can be done. However, if you are going to build higher order libraries on top of this language, then you need to be able to count on these enhancements being present. In other words, the compiler plugin needs to be a required part of the compiler. Fine. Now what is it that we were trying to avoid? Extra runtime baggage, right? Well if you have a compiler that is going to enhance a large number of the classes in the JDK, hello baggage. Maybe it won't be as much baggage as 4 MB runtime library, but it might not be a lot less either. Also, it raises the potential problem of interoperability with existing Java libraries. If I import a Hibernate jar that gives me a java.util.List, that list is not going to be enhanced by my compiler -- because it wasn't compiled with my javac.next, it was compiled with javac.old. What's going to happen here?

Now there is an obvious happy way to deal with the runtime library question: rt.jar. If java.next was Java, and the super revamped collections, IO, threading, etc. classes were part of the JDK, then there is no need for a runtime library since now it has been included with the JDK. However, given the incredibly uncertain state of Java 7, not to mention the long term prospects of Java, does this seem remotely possible to anyone? I don't think so. I think the heir apparent to Java cannot be Java, and I think because of that, it's gotta have a runtime library of its own.

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;
    }
}

JRuby 1.1.3 Performance

It's been awhile since I did a post with pretty graphs and meaningless micro-benchmarks. I am using the latest version of JRuby, 1.1.3 on a new project. I knew from some correspondence with Charlie Nutter that the performance bug that I had encountered previously were believed to be solved. I said believed because he had not had a chance to test on the IBM J9 JVM that (along with some other JVMs) exhibited the performance problem. Actually this was fixed in 1.1.2, and I should have tested things then, but didn't get around to it until now. I decided to throw in the latest beta of JDK 1.6 update 10, the magical JDK for The Rest of Us. Here is the purrty chart:


The good news is that even with the J9 JVM, JRuby outperforms native Ruby, at least on this mathematical algorithm. This was not the case prior, so the JRuby fixes have really helped. In fact, if I look at the last data point (x=100), the code executed in less than half the time it took previously with the only change being the JRuby 1.1.3 instead of 1.1. I could describe the source of the bug, but you are much better off reading Charlie's description.