tag:blogger.com,1999:blog-69581260659768022922024-03-12T17:15:27.986-07:00Code-o-maticThe programming blog of Dimitris AndreouAnonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.comBlogger32125tag:blogger.com,1999:blog-6958126065976802292.post-84904960345174559822012-02-05T21:13:00.000-08:002012-02-05T22:49:25.960-08:00Updated: Memory cost per Java/Guava structure (+Cache)I just updated the <a href="http://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures?ts=1328503747&updated=ElementCostInDataStructures"><b>ElementCostInDataStructures</b></a> page, after 6 months, bringing it in line with the latest Guava version (11).<br />
<br />
The most interesting part is just how easy it is to measure the cost per entry in a <a href="http://docs.guava-libraries.googlecode.com/git-history/v11.0.1/javadoc/com/google/common/cache/Cache.html">Cache</a> (or <a href="http://docs.guava-libraries.googlecode.com/git-history/v11.0.1/javadoc/com/google/common/cache/LoadingCache.html">LoadingCache</a>, which turns out to be equivalent). This is the cheat-sheet I compiled.<br />
<br />
<span style="font-size: large;">To compute the cost of a single (key, value) entry:</span><br />
<ul>
<li>If you use <b>HashMap</b> or <b>ConcurrentHashMap</b>, the cost is <b>8 words (32 bytes)</b></li>
<li>If you <b>switch to </b><a href="http://docs.guava-libraries.googlecode.com/git-history/v11.0.1/javadoc/com/google/common/cache/Cache.html">Cache</a>/<a href="http://docs.guava-libraries.googlecode.com/git-history/v11.0.1/javadoc/com/google/common/cache/LoadingCache.html">LoadingCache</a>, the cost is <b>12 words (48 bytes)</b></li>
<li>If you <b><a href="http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/cache/CacheBuilder.html#expireAfterAccess(long, java.util.concurrent.TimeUnit)">add expiration</a></b> of either kind (or both), <b>add 4 words (16 bytes)</b></li>
<li>If you use <b><a href="http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/cache/CacheBuilder.html">maximumSize()</a></b>, <b>add</b> <b>4 words (16 bytes)</b></li>
<li>If you use <b><a href="http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/cache/CacheBuilder.html#weakKeys()">weakKeys()</a></b>, <b>add 4 words (16 bytes)</b></li>
<li>If you use <a href="http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/cache/CacheBuilder.html#weakValues()"><b>weakValues()</b></a> or <a href="http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/cache/CacheBuilder.html#softValues()"><b>softValues()</b></a>, <b>add 4 words (16 bytes)</b></li>
</ul>
<div>
<b><br /></b></div>
<div>
So, consider this example from the javadoc:</div>
<div>
<br /></div>
<div>
<pre style="background-color: white;"> <code>LoadingCache<key, graph=""> graphs = CacheBuilder.newBuilder()
.maximumSize(10000)
.expireAfterWrite(10, TimeUnit.MINUTES)
.removalListener(MY_LISTENER)
.build(
new CacheLoader<key, graph="">() {
public Graph load(Key key) throws AnyException {
return createExpensiveGraph(key);
}
});</key,></key,></code></pre>
<pre style="background-color: white;"><code>
</code></pre>
The cost of an Entry in this structure this is computed as follows:</div>
<div>
<ul>
<li>It's a Cache: <b>+12 words</b></li>
<li>It uses maximumSize(): <b>+4 words</b></li>
<li>It uses expiration: <b>+4 words</b></li>
</ul>
<div>
Thus, each (key, value) entry would have a footprint of <b>20 words</b> (thus 80 bytes in a 32bit VM, or 160 in a 64bit one). </div>
</div>
<div>
<br /></div>
<div>
To estimate the overhead imposed in the garbage collector, one could count how many references (pointers) each entry introduces, which the garbage collector would have to traverse to compute object reachability. The same list again, this time only counting references:</div>
<div>
<br /></div>
<div>
<ul>
<li>If you use <b>HashMap</b> or <b>ConcurrentHashMap</b>, the cost is <b>5 references</b></li>
<li>If you <b>switch to </b><a href="http://docs.guava-libraries.googlecode.com/git-history/v11.0.1/javadoc/com/google/common/cache/Cache.html">Cache</a>/<a href="http://docs.guava-libraries.googlecode.com/git-history/v11.0.1/javadoc/com/google/common/cache/LoadingCache.html">LoadingCache</a>, the cost is <b>6 references</b></li>
<li>If you <b><a href="http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/cache/CacheBuilder.html#expireAfterAccess(long, java.util.concurrent.TimeUnit)">add expiration</a></b> of either kind (or both), <b>add 2 references</b></li>
<li>If you use <b><a href="http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/cache/CacheBuilder.html">maximumSize()</a></b>, <b>add</b> <b>2 references</b></li>
<li>If you use <b><a href="http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/cache/CacheBuilder.html#weakKeys()">weakKeys()</a></b>, <b>add 3 references</b></li>
<li>If you use <a href="http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/cache/CacheBuilder.html#weakValues()"><b>weakValues()</b></a> or <a href="http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/cache/CacheBuilder.html#softValues()"><b>softValues()</b></a>, <b>add 4 references</b></li>
</ul>
<div>
Thus, for example, if you use all features together (expiration, maximumSize(), weakKeys(), and weak or soft values), then each entry introduces 6+2+2+3+4 = <b>17 references</b>. If you have 1000 entries in this cache, that would imply 17,000 references.</div>
</div>
<div>
<br /></div>
<div>
A simple advice to close this post: since these numbers can quickly add up, be sure to use only those features that your application needs. Don't overdo it just because these features are easily accessible - if you can practically get away with fewer features, do so, and you'll get a leaner cache.<br />
<br />
That said, I'm positively surprised with the Cache implementation - that you pay exactly for what you use, and that the cost various combinations of features is simply <b>the sum</b> of the cost of the individual features. This is not obvious, not given, and not an accident, but good engineering. </div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com2tag:blogger.com,1999:blog-6958126065976802292.post-48176557222947620752011-08-11T19:56:00.001-07:002011-08-11T19:56:41.931-07:00Few words on false sharing of cache lines<span class="Apple-style-span" style="background-color: white; font-family: Arial, sans-serif; font-size: 13px; line-height: 18px;">Spent some quality time reading the native code behind java.lang.Object, particularly checking how synchronization is implemented (really complicated code, and critically important for the whole platform as you can imagine).<br />
<br />
It is implemented like this (ton of details left out): of the 8 bytes of the object, 4 of them, if the object is used as a lock, are interpreted as a pointer to some ObjectMonitor, basically a queue of waiting threads. The implied CAS operation associated with entering or exiting a synchronized block is targetted (unless I misread it), to a word _inside_ the bytes of the Object, not the linked structure. This basically means that if you have an "locks" Object[8] array (initialized with "new Object()" in a loop), and you grab lock[3] from one thread, and lock[7] from another, these are likely to interfere with one another (CASes on the same cache line, one succeeding may spuriously cause the other to fail and retry). ReentrantLock is less susceptible to this problem, since it weighs at 40 bytes instead of 8, but still. All of this is fixable through padding.<br />
<br />
This is not to imply that only CAS operations on nearby locations are a problem; even plain writes/reads of nearby memory locations from different threads will cause false cache sharing and increased cache coherency traffic. </span>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com0tag:blogger.com,1999:blog-6958126065976802292.post-63277673029719439882011-03-28T14:02:00.000-07:002011-03-28T14:02:01.793-07:00James Gosling at Google!Woohoo! James just joined Google!! Finally!Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com0tag:blogger.com,1999:blog-6958126065976802292.post-3953487910252006582011-01-18T00:13:00.000-08:002011-02-02T09:12:14.810-08:00A note on API Design - call-stack as the source of a pervasive dualityI'll talk about few simple, often overlooked, yet pervasive and important, aspects of API design. They come by many names and many forms; if you have written code of any length, you have already faced at some level what I'm going to discuss. Long story short: almost any non-trivial API can be meaningfully designed in two, in some sense dual ways. Don't pick randomly. If your library is popular and frequently used, this matter has profound importance: chances are that users will press for an implementation of the dual, no matter which way you chose to offer - not always realizing that what they asked for is already implemented, just turned "inside out". If you don't realize this duality, you risk mindlessly duplicating lots of things, without realizing it, increasing the entropy of your library.<br />
<br />
So my bet is that if you are doing API design, you are probably interested. (<b>Edit:</b> if you want to understand actors, you might also be interested!)<br />
<br />
This is certainly not just a theoretical issue. Some well known manifestations of the phenomenon in the real world:<br />
<ul><li>The introduction of <a href="http://stax.codehaus.org/Home">StAX</a>, while <a href="http://sax.sourceforge.net/">SAX</a> was there</li>
<li>The many requests (or cries) for having Collection#forEach() kind of methods, to complement the #iterator()-based approach (<a href="http://gafter.blogspot.com/2007/07/internal-versus-external-iterators.html">related post by Neal Gafter</a>)</li>
<li>Scala collections, which offer both iteration styles (passing a callback, or getting an iterator)</li>
<li>Servlets (which are callbacks) vs <a href="http://rifers.org/">RIFE</a> framework (recall their motto, "do scanf() over the web?" - they perceived that in this way the brought the "simplicity of console applications programming to the web".)</li>
<li>Callbacks, continuations, python's nifty "yield" (generators), trampolines, all come from the some place as well.</li>
</ul><br />
And that place is the good old call-stack.<br />
<br />
Some (very) basic concepts up-front, to make sure we are on the same page. By "API", we usually refer to the layer through which user code and library code communicates. In Java, that is methods and the types they are defined in. Communication between these two parties (in either direction) typically happens by invoking methods: user code invoking library code, or the inverse (after the user code hands some callbacks to the library code, of course, since the library doesn't know its users). Method invocation occurs in a thread. The caller's stackframe issues the invocation to the callee, which pushes the callee's stackframe on the call-stack. Since it is a stack, the caller's stackframe (i.e., local variables + program counter) outlives the one of the callee. Trivial fact, but not trivial consequences.<br />
<br />
Now, consider any two state machines that need to work together. When you are using an iterator, you are interacting with a state machine. When you pass callbacks to a parser, you interact with a state machine. Your program is a state machine, anything you invoke is also one - but we will concern ourselves with non-trivial state machines - even a pure function is a state machine, but it has only a single, unchanging state.<br />
<br />
Since we are talking about API design, say one state machine is provided as a "library", and the other is "user code", communicating through some API (I only need to address the case of *two* state-machines; for more, you can recursively apply the same arguments). To make it concrete, lets use as an example these very simple state machines:<br />
<ul><li>A state machine that remembers/reports the maximum element it has seen</li>
<li>A state machine that produces a set of elements</li>
</ul>And we want to combine them together so we compute the maximum element of a set.<br />
<br />
In a single thread's call-stack, one of these must be deeper in the stack than the other, thus there are only two different configurations to arrange this interaction. One must play the role of the caller (for lack of a better name, I'll call this role <b>active</b>, because it is the one that initiates the invocations to the second), the other must play the role of the callee (<b>passive</b> - it reacts to invocations by the active one). The messaging works as follows: The caller (active) passes a message by <i>invoking</i>, the callee (passive) answers by <i>returning</i> (and it has to return, if the computation ever halts).<br />
<br />
Lets see the two arrangements of the the aforementioned state machines, in very simplified code:<br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b>//library - active</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">static int findMax(Iterator<integer> integers) {</integer></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> int max = Integer.MIN_VALUE; <b>// <-- call-stack encoded state</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> while (integers.hasNext()) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> max = Math.max(max, integers.next());</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return max;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b>//user code - passive</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">class ValuesFromAnArray implements Iterator<integer> {</integer></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> private final int[] array;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> private int position; //heap-encoded state</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> ValuesFromAnArray(int[] array) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> this.array = array;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> </span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b>// API layer between library and user code</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b></b> public Integer next() { </span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> if (!hasNext()) throw new NoSuchElementException();</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return array[position++];</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b>// API layer between library and user code</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b></b> public boolean hasNext() { </span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return position < array.length;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span><br />
(I don't concern myself with trivialities like how to wrap the Iterator into an Iterable).<br />
<br />
Here, the library is active. The user code returns a value, and updates its state (which must be stored in the heap) so next time it will return the next value. The active library has an easier job - it only uses a local var for its state, and it doesn't have to explicitly store where it was (so it can come back to it) before calling the user code, since it implicitly uses the <i>program counter</i> to store that information. (And if you think about it, if you have a method and you have 8 independent positions, like nested if's of depth equal to 3, and you enter one of them, you effectively use the program counter to encode <i>3 bits of information</i>. To turn this into a heap-based state machine, be sure to remember to encode those three bits in the heap as well!) The passive user code is basically a simplistic iterator (and iterators are a fine example of constructs designed to be passive).<br />
<br />
The other option is this:<br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b>//user code - active</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">int[] array = ...;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">MaxFinder m = new MaxFinder();</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">for (int value : array) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> m.seeValue(value);</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">int max = m.max();</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b>//library - passive</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">class MaxFinder {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> private int max = Integer.MIN_VALUE; <b>//heap-encoded state</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b>// API layer between user code and library</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b></b> void seeValue(int value) { </span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> max = Math.max(max, value);</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span><br />
<div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b>// API layer between user code and library</b></span></div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> int max() {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return max;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<br />
In this case, the user code is active and the library is passive. Again, the passive one is forced to encode its state in the heap.<br />
<br />
Both work. All we did is a simple mechanical transformation to go from the one to the other. The question for the library designer:<br />
<ul><li>Which option to offer? (Or offer both??)</li>
</ul>That's not so trivial. Lets try to compare:<br />
<br />
<b>1. Syntax:</b> There is no doubt that having the option to encode your state in the call-stack is a big <i>syntactic</i> win (big, but only syntactic). Not so much because of local vars, but because of the program counter: All those nifty for-loops, nested if statements and what not, look so ugly when encoded in the heap. For example, here is some active user code:<br />
<br />
<div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">MaxFinder maxFinder = new MaxFinder();</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">for (int i = 0; i < 10; i++) {</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> for (int j = 0; j < 5; j++) {</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> maxFinder.seeValue(someComplicatedFunction(i, j)); </span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span>Easy. Lets see what happens if we try to transform this into passive user code:<br />
<br />
<div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">return new AbstractIterator<integer>() { //Guava's AbstractIterator for convenience</integer></span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> int i = 0;</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> int j = 0;</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> protected Integer computeNext() {</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> try {</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return (i < 5) ? someComplicatedFunction(i, j) : endOfData();</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> } finally {</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> j++;</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> if (j >= 5) {</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> i++;</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> j = 0;</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">};</span></div></div><div><br />
Ouch - that's like we took a shotgun and splattered the previous code into pieces. Of course, I'm biased: after having read countless for-loops, I tend to understand them more easily and think them simpler, compared to the individual pieces of them scattered here and there. "It's just syntax", in the end (mind you, the difference could be a lot worse though).</div><div><br />
</div><div><b>2. Composability</b>: Now this is not aesthetics any more, but it's a more serious question between "works" or "doesn't work". If you offer your library as active, you force the user code to be passive. If the user code is already written, and is active, <i>then it simply can't work with the active library</i>. It is precisely this user that will complain to you about your library and/or ask you to offer a passive counterpart in addition to the active you already offered. One of the two parties must agree to use <i>return</i> to send a message back, instead of recursively invoking a method. If neither is passive, the result will be infinite recursion. <i>An active participant requires control of the call-stack for the duration of the coordination</i> (corollary, two actives can only work together if each one has its own call-stack - see "trampoline" below). But if you offer your library as passive, <i>you don't preclude any option for the user</i> (it can be either active or passive), and thus this is the most flexible. </div><div><br />
</div><br />
To exemplify the last point, (this is an adaptation from <a href="http://gafter.blogspot.com/2007/07/internal-versus-external-iterators.html/">Gafter's post</a>) suppose we have two lists and we want to test whether they are equal. If we can produce iterators (i.e., passive state machines), it is easy:<br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">//<b>PassiveList offers #iterator()</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">boolean areEqual(PassiveList list1, PassiveList list2) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> if (list1.size() != list2.size()) return false;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Iterator i1 = list1.<b>iterator()</b>;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Iterator i2 = list2.<b>iterator()</b>;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> while (i1.<b>hasNext()</b>) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> if (i1.<b>next()</b> != <b>i2.next()</b>) return false;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return true;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<br />
If one of the lists was active (had a #forEach() operation instead of giving an iterator), it is still implementable, let the active control the passive:<br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b>//ActiveList offers #forEach(ElementHandler)</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">boolean areEqual(ActiveList activeList, PassiveList passiveList) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> if (activeList.size() != passiveList.size()) return false;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> </span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> final Iterator iterator = passiveList.<b>iterator()</b>;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> final boolean[] equal = { true }; </span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> activeList.<b>forEach(new ElementHandler() {</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b> public void process(Object e)</b> {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> if (e != iterator.<b>next()</b>) equal[0] = false;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> } //don't nitpick about not breaking early!</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> });</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return equal[0];</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<br />
But in principle, it's not possible to implement the following method, without spawning a second thread (again, see trampoline, below), :<br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">//both are active!</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">boolean areEqual(ActiveList list1, ActiveList list2);</span><br />
<br />
<b>3) Exceptions: </b>Another (Java-specific) way that the two option differ is <i>checked exceptions</i>, unfortunately. If you create an active library, you have to anticipate your passive user code may require to throw checked exceptions - so creating the API (implemented by user code) without knowing the checked exceptions beforehand is problematic and ugly (this have to somehow be reflected in the API signatures, and generified exceptions are not for the weak-hearted), whereas if you let the user code take the active position, it is oh-too-easy for the user code to wrap the whole thing in a try/catch or add a throws clause in the enclosing method (the enclosing method is of not offered by your library and is no concern to you - if it is not <i>your </i>code that throws checked exceptions, you don't have to worry about them, and this is good). <span class="Apple-style-span" style="font-size: xx-small;">Oh well. Just another reason we all should be doing scala, eventually. Lets quickly hide this under the carpet for now.</span> Credit for noting this important caveat goes to Chris Povirk.<br />
<br />
So where these considerations leave us? My rules of thumb (not entirely contradiction-free):<br />
<br />
<ol><li><i>Let the more complicated participant have the active position</i>; that piece of code will benefit the most by having its stackframe available for encoding its state. </li>
<li>If you provide a library, <i>offer it as passive</i> - so you leave all options open for the user.<br />
<br />
But what to do if you anticipate *the library* to be the more complicated participant? Do you choose to make it active and force user code to be passive? What if you are wrong in your estimation? It's a tough call. But in the end, if you are forced to offer your library also as active, at least place that version near the passive one, so it's apparent that these two perform the same function, and so the users have to look for this functionality at a single place, not two.<br />
</li>
<li>If though the library is supposed to offer parallelization to the user, there is no option: you <b>have</b> to make it active, because parallelization boils down to controlling how to invoke user's code. (See <a href="http://gee.cs.oswego.edu/dl/jsr166/dist/extra166ydocs/extra166y/ParallelArray.html">ParallelArray</a>'s active operations. This also offers a passive iterator, but it would be folly to use it)</li>
</ol><br />
That was the meat of this post. I mentioned trampolines above, so in the remaining part, I'll touch upon that.<br />
<br />
Python generators are, indeed, beautiful. You write an <i>active</i> piece of code, and some python (alas, very inefficient) piece of magic transforms it into a <i>passive</i> construct (iterator) out of that (which, recall, can be used with another active counterpart). Thus, you get the best of both worlds: <b>both</b> parties (e.g. producer and consumer, here) can be active!<br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b>//producer - active!</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">Iterator<integer> iterator = magicTrampoline(new AbstractProducer<integer>() {</integer></integer></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public void run() {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> for (int i = 0; i < 10; i++) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> for (int j = 0; j < 5; j++) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> produce(complicatedFunction(i, j));</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">};</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b>//consumer - active!</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">while (iterator.hasNext())</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> consume(iterator.next());</span><br />
<br />
This is certainly the best option for code readability. The cost is, we need an extra thread (more precisely, we need an extra call-stack). "Trampoline" is the common name of the port of this to Java. I wanted to link to some implementation here, but couldn't readily find a nice one. I'll just sketch the implementation anyway: the idea is that you let the producer run on a separate (from the consumer) thread. Thus message-passing between producer and consumer do not happen in the same call-stack, but via another means, say via a BlockingQueue (the producer puts, the consumer takes). So, the producer doesn't have to destroy its stackframe(s) after producing an element, but it can safely hold on to it (remember that this was not possible in the single-thread scenario, with message passing via the call-stack, that would lead to infinite recursion).<br />
<br />
<b>--EDIT</b><br />
<b></b>Sure I can find an implementation of the above - <a href="http://www.google.com/search?sourceid=chrome&ie=UTF-8&q=scala+actors">scala actors</a>! The actors interact in an active (of course!) fashion, and this is possible because they communicate by <i>exchanging messages, </i>not<i> invocations</i>, thus no party needs to play the passive role. (Of course, underneath there is the good old BlockingQueue and the trampoline mechanics mentioned above. ) And yet, even in scala actors, there are the so called reactive actors - these don't hold on to their thread (and their call-stack), thus are not as wasteful as the regular actors, but, as per the discussion above, they are passive. This is the way one can tie actors in this discussion, and understand these through a different perspective.<br />
<b>--/EDIT</b><br />
<br />
Since the cost for this is very high (not just the second thread itself, but the frequent blockings/context switches), it is not to be recommended in Java, unless we someday get much more lightweight threads, like those in Erlang. (And I can certainly imagine the joy of Erlang programmers, who can always readily use their call-stack to encode their complex state machines, instead of jumping through hops just so they do not introduce another thread.)<br />
<br />
(Another way to achieve this would be via continuations - which Java doesn't support natively.)<br />
<br />
And a departing story: 4 years ago, I played with these ideas in the context of implementing complex gesture detection for a graph editor, amongst other graph related tasks. Use-case: implement drag and drop for nodes (a common task). This is what my experimental code looked like - quite elegant:<br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><b>//active pattern detection!</b></span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">Event firstEvent = awaitEvent();</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">if (firstEvent.isMouseDown()) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Event nextEvent;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> while ((nextEvent = awaitEvent()).isMouseDrag()) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> continue;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> if (nextEvent.isMouseUp()) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> //drag and drop is complete!</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">} else { </span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> ...</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<br />
If you have read all the way to here (phew!), you can probably imagine how "fun" (ugh) would be transforming the pattern detection to a passive, say, MouseListener/MouseMotionListener (and translating those if's and else's and while's...). Be my guest and try (I'm kidding - just don't). This is the source of my first rule of thumb: it was via such, sufficiently complicated state machines that I observed how much the code can be simplified just through the act of making it active.<br />
<br />
To better understand the last example and how it's relevant, note that Swing itself is an active state machine - remember, it owns the event-dispatching thread, thus user code is forced into the passive role. (Which is also consistent with my first rule of thumb: swing, the most complex machinery, taking up the active, more convenient role).Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com10tag:blogger.com,1999:blog-6958126065976802292.post-35999120726593692472010-12-12T23:19:00.000-08:002011-01-07T13:33:24.658-08:00How long is the period of random numbers created by java.util.Random?<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">The answer is, <i>pretty darn long!</i> </span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">I feel a bit cheated for not knowning, while I had several times seen the code the years before.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">So it uses a good old linear congruential generator:</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">x = A * x + C</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">So, java.util.Random uses these two constants (A and C respectively):<br />
</span><br />
<br />
<div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> private final static long multiplier = 0x5DEECE66DL;</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> private final static long addend = 0xBL;</span></div><div><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br />
</span></div><div><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Quite appropriate to place two "random" numbers in the Random class, right? Only these are not <i>entirely </i>random...</span></div><div><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br />
</span></div><div><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">0x5DEECE66DL</span> </span><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">% 8 == 5</span></div><div><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">and </span></div><div><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">0xBL </span>is an odd.</span></div><div><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br />
</span></div><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">So what? </span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br />
</span></span><br />
<div><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">It turns out, when these exact conditions are satisfied, the defined period is <i>maximal</i>, so the generated period (x is long) is 2^64. This piece of magic is documented <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.1024">here, page 9</a>. The "why" of it is beyond me. </span></div><div><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br />
</span></div><div><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">If any ninja mathematician comes across this post, please leave some explanation if you can.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><b>EDIT: </b>oops. I overlooked that java.util.Random uses a mask to only reduce itself to 48 bits, instead of 64, so correspondingly the period is 2^48 instead of 2^64; apparently in an attempt to increase the quality of the generated numbers. In any case, if you need longer period, the technique described here will do the trick.</span></div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com4tag:blogger.com,1999:blog-6958126065976802292.post-71618215334772884432010-12-12T18:24:00.000-08:002010-12-12T18:26:00.926-08:00Juggling consistent hashing, hashtables, and good old sorting<a href="http://en.wikipedia.org/wiki/Consistent_hashing">Consistent hashing</a> can be summarized in one sentence: it is a hashtable with variant-length buckets.<br />
<br />
You have a line segment (that's the key space). Breaking it to N equal parts (the buckets) means it is very easy (O(1)) to compute which part contains a given point. But if you increase or decrease N, all parts change (and shrink or grow respectively). Only the first and the last part have one of its ends unaffected, but the rest have both their ends moved.<br />
<br />
Now consider breaking it in N parts, but not of necessarily the same length. Now it is easier to change the number of parts. Do you want more parts? Break one in two pieces. Want fewer parts? Merge two parts sitting next to each other. All other parts remain firm in their place, unaffected. But now finding which part contains a given point gets more complicated (O(logN) if you keep the parts sorted, say in a red-black tree).<br />
<br />
Hashtables themselves can be summarized in an interesting way: it is <b>sorting</b>...by hash (it doesn't matter if the original key space is not totally ordered - <i>the hashes are</i>). But if it is sorting, where the logN factor in the complexity of hashtable operations? Well, there isn't one: hashes are small natural numbers (bounded by the hashtable size, which is O(N) of the elements in it). And what do you think of when you want to sort small natural numbers? <a href="http://en.wikipedia.org/wiki/Counting_sort">Counting sort</a>. (Caveat: hash functions do not just aim to map a large key space into a sequence of natural numbers, that's only part of the story. They also aim to approximate a random permutation of the original space, which is separately useful - to try to load balance the buckets when the incoming distribution is not uniform. In consistent hashing, we sacrifice the first role of hash functions, but we keep this latter one).<br />
<br />
Trying to compress the discussion above:<br />
<br />
<ul><li>Hashtables are really counting sort</li>
<ul><li>(Yes, data structures <i>are</i> algorithms)</li>
<li>An <i>equal</i> piece of the (approximately permuted) key space is mapped to each bucket</li>
<ul><li>Easy to find the corresponding bucket for a key (++)</li>
<li>Changing the number of buckets affects the mapped spaces of all buckets (--)</li>
</ul></ul><li>Consistent hashing differs in the following way:</li>
<ul><li> A <i>variable </i>piece the (approximately permuted) key space is mapped to each bucket</li>
<ul><li>Harder to find the corresponding bucket for a key (--)</li>
<li>Easy to split or merge buckets, without affecting any other buckets (++)</li>
</ul></ul></ul><br />
<br />
Bonus section: <a href="http://en.wikipedia.org/wiki/BigTable">Bigtables</a> (and the good old Bigtable paper <a href="http://static.googleusercontent.com/external_content/untrusted_dlcp/labs.google.com/en/us/papers/bigtable-osdi06.pdf">here</a>). In Bigtable, The rows are primarily sorted by row key. The tablets (think buckets) are variable length, so that overloaded tablets can be split, without touching the huge amount of data that potentially reside in the same bigtable. (One can help load balancing the tablets by -did you guess it?- sorting by hash first...). So, here you go. The rows are <i>sorted</i>. Yet it can still rightfully be described as consistent <i>hashing</i>. Confused yet? Well, at least I tried. :)Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com0tag:blogger.com,1999:blog-6958126065976802292.post-30199428615209009372010-10-20T02:47:00.000-07:002010-10-20T02:50:45.645-07:00Memory cost (per entry) for various Java data structuresHave you seen this? <a href="http://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures">http://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures</a><br />
It shows the memory cost <i>per each entry</i> for various common and not-so-common Java data structures. For example, have you wondered when you put() an entry to a HashMap, how much memory footprint you create, <i>apart</i> from the space occupied by your key and your value (i.e. only by internal artifacts introduced by HashMap itself)? There are the answers to such questions.<br />
<br />
It also exemplifies the utility of my <a href="http://code.google.com/p/memory-measurer/">memory measuring tool</a>, which I recently redesigned to decouple object exploration from measuring the memory usage (bytes) of objects, so I can use the same exploration to derive more qualitative statistics, like number of objects in a object graph, number of references, and number of primitives (which would directly reflect memory usage if it weren't for effects of alignment).<br />
<br />
If you are designing data structures in Java, it would be silly not to use this tool. Seriously. (Profilers can be used to somewhat the same effect, but why fire it up and click buttons till you get where you want and take numbers and calculate by yourself, when you can do it more precisely with very simple code).<br />
<br />
Future work: do the same for the immutable <a href="http://guava-libraries.googlecode.com/">Guava</a> collections.Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com6tag:blogger.com,1999:blog-6958126065976802292.post-28541606612734452612010-07-29T18:42:00.000-07:002012-02-18T16:49:12.157-08:00Graph reachability, transitive closures, and a nasty historical accident in the pre-google era<div class="separator" style="clear: both; text-align: left;">
Last few days I'm feeling a bit like an archaeologist. It's probably a great story to explain to a newcomer just what's the importance of the internet, coupled with a great search engine. But I digress.</div>
<br />
What follows is a pretty long post, covering a lot of ground in the graph reachability problem and transitive closures, enumerating various naive solutions (i.e., the ones you are likely to see used), then moving to much more promising approaches.<br />
<span class="Apple-style-span" style="font-size: medium;"><br />
</span><br />
<b><span class="Apple-style-span"><span class="Apple-style-span" style="font-size: x-large;">Introduction</span></span></b><br />
<span class="Apple-style-span" style="font-size: medium;"><br />
</span><br />
Let's say you have a directed graph, <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">G = (V, E)</span>, and you want to know <i>real fast</i> whether you can reach some node from some other, in other words whether there is a directed path <b>u --> v</b>, for any nodes <b>u</b> and <b>v</b>. (Take a moment to convince yourself that this is a trivial problem if the graph is undirected). Before we continue, lets stop and think where this might be useful. Consider a (really silly) class hierarchy (we also call it an ontology):<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjsUvGPyD2SMuUYhwKMqQduALaGM8gjMrK2K-nw_G5HKyqDSd4TyPJ6RCyprukG9b0FUbLWmzm3UvkvEnk2C_AQUPvLu-0MrbRL556ZSutWkkSUa86pBmOzzDJ2gSeVHjjwyqLu5Mpcup5C/s1600/class_hierarchy.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="241" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjsUvGPyD2SMuUYhwKMqQduALaGM8gjMrK2K-nw_G5HKyqDSd4TyPJ6RCyprukG9b0FUbLWmzm3UvkvEnk2C_AQUPvLu-0MrbRL556ZSutWkkSUa86pBmOzzDJ2gSeVHjjwyqLu5Mpcup5C/s640/class_hierarchy.png" width="640" /></a></div>
<br />
Testing whether there is a directed path between two nodes in a class hierarchy is equivalent to asking "is this class a subclass of another?". That's basically what the <b><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">instanceof</span> </b>Java operator does (if we only consider classes, then subtyping in Java forms a tree - single inheritance, remember? - but if we add interfaces in the mix, we get a DAG, but thankfully, never a cycle).<br />
<br />
Lets formally denote such a query by a function <b><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">existsPath: V x V --> {1, 0}</span><span class="Apple-style-span" style="font-family: inherit;"><span class="Apple-style-span" style="font-weight: normal;">.</span></span> </b>It takes an ordered pair of nodes, and returns whether there is a path from the first to the second. Now, lets make sure that having such an <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">existsPath</span> function is, in fact, <b>the <a href="http://en.wikipedia.org/wiki/Characteristic_function">characteristic function</a> of the <a href="http://en.wikipedia.org/wiki/Transitive_closure">transitive closure</a></b> of the graph, that is, given any edge, we can apply this function to it to test whether it belongs to the transitive closure or not, i.e., whether it is one of the following edges:<br />
<span class="Apple-style-span" style="font-size: medium;"><br />
</span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhuS8jE6CANe5XAHh7UUJoGTjyS7jgi0kF9VaEVcObQBRpdQckP7iurvCNVBcXCFPg80-9TyQiffXOTPE0DLBDXZwGRI_UVI3qaBM0ewRHTFid6Oh4ag_qCwpMS3HGbzdTZYDnWvGT3H0SF/s1600/class_hierarchy_tr.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><span class="Apple-style-span" style="font-size: medium;"><img border="0" height="241" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhuS8jE6CANe5XAHh7UUJoGTjyS7jgi0kF9VaEVcObQBRpdQckP7iurvCNVBcXCFPg80-9TyQiffXOTPE0DLBDXZwGRI_UVI3qaBM0ewRHTFid6Oh4ag_qCwpMS3HGbzdTZYDnWvGT3H0SF/s640/class_hierarchy_tr.png" width="640" /></span></a></div>
<span class="Apple-style-span" style="font-size: medium;"><br />
</span><br />
<span class="Apple-style-span" style="font-size: medium;"><br />
</span><br />
When we talk about transitive closure, though, we mean something <i>more</i> than merely being able to answer graph reachability queries - we also imply that we possess a function <b><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">successorSet: V --> Powerset(V)</span></b>. i.e., that we can find all ancestors of a node, instead of checking if a <b>particular</b> node is an ancestor of it or not.<br />
<br />
By the way, the above explanation is exactly the reason why in <a href="http://code.google.com/p/flexigraph/">Flexigraph</a><span class="Apple-style-span" style="font-size: medium;"><span class="Apple-style-span" style="font-size: medium;"> I define the interfaces (sorry, but blogger doesn't play very nicely with source code):</span><br />
</span><br />
<span class="Apple-style-span" style="font-size: medium;"><span class="Apple-style-span" style="font-size: medium;"><br /></span></span><br />
<table id="src_table_0" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; border-collapse: collapse; font-family: monospace; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; white-space: pre;"><tbody style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;">
<tr id="sl_svn2_10" style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;"><td class="source" style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 4px; padding-right: 0px; padding-top: 0px; vertical-align: top; white-space: pre-wrap;"><span class="kwd" style="color: #000088;">public</span><span class="pln" style="color: black;"> interface </span><span class="typ" style="color: #660066;">PathFinder</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;"><br /></span></td></tr>
<tr id="sl_svn2_19" style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;"><td class="source" style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 4px; padding-right: 0px; padding-top: 0px; vertical-align: top; white-space: pre-wrap;"><span class="pln" style="color: black;"> </span><span class="kwd" style="color: #000088;">boolean</span><span class="pln" style="color: black;"> pathExists</span><span class="pun" style="color: #666600;">(</span><span class="typ" style="color: #660066;">Node</span><span class="pln" style="color: black;"> n1</span><span class="pun" style="color: #666600;">,</span><span class="pln" style="color: black;"> </span><span class="typ" style="color: #660066;">Node</span><span class="pln" style="color: black;"> n2</span><span class="pun" style="color: #666600;">);</span><span class="pln" style="color: black;"><br /></span></td></tr>
<tr id="sl_svn2_20" style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;"><td class="source" style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 4px; padding-right: 0px; padding-top: 0px; vertical-align: top; white-space: pre-wrap;"><span class="pun" style="color: #666600;">}</span></td></tr>
</tbody></table>
<br />
<table id="src_table_0" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; border-collapse: collapse; font-family: monospace; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px; white-space: pre;"><tbody style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;">
<tr id="sl_svn2_12" style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;"><td class="source" style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 4px; padding-right: 0px; padding-top: 0px; vertical-align: top; white-space: pre-wrap;"><span class="kwd" style="color: #000088;">public</span><span class="pln" style="color: black;"> interface </span><span class="typ" style="color: #660066;">Closure</span><span class="pln" style="color: black;"> </span><span class="kwd" style="color: #000088;">extends</span><span class="pln" style="color: black;"> </span><span class="typ" style="color: #660066;">PathFindr</span><span class="pln" style="color: black;"> </span><span class="pun" style="color: #666600;">{</span><span class="pln" style="color: black;"><br /></span></td></tr>
<tr id="sl_svn2_19" style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;"><td class="source" style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 4px; padding-right: 0px; padding-top: 0px; vertical-align: top; white-space: pre-wrap;"><span class="pln" style="color: black;"> </span><span class="typ" style="color: #660066;">SuccessorSet</span><span class="pln" style="color: black;"> successorsOf</span><span class="pun" style="color: #666600;">(</span><span class="typ" style="color: #660066;">Node</span><span class="pln" style="color: black;"> node</span><span class="pun" style="color: #666600;">);</span><span class="pln" style="color: black;"><br /></span></td></tr>
<tr id="sl_svn2_20" style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;"><td class="source" style="margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; padding-bottom: 0px; padding-left: 4px; padding-right: 0px; padding-top: 0px; vertical-align: top; white-space: pre-wrap;"><span class="pun" style="color: #666600;">}</span></td></tr>
</tbody></table>
<br />
"<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; border-collapse: collapse; font-family: monospace; white-space: pre-wrap;"><span class="typ" style="color: #660066;">Closure</span></span><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; border-collapse: collapse; font-family: monospace; white-space: pre-wrap;"><span class="pln" style="color: black;"> </span></span><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; border-collapse: collapse; font-family: monospace; white-space: pre-wrap;"><span class="kwd" style="color: #000088;">extends</span></span><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; border-collapse: collapse; font-family: monospace; white-space: pre-wrap;"><span class="pln" style="color: black;"> </span></span><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; border-collapse: collapse; font-family: monospace; white-space: pre-wrap;"><span class="typ" style="color: #660066;">PathFinder</span></span>" is basically a theorem expressed in code, that <b>any transitive closure representation is also a graph reachability representation</b>. That's the precise relation between these two concepts - I'm not aware of any Java graph library that gets these right. Continuing the self-plug, if you need to work with transitive closures/reductions, you might find the whole <a href="http://code.google.com/p/flexigraph/source/browse/trunk/src/gr/forth/ics/graph/algo/transitivity/">transitivity package</a> interesting - compare this, for example, with <a href="http://www.jgrapht.org/javadoc/org/jgrapht/alg/TransitiveClosure.html">JGraphT support</a>, or <a href="http://www.yworks.com/products/yfiles/doc/api/y/algo/Transitivity.html">yWorks support</a>: a sad state of affairs. But I digress again.<br />
<br />
<b><span class="Apple-style-span" style="font-size: x-large;">Supporting graph reachability queries</span></b><br />
<br />
Ok, lets concentrate now on actually implementing support for graph reachability queries. These are the most important questions to ask before we start:<br />
<ul>
<li><b>How much memory are we willing to spend?</b></li>
<li><b>Is the graph static? Or update operation are supported (and which)?</b></li>
</ul>
Lets explore the design space based on some typical answers to the above questions.<br />
<br />
<b>Bit-matrix: </b>The fastest reachability test is offered by the bit-matrix method: make a |V| x |V| matrix, and store in each cell whether there is a path from the row-node to the column-node. This actually <i>materializes</i> the transitive closure, in the sense that we explicitly (rather than implicitly, to some degree) represent it (and we already argued that representing the transitive closure also implies support for graph reachability queries).<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiGdpS1hU47WsaGgyOX8vbbqIaITTF6g21c61Rt-cw9h4oZR05qOBvqbVvCT1qaWMo6yjlCgZ4htwq1Yar7ycHsbG63B7eZ5w_YWsZp6I1Q1MLLtdjzInI2ZvAA6av4IxSgm9XG-yAia5Pq/s1600/bitmap.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="136" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiGdpS1hU47WsaGgyOX8vbbqIaITTF6g21c61Rt-cw9h4oZR05qOBvqbVvCT1qaWMo6yjlCgZ4htwq1Yar7ycHsbG63B7eZ5w_YWsZp6I1Q1MLLtdjzInI2ZvAA6av4IxSgm9XG-yAia5Pq/s400/bitmap.PNG" width="400" /></a></div>
<br />
<br />
Of course, this has some obvious shortcomings. Firstly, it uses <b>O(|V| ^ 2)</b> memory - but this is not as bad as it looks, and it would probably be a good solution for you <b>if your graph is static</b>. Which leads us to the second problem - <b>it is terrible if you expect to frequently update your graph</b>.<br />
<br />
<b>Adjacency-list graph representation: </b>another way of representing the transitive closure is to just create an <a href="http://en.wikipedia.org/wiki/Adjacency_list">adjacency-list</a> graph with all the edges of the transitive closure in it. In the example, that would mean to create a graph to represent the second image. (This is what JGraphT and yWorks offer - it's the simplest to implement). This has numerous disadvantages. First, this is a costly representation - such a representation is good for <i>sparse</i> graphs, but it is very easy for a sparse graph to have a <i>dense</i> transitive closure (consider a single path). Worse, if you represent each edge with an actual "Edge" object, then you are quite probably end up with a representation even costlier than the naive bitmap method - <b>compare using a single bit to encode an edge vs using at least 12 bytes </b>(at least, but typically quite more than that), i.e. <b>96bits. </b>Also, this representation <b>doesn't even offer fast reachability test</b> - testing whether two nodes are connected depends on the minimum degree of those nodes, and this degree can be large in a dense graph. All in all, this representation is the lest likely to be the best for a given application.<br />
<br />
<b>Agrawal et al: </b>Now, lets see the approach in a very influential paper published in 1989: <span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;"> </span><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;"><a href="https://docs.google.com/viewer?url=http%3A%2F%2Fsites.google.com%2Fsite%2Fjimandreou%2Fvarious%2FAgrawal-EfficientManagementofTransitiveRelationshipsinLargeDataandKnowledgeBases.pdf%3Fattredirects%3D0%26d%3D1">Efficient Management of Transitive Relationships in Large Data and Knowledge Bases</a>. Lets see a figure from this paper, starting from the simple case of supporting reachability queries <b>in a tree</b>: </span><br />
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;"><br />
</span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhMQIj6i7bg97lLeqX8qqfQ2XOu2E_KN-z_Plwz3MCoptnPXnNDdDviQaTh6_kwmNlG17ZkJeEQcuFPE0ZJl_Tr5RQyBAyZ0GwIIIISV_S_pj5vfjnSY2oKwPqz3rFMvq0gO88GwJcwLO54/s1600/agrawal.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="312" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhMQIj6i7bg97lLeqX8qqfQ2XOu2E_KN-z_Plwz3MCoptnPXnNDdDviQaTh6_kwmNlG17ZkJeEQcuFPE0ZJl_Tr5RQyBAyZ0GwIIIISV_S_pj5vfjnSY2oKwPqz3rFMvq0gO88GwJcwLO54/s640/agrawal.PNG" width="640" /></a></div>
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">(Don't be confused by the edge directions, they just happened to drew them the other way around). Each node is labelled with a pair of integers - think of each pair as an interval in the X-axis. The <i>second</i> number is the post-order index of that node in the tree, while the first number is equal to <i>the minimum <a href="http://en.wikipedia.org/wiki/Tree_traversal">post-order</a> index of any descendant</i> of that node. Lets quickly visualize those pairs as intervals:</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgCJNVaFYluU6TXhVvibI51jNe1MM95pixuQE1OPZa2TWGjl0kIiaRc_pT4S37SllOHUWK8Grw_epxAJkV2i8KcDMh1jYyNchJ4A97gTO__75pO0DZHuZkwmp6CUU72hWJGa4FkZTQfw7dJ/s1600/agrawal2.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgCJNVaFYluU6TXhVvibI51jNe1MM95pixuQE1OPZa2TWGjl0kIiaRc_pT4S37SllOHUWK8Grw_epxAJkV2i8KcDMh1jYyNchJ4A97gTO__75pO0DZHuZkwmp6CUU72hWJGa4FkZTQfw7dJ/s320/agrawal2.PNG" width="212" /></a></div>
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">As you can see, the interval of each node <i>subsumes</i> (<i>is a proper superset of</i>) the intervals of <i>exactly</i> its descendants. Thus, we can quickly test whether "<b>e</b> <b>is a descendant of</b> <b>b</b>" by asking "<b>is <i>3</i> contained in the interval [1, 4]?</b>", in <b>O(1) </b>time. </span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">Quick check: does it easily support graph updates? <b>No!</b> Inserting a new leaf under node <b>g</b> would require changing the numbers of <b>g and everything on its right </b>(that is, <b><i>all<span class="Apple-style-span" style="font-weight: normal;"> <span class="Apple-style-span" style="font-style: normal;">the nodes of the graph!). </span></span></i></b>And we are still only discussing about trees. Lets see how this generalizes for acyclic graphs (this can be similarly generalized to general graphs, but I won't elaborate on that here). Again, a figure from the paper:</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh3NWpw-pQj4yVk0Xy6FfPoNZvwMXI_T1kfDGXns7W9Gjv8jBLuSuI9IqGDHh_aoU4zPcmYkkiWFrJi5yBq3VEdzKIQdhsGJQF41OKT7vVGx8IFdgye_Ypc2ZY36HnIS8Y0wzqUth9UKFjh/s1600/agrawal3.PNG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="288" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh3NWpw-pQj4yVk0Xy6FfPoNZvwMXI_T1kfDGXns7W9Gjv8jBLuSuI9IqGDHh_aoU4zPcmYkkiWFrJi5yBq3VEdzKIQdhsGJQF41OKT7vVGx8IFdgye_Ypc2ZY36HnIS8Y0wzqUth9UKFjh/s640/agrawal3.PNG" width="640" /></a></div>
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">Note that some non-tree edges have been added, particularly <b><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">d --> b</span> </b>(the rest of the inserted are actually redundant, yes, they could have used a better example). Also note that now <b>d </b>is represented by <b>two</b> intervals, [6,7] and [1,4]. The same invariants are observed as above - the interval <i>set</i> of each node <i>subsumes</i> any interval of <i>exactly</i> its descendants. Basically, we start with a tree (forest) of the graph, label it as previously, and then process all non-tree edges, by <b>propagating</b> all the intervals of the descendant to <b>all</b> its ancestors via that edge.</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">Second check: how does this cope with graph updates? <b>Much worse! </b>If, for example, we have to change the interval of <b>g</b>, we now must <b>search potentially the whole graph</b> and track <i>where</i> its interval might have been propagated, fixing all those occurrences with the new interval of <b>g</b>. Well, this sucks big time.</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">Now, lets try to justify the "historical accident" that the title promises. <b>What if I told you that this problem was already solved 7 years earlier than Agrawal reintroduced it? </b>More importantly, <b>what if I told you that <span class="Apple-style-span" style="font-weight: normal;">(apparently!) </span><i>hardly anyone noticed</i> this since then? </b>It's hard to believe. For example, here is a technical report published recently, in 2006: </span></span><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;"><a href="http://www.blogger.com/goog_804827837">Preuveneers, Berbers - Prime Numbers Considered Useful</a></span><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;"><a href="https://docs.google.com/viewer?url=http%3A%2F%2Fsites.google.com%2Fsite%2Fjimandreou%2Fvarious%2FPreuveneers%252CBerbers-PrimeNumbersConsideredUseful%25282006%2529.pdf%3Fattredirects%3D0%26d%3D1"> </a>. Don't bother reading all those 50 pages - here is a relevant quote (shortly after having presented the Agrawal et al method - emphasis mine):</span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"></span><br />
<blockquote>
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;">In the previous section several encoding algorithms for efficient subsumption or subtype testing were discussed. As previously outlined, <b>the major concern is support for efficient incremental and conflict-free encoding</b>. While most algorithms provide a way to encode new classes without re-encoding the whole hierarchy, <b>they often require going through the hierarchy to find and modify any </b><b>conflicting codes</b>. The <b><i>only</i></b> algorithm that does not suffer from this issue is the <b><i>binary matrix</i></b> method, but this method is the most expensive one with respect to the encoding length as no compaction of the representation is achieved.</span></blockquote>
This statement is the authors' motivation for design a new approach (a not too practical dare I say, requiring expensive computations on very large integers). They didn't know the solution.<br />
<div>
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="font-family: 'Times New Roman';"><br />
</span></span></div>
<div>
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="font-family: 'Times New Roman';"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px;">Here is another example, published in 2004.</span></span><a href="https://docs.google.com/viewer?url=http%3A%2F%2Fsites.google.com%2Fsite%2Fjimandreou%2Fvarious%2FChristophides-OptimizingTaxonomicSemanticWebQueriesUsingLabelingSchemes.pdf%3Fattredirects%3D0%26d%3D1">Christophides - Optimizing Taxonomic Semantic Web Queries Using Labeling Schemes</a>. </span>This is a great informative paper surveying at depth a number of different graph reachability schemes, with a focus on databases. Christophides, actually, is my former supervisor, Professor at the University of Crete, and a good friend. Unfortunately, even though this paper actually cites the paper that contains the key idea, they also didn't know the solution (this I know first-hand).</div>
<div>
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span></div>
<div>
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">Yet another example, published in 1999: <a href="https://docs.google.com/viewer?url=http%3A%2F%2Fsites.google.com%2Fsite%2Fjimandreou%2Fvarious%2FBommel%252CBeck-IncrementalEncodingofMultipleInheritanceHierarchies%25281999%2529.pdf%3Fattredirects%3D0%26d%3D1">Bommel, Beck - Incremental Encoding of Multiple Inheritance Hierarchies</a>. Again, they didn't know the solution, so they ended up creating a more complicated, less-than-ideal work-around (see for yourself).</span></span></div>
<div>
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span></div>
<div>
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">I don't even dare to look into all <a href="http://scholar.google.co.uk/scholar?cites=17382624612013631960&as_sdt=2005&sciodt=2000&hl=en">~250 papers that cite Agrawal's work</a>.</span></span></div>
<div>
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span></div>
<div>
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;">This is rather embarrassing. Before continuing, this kind of regression would have been highly unlikely if there was an efficient way (e.g. <a href="http://scholar.google.com/">google scholar</a> :) ) to search for relevant research. Here goes the obligatory <a href="http://en.wikipedia.org/wiki/Memex">memex</a> link.</span></div>
<div>
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;"><br />
</span></div>
<div>
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;">That being said, lets finally turn our attention to the mysterious solution that was missed by seemingly everyone. </span><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;"><a href="https://docs.google.com/viewer?url=http%3A%2F%2Fsites.google.com%2Fsite%2Fjimandreou%2Fvarious%2FDietz-Maintainingorderinalinkedlist.pdf%3Fattredirects%3D0%26d%3D1">Dietz - Maintaining order in a linked list</a>. This paper was published much earlier - in 1982, a year special to me since that's when I was born. </span><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;">Dietz introduces the (lets call it so) <i>order maintainance structure</i>, defined by this interface:</span><br />
<ul>
<li><span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><b>Insert(x, y)</b><br />
Inserts element x right afterwards element y.<br />
</span></span></li>
<li><span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><b>Delete(x) </b>(Obvious)<br />
</span></span></li>
<li><span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><b>Order(x, y) </b><br />
Returns whether x <i>precedes</i> y.</span></span></li>
</ul>
<span style="font-family: Arial, Verdana, sans-serif;">So this is basically similar to a linked list, with the addition that we can ask (in constant time!) whether a particular list node precedes another. The actual data structure proposed to fulfill this interface has been superseded by Dietz and Sleator in </span><a href="https://docs.google.com/viewer?url=http%3A%2F%2Fsites.google.com%2Fsite%2Fjimandreou%2Fvarious%2FDietz%252CSleator-TwoAlgorithmsforMaintainingOrderinaList%25281988%2529.pdf%3Fattredirects%3D0%26d%3D1" style="font-family: Arial, Verdana, sans-serif;">Two Algorithms for Maintaining Order in a List (1988)</a><span style="font-family: Arial, Verdana, sans-serif;">, and then recently by Bender et al in </span><a href="https://docs.google.com/viewer?url=http%3A%2F%2Fsites.google.com%2Fsite%2Fjimandreou%2Fvarious%2FBender-DataStructuresforMaintainingSetPartitions%25282003%2529.pdf%3Fattredirects%3D0%26d%3D1" style="font-family: Arial, Verdana, sans-serif;">Two Simplified Algorithms for Maintaining Order in a List</a><span style="font-family: Arial, Verdana, sans-serif;">. </span><i style="font-family: Arial, Verdana, sans-serif;">These structures offer amortized O(1) time complexity for all these operations</i><b style="font-family: Arial, Verdana, sans-serif;"> </b><span style="font-family: Arial, Verdana, sans-serif;">(there are also versions offering O(1) worst case, but they are significantly more complex to implement, and likely to be slower in practice). </span><a href="http://code.google.com/p/transitivity-utils/source/browse/trunk/src/edu/bath/transitivityutils/OrderList.java" style="font-family: Arial, Verdana, sans-serif;">Here is my implementation of Bender's structure</a><span style="font-family: Arial, Verdana, sans-serif;">.</span><br />
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;"><br />
</span><br />
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;">So how can this structure solve the incremental updates problem? Let's see Dietz' solution of the case of trees. Lets draw another tree.</span><br />
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; font-family: 'Times New Roman';"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgFY-GCAplP9mF38HWxjvTFj2-x0c9dqKmYrd30w3DEB47bt9mr2FpLCEVe2EOAI5YHv7ImQJ5xocXD2ZO5eGt5zRBpliUaj109ed3X-02lULrBnlEZ2arUVZQj7Uk_7AAP9Hx15kDMJj0D/s1600/class_hierarchy3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="282" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgFY-GCAplP9mF38HWxjvTFj2-x0c9dqKmYrd30w3DEB47bt9mr2FpLCEVe2EOAI5YHv7ImQJ5xocXD2ZO5eGt5zRBpliUaj109ed3X-02lULrBnlEZ2arUVZQj7Uk_7AAP9Hx15kDMJj0D/s640/class_hierarchy3.png" width="640" /></a></span></span><br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;"><br />
</span><br />
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;">Okay, so this is the same tree, and I have labelled the nodes with intervals, with one catch - the intervals do not comprise integers, but symbolic names. What's the deal, you say? Here's the deal!</span><br />
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;"><br />
</span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhKf0u0dw-k3PWx8Y9YVIg77sGZNd9nvZS1ShSnZVTqzViNCDSUUrnJ3D2UtL-mIM57Kkh-VoD6Crt4BkFDQ34-3QHGQ2rs6UpG8WAn7TFKynPKOrbta2U-7eiJCmGcWG7IK5v81FAdvHe8/s1600/list.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="84" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhKf0u0dw-k3PWx8Y9YVIg77sGZNd9nvZS1ShSnZVTqzViNCDSUUrnJ3D2UtL-mIM57Kkh-VoD6Crt4BkFDQ34-3QHGQ2rs6UpG8WAn7TFKynPKOrbta2U-7eiJCmGcWG7IK5v81FAdvHe8/s640/list.png" width="640" /></a></div>
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;"><br />
</span><br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">That's it! The colors are there so you can easily match-up the respective nodes. This is a linked list, or more precisely, the order-maintainance list. Any two nodes in it define an interval. For example, [Pet_pre, Pet_post] interval (green in the picture) subsumes both Cat's and Dog's nodes - precisely because it is an ancestor of both! <b>Note that, internally, these list nodes <i>do</i> in fact contain integers that observe the total order </b>(e.g., are monotonically increasing from left to right)<b> so we can test in O(1) whether a node precedes another</b>. This is quite a simple structure, and there are very good algorithms for inserting a node in it - if there is no space between the integers of the adjacent nodes, an appropriate region of this list is renumbered.</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><b><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; font-family: 'Times New Roman'; font-weight: normal;"><span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><b>Update: </b>probably it's obvious, but better be specific. So how do we add a descendant? Let's say we want to add a graph node <b>X</b> that is a subclass of Pet. We simply create two list nodes, X_pre, X_post, and insert them right <i>before</i> Pet_post. That would result in a chain <b><span class="Apple-style-span" style="color: #cc0000;">Pet_pre</span></b> --> [whatever nodes were already here]<whatever here="" previously="" was=""> --> <b><span class="Apple-style-span" style="color: blue;">X_pre</span></b> --> <b><span class="Apple-style-span" style="color: blue;">X_post</span></b> --> <b><span class="Apple-style-span" style="color: red;">Pet_post</span></b>. </whatever></span></span></span><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; font-family: 'Times New Roman'; font-weight: normal;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif;">Or we could add these right <i>after</i> Pet_pre, it's equivalent really. (As a coincidence, both Dietz and I chose the first alternative, to insert child_pre and child_post right <i>before </i>parent_post. I had a reason for this actually, there is a tiny difference because I'm using Integer.MIN_VALUE as a sentinel value, but that would be way too much details for this post). Of course, to insert a node, say B, between two others, say A and C, we have to find an integer between label(A) and label(C), i.e. to make sure that we have label(A) < label(B) < label(C), without affecting any existing label relation. If label(A) = label(C) + 1 (i.e., consecutive, no space between them for a new node), we have some nodes to <i>make</i> space at the place of insertion. Compare with Dietz' Figure 4.1, in the "Maintaining order in a linked list" paper.</span></span></b></span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">While this might not seem such a big win for the case of trees, it is absolutely necessary in the case of graphs. This is what Agrawal et al missed! <b>Instead of using integers directly, they should have used nodes of an order-maintainance structure.</b> Why? Because when an interval does not have space to accommodate a new descendant, instead of widening the interval and then <b>scanning the whole graph to find appearances of those integers to fix them, we instead make only local changes in the order maintainance structure in O(1), <i><u>without even touching the graph</u></i>!</b></span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; line-height: 28px;"><br />
</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">You can visualize the difference in the following example.</span></span><br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi5hwF0JVTeani9k0hblYZhplU5K2AtNwrsyBNmKlXngJ45CqMkSOEgTVvGBgtbzE1nScr3x8W9HXqTwEf-qPyBg4SlMafUWrv7XStQrOk3S58M7t-pomnUw-tBTWgbf57VoRX27hIp7H1H/s1600/class_hierarchy5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="500" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi5hwF0JVTeani9k0hblYZhplU5K2AtNwrsyBNmKlXngJ45CqMkSOEgTVvGBgtbzE1nScr3x8W9HXqTwEf-qPyBg4SlMafUWrv7XStQrOk3S58M7t-pomnUw-tBTWgbf57VoRX27hIp7H1H/s640/class_hierarchy5.png" width="640" /></a></div>
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">The segmented edges are non-tree edges, so they propagate upwards the intervals, thus, the <b>H</b> node ends up having 4 distinct intervals. Now, if instead of nodes such as E_pre and E_post, we had numbers (say, (5,6)), what would have happened if we wanted to add a descendant under <b>E</b> but it had no space in its interval? We would fix the boundaries of E's interval, and we would have to search the graph to see where the old boundaries have been propagated (i.e. in nodes <b>F </b>and <b>H</b>). With the order maintainance structure, <b>this is not needed</b>. We locally renumber whichever node is required, and we do it <b>once - we only renumber E_pre and E_post once, and due to node sharing </b>(instead of copied values/integers!)<b>, it doesn't matter where these might have been propagated, all positions are <u>automatically</u> fixed too! <span class="Apple-style-span" style="font-weight: normal;">Contrast this to having to visit </span>F, G<span class="Apple-style-span" style="font-weight: normal;"> and </span>H<span class="Apple-style-span" style="font-weight: normal;">, find </span>E_pre<span class="Apple-style-span" style="font-weight: normal;">, </span>E_post<span class="Apple-style-span" style="font-weight: normal;"> in their intervals, and fix them in all places. Let alone if we had to renumber a series of intervals, and hunt the propagations of all of them in the graph, and so on...</span></b></span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><b><br />
</b></span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">Just for completeness, this is what the order maintainance list would look like, in the last example:</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">A_pre --> B_pre --> C_pre --> D_pre --> <b>E_pre</b> --> <b>E_post </b>--> D_post --> F_pre --> F_post --> C_post --> G_pre --> G_post --> B_post --> H_pre --> H_post --> A_post.</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">In this structure we perform the renumbering, not in the graph! Particularly, in some (typically small) region that contains the two nodes inside which we want to insert something.</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">So, there you go. This is the trick I (<b>re</b>)discovered on some Friday of last March, and ended up coding <a href="http://code.google.com/p/transitivity-utils">http://code.google.com/p/transitivity-utils</a> in the following weekend, which implements all of the above and more, so you don't have to. It is hard to believe that this went unnoticed for 20 years - and even harder to believe that the solution was there all along,</span></span><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif; line-height: 28px;"> waiting for someone to make the connection. </span><br />
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif; line-height: 28px;"><br />
</span><br />
<span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif; line-height: 28px;"></span><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px; font-family: Arial, Verdana, sans-serif; line-height: 28px;">Now that's something to ponder about. Oh, and thanks, Dietz, great work!</span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;"><br />
</span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Verdana, sans-serif;"><span class="Apple-style-span" style="-webkit-border-horizontal-spacing: 2px; -webkit-border-vertical-spacing: 2px;">If you managed to read all the way down to here, my thanks for your patience. That was way too long a post, but hopefully, you also earned something out of it. I regard this a very interesting story, and wish I was a better storyteller than this, but here you go. :)</span></span></div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com4tag:blogger.com,1999:blog-6958126065976802292.post-11022994738557181062010-07-25T12:13:00.000-07:002010-07-25T16:54:47.166-07:00Google File System - the 'bandwidth' problemI am reading the very interesting <a href="https://docs.google.com/viewer?url=http%3A%2F%2Fstatic.googleusercontent.com%2Fexternal_content%2Funtrusted_dlcp%2Flabs.google.com%2Fen%2F%2Fpapers%2Fgfs-sosp2003.pdf">Google File System</a> paper. It describes the situation back in 2003, not sure how much things have changed since then. Before moving to the subject of this post, lets sum up some interesting points of that paper first (only based on my certainly incomplete understanding).<br />
<br />
<br />
<ul><li>GFS clearly favors <b>appending</b> to files than <b>random access</b> writing. If all mutations of a file are appends, sequential readers (readers that scan the whole of the file - which represents the vast majority of cases) have also extra consistency guarantees: in the face of concurrent modifications, the only "bad" thing that they may see is the file ending prematurely. But everything up to that point is guaranteed to be well defined and consistent.</li>
<li>A GFS file can be used as an excellent producer-consumer queue! Multiple producers may append ("record append") to the file, with no need for extra synchronization/distributed locking. This is a weaker form of append - the client <b>does not choose </b>where the data end up to, <b>the primary replica server of that file chooses this</b>, and the clients get a guarantee that the update with occur <b>at least once</b> (well, not exactly once, but one can work-around this by uniquely naming the records, if they aren't already named so). This seems much simpler and better than either having to establish distributed locking protocols between producers, or letting them choose the offset in the file where their append should take place, and trying to resolve potential (and possibly very frequent) collisions.</li>
<li>Automatic <b>garbage collection</b> of orphaned chunks (file pieces) is implemented.</li>
<li><b>There are quite weak concurrency guarantees</b> <b>for writers that write <i>lots</i> of data</b>. The writer client needs to break up the data into acceptably small pieces, and each piece is written atomically - but if there are multiple writers doing the same, the final result is undefined, it could contain random fragments of the data of each writer.</li>
<li><b>File metadata updates are atomic</b>. This is particularly nice, consider the following case: a writer writes to a file, and <b>after </b> it's done writing, it <b>atomically </b>renames the file to a name which can then publish to readers. This is the analog of doing a <b>compare-and-swap </b>(CAS) in a shared memory multiprocessor (SMP), which, importantly, is the base of most <b>lock-free algorithms</b>. In particular, the writer that writes to a file (unknown to others) is like a thread doing thread-local computation, and only announce the result in the end via an atomic pointer update (<b>atomically</b> update a root pointer, if nobody has already changed it, or in GFS, if nobody has created the intended filename first).</li>
</ul><div>Now, on to the piece that found curious enough to make a post about. A couple of key points:</div><div><ul><li><b>When a client wants to write, it can pick whatever replica</b> to initiate this action (presumably the replica closer to it - and in Google's case, they can infer the "closeness" of two nodes by inspecting their IPs). </li>
<li><b>The data must be stored </b>(temporarily)<b> to all replicas before the client notifies the </b>(designated) <b>primary replica that the write should be committed. </b></li>
</ul></div><div><br />
</div><div>This leads to the problem: <b>How to move client's data to be written, to all replicas?</b> Google's answer is <b>through a chain (hamiltonian path) through all replicas, </b>starting at the replica that was contacted by the client. This is preferred over e.g. a dissemination tree, so as to bound the requirements of out-bandwidth of replicas - perhaps the best dissemination could be a star-like tree, but too much burden would be placed on the central node, and so on). </div><div><br />
</div><div>Here is a picture taken from the aforementioned paper. Note the thick arrows, they show the chain that data goes through, from the client and to all replicas. </div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiz5_ofp1Ka9d3HBvXoVSNOk6herYpshPl32GBx5qRzMRUExK4wpiPnPRitmIbmsep02IDPPDEC7XawQ_25EVlnVgGhYxvgOx3PQf1Uice-u2IbKZpWxEgJrRXfsETjB8DavBU5HWNTcd4R/s1600/Write+Control+and+Data+Flow.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="362" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiz5_ofp1Ka9d3HBvXoVSNOk6herYpshPl32GBx5qRzMRUExK4wpiPnPRitmIbmsep02IDPPDEC7XawQ_25EVlnVgGhYxvgOx3PQf1Uice-u2IbKZpWxEgJrRXfsETjB8DavBU5HWNTcd4R/s400/Write+Control+and+Data+Flow.png" width="400" /></a></div><div><b>But how do we choose the next replica in the chain?</b> I.e., why we send the data from Replica A to the Primary Replica and then to Replica B, rather than the other way around? Google is using a <b>simple, greedy rule: pick the replica </b>(that hasn't seen the data yet)<b> that is closest to the current one.</b></div><div><b><br />
</b></div><div>This looks like the well (ok, perhaps not so well) known graph theoretic problem, the <a href="http://en.wikipedia.org/wiki/Graph_bandwidth">Bandwidth Problem</a>. That is, we have a graph, and we want to create some linear order of the nodes, so that we minimize the total edge distances (e.g. if we put nodes side-by-side, the edges between them would have very low distance/cost). It's NP-Hard.</div><div><br />
</div><div>To visualize the bandwidth problem, I'm stealing a picture from the excellent Skiena's book, the <a href="http://www.amazon.com/exec/obidos/ASIN/1848000693/thealgorithmrepo">Algorithm Design Manual</a>, which I highly recommend. (I guess a free ad here should worth stealing a small picture :-/ ). (By the way, <a href="https://docs.google.com/viewer?url=http%3A%2F%2Fsites.google.com%2Fsite%2Fjimandreou%2Fvarious%2FCopingwiththeNP-HardnessoftheGraphBandwidthProblem.pdf">here is an excellent treatment of the problem</a> by Uriel Feige, very conveniently containing approximation algorithms and heuristics).</div><div><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgShBLpZt2FmAFx_EZXlYhOst15AlaqU_sj5AFCKDtCVTHChflr1csg7HwIkuJayIPU9aSFMSnxlGFxa6PY2MDrSk704knrxnWKXzWco7IcLh6IQSt1BTTt_DdxUMqr7NrqoOI7HgWbfhGk/s1600/bandwidth.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="161" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgShBLpZt2FmAFx_EZXlYhOst15AlaqU_sj5AFCKDtCVTHChflr1csg7HwIkuJayIPU9aSFMSnxlGFxa6PY2MDrSk704knrxnWKXzWco7IcLh6IQSt1BTTt_DdxUMqr7NrqoOI7HgWbfhGk/s400/bandwidth.png" width="400" /></a></div><div><br />
</div><div>Well, almost, but not <i>exactly</i> the same problem. The subtle difference is that in the Bandwidth Problem, we seek to minimize the distance/cost sum of <b>all</b> edges, while in the case of GFS, we only need to minimize the length of a single (any) Hamiltonian path (the picture just shows an easy case, where apart from a single path there are no more edges in the graph).</div><div><br />
</div><div>Ok, so I don't know yet how to state this problem. (While reading the paper, I thought it was the same problem, thus the title of this post). Let me do something else for now - lets try to be create an example that <b>maximizes the cost for GFS' heuristic</b>. Here is what I came up with (click to see larger size):</div><div><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhksRqEt1G5uZ8ftjDeFZDZy5KTy479RQm12pywxmGNaehuUrcw2nGXygCwfAJp7uqH9e0gvJqVl0sWvAJQwEu4aDOBqQMdDLm-Ad_e0lTbir9NNAF9k0s69eliU7l_mXA189w_ffoBl_Wu/s1600/bandwidth.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="77" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhksRqEt1G5uZ8ftjDeFZDZy5KTy479RQm12pywxmGNaehuUrcw2nGXygCwfAJp7uqH9e0gvJqVl0sWvAJQwEu4aDOBqQMdDLm-Ad_e0lTbir9NNAF9k0s69eliU7l_mXA189w_ffoBl_Wu/s400/bandwidth.png" width="400" /></a></div><div><br />
</div><div>I think that's the worst case scenario. The client chooses the replica in the middle, then we go to the right 1 step (because the one at the left is at distance 2), then we go to the left 3 steps (because the one at the right is at distance 4), and so on, going back and forth, with a total distance travelled = <b>1 + 3 + 7 + 15 = (2^1 - 1) + (2^2 - 1) + (2^3 - 1) + (2^4 - 1) = (2^5 - 1)</b> <b><span class="Apple-style-span" style="font-weight: normal;">=</span> 31</b>, or more generally, exactly<b> 2^N - 1!</b> (Of course, don't hold your breath on ever seeing such a topology in an actual GFS cluster!) The optimal solution here would be to go immediately to a boundary replica, either farthest left or right (choose the one closest), and then linearly visit the rest. That would yield a cost of<b> (1 + 4) + (1 + 2 + 4 + 8) = 20, </b>(1 + 4 to go to the farthest right replica, and then going all the way to the left) or more generally, exactly <b>2^(N - 1) + 2^(N - 3) </b>(it's fun to work this formula out!). </div><div><br />
</div><div>Now, <b>how much worse is Google's heuristic than the optimal solution? </b></div><div><b><br />
</b></div><div>It turns out, (if we assume that I did find the worst case scenario)<b>, <i>Google's solution is at most a factor of 8/5 (= 1.6) of the optimal solution!</i><span class="Apple-style-span" style="font-size: x-large;"> </span><span class="Apple-style-span" style="font-size: small;"><span class="Apple-style-span" style="font-weight: normal;">(Well, sure enough. To compare 2^N to 2^(N-1) + 2^(N-3), divide everything by 2^N, so we have 1 compared to 1/2 + 1/8, or 5/8). </span></span><span class="Apple-style-span" style="font-weight: normal;">Wow! That's extremely good for something as simple! I didn't expect to find such an exact result - one can also <b><span class="Apple-style-span" style="font-weight: normal;">compute this easily</span></b> via <a href="http://www.wolframalpha.com/input/?i=lim+((2^n+-+1)+/+((2^(n+-+1)+%2B+2^(n+-+3)))+as+n-%3Einfinity">WolframAlpha</a>, which is <i>way</i> too cool in this kind of problems.</span></b></div><div><b><span class="Apple-style-span" style="font-weight: normal;"><br />
</span></b></div><div>Nice, nice, nice. I thought I would be find something ludicrously bad (in a completely unrealistic scenario), but it turns out, that's just 1.6 times the optimal solution at most!</div><div><br />
</div><div><br />
</div><div>/sheer happy - we haz it :)<br />
<br />
<b><span class="Apple-style-span" style="font-size: x-large;">Addendum:</span></b><br />
<span class="Apple-style-span" style="font-size: x-large;"><b><br />
</b></span><br />
Ah, the art of creating good corner case examples. It turns out the above is not the worst case, there is a worse than that, and quite simpler too (I had thought about this earlier, but for some reason I decided that forcing the algorithm to continually go back and forth would be the most expensive).<br />
<br />
Consider this example (again, click to see in full size):<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLT_A5DIDAAligBOAPBmZ3bDSyzPMgWvHmJjEF1q8_xMNCNY4nr9VJV9OzTrJGiVNwpiXhyjS5kR-JRTDllwO6M1A9bkZaRo0GDiikxnXOMtLpnfy4jQ6UWkv6n7whQxoK_HAv_4ZFFaqO/s1600/bandwidth.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="112" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgLT_A5DIDAAligBOAPBmZ3bDSyzPMgWvHmJjEF1q8_xMNCNY4nr9VJV9OzTrJGiVNwpiXhyjS5kR-JRTDllwO6M1A9bkZaRo0GDiikxnXOMtLpnfy4jQ6UWkv6n7whQxoK_HAv_4ZFFaqO/s400/bandwidth.png" width="400" /></a></div>Each adjacent replica pair is separated by unit distance, while the last two are separated by two. We can make the path arbitrarily long, easily forcing the algorithm to choose a path which is a factor of <b>2 - ε </b>longer than the optimal. And this is to be further restrained: I'm only considering geometric graphs, i.e. graphs where the <a href="http://en.wikipedia.org/wiki/Triangle_inequality">triangle inequality</a> holds. <b>I have next to no idea whether actual network topologies resemble geometric graphs</b>, and certainly one could construct much worse examples in graphs where the notion of distance is completely arbitrary (but distances in a network topology certainly isn't an arbitrary function). It's too late in the night to worry about that, so lets stop here hoping I'm still making some sense. :)<br />
<br />
By the way, I recently bought <a href="http://www.amazon.com/Approximation-Algorithms-Vijay-V-Vazirani/dp/3540653678">Vazirani's Approximate Algorithms</a> book. Neat, refreshing read, and highly recommended.</div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com0tag:blogger.com,1999:blog-6958126065976802292.post-3463234837845029282010-06-21T07:02:00.000-07:002010-06-21T07:02:30.536-07:00My oldies but goldies pet projectsFinally! I took the time to upload some of my old pet projects on google code. Briefly:<br />
<br />
<br />
<ul><li><a href="http://code.google.com/p/flexigraph/">Flexigraph</a>: a life-saver of a graph library. :) Packed with several unique features, but I have no time to comment them. Especially the Traverser API scoffs at all other java graph libraries of today (and this is several years old by now).</li>
<li><a href="http://code.google.com/p/jbenchy/">JBenchy</a>: (my friends know this by the imaginative name "aggregator"). This is another life-saver if you are in the business of doing benchmarks/experiments and want a systematic way to store and analyze your collected points. Leverages the sheer expressive and analytical power of SQL GROUP BY statements, yet it hides all SQL from you so you can concentrate on your benchmark itself. It can also create nice diagrams for you, if you need some help with visualization.</li>
<li><a href="http://code.google.com/p/memory-measurer/">MemoryMeasurer</a>: Another uncharacteristically exotic name for a project! This little gem can compute the memory footprint of an arbitrary object graph / data structure. Did you ever wonder how much space does a default HashMap takes? Or an ArrayList of 5 HashMaps? Or whatever? Well, this is the tool for you. Also note that you can use it with JBenchy to create benchmarks for data structures, if this happens to be your thing. Oh, by the way, a new HashMap() takes 120 bytes, in case you <i>did</i> wonder.</li>
</ul><div>Good! All my pets in line, with a new home. Enjoy :)</div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com1tag:blogger.com,1999:blog-6958126065976802292.post-512668495167276882010-05-06T09:30:00.000-07:002010-05-06T10:06:58.248-07:00Motivating Divide and Conquer paradigmJust the other day I went in my old University, met former teachers and collaborators... fun!<br />
<br />
I also attended a lecture on algorithms. The topic: Divide and Conquer.<br />
<br />
The professor presented a very simple example to make the technique apparent. The problem? Find the minimum element of a list. Instead of doing the usual (in pseudocode):<br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">result = +oo;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">foreach e in list {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> result = min(e, result)</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<br />
The divide 'n conquer approach would be:<br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">function min(list) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> if (list.size == 1) return array[0]</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> else {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> k = list.length / 2</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return min(</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> findMin(list.subList(1, k)), </span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> findMin(list.subList(k+1, list.size)))</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<br />
One could ask, "what's the point". In this example, this doesn't sound important at all. A student with good practical experience with programming would readily recognize that the latter, sophisticated approach is likely to perform worse than the straight-forward iteration. Indeed, a student there asked, "do we gain any gain in time complexity by following the latter approach in this example?". Unfortunately, the answer was no, both <span class="Apple-style-span" style="font-family: inherit;">versions are O(n), so the exercise "is" pointless. </span><br />
<span class="Apple-style-span" style="font-family: inherit;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: inherit;">Quite some years after the period when I was an undergraduate student, and reflecting on that experience, that was my main gripe with how Computer Science was being taught. Without proper motivation! The student must somehow "guess" by him/herself the importance of the covered topics. An example dialogue that could ensue between students: "-Hey, what did you learn today? -Nothing much, something called 'divide and conquer', it's just a way to create complicated solutions when simple and as good solutions already exist".</span><br />
<span class="Apple-style-span" style="font-family: inherit;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: inherit;">Since I was attending, I thought I should intervene and give the very, very, very imporant motivation for learning this algorithm design paradigm. The reason is the all-too-known fact that CPUs have stopped getting faster, and they only become more numerous. This can be easily recognized, but it also has a tremendous implication in how we design software. Even for this simplistic problem, the first method of computing the minimum element is <b>doomed</b>. It may not fail tomorrow, it might not fail next year or the year after, but it's doomed nevertheless. Imagine you have a billion elements of which to find the minimum. Also imagine your run-of-the-mill computer has hundreds of processing cores (by the way, we should stop calling them CPUs/<b>Central</b> Processing Units, how "central" is something you have hundreds of?).</span><br />
<span class="Apple-style-span" style="font-family: inherit;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: inherit;">Here is the expression that the first method is trying to evaluate:</span><br />
<span class="Apple-style-span" style="font-family: inherit;"><br />
</span><br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEifnjyUJ_zashEiNkiW_kfRSyY7L-8_zSRQx0jpLzxNDNCGQ9pM9x3dXDEPqdRKIcNpGKSeZboKFtsPoARUV49udmp3Bni_HIo6HTenrkdIqxD_T-I7HnZ9Orrlsg8VthgYMc4G-WX4mEHi/s1600/iterated.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEifnjyUJ_zashEiNkiW_kfRSyY7L-8_zSRQx0jpLzxNDNCGQ9pM9x3dXDEPqdRKIcNpGKSeZboKFtsPoARUV49udmp3Bni_HIo6HTenrkdIqxD_T-I7HnZ9Orrlsg8VthgYMc4G-WX4mEHi/s400/iterated.png" width="282" /></a></div><span class="Apple-style-span" style="font-family: inherit;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: inherit;"><br />
</span><br />
I.e., you first find the minimum of the first two elements, then you find the minimum of that and the third element, then the minimum of that and the fourth element, etc, etc. The point is, the <b>Kth</b> call (K>1) to min() always must wait first for the result of the <b>(K-1)th </b>call of min() to become available. Each min() invocation takes (say) a unit of time, so the final computation cannot consume less that K time units, no matter whether you have a single core or thousands of them. The so called "critical path" (the longest path of things that must happen sequentially) as is also apparent in the diagram, has length K. Bad.<br />
<br />
This is what happens with divide and conquer instead:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh5RCiRjl3M-fL0Oqo7XdP68i5e3rodRvxKnatI3cIX35WDZjTPNyRpaKs-rY1yeJLhbf1StTfx0b0gt3YLJZoLMNAcYhBSZb_mdn1Zm_Y05DN23WS2YiYEVhyphenhyphenon9wF91nlv-hmTku_ExS5/s1600/divide_conquer.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh5RCiRjl3M-fL0Oqo7XdP68i5e3rodRvxKnatI3cIX35WDZjTPNyRpaKs-rY1yeJLhbf1StTfx0b0gt3YLJZoLMNAcYhBSZb_mdn1Zm_Y05DN23WS2YiYEVhyphenhyphenon9wF91nlv-hmTku_ExS5/s400/divide_conquer.png" width="400" /></a></div><br />
Still, the root depends to two other min() invocations, and must wait for them before evaluating itself. But those two are not dependent on each other, <b>they may run in parallel. </b>The critical path here has length only logK. Thus, divide and conquer can solve this problem in <b>O(logN) </b>instead of <b>O(N)</b>. Without leaving your excess of processing cores to sit (and waste energy) idly.<br />
<br />
As I explained to the student, this epitomizes programming of the future. Of course that's a hyperbole, but hyperboles are useful to drive a point home. And it is certainly better than present something dry to the student, without any hint of its importance - that's the recipy to make him/her <b>not </b>pay attention, and soon forget about this weird, exotic thingy.<br />
<br />
That's all for now! Oh, and if you want to actually implement algorithms like this, and you code in Java, the <a href="http://gee.cs.oswego.edu/dl/concurrency-interest/index.html">fork/join framework</a> is something you'll definitely want to learn.Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com0tag:blogger.com,1999:blog-6958126065976802292.post-33306932742696453112010-04-13T17:02:00.000-07:002010-04-13T17:02:03.752-07:00My solution to Matrix-Chain-Order problem (Chapter 15 of CLRS)<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">For practice, I tried solving the problem "Matrix-Chain-Order" that appears on section 15.2 of </span><a href="http://mitpress.mit.edu/catalog/item/default.asp?tid=8570&ttype=2"><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Introduction to Algorithms</span></a><span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"> (that's the chapter on Dynamic Programming). In short, one gets a list of (compatible) matrices, A1, A2, A3... An, and the problem is to compute the optimal order for creating their product. </span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">I liked my solution, so I'm posting this just for the record. This should be helpful if one is reading that section and looks for a Java implementation of that problem (in order to compare with his own solution of course :)). To make it tougher, I tried it writing this first on paper, then in my IDE, to see how many errors would slip in the paper version. There were two: a single off-by-one error in the inner loop (damn!), and that I forgot some components of the cost of a particular multiplication expression.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">It creates optimal multiplication expressions of increasing width. Initially width == 1, and we just have the leaves, the matrixes themselves. Next, we find the optimal expressions of width == 2, but there is only one order to multiple 2 arrays, so nothing special happens. After that, things get more interesting, since we get to create various possible trees for each sequence of matrixes, and retain the best.</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Amazingly, it is exactly one year (to the day!) ago that I posted a same exercise in tree building (enumerating binary trees, also via dynamic programming): <span class="Apple-style-span" style="font-family: 'Times New Roman';"><a href="http://code-o-matic.blogspot.com/2009/04/wonderful-programming-exercise.html">http://code-o-matic.blogspot.com/2009/04/wonderful-programming-exercise.html</a></span></span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">I think I need more diversity :)</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: Arial, Helvetica, sans-serif;">Anyway. The main method is this:</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span><br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public static void main(String[] args) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Op op = matrixChainOrder(Arrays.asList(</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> new Matrix(30, 35),</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> new Matrix(35, 15),</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> new Matrix(15, 5),</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> new Matrix(5, 10),</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> new Matrix(10, 20),</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> new Matrix(20, 25)));</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> System.out.println(op);</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> System.out.println("Cost: " + op.cost());</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span><br />
<div><br />
</div><div>And it prints:</div><div><br />
</div><div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">(([30 X 35] * ([35 X 15] * [15 X 5])) * (([5 X 10] * [10 X 20]) * [20 X 25]))</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">Cost: 15125</span></div><div><br />
</div><div>(This mimicks the example and solution of the book, but it also creates the expression of the multiplication, easy to pretty-print and ready to be computed).</div><div><br />
</div><div>The full code:</div><div><br />
</div><div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">import java.util.*;</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">public class Matrixes {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public static void main(String[] args) {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Op op = matrixChainOrder(Arrays.asList(</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> new Matrix(30, 35),</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> new Matrix(35, 15),</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> new Matrix(15, 5),</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> new Matrix(5, 10),</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> new Matrix(10, 20),</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> new Matrix(20, 25)));</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> System.out.println(op);</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> System.out.println("Cost: " + op.cost());</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> static Op matrixChainOrder(List<matrix> matrixes) {</matrix></span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Map<interval, op=""> optima = new HashMap<interval, op="">();</interval,></interval,></span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> for (int i = 0; i < matrixes.size(); i++) {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> optima.put(new Interval(i, i), new Leaf(matrixes.get(i)));</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> for (int width = 1; width < matrixes.size(); width++) {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> for (int offset = 0; offset < matrixes.size() - width; offset++) {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Op best = DUMMY;</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> for (int cut = 0; cut < width; cut++) {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Op left = optima.get(new Interval(offset, offset + cut));</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Op right = optima.get(new Interval(offset + cut + 1, offset + width));</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Op mul = new Mul(left, right);</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> if (mul.cost() < best.cost()) {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> best = mul;</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> optima.put(new Interval(offset, offset + width), best);</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return optima.get(new Interval(0, matrixes.size() - 1));</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> private static final Op DUMMY = new Op() {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public int cost() { return Integer.MAX_VALUE; }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public Matrix compute() { throw new AssertionError(); }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public int rows() { throw new AssertionError(); }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public int columns() { throw new AssertionError(); }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> };</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> private static class Interval {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> final int begin;</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> final int end;</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Interval(int begin, int end) { this.begin = begin; this.end = end; }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public boolean equals(Object o) {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> if (!(o instanceof Interval)) return false;</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Interval that = (Interval)o;</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return this.begin == that.begin && this.end == that.end;</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public int hashCode() { return 31 * begin * (17 + end * 31); }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public String toString() { return "[" + begin + ".." + end + "]"; }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">class Matrix {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> final int rows; final int columns;</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Matrix(int rows, int columns) { this.rows = rows; this.columns = columns; }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> int rows() { return rows; }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> int columns() { return columns; }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public String toString() { return "[" + rows + " X " + columns + "]"; }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">interface Op {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> int cost();</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Matrix compute();</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> int rows();</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> int columns();</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">class Leaf implements Op {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> final Matrix matrix;</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Leaf(Matrix matrix) { this.matrix = matrix; }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public int cost() { return 0; }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public Matrix compute() { return matrix; }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public int rows() { return matrix.rows(); }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public int columns() { return matrix.columns(); }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public String toString() { return matrix.toString(); }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">class Mul implements Op {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> final Op left;</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> final Op right;</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> Mul(Op left, Op right) {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> this.left = left; this.right = right;</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public int rows() {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return left.rows();</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public int columns() {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return right.columns();</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public int cost() {</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return left.rows() * left.columns() * right.columns() + left.cost() + right.cost();</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public Matrix compute() { throw new UnsupportedOperationException("later"); }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> public String toString() { return "(" + left + " * " + right + ")"; }</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span></div></div></div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com1tag:blogger.com,1999:blog-6958126065976802292.post-26220376357408023052010-03-15T15:34:00.000-07:002010-03-26T03:41:23.670-07:00Announcing transitivity utilities projectCheck out my new project: <a href="http://code.google.com/p/transitivity-utils/">http://code.google.com/p/transitivity-utils/</a><br />
<br />
This is the recycled message I sent about this at the guava mailing list:<br />
<div><br />
</div><div>--------</div>I have implemented some new data structures that may be of interest to someone. It is about maintaining transitive relations efficiently, both in terms of memory and time complexity. Internally it uses interval-encoding for elements, which for example can handle reachability queries in trees in just O(1) time and O(1) memory per element. It's not good for graphs that are close to full bipartite graphs - then memory degenerates to O(N) per element and O(logN) for testing reachability.<br />
<br />
<div>Historically, the motivation for this line of research has been encoding inheritance relations in knowledge bases. (For a more familiar example, this can be used to directly implement the instanceof operator of Java, but I don't suggest that!).<br />
<br />
The central type amounts to:<br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">TransitiveRelation {<br />
void relate(E subject, E object);<br />
boolean areRelated(E subject, E object);<br />
}</span><br />
<br />
<br />
This should be considered for any algorithm that relies on reachability queries.<br />
<br />
I regard the API rather stable (except for I might need better names here and there).<br />
----<br />
Boy, the effort it takes.<br />
<br />
Long story short, I believe I've found the sweetest spot in the design space for this problem. It contains magic sauce found nowhere else. The gist of the underlying solution is so (deceptively?!) simple that it's hard not to ask: "how could <i>that </i>be overlooked for 20 years?". The details will wait for a future post (but the source is there already).</div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com0tag:blogger.com,1999:blog-6958126065976802292.post-82328863778403939252010-02-19T04:42:00.000-08:002010-02-19T05:26:44.753-08:00Find the average between two ints (facing possible overflows/underflows)How do you compute the average between two ints in Java?<br />
<br />
How about...<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">(x + y) / 2</span><br />
<br />
Well, that doesn't work when (x + y) can overflow, and in fact this buggy implementation was lurking in the binary-search and mergesort implementations of JDK till recent years. (Obligatory Josh Bloch link: <a href="http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html">http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html</a>)<br />
<br />
It's an interesting puzzle for you to meditate and try out yourself - it looks simple, but it's not. I have yet to find a simple solution that works without assumptions on x, y - just any ints.<br />
<br />
Blochs first solution is this:<br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">x + (y - x) / 2</span><br />
<br />
I.e. starting with x and adding half the distance to <b>y</b>. Only that this assumes that x,y > 0, otherwise y-x can itself overflow!<br />
<br />
The second solution:<br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">(x + y) >>> 1</span><br />
<br />
Pretty nifty. If (x + y) <i>does</i> overflow, the high bit of the number (which determines the sign) will become one, i.e. negative, but >>> 1 will do the division and put a zero there. But what if (x + y) underflows (x, y are big negative numbers)? Oops.<br />
<br />
So neither solution works for all cases.<br />
<br />
Still working out a solution. In my case, I only need that <span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">average(x, y) != x && average(x, y) != y</span>, when x and y are not consecutive ints. Any helping hand appreciated :)<br />
<br />
My current solution:<br />
<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">static int avg(int x, int y) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return diffSign(x, y) ? (x + y) / 2 : x + (y - x) / 2;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">static boolean diffSign(int x, int y) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return (x ^ y) < 0;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<div><br />
</div><div><i>diffSign</i> returns true iff x and y do not have the same sign. In that case only, (x + y) is safe. Otherwise, (y - x) is safe, so I go for that option. This solution works for corner cases (like Integer.MIN_VALUE) too. Well, I don't think I can get it any simpler (assuming it's really correct). Can you?<br />
<br />
-edit-<br />
It turns out there is a much more elegant solution, which is provably correct, <a href="http://docs.google.com/viewer?url=http://joyofprogramming.com/Docs_ColumnArticles/26-JoP-Feb-09.pdf">found here</a>.<br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">static int avg(int x, int y) {</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"> return (x & y) + (x ^ y) / 2;</span><br />
<span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;">}</span><br />
<br />
Wow!..</div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com8tag:blogger.com,1999:blog-6958126065976802292.post-23190935881742087682010-01-13T14:47:00.000-08:002010-01-13T14:47:35.731-08:00Traits defining equals, combined with case classesI just contributed a <a href="http://stackoverflow.com/questions/1332574/common-programming-mistakes-for-scala-developers-to-avoid/2060849#2060849">"common programming mistake for Scala developers"</a>, in the relevant <a href="http://stackoverflow.com/questions/1332574/common-programming-mistakes-for-scala-developers-to-avoid">thread</a> over at <a href="http://stackoverflow.com/">stackoverflow</a> (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.Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com0tag:blogger.com,1999:blog-6958126065976802292.post-38436313833467743412010-01-08T14:46:00.000-08:002010-01-11T00:06:59.208-08:00Thoughts on Actors<a href="http://old.nabble.com/Guidelines-for-applying-Akka-in-practical-solutions-td27077976.html">This discussion</a> (started today) on the scala mailing list relates to understanding the usefulness of <a href="http://akkasource.org/">Akka</a>, and more generally, <a href="http://www.scala-lang.org/node/242">actors</a>.<br />
<br />
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.<br />
<br />
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 <a href="http://java.sun.com/javase/6/docs/api/java/util/concurrent/BlockingQueue.html">BlockingQueues </a>(or, soon, <a href="http://gee.cs.oswego.edu/dl/jsr166/dist/jsr166ydocs/jsr166y/TransferQueue.html">TransferQueues</a>). There already exists the <a href="http://java.sun.com/javase/6/docs/api/java/util/concurrent/Executor.html">executor</a> framework, and the <a href="http://gee.cs.oswego.edu/dl/papers/fj.pdf">fork/join framework</a>, to provide thread pools and fine-grained parallelism.<br />
<br />
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 <a href="http://lamp.epfl.ch/~phaller/doc/haller07coord.pdf">Haller/Odersky</a> 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. <b>(Edit</b>: Probably I'm wrong to classify the last case as a race condition, it's likely just a data race, following the nomeclature of <a href="http://www.javaconcurrencyinpractice.com/">JCiP</a><b>)</b>.<br />
<br />
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 <a href="https://lampsvn.epfl.ch/trac/scala/browser/scala/trunk/src/actors/scala/actors/scheduler/ForkJoinScheduler.scala">ForkJoinScheduler</a> (i.e. using the fork/join framework), this quotation from the javadocs of <a href="http://gee.cs.oswego.edu/dl/jsr166/dist/jsr166ydocs/jsr166y/ForkJoinPool.html">ForkJoinPool </a>is interesting:<br />
<br />
<blockquote>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.<br />
</blockquote><br />
This leads to some obvious questions which I can't answer easily at all:<br />
<br />
<ol><li>What are the (performance) implications of using (blocking) IO in actors? (I haven't seen similar warnings given to actors users).</li>
<li>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?</li>
</ol><br />
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 <a href="http://gee.cs.oswego.edu/dl/jsr166/dist/jsr166ydocs/jsr166y/ForkJoinTask.html#join()">join()</a> subtasks, to go and execute other tasks while waiting (via <a href="http://gee.cs.oswego.edu/dl/jsr166/dist/jsr166ydocs/jsr166y/ForkJoinTask.html#helpJoin()">helpJoin()</a>).<br />
<br />
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.Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com4tag:blogger.com,1999:blog-6958126065976802292.post-6061640918166368812009-12-26T04:35:00.000-08:002010-01-06T18:22:08.320-08:00Barbara Liskov talk and vintage photo<div style="text-align: left;">Few days earlier I was happy to see this talk given by Barbara Liskov:<br />
</div><br />
<a href="http://www.infoq.com/presentations/liskov-power-of-abstraction">http://www.infoq.com/presentations/liskov-power-of-abstraction</a><br />
<br />
Few days earlier I submitted a paper to <a href="http://www.eswc2010.org/">ESWC10</a> (<a href="http://sites.google.com/site/jimandreou/publications"> found here </a>, 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). <br />
<div><br />
</div><div>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 <i>goto </i>statement was evil or not!<br />
</div><div><br />
</div><div>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!<br />
</div><div style="text-align: left;"><br />
</div><div style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjUpY9ncGG-JB3ufB9MYVyBMCsWUmC8edmHtbWsMEkMWPO2EY8lcqc79NwdktLWVBWHI0CfpDZHoLjee2NWdtGIVIockCQlv_npiY2MSTyMUlfAWrcqfX8fGVEHiQrOA6cxZ6fY9jW4o3UZ/s1600-h/barbara_liskov.jpg" onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"><img alt="" border="0" id="BLOGGER_PHOTO_ID_5419526393074324914" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjUpY9ncGG-JB3ufB9MYVyBMCsWUmC8edmHtbWsMEkMWPO2EY8lcqc79NwdktLWVBWHI0CfpDZHoLjee2NWdtGIVIockCQlv_npiY2MSTyMUlfAWrcqfX8fGVEHiQrOA6cxZ6fY9jW4o3UZ/s400/barbara_liskov.jpg" style="cursor: pointer; display: block; height: 223px; margin-bottom: 10px; margin-left: auto; margin-right: auto; margin-top: 0px; text-align: center; width: 400px;" /></a><br />
</div><div style="text-align: center;"><br />
</div><div style="text-align: left;">I will leave the photo uncommented - it speaks for itself. -edit: well, I commented it after all, see below :)<br />
</div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com3tag:blogger.com,1999:blog-6958126065976802292.post-80218172011437991042009-10-20T12:30:00.001-07:002009-10-20T12:53:52.203-07:00Beware of recursive set union building!The excellent <a href="http://code.google.com/p/google-collections/">Google collections</a> library spoils many of us, but that doesn't mean we can afford not being alert using it! <div><br /></div><div>Observe how easy it is, for example, to create the (live) union of two sets: <a href="http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Sets.html#union(java.util.Set, java.util.Set)">Sets.union(setA, setB)</a>.</div><div><br /></div><div>One might be tempted to write code like the following, to make the union of all sets in "S":</div><pre><br />Set<E> union = Collections.emptySet();<br /> for (Set<E> someSet : S) {<br /> union = Sets.union(someSet, union)<br />}<br /></pre>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).<br /><div><br /></div><div>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.</div><div><br /></div><div>To understand the issue, consider the algorithm for computing the elements of the union of sets A and B:</div><pre><br />report all elements in A<br />for all items x in A<br /> if !b.contains(x)<br /> report x<br /></pre><br />Now consider this union: <b>union(A, union(B, union(C, D)))</b>, graphically shown below.<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhshOxXMmGnXGDNz0p6FcCMg8XHvUktx_2ndszFBxUjsmC1w3Ws1D_4-v-ICTUxul-S7YnDtjBrLcMWXWOtsJe3Cgi9S9XD6lsdGH2SOJORXsveBffUd1VE3Sq-5HCXwfzh5i9W20JCFcK7/s1600-h/tree.png"><br /><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 180px; height: 270px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhshOxXMmGnXGDNz0p6FcCMg8XHvUktx_2ndszFBxUjsmC1w3Ws1D_4-v-ICTUxul-S7YnDtjBrLcMWXWOtsJe3Cgi9S9XD6lsdGH2SOJORXsveBffUd1VE3Sq-5HCXwfzh5i9W20JCFcK7/s320/tree.png" border="0" alt="" id="BLOGGER_PHOTO_ID_5394770434681636834" /></a><br /><br /><div>This is how the union's iterator would report its elements:</div><div><br /></div><div>1) Iterate and report all elements of A</div><div>2) Iterate elements of B, if they are not in A, report them</div><div>3) Iterate elements in C, if they are not in B, then if they are not in A, report them</div><div>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</div><div><br /></div><div>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).</div><div><br /></div><div>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 :)</div><div><br /></div><div>Till next time,</div><div>Bye bye!</div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com1tag:blogger.com,1999:blog-6958126065976802292.post-41819739294438543592009-10-08T19:18:00.001-07:002009-10-08T19:23:41.838-07:00Using JConsole to monitor...JConsole<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjSsyCvjvqrGo8saQRf-_mFLioO9us6stQnUNBZqXZYBy6f5Rq5zSb5UZW1z9T0SGzRY_jPY18ILtSLExz80hNfbeF8-jjPofzlvLxDRWn2qQ4EssuMwCKwOV9lWJYT9YkcxW6D-t8tKJ6g/s1600-h/jconsole.JPG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px; height: 266px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjSsyCvjvqrGo8saQRf-_mFLioO9us6stQnUNBZqXZYBy6f5Rq5zSb5UZW1z9T0SGzRY_jPY18ILtSLExz80hNfbeF8-jjPofzlvLxDRWn2qQ4EssuMwCKwOV9lWJYT9YkcxW6D-t8tKJ6g/s320/jconsole.JPG" border="0" alt="" id="BLOGGER_PHOTO_ID_5390419480124423570" /></a><br />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 :)<br /><br /><div>For what it worths, here is the stack trace:</div><div><pre><br />sun.tools.jconsole.Worker.add(Worker.java:56)<br />sun.tools.jconsole.Tab.workerAdd(Tab.java:73)<br /> - locked sun.tools.jconsole.ThreadTab@c829e3<br />sun.tools.jconsole.ThreadTab.valueChanged(ThreadTab.java:316)<br />javax.swing.JList.fireSelectionValueChanged(JList.java:1765)<br />javax.swing.JList$ListSelectionHandler.valueChanged(JList.java:1779)<br />javax.swing.DefaultListSelectionModel.fireValueChanged(DefaultListSelectionModel.java:167)<br />javax.swing.DefaultListSelectionModel.fireValueChanged(DefaultListSelectionModel.java:137)<br />javax.swing.DefaultListSelectionModel.setValueIsAdjusting(DefaultListSelectionModel.java:668)<br />javax.swing.JList.setValueIsAdjusting(JList.java:2110)<br />javax.swing.plaf.basic.BasicListUI$Handler.mouseReleased(BasicListUI.java:2788)<br />java.awt.AWTEventMulticaster.mouseReleased(AWTEventMulticaster.java:273)<br />java.awt.Component.processMouseEvent(Component.java:6263)<br />javax.swing.JComponent.processMouseEvent(JComponent.java:3267)<br />java.awt.Component.processEvent(Component.java:6028)<br /></pre><pre>I'm monitoring a process that should take about 2 hours, so yes, I do have a lot of time in my hands :)</pre></div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com0tag:blogger.com,1999:blog-6958126065976802292.post-52556177880705694232009-09-18T14:29:00.000-07:002009-09-18T14:41:31.306-07:00Rapidshare can compress any file to just 16 bytes!!!Or so it <a href="http://rapidshare.com/privacypolicy.html">claims</a>:<div><br /></div><div><span class="Apple-style-span" style=" ;font-family:arial, sans-serif;font-size:13px;"><blockquote>there is a program which calculates the MD5 checksum for each file immediately after the upload. <b>The MD5 checksum is a 16 bytes value</b> 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 <b>delete the file</b> upon notification and <b>a</b><b>dd the MD5 checksum to a blacklist</b><b>, so the same file cannot be uploaded again</b>.</blockquote></span></div><div><span class="Apple-style-span" style="font-family:arial, sans-serif;font-size:100%;"><span class="Apple-style-span" style="font-size:13px;"><br /></span></span></div><div><span class="Apple-style-span" style="font-family:arial, sans-serif;font-size:100%;"><span class="Apple-style-span" style="font-size:13px;">(Emphasis mine).</span></span></div><div><span class="Apple-style-span" style="font-family:arial, sans-serif;font-size:100%;"><span class="Apple-style-span" style="font-size:13px;"><br /></span></span></div><div><span class="Apple-style-span" style="font-family:arial, sans-serif;font-size:100%;"><span class="Apple-style-span" style="font-size:13px;">Now, I really, really, <i>really</i> want to see their blacklist implementation, since obviously it holds the key to the dark art of <span class="Apple-style-span" style="font-style: italic; ">infinite compression, <span class="Apple-style-span" style="font-style: normal;">which is</span><span class="Apple-style-span" style="font-style: normal; "> the Holy Grail Of Computer Science, the Universe, and Everything. Yes, the notorious Holy Grail that nobody wants to touch because <a href="http://matt.might.net/articles/why-infinite-or-guaranteed-file-compression-is-impossible/">apparently it's the favorite pooping place</a> for some very special pigeons...</span></span></span></span></div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com0tag:blogger.com,1999:blog-6958126065976802292.post-81917064813130075732009-09-14T12:35:00.000-07:002009-10-04T09:36:00.365-07:00JComboBox pure crazinessSomeone asked me why his ItemListener, attached to a JComboBox, was getting <b>two</b> events when he selected something on it. Weird.<div><br /></div><div><span class="Apple-style-span">I looked up JComboBox' javadocs, just to be sured, and....</span><a href="http://java.sun.com/j2se/1.5.0/docs/api/javax/swing/JComboBox.html#addItemListener(java.awt.event.ItemListener)">this is what I found</a><span class="Apple-style-span">:</span></div><div><br /></div><div><span class="Apple-style-span" style=" ;font-family:'times new roman';"></span></div><blockquote><div><span class="Apple-style-span" style=" ;font-family:'times new roman';">Adds an <code>ItemListener</code>.</span></div><div><span class="Apple-style-span" style=" ;font-family:'times new roman';"><p><code>aListener</code> will receive one <b>or two</b> <code>ItemEvent</code>s when the selected item changes.</p></span></div><div></div></blockquote><div>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 <i>feature</i> instead. Way to go!</div><div><br /></div><div><span class="Apple-style-span" style=" ;font-family:'times new roman';"><p></p></span></div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com2tag:blogger.com,1999:blog-6958126065976802292.post-91583388344181499242009-07-29T17:35:00.000-07:002009-10-23T02:11:47.903-07:00The best way to enumerated directed acyclic graphs<div style="text-align: center;"><br /></div><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh_v0wuU8xJKrMZE2grCgF05i2rwkrbPMtcRkrmDJ2Q3Km00SzFx4fx7HH_27B5bhwvsM3JD_6N08EQhuIija6t9DTb1hHnJgxRSWcolxZpYZgfjRXQ6_jn6GxHUGnTY44muwegX8eG_B_Z/s1600-h/numbered_matrix.PNG"></a><div style="text-align: center;"><br /></div><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi-Dj0ZnjvC28UfwLRcR7MtsP_hVLCwnzBaAlU3tYJm7FjMfkENAl2u2XpNvzII-5N6rV42dXMipoHuvXtVST9cFr9dpD744UvzCWlg1KTJgKqoSVfrNB3Nd_XE0DYnCdjEYE3uI532727Y/s1600-h/matrix.png"></a><div>Here is a tricky problem for the algorithmically oriented people to ponder about: "enumerate all directed acyclic graphs (DAGs) of a given size <i>n</i>".</div><div><br /></div><div>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).</div><div><br /></div><div>First, some background. "Are you nuts? Enumerating <i>graphs</i>? You'll get huge numbers of them almost immediately!". Well, true. For example, <a href="http://www.research.att.com/%7Enjas/sequences/A000088">here is the arithmetic sequence</a> 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.</div><div><br /></div><div>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 <a href="http://www.research.att.com/%7Enjas/sequences/A000112">partially ordered sets</a>. A partially ordered set is also a DAG, with the further restriction that its <a href="http://en.wikipedia.org/wiki/Transitive_reduction">transitive reduction</a> is <b>itself </b>(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.</div><div><br /></div><div>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 <b><i>N</i> </b>of generated graphs. At the iteration, the <b><i>N</i></b><i>th</i> node of the graphs is created and combined with all graphs of size <b>N-1</b> in every possible way. How many ways are there? We are only allowed to connect the new node <b>to</b> the older nodes (not the other way around), so we only generated DAGs, so there are <b>N-1</b> possible edges to add. The power set of this is <b>2^(N-1)</b>, and this is every possible way that a given graph with <b>N-1</b> size can be extended with a new node.</div><div><br /></div><div>This produced DAGs of count 2^0 (1 node), 2^1 (2 nodes)</div><div><ul><li><b>2^0 = 1</b>(one node)</li><li><b>2^1 = 2 </b>(two nodes)</li><li><b>2^3 = 8</b> (three nodes)</li><li><b>2^6 = 64</b> (four nodes)</li><li><b>2^10 = 1024</b> (five nodes)</li><li><b>2^15 = 32768</b> (six nodes)</li><li><b>2^21 = 2097152</b> ( seven nodes)</li></ul></div><div>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 <b>60 bytes for each graph, </b>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 <b>N</b> shared the <b>N-1</b> nodes of it, along with their adjacency lists, with the previous graph of size <b>N-1</b> 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 <a href="http://en.wikipedia.org/wiki/Persistent_data_structure">persistent data structures</a> really excel, but in Javaland the reusable implementations are few and far between - did I mention yet you should check out <a href="http://www.scala-lang.org/">Scala</a>?)</div><div><br /></div><div>Then, I talked with <a href="http://www.cs.bath.ac.uk/%7Emjb/">Martin</a>, 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 <i>do</i> you want to have a freak of nature like this one???" and other related sub-discussions, he suggested enumerating <i>all undirected general </i><i>graphs</i> (not directed, not acyclic: this is what is offered) by <a href="http://cs.anu.edu.au/%7Ebdm/nauty/">nauty</a>, 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.</div><div><br /></div><div>From there, it only took few seconds to bump on the correct solution, which is very simple. See the following table:</div><div><br /></div><div><br /></div><div><span class="Apple-style-span" style="color: rgb(0, 0, 238);"><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi-Dj0ZnjvC28UfwLRcR7MtsP_hVLCwnzBaAlU3tYJm7FjMfkENAl2u2XpNvzII-5N6rV42dXMipoHuvXtVST9cFr9dpD744UvzCWlg1KTJgKqoSVfrNB3Nd_XE0DYnCdjEYE3uI532727Y/s320/matrix.png" alt="" id="BLOGGER_PHOTO_ID_5364042004692414002" style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 320px; height: 294px;" border="0" /></span></div><div><br /></div><div>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 <b>0</b> or <b>1</b>, 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 <span style="font-weight: bold;">is</span> 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 <b>n</b> 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: <b>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.</b> 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? :)</div><div><br /></div><div>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 <b>general </b>graphs, where each graph would be subsequently transformed to many, many DAGs.</div><div><br /></div><div><b>Addendum: </b>The above description leaves a tricky part uncommented. We saw how to generate all DAGs with <i>n </i>nodes, i.e. :<br /><br /><span class="Apple-style-span" style="font-family:'courier new';">int currentGraph = 1 << (n - 1) * (n - 2) / 2 ;</span></div><div><span class="Apple-style-span" style="font-family:'courier new';">while (currentGraph >= 0) {</span></div><div><span class="Apple-style-span" style="font-family:'courier new';"> currentGraph--; //represents a DAG!</span></div><div><span class="Apple-style-span" style="font-family:'courier new';">}</span><br /><br /></div><div>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>i</i><i> </i>to node <i>j</i>. Here is the implementation of this test, by <a href="http://www.csd.uoc.gr/%7Evuzukid/">Nelly Vouzoukidou</a>, a graduate cs student at Univ. of Crete:</div><div><br /></div><br /><pre><br />boolean hasEdge(int graph, int i, int j) {<br /> return i > j && isSet(graph, i * (i - 1) / 2 + j)<br />}<br /><br />//just checks whether a given bit of a number is set<br />boolean isSet(int number, int bit) {<br /> return number & (1 << bit) & number != 0;<br />}<br /></pre><br /><br /><div>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.</div><div><span class="Apple-style-span" style="color: rgb(0, 0, 238);font-family:Georgia;" ><img src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh_v0wuU8xJKrMZE2grCgF05i2rwkrbPMtcRkrmDJ2Q3Km00SzFx4fx7HH_27B5bhwvsM3JD_6N08EQhuIija6t9DTb1hHnJgxRSWcolxZpYZgfjRXQ6_jn6GxHUGnTY44muwegX8eG_B_Z/s320/numbered_matrix.PNG" alt="" id="BLOGGER_PHOTO_ID_5365668796641344130" style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 320px; height: 294px;" border="0" /></span></div><div><br /></div><div>If you found this interesting, you might want to check out <a href="http://code-o-matic.blogspot.com/2009/04/wonderful-programming-exercise.html">an older post about enumerating all binary trees</a>, where also an amusing solution is produced.</div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com2tag:blogger.com,1999:blog-6958126065976802292.post-62499546689753755472009-07-06T13:56:00.001-07:002009-07-06T14:04:31.656-07:00This is how real men do garbage collection!I was quite fascinated today seeing the way the famous JDK figure Martin Bucholtz does garbage collection. Anyone believing he takes garbage more seriously than that?<div><br /></div>Enjoy:<br /><pre><br />private static final Runtime rt = Runtime.getRuntime();<br />static void gcTillYouDrop() {<br /> rt.gc();<br /> rt.runFinalization();<br /> final CountDownLatch latch = new CountDownLatch(1);<br /> new Object() {<br /> protected void finalize() {<br /> latch.countDown();<br /> }<br /> };<br /> rt.gc();<br /> try {<br /> latch.await();<br /> }<br /> catch(InterruptedException ie){<br /> throw new Error(ie);<br /> }<br />}<br /></pre><br /><br />"Hyper-paranoid" indeed, in the words of <a href="http://smallwig.blogspot.com/">Kevin</a>.Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com2tag:blogger.com,1999:blog-6958126065976802292.post-57075079857149158392009-06-18T10:26:00.001-07:002009-06-18T10:29:23.424-07:00Funniest Java Interface<pre>interface sun.net.www.http.<b>Hurryable</b> {<br /> boolean <b>hurry</b>();<br />}</pre><pre><br /></pre><pre><b><span class="Apple-style-span" style="font-size: large;">:-)</span></b></pre>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com2tag:blogger.com,1999:blog-6958126065976802292.post-24899321504817805342009-06-16T03:31:00.000-07:002009-06-16T03:55:31.489-07:00Funny ConcurrentModificationException while playing with Google's Multimap(Disclaimer: Google's Multimap surely work fine and as advertised - this post describes a potentially confusing code interaction which can result in unintuitive ConcurrentModificationExceptions)<div><br /></div><div>First, lets create a multimap:</div><div><span class="Apple-style-span" style="font-family:-webkit-monospace;font-size:100%;"><span class="Apple-style-span" style=" white-space: pre;font-size:13px;"><span class="Apple-style-span" style="font-family:Georgia;font-size:130%;"><span class="Apple-style-span" style=" white-space: normal;font-size:16px;"><br /></span></span></span></span></div><div><pre>Multimap multimap = HashMultimap.create();<br /></pre><br /></div><div>Put somehow some values to it:</div><div><br /></div><div><pre>putSomeValues(multimap);</pre></div><div><br /></div><div>Now lets iterate its key set, and potentially filter some elements of each key's collection:</div><div><pre>for (Key key : multimap.keySet()) {<br /> Collection values = multimap.get(key);<br /><br /> ...<br /> if (something) {<br /> Value someValue = ...;<br /> values.remove(someValue);<br /> }<br />}</pre></div><div>(We could iterate its entries() as well, which is supposedly faster, but for now, I won't bother).</div><div><br /></div><div>This seems safe. I iterate the keys, and don't perform any structural modification in the multimap, I might only make a collection inside it shorter.</div><div><br /></div><div>Well, no. It can blow if "values" becomes empty, since then the multimap will remove the respective entry from the map (this is a very desirable behavior, to be sure), thus structurally modifying the map, thus ConcurrentModificationException when the iterator will try to fetch the next key.</div><div><br /></div><div>This may be quite nasty if only rarely the "values" collection goes empty and triggers this behavior, so it's good to know. </div><div><br /></div><div>My solution is this:</div><div><br /></div><div><pre>Iterator keyIterator = multimap.keySet().iterator();<br />while (keyIterator.hasNext()) {<br />Key key = keyIterator.next();<br />Collection values = multimap.get(key);<br /><br />...<br />if (something) {<br /> Value someValue = ...;<br /> if (values.size() == 1 && values.contains(someValue)) {<br /> keyIterator.remove();<br /> continue; //this is not really needed<br /> }<br /> values.remove(someValue);<br />}<br />}<br /></pre></div><div>Quite simpler would be to simply change this:</div><div><div><br /></div><div><span class="Apple-style-span" style="font-family:'courier new';">for (Key key : multimap.keySet()) {</span></div><div><br /></div><div>To this:</div><div><br /></div><div><div><span class="Apple-style-span" style="font-family:'courier new';">for (Key key : Lists.newArrayList(multimap.keySet())) {</span></div><div><br /></div><div>If you don't mind creating a copy of the entire key set up-front.</div></div></div>Anonymoushttp://www.blogger.com/profile/07286834543482860937noreply@blogger.com0