Apparently Google has recently become extremely paranoid about what may harm my computer. Here's a screenshot of some search results:
Looks like every result is dangerous...now here's what happens when I click on one of these dangerous links:
Must be Apple's developer website is out to get me...
Note: The behavior seems to have stopped. Quick failed Google experiment?
Sphere: Related ContentI've been experimenting in my spare time with the Scala actors library for about a year now. Initially it was mostly as part of my participation in the Widefinder project, but for the past several months I've been working on building more complicated abstractions using the actor library. The challenge with Widefinder, if you chose to keep your parallelism implementation generic and reusable, was to spread line-oriented input stream processing across as many threads as possible (ok, some may disagree with that, but that was my simplified take). This was relatively straight forward because the lines didn't have to be processed in any given order. Actors worked well for the task, and I was able to build a fairly generic set of classes that could be used in a very natural way for any similar problem.
I was feeling pretty good about Widefinder so I decided tackle a more complicated problem: parallelizing XML parsing (I'll write more on that later). In the process of exploring various ideas to help parallelize the parsing of XML I started butting my head against limitations of the actors library. For example, I built an "asynchronous stream" class - something like a normal Scala stream but instead of being entirely lazy, it asynchronously evaluates itself ahead of what has already been consumed, effectively parallelizing computation of the stream. This worked, except that if the stream wasn't fully evaluated the application using the stream wouldn't terminate properly because it's actor was still active. That made sense, as in many actor based applications you wouldn't want them to terminate before all the actors were finished, so I tried to make a custom scheduler that used daemon threads and therefore would allow the application to terminate without all of the actor threads terminating. This seemed like a straight forward task, except that it turned out to not be possible given some current limitations (link to enhancement about schedulers). So I set myself to fixing/enhancing the actors library to meet my needs and submit some patches.
Making fixes and enhancements to the actors library turned out to be a much bigger challenge than I expected. The external API for actors, particularly the documented part, is pretty clean and flexible. However internally, at least to a new set of eyes, there is a lot of spaghetti (count methods and variables that are defined as private[actors] so all the classes in the package can muck with them), oddly named variables and methods, and over a dozen mutable variables on the Actor trait that must all be correctly set in the right combination in order for the actor to work - and completely lacking any sort of structured means of manipulating them. I braved this, submitted some patches, and even wrote several enhancements that I did not submit, but I kept running into subtle problems that seemed almost impossible to track down. I would sprinkle assertions throughout the code only to realize that even when things seemed to work much of what I assuming was really holding. In other words I was getting lucky - or unlucky - as challenges like this are pretty common when doing parallel programming.
By this time I had a reasonable, albeit incomplete and with some inaccuracies, idea of what all those magical instance variables within Actor do and how they correspond to meaningful states. Here is my take on it:
waitingFor - the partial function that the actor is using to wait for a matching messageshouldExit - used to signal that the actor should exit instead of doing normal processingisSuspended - seems to indicate that the actor is waiting while blocked on a threadisDetached - the actor is waiting and is not attached to a threadisWaiting - the actor is waiting in some waymailbox - queue of messages for the actorsessions - list used as a stack to keep track of the sender of messages while they are being processedreceived - the message that was received, used to pass around a received message, could be replaced with local variable within functionsexitReason - the reason why the actor exited, default to 'normal when the actor is initialized and can be modified at any time, so it is there even when the actor has not yet exited.onTimeout - used for keeping track of a timeout action so that it can be canceled if a message is received within the timeout periodkill - a function invoked by reaction prior to invoking exit on the actor. It is used by loop and loopWhile to bypass the normal exit process of reactionstrapExit - if false (the default) then the actor will exit when an actor that it is linked to exits, if it's true then it will receive an Exit messagerc - a reply channel - unclear why it is actually needed because it is never used other than to be set in freshReplyChannel on every invokationlinks - a list of linked actors. Linked actors are notified or shutdown when the actor that they are linked to shuts downcontinuation - the function to be executed when the actor resumesAll those were pretty confusing, and it took me weeks to make any sense out of them - and usually the sense I made contained subtle flaws, so I decided to do something drastic. In my opinion the actors library is in desperate need of being refactored into something that encapsulates its state better and makes it much more explicit so you do not need to be an advanced adept to figure out what is happening inside the library. So I decided to do that refactoring and see where it lead me.
I distilled much of the above instance variables into the following states, which I have represented as immutable objects:
NotStarted - the initial state of the actorStartScheduled - the actor has been started but has not yet been attached a thread or started executing its bodyRunning - the actor is bound to a thread and is executing its bodyLooping - a special case of running where the body is repeated while a specified condition holdsKilling - when an actor is Running it cannot be directly stopped by the library, so it is shifted into the Killing state. When the library receives control while the actor is running it checks to see if the state has been changed to Killing. If the state has been changed to Killing, then it takes actions to regain control from user code so that the actor can be cleanly shutdown.BlockedWait - the type of wait performed within a receive block where the actor is waiting for a message while attached to a thread. There may be a timeout specified after which the actor will wakeup.DetachedWait - the type of wait performed within a react block when no matching message is available.ContinuationScheduled - similar to StartScheduled, only the processing of the message the actor was waiting for when in the DetachedWait state is scheduled instead of the starting of the actor.Finished - the actor teriminated normallyKilled - the actor was killed before it could complete executionUnhandledThrowable - an exception was thrown, usually from "user code," and not handledInternalError - an error occurred within the actor library...and now there are the following instance variables:
state - the state of the actormailbox queue of messages for the actorsessions list used as a stack to keep track of the sender of messages while they are being processedtrapExit - if false (the default) then the actor will exit when an actor that it is linked to exits, if it's true then it will receive an Exit messagelinks - a list of linked actors. Linked actors are notified or shutdown when the actor that they are linked to shuts down .Reducing the statefulness of the actor, and more importantly making the primary state explicit instead of implicit, makes the code much easier to both debug and extend. In working with actors, I found that it's relatively common to have an actor just seem to stop. It could be because it's waiting for a message, it could be because it's stuck in a loop, it could be any number of things. Without explicit state, it's very difficult to tell exactly what's happening with an actor. With explicit state, it's right there in your debugger.
I have the code in a Bitbucket repository in the "actor_state_machine" branch. Most of the changes are in the actor.scala file and I highly encourage you to take a look at the differences. Right now it the Scala test suite completes with the same results as the trunk as of a couple months ago, and I've added a couple tests to catch problems that it didn't. Next I'm going to do a little more refactoring and general code cleanup, then I'm going to focus on expanding the test suite. The current Scala testing tool, partest, uses actors heavily so it gives them a workout, but there aren't any explicit tests for actors. Finally, I'm going to try to decouple the states from one another and try to extract their code from the Actor trait so that they can be tested as independent units and are more extensible. I'm not sure what I'm actually going to do with the code. I'd be happy to contribute it back to the EPFL, but given it is such a substantial departure I'm not sure they would want it. So I'll probably end up moving it into another namespace and distributing it as a separate library.
Sphere: Related ContentNormally I don't blog on politics. I think they tend to draw away from technical content. But it's the day after the election, so I can't help myself. The countdown to the birth of the U.S.S.R. has begun. That's the United States Socialist Republic. For years now Bush has eroded our personal freedoms in the name of physical safety from terrorists. Now Obama will launch down the same path in pursuit of economic safety. In the end, America stands to lose all that has made it great, not from powers from without, but wasted away due to fears from within. Of course it's not too late. We stand to lose our greatest strengths, but they are not lost yet, and what is lost can be regained. We are still a democracy, by and large we are still free, and the voice of liberty will still be heard if we have the courage to raise it.
Sphere: Related ContentI received a few comments on my blog about type inference and its affect on readability saying that the problem isn't really a problem if you have proper tool support. You have API docs, IDE based assistance, and even interesting tools like the OCaml Browser. The problem is that these don't really address the problem. Programming requires a lot of concentration and is best done in a state of flow. This means that anything that causes distraction or disruption is the enemy. Flipping to another window in order to see some documentation requires a non-value added thought. So does moving the cursor so that an IDE will display a popup with the inferred type. Thoughts simply flow better if the code is readily readable, and code that requires a special tool to read is not readable.
There's also less benefits to having code that is readable without external assistance. While code may spend most of its life being displayed in an IDE, it certainly doesn't spend all of its life there. Books, articles, blogs, and other such media often contain code as well. Despite the ubiquity of the internet, I think having at least one book in dead tree format is still essential for a programming languages to be successful (and in some cases even taken seriously), and the last time I checked dead trees don't have popup windows. Most online postings don't have intelligent help, either, although I suppose it would be possible if someone really wanted to put in the effort. Regardless, the readability of a language in these formats will have a major impact on how easy a language is to learn, and ultimately how well it is accepted.
The bottom line is that despite all the great and useful tools there are out there, it is still critical for a language to stand on its own without major tool support.
Sphere: Related ContentI've been pondering the results of the Cedric's Code Challenge, and wondering just how much benefit is derived from optimized, purpose-specific solutions as opposed to solutions that rely on a more general libraries or frameworks. It's fairly common to see debates where one person (or group) insists that general constructs from a standard library or other such solutions represent an unacceptable overhead, and the other side claims that the overhead is meaningless compared to runtime optimizations performed by HotSpot and the cost of programmer time. These debates can be rather painful to watch, as both sides generally have good points, yet often seem to be arguing right past one another. Consequently, I think a little exploration of various potential optimizations and what their respective impacts on performance would be beneficial.
For purposes here, I'm going to say that a solution based on a general framework would be one that uses a general purpose library to generate permutations of digits, filters out the ones with a leading zero, converts the permutations to numbers, and then collects the desired statistics. A purpose specific solution would be one such as Crazy Bob's that is tailor-made for generating numbers based on permuted digits.
I'm not aware of a combinatronics library for Scala, but it is simple enough to write a generic permutation generating function:
def permute[E](s: Set[E], n: Int)(f: List[E] => Unit): Unit = {
def p(s: Set[E], r: List[E]): Unit =
if (r.length == n) f(r) else for(e <- s) p(s - e, e :: r)
p(s, Nil)
}
This recursively generates all of the possible permutations. When it as generated a complete permutation, it passes it to the function specified by the caller. If s is an ordered set, then the permutations will be generated in a predictable order. This can then be used to generate the permutations of digits for the code challenge, as follows:
val digits = TreeSet(0L, 1L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L)
def main(args: Array[String]): Unit = {
val start = java.lang.System.nanoTime
var last, cnt, jumpLow, jumpMagnitude = 0L
for(d <- 1 to 10) permute(digits, d) { p =>
val xs = p.reverse // digits are generated in the wrong order so must be reversed
if (xs.head != 0L) { // make sure this is a valid set of digits
val cur = xs.foldLeft(0L)((z, a) => (z * 10L) + a)
val dif = cur - last
if (dif > jumpMagnitude) {
jumpLow = last
jumpMagnitude = dif
}
last = cur
cnt = cnt + 1L
}
}
val end = java.lang.System.nanoTime
println("Count: " + cnt)
println("Jump: " + jumpMagnitude + " (from " + jumpLow + " to " + (jumpLow + jumpMagnitude) + ")")
println("Time: " + ((end - start) / 1000000L) + " ms")
}
This solution takes about 13 seconds on my MacBook.
The above permutation function can be tweaked as follows to generate only valid permutations (ones without the leading zero), and thereby saving about 10% execution time.
def digitPermute(n: Int)(f: List[Long] => Unit): Unit = {
def p(s: Set[Long], r: List[Long]): Unit =
if (r.length == n) f(r) else for(e <- s) p(s - e, e :: r)
for(first <- (digits - 0L)) p(digits - first, first :: Nil)
}
The above solution executes in about 12 seconds.
Both of the methods above construct lists of numbers which are later assembled into numbers. This wastes memory and cycles, because only the resulting numbers are required and they can be accumulated much more efficiently. Doing so, as shown below, reduces execution time to about 7 seconds.
val digits = TreeSet(0L, 1L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L)
def digitPermute(n: Int)(f: Long => Unit): Unit = {
def p(s: Set[Long], d: Int, r: Long): Unit =
if (d == n) f(r) else for(e <- s) p(s - e, d + 1, r * 10L + e)
for(first <- (digits - 0L)) p(digits - first, 1, first)
}
The above implementations all use TreeSet from Scala's standard library, which imposes a few performance penalties. For one, it is "generic." This means that it requires both type-erasure and boxing instead of using primitives. Second, if you look carefully at the definition of TreeSet, you'll notice that it doesn't require its contents to be Ordered, but rather uses a (potentially implicit) view converting the contained type into an Ordered. This adds an extra layers of indirection and therefore an extra cost.
final class LongSet (val contents: Array[Long]) {
private def indexOf(v: Long, min: Int, max: Int): Int = {
if (min > max) -1
else {
val mid = (min + max) >>> 1
val midVal = contents(mid)
if (midVal < v) indexOf(v, mid + 1, max)
else if (midVal > v) indexOf(v, min, mid - 1)
else mid
}
}
def foreach(f: Long => Unit) {
var i = 0
val max = contents.length
while (i < max) {
f(contents(i))
i = i + 1
}
}
def -(v: Long): LongSet = {
val max = contents.length - 1
if (indexOf(v, 0, max) < 0) this
else {
val a = new Array[Long](max)
var i, j = 0
while (i <= max) {
val cur = contents(i)
if (cur != v) {
a(j) = contents(i)
j = j + 1
}
i = i + 1
}
new LongSet(a)
}
}
}
val digits = new LongSet(Array(0L, 1L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L))
def digitPermute(n: Int)(f: Long => Unit): Unit = {
def p(s: LongSet, d: Int, r: Long): Unit =
if (d == n) f(r) else for(e <- s) p(s - e, d + 1, r * 10L + e)
for(first <- (digits - 0L)) p(digits - first, 1, first)
}
This implementation brings the execution time down to ~1.7 seconds, representing a substantial savings over TreeSet. The comparison isn't quite fair, as TreeSet uses a Red-Black balanced tree and the code above uses a sorted array, but the difference is still substantial and shows that having a more targeted data structure can improve performance significantly. At this point you might be thinking "Well no sh*t sherlock! Of course a data structure tuned for a specific type is faster than one that is written to handle any type!" That's true...to a point. Not all languages implement generics using type erasure and require boxing of values within parameterized classes. For example, C++ was designed to ensure that data structures implemented using templates imposed little or no overhead above more raw ones.
Another approach is to use a more special-purpose data structure in the permutation function without reducing its generality. The linked set used in Crazy Bob's solution can be generalized to generating permutations of any type. Unfortunately, this structure is mutable, and mutates on every invocation. This means that while it would be possible to pass it directly to client code, it would be extremely dangerous because the client code may maintain a reference to the rapidly changing data structure. Consequently, the structure needs to be copied into a list or similar structure before being passed to client code. The solution built around the code below completes in ~5 seconds, which is slower than using an structure explicitly coded for dealing with longs and generating longs, but over twice as fast as generating permutations using the standard TreeSet class.
private final class Element[E](val value: E, var next: Element[E], var previous: Element[E]) {
/** remove an element from the set*/
def use() {
if (previous ne null) previous.next = next
if (next ne null) next.previous = previous
}
/** put an element back in the set */
def yieldValue() {
if (previous ne null) previous.next = this
if (next ne null) next.previous = this
}
}
private def buildElements[E](s: Set[E]): Element[E] = {
val iter = s.elements
val first = new Element(iter.next, null, null)
var cur = first
while(iter.hasNext) {
cur.next = new Element(iter.next, null, cur)
cur = cur.next
}
first
}
def permute[E](s: Set[E], n: Int)(f: List[E] => Unit): Unit = {
def p(start: Element[E], head: Element[E], r: List[E]): Unit = {
def take(current: Element[E]): Unit = {
if (current ne null) {
val newR = current.value :: r
if (newR.length == n) {
f(newR)
take(current.next)
} else {
current.use()
val newHead = if (current eq head) head.next else head
p(newHead, newHead, newR)
current.yieldValue()
take(current.next)
}
}
}
take(start)
}
val first = buildElements(s)
p(first, first, Nil)
}
The various implementations here represent a sampling of various ways that Cedric's Code Challenge can be implemented in Scala, and the effects they have on performance. A relatively direct port of Crazy Bob's solution to Scala completes in ~0.4 seconds, making it by far the fastest solution and about 30 times faster than the solution using standard data structures with a generic permutation generator. That's not really surprising, so what can we conclude? The most obvious conclusion is that avoiding the construction of intermediate objects yields a substantial speedup. This can be seen in two places. The first is in the switch from constructing a List to represent the permutation to accumulating the Long directly. The second is in using a special-purpose mutable data structure to generate the permutations, thereby avoiding repeated allocations of Set objects. Finally, reducing overhead due to things like boxing and the casts associated with type erasure does make a noticeable difference in performance. On the flip side, Scala's closure based constructs, such as nested functions and for loops, added negligible overhead, if any at all. Using more general constructs instead of more specific ones clearly has a substantial performance cost, but it's also worth mentioning that the cost is trivial compared to the benefit received in the transition from a brute-force solution to an optimal algorithm.
Sphere: Related Content