about:random

Haskell Interval Maps

2012-01-02T06:29:00.000-08:00

I just released my first package on Hackage: a library similar to Data.Map, but taking intervals as keys and allowing efficient search for all keys containing a point or contained in an interval, for example.

I needed a data structure - in Java - to search in a set of overlapping appointments, that is, intervals of timestamps. I found nothing suitable on the web, and so I started to implement it on my own. Wikipedia yielded augmented search trees as the basic idea. I often use Haskell for prototyping stuff I'll eventually have to implement in Java, C, or whatever.

After that I had a leftover Haskell implementation, and thought that completing it might be a good project to get a bit more into Haskell again. I've been following Haskell for a long time (since before there were type classes, actually), but never used it for larger projects, and I've not kept up with recent developments.

I used How to Write a Haskell Program as a guideline.

The first thing to do was to implement a reasonably full-featured interface. Data.Map was the obvious guideline to use, and I was dismayed by the number of functions it offers. It really seems a bit too rich. It's certainly nice to have all these functions, but on the other hand the pure mass of them also makes it harder to use the library (now, which function should I use...) and to read code using it. In the end I did implement most of them, but it was really a tough decision not to go for a leaner interface.

Next step was going for better test coverage. QuickCheck is great, so that did not take too long (but my test code looks ugly and could use some refactoring). What did take much longer was fixing the bugs this uncovered, especially in the delete... functions.

Next was the standard Haskell build system: cabal. This also took some time. Despite the good user manual, I still had trouble with many aspects. For starts: which version of base do I need? To my surprise, I did not find reasonable documentation about this anywhere. Integrating the tests was also a bit tricky.

I also wrote some performance tests using criterion, but found that the results are very unreliable on my system. But at least I was able to see that the performance was reasonably close to Data.Map for the basic functions, and that fromDistinctAscList seemed indeed to be linear.

Here's the projects home page: http://www.chr-breitkopf.de/comp/IntervalMap/
Hackage: http://hackage.haskell.org/package/IntervalMap-0.2.0

Bitten by Implicits

2011-09-28T01:05:00.000-07:00

I just wasted half a day tracking down a NullPointerException in a mixed Scala/Java project.

The original problem was a NPE iterating through a list returned by a java method:

    import scala.collection.JavaConversions._

    for (x <- javaMethod())
       ...

I found the reason quickly enough: the java method was still null-infected - it returned null instead of the empty list when no results were found.
I was in a bit of a hurry, so instead of refactoring the Java method, I went though a helper:

for (x <- fixNull(javaMethod()))
       ...

    def fixNull(xs: Iterable[String]): Iterable[String] = {
        if (xs == null) Nil else xs
    }

To my utter astonishment, this did not fix the NPE. The reason is probably obvious to more seasoned scala programmers, but took me quite some time to see. Actually, after some futile debugging experiments, I just gave up and went home. Quite typically, the critical insight came 5 minutes after leaving the office. Work is just not conductive to creative thinking :-)

Actually, this is a type problem. javaMethod returns a java.util.List[String], but fixNulls wants a Scala Iterable. So the Scala compiler inserts an implict conversion from JavaConversions. Unfortunately, the conversion wraps a returned null into an object, so xs == null always returns false!

Changing the argument type fixes the problem:

    def fixNull(xs: java.util.List[String]): Iterable[String] = ...

I think that this would have been easier to find if the JavaConversions wrappers would throw a NPE when asked to wrap a null. Then the problem would have been obvious from the stack trace.

For me, that is another example why having "invisible" things in your code is problematic. Scala implicits can be extremely helpful, but you must be aware of them when debugging.

Of course, the best solution is to refactor the Java code to return an empty list instead of null.

A short-lived misfortune

2011-08-08T06:30:00.000-07:00

Last night, there was break-in into my employers offices, and some notebooks were stolen, among them my Lemote Yeeloong.

When the police arrived, they mentioned that some notebooks had been found in a garbage can at a nearby kebab place. They even had a list of models and serial numbers.

Given that the Lemote is more of a curiosity here in Germany, it was fairly obvious that it was mine even without checking the serial number. I was directed to the appropriate police office, just a few hundred meters away.
After a short wait, and signing a receipt, I had my notebook back. The battery was empty, but otherwise, not a scratch (and, thankfully, no kebab).

All in all, it took just about 3 hours from the discovery of the theft, to having the notebook back on my desk. The was some luck involved, but still, I was quite impressed by the effectiveness of the police.

ICFP Programming Contest 2011

2011-06-19T17:29:00.000-07:00

Whew! Finally over. I liked the task, because of much prior experience with lambda calculus and SK combinators (but not MTG). That didn't help much though - I did not find a way to compose functions until a few hours ago. By then I was too tired to try and implement it. More detailed write-up soon.

Ok, here it goes:

The contest started at 2:00 in the night, so I decided get a decent sleep and looked at the task only some 6 hours after the start. I liked the task at first sight: lambda calculus and combinators! Cool card images, too.

To be able react to the game state during play, it was necessary to implement the game mechanics, so I wrote a straightforward implementation in Haskell. For the logic, I first wrote code to generate a number in a given slot, using the zero, succ, and dbl cards. For a start into strategy, I used that to decrement the opponents slot with the lowest vitality. Obviously not a winning strategy, but I wasn't ready to tackle help and attack yet.

Before the submission to the unofficial tournament server, I dutifully tested the executable on my Debian Squeeze VM. It did not run, because of shared library problems. So I tried static linking, but to my surprise discovered that ghc does not support that on Linux :-( So I had to compile on the Debian VM. A bit of a hassle, but not that bad.

I submitted my server, and soon got some "submission failed" problems. Not too many - about one failure every few games. Some of those were due to timeouts, so I did some code tuning. I also noted a problem with the zero card not being converted to a number in some places (0-ary functions are bad), and fixed those, too.

After that, I was quite optimistic that my submission would work. But no such luck - I still got "invalid format" errors. Lacking a more informative error message, at this point I could only review all pattern matches that ended with a _ -> error ("can't happen") clause, but I did not find the cause of the problem.

Now, the best resource would probably have been to try harder to reproduce the bug, but what I did instead (out of desperation, really) was to re-implement my player in another language: C. This did not take long, and I actually discovered the mistakes in the Haskell version while coding. As it turns out, being mentally in "pure mode", I had not faithfully implemented the order of side-effects resulting from the call-by-value evaluation. Also, there was a problem in my implementation of the help and attack cards, where I would produce an error if the j parameter was not a valid slot number too early, without first decrementing the vitality of slot i. While I thought that the actual game logic would be easier to implement in Haskell, the core of the C version looked much cleaner at that point, so I continued developing that version. It worked without problems on the first attempt. Another nice thing was that I could submit statically linked executables directly from my 32-bit desktop system instead of having to use the 64-bit VM on my notebook. Nicer for my eyes and back, that is. Even though I allocated memory for some applications, I did not release it, figuring that 500M go a long way (with a value struct being 12 bytes in size in 32-bit mode). I could always use the Boehm GC if necessary.

At that point is was Saturday evening, and I had made no progress toward a good game strategy. So I finally sat down with pen and paper, and tried to drag up my old SKI and lambda-calculus knowledge. That used to be quite good - I still have a toy functional language implemented by combinator reduction lying around, and once knew S, K, I and friends (B, C, B', C' and so on) by heart. But, as more than one contest participant has noticed, doing the implementation first and the creative "brain-work" later in the contest is often the wrong order - by the time you've finished the necessary groundwork and maybe a few tools, you're likely out of sleep and not in the best frame of mind for creative thinking.

I was stumped for a long time trying to find a general way to compose functions. That I solved a few hours before the contest's end (using slot 0 and K _, S _, _ get, _ zero).

As for strategy, it seemed obvious, that one should use help to build up vitality and use that to attack the opponent. I did not manage to implement such a scheme in the remaining time.

My submission.

After the contest

Given that I had prior experience with combinators, I was quite frustrated at my bad performance. In retrospect, what has held me up most was, I think, that the contest theme got me in a pure functional mindset, and I mostly blanked out the side-effects arising from call-by-value semantics. Combinators just scream "lazy" and "pure" to me, which caused my mind to ignore the glaringly obvious possibility of executing several vitality-affecting operations in one action (simple example: _ inc, S _, _ inc, _ zero). That, together with get to make copies for later use, would have got me in the right direction for a better result. That still would not have been a top result, as I doubt that I would have figured out how to use zombie effectively, but it would have been into the "ok" instead of "also running" category. The same problem, thinking pure, was also responsible for the bugs in my earlier Haskell implementation. So getting that right from the start would have saved me at least 12 hours of debugging and the C implementation, too.

I also completely ignored the approach NOT to do a simulation. Thus, I missed implementing some simple players that would later have helped me to debug my non-working implementation. In particular, the echo player, the random Player are absurdly easy to implement and might have helped in debugging. Also, writing and evaluating a few functions by hand might have gotten me around my mental "only one side-effect per action" block.

But as usual, I had much fun and greatly enjoyed the contest. Many thank to the organizers for the interesting task! I'm looking forward to see all the cool strategies the top contestants are sure to have devised. In particular, I'm curious what really can be done with zombie.

Lemote Yeelong Benchmarks

2011-05-24T08:39:00.000-07:00

A few weeks ago, I got my Lemote Yeeloong netbook. After a veritable odyssey of OS upgrades / rescues and reinstallations, caused by stupidity (mine), unfamiliarity with Debian, and unstable to non-existent connectivity to the Chinese download sites, I was finally able to run some benchmarks.

According to the Loongson 2F website, the CPU should "Outperform 1GHz Pentium III".

I do not have access to a 1GHz PIII, so I used an Asus EeePc 701 for comparison. It has an Intel Celeron-M ULV 353 underclocked to 630 MHz. Taking these SuperPI benchmark results, which are probably best case for frequency scaling, would place the CPUs about equal (Pentium III 1 GHz at 130 sec., and Celeron-M 630 MHz at 126 sec.)

System comparison:

System	CPU	MHz	L2 Cache	Memory	OS
Lemote Yeeloong 8089	Loongson 2F	800	512 KB	1 GB	Fedora 13
EeePc 701	Celeron-M ULV 353	630	512 KB	2 GB	Scientific Linux 6

I used Fedora instead of Debian on the Lemote because it uses the MIPS n32 ABI, for potentially much better performance.

Stream TRIAD bandwidth

Stream results are rather bad:

System	TRIAD MB/sec
Yeeloong	601
EeePc	1220

bzip2 compression

As an integer benchmark, I used bzip2 to decompress and compress the gcc 4.6.0 source tarball (71,579,535 bytes). Time is user time in seconds.

System	Decompress	Compress	bzip2 version
Yeeloong	145.69	767.74	from OS
Yeeloong	140.90	521.15	bzip 1.0.6, compiled with gcc 4.6.0 with default optimization
EeePc	114.09	507.09	from OS

Radiance rendering

Using Mark Stock's benchmark test. Unfortunately, on the Yeeloong, -O3 -ffast-math delivered invalid results, so I had to compile with the flags listed below. I'll try to rerun this with a newer version of gcc, as this gives a big improvement on some platforms (AMD64, for example, but not on the Celeron-M).

System	User time	Compiler	Flags
Yeeloong	17915	gcc 4.4.4	-march=native -O3 -fno-math-errno -funsafe-math-optimizations
EeePc	15884	gcc 4.7.0 20110501	-march=native -Ofast

Hint

The systems are almost identical at about 67 MQuips, but, as indicated by the Stream result, the Loongson is hampered by bad main memory and, apparently, L2 cache, performance.

Updates:
2011-05-25 updated bzip2 results

Which JVM for Scala?

2011-05-03T07:27:00.000-07:00

After noticing that Scala programs usually run much faster with the HotSpot server VM than with the client VM, I wanted to test a few more VMs and options.

I used a single small Scala program for testing: a variation of the n-Queens puzzle. You can download source and jars here. Scala version was 2.8.1.final.

The program was run with default VM options, except for -client / -server (-Xem:client / -Xem:server for harmony), e.g.:

    jvm\bin\java -server -cp scala-library.jar;Queens.jar Queens

The test were run on a Core 2 Duo E8500 (3.16GHz, 6MB L2) in Windows XP 32-Bit. The runtime is the best time of the three 12 Queens runs, in seconds.

opt	default	JVM
1.32	1.79	java7-server	Java HotSpot(TM) Server VM (build 21.0-b10, mixed mode)
1.37	1.83	hotspot-server	Java HotSpot(TM) Server VM (build 20.0-b11, mixed mode)
1.95	2.04	jrockit-client	Oracle JRockit(R) (build R28.1.3-11-141760-1.6.0_24-20110301-1429-windows-ia32, compiled mode)
2.24	2.25	jrockit-server	Oracle JRockit(R) (build R28.1.3-11-141760-1.6.0_24-20110301-1429-windows-ia32, compiled mode)
6.89	6.59	java7-client	Java HotSpot(TM) Client VM (build 21.0-b10, mixed mode, sharing)
6.91	7.34	hotspot-client	Java HotSpot(TM) Client VM (build 20.0-b11, mixed mode, sharing)
86.64	crashed	harmony-server	Apache Harmony DRLVM (1.6.0-r991881)
92.50	90.60	harmony-client	Apache Harmony DRLVM (1.6.0-r991881)

So, for best performance, stay with the HotSpot VM, and always use -server. You probably need to install a full JDK for this - the JRE only includes the client VM.

Using the -optimize flag when compiling seems to be a win, too, but I would try it on a few more programs before relying on it.

Scala and Java

2011-04-28T08:38:00.000-07:00

I finally decided to write a new module for an existing Java application in Scala.

There were several reasons to use Scala instead of Java:

Coding speed because of much shorter code.
The only way to really learn a language is to use it for a real project
I was bored and looking for some excitement :-)

The time that I could pick up a new language just by reading a book seem to be gone. I think (hope!) that the reason is not age or lack of focus, but rather that the languages have changed. Say, for example, that you know Java and want to learn C#. That should be fairly simple - both are object-oriented languages with very similar syntax and semantics. Actually, even a relatively simple OO language is much more complex than, say, Pascal. Scala is harder, especially if you've never done functional programming, but still, the language is the smaller problem. The big problem are ever-growing libraries and frameworks. You need to become familiar with at least part of this for any real program. And the libraries are often less well designed and coherent than the language.

For me, the downsides of using Scala are mostly in the development environment. I use Eclipse for Java development and am very happy with it. Not so much when writing new code - I can do that just fine in Emacs or even a simple text editor. It's when maintaining and extending a larger codebase written by multiple developers where the features of a good IDE - for example type-based autocompletion, hovering to see Javadoc comments, or refactoring - really pay off.

The sad fact is that I could not get the Scala IDE for Eclipse to work. I tried on two different systems, even on a older Galileo Eclipse, but to no avail. Sometimes just adding the Scala nature would completely break a java project. And often Eclipse will just hang. And even if it sort of works, no refactorings, not even rename!

So I wrote the new module as a separate Scala-only project using Emacs with scala-mode and ENSIME. This worked reasonably well.

After finishing the first version, I asked myself this question: "Are there just a few features that Java would need so I would not be tempted to use Scala instead?".

My first (probably obvious) answer: "Closures".

Being able to write

    gotIt = aList.exists(x => x.isFoo && !x.isBar && x.baz == myBaz)

instead of

    gotIt = existsFoo(aList, myBaz);
    ...
    private static boolean existsFoo(Iterable<Thingy> xs, Thingy y) {
        for (Thingy x : xs) {
            if (x.isFoo() && !x.isBar() && x.getBaz().equals(y))
                return true;
        }
        return false;
    }

or, using Guava

    gotIt = Iterables.any(aList, new Predicate<Thingy>() {
                                      public boolean apply(Thingy x) {
                                          return x.isFoo() && !x.isBar() && x.getBaz().equals(myBaz);
                                      }
                                 });

is a huge win.

In Java with JSR 335 this would look like this (assuming type inference for the lambda argument):

    gotIt = Iterable.any(aList, #{ x -> x.isFoo() && !x.isBar() && x.getBaz().equals(myBaz) });

Of course, Scala has a lot more to offer than just closures. I also used implicits to implement wrappers for so number-like classes, so I can write

    if (c < a + b) ...

instead of

    if (c.compareTo(a.add(b)) < 0) ...

List comprehensions (for) also came in handy, as well as pattern matching. Currying, together with closures makes for unobtrusive and readable resource cleanup (or closing HTML tags, in my case):

    log.in("Foo") {
      ...
    }

instead of

    log.openTag("Foo");
    try {
        ...
    } finally {
        log.closeTag("Foo");
    }

All in all, I probably would not have used Scala if Java had only closures. But I'm not sorry I did. The code is much shorter and nicer to read than a Java version could ever be.

Beach after Storm

2011-02-12T04:21:00.000-08:00

Name my Class, please

2011-01-28T01:10:00.000-08:00

The bug was hard to reproduce. At least it was obvious that it was a deadlock issue, because the Oracle said so: ORA-00060: deadlock detected while waiting for resource

Of course, the customers had access to multiprocessor machines earlier than we developers did. So we could not reproduce the problem in-house.

Once we had access to multiprocessor-machines, we still were not able to reproduce the problem. But later, as cores became more abundant, and with real customer data, it would sometimes happen.

The root cause of the problem was parallel execution of transactions that did a mixture of updates and inserts on the same table and possible the same primary key.

To prevent this error, two approaches seemed possible to me:

Switch Oracle to Serializable isolation level and retry the transactions in case of Cannot serialize access errors.
Never execute transactions affecting the same primary key in parallel.

The latter approach seemed to offer higher performance (which was, after all, the reason to go parallel in the first place), because it would also reduce index block contention.

So what I did was implement a variant of ExecutorService that is given a function to extract a key from a Callable<?>> object on construction. It behaves like a fixed thread pool, with the additional constraint that it will never run tasks with the same key in parallel.

That was easy enough to implement, at least given my modest scalability requirements, and the rather coarse-grained tasks. It would probably take rather more time to implement an industrial strength version that would also offer high performance on very fine-grained tasks and implement the full ExecutorService interface.

But anyway, it solved the problem, so I'm quite satisfied with this solution. The only problem is that I've not been able to come up with a good name. It is currently called LimitedThreadPool. RestrictedThreadPool was also an option. Both of these names suggest that the class is a kind of thread pool that is somehow limited or restricted. But the exact way in which it is restricted - never running certain tasks with the same key in parallel - is not expressed at all. KeySerializedThreadPool or PartlySerializedThreadPool seem to go in the right direction, but I can't say that I'm really satisfied with either of them.

So, if anyone can come up with a better name, please let me know!

Cache sizes visible in JavaScript?

2011-01-18T06:27:00.000-08:00

Given the recent advances in JavaScript engines, I wanted to know whether cache effects come into play. So I wrote a simple memory benchmark. Results look interesting at first:

From this graph you might guess that my system has 64K L1, 512K L2, and 6M L3 cache. Which turns out to be correct (Phenom X6).

So the memory hierarchy is visible, but if you look at the absolute numbers (GB/sec), you see that there is less than 10 % difference between L1 cache and main memory. Plotting the results against the same benchmark written in Java makes this obvious:

Of course, JavaScript is much harder to optimize than Java. It has only heterogeneous arrays of values, and only one number type.

At the moment, it seems that you can safely ignore locality in JavaScript. The effect is there, but so small as to be irrelevant, even in the fastest JavaScript implementations.

Bugs: Let's call it a day

2010-12-13T03:36:00.000-08:00

A customer reported a bug: Printing a certain report would sometimes crash. Of course, we could not reproduce it, not even in the customers own environment. The stack trace was not helpful, either. A conversion from string to number failed, but we could not see how the string could contain an invalid format. It took some time digging around the code to find the problem in a module of utility functions.

Today, learning a new programming language is usually not that difficult. It's quite likely that you've already seen most of the concepts in a language you know. The trouble is in the libraries and frameworks. Just knowing whether a certain function might be provided by a library is not easy. Really getting to know a framework and the way it's supposed to be used can really take some time.

Our outsourcing partner in Asia had only done Java projects so far, and our VB 6 to VB.NET port was their first .NET project. So it's not surprising that the .NET framework was not as fully used as possible.

In the case of the bug mentioned above, during development we had reported that the program did not work in Germany because the localized decimal separator was not used. Obviously, the framework just has to have some way to access this, but the programmer was not aware of this, had trouble specifying the right search terms, or whatever. So instead of just using

  CultureInfo.CurrentCulture.NumberFormat.CurrencyDecimalSeparator

he or she implemented this wierd solution:

  If Date.Now.ToString("dddd").Contains("tag") Then
     sep = ","
  Else
     sep = "."
  End If

The programmer must have snarfed up enough German somewhere to think that German weekday names all end with "tag". As soon as we saw this code, we set the system date to a Wednesday ("Mittwoch" in German), and promptly could reproduce the bug.

Bokeh in the Mainstream

2010-08-23T02:24:00.000-07:00

Only a few years ago, using the term "Bokeh" would get you questioning looks from most photographers. This has changed by now. Not only do most photographers know what bokeh means - it's even arrived in the marketing departments. The announcement of the new version of the Nikkor 1.4/85, is a good example: Bokeh is mentioned not only in side-notes, but features prominently in several places.

Of course, whenever marketing's involved, there is the possibility that it's only marketing, and there's no way to know if good bokeh was in the actual lens designers requirements. We'll have to see whether the lens delivers that promise, and in particular, if it is as good or even better than its immediate predecessor.

Scala Microbenchmarks

2010-08-10T10:19:00.000-07:00

I did some microbenchmarks of scala loops using caliper. The goal was to find out just how high the penalty for using higher level constructs vs imperative-style loops is. Of course, all the usual caveats about microbenchmarks do apply, so take the results with a bag of salt.

The microbenchmark I used was counting odd numbers in an array of integers. The array was initialized with ascending numbers starting from 0, that is, numbers(i) = i.

The different ways to count:

Method	Description	code snippet
WhileBits	while loop with bitwise op	while (i < n) { count += (numbers(i) & 1) i += 1 }
WhileIf	while loop with conditional	while (i < n) { if ((numbers(i) & 1) != 0) { count += 1 } i += 1 }
ForeachBits	iterator	for (i <- numbers) { count += (i & 1) }
Count	count method	numbers.count((n) => (n & 1) != 0)
Filter	filter and length	numbers.filter((n) => (n & 1) != 0).length
MapSum	map and sum using foldLeft	numbers.map((n) => n & 1).foldLeft(0){(a,b) => a+b}

Here are the results. Scala version was 2.8.0.final. The VM used was Sun HotSpot 1.6.0_20, running on Windows XP 32-bit on a Core 2 8500. Times are in microseconds, but the exact times are not that important - what matters is the relative speed.

Method	client vm	server vm
WhileBits	1.92	1.20
WhileIf	2.54	2.66
ForeachBits	29.14	14.71
Count	36.96	24.23
Filter	50.02	24.70
MapSum	97.18	39.95

Using the scalac -optimise flag does almost nothing for this code (actually, it makes it a bit slower, but not that much).

My conclusions:

For inner loops with arithmetic, using low-level code may be a good idea.
The performance of the iterator (ForeachBits) is especially disappointing. I would have expected this to be as fast as the while loop. But scalac -print shows that no kind of optimization or inlining is done.
Use the server VM, if you can. Typically, this does more for Scala than for Java code. Corollary: Scala performance will be especially bad on simple VMs (Android, for example).

Website Monitoring

2010-07-27T06:08:00.000-07:00

I recently discovered by accident that a simple Ajax app on my website did not work any more. Bugs happen, I fixed the bug, and everything's ok again.

Or is it?

The problematic words above are "by accident". If I hadn't decided to see how the site looks on my Android phone, I might not have discovered this at all.

The problem was that the webservice was running under PHP 4 instead of PHP 5, due to a missing .htaccess file. I did not find out how I deleted that file, but using old access logs, I found out when: 8 months ago!

But, why didn't the users complain? In this case, the app hardly had any users, which explains why I did not get any emails about the site not working. But relying on your users is of dubious value at best - most won't take the trouble to email you and will just go elsewhere.

So, this was a lesson for me: if you care about your websites, you have to monitor them on a regular basis.

Now the questions is: how? I firmly believe in the rule "If you really want something done, you have to automate it". So far, my monitoring was "look at the logs from time to time" (once per week or less often). I probably would have noticed a major problem on a more popular page, such as bokeh.de this way, the chance for seeing the problem in the little-used MapExplorer was close to zero. And even if I'd seen it, that still would have been after a week or more of downtime.

For this particular problem, the webservice itself could have reported it, if it had better error handling - an exception like the missing (in PHP 4) json_encode function clearly justifies sending a notification mail, or at least logging a fatal error somewhere. So good error handling is a necessity, too, but I'll never catch all possible problems, and, more important, it does not handle the case that my provider has an outage or something like that.

I think that a good solution would be to use a tool like webtest to write automated test for the sites, run that as a daily cron job, and send mail if something breaks.

I wonder how other people monitor their sites, especially if there is dynamic content or Ajax apps. Are there any easier ways to do this?

ICFP Contest 2010

2010-06-21T01:07:00.000-07:00

The contest started on 14:00 local time.

First thing to do was getting the specifications for factory circuits. There were two aspects: gate function, and circuit logic (what does "backwards" mean?).

I submitted three trivial factories (1 and 2 gates only) to get their output, and then did a brute force search for the gate logic and input stream.

This was quite unsuccessful, because I started off with the "obvious" definition of backwards (topological ordering starting from X gate).

Finally was frustrated enough to look for some hints on the web, and found another definition of backwards (by gate number), that I would never have considered. (Is that cheating? I'm divided on that - hints like that would have been dropped on the official IRC channels or mailing lists of previous contests, too. The post that mentioned gate order actually also contained the gate logic, but I decided not to use that.)

With the correct definition of "backwards", finding the gate logic and input took about 1 hour of brute-force search.

That was my only real achievement in this contest, because after that I was stumped. I never found a way to construct circuits by hand.

So again the only thing to try was exhaustive search, and I found the smallest circuit (6 gates) that would yield the key prefix after some hours. By then it was Sunday afternoon.

I did not try very hard to solve the next riddle - car and fuel encoding - the parser error messages were not helpful, and nothing obvious came to mind. So I did not submit any cars or fuel for other cars.

Given that I did not get to the main part of the task at all, it's hard to make a final conclusion about this years contest. I sucked at it, obviously, but that's nothing new. What turned me off a bit is that the "riddles" at the start (circuit/gate semantics and car/fuel encoding) did seem to require a certain amount of lucky guessing - at least, I'm not aware of a purely systematic way to solve them.

Why I haven't learned to love Scala yet

2010-06-18T03:26:00.000-07:00

Scala should be my favorite programming language. It's a natural - everything important fits:

Functional: can program in functional style without jumping through any hoops
Static typing: powerful type system with just enough automatic inference to not get into the way
going non-functional for IO, efficiency, or logging/tracing is easy
runs on JVM
closely integrated with Java - use all those libraries I may not love but know
performance is usually good enough

So why don't I get that warm fuzzy feeling when reading or writing Scala code? I've tried more than usual for a new language. I even bought the book: Programming in Scala.

There are probably some more intangible features that don't match my preferences:

syntax seems complicated and sometimes wierd
multiparadigm - there's always more than one way to do it (TMTOWTDI)
and, of course: a language with built-in XML support can't be up to no good ;-)

You might ask why I'm looking for a new language.

It's mostly a dissatisfaction with Haskell, my "official" favorite language - that is, until I try to write a real program in it. Then I switch to a "work" language most of the time. If you spend 40 hours per week hacking in you not-so-favorite language A and and at most 2 hours in your favorite language B, it's highly likely that you'll be more productive in A, just because of great familiarity with the language and its libraries. It especially hurts when something that is easy in A seems harder and longer-winded in B.

So I often prototype things in Haskell, and write simple scripts, too, but as soon as there's more IO, a database, or even (horror) a GUI, it's back to Java or C. A Haskell program that has the IO monad in every nook and cranny does not feel that elegant to me any more. Maybe I'm just too inexperienced to properly encapsulate side effects, but sometimes the choice between pure and impure seems very hard, especially when I just want to add some logging or something comparable. Also, the Haskell libraries seem continually in a state of flux, and the library docs is much worse than for many other languages.

So there that's the reason for my search: I want my "must have" features (static typing, functional style) and some "nice to haves" (JVM, stable library) in a language I can use for real projects.

I hope my current dissatisfaction will vanish when I get more familiar with Scala - some things, especially syntax, you just have to get used to. TMTOWTDI can be fixed by adopting a programming style and some patterns, and sticking to it.

In a few hours, the ICPF programming context 2010 starts. Unless it's clearly a complete mismatch for the task, I'll use Scala this year.

Android Performance

2010-06-14T03:52:00.000-07:00

I recently got a Motorola Milestone (aka Droid), and I'm testing whether it's fast enough for a straight port of MapExplorer.

On the slowest PC I have available (a first-generation EeePc 701 - Intel Celeron-M ULV 353 underclocked to 630 MHz), with the HotSpot Client VM, LoS computation takes 1 - 2 seconds on average.

For integer code, the Milestone's CPU (TI OMAP3430 ARM Cortex A8 running at 550 Mhz) should at least be in the same ballpark as the Celeron, even though it's in-order. For FP, I don't even have a clue. It could be anywhere from about as fast to 20 times slower.

So I wrote a small wrapper app containing just the LoS computation with results written to a text view. I didn't have the patience to do a full-map benchmark run yet, but LoS computation seems to take from 15 to 30 seconds. More than an order of magnitude slower than the Celeron, and probably a bit too slow for practical use.

On the other hand, it's also not that slow that it forces a different approach like using precomputed LoS. Newer phones have faster CPUs and then there's Android 2.2 (Froyo) which has a JIT that presumably speeds up CPU-intensive code (including floating-point) by at least a factor of two. Combined, that would result in times below 10 seconds.

Unfortunately, I can't test whether the JIT will speed up the LoS computation using the SDK, because it emulates a CPU without hardware FP support, where the JIT won't have any effect.

Given that I have limited time to work on this, performance seems promising enough to prefer a straight port. While the features of the online computation as opposed to precomputed LoS, namely being able to modify the map on the fly, are probably rarely used, switching to precomputed would still require some more work (checksums for maps, how to handle used-supplied maps).

Even with the JIT, the Dalvik VM will remain far behind HotSpot or optimizing compiler performance for some time. For example, there's usually no difference between using getters/setters and direct field access in HotSpot, but a factor of 7 in Froyo. Actually, I have to admit that I sort of like the current situation. I'm a coder at heart, and performance tuning is a really gratifying excercise (especially if it works). When was the last time you actually gained performance by doing CSE by hand? In Android, that's the thing to do in tight loops.

Trouble with True

2010-06-08T09:14:00.000-07:00

But let your communication be, Yea, yea; Nay, nay: for whatsoever is more than these cometh of evil.
Matthew 5,37

Could there be anything more basic and obvious to a computer programmer that the data type of truth values, commonly known as boolean? With just two values, it's not only much easier that, say integers, but it also is the foundation for the most basic of control structures. It's even in the bible (the one cited above, not TAOCP).

So, constructs like this

  if (logging == true) {
     log.info("I said so!");
  }

or this

  if (<condition>) {
    var = true;
  } else {
    var = false;
  }

always leave my quite irritated. What's going on here? Why was it written this way?

In the first example, assuming it's Java, there's nothing operationally wrong with the code. In Java, comparing to true is the identity operation on booleans, so adding it it does not hurt. What irks me is that I have no idea what brings a programmer to writing it this way - I always have the disturbing feeling that the programmer who writes this way may not really have understood about booleans.

I'm always tempted to suggest either adding a few more "== true" to be really sure not to accidentally miss a true value:

  if ((((logging == true) == true) == true) == true) {
    ...
  }

or to also add a few identity operations to other data types - if it's good for booleans, it can't hurt doing it for int, no?

  for (i = 0 + 0; i + 0 < n; i = i + 0 + 1) {
    ...
  }

For some reason, no one is willing to do that.

What makes the example really irritating is that there are many languages, for example C, Lisp, or VB6, where comparing to true is not the identity operation on booleans, because in these languages there are many values that are regarded as true in the if statement. The constant true equals only one of these values. So, if the code above were not Java but C, what was the intention of the programmer? Did he really want to compare the variable to only one specific true value, and treat others as false? Or did he know that in this case the variable can only have the values true and false? Or is the code simply wrong?

In the second example there is no problem with correctness. It's only the style that's completely hilarious. Why is the expression not assigned directly?

  var = <condition>;

My feeling is that there is a tendency not to view boolean as a "first class type" like numbers. It is viewed as somehow "special" and some programmers are unsure just where a boolean variable or expression may be used. I've actually spoken to people who think the direct assignment above just looks unnatural, and who find the version with if to be more readable. How can that be?

Maybe it's just that numbers are much deeper ingrained. A multiplication table, even only for the natural numbers from 1 to 10, is much larger than the table for the boolean functions, but most of us learned the multiplication table in elementary school, but the boolean functions much later, if at all.

Still this spells trouble for the trend to more functional and expression-based languages. If even boolean is hard to grasp as a first class type, what about higher-order functions and other things decidedly more complex than that?