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!

The best way to enumerated directed acyclic graphs

Here is a tricky problem for the algorithmically oriented people to ponder about: "enumerate all directed acyclic graphs (DAGs) of a given size n".

I'll describe the process I followed in tackling this problem (the result is rather fascinating), but if you find this challenging enough, it would be good to stop reading for a while and see if you can solve it (hopefully in a good way).

First, some background. "Are you nuts? Enumerating graphs? You'll get huge numbers of them almost immediately!". Well, true. For example, here is the arithmetic sequence that shows just how many distinct (non-isomorphic) general graphs there are. It gets out of hand really quickly. Well, some background. I'm trying to develop an algorithm that takes as input a DAG, but it's quite hard to analyze and/or compare it with existing algorithms. So I'm interested in exhausting all possible inputs up to a certain size and count the logical steps of the algorithm for each problem instance, which can offer me useful feedback on the algorithm design, or show me which graphs produce the worst behavior of the algorithm, for which graphs the algorithm performs better than other algorithms, and so on.

Now, on to business. Upon some research, it seems there is no known sequence defining the number of unique DAGs per node count out there. The closest I found is the number of partially ordered sets. A partially ordered set is also a DAG, with the further restriction that its transitive reduction is itself (i.e. no redundant edges exist). Since there are many DAGs which yield the same transitively reduced DAG, it is obvious that this sequence is a strictly lower bound on the number of DAGs.

My first approach was rather brave, but futile nevertheless. I started about defining the sole graph of size 1 (no self loops), which is just a node. Then iteratively I increased the size N of generated graphs. At the iteration, the Nth node of the graphs is created and combined with all graphs of size N-1 in every possible way. How many ways are there? We are only allowed to connect the new node to the older nodes (not the other way around), so we only generated DAGs, so there are N-1 possible edges to add. The power set of this is 2^(N-1), and this is every possible way that a given graph with N-1 size can be extended with a new node.

This produced DAGs of count 2^0 (1 node), 2^1 (2 nodes)

• 2^0 = 1(one node)
• 2^1 = 2 (two nodes)
• 2^3 = 8 (three nodes)
• 2^6 = 64 (four nodes)
• 2^10 = 1024 (five nodes)
• 2^15 = 32768 (six nodes)
• 2^21 = 2097152 ( seven nodes)

The next milestone was 2^28 (268435456) graphs, but I ran out of memory. :) But storing more than two million graphs of 7 nodes and up to 21 nodes is a formidable task. I managed to pack all those graphs in about 120mb of RAM, meaning less than 60 bytes for each graph, which for a adjacency lists implementation, is pretty impressive. (But adjacency matrix where each possible edge represented as single bits would be the most economical representation). This is possible because each graph of size N shared the N-1 nodes of it, along with their adjacency lists, with the previous graph of size N-1 that it extended, so the cost of each graph is more or less the cost of the final node and its list. (This is the kind of stuff where persistent data structures really excel, but in Javaland the reusable implementations are few and far between - did I mention yet you should check out Scala?)

Then, I talked with Martin, a collegue/Phd student at the Univ. of Bath, who mostly works on NP-hard problems, and apart from a long discussion on "why one earth do you want to have a freak of nature like this one???" and other related sub-discussions, he suggested enumerating all undirected general graphs (not directed, not acyclic: this is what is offered) by nauty, and then produce all DAGs from each graph. Quite a huge amount of work: 2^(n(n-1)) number of graphs, multiplied by the number of DAGs created from each (which can be up to 2^(n-1)(n-2) / 2). But most importantly, he mentioned that nauty enumerates the graphs without having to store the smaller ones, which made me challenge my approach of generating the DAGs.

From there, it only took few seconds to bump on the correct solution, which is very simple. See the following table:

This table is meant to be a graph's adjacency matrix. The rows, as well as the columns, represent the graph's nodes. Each cell can be 0 or 1, to denote if there is a node from the row-node to the column-node, respectively. Note that the nodes of the matrix are actually in topological order (which is defined in DAGs) - a node/row is only allowed to connect to nodes after/up of it, not before/down of it - thus this matrix, the gray area are edges that if were allowed, they would violate the defined topological order. Only the white cells can contain 1, but the can also contain 0 of course. So what do we have here? For a DAG of n nodes, we have this nxn matrix, and (n-1)(n-2)/2 cells which can independently vary between 0 or 1. The solution from here is easy: Just arrange these cells as bits in a bit string, i.e. a binary number, start with zero, and increment it by one at each step, till the number consists of only 1's. Constant storage space, just a number of (n-1)(n-2)/2 bits! And a trivial way to enumerate the dags, transform the enumeration problem to the problem of...adding 1 to a binary number. All it takes is decoding the number into the respective DAG. Isn't this elegant? :)

To sum up, this procedure creates 2^((n-1)(n-2) / 2) DAGs, in equal number of iterations. Which in contrary to the suggested method, has half the exponent, i.e. for n = 10, the last method would yield 2^45 steps/DAGs, while using nauty would create 2^90 general graphs, where each graph would be subsequently transformed to many, many DAGs.

Addendum: The above description leaves a tricky part uncommented. We saw how to generate all DAGs with n nodes, i.e. :

int currentGraph = 1 << (n - 1) * (n - 2) / 2 ;

while (currentGraph >= 0) {

currentGraph--; //represents a DAG!

}

But how to interpret these numbers as graphs? We have to be able to answer, for all graphs, whether there is an edge (i --> j), i.e. connecting node i to node j. Here is the implementation of this test, by Nelly Vouzoukidou, a graduate cs student at Univ. of Crete:

boolean hasEdge(int graph, int i, int j) {
  return i > j && isSet(graph, i * (i - 1)  / 2 + j)
}

//just checks whether a given bit of a number is set
boolean isSet(int number, int bit) {
  return number & (1 << bit) & number != 0;
}

You can see the second picture to understand the bits layout that this formula represents. There is a nice geometric interpretation of it too: "i * (i - 1) / 2" is the surface of the triangle above the selected row. To that, we add "j" to go to the desired cell, since at every row, each cell represents the next bit of its left cell.

If you found this interesting, you might want to check out an older post about enumerating all binary trees, where also an amusing solution is produced.