Traits defining equals, combined with case classes

I just contributed a "common programming mistake for Scala developers", in the relevant thread over at stackoverflow (which seems to be turning into a mania, given I contributed quite valuable time myself without really thinking about it). It describes a pitfall from the interplay of case classes, traits and equality defined in the latter - by no means this can be really a "common" mistake, but it is not obvious enough so some help to keep it uncommon doesn't hurt.

Thoughts on Actors

This discussion (started today) on the scala mailing list relates to understanding the usefulness of Akka, and more generally, actors.

Somebody suggested comparing using actors to using locks directly. The following are my comments, intially meant as a response, but I ended summarizing many of my current concerns/questions regarding the actor programming model.

This contrast between actors and low-level concurrent programming (e.g. locks) is misleading. It's not like that there are actors, then a huge void, and then locks, where we get to choose an extreme. There are tons of things in-between. For example, message passing in a single VM is trivial to implement on top of BlockingQueues (or, soon, TransferQueues). There already exists the executor framework, and the fork/join framework, to provide thread pools and fine-grained parallelism.

My take is that actors provide a simplified, more elegant programming model than using the underlying tools directly. At their core, typical actors are a Runnable accompanied with a BlockingQueue (mailbox), while reactors are event listeners. A strong point of actors, as the Haller/Odersky paper shows, is that they unify thread-based and event-based models - one can use and combine either under the same framework. This programming model is still young and requires exploration to find its best use cases and fully appreciate it. As much as anything, this too needs an "Effective Actors" type of book. It is easy to go wrong too, especially for beginners trying to wrap their heads around MPI-like programming. Deadlocks are still possible (actors waiting forever for messages that will not come), race conditions are still possible (an actor giving up on waiting a reply, right before the actual reply arrives), it's not like the usual suspects of concurrent programming have magically vanished. (Edit: Probably I'm wrong to classify the last case as a race condition, it's likely just a data race, following the nomeclature of JCiP).

Moreover, the simplification has its cost too - it's not easy, at least for me, to reason about performance implications. For example, assuming scala actors that depend on ForkJoinScheduler (i.e. using the fork/join framework), this quotation from the javadocs of ForkJoinPool is interesting:

A ForkJoinPool may be constructed with a given parallelism level (target pool size), which it attempts to maintain by dynamically adding, suspending, or resuming threads, even if some tasks are waiting to join others. However, no such adjustments are performed in the face of blocked IO or other unmanaged synchronization.

This leads to some obvious questions which I can't answer easily at all:

1. What are the (performance) implications of using (blocking) IO in actors? (I haven't seen similar warnings given to actors users).
2. Noting that tasks are never joined, all receive() blocking calls fall under "unmanaged synchronization" as per the javadoc, so what are the implications of this fact?

So, simplification also seems to come at the cost of hiding possible important optimizations, like having a thread that needs to block in order to join() subtasks, to go and execute other tasks while waiting (via helpJoin()).

I'm not sure what the conclusion should be. Hopefully in 3-4 years collective experience will be substantial and we will better understand how these shiny new tools are best used, and when the underlying concurrency utilities should be used instead. Personally, as of now, while I am eager to experiment with actors, I feel more at home with more low-level tools, so I can more easily reason about the performance characteristics of my code. Hopefully someone will submit to the task of writing a good scala actors book - current books are OK, but Scala is new, so they are devoted to Scala mostly, and perhaps have a chapter on actors, which is too little to go anywhere beyond the very basics.

Barbara Liskov talk and vintage photo

Few days earlier I was happy to see this talk given by Barbara Liskov:

http://www.infoq.com/presentations/liskov-power-of-abstraction

Few days earlier I submitted a paper to ESWC10 ( found here , titled "Flexible Ranking and Matchmaking for Semantic Service Discovery"), which happened to include a reference to Liskov and her well known substitution principle (the bottom side of the 3rd page).

It was not a big deal, just "common sense" reiterated. As you will notice from the talk above, though, at the 70ies this kind of "common sense" we take for granted today, was debatable and unclear then -- just as debatable was whether the goto statement was evil or not!

One thing that impressed me most in that talk was a photo that Barbara shared with the audience, from the 70ies. I had never saw her young!

I will leave the photo uncommented - it speaks for itself. -edit: well, I commented it after all, see below :)

Beware of recursive set union building!

The excellent Google collections library spoils many of us, but that doesn't mean we can afford not being alert using it!

Observe how easy it is, for example, to create the (live) union of two sets: Sets.union(setA, setB).

One might be tempted to write code like the following, to make the union of all sets in "S":

Set<E> union = Collections.emptySet();
 for (Set<E> someSet : S) {
   union = Sets.union(someSet, union)
}

Wow! This build the union in just O(|S|) time! Sure enough, accessing the elements of the union is a different issue, but how slow could it be? (Note that we do pass the smallest union as first argument, in agreement with what javadocs suggest).

Well, it turns out, this is quite slow. Iterating over the elements of the union take O(N|S|), which for really small sets can be up to O(N^2), where N is the number of all elements of the union. In comparison, creating a single HashSet and calling addAll() to add each set in S to that, takes only O(N) time.

To understand the issue, consider the algorithm for computing the elements of the union of sets A and B:

report all elements in A
for all items x in A
 if !b.contains(x)
   report x

Now consider this union: union(A, union(B, union(C, D))), graphically shown below.

This is how the union's iterator would report its elements:

1) Iterate and report all elements of A

2) Iterate elements of B, if they are not in A, report them

3) Iterate elements in C, if they are not in B, then if they are not in A, report them

4) Iterate elements in D, if they are not in C, then if they are not in B, then if they are not in A, report them

See the pattern there? Well, that's it. Just resist the temptation to make a recursive union, that's all. (I haven't looked the matter deeply, but I think this shouldn't be affecting recursive intersection or recursive difference).

So, in this case, creating a big HashSet and dumping all elements in it is the way to go. It is a bit of a pity that a HashSet is really a HashMap in disguise, i.e. horribly wasteful (compared to what a genuine HashSet implementation should be), but that's life in Java :)

Till next time,

Bye bye!

Using JConsole to monitor...JConsole

I was in the mood for some recursive monitoring, so I fired up a JConsole process and ordered it to monitor itself. I managed to make it show the stack trace of the thread that had the task to show the stack trace of the thread that had the....... you get the idea :)

For what it worths, here is the stack trace:

sun.tools.jconsole.Worker.add(Worker.java:56)
sun.tools.jconsole.Tab.workerAdd(Tab.java:73)
  - locked sun.tools.jconsole.ThreadTab@c829e3
sun.tools.jconsole.ThreadTab.valueChanged(ThreadTab.java:316)
javax.swing.JList.fireSelectionValueChanged(JList.java:1765)
javax.swing.JList$ListSelectionHandler.valueChanged(JList.java:1779)
javax.swing.DefaultListSelectionModel.fireValueChanged(DefaultListSelectionModel.java:167)
javax.swing.DefaultListSelectionModel.fireValueChanged(DefaultListSelectionModel.java:137)
javax.swing.DefaultListSelectionModel.setValueIsAdjusting(DefaultListSelectionModel.java:668)
javax.swing.JList.setValueIsAdjusting(JList.java:2110)
javax.swing.plaf.basic.BasicListUI$Handler.mouseReleased(BasicListUI.java:2788)
java.awt.AWTEventMulticaster.mouseReleased(AWTEventMulticaster.java:273)
java.awt.Component.processMouseEvent(Component.java:6263)
javax.swing.JComponent.processMouseEvent(JComponent.java:3267)
java.awt.Component.processEvent(Component.java:6028)

I'm monitoring a process that should take about 2 hours, so yes, I do have a lot of time in my hands :)

Rapidshare can compress any file to just 16 bytes!!!

Or so it claims:

there is a program which calculates the MD5 checksum for each file immediately after the upload. The MD5 checksum is a 16 bytes value which is alsways the same when calculated for the same file. This value is stored in connection with the file. If you upload and distribute an illegal file, we will delete the file upon notification and add the MD5 checksum to a blacklist, so the same file cannot be uploaded again.

(Emphasis mine).

Now, I really, really, really want to see their blacklist implementation, since obviously it holds the key to the dark art of infinite compression, which is the Holy Grail Of Computer Science, the Universe, and Everything. Yes, the notorious Holy Grail that nobody wants to touch because apparently it's the favorite pooping place for some very special pigeons...

JComboBox pure craziness

Someone asked me why his ItemListener, attached to a JComboBox, was getting two events when he selected something on it. Weird.

I looked up JComboBox' javadocs, just to be sured, and....this is what I found:

Adds an ItemListener.

aListener will receive one or two ItemEvents when the selected item changes.

I understand Swing is a huge framework and it has its rough edges...but this? It certainly looks like someone couldn't fix this strange behavior, and desided to make it a documented feature instead. Way to go!