Groovin’ in Java

March 7, 2012

I’ve just been watching an interesting presentation on using Groovy as an additional toolkit in Java.  Groovy excels in handling XML, File I/O and JDBC, as well as offering good support for Collections and Closures (as regular readers of this blog already know!).  The type of things you typically need to do day-in-day-out for your regular job.

If you want to learn more about what you can do with Groovy in the real world take a look at the presentation on InfoQ – Improve Your Java with Groovy

The presenter, Ken Kousen, also has a good blog with some very useful information on using Groovy for doing regular & proper programming tasks – the sort of thing it’s really intended for – not what I do here!

He’s got a book in the works, Making Java Groovy, which should be coming out in late 2012.

Advertisements

I was interested to see that JetBrains, creators of the splendid IntelliJ IDEA IDE amongst other things, are working on their own “better-Java-than-Java” language, Kotlin.

Ostensibly this is to resolve some of the “issues” that the Java language has, whilst being simpler than the currently strongest competitor, Scala.  Kotlin is going to be supported as a first-class citizen in the IDEA IDE from around the end of 2011.

There’s a lot of talk on various fora about the need (or lack of) for introducing a new language when others like Scala, Groovy and Clojure are becoming more established.  This is similar to the fuss back in April 2011 when Gavin King “leaked” the news that Red Hat were working on their “Ceylon” JVM-hosted language.  The public launch of Ceylon is likely to be in the same sort of timescale.

Most of the chatter seems to be about the benefits around the features of the languages, semantic overhead of learning, efficiency of execution, dilution of Java skillsets, etc.  All are interesting and sound discussions.

What I’m not seeing is anyone saying about the pure commercial value of a company such as JetBrains or RedHat launching their languages focusing on their their own ecosystems.  I don’t believe these guys aren’t doing it for the love of the Java community. They’re doing it for cold, hard cash… any why not?

It’s interesting that JetBrains are saying that Kotlin is intended for “industrial use”.  By this I’m expecting the real value-add features (which must be compelling) to be supported in their paid-for “Ultimate” edition of IDEA rather than the free “Community” version and they’re targeting the “enterprise” market.

They would need to convince “corporate” development managers of the benefits of the Kotlin, disabuse them of the risks of selecting a single vendor language  and get it embedded into their companies order to monetise the investment in developing it.

That’s not to say they’re wrong to try – look at how successful VB6 was and that’s a single company language supported by a strong IDE!

They’ll have to be quick though.

Java 7 has just been released and Java 8 is due in late 2012.  Whilst J7 addresses quite a few “niggles” with Java (including reducing some noise around Generics and the equivalent of C#‘s “using” statement)  and add some good features into the JVM it’s not the complete “Project Coin” package.

The “big thing” being sold in all these new languages are Lambdas/Closures which won’t come until J8.  (You can see the split of features here.) This means that they’ll have 12 months to get some traction before the “official” Java language supports this.

Personally, I don’t believe that having closures in an OO imperative language is that important.  Useful, of course, but not the end of world if they’re lacking.  There didn’t seem to be much demand for them in Java before Ruby on Rails became popular in 2006 and there was an outbreak of scripting-envy across the Java community.

Of course, with the JVM bytecode instruction InvokeDynamic being added in Java 7 it means that dynamic language such as JRuby should become much more performant so, if you really want closures on the JVM why not just use that?

I think it’s disappointing that the official Java/JVM ecosystem has been on a bit of a hiatus for the last 5 years (Java 6 was released in 2006) but it’s kind of understandable given the situation with Sun and Oracle.  It’s also disappointing that Coin was split across two releases as this will delay adoption too and, in the Java world, allow third-parties to fill the perceived gap with semi-official solutions in the interim.

It will be interesting to see how this all plays out.  I do hope it doesn’t distract JetBrain or RedHat/JBoss from continuting to provide world-class platform support for the official Java stack on their products.

I’ve started putting the source for my Project Euler solutions up in a public repository on GitHub. I won’t push them up there until I’ve written a corresponding blog entry, so they’ll lag a little behind what I’m actually doing.

I’m doing this primarily so I can get some experience in using Git which is growing in popularity in the Open Source world.

My first impressions are that it’s really very good for decentralised development and having a local copy of the entire repository for the codebase means that, for offline development, it’s hard to beat. All the supporting features like tracking moved files, creating personal branches and merging changes, even to the point of selecting partial changes within a file, are very good.

However, when compared to something like Subversion, which I’ve used for the past few years, it’s not as convenient when all you want to do is checkout a single file from the shared repository, to fix a typo for instance, and commit it back. Platform tooling is also much better for Subversion due to its lengthy popularity.

Git also seems very oriented towards textual source rather being a general object versioning system. I can imagine that storing large binary files, such as graphics for a game or website, or 3rd-party compiled libraries that change regularly would cause a mammoth repository bloat and extend a new checkout time to something REALLY horrid. There seems to be some support for submodules that might alleviate this by keeping the binary elements in a separate project but it seems a bit awkward.

Horses for courses, I guess. Github is free and convenient so it’s fine for what I intend to use it for.

Read the details of the problem here

Summary

Consecutive positive divisors.

Solution

I went straight to Java for this problem. I felt that a sieve approach to count the divisors would be better than trying to actually calculate the divisors themselves for such a large range of numbers. Given past performance of Groovy when carrying out such activity I thought it would be a non-starter to use it and I couldn’t see a better algorithm.

Coding was straightforward. I used a simple optimisation to allow the outer-loop to only run to the square-root of LIMIT but nothing extraordinary.

final int LIMIT = 10000000;
int[] sieve = new int[LIMIT+1];
Arrays.fill(sieve, 2);  // don't worry about elements 0 & 1

for (int i = 2; i <= (int)Math.sqrt(LIMIT); i++) {

    int j = i * i;
    sieve[j]--;

    while (j <= LIMIT) {
        sieve[j] += 2;
        j += i;
    }
}

int answer = 0;

for (int i = 2; i < LIMIT; i++) {
    if (sieve[i] == sieve[i+1]) answer++;
}

This runs in 2.16 seconds.

Conclusion

Groovy? A simple ported implementation that doesn’t use any special features runs in 15.3 seconds. So not far out, but not quite there!

Note: After solving this and gaining access to the forum, it seems that there is a technique that solves this in an amazing 312 ms using Java, but porting this to Groovy actually takes longer, at 24.1 seconds, than the simple optimisation. I’ll do some more research into why this is because it seems like a strange pathological behaviour, maybe to do with memory management or array access patterns.

Project Euler Problem #23

February 9, 2010

Read the details of the problem here

Summary

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Solution

FAIL. Sad to say but this one defeated me – I just couldn’t get it to break the 15 second limit when using Groovy. My initial implementation used various Groovy features like adding isAbundant() and sumOfProperDivisors() methods to the Integer class and accumulating abundant numbers in lists, etc. but the runtime was 55 seconds. Gradually removing these syntactical niceties and using more inline code got me back to 21.2 seconds. I could have opted again for a multi-threaded approach similar to that which I took for Solution #14 and that would have probably got me down to below 15 seconds but I took the easy way out and ported it over to Java.

import java.util.Arrays;

final int LO_VAL = 12;
final int HI_VAL = 28123+1;

boolean[] isAbundant = new boolean[HI_VAL-LO_VAL+1];
Arrays.fill(isAbundant, false);

for (int i = LO_VAL; i <= HI_VAL-LO_VAL; i++) {
    int sum = 1;
    int sqrt = (int)Math.sqrt(i);
    for (int d = 2; d <= sqrt; d++) {
        if (i % d == 0) sum += d + i / d;
    }
    if (sqrt * sqrt == i) sum -= sqrt;
    isAbundant[i] = (sum > i);
}

boolean[] nums = new boolean[HI_VAL];
Arrays.fill(nums, false);

for (int i = LO_VAL; i < isAbundant.length; i++) {
    if (isAbundant[i]) {
        for (int j = i; j  < isAbundant.length; j++) {
            if (isAbundant[j]) {
                int sum = i + j;
                if (sum >= HI_VAL) break;
                nums[sum] = true;
            }
        }
    }
}

int answer = 0;

for (int i = 0; i < HI_VAL; i++) {
    if (!nums[i]) answer += i;
}

This code runs in 0.80 seconds. As you’d expect, the vast majority of the time is being spent in the nested loop running through the sums of abundant numbers.

Conclusion

Groovy just isn’t as performant as Java for this sort of work!

Project Euler Problem #14

January 29, 2010

Read the details of the problem here

Summary

Find the longest sequence using a starting number under one million.

Solution

This one was hard. Not so much in working out an algorithm, which is just pretty much as it says in the question, but simply in getting Groovy to execute it in under 15 seconds.

Here is my first realistic attempt; I put in a cache to store partial results, initially I had tried a dictionary/map and then a List but the performance was lousy so I reverted to using a simple array. I also tinkered with the CACHE_SIZE and found that it was pretty much optimal to have the size the same as the maximum value of i as this saved having another range validation when updating the cache.

def ( maxlen, answer ) = [ 0, 0 ]

def CACHE_SIZE = 1000000
def cache = new int[CACHE_SIZE]

for (i in 1..<1000000) {
  long n = i
  def len = 1
  while (n > 1) {
      if ((n < CACHE_SIZE) && (cache[(int)n] != 0)) {
          len += cache[(int)n] - 1
          break
      }
      n = (n % 2 == 0) ? n / 2 : (3 * n + 1)
      len++
  }
  cache[i] = len
  if (len > maxlen) ( maxlen, answer ) = [ len, i ]
}

This ran in 102.6 seconds. (The ArrayList version of the cache, defined as [0] * CACHE_SIZE had been a lot slower than the native array, taking 144 seconds.) So nowhere near the 15 second target. A bit of profiling showed that the single calculation line was taking 81% of the runtime. Talk about a hotspot!

I couldn’t see how the algorithm could be significantly changed so some micro-optimisation was in order. I’d done low-level performance programming when I used to be interested in graphics programming back in the days of 66 MHz 80486 CPUs but was hoping that today’s high-level Java compilers would remove some of that burden.

My first change was to make the maths (n % 2 == 0) statement into a logical one. I was only interested in the low-bit so I could replace it with ((n & 1) == 0). This brought the runtime down to 97.1 seconds – a saving of 5% – so not too impressive.

Next I changed the (n / 2) statement into n.intdiv(2). As n is defined as a long (and has to be as it exceeds 32-bits for some values of i) and 2 is a constant integer I figured that Groovy should be forcing integer division anyway, but I’d put it in explicitly in any case. This made a HUGE difference, bringing the runtime down to 20.3 seconds. A reduction of 79%!

So, if division was so expensive, could the same be said for multiplication? I next changed the (3 * n + 1) statement to (n + n + n + 1). This got the execution time down to 19.7 seconds – another 3% shaved off. Not much but I’ll take what I can get.

I went back to the n.intdiv(2) statement. One of the tricks when writing in assembler/C is to use a right- or left-shift to divide or multiply by two though this can have implications on the sign-bit. I thought I’d give it a go and changed n.intdiv(2) to (n >> 1). This dropped the time down to 19.3 seconds – barely a 2% saving but worth having. (I did also try the unsigned right-shift operator “>>>” but this had no material effect either way.)

I stopped and had a bit of a think about the problem. I’d reduced the maths overhead as low as I could. It was now only 33% of the runtime. How could I do less of the other 67%? It was only possible to arrive at the termination condition from an even number, a “2” (obviously). The formula used meant that any odd value of n would be changed to a non-terminal even number which would then be immediately divided by 2 on the next pass. So, could these steps be combined and reduce the runtime of the inner while-loop?

The answer was, of course, yes. With the inner-loop replaced with the code below it runs in 15.2 seconds – some 21% faster than before. Still fractionally outside my 15 second cut-off but 85% faster than my initial attempt! The Java equivalent runs in 196 ms – 77x faster – and, for what it matters, a Delphi 6 version takes a mere 117 ms.

if ((n & 1) == 0) {
    n >>= 1
    len++
}
else {
    n = (n + n + n + 1) >> 1
    len += 2
}

How about multithreading the solution? I’ve got 2 cores on my CPU – so let’s use them. Groovy makes this very easy as Closures are Runnables. I took some liberties with thread safety around the cache which the threads share for efficiency and the division of labour between threads was fairly arbitrary. I could have used a queue with the threads pulling work off as they became free, but as this was a hack anyway, these conditions sufficed for my purpose.

Here’s my final offering:

def solve14(start, end, cache, results) {

    def ( maxlen, answer ) = [ 0, 0 ]
    def cache_size = cache.size()

    for (i in start..<end) {
      long n = i
      def len = 1
      while (n > 1) {
          if ((n < cache_size) && (cache[(int)n] != 0)) {
              len += cache[(int)n] - 1
              break
          }
          if ((n & 1) == 0) {
              n >>= 1
              len++
          }
          else {
              n = (n + n + n + 1) >> 1
              len += 2
          }
      }
      cache[i] = len
      if (len > maxlen) ( maxlen, answer ) = [ len, i ]
    }
    results[maxlen] = answer
}

def results = [:] as Hashtable
def CACHE_SIZE = 1000000
def cache = new int[CACHE_SIZE]

def threads = [
    new Thread() { solve14(670000, 1000000, cache, results) },
    new Thread() { solve14(0, 670000, cache, results) }
]

for (thread in threads) {
    thread.start()
}

for (thread in threads) {
    thread.join()
}

def answer = results[results.keySet().max()]

This completes in 10.7 seconds – quite comfortably inside my, admittedly somewhat arbitrary, limit of 15 seconds! It’s marginally faster (by 1 second) to start the upper bound thread first. Although I’ve cheated by using multiple threads to get below the cut-off, it’s not a bad result given how poor initial performance was.

Conclusion

If calculation performance really is needed, then steer clear of Groovy. If you do stick to using Groovy there are a few manual tricks you can use to make it go faster as Groovy doesn’t do it for you!

I’m not going to muck about like this again for computationally intensive solutions. If Java will do the job within the timeframe then I’ll use it either in whole, or in part. After all, what’s the point of having tight Java integration if you don’t use it from time-to-time?