Erik Engbrecht's Blog

Martin Odersky's Scala Levels

2011-01-16T22:42:00.003-05:00

I just saw Martin's post on levels of expertise in Scala, and Tony Morris's response. The concept of levels is something that many in the community have called for repeatedly, in order to help ease people - especially team members who may be a little put off by some of Scala's more advanced features - into the language more gently. I understand the motivation, but it has always struck me as somewhat odd. The reason is that I think one needs to have very compelling reason for such a significant change to be justified, especially a change from a mature, mainstream technology such as Java into one as new an immature as Scala. To being, I'll recount my experience with adding Python as a stable in my programming toolbox.

Learning Python

I dabbled it Python a lot before really using it extensively. Much of my initial usage basically amounted to using Jython as a repl for interactively poking at Java libraries, especially ones that weren't particularly well documented. I thought Python was neat, but at the time most of my programming experience was in C++ and Java. I valued static typing. I valued having a compiler. When I was in college, I had a professor who said something along the line so of "The compiler is your friend. Write your code so that the compiler is more likely to catch your mistakes. Don't try to trick it or bypass it." This was in the context of C++ programming, and given all the ways that one can shoot himself in the foot using C++, it always seemed like sage advice. So giving up have a compiler to catch my mistakes, and an explicit structure clearly present in my code, seemed like an awful lot to ask. Sure, Python is more concise, but in my opinion conciseness is often more a matter of how closely the libraries you're using match the problem that you are trying to solve. About a year ago I had some experimental Python code that I had thrown together that did some regular expression heavy text processing then some XML processing (I was processing output of an application that produced invalid XML, so the first phase was the fix it so the XML parser wouldn't crash and the second was to actually process it). I can't remember why, but I decided to convert it to Java. I think it was because I wanted to integrate it with something that integrated well with Java, but not as well with Python. Anyway, the point is that the Python code and the Java code weren't that different in length. Sure, Java has a lot more boiler plate, but once your code starts being dominated by actual logic instead of getters and setters, it's the libraries that make the difference.

Anyway, I didn't really get into Python until I discovered and thoroughly learned metaclasses and descriptors. In my mind, they took Python from being a toy with a clean syntax to a language that opened up an entire new dimension of abstraction. A dimension of abstraction that had been missing all me life. A dimension that I had glimpsed in C++ template metaprogramming but had never quite managed to enter. All of a sudden I had this tool that enabled me to drastically and repeatedly reduce code sizes all while making the business logic cleaner and more explicit. I had a means to encode my ideas such that they enabled my coworkers to use them without fulling understanding them (an admittedly dangerous proposition). It was beautiful! They remain an important part of my toolbox to this day.

Incidentally, my first uses metaclasses and descriptors was to concisely implement immutable, lazy data structures. This was long before I knew anything about functional programming.

Learning Scala

I also dabbled in Scala a lot before really becoming enamored with it. I was caught by the conciseness over Java, especially the absence of getters and setters, the presence of operator overloading, and multiple inheritance using traits. But I had operator overloading and multiple inheritance in both C++ and Python. I could usually abstract away explicit getters and setters in Python, and by the time I started picking up Scala I had already made a significant shift towards immutability and laziness, so setters weren't as necessary. Scala was neat, and the compatibility with Java was a real benefit, but at first it didn't seem compelling. In fact, when I first started experimenting with Scala it seemed too buggy to really be worth it. Something worth watching, but not yet worth using. Also, by the time I started learning Scala I had already learned Common Lisp and functional programming with full tail-call optimization seemed awkward (and still does).

What eventually sold me on Scala was higher-kinded types, companion objects, and objects-as-modules. You see, but the time I started picking up Scala I had already developed a habit of using a lot of generic programming. This is easy in Python where there's no compiler check a type system to tell you that you are wrong. But a lot of the patterns I commonly used couldn't be translated into Java generics (in fact, in my first foray into Java generics I crashed javac writing code that was compliant with the Java specification). Scala gave me concise programs and type safety! And with the introduction of collections that actually use higher-kinded types in 2.8.0, along with the leaps and bounds made in robustness, I think it finally reached threshold for serious use.

That's not to say these are the only key features. Understanding folds was a real eureka moment for me. I'm not sure how one can do effective functional programming without them, but perhaps there is a way. Implicit definitions are also key, and they are used so extensively in Scala libraries that I think writing Scala without a decent understanding of them is nothing short of voodoo programming. In short, there's a lot, and the features tend combine together in powerful ways.

Summary

I understand the motivation for establishing levels, but I personally think if one avoids many of the features that Martin has flagged as advanced, then the benefits of Scala don't justify the risk of using such a new technology and the need to retrain people. I think without them one is better off finding a better library or framework for their current stack. Also, between the fact that advanced features are omnipresent in the libraries, and teams will always have someone who wants to use the more powerful features, avoiding them works a lot better in theory than it does in practice. You can't not use them, unless you don't use Scala's standard library and avoid almost any library written explicitly for Scala. You can only pretend that you are not using them.

This is probably going to get me flamed, but reward must justify risk. In many circumstances Scala has the features to justify the risk associated with it, but the justification quickly vanishes as the more powerful features are stripped away. So while I think a programmer may be productive at Martin's lower levels, they don't justify Scala over Java.

Types of Project Failure

2011-01-12T00:00:00.001-05:00

I saw this question on StackExchange and it made me think about all the projects I've been on that have failed in various ways, and at times been both declared a success and in my opinion been a failure at the same time (this happens to me a lot). Michael Krigsman posted a list of six different types a while back, but they are somewhat IT centric and are more root causes than types (not that identifying root causes isn't a worthwhile exercise - it is). In fact, when if you Google for "types of project failures," the hits in general are IT centric. This may not seem surprising, but I think the topic deserves more general treatment. I'm going to focus on product development and/or deployment type projects, although I suspect much can be generalized to other areas.

Here's my list:

Failure to meet one or more readily measurable objectives (cost, schedule, testable requirements, etc)
Failure to deliver value consummate with the cost of the project
Unnecessary collateral damage done to individuals or business relationships

I think these are important because in my experience they are the types of failure that are traded "under the table." Most good project managers will watch their measurable objectives very closely, and wield them as a weapon as failure approaches. They can do this because objective measures rarely sufficiently reflect "true value" to the sponsor. They simply can't, because value is very hard to quantify, and may take months, years, or even decades to measure. By focusing on the objective measures, the PM can give the sponsor the opportunity to choose how he wants to fail (or "redefine success," depending on how you see it) without excessive blame falling of the project team.

Subjective Objective Failure

The objective measures of failure are what receive the most attention, because, well, they're tangible and people can actually act upon them. My definition of failure here is probably a bit looser than normal. I believe that every project involves an element of risk. If you allocate the budget and schedule for a project such that is has a 50% chance of being met - which may be a perfectly reasonable thing to do - and the project comes in over budget but within a reasonably expected margin relative to the uncertainty, then I think the project is still a success. The same goes for requirements. There's going to be some churn, because no set of requirements is ever complete. There's going to be some unmet requirements. There are always some requirements that don't make sense, are completely extraneous, or are aggressive beyond what is genuinely expected. The customer may harp on some unmet requirement, and the PM may counter with some scope increase that was delivered, but ultimately one can tell if stakeholders feel a product meets its requirements or not. It's a subjective measure, but it's a relatively direct derivation from objective measures.

Value Failure

Failure to deliver sufficient value is usually what the customer really cares about. One common situation I've seen is where requirements critical to the system's ConOps, especially untestable ones or ones that are identified late in the game, are abandoned in the name of meeting more tangible measures. In a more rational world such projects would either be canceled or have success redefined to include sufficient resources to meet the ConOps. But the world is not rational. Sometimes the resources can't be increased because they are not available, but the sponsor or other team members chooses to be optimistic that they will become available soon enough to preserve the system's value proposition, and thus the team should soldier on. This isn't just budget and schedule - I think one of the more common problems I've seen is allocation of critical personnel. Other times it would be politically inconvenient to terminate a project due to loss of face, necessity of pointing out an inconvenient truth about some en vogue technology or process (e.g. one advocated by a politically influential group or person), or idle workers who cost just as much when they're idle as when they're doing something that might have value, or just a general obsession with sunk costs.

This is where the "value consummate with the cost" comes in. Every project has an opportunity cost in addition to a direct cost. Why won't critical personnel be reallocated even though there's sufficient budget? Because they're working on something more important. A naive definition of value failure would be a negative ROI, or an ROI below the cost of capital, but it's often much more complicated.

It's also important to note here that I'm not talking about promised ROI or other promised operational benefits. Often times projects are sold on the premise that they will yield outlandish gains. Sometimes people believe them. Often times they don't. But regardless, and usually perfectly possible to deliver significant value without meeting these promises. This would be a case of accepting objective failure because the value proposition is still there, it's just not as sweet as it was once believed to be.

Collateral Damage

Collateral damage receives a fair amount of press. We've all heard of, and most of us have one time or another worked, a Death March project. In fact, when I first thought about failure due to collateral damage, I thought any project causing significant collateral damage would also fall under at least one of the other two categories. It would be more a consequence of the others than a type unto itself. But then I thought about it, and realized experienced a couple projects where I feel the damage done to people was unacceptable, despite the fact that in terms of traditional measures and value delivered they were successful. There's a couple ways this can happen. One is that there are some intermediate setbacks from which the project ultimately recovers, but one or more people are made into scapegoats. Another way arises from interactions among team members that are allowed to grow toxic but never reach the point where they boil over. In my experience a common cause is an "extreme" performer, either someone who is really good or really bad, with a very difficult personality, particularly when the two are combined on a project with weak management.

Now, you might be wondering what the necessary causes of collateral damage are. It's actually fairly simple. Consider a large project that involves a large subcontract. The project may honestly discover that the value contributed by the subcontract does not justify its cost, or that the deliverables of the subcontract are entirely unnecessary. In this case the subcontract should be terminated, which in turn is likely to lead to a souring of the business relationship between the contractor and the subcontractor, along with potentially significant layoffs at the subcontractor. Often times a business must take action, and there will be people or other businesses who lose out through no fault of their own.

Back to Trading Among Failure Types

A Project Manager, along with projects sponsors and other key stakeholders, may actively choose which type of failure, or balance among them, is most desirable. Sometimes this "failure" can even really be success, so long as significant value is delivered. Some of the possible trades include:

Failing to meet budget and schedule in order to ensure value.
Sacrificing value in order to meet budget and schedule...
...potentially to avoid the collateral damage that would be inflicted in the case of an overt failure
Inflicting collateral damage through practices such as continuous overtime in order to ensure value or completing on target
Accepting reduced value or increased budget/schedule in order to avoid the collateral damage of the political fallout for not using a favored technology or process

Ultimately some of these trades are inevitable. Personally, I strongly prefer focusing on value. Do what it takes while the value proposition remains solid and the project doesn't resemble a money pit. Kill it when the value proposition disappears or it clearly becomes an infinite resource sink. But of course I know this is rather naive, and sometimes preventing political fallout, which I tend to willfully ignore in my question for truth, justice, and working technology; has an unacceptable if intangible impact. One of my most distinct memories is having a long conversation with a middle manager about a runaway project, and at the end being told something like "Erik, I agree with you. I know you're right. We're wasting time and money. But the money isn't worth the political mess it would create if I cut it off or forcefully reorganized the project." I appreciated the honesty, but it completely floored me, because it meant not only that politics could trump money, but politics could trump my time, which was being wasted. Now I see the wisdom in it, and simply try to avoid such traps when I see them and escape them as quickly as possible when I trip over them.

StackOverflow and Scraper Sites

2011-01-03T12:49:00.001-05:00

I recently noticed that Google searches were turning up a lot of sites that mirror StackOverflow content as opposed to the originals. It appears that I'm not alone. This morning Jeff Atwood blogged about how they're having increasing problems with these sites receiving higher Google rankings. His post, and especially the comments, are filled with righteous indignation about how it's the end of the Internet as we know it. Of course, I can't remember a time when search results weren't polluted faked-out results, so I don't understand why he's so surprised.

But I do think this situation is different. The difference is that in many cases the presentation is far different from my previous exposure to link farms. Historically, my impression is that pages on such sites generally have the following attributes:

The recycled content is poorly formated and often truncated
Unrelated content from multiple sources is lumped together in a single page (usually there is some common keyword)
Advertisements are extremely dominant and often unrelated to the content
The link-to-content ratio is often very high, and the links are to unrelated content

In fact, I think if one were to develop a set of quantitative metrics that could be automatically measured for pages based on the above criteria, I think StackOverflow would perform worse than some of the sites that mirror its content. It's rather ironic, but if you think about it, if you wanted to defeat an algorithm that was developed to find the "best" source for some common content, you'd do everything you could to make your scraper site look more legitimate than the original. Let's compare a question on StackOverflow with it's cousin on eFreedom.com.

Analysis

The primary content is essentially the same with similar formatting. The two major differences are that eFreedom only directly displays the selected answer, as opposed to all of the answers with the selected answer on the top, and none of the comments are displayed. This may help avoid triggering the "unrelated content" rule, because the selected answer is probably the most cohesive with the question, and comments frequently veer off-topic. But I suspect the affect is minimal.

Now consider the advertisements. eFreedom has a few more, but they are more closely tied to the content (using Google AdWords, which probably helps). The advertisements on StackOverflow are for jobs identified via geolocation (I live in Maryland), and the words in them don't correlate particularly well to the primary content, even though they are arguably more relevant to StackOverflow users that run-of-the-mill AdWords ones.

Now let's consider the related links. StackOverflow has links to ~25 related questions in a column along the side. The only content from the questions in the title, and the majority seem to be related based on matching a single tag from the question. eFreedom, on the other hand has links to 10 related questions (they appear to be matching on both tags), puts them inline with the main content, and includes a brief summary. As a human being I think the StackOverflow links are much more noisy and less useful. If I try to think like an algorithm, what I notice is StackOverflow has a higher link-to-content ratio, and the links are to more weakly related content.

The only other major difference is that eFreedom has a "social network bar" on the page. I'm not sure how this would affect ranking. It probably helps with obtaining links.

If you look at the HTML for each page, both use Google Analytics, both use what I'm assuming is a CDN for images, and StackOverflow appears to have a second analysis service. On casual inspection, neither appear to be laden with external content for tracking purposes, although without deeper inspection there's no way to be sure. But I presume a having a large number of tracking links would make a site look more like spam, and having few of them make it look more legit.

Conclusion

I don't think either site looks like spam, but between the two, StackOverflow has more spam-like characteristics. eFreedom's content and links are considerably less noisy than StackOverflow's. Is eFreedom being a leach? Yes, certainly, but it, and I believe some of the other sites replicating StackOverflow's content, don't look like traditional link-spam sites. In fact, for a person who is just looking for content, as opposed to looking to participate in a community, then eFreedom is at least as good, if not slightly better. There may be a moral argument that the original source should be given priority over replications, but from a pure content quality perspective StackOverflow and its copiers are essentially identical, and computer algorithms aren't generally in the business of making moral judgements. Also, there are many forums and mailing list archives out there that have atrocious user interfaces where the casual searcher is likely better off being directed to a content aggregator than to the original source, so I don't think a general rule giving preference to original sources would be productive. Ultimately, I think open community sites like StackOverflow are going to have to compete with better SEO and perhaps better search and browsing UI's for non-contributors, rather than relying up search engines to perform some miracle, because the truth is that from a content consumption perspective the replicated sites are just as good.

Easier object inspection in the Scala REPL

2010-12-28T18:54:00.003-05:00

If you're like me, you spend a fair amount of time poking at objects of poorly documented classes in a REPL (Scala or otherwise...). This is great compared to writing whole test programs solely for the purpose of seeing what something does or what data it really contains, but it can be quite time consuming. So I've written a utility for use on the Scala REPL that will print out all of the "attributes" of an object. Here's some sample usage:

scala> import replutils._
import replutils._

scala> case class Test(a: CharSequence, b: Int)
defined class Test

scala> val t = Test("hello", 1)
t: Test = Test(hello,1)

scala> printAttrValues(t)
hashCode: int = -229308731
b: int = 1
a: CharSequence (String) = hello
productArity: int = 2
getClass: Class = class line0$object$$iw$$iw$Test

That looks fairly anti-climatic, but after spending hours typing objName. to see what's there, and poking at methods, it seems like a miracle. Also, one neat feature of it is that if the class of the object returned is different from the class declared on the method, it prints both the declared class and the actual returned class.

Code and further usage instructions is available on BitBucket here.

So what exactly is an attribute?

I haven't quite figured that out yet. Right now it is any method that meets the following criteria:

the method has zero arguments
the method is public
the method is not static
the method's name is not on the exclude list (e.g. wait)
the method's return type is not on the exclude list (e.g. Unit/void)
the method is not a "default argument" method

Please post any feedback in the comments here, or better yet in the issue tracker on Bitbucket.

Playing with Scala Products

2010-12-27T21:25:00.003-05:00

Have you ever wanted something like a case class, that magically provides decent (for some definition of decent) implementations of methods like equals and hashCode, but without all of the restrictions? I know that I have. Frequently. And recently I ran into an answer on StackOverflow that gave me an idea for how to do it. The trick is to play with Products. I'm not sure how good of an idea it is, but I figure the Internet will tell me. Here's the basic idea:

import scala.runtime.ScalaRunTime

trait ProductMixin extends Product {
  def canEqual(other: Any) = toProduct(other) ne null
  protected def equalityClass = getClass
  protected def equalityClassCheck(cls: Class[_]) = equalityClass.isAssignableFrom(cls)
  protected def toProduct(a: Any): Product = a match {
    case a: Product if productArity == a.productArity && equalityClassCheck(a.getClass) => a
    case _ => null
  }
  override def equals(other: Any) = toProduct(other) match {
    case null => false
    case p if p eq this => true
    case p => {
      var i = 0
      var r = true
      while(i < productArity && r) {
 if (productElement(i) != p.productElement(i)) r = false
 i += 1
      }
      r
    }
  }
  override def productPrefix = try {
    getClass.getSimpleName()
  } catch {
    //workaround for #4118, so classes can be defined in the REPL that extend ProductMixin
    case e: InternalError if e.getMessage == "Malformed class name" => getClass.getName()
  }
  override def hashCode = ScalaRunTime._hashCode(this)
  override def toString = ScalaRunTime._toString(this)
}

Basic Usage

There's a couple ways to use ProductMixin. The first, and probably the simplest, is to extends one of the ProductN classes and provide the appropriate defs:

class Cat(val name: String, val age: Int) extends Product2[String, Int] with ProductMixin {
  def _1 = name
  def _2 = age
}

The second way is to provide them yourself:

 class Dog(val name: String, age: Int) extends ProductMixin {
  def productArity = 2
  def productElement(i: Int) = i match {
    case 0 => name
    case 1 => age
  }
}

Either way, the result is something that has many of the benefits of case classes but allows for more flexibility. Here's some sample usage:

scala> val c1 = new Cat("Felix", 2)
val c1 = new Cat("Felix", 2)
c1: Cat = Cat(Felix,2)

scala> val c2 = new Cat("Alley Cat", 1)
val c2 = new Cat("Alley Cat", 1)
c2: Cat = Cat(Alley Cat,1)

scala> val c3 = new Cat("Alley Cat", 1)
val c3 = new Cat("Alley Cat", 1)
c3: Cat = Cat(Alley Cat,1)

scala> c2 == c3
c2 == c3
res0: Boolean = true

scala> c1 == c2
c1 == c2
res1: Boolean = false

Dealing with Inheritance

Equality in the presence of inheritance is very tricky. But, possibly foolishly, ProductMixin makes it easy! Let's say you have a hierarchy, and you want all the classes under some root class to be able to equal each other. Here's how it would be done by overriding the equalityClass so that it is the root of the hierarchy (using a not-so-good example):

scala> abstract class Animal(val name: String, val age: Int) extends Product2[String, Int] with ProductMixin {
     | override protected def equalityClass = classOf[Animal]
     | def _1 = name
     | def _2 = age
     | }
defined class Animal

scala> class Dog(name: String, age: Int) extends Animal(name, age)
class Dog(name: String, age: Int) extends Animal(name, age)
defined class Dog

scala> class Cat(name: String, age: Int) extends Animal(name, age)
class Cat(name: String, age: Int) extends Animal(name, age)
defined class Cat

scala> val c = new Cat("Felix", 1)
val c = new Cat("Felix", 1)
c: Cat = Cat(Felix,1)

scala> val d = new Dog("Felix", 1)
val d = new Dog("Felix", 1)
d: Dog = Dog(Felix,1)

scala> c == d
c == d
res0: Boolean = true

The reverse can also be accomplished by overriding equalityClassCheck such that it checks that the classes are equal instead of using isAssignableFrom. That would mean two objects could be equal if and only if they are the same class.

Wrapup

I don't know to what extent this is a good idea. I've only tested it a bit in the REPL. It's neat, but there is one problem that comes to mind: performance. Any primitive members that are elements of the product will end up being boxed prior to usage in the hashCode and equality methods, the extra layers of indirection aren't free, and neither is the loop. That being said, case classes use the exact same method for hashing, so in what way they pay the same penalty, and unless code is really hashing and equality heavy it probably wouldn't be noticeable.

Scala is for VB programmers

2010-08-26T07:44:00.003-04:00

Normally I don't go for flame bait titles. But I haven't finished my morning coffee yet so I can't help myself. There's once again a debate raging across the internet about whether Scala is more or less complex than Java, along with the more nuanced argument that yes, it is more complex but only framework and library developers have to contend with this complexity. This argument usually happens when someone posts a little bit of code like this:

def map[B, That](f: A => B)(implicit bf: CanBuildFrom[Repr, B, That]): That

And then someone responds like this:

Why do not people realize that Java is too difficult for the average programmer? That is the true purpose of Scala, to escape the complexity of Java code! Framework code in Scala, with heavy use of implicit keywords and all kinds of type abstractions, is very difficult. This is correct, but this code is not meant for innocent eyes. You do not use that sort of code when you write an application.

I've seen this type of thinking before. A few years ago I had a bout of insanity and lead an ASP.NET project using ASP.NET 2.0. I had no .NET experience prior to this project. The project failed, although the reasons for that failure are legion and unimportant here. But I noticed something about ASP.NET developers: they have no clue how the technology works. It's a black box. Do you why? Because it is a black box. I searched and searched and couldn't even find a good illustration of the lifecycle for an ASP.NET page that's using events. This type of information is put front and center in the Java world. It's absolutely buried in the Microsoft world. Or at least the parts of it that target the hoards of VB programmers that are undyingly loyal to MS. The framework is magic dust created by the great wizards in Redmond so that you can build solutions for your customers. Do not question the dust. Think about VB. Or, no don't, it might damage your brain. My coffee hasn't quite kicked in, so I should have some immunity, so I'll do it for you. VB is a black box (well, at old school VB6). It was designed to allow people who do not know how to really program, and who will probably never know how to program, to create applications. It's completely flat, opaque abstraction. The dichotomy between the application developer and the framework developer is as high and as thick as the gates of Mordor.

There are many people in the Scala community that claim Scala's complexity can be hidden from the application program. I don't believe them, but there's a chance that they are right. It's technically feasible, and I can see how it could happen if Scala started attracting lots of VB programmers. I can't see how it's going to attract lots of VB programmers, but apparently many people in the Scala community think Scala is for VB programmers. So we'll just have to wait and see...

Scala Actors: loop, react, and schedulers

2010-08-22T21:41:00.003-04:00

One of the unfortunate aspects of many of the "published" (meaning blogged) Scala Actor benchmarks out there is that they rarely pay much attention, if any, to the affects of seemingly idiomatic patterns on performance. Some of the main culprits are:

react versus receive (event-based versus threaded)
loop/react versus recursive react
loop/receive versus receive/while
tweaking (or failing to tweak) the scheduler

I've been working on setting up a "benchmarking framework" in conjunction with experimenting with modifications to the underlying thread pool so that all the possible permutations are automatically tested. What I have right now is a classic "ring" benchmark setup to permute the schedulers and loop/react versus recursive react. The loop/react pattern is more idiomatic (or at least more common), but higher overhead, and it looks something like this:

loop {
  react {
    case Msg(m) => // do stuff
    case Stop => exit()
  }
}

The reason it is high-overhead is that both loop and react raise control flow exceptions that result in the creation of new tasks for the thread pool when they are hit, so for each loop, two exceptions are raised and two tasks are executed. There's overhead in both of the operations, especially raising the exceptions. The recursive react pattern looks like this, so it can avoid the extra exception/task:

def rloop(): Unit = react {  //this would be called by the act() method
  case Msg(m) => {
    // do stuff
    rloop()
  }
  case Stop => // just drop out or call exit()
}

Using loop instead of recursive react effectively doubles the number of tasks that the thread pool has to execute in order to accomplish the same amount of work, which in turn makes it so any overhead in the scheduler is far more pronounced when using loop. Now, I should point out that the overhead really isn't that large, so if the actor is performing significant computations it will be lost in the noise. But it's fairly common to have actors do fairly little with each message. Here's some results from the ring benchmark using 10 rings of 10,000 actors passing a token around them 100 times before exiting. I'm using multiple rings because otherwise there is no parallelism in the benchmark. These are being run on my dual core Macbook.

Scheduler	ReactMethod	Time (sec)
ManagedForkJoinScheduler	LoopReact	45.416058
ManagedForkJoinScheduler	RecursiveReact	25.509482
ForkJoinScheduler	LoopReact	65.268584
ForkJoinScheduler	RecursiveReact	45.85605
ResizableThreadPoolScheduler	LoopReact	98.084794
ResizableThreadPoolScheduler	RecursiveReact	53.379757

The fork/join schedulers are faster than the ResizableThreadPoolScheduler because rather than have all of the worker threads pull tasks off of a single, shared queue; each thread maintains its own local dequeue where it can place tasks directly onto if they are generated while it is running a task. This creates a kind of "fast path" for the tasks that involves much less overhead.

I believe the primary reason ManagedForkJoinScheduler is faster because ForkJoinScheduler does not always leverage the "fast path," even when in theory it could be used. I'm unsure about some of the rationale behind it, but I know some of the time the fast path is bypassed probabilistically in order to reduce the chances of starvation causing deadlock in the presence of long running or blocking tasks. ManagedForkJoinScheduler escapes this particular issue by more actively monitoring the underlying thread pool, and growing it when tasks are being starved. The second reason, and I'm somewhat unsure of the actual degree of the affects, if that ForkJoinScheduler configures the underlying thread pool so that the threads work through the local dequeues in FIFO order, while ManagedForkJoinScheduler configures the pool such that the local dequeues are processed in LIFO order. Processing in LIFO order allows the pool to take advantage of locality with regard to the tasks, basically assuming that the last task generated is the most likely to use data that's currently in cache, and thus reduce cache misses.

The benchmark outputs a lot more information than I captured in the above table. If you'd like to run it, you can obtain the code here. The project uses sbt, so you'll need to have it working on your computer. After you run update in sbt to download all of the dependencies, you can run the ring benchmark as follows:

$ sbt
[info] Building project ManagedForkJoinPool 1.0 against Scala 2.8.0
[info]    using ManagedForkJoinPoolProject with sbt 0.7.4 and Scala 2.7.7
> ringbenchmark
[info] 
[info] == compile ==
[info]   Source analysis: 1 new/modified, 0 indirectly invalidated, 0 removed.
[info] Compiling main sources...
[info] Compilation successful.
[info]   Post-analysis: 79 classes.
[info] == compile ==
[info] 
[info] == copy-resources ==
[info] == copy-resources ==
[info] 
[info] == ringbenchmark ==
[info] RingBenchmark ManagedForkJoinScheduler LoopReact 2 ....output truncated...

You can tweak the benchmarks by modifying the sbt project file. If you do run them, I'm very interested in the results.

Concurrency Benchmarking, Actors, and sbt tricks

2010-08-21T15:09:00.006-04:00

Have you ever noticed that other people's microbenchmarks tend to be hard to run and often impossible to duplicate? And are frequently caveated to the hilt? When it gets down to it, a benchmark is really an experiment, and ideally a scientific experiment. That means all factors that are relevant to the results should be clearly recorded, and the tests should be easy for others to duplicate.

Custom sbt actions for benchmarks

In order to test and run benchmarks on the work I'm doing around creating a managed variant of the JSR-166y ForkJoinPool along with supporting infrastructure for use with Scala Actors, I'm creating a test harness that captures a host of environmental factors about how it was run, and writing sbt actions to make it easy to run the benchmarks and automatically permute the variables.

It still needs a lot of work, but I had some trouble figuring out a really basic task so I thought I'd share it. Basically I wanted to build a Task object that consists of several tasks based on information in the project definition and permuted parameters. It actually pretty easy, as you can see in the snippet below from my project definition:

  /** this task executes the PingPong benchmark using each available scheduler */
  lazy val pingpongbench = pingpongTaskList
  /** produces a sequence of run tasks using all the available schedulers  */
  def pingpongTaskList = {
    val pairs = 100
    val messagesPerPair = 10000
    val tasks = for(sched <- schedulers) yield pingpongTask(sched, pairs, messagesPerPair)
    tasks.reduceLeft((a, b) => a && b)
  }

You can see the whole file here. Basically Task has an && operator that essentially allows you to concatenate one task with another task. This allows you to build a whole chain of tasks. In the example above, I'm having it run the benchmark once for each scheduler configuration. Soon, I'm going to make it permute other parameters. But right now my test harness isn't playing nicely with the schedulers included in the Scala distribution, so first things first.

There's also one other little customization, which is documented, but I think it's important for benchmarking. By default, sbt runs your code in its own process. This can cause problems with multithreaded code, especially if it doesn't terminate properly. It also means the next benchmark to run has to content with any junk that the previous benchmark left around. So I configured sbt to fork new processes. It just required one line:

override def fork = forkRun

Important variables

Here's what I'm capturing for each run right now so that the results can all be dumped into a big spreadsheet for analysis. I'd like to capture more information about the host machine, such as more information about the CPUs and the loading when the benchmark is being run, but haven't got that far yet. Currently these are all captured from within the benchmark process, mostly using system properties and the Runtime object.

Test Name - obviously needed so that results from multiple benchmarks can be stored in the same file
Scheduler - this is my primary variable right now, I want to run each benchmark with each scheduler while holding everything else constant
# of Cores/Processors - essential so that anyone looking at the results has an idea about the hardware used
Java VM Name - different VMs can perform quite differently
Java VM Version - performance characteristics change from version to version (usually getting better)
Java Version - same reason as above, but this is probably the more publicly known version number
Scala Version - this could be important in the future, as it becomes more common for different projects to be on different version of Scala
OS Name and version - again, it can affect performance
Processor Architecture
Approximate Concurrency (number of simultaneously alive actors) - this allows us to examine concurrency levels versus resource consumption, more concurrency does not necessarily mean that more cores or threads would be helpful
Approximate Parallelism (number of simultaneously runnable actors) - this measures how many cores/threads the benchmark can really keep busy
Approximate Total Messages - this estimates the amount of activity that takes place during the benchmark, generally the benchmarks I'm looking at contain very little logic because they are intended to measure overhead introduced by the framework
Total Wall Clock Time (seconds) - as measured using nanoTime within the benchmark process
Initial Thread and Maximum Observed Thread Count - used to examine automatic expansion of the thread pool
Initial Free Memory and Minimum Observed Free Memory - threads use a fair amount of memory, so performance impacts may show up as pressure on the GC as well has contention for the CPU
Initial and Maximum Observed Total Memory - threads use a lot of memory, so it's important to track usage
Verbose - debugging output pretty much invalidates any of these tests

Improving Schedulers for High-level, Fine-grained Concurrency Frameworks

2010-08-08T18:33:00.007-04:00

Quite a while ago, Greg Meredith made a comment that really made me stop and think, and that has been lingering in the back of my mind ever since:

Erik, Alex, John, et al, i'm loathe to hijack this thread -- which is a good one -- but the experience with the lock up described below is really just the tip of the iceberg. Unless specific scheduling contracts and semantics can be worked out, a pluggable scheduling architecture is just asking for disaster. Worse, it means that a whole host of compiler support that could be provided to apps that use actor-based concurrency is null and void because those solutions (be they model-checking or types-based) will critically depend on specific ranges of scheduling semantics. Actors and other higher level concurrency constructs are a major appeal of languages like scala. If they prove themselves to be "not ready for prime time" the impact on perception might not be contained to just that usage of the language. Best wishes, --greg

That wasn't the first time that Greg made a comment along those lines, and it certainly wasn't the last. At one point he offered to allow a few individuals look at some older code that he believed could help. Greg's a really smart guy. If he's worried, we should all be worried.

Empirical Evidence of the Problem

Contrary to what many may think this is hardly an academic problem. A significant portion of the issues people new to Scala Actors have trace to the fact that they expect the scheduler to be making guarantees that it simply does not make. Here's a sampling:

Actors not creating enough threads
Scala Actors different behavior on JRE 1.5 and 1.6
Actor starvation problem (related to previous)
Actor as new thread

There are others, including cases where people have both rightly and wrongly blamed the default scheduler for serious problems with their programs. Most of the above can be traced back to the fact that the default scheduler for Scala Actors uses a slightly modified version of the JSR166y ForkJoinPool, which has issues described below (source):

Like all lightweight-task frameworks, ForkJoin (FJ) does not explicitly cope with blocked IO: If a worker thread blocks on IO, then (1) it is not available to help process other tasks (2) Other worker threads waiting for the task to complete (i.e., to join it) may run out of work and waste CPU cycles. Neither of these issues completely eliminates potential use, but they do require a lot of explicit care. For example, you could place tasks that may experience sustained blockages in their own small ForkJoinPools. (The Fortress folks do something along these lines mapping fortress "fair" threads onto forkjoin.) You can also dynamically increase worker pool sizes (we have methods to do this) when blockages may occur. All in all though, the reason for the restrictions and advice are that we do not have good automated support for these kinds of cases, and don't yet know of the best practices, or whether it is a good idea at all.

The Scope of the Issue

The issue here is neither limited to Scala nor to actor based concurrency. The general consensus in the concurrency community is that locks and threads are not the right abstractions for concurrency in application code (or hardly any code, for that matter), but there isn't any consensus on what the right abstractions are, or if there is consensus it is that the right abstractions are problem specific. There's no one-size-fits-all concurrency abstraction.

The one trait that all high-level or higher-order concurrency abstractions have in common is that under the hood they rely on some sort of managed thread pool and/or scheduler. For purposes here, when I say "scheduler," I mean the layer with which a concurrency framework interacts directly and likely contains framework-specific logic. When I say "thread pool," I mean the layer that directly manages the threads and is concurrency framework agnostic and may even be shared by several schedulers (sharing will be problematic, but I think ultimately necessary). This isn't a hard line, and often times they may be lumped into one. However I think it's a useful dichotomy. I'm also assuming the scheduler and thread pool rely on cooperative thread sharing, and that preemptive multitasking is left to the virtual machine and/or operating system.

The point is, any concurrency abstraction where the user can submit arbitrary code to be executing can ultimately run into serious issues if that user code does something it does not expect. For example, the fork-join scheduler from JSR-166y that the Scala Actors library uses (I think Clojure uses it as well, but it may not) doesn't automatically enlarge its pool in the presence of unmanaged blocks (including normal blocking IO) or simple long-running computations. This results in the majority of the problems I previously cited, because blocking operations are extremely common tasks, and thus a very leaky abstraction.

Key Characteristics of a Good Scheduler

Unfortunately my command of type theory is rudimentary at best, so while Greg could probably describe a well-behaved scheduler using types, I'm going to have to resort to plain English:

The user should not have to think about choosing a scheduler.
The user should not have to think about the size of the thread pool managed by the scheduler.
The user should be able to write code naturally without worrying about any assumptions the scheduler may make
The user should not have to worry about starting or stopping the scheduler
Multiple flavors of concurrency abstraction should be able to share the same thread pool.
The scheduler should impose minimal overhead.

There's probably others, but I think this is a good start.

The Performance Problem

So why hasn't this problem already been solved? Perhaps it has been already and I just don't know about it. If someone has, please let me know. But as far as I can tell it's because there's a perceived nasty performance trade. Here's a quote from Philipp Haller:

The starvation detection mechanism in Scala 2.7 was too expensive to support in the new default scheduler. However, there is a starvation detection mechanism for thread-blocking methods of the `Actor` object (`receive` etc.).

Similar answers have been provided when people have questioned the wisdom of using the FJ framework over the classes included with the JDK. I've tested it a bit and it's true, the FJ framework does yield a significant improvement for certain classes of tasks over JDK classes (although I believe using exceptions for control flow imposes a far larger penalty). Basically it appears that the overhead associated with known solutions to the problem overcomes the introduced benefits of fine-grained concurrency,

ForkJoinPool in a nutshell

What makes ForkJoinPool so fast (other than highly optimized code) is that uses a two-level architecture for its task queues. There's one queue for the pool, and the one dequeue per thread. Most of the data associated with the dequeues is only updated from the owning thread so that tasks can be added and removed without synchronization and minimal volatile and CAS operations. The worker threads also steal work from one another in order to spread out the load. When a worker is deciding the next task to execute, it performs the following checks, using the first one to return a task:

The thread's own local dequeue
The dequeues of other threads in the pool, scanned in a psuedo-random pattern with guiding hints
The common task queue

Threads are only added to the pool if a ManagedBlocker that the pool can see if used to block causing the target concurrency to not the be met. The default target concurrency for the ForkJoinPool is set to the number of available processors. In Scala Actors this is overridden to be twice the number of available processors. The idea behind this is simple: If you're keeping all your processors busy, then adding more threads will just slow you down. As we've seen, problems arise when a higher level of concurrency is needed due to unmanaged blocks, long running computations, or simply the required concurrency being inherently higher than the default concurrency. This happens because as long as a worker is busy or has something in its local dequeue, it won't look elsewhere for tasks. If all the workers are in this state, tasks can simply accumulate, resulting in starvation.

A Crack at Solving the Problem

As you might have guessed by now, I'm trying to solve this problem. Right now I wouldn't use the code for anything beyond testing the code, but despite the fact I'm still wrestling with the internals of ForkJoinPool I've experienced good results so far. My approach is simple: I added in a manager thread that monitors the changes in size of the various queues in the pool, and if they've been flushed since the last check, and grows the pool it tasks appear to be being starved. The overhead imposed on each worker is minimal, as it only has to update a single additional volatile field when it clears out its queue. The overhead of the manager thread is something, but in the benchmarking I've done so far it doesn't seem to add noticeable overhead. Ironically, Scala Actors already maintain a dedicated thread for the scheduler, its just that the heuristic check on the size of the pool were removed in 2.8 (although honestly they never worked that well).

I have two simple tests/micro-benchmarks using Scala Actors with a custom scheduler built on my ManagedForkJoinPool. The SleepyActor benchmark performs extremely poorly if the scheduler doesn't significantly grow the pool, because each actor sleeps on the thread. The PingPong benchmark spawns a bunch of pairs of actors that simply message each other back-and-forth. It is the type of use case where the ForkJoinScheduler shines, at least in terms of throughput. The results on my MacBook are as follows (these are NOT scientific):

Benchmark	Default Scheduler	ManagedForkJoinScheduler	ResizeableThreadPoolScheduler
SleepyActor	92 sec	30 sec	not tested
PingPong	59.49 sec	47.17 sec	66.02 sec

As you can see, performance actually improved with my scheduler. This is because the default scheduler for Scala Actors does not always use the "fast path" and put new tasks on the dequeue of the thread creating them. It only does it about half the time. So for the PingPong test you can see how the thread local queues impact performance.

Conclusions

It's too early to draw solid conclusions, but based on what I've done so far I think I can develop a solid heuristic for managing the thread pool size, and that the overhead will be negligible. The key is to not impose any more overhead on the worker threads, and to keep the computational overhead of the manager thread a low as possible. This means that the heuristic needs to be simple, and that the wait times between checks should be a long as possible, probably dynamically sized based on how smoothly the pool seems to be running.

What I need right now are more tests and benchmarks to cover "real world" scenarios. I also need to test on machines with more cores. My MacBook doesn't exactly present a powerful system. If anyone has suggestions, please post them!

Is the Market for Technical Workers a Market for Lemons?

2010-08-01T08:55:00.004-04:00

I saw this article about Amazon Mechanical Turk this morning, and it struck me that the market for technical talent, and especially in software engineering and IT talent, is a market for lemons. For a little more critical (and hopeful!) look at the idea, take a look at this post at the Mises Institute.

What's a Lemon Market?

The basic idea behind a market for lemons is that the seller has significantly more information about the quality of a product than the buyer (e.g. an information asymmetry). The consequence of this is that buyers are unwilling to pay for more than the perceived average value of the goods on the market, because the buyer does not know whether he is going to get a cherry (a high quality good) or a lemon (a low quality good). This then creates disincentives to sell cherries, because buyers will not pay their market value, and incentives to sell lemons, because they can be sold for more than they are worth. This creates a sort of vicious cycle where high quality goods are withdrawn for the market, thus lowering the average quality of the available goods and consequently the prices buyers are willing to pay. The ultimate result is a race to the bottom in terms of prices, with high quality goods vanishing as collateral damage.

There are five criterion for a lemon market (paraphrased and reordered from Wikipedia):

Asymmetry of information such that buyers cannot accurately assess the quality of goods and sellers can.
There is an incentive for sellers to pass off low quality goods has high quality goods.
There is either a wide continuum in the quality of goods being sold, or the average quality is sufficiently low such that buyers are pessimistic about the quality of goods available.
Sellers have no credible means of disclosing the quality of the goods they offer.
There is a deficiency of available public quality assurance.

The Lemon Market for Technical Talent

The market for technical talent is similar. The information available about most job candidates for technical positions is superficial at best, and completely inaccurate at worst. Furthermore, even when information is available, the buyers often do not have the knowledge required to evaluate it. This even extends existing, long term employees and contractors. Finally, the quality of an employee is often highly contextual - environmental and cultural factors can significantly boost or dampen a person, and those same factors may have the opposite effect on another. So let's rundown the different factors:

Information Asymmetry: Resumes are short, shallow, and often deceptive. Technical skills are very difficult to assess during an interview, and cultural fit can be almost impossible to assess.
Incentives for sellers to deceive buyers: Resumes are deceptive for a reason. It's often stated that you need to pad your resume, because the person looking at it is automatically going to assume it is padded. Furthermore, for almost two decades now technology has been a source of high paying jobs that can be obtained with marginal effort (just turn on the radio and listen for advertisements for schools offering technology training).
Continuum in the quality of goods: This exists in all professions.
Sellers have no credible means of disclosing quality: This is largely but not entirely true. Most paid work that technology professionals do cannot be disclosed in detail, and even when it is there is reason for sellers to doubt the credibility. Employment agreements may also place restrictions of the disclosure of closely related work, even if it is done on one's on time with one's own resources.
Deficiency of public quality assurance: Employment laws and potentials for litigation (at least here in the U.S.) make the disclosure of employee or even outsourcer performance very risky. Individual workers cannot effectively provide guarantees, and those provided by outsourcers are generally meaningless.

All this really amounts to is: Sellers have no good way of providing information regarding their high quality products, and buyers have no good way of obtaining reliable information about a seller's products. The problem centers entirely around making information available and ensuring its accuracy.

What Technology Professionals can do

Technology Professionals need to build up public reputations. We need to make samples of our work, or at least proxies of samples, publicly available. We need to build more professional communities with broader participation and more local, face-to-face engagement.

I think broader participation is the key. If you look at other professions (yes, I know, I'm lumping all "technology professionals" together and I frequently rant against such a lumping), members are much more active in various groups and associations. In many it's expected and even explicitly required by employers. Sure, there are tons of groups on the internet. There are numerous, and often times enormous technology conferences. There are countless technology blogs and community websites. But I think the conferences are generally too big to be meaningful because most attendees essentially end up being passive receptacles for sales pitches (that's the purpose of these conferences) and maybe they do a little networking and learning on the side. I think even the most active community sites really represent very small slices of the professionals they are intended to serve. Most professionals are passive participants in them at best, just like with conferences.

But there are millions of engineers, software developers, and IT professionals out there. Millions! How many of them do you find actively participating in professional communities of any kind? Not many when you really think about it. This is a problem because as long as the vast majority technology professionals have no public, professional identity, the vast majority of employers aren't going to see professional reputation as a useful search criterion or even measure when considering candidates.

What Employers can do

Employers can do one of two things:

Expect applicants for new positions to provide meaningful evidence of their skills and take the time to evaluate such evidence
Just outsource everything to the cheapest company possible. Information on quality is largely unavailable and unreliable, but information on price is readily available and relatively accurate.

You can see which one of those strategies is dominating the marketplace. One requires effort and involves going against the tide. The other is easy (at least to start, it's not easy to make work), and involves running along with the herd.

Except in the limited number of cases were employers, and the hiring managers who work for them, genuinely believe they can achieve a competitive advantage by actively seeking out candidates with demonstrated qualifications (as opposed to a padded resume and fast talk during an interview), I don't think employers are going to seriously consider reputation and objective evidence of skills until such information is easily obtainable and fairly reliable.

Is there any hope?

Yes!

We live and work in an information economy where new forms of information become available everyday. There is no reason to believe just because today employers mostly hire on faith and expect luck to carry them through, the in the future there won't be much more information available. I'm sure there are several companies working on aggregating such information right now. The market is huge. While companies will rarely put much effort into obtaining information and aggregating it into a useful form, they will often pay large quantities of money for it. The key is to make sure the information is there for them to use.

Also, if your resume makes it through all the wickets to a real hiring manager, if you provide an easy way for him to find more good information about you, he'll probably use it. Interviewing people is a lot of work. Deciding among candidates can be very hard. Extra information will almost certainly be used. It just has to be easy to obtain. People are lazy.

But what about old fashioned networking?

I think the numbers involved are too large and relying on old-fashioned networks tends to yield too poor of results. Recommendations and referrals are certainly useful and lead to many, many hires. But they tend to be made more based on personal relationships than based on real qualifications and therefore need to be checked. Schmoozing isn't a real technical skill. That being said, it could quite likely get you a job. It's just that in general I don't want to work with such people in a technical capacity, so I'm not going to recommend people go do it in order to obtain technical jobs. I'm selfish that way.

Higher-Level versus Higher-Order Abstraction

2010-07-27T21:35:00.009-04:00

Engineering in general, and software engineering in particular, is all about abstraction. The creation and utilization of abstractions is a core part of the daily activities of every good engineer, and many engineers are on a never ending quest to increase their level of abstraction. Abstraction both increases productivity and increases the complexity of problems that can be tackled. Few would argue that increased abstraction is a bad thing.

But people do argue about abstraction, and often condemn abstractions that they view as unfit or too complex. It is common to hear a software developer praise the merits of one means of abstraction and then demean another in the same breath. Some abstractions are too general. Some aren't general enough. Some are simply too complex or, ironically, too abstract. So while engineers almost universally agree that abstraction is good, and more abstraction is better; they often disagree fiercely about what genuinely constitutes "better."

What is an abstraction?

Simply put, an abstraction is something that hides the details involved in realizing a concept, and thus frees the engineer to focus on the problem at hand rather than the details of some other concern. This can take many, many forms. The simplest and most common, so common that the term is often used to describe almost all "good" abstractions, is higher-level abstractions.

Higher-level Abstractions

Higher-level abstractions are fairly simple: they encapsulate details so that they can be used without knowledge or concern about the details. Let's consider a simple example in Scala 2.8 (you can copy and paste these examples directly into the Scala 2.8 REPL):

scala> def sum(data: Array[Double]): Double = {
     |   var i = 0
     |   var total = 0.0 
     |   while(i < data.length) {
     |     total = total + data(i)
     |     i = i + 1
     |   }
     |   total
     | }
scala> def mean(data: Array[Double]): Double = sum(data) / data.length

So we have two functions: one that computes the sum of an array of doubles, and one that computes the mean. Pretty much any programmer (professional or otherwise) would feel confident both writing and using such functions. They are written in a modern multi-paradigm programming language yet I bet if you went back in time and showed them to programmers in some of the very first high-level languages they would recognize exactly what they do. They clearly encapsulate the details of performing certain computations. But what's more interesting about them is what's missing from them:

Polymorphism
Closures or first-class functions
Usage or creation of higher-order functions
Other Scala magic such as type classes and implicit parameters

In other words, they provide a simple, layered, hierarchical abstraction in a very bounded way. If we step away from software for a minute, you can imagine a digital designer placing a symbol for an adder or a register on a schematic without worrying about the arrangement of transistors that will be required to realize them in an actual circuit, or a mechanical engineer selecting a standard screw or clamp. These are parts that can be simply built, tested, and composed into larger devices.

Higher-Order Abstraction Take 1: The Mathematics of Fruit

Imagine I have some apples. But unfortunately I'm here, off in the internet, show I can't show them to you. I need an abstraction to tell you about them. For example, I could say I have two apples. Two is a number, and numbers are abstractions. I can use the same number two to describe the number of McIntoshes in my refrigerator or the number of Apple Macintoshes I own. Now let's say I also want to talk about my strawberries and blueberries. I have 16 strawberries and 100 blueberries. How many pieces of fruit do I have? 118! How did I figure that out? I used arithmetic, which is an abstraction of higher order than numbers. How let's say I want to know how many days it will be before I will have eaten all my strawberries. I can write an equation such as: current_fruit - pieces_per_day * number_of_days = fruit_after_number_of_days. I can do even more with this by solving for different variables. This is algebra, and it is a higher-order abstraction than arithmetic. Now let's say I want to build upon that so that I can study the dynamics of the amount of fruit in my refrigerator. I purchase fruit and put it in my refrigerator. I take fruit out and eat it. I forget about fruit and it gets moldy, the I remove it and throw it away. I can capture all of these as a system of differential equations, and using calculus describe all sorts of things about my fruit at any given point in time. Calculus is a higher-order abstraction that algebra. In fact, abstractions similar to the ones built with calculus are what I mean when I say "higher-order abstraction."

At each step up the chain of mathematics both the generality and number of concepts that can be conveyed by a single abstraction increased. In the case of calculus it becomes essentially infinite, and that's the essence of higher-order abstractions: they deal with the infinite or near-infinite. Also, observe that almost everyone from relatively small children on up understand numbers and arithmetic, most adolescents and adults can stumble through applying algebra, and only a very small portion of the population knows anything about calculus, much less can effectively apply it. Also observe that the functions I defined earlier are just below algebra in terms of their order of abstraction.

Higher-Order Abstraction Take 2: Programming in Scala

Let's see if we can sprinkle some higher-order abstraction into our previously defined functions:

scala> def sum(data: Traversable[Double]) = data.foldLeft(0.0)(_ + _)

This definition of sum exposes one higher-order abstraction (polymorphism - it now can use any Traversable[Double] instead of just an Array[Double]), and it uses higher-order functions in its implementation to perform the summation. This new definition is both much shorter and much more general, but it's still relatively approachable, especially for use. Calling it with an Array[Double] works as before, and now it can be used with any number of collections, so long as the collections contain doubles. But forcing the collections to contain doubles is very limiting, so let's see if we can do better:

scala> def sum[T](data: Traversable[T])(implicit n: Numeric[T]): T = {                                  
     |   import n._
     |   data.foldLeft(zero)(_ + _)
     | }

Ahhh, that's better! Much more general. Not only will this work for any numeric type defined in the Scala standard library, but for any numeric type for which the Numeric type class has been defined! It doesn't even need to be in the same class hierarchy! In order to introduce this new level of generality, we've also introduced the following higher-order abstractions:

Classic polymorphism (Traversable instead of Array)
Parametric polymorphism (the type parameter T for various classes)
Higher-order functions and closures (foldLeft and it's argument that does addition)
Type classes (well, Scala's flavor of type classes, e.g. Numeric)

Now, this is the point where people start screaming that abstraction has gone too far. Many professional programmers would look at it and think "WTF?" They could still guess what it does, but the mechanics are quite elusive for anyone that doesn't know Scala reasonably well. That being said, the code is still far more compact than the original imperative version and is extremely general (to which someone replies "Yes, but it's slow a heck compared to the original!"). At this point I would say the order of abstraction has went from being just below algebra to being on par with integral calculus. Just like with mathematics, we see a significant drop off in the number of people who readily understand it.

Higher-Order Abstraction Take 3: Conclusions

Let's consider a short, incomplete list of higher-order abstractions, means of abstraction, and fields that rely upon higher-order abstractions:

Higher-order functions
Polymorphism and parametric polymorphism
Metaclasses such as in Python and Smalltalk
Rich macros such as in Lisp or C++ Templates
Calculus and all the mathematics built upon it (and various other forms of advanced math)
First-order Logic and its kin, and all the higher-order logics
Any physics or other sciences that are built upon calculus
Any engineering or other applications that are built upon physics

Higher-order abstractions tend to exhibit one or more of the following traits:

They deal in infinities (e.g. integration and differentiation in calculus, universal and existential quantification in first-order logic, polymorphism and type classes in programming)
They deal in transformations (e.g. integration and differentiation in calculus, metaclasses and macros in programming)
They rely upon composition rules (e.g. chain rule and integration by parts in calculus, higher-order functions in programming)
Learning to use any given form of higher-order abstraction requires significant effort and discipline, therefore they tend to be the tools of specialists
They form the foundation of our modern, technological society.

The last two can be converted into conclusions:

Higher-order abstractions are critical for most interesting forms of science and technology
You can't expect a colleague or customer from another field to understand the higher-order abstractions in your field, even if his own field is totally immersed in higher-order abstraction

Windows 7 Upgrade (so far)

2010-07-24T20:32:00.002-04:00

A few weeks ago my wife's Lenovo laptop caught a really nasty virus. Symantec antivirus couldn't clean it up. But I had recovery media (although it was Vista instead of XP), so I used Knoppix to low-level the HD and flashed an updated BIOS (I've had previous experience with viruses that could be stopped via nothing less). Unfortunately the restore media didn't work...it would boot up, think a while, and the reboot. I also tried a XP install using an old XP disk I had laying around, but the XP installer doesn't get along with the new SATA controller in the laptop, so it BSODs. Working around this problem seems to require creating a special driver disk, which seems to require Windows, which creates a problem because all I have are Leopard (about 2 crashes in almost 3 years, a no viruses, versus what seems like a plague on my wife's laptop every 6 months), and Knoppix. So, being a person who value's his time more than his money, I went out and bought a Windows 7 Professional upgrade. All the Microsoft related blogs assured me this would work, and indeed I have a working install the went almost a smooth as butter. The "almost" is the activation process. I have yet to successfully activate. Going into this my assumption was I would have to call Microsoft in order to activate. What I didn't realize is that their human systems don't seem any smarter than their automated systems. So first I called the phone number that Microsoft's support website told me to call. Several layers deep this told me to call a special activation line. I want to commend Microsoft at this point for avoiding such advanced technology as call transfers. You really can't trust technology that's decades old. It's better to let people transfer themselves. So I call the line, and speak to a very friendly automated system. It's asking me for my "installation id," but there isn't one. There isn't one because the computer is connected to the internet, and some genius decided that if one has the internet one would never use the phone system, which would normally be true if some brilliant licensing policy maker hadn't decided that the only way to activate a "clean install" is via the phone system. Anyway, the nice automated system transfers me to a human being. Guess what the human asks me for? An installation id. I tell him I don't have one. I read the various things on my screen to him. He then asks if I am connected to the internet. I say yes. He tells me to disconnect. I disconnect and start over, ultimately ending up in the same place with no installation ID. The support person gives up and tells me I have a deep technical problem, which will require technical support, not activation support (I'm now imaging myself setting up a conference call with tech support, activation support, and the nice automated system lady). Tech support is of course only a US working hours affair, not a Saturday evening affair. It turns out the automated support guy just wasn't persistent enough. After hanging up, I reboot the computer and try again without internet. It appears to get me to the same place, except when I hit the magic "next" button, instead of receiving a message telling me that my product key is not valid, I receive an installation ID and am told to call the activation line (which is a 3rd phone number, but gets me to the same place as the first). I want to take a moment to point out some huge flaws here:

The automated system just assumed I would have an installation ID, and had no explanation of how I was supposed to obtain one or why I might not see one, while the activation software is explicitly designed to not provide one to someone connected to the internet
The human being had a vague idea that being connected to the internet was a problem, although he didn't realize it until repeating his requests half a dozen times, and even though he had a vague idea how to induce Windows 7 into providing one, he didn't actually know and gave up quickly
About 2 minutes would of poking after 30 minutes of bouncing around on the phone rewarded me with an installation id

Ok, so let's try again. This time I provide the installation id to the automated system, and the automated system informs me that it is invalid, and sends me to another human being. After 5 or 10 minutes the human being informs me that I need to have a Microsoft OS already installed in order to use an upgrade, and that I cannot use a clean install. He says it is impossible that Windows XP would refuse to install, and thinks it's completely reasonable that I would install one OS just to install another. I rant at him for a few minutes about how my product packaging says nothing about not being able to do a clean install (in fact, it's the only way to upgrade from XP according to the included instructions, although maybe it does some magic if the installer reformats the HD instead of the user already doing it). Anyway, I explain this all to him while trying to remain calm. He puts me on hold. Then when he comes back he tells me that he gave me wrong information because a server is down, and that I need to call back in 30 minutes when the server is up. So I did that. This time after I read my installation ID to the support person, which he told me was invalid. He told me to exit activation and enter my product key again. I dutifully did this, then he put me on hold while he waited for my product key to come up. This of course would never happen, because I wasn't connected to the internet, and it fact cannot obtain an installation id when connected to the internet. After a few minutes on hold, I was transfered to Microsoft technical support, which of course was closed. So let's recap so far:

None of the Microsoft activation people or systems know what you need to do in order to obtain an installation id, all of them expect you to just have one
In order to obtain an installation id, as far as I can tell you can't be connected to the internet (certain options only appear if you are not connected)
Some support people seem to assume that you are connected to the internet, even though the information they request will never come up if you are not connected to the internet
Support people will transfer you to a line that will not answer without even telling you that you are being transfered
That line seems to only be open during US business hours, which would mean they seem to assume that either you professionally support Microsoft products or are unemployed.

If I can't make this work tomorrow, I think I'm going to obtain an updated version of MS Office for my Mac and give it to my wife, then just install Ubuntu on her laptop.

Changing Tastes

2010-01-16T10:31:00.000-05:00

When I was a kid, I hated onions, green peppers, and mushrooms. I used to tell people I was allergic to mushrooms so they wouldn't try to make me eat them. I hated any sort of chunky sauce or really textured meat. I think I wanted everything to have either the consistency of a chicken nugget or ketchup. My parents used to tell me that when I was older my tastes would change. That I liked crappy food, disliked good food, and eventually I would realize it. They were right.

So kids like chicken nuggets and ketchup. Wow, huge revelation. What does this have to do with technology? I'm on the steering committee for an internal conference on software engineering that my employer is holding. I'm the most junior person on the committee, and most of the members are managers who have more managers reporting to them. Our technical program committee (separate, more technical people on it, but all very senior) just finished abstract selection and we've been discussing topics and candidates for a panel discussion. During this process I have been absolutely shocked by how my tastes differ from those of my colleagues.

I've noticed that within the presentations selected topics on process, architecture, and management are over-represented. On the other side, many of the abstracts that I thought were very good and deeply technical fell below the line. I can't quite say there was a bias towards "high level" topics, because I think they were over-represented in the submissions. Given the diversity of technology that's almost inevitable. A guy doing embedded signal processing and a guy doing enterprise systems would most likely submit very different technical abstracts, but ones on management or process could be identical. It's almost inevitable that topics that are common across specialties will have more submissions.

There's a similar story with the panel discussion. I wanted a narrower technical topic, preferably one that is a little controversial so panelists and maybe even the audience can engage in debate. My colleagues were more concerned with who is going to be on the panel than what they would talk about, and keeping the topic broad enough to give the panelists freedom.

What's clear is that my colleagues clearly have different tastes in presentation content than me. I think they are genuinely trying to compose the best conference they can, and using their own experiences and preferences as a guide. I think their choices have been reasonable and well intentioned. I just disagree with many of them. If I had been the TPC chair, I would have explicitly biased the selection criteria towards deeper, technical topics. Those are the topics I would attend, even if they are outside my area of expertise. I would use my preferences as a guide. But that leaves me wondering, in another five years or ten years are my tastes going change? My tastes have certainly changed over the past decade, so I have no reason to believe they won't change over the next. Will I prefer process over technology and architecture over implementation? Will I stop thinking "show me the code!" and "show me the scalability benchmarks!" when see a bunch of boxes with lines between them? I don't think so, but only time will tell. When I was a kid, I would have never believed that I would ever willingly eat raw fish, much less enjoy it, but today I do.

Your Company's App

2010-01-05T22:59:00.001-05:00

Tim Bray just posted a blog about how Enterprise IT is doing it wrong. I can't really argue with that. He goes on to explain that Enterprise IT needs to learn from those companies building Web 2.0, because they deliver more functionality in less time and for a whole lot less money. This is where his argument breaks down. The problem is the type of Enterprise Systems he's talking about aren't Twitter, they're your company's app.

I work at a pretty big, stodgy, conservative company. I'm pretty sure, as far as things like ERP and PLM are concerned, my employer is exactly the type of company Tim is talking about, and like I said - he's probably right about the problem. But based on my own experiences and observations at my one lonely company, I think he's wrong in his suggestions. Comparing ERP and Facebook is like comparing apples and Apple Jacks.

The reason I think this is that in terms of deploying Enterprise 2.0 applications I think my employer has done fairly well. We have...

A wiki
A "business networking" site, kind of like Linkedin
A microblogging site
A question & answer board similar to Stack Overflow
An on-demand cloud computing environment, kind of like Amazon E2C

...and probably more stuff that I'm not aware of yet. Some of the above were bought, some were built, some were cobbled together with stuff from a variety of sources. I think most of them were built and deployed, at least initially, for costs about as competitive as possible with Web 2.0 startups and in reasonable timeframes. Of course, this means intranet scale at a Fortune 100 company (or in some cases a subset of it), not successful internet scale.

The problems the above face is much like the problem your typical startup faces: attracting users, keeping investors (sponsors) happy, dealing with the occasional onslaught of visitors after some publicity. But these problems are very different from the problems a traditional Enterprise Application faces. There is SOX compliance. There are no entrenched stakeholders. There are no legacy systems, or if there are they aren't that important. If only 10% of the potential user community actually uses the application, it's a glowing success. Negligible adoption can be accepted for extended periods while the culture adjusts, because the carrying cost of such applications is low.

But enterprise systems needs to deal with SOX. They have more entrenched stakeholders than you can count. These days there's always at least one legacy system, and often several due to disparate business units and acquisitions. If these systems fail, business stops, people don't get paid, or the financials are wrong. If only 90% of your buyers use your ERP systems to process purchase orders, it's an abject failure and possibly endangering the company.

A year or two ago someone "discovered" that a very common, important record in one of our internal systems had 44 (or something like that) required fields, and decided that this was ridiculous. A team was formed to streamline the processes associated with this record by reducing the number of fields. A detailed process audit was conducted. It turned out that every single one of them played a critical role in a downstream process. All the fields remained, and some old timers smiled knowingly.

As many humorless commenters pointed out on Eric Burke's blog, your company's app is your company's app for a reason, and often it's a good reason. These applications aren't complicated because of the technology. Internet applications are complex due to extrinsic forces - the sheer number of users and quantity of data that can deluge the application at any given moment. Enterprise systems tend to be the opposite. Their complexity is intrinsic due to the complexity of the diverse processes the support. The technology complexity (most of which is accidental) is secondary. Tim's suggestions provide a means of addressing technological complexity, and of building green field non-business critical applications in the face of uncertain requirements. They don't provide a means for dealing with critical systems laden with stakeholders, politics, and legacy.

I think the solution, or at least part of the solution, to the problem with enterprise systems lies in removing much of the functionality from them. There are things that must be right all of them time, but most of business (and engineering, etc) exists on a much fuzzier plane. The problem comes from coupling the precise (e.g. general ledger) with the imprecise (e.g. CM on an early stage design), and thus subjecting the imprecise to overly burdensome controls and restrictions. Only after this separation has been carefully implemented can functionality evolve in an agile fashion.

Pondering Actor Design Trades

2009-06-21T21:20:00.002-04:00

There's been a lot of discussion of the Scala actors library lately, much of it critical, and a recent flurry of alternate implementations. The alternate implementations (except my languishing state-based one ;-) all have one thing in common: They are several orders of magnitude simpler. Writing a basic actor implementation is actually pretty trivial, especially given java.util.concurrent classes that provide a decent chunk of the functionality in Scala actors, all for free on JDK5+. So this begs the question few questions:

Why is the standard Scala actor implementation so complex when others have done it in a such simpler fashion?
Is it better to have one, big actor library that supports a wide variety of use cases, or a bunch of smaller ones targeted at specific niches and programming styles?
If there are to be a bunch, should they just be conceptually similar (e.g. all based on the actor model), or should there be interoperability among them?

I'm not going to answer these questions now. Instead, I'm going to try to start laying out some of what I believe to be the key characteristics of an actor implementation, and how they detract or enforce one another. So here it goes:

Guarantees
Expressivity
Extensibility
Performance
Scalability

Guarantees

The purpose of a concurrency framework is to make concurrency easier. Concurrency is hard largely because it is extremely difficult to reason about, and thus concurrent code tends to be hard to write, laden with bugs, and subject to various odd pitfalls. By providing various guarantees, a concurrency framework makes it easier to reason about concurrent code. Actors are intended to free the programmer from worrying about things like locks, semaphores, thread management, etc. by encapsulating all that complexity behind a simple interface, assuming the programmer follows some basic rules like "no shared mutable state among actors."

The problem with guarantees is that in they tend to break down in the presence of limited CPU and memory resources.

Expressivity

Expressivity is difficult to define. For purposes here, I'm going to define it as the degree to which a concise, natural expression of the programmer's intent is supported, and illustrate it by comparing Scala Actor to Lift Actor. Scala Actors allow you to execute logic independent of message processing (note: this a violation of the theoretical model for actors) by simply placing it in the act method. Lift Actors, on the other hand, are only triggered when they receive of message (this is consistent with the theoretical model). For example, this makes it so that Scala Actors can do things such as perform possibly costly setup operations in their own thread before they start listening for messages. In order to accomplish this in the Lift model, the programmer must create the actor and then send it some sort of "init" message. The same effect can be achieved with both implementations, but it is more naturally supported by Scala Actors. Of course there is a tradeoff here, as deviating from the theoretical model potentially weakens any guarantees that the model may provide. The Scala Actor way also implies that an Actor has an explicit lifecycle, which as we'll see later has other significant implications.

Another example is what I'll call the "nested react pattern." It is relatively common to want an actor to take on a different behavior after processing a message, thus altering which messages are ignored and how the received messages are processed.

loop {
 react {
    case 'foo => { 
      // do some stuff...
      react {
        case 'bar => // do some other stuff... 
      } 
    } 
  } 
}

The code above alternates between processing 'foo messages and 'bar messages. This can be done with Lift Actor as well, but the expression is a little less natural:

class MyActor extends LiftActor {
  private val fooMode: PartialFunction[Any, Unit] = {
    case 'foo => {
      // do some stuff
      mode = barMode
    }
  }
  private val barMode: PartialFunction[Any, Unit] = {
    case 'bar => {
      // do some other stuff...
      mode = fooMode
    }
  }
  private var mode = fooMode
  protected def messageHandler = mode
}

Finally, Lift Actors exclusively use an event-based model and have no support for blocking on a thread while waiting for a message, and thus looses the ability to express patterns such as the following:

loop {
  react {
    case 'converToNumber => {
      val i: Int = receive {
        case 'one => 1
        case 'two => 2
        case 'three => 3
      }
      reply(i)
    }
  }
}

Extensibility

For purposes here, I'm going to use "extensible" to mean that a piece of software is extensible if capabilities can be added without modifying the core or breaking its semantics in a amount of effort proportional to the size of the extension. This is narrower than the traditional definition of extensibility, which also covers the ability of a system to evolve internally. A good example of extensibility is the ability of both Scala Actors and Lift Actors to allow the user to specify a custom scheduler. Other examples could include adding control structures, using a different data structure for a mailbox.

The challenge with extensibility is that in order to enable it, what could otherwise be treated as the internal bits of the library must instead have well defined interfaces for components along with appropriate hooks for inserting them. For example, a while ago I did some work to make the MessageQueue used for the mailbox overrideable (it has temporarily been overcome-by-events due to other changes). This is a small example, but it shows how extensibility requires a greater degree of forethought.

Extensibility also benefits substantially from simplicity. Scala Actors are almost impossible to extend from outside the scala.actors package because of their heavy reliance on package-private methods and state (mostly fixed here, but I broke remote actors in the process so no patch yet). Lift Actors, on the other hand, are very extensible, at least within the bounds of their design (purely event-based actors with no explicit lifecyle). Many of the flow control mechanisms could be implemented on top of the baseline approach.

At this point we see that extensibility has an interesting relationship with expressivity. I previously claimed that Scala Actors were more expressive because the wide variety of control structures they provide (and I didn't even touch on some of the DSL-like functionality that enables all sorts of interesting things). However, given Lift Actors far simpler and more extensible foundation, there is much more opportunity to create custom control structures as extensions to Lift Actors without modifying the core. Thus, if you are willing to do some lower-level programming, it could be argued that Lift Actors are in reality more expressive due to their extensibility.

Performance and Scalability

For purposes here, I'm going to treat performance as the rate a which an actor can receive and process messages at a relatively small, fixed number of simultaneous actors. This means that improving performance in largely a matter of reducing the time it takes from when a message is initially sent to when user-code within the actor begins processing the message, including minimizing any pause between when an actor finishes processing one message and is available to start processing the next. For moderate numbers of actors, performance is often maximized by having one thread per actor, and having the actor block while waiting for a message. Given enough actors, the memory requirements of using a thread for each actor will eventually cause more slowdown than cost of scheduling a new reaction for each message. This is illustrated in Philipp Haller's paper, "Actors that Unify Threads and Events" in the following graph:

Note that the above graph covers a microbenchmark running a simple, non-memory intensive task, and that the thread line is not a measurement of thread-bound actors, but rather of a simple threaded implementation. However, my own benchmarking has shown that receive-based (ones that block on a thread) compare to event-based actors in almost the same way as threads to event-based actors in the above graph. Also, remember that given a real application where heap space is needed for things besides the stacks of thousands of threads the point where the JVM throws an OutOfMemoryError will be much farther to the left. There are also more subtle issues. One of my first experiences with the Scala Actors library was creating a deadlock. I created more thread-bound actors than the scheduler wanted to create threads, and thus actors were stuck blocking on threads waiting for messages from an actor that hadn't started yet because there were no available threads. In other words, blocking can lead to situations such as deadlock, starvation, and simply extreme forms of unfairness with respect to how much CPU time is allocated each actor. These all go against highly desirable guarantees that a actor library should provide outside of extreme circumstances.

Ultimately event-based actors make the better model. For one, part of the reason why event-based Scala Actors are so expensive is that they suspend by throwing an exception to return control from user code to the library. While exceptions have been heavily optimized in the JVM, especially in recent versions, they are still substantially slower than normal return paths. Scala Actors need to use exceptions to suspend is a consequence of their expressivity. Basically, because the library as little or no knowledge of what an actor is doing within a reaction, it cannot rely on traditional returns without introducing special control structures (see reactWhile numbers in one of my previous blogs). Lift Actors, on the other hand, have do not need to use exceptions for control flow because the message processing cycle is essentially fixed - user code cannot intersperse weird (or even not-so-weird) patterns within it, or mix in blocking receives with event-based ones. Another potential optimization of event-based actors is to have them block if there are plenty of threads available, and then release it if the thread they are on is needed by the scheduler. To my knowledge this optimization is not implemented anywhere, but I think it would be relatively straight forward. The only problem is that the actor becomes more tightly bound to its scheduler.

Parting Thoughts

Ultimately, time and community willing, I'd like to evolve what is here, plus solid treatment of a lot of lower-level details, into a Scala Improvement Document (SID). There are a lot of subtle trades involved, and I think producing a general-purpose actors library is at least an order-of-magnitude more difficult than producing a special-purpose one. I also believe that if an actor implementation is part of the standard library, then it should provide the necessary extension points for when users need something special-purpose they can create it and still leverage components of the standard library and interoperate with other actors. In order words, I think it should define both the interface portion of an API along with providing a solid implementation. I don't think we'll even get their without a clear and common understanding of the various considerations involved.

I'm on Twitter!

2009-05-25T22:42:00.001-04:00

For those of you with ADD or it's internet induced equivalents, I've started posting on Twitter. I long avoided it because I feel like the last thing people need is yet another half-baked information stream, but then people seem to like it so I'm giving it a shot. I'll post links to bugs, patches, and other comments regarding my efforts (and those of others) with Scala actors...along with other less important matters. http://twitter.com/ErikEngbrecht

Refactoring Scala Actors: Progress Update

2009-05-25T22:32:00.002-04:00

It's been a while since I've posted, so I thought I'd give everyone a status update. This post covers several different semi-disjoint topics at a fairly high level. I plan on diving into some of the issues later this week and beyond, but for now...

State-machine Based Actors

A while back Philipp Haller, the original author and current maintainer of the Scala actors library, contacted and basically said he found the changes I was making really interesting, but he really needed a smaller, more gradual set of patches. It's a perfectly reasonable request, as I had pretty much completely ripped apart his library. I had rethought my approach, anyway, so I went about moving my state-machine based actor implementation into its own package and rewiring some of the pieces so that they could share common base traits, common infrastructure, and interoperate with one another as if they were the same library. So I shoved my code into scalax.actors, and started hacking insertion points for my code into the main library.

The first thing I thought I needed was a base trait that defines the basic structure and operations of an actor, so created a BaseActor in between AbstractActor and Actor (as well as my own StateActor):

trait BaseActor extends AbstractActor {
  def react(f: PartialFunction[Any, Unit]): Nothing
  def reactWithin(msec: Long)(f: PartialFunction[Any, Unit]): Nothing
  def receive[A](f: PartialFunction[Any, A]): A
  def receiveWithin[R](msec: Long)(f: PartialFunction[Any, R]): R
  /*def loop(body: => Unit): Nothing */
  /*def loopWhile(cond: => Boolean)(body: => Unit): Nothing */
  protected[actors] def mailbox: MessageQueue[Message[Any]]
  private[actors] final def mailboxForChannel: MessageQueue[Message[Any]] = mailbox
  def mailboxSize: Int
  def send(msg: Any, replyTo: OutputChannel[Any]): Unit
  def forward(msg: Any): Unit
  def reply(msg: Any): Unit
  /*protected[actors]*/ def sender: OutputChannel[Any]
  def ? : Any
  def start(): AbstractActor
  def freshReplyChannel: Channel[Any] = new Channel[Any](this)
  def scheduler: IScheduler //TODO: restrict access to scheduler??
}

I don't think BaseActor is going to be a permanent fixture because its contents probably belong in AbstractActor instead, but for now it serves its purpose. One of the first things you should notice is that way to much stuff in there is public. Most of it should be protected, or perhaps somewhere else entirely (like an InputChannel encapsulated by the actor).

Reworking MessageQueue

There's also the issue of the mailbox, which is a rather important and a den of mutable data that is passed all around with private[actors] qualifiers. Basically it separates the Message from the elements within the MessageQueue, so that the MessageQueue can keep its internal structure private, and thus facilitating making it a trait so that an actor can provide its own specialized implementation. I was about to submit a patch for the change, but a fix for a memory leak in FJTaskRunner came about that relied on clearing mutable fields in the message when a task is done processing. I have an alternative fix by changing pieces of FJTaskScheduler2, but schedulers in general and FJTaskScheduler2 in specific are in flux right now due to bugs (here and here and probably elsewhere), and I want to tweak the design a bit, so I'm holding off.

Fixing Schedulers

Which brings me to schedulers... Problems with plugging in custom schedulers (mostly fixed) are what originally caused me to dive into the guts of the actor library. Closely related to schedulers is ActorGC, which is absolutely essential to actors (almost) transparently abstracting threads, but can also be problematic due to it's fundamentally non-deterministic nature (it relies on the garbage collector for some of its more advanced capabilities). That being said, now in trunk ActorGC is optional, so environments that don't require an implicit shutdown of the actor worker threads can avoid the added complexity. I intend to cover the details of ActorGC very soon. There should also be a default scheduler with daemon semantics coming, which has a number of use cases.

Closing Matter

There's a lot more going on. Some recent flare-ups on Scala Internals mailing, despite being a tad melodramatic, brought a welcome focus on actors for the next release of Scala. The issue has also given rise to two minimalistic actor implementations, one in Lift and the other in Scalaz. They both make interesting data points for design and potential interoperability (remember: one of my primary goals is an actor implementation that lets you plug in what you need). There's issues around ActorProxy that I think will be a little hairy to sort out, but I'm confident they will be. And finally, there's the omnipresent issue of ensuring actor's really make the guarantees that they claim (right now I think they do, but I wouldn't place money on it until I have tests to prove it).

That's it for now. I'm going to try to take the time to blog about many of the above issues and more in depth in the coming weeks, and hopefully gain some insights from out in the cloud.

McKinsey and Cloud Computing

2009-04-21T22:39:00.002-04:00

McKinsey has created a tempest-in-a-teapot by denouncing the economics behind both in-the-cloud-cloud such as Amazon E2C and behind-the-firewall clouds for large enterprises. At a high level I think their analysis is actually pretty good, but the conclusions misleading due to a semantic twist. They use Amazon E2C as a model, and their conclusions go something like this:

Amazon E2C virtual CPU cycles are more expensive than real, in-house CPU cycles
You waste 90% of those in-house CPU cycles
You'll waste almost as many of those virtual cloud CPU cycles, only they cost more, so they are a bad deal
You stand a decent shot at saving some of those real CPU cycles through virtualization, so you should aggressively virtualize your datacenter
You're too inept to deliver a flexible cloud behind-the-firewall, so don't even try

I'll let you ponder which of the above statements is misleading while I address some related topics.

The goals of cloud computing are as old as computing itself. They are:

Reduce the time it takes to deploy a new application
Reduce the marginal cost of deploying a new application over "standard" methods
Reduce the marginal increase to recurring costs caused by deploying a new application over "standard" methods

Back in the days of yore, when programmers were real men, the solution to this was time sharing. Computers were expensive and therefore should be run at as a high of utilization as possible. While making people stand in line a wait to run their batch jobs was a pleasing ego trip for the data center operators, the machines still wasted CPU time while performing slow I/O operations and waiting in line generally made users unhappy. Thus time sharing was born, and in a quite real sense the first cloud computing environments, because in many cases a large institution would purchase and host the infrastructure and then lease it out of smaller institutions or individuals.

The problem here is that the marginal cost equations end up looking like a stair-step function. If you had a new application, and your enterprise / institution had excess mainframe capacity, then the marginal cost of letting you run your application was near zero. But if there was no spare capacity - meaning the mainframe was being efficiently utilized - then the marginal cost was high because either someone else had to be booted off or you needed an additional mainframe.

Now fast-forward a couple decades to the PC revolution. Somewhere along the way the cost curves for computers and people crossed, so it became appropriate to let the computer sit idle waiting for input from a user rather than having a user sit idle while waiting for a computer. Now you could have lots of computers with lots of applications running on each one (although initially it was one application at at time, but still, the computer could run any number of them). This smoothed out the non-recurring marginal cost curve, but as PCs proliferated it drove up recurring costs through sheer volume.

Unfortunately this had problems. Many applications didn't work well without centralized backends, and some users still needed more compute power than could be reasonably mustered on the desktop. So the new PCs were connected to mainframes, minicomputers, and eventually servers. Thus client-server computing was born, along with increasingly confusing IT economics. PCs were cheap, and constantly becoming cheaper, but backend hardware remained expensive. The marginal non-recurring cost becomes completely dependent on the nature of the application, and recurring costs simply begin to climb with no end in sight.

Now fast forward a little more. Microsoft releases a "server" operating system that runs on suped up PCs an convinces a whole bunch of bean counters that they can solve their remaining marginal non-recurring cost problems with Wintel servers that don't cost much more than PCs. Now more expensive servers. No more having to divide the cost of a single piece of hardware across several project. Now if you want to add an application you can just add an inexpensive new Wintel server. By this time the recurring cost equation had already become a jumbled mess, and the number of servers was still dwarfed by the PC on every desk, so there no tying back the ever increasing recurring costs. This problem was then further exacerbated by Linux giving the Unix holdouts access to the same cheap hardware.

Thus began the era of one or more physical servers per application, which is where we are today, with McKinsey's suggestion for addressing: virtualization behind the firewall. The problem with this suggestion is that, for a large enterprise, it isn't really that different from the cloud-in-the-cloud solution that they denounce as uneconomical. One way is outsourcing a virtualized infrastructure to Amazon or similar, and the other is outsourcing it to their existing IT provider (ok, not all large enterprises outsource their IT, but a whole lot do).

Virtualization, in the cloud or otherwise, isn't the solution because it doesn't address the root cause of the problem - proliferation of (virtual) servers and the various pieces of infrastructure software that run on them, such as web servers and databases. Hardware is cheap. Software is often expensive. System administrators are always expensive. Virtualization attacks the most minor portion of the equation.

Virtualization is the right concept applied to the wrong level of the application stack. Applications need to be protected from one another, but if they are built in anything resembling a reasonable way (that's a big caveat, because many aren't) then they don't need the full protections of running in a separate OS instance. There's even a long standing commercially viable market for such a thing: shared web hosting.

It may not be very enterprisey, but shared web site/application hosting can easily be had for about $5 per month. The cost quickly goes up as you add capabilities, but still - companies are making money by charging arbitrary people $5 per month to let them run arbitrary code on servers shared by countless other customers running arbitrary code. How many enterprise IT organizations can offer a similar service at even an order-of-magnitude greater cost?

Not many, if any. Yet do we see suggestions pointing out that Apache, IIS, Oracle, SQL Server, and countless other pieces of infrastructure can relatively easily be configured to let several applications share compute resources and expensive software licenses? Nope. They suggest you take your current mess, and virtualize it behind the firewall instead of virtualizing it outside the firewall.

Refactoring Scala Actors: Rethinking the Approach

2009-02-10T20:17:00.002-05:00

When I started refactoring Scala's actor library, I really had several goals:

Reduce the coupling within the library so that the implementation can be more easily extended and customized
Create a more transparent and "programmer friendly" actor implementation
Improve performance of various use cases
Make actors that interact better with their environment, particularly non-actor code
Maintain API compatibility with the existing library to the maximum extent practical

Thus far I've done my work by completely overhauling the Actor trait directly in the library. While I have plans for how this will reduce coupling, the haven't come to fruition yet. I think my state machine model is considerably more transparent and programmer friendly than the current implementation. The state an actor in is always clear, transition are reasonably well defined, and performing correct locking and unlocking is now pretty straight forward. I've substantially improved the performance of event-based actors for the common case where an actor loops while it receives messages until some termination criterion is reached. I haven't done anything with making them interact better with their environment yet, as I believe Philipp Haller is in the process of incorporating some changes for which I submitted patches several months back that will help considerably (he doesn't appear to be using the patches directly, but the changes I've seen are close enough).

A few days ago David MacIver asked me a couple interesting questions on IRC:

Have you considered using Kilim?
Have you looked at the continuations support that appears to be emerging as a compiler plugin?

Using Kilim would almost certainly disqualify the changes I'm making from incorporation into the standard library because of the external dependency on a prerelease framework that uses bytecode manipulation, and I don't think the fledgling continuation support is mature enough to experiment with yet (or maybe just not well documented enough yet, who knows...). That being said, both of these would be interesting avenues of development. Event based actors rely heavily on continuations, and the performance of those continuations has a substantial effect on the performance of the actors. Ultimately a properly decoupled implementation would allow someone to build an API compatible actor implementation on either of these technologies, or something else entirely.

I also received a recent nudge on the mailing list, when someone pointed out that it would be easier to experiment with my library if it was in it's own package. I somewhat disagree with that. It would be easier to experiment with it if you didn't have to do an entire build of the Scala distribution that has my code in it, and unfortunately for the foreseeable future I'm going to be depending on both code that is being committed into the trunk and on the ability to modify said code. Also, the way I have it setup today, if someone wanted to test their Scala application/library/framework against my state-based actors, they would just have to pull my Mercurial repository, build it, and rebuild against the resulting distribution. On the downside, it's a pain to do side-by-side comparisons between the two implementations, because you have to switch distributions and rebuild every time.

That being said, decoupling is one of my primary goals, and Martin & Company have already set the precedence of doing major work in a separate package with their efforts on redesigning the Scala collections library. So as soon as I finish up some of my immediate tasks and have a good build again (I'm in the middle of redesigning the control flow pattern to minimize the stack size when exceptions are thrown), I'm going to push most of the public and protected interface on Actor into a new trait that will be between Actor and AbstractActor as abstract methods, move my code out of scala.actors and into scalax.actors in my own directory. I definitely keep it within the same repository as the Scala distribution code, and will probably just make another directory for it. This means I'll have to mess with Sabbus to add my portion to the build, which won't be fun, but shouldn't be too hard. I'm sure there's going to be a lot more to do to extract it out, so I'll be adding items to my issues list as I think of them.

The end result should be my state based actors and the existing actors being able to live side-by-side and interact with one another in the same program. Assuming I can at least get some patches into the main library, it will also mean that the future of my work will not be dependent on being incorporated into the standard distribution. If it is, great, if not, I can distribute it separately. I would have done this from the start, but initially I was highly dependent on the existing code and infrastructure into order to get something working reasonably quickly, and to be able to smoke it out to see if it indeed worked. Back in December I was basically breaking partest with every change. But now things are reasonably stable, I rarely break partest, and I don't think it will take much for my code to be able to stand on its own.

So what does everyone think? Is this a good direction to head in?

Profiling the ExceptionBlob

2009-02-06T22:37:00.002-05:00

Last week on the Scala IRC channel (#scala) I chatted with several people about the need to substantially reduce the use of exceptions for flow control within the Scala Actors library. My remarks were met with a certain amount of healthy skepticism, as significant progress has been made on improving the performance of Java exceptions, as stated by John Rose in his blog Longjumps Considered Inexpensive.

I highly suggest you go read the post. I don't doubt anything stated in it, and in fact noticed a substantial performance improvement when I stopped benchmarking against Java 5 and started doing it against Java 6 (I usually work on a Mac, and Java 5 is the default VM), and expect even more improvements with Java 7. Once you're done, I'd like to call your attention to a couple fragments of it (additional emphasis mine):

The Hotspot JIT can optimize a throw of a preallocated exception into a simple goto, if the thrower and catcher are together in the same compilation unit (which happens because of inlining).

Here is a concrete example of non-local return, implemented efficiently via a cloned exception. I have observed the Hotspot server compiler emitting a machine-level goto for the throws. With current server VM optimizations of this code, the cost of a non-local return is less than three times the cost of a plain (local) return; with the client VM the ratio is ten. See the code example and benchmark for details: NonLocalExit.java (javadoc).

These statements have a couple implications:

Reducing a throw to a long jump requires a certain amount of HotSpot magic take place to ensure that the throw and catch are in the same compilation unit. The more complex the code is, the less likely this is to happen.
Long jumps are still substantially slower than normal returns

I think John's post received a lot of attention, and people (including myself) saw it, didn't read it carefully, and assumed that HotSpot now performed miracles with cached exceptions. What we missed was a post to the MLVM development mailing list about a year later by Charles Nutter, who had noticed that his non-local returns in JRuby where not being compiled down into long jumps, and subsequent response from John Rose. There's a lot of very good technical discussion in there, but I think the gist is that HotSpot's ability to optimize throws into long jumps is still limited, it often needs help to do so, and very smart people are working at improving it.

Of course that all still leaves the question: Just how much slower are cached exceptions than a normal return? I can't really answer that in the general case, but I did put together a couple mircobenchmarks in Java that somewhat simulate the type of stack creation that happens within my state-based actors. The benchmark is pretty simple. It recursively descends down, incrementing a member variable, and then on the way back up it decrements another member variable. In the case of the exception-based return, it does the decrements within a finally block. This admittedly is rather pathological code, but it is also simple and easy to understand.

Here's the normal return version:

public class NormalReturn {
    public static void main(String[] args) {
        NormalReturn m = new NormalReturn();
        m.doTest(10000000);
    }
    public void doTest(int times) {
        for(int i = 0; i < times; i++) {
            down = 0;
            up = 0;
            deepRecurse(1000);
        }
        System.out.println(down);
        System.out.println(up);
    }
    private int down = 0;
    private int up = 0;
    public void deepRecurse(int i) {
        down++;
        if (down <= i) {
            deepRecurse(i);
            up--;
        }
    }
}

...and here's the version that uses a cached exception:

public class TryFinally {
    private static class Signal extends RuntimeException {
        @Override
        public Signal fillInStackTrace() { return this; }
    }
    private Signal signal = new Signal();
    public static void main(String[] args) {
        TryFinally m = new TryFinally();
        m.doTest(10000000);
    }
    public void doTest(int times) {
        for(int i = 0; i < times; i++) {
            try {
                down = 0;
                up = 0;
                deepRecurse(1000);
            } catch (Signal s) {
                // do nothing
            }
        }
        System.out.println(down);
        System.out.println(up);
    }
    private int down = 0;
    private int up = 0;
    public void deepRecurse(int i) {
        try {
            down++;
            if (down == i) throw signal;
            else deepRecurse(i);
        } finally {
            up--;
        }
    }
}

With profiling turned off on and -server on Java 6 on my Mac, the normal return version takes about 60 seconds to complete, while the TryFinally version takes over 10 minutes. That's certainly much better than the 30x figure John Rose cited for the client VM, but it's still an order-of-magnitude worse than a normal return. One interesting thing about the benchmark is that if you decrease the recursion depth and increase the number of times deepRecurse() is executed the total time stays relatively constant.

So with this in mind, I'm going to work hard to refactor the actors library to keep exception usage to a minimum, an where it must be used to minimize the depth of the stack.

Scala Actors versus the ExceptionBlob

2009-02-06T18:03:00.003-05:00

I've begun some very preliminary benchmarking of my state-based actors library against the current standard actors library and seen some rather interesting results. The test I'm running spawns four pairs of actors and sends about 40 million messages between each pair. The only logic in the actors is to count how many messages they have received, ensure they are received in order, and occasionally send back a "More" message. This is so the mailbox doesn't overfill and cause out-of-memory errors.

The benchmark has three different incarnations, each testing a different way of processing messages until some termination condition occurs. The versions are:

loop
recursive react
reactWhile (only available with the State-based actors, but relatively easy to port to "classic" actors)

The code for the loop version is below:

class LoopPingSender(val totalPings: Int, val pingReceiver: LoopPingReceiver) extends Actor {
  private var pingsSent = 0
  def act() {
    Actor.loop {
      pingReceiver ! Ping(pingsSent)
      pingsSent += 1
      if (pingsSent == totalPings) {
        println("Sender Done")
        exit("sender completed successfully")
      } else if ((pingsSent % 1000) == 0) react {
        case More => 
      }
    }
  }
}
class LoopPingReceiver(val totalPings: Int) extends Actor {
  private var pingsReceived = 0
  def act() {
    Actor.loop {
      react {
        case Ping(n) if n == pingsReceived => {
          pingsReceived += 1
          if (pingsReceived == totalPings) {
            println("Receiver Done")
            exit("receiver completed successfully")
          } else if ((pingsReceived % 1000) == 0) {
            reply(More)
          }
        }
        case Ping(n) => {
          println("error")
          exit("invalid n value: " + n)
        }
      }
    }
  }
}

The non-scientifically gathered results are as follows, all times in seconds:

Version	Standard Actors	State-based Actors
loop	298.22	96.84
Recursive react	90.25	113.57
reactWhile	N/A	40.63

Standard Actor `loop`

Let's consider the loop version first. loop in the standard actor implementation is rather convoluted. Rather than directly supporting looping, the standard actor implementation provides a package private hook for a function that is executed when the actor is terminating. loop uses this hook to subvert the termination process by throwing an exception and subsequently restarting execution of the actor. This makes it so that two exceptions are thrown per message processed rather than the normal one. Here's a small snippet from the profiling results:

     Compiled + native   Method                        
 40.0%  5148  +     0    ExceptionBlob
 13.9%   658  +  1133    scala.actors.Scheduler$$anon$2.run
 13.1%   391  +  1299    scala.actors.Actor$.loop
  3.4%   441  +     0    scala.actors.FJTaskRunner.run
--- snip ---
 73.7%  6705  +  2771    Total compiled

         Stub + native   Method                        
 20.6%     0  +  2654    java.lang.Thread.isInterrupted

What you can see is that the ExceptionBlob is dominating the runtime, followed by Thread.isInterrupted. ExceptionBlob is a class in the JVM that observes the unwinding of the stack. As far as I could discern through so separate microbenchmarking (which I'll discuss another day, after I've spent some time in HotSpot code), the amount of time consumed by ExceptionBlob is proportionate depth of the stack being unwound by exceptions. In other words, throwing fewer exceptions doesn't do any good if you use them to unwind deeper stacks, and unwinding shallower stacks doesn't do any good if you throw more exceptions. Caching exceptions doesn't help, either, but I digress. The bottom line is that loop is pretty inefficient in the standard actors implementation.

State-based Actor `loop`

In my state-based actors, there are two states to handle looping, both of which are subclasses of Running. The first is Looping, which is initially entered when the actor starts looping. The second is ResumeLooping, which is used to resume looping after the actor has been suspended. Both run the body of the react in a tail-recursive loop until their are no more messages to process, at which time they suspend the actor. This means that many message can potentially be processed before any exception-based signaling is used. The following is a snippet from a profile:

     Compiled + native   Method                        
 67.5%  3233  +     0    ExceptionBlob
  6.4%   306  +     0    scala.actors.Actor$class.withLock
  4.9%    44  +   189    actorbench.LoopPingSender$$anonfun$act$1.apply
  4.8%    97  +   135    scala.actors.Actor$$anonfun$send$1.apply
  4.5%   116  +    99    scala.actors.Actor$Running.tr$1
  3.8%    36  +   145    scala.actors.Actor$ResumeLooping.enter
--- snip ---
         Stub + native   Method                        
  0.2%     0  +     9    java.lang.Thread.isInterrupted

Again, ExceptionBlob dominates the execution time, although the total time it consumes is lower. Unfortunately, despite using significantly fewer exception signals, my state-based actors tend to build up significantly deeper stacks than the actors in the standard library.

Standard Actor recursive `react`

Recursive react seems to be the best performing looping pattern for the standard actor library. It's a pretty simple pattern:

class PingSender(val totalPings: Int, val pingReceiver: PingReceiver) extends Actor {
  def act() {
    def recurse(i: Int): Unit = {
      if (i > 0) {
        pingReceiver ! Ping(i)
        if ((i % 1000) == 0) {
          react {
            case More => recurse(i - 1)
          }
        } else {
          recurse(i - 1)
        }
      } else {
        println("Sender Done")
      }
    }
    recurse(totalPings)
  }
}

As you can see, the function containing the react block is simply recursively called as needed. Note that despite the fact that the recursive call appears to be in a tail position, it is not a tail recursive call and will not be optimized by the compiler. The PartialFunction defined within the react block is actually a separate object with an apply method, so while recurse and the PartialFunction are mutually recursive, they are not tail recursive.

     Compiled + native   Method                        
 19.1%   456  +     0    ExceptionBlob
 13.0%    89  +   221    scala.actors.Reaction.run
  8.6%    53  +   152    scala.actors.Actor$class.send
  7.9%    61  +   127    scala.actors.Actor$class.react
  5.3%    59  +    67    scala.Iterator$class.toList
--- snip ---
 68.1%   862  +   765    Total compiled

         Stub + native   Method                        
 26.4%     0  +   631    java.lang.Thread.isInterrupted
--- snip ---
 26.9%     0  +   643    Total stub

This time Thread.isInterrupted dominates, with ExceptionBlob not too far behind.

Actor States recursive `react`

It turns out that the "hybrid trampoline" I implemented to facilitate recursive reacts without giving up the thread provides pretty bad performance.

 64.9%  3714  +     0    ExceptionBlob
 11.4%   568  +    85    scala.actors.Actor$class.withoutLock
  8.4%   478  +     1    scala.actors.Actor$class.withLock
  5.1%    90  +   201    scala.actors.Actor$$anonfun$reactWithin$1.apply
  4.2%   115  +   125    scala.actors.Actor$$anonfun$send$1.apply
--- snip ---
 97.8%  5006  +   595    Total compiled
         Stub + native   Method                        
  0.1%     0  +     6    java.lang.Thread.currentThread
--- snip ---
  0.2%     0  +    12    Total stub

The problem is that when I wrote it, I thought that the cost of throwing exceptions was primarily proportionate to the number of exceptions thrown rather than the amount of stack that is unwound. Consequently, I made the trampoline only bounce once every n invocations in order to reduce the number of exceptions being thrown. As it turns out, what I should do is find a place where the stack is likely to be the shallowest, and throw an exception every time.

Actor States `reactWhile`

reactWhile addresses the pitfalls presented in the previous versions and provides roughly twice the performance of next best performer, recursive react on the standard actor library.

     Compiled + native   Method                        
 30.0%   171  +   331    scala.actors.Actor$Running.tr$1
 24.4%   263  +   146    actorbench.ReactWhileReceiver.withLock
 12.4%    26  +   181    actorbench.ReactWhileSender.sendPings
  8.5%   142  +     0    scala.actors.Actor$class.withoutLock
--- snip ---
 79.0%   660  +   661    Total compiled

         Stub + native   Method                        
 15.1%     0  +   252    java.lang.Thread.isInterrupted
  0.9%     0  +    15    java.lang.Thread.currentThread
 16.0%     0  +   267    Total stub

ExceptionBlob has completely disappeared from the profile. That is because reactWhile makes minimal use of exceptions for signaling. Consequently, its performance is dominated by some of the complicated for my (worthless) hybrid trampoline, my completely unoptimized lock implementation, and calls to Thread.isInterrupted that are made when the bound thread is returned to the pool when the actor suspends. I'll write a blog on how reactWhile works at a later date, after I cleanup some of the other problems that I've listed.

Parting Matter

It really annoys me when people post benchmark results without providing details of their setup along with all of the code required to duplicate them, and that's just what I've done. I've also benchmarked a very narrow set of behavior, failed for warm up the JVM, and not run multiple trials. Developing a lightweight framework for benchmarking actor performance, along with a more comprehensive set of benchmarks is on my to-do list. Once I have that, I'll start doing more rigorous benchmarking. But I don't think I quite need it yet because bottlenecks are showing up quickly and consistently in my profiling, and in most cases they seem to have reasonably straight forward solutions. All the above profiles against my library were done against revision 49658b3475e2 in my bitbucket repository, so you can at least access that code.

Google is Paranoid

2009-01-31T10:16:00.005-05:00

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?

Refactoring Scala Actors

2009-01-24T15:52:00.002-05:00

I'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 message
shouldExit - used to signal that the actor should exit instead of doing normal processing
isSuspended - seems to indicate that the actor is waiting while blocked on a thread
isDetached - the actor is waiting and is not attached to a thread
isWaiting - the actor is waiting in some way
mailbox - queue of messages for the actor
sessions - list used as a stack to keep track of the sender of messages while they are being processed
received - the message that was received, used to pass around a received message, could be replaced with local variable within functions
exitReason - 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 period
kill - 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 reactions
trapExit - 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 message
rc - a reply channel - unclear why it is actually needed because it is never used other than to be set in freshReplyChannel on every invokation
links - a list of linked actors. Linked actors are notified or shutdown when the actor that they are linked to shuts down
continuation - the function to be executed when the actor resumes

All 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 actor
Active States
- StartScheduled - the actor has been started but has not yet been attached a thread or started executing its body
- Running States - states where the actor is bound to a thread and is executing its body
  - Running - the actor is bound to a thread and is executing its body
  - Looping - a special case of running where the body is repeated while a specified condition holds
  - Killing - 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.
- Wait States
  - 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.
Terminal States
- Finished - the actor teriminated normally
- Killed - the actor was killed before it could complete execution
- UnhandledThrowable - an exception was thrown, usually from "user code," and not handled
- InternalError - an error occurred within the actor library

...and now there are the following instance variables:

state - the state of the actor
mailbox queue of messages for the actor
sessions list used as a stack to keep track of the sender of messages while they are being processed
trapExit - 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 message
links - 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.

Countdown to the U.S.S.R.

2008-11-05T07:08:00.003-05:00

Normally 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.

Languages Readability and Tool Support

2008-08-04T22:29:00.004-04:00

I 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.

The Costs of Generality

2008-08-03T20:24:00.002-04:00

I'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.

The General Solution

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.

Generate Only Valid Permutations

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.

Accumulating Numbers Instead of Lists

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)
  }

Long Set without Boxing

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.

Special Purpose Set for Permutation Generation

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)
  }

Conclusion

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.

System.identityHashCode

2008-07-15T22:06:00.002-04:00

A recent thread on the the Scala IRC channel piqued my curiosity about exactly how System.identityHashcode works. It looks like as less heated remarks have flushed out the conversation more the definition was irrelevant, but regardless, I think it's interesting. Thankfully Sun open-sourced the their implementation of the Java platform so it was pretty easy to find out exactly how it works.

It turns out the Sun JVM contains three different algorithms for calculating the identity hash, none of which are guaranteed to yield unique hash codes. That's not surprising, because on a 64 bit architecture, doing that would be almost impossible. I say almost because one could just generate them as sequential numbers, and then crash the JVM when it runs out of 32 bit hash codes (an OutOfHashCodesError ;-).

From share/vm/runtime/synchronizer.cpp:

static inline intptr_t get_next_hash(Thread * Self, oop obj) {
  intptr_t value = 0 ; 
  if (hashCode == 0) { 
     // This form uses an unguarded global Park-Miller RNG, 
     // so it's possible for two threads to race and generate the same RNG.
     // On MP system we'll have lots of RW access to a global, so the
     // mechanism induces lots of coherency traffic.  
     value = os::random() ; 
  } else
  if (hashCode == 1) { 
     // This variation has the property of being stable (idempotent)
     // between STW operations.  This can be useful in some of the 1-0
     // synchronization schemes.  
     intptr_t addrBits = intptr_t(obj) >> 3 ; 
     value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ; 
  } else 
  if (hashCode == 2) { 
     value = 1 ;            // for sensitivity testing
  } else { 
     // Marsaglia's xor-shift scheme with thread-specific state
     // This is probably the best overall implementation -- we'll
     // likely make this the default in future releases.
     unsigned t = Self->_hashStateX ; 
     t ^= (t << 11) ; 
     Self->_hashStateX = Self->_hashStateY ; 
     Self->_hashStateY = Self->_hashStateZ ; 
     Self->_hashStateZ = Self->_hashStateW ; 
     unsigned v = Self->_hashStateW ; 
     v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ; 
     Self->_hashStateW = v ; 
     value = v ; 
  } 

  value &= markOopDesc::hash_mask;
  if (value == 0) value = 0xBAD ; 
  assert (value != markOopDesc::no_hash, "invariant") ; 
  TEVENT (hashCode: GENERATE) ;
  return value;
}

What's interesting is that there's an algorithm in there (hashCode == 2) where the identity hash code turns out to always be the same all objects. I'm pretty sure it's there solely for testing purposes, so they can run tests against the JVM and standard library and ensure no piece of code is relying on the uniqueness of the identity hash code.

This relates back to my previous point about transparency. Because Sun's JVM is open source, it's possible for anyone to peek inside and see how the various bits work, and what assumptions the Sun JVM engineers are and are not making about those pieces.

Trust in Authority vs Trust in Transparency

2008-07-15T07:19:00.001-04:00

This morning Murph posted a blog on the "censorship" of Wikipedia by over-zealous article owners, citing a posting by Lawrence Solomon about an experience with editing an article related to global warming. Murph uses this to support one of his common conspiracy theories that Wikipedia, and social media in general, is doomed because of this kind of censorship and deliberate distortion of the facts.

What's interesting is that this censorship took place in the open. Anyone who knows where to look can see exactly what changes were made by Solomon, and their disposition relative to the current official article or any other version of it. Here's Solomon's version versus the current version.

The core issue here isn't censorship. Editors will always censor. Their job is to act as filters. Furthermore, every editor is subject to biases, whether they be his own or those imposed on him by a third party such as his employer. With most publications the editorial process happens behind closed doors with unseen forces. With Wikipedia the process happens right before the eyes of the world.

The real issue here is that Murph trusts authority more than transparency. Someone corrected an article, and the correction was subsequently removed due to political bias. I'm sure that's happened time and time again in every encyclopedia that has ever been published. The difference is in this case the change was transparent, with the politics open for all to judge, where with a traditional model we would have never known.

If history has taught us anything, it's that placing too much faith in authority is a bad idea. Our authority figures are all human, and our authoritative organizations are still organizations of people. They are both fallible and corruptable. We can't entirely strip authority from our society because that would lead to anarchy, but we can make authority more transparent, and with transparency we can judge for ourselves.

In this particular case the editorial process of Wikipedia probably failed to yield the most accurate article possible, at least as the article stands today. I'm not an expert on the subject matter, but I think Solomon's corrections were most likely correct. That being said, I think the process has succeeded. The changes Solomon made have not be entirely censored, they have merely been driven from the main page. Discourse continues with regards to their validity. The biases of the editors have been made public. The last thing we want to do is reseal that process behind closed doors, simply because in this case we didn't like some of the results.

Love, Hate, and Type Inference

2008-07-13T13:49:00.006-04:00

Ever since I started using Scala, I've had somewhat of a love-hate relationship with type inference. On the local level, type inference can make code much more concise, easier to read, and easier to refactor. It makes code easier to read because in cases where the type of variable is obvious, type annotations just add noise that distract from the meaning of the code. It makes code easier to refactor, because often times changes to the type of something in one place in a program can ripple throughout the rest of the program through a simple recompile, assuming the new type supports the methods being used on the original type. This leads to something akin to structural typing without the associated overhead.

However, at a more macro level I think type inference can make code much more difficult to read. For example, consider the following code from the Scalax library (full source here):

//  Scalax - The Scala Community Library
//  Copyright (c) 2005-8 The Scalax Project. All rights reserved
abstract class InputStreamResource[+I <: InputStream] extends CloseableResource[I] {
    def buffered : InputStreamResource[BufferedInputStream] =
        new InputStreamResource[BufferedInputStream] with Wrapper {
            type Handle = BufferedInputStream
            override def wrap(is : SelfHandle) = new BufferedInputStream(is)
            
            override def buffered = this
        }

    def slurp() = for (is <- this) yield StreamHelp.slurp(is)
    
    /* Obtains a Reader using the system default charset. */
    def reader =
        new ReaderResource[Reader] with Wrapper {
            type Handle = Reader
            // XXX: should be UTF-8 by default instead of OS default
            // practically, here in Russia I never used default charset
            override def wrap(is : SelfHandle) = new InputStreamReader(is)
        }
    
    def gunzip =
        new InputStreamResource[GZIPInputStream] with Wrapper {
            type Handle = GZIPInputStream
            override def wrap(is : SelfHandle) = new GZIPInputStream(is)
        }
    
    /** Obtains a Reader using the supplied charset. */
    def reader(charset : String) = {
        // Do this lookup before opening the file, since it might fail.
        val cs = Charset.forName(charset)
        new ReaderResource[Reader] with Wrapper {
            type Handle = Reader
            override def wrap(is : SelfHandle) = new InputStreamReader(is, cs)
        }
    }
    
    def lines = reader.lines
    
    def lines(charset : String) = reader(charset).lines
    
    def readLines() = reader.readLines()
    
    def readLine() = reader.readLine()
    
    def pumpTo[O <: OutputStream](osr : OutputStreamResource[O]) {
        // Note InputStream should be opened before OutputStream
        for (is <- this; os <- osr) StreamHelp.pump(is, os)
    }
}

This is an example of where type inference makes code easier to refactor yet more difficult to read. If one were to change the return type of the reader methods, or the subsequent lines and/or readLines methods on that type, then the return types of these methods would automatically change on recompile. However, now try to figure out the return types of the lines and readLines methods. In order to do that, you need to know what the return type of the reader method is, and the structure of that type. Figuring out the return type of reader is reasonably straight forward, as it is defined in the same. However, the base class for the return type is not, so in order to figure it out you need to trace through several class definitions and potentially in other source files. I doubt this is a big deal for those people who are intimately familiar with the code, but I pity the new guy who has to sort it out when he's trying to create a new subclass of this abstract class. Of course, there's always the API docs, so users of the code, and the poor new guy, do have a place to turn.

So that's Scala, which supports a relatively limited form of type inference. Now, let's consider a snippet of OCaml, which has much fuller type inference, that I stole from Mauricio Fernandez:

   (* Copyright (C) 2008 Mauricio Fernandez  http//eigenclass.org
      Solution to the coding challenge at
      http://beust.com/weblog/archives/000491.html *)
   open Printf
   module S = Set.Make(struct type t = int let compare = (-) end)
   let (--) set elm = S.remove elm set
  
   let permutations f zero digits len =
     let base = S.cardinal digits in
     let rec aux n digits = function
         0 -> f n
       | len -> S.iter (fun s -> aux (n * base + s) (digits -- s) (len-1)) digits
     in S.iter (fun s -> aux s (digits -- s) (len - 1)) (digits -- zero)
 
   let () =
     let max = 10_000_000_000 in
     let digits = List.fold_right S.add [0; 1; 2; 3; 4; 5; 6; 7; 8; 9] S.empty in
  
     let count = ref 0 and prev = ref 0 and maxj = ref 0 and base = ref 0 in
     let report () = printf "Found %d numbers under %d.\n" !count max;
                     printf "Max jump: %d (%d -- %d).\n" !maxj !base (!base + !maxj)
   
     in try
       for i = 1 to 10 do
         permutations
           (fun num ->
              if num >= max then raise Exit;
              (* printf "%d\n" num; *)
              incr count;
              let jump = num - !prev in
                if jump > !maxj then (maxj := jump; base := !prev);
                prev := num)
           0 digits i
       done;
       report ()
     with Exit -> report ()

It's not entirely fair that I am picking on this OCaml code, because I don't know the language. Also, this is a short, self-contained program that I personally would be likely to write in Python without any type annotations at all. So in a way, for short programs like this, I think full type inference is great. You get all of the protection of static typing with none of the hassle. That being said, I think it would be extremely difficult to approach a large code base that is this devoid of type annotations.

All this adds up to my love-hate relationship with type inference. I love it when I'm writing my own code, and I hate it (aside from local variables) when I am reading other people's code. Over the past months I've decreased my use of it in Scala, preferring instead to explicitly specify types wherever they would not be entirely obvious from looking at the code, even though all my Scala code is hobby-work so no one else has to read it. Of course, being hobby work, I often go days, weeks, or even months without looking at a chunk of code, so I often need help remembering what I wrote. Overall I would say that excessive reliance on type inference obfuscates code, and that there are plenty ways for programmers to obfuscate their code, so it is a style issue as opposed to a language design issue. I also think it will be interesting to see how many dynamic language people migrate over to languages with strong type inference as these languages gain more attention. As you can see from the OCaml code above, there is no extra "typing burden" placed on the programmer. If the program is correctly typed, it will compile and run quickly. If not, it won't. In theory this should satisfy the "type annotations are too much work/add too much noise to my program" camp, but not the "I don't want the compiler telling me what I can and can't do" camp. My guess is that more people fall into the latter than the former, even the ones that claim they don't, but only time will tell.

Update: I just had a thought. Try thinking of type inference like using pronouns in natural languages. Imagine talking to a person who rarely uses pronouns. It's slow, cumbersome, and occasionally makes you think the speaker thinks you are an idiot who can't remember what he said 30 seconds ago. Likewise, when someone speaks entirely in pronouns, especially when they use a pronoun to refer to something that isn't part of the immediate conversation, it leads to utter confusion. Context is key, and the compiler can usually keep a much more distant context in its working memory than a programmer can. Type annotations provide context. Type inference assumes context.

Update 2: Here's a link to some OCaml API docs, where, just like in Scala, you can clearly see the inferred types.

Cedric's Code Challenge

2008-06-28T21:17:00.003-04:00

Cedric Buest issued a interesting little challenge this morning:

Here is an interesting coding challenge: write a counter function that counts from 1 to max but only returns numbers whose digits don't repeat.

For example, part of the output would be:

8, 9, 10, 12 (11 is not valid)

98, 102, 103 (99, 100 and 101 are not valid)

5432, 5436, 5437 (5433, 5434 and 5435 are not valid)

Also:

Display the biggest jump (in the sequences above, it's 4: 98 -> 102)

Display the total count of numbers

Give these two values for max=10000

He welcomed brute-force solutions, but really the challenge here is in coming up with something more efficient and elegant. There are basically three general approaches:

Run through all the numbers from 0 to n, test each for no repeating digits, and track the above statistics while you do it. This is the brute force method.
Permute the digits in a fashion that generates numbers sequentially and track the statistics. Alternatively you could generate them in any order, sort them, and then calculate the statistics.
Derive a heuristic that proves a given sequence of numbers will all contain repeated digits and can therefore be skipped.

I think #2 is probably the ideal fashion, but I didn't think of it until I was mostly done coding #3.

Finding Repeated Digits

The first step in solving this problem, no matter what the approach, is to come up with an algorithm to detect repeated digits. Commenters on Cedric's blog came up with a number of ways to do this, most of which centered around converting the integer into a string and then finding repeated characters. This is a rather frighteningly inefficient approach. There is certainly no need to convert the number into a string in order to know its digits. A much simpler approach is allocate a ten element array of booleans initialized to false, and start generate the digits from lowest to highest by moding the number by ten. The first time you encounter a digit, you flip it's associated array element to true. The second time, you exit because you have detected a repeat. The array is essentially serving as a thrifty man's map. Here it is in Scala:

  def containsRepeatedDigit(i: Long): Boolean = {
    val digits = new Array[Boolean](10) // elements default to false
    def f(i: Long): Boolean = {
      if (i == 0L) false // all digits have been processed
      else {
        val d = (i % 10L).asInstanceOf[Int]
        if (digits(d)) true
        else {
          digits(d) = true
          f(i / 10L)
        }
      }
    }
    if (i < 11L) false else f(i)
  }

The Heuristic

Consider the number 2201. It has repeating digits. The question is: What's the next number without repeating digits? It is 2301. You could calculate it using brute-force, but you'd end up scanning an extra 99 numbers. Notice that the repetition is in the upper digits. This means that you will cannot get a number with non-repeating digits until the second digit (counting from the left) changes. Now consider the number 2200. In this case changes need to occur in both the lower digits and the upper digits, however addressing the upper digits allows us to skip a much larger section of the search space. Finally, consider 22200. In this case, you still want the second digit. However, you are searching from the right, so algorithms what detect the first repeat won't work. Here's Scala code to find the appropriate digit. Notice that it looks very similar to the repeated digit test above.

  def max(array: Array[Int]): Int = {
    def f(idx: Int, m: Int): Int = {
      if (idx == array.length) m
      else if (array(idx) > m) f(idx + 1, array(idx))
      else f(idx + 1, m)
    }
    f(1, array(0))
  }

  def repeatedDigit(i: Long): Int = {
    val prevIdx = new Array[Int](10)
    val recentIdx = new Array[Int](10)
    def f(i: Long, idx: Int) {
      if (i > 0) {
        val d = (i % 10L).asInstanceOf[Int]
        if (recentIdx(d) > 0) prevIdx(d) = recentIdx(d)
        recentIdx(d) = idx
        f(i / 10L, idx + 1)
      }
    }
    f(i, 1)
    Math.max(max(prevIdx), 0)
  }

Now that we have an algorithm for finding the highest digit that needs to be changed, we need one that will take that information and turn it into the next possible number containing no repeating digits. This simply requires basic arithmetic.

  def nextPossibleNonRepeating(i: Long): Long = 
        nextPossibleNonRepeating(i, repeatedDigit(i))

  def nextPossibleNonRepeating(i: Long, idx: Int): Long = {
    if (idx == 0) i + 1L
    else {
      val p = Math.pow(10.0, (idx - 1).asInstanceOf[Double]).asInstanceOf[Long]
      val r = i % p
      val d = p - r
      i + d
    }
  }

Given this, it is easy to generate a sequence:

  def nextNonRepeating(i: Long): Long = nextNonRepeating(i, repeatedDigit(i))
  def nextNonRepeating(i: Long, idx: Int): Long = {
    val p = nextPossibleNonRepeating(i, idx)
    val d = repeatedDigit(p)
    if (d == 0) p else nextNonRepeating(p, d)
  }

Solution

Once this is all done, the solution is pretty straight-forward. It takes the general form of the function use to generate the next number with non-repeating digits, only it has to keep track of a bunch of extra information.

  def printNonRepeatingReport(start: Long, stop: Long, last: Long, gapLow: Long,
                              gapHigh: Long, cnt: Long): Unit = {
    if (start > stop) {
      println("max: " + last)
      println("max gap: " + (gapHigh - gapLow) + " between " + 
              gapLow + " and " + gapHigh)
      println("count: " + cnt)
    } else {
      val d = repeatedDigit(start)
      if (d == 0L) {
        //println(start)
        val gap = start - last
        val (gl, gh) = if (gap > (gapHigh - gapLow)) (last, start) 
                       else (gapLow, gapHigh)
        printNonRepeatingReport(start + 1L, stop, start, gl, gh, cnt + 1L)
      } else {
        printNonRepeatingReport(nextPossibleNonRepeating(start, d), stop, last, 
                                gapLow, gapHigh, cnt)
      }
    }
  }

Results

I'm not going to list all the numbers here, just the statistics for 1-10,000:

max: 9,876
max gap: 105 between 1,098 and 1,203
count: 5,274

Of course I haven't checked it against a brute-force solution or other posted solution, so I owe a beer/coffee/tea, depending on your persuasion, to anyone who can point out a bug and provide the solution.

Just for kicks, here's to 10,000,000,000:

max: 9,876,543,210
max gap: 104,691,357 between 1,098,765,432 and 1,203,456,789
count: 8,877,690

Which took 1 minute 23 seconds on my MacBook. Try that with a brute-force approach.

Google AppEngine

2008-06-23T19:54:00.002-04:00

There's a lot of buzz out there about how Google AppEngine is a game changer. My question is: Which game? AppEngine reduces the cost of hosting a web application down to zero. Zero is a pretty profound number. You don't even need to provide a credit card number in case they might want to charge you some day. All you need to a mobile phone number capable of receiving text messages. This means that not only is there no up-front cost, but also that there is no risk that you will suddenly incur huge fees for exceeding transfer quotas when you are lucky enough to be Slashdotted . Your application will just be temporarily unavailable. Hey, if that service level is good enough for Twitter , it's good enough for you, right?

The Open Source Game

Starting an open source project has been free for years. Many project hosting communities exist, providing projects with source code management, issue tracking, wikis, mailing lists, other features, and even a little visibility within their directories. Web hosting is not exactly expensive, especially light-weight scripting languages like PHP , Perl , and Python ; but it still costs something and therefore requires a sponsor. Often times for a fledgling project the sponsor is also the founder, who also happens to be the lead programmer, help desk, and promoter. There are some who do an amazing job of doing this , but for the most part I think project founders choose to wait.

Note: If I am wrong about the availability of good, free hosting for open source web applications, please provide links to them in the comments section. I would love to be proven wrong on this.

The Startup Game

If Paul Graham were to comment on AppEngine, it probably be that it eliminates one of the last remaining excuses anyone may have to launching a web startup. If you have an idea, some time, and can hack Python – you can launch a web application with AppEngine. You don't need money, infrastructure, long-term commitment, or any of those other things that may scare a person away from a startup. With AdSense, you even monetize your application without hardly any effort.

Of course there are limitations. For one thing, AppEngine is very limited in what it can do. Pretty much any idea with even moderate bandwidth, storage, or computation requirements that cannot be delegated to another web application (e.g. embedding YouTube functionality) is out. So, unless you plan on building a business based on mashing together existing applications, then AppEngine probably is not your free lunch. That being said, I fully expect that Google will gradually add APIs for all of its applications to AppEngine, thereby providing a very powerful base for new-but-thin ideas.

The R&D Game

Just for a moment, let's say there was a company that required all of its employees to spend 20% of their time working on a project other than their primary job. This is a company that is betting that it cannot predict which idea is going to be the next big thing, so it must try lots and lots of things and see what sticks. As this company grows, providing infrastructure for those projects would become a real challenge. Especially providing infrastructure that allows them to be testing in the wild as opposed to simply internally, and allows the projects to instantly scale if they just happen to turn out to be a success. This company would also want to ensure their employees weren't slowed down by having to deal with muck . Such a company would need an infrastructure that could scale to support many, many applications without burdening infrastructure teams. Such a company would need AppEngine.

Now extend the idea further. Let's say it doesn't really matter whether the next big thing was developed by an employee or not. What matters is that the next big idea is bound to the company, for example by using the company standard authentication mechanism or, more importantly, the company standard monetization mechanism.

Ok, so we all know what company I'm talking about. AppEngine allows Google to outsource some of their R&D at very low cost, and given that most successful AppEngine developers will probably choose AdSense to monetize their creations, Google stands to profit regardless of whether they ever pay any fees or not. In cases where creators do pay hosting fees, the great Google gets paid twice.

The Recruitment Game

Distinguishing among potential recruits is very challenging. The accomplished academic is almost certainly smart, may fall apart when asked to work with a significant team on something important to the company rather than a research interest. The industry veteran may have great corporate experience, but political skills could be masking shallow or outdated technical skills. The bottom line is recruiting is hard because in most cases you never see a direct sampling of an individual's work. At best you can see what a team he was on produced and take at educated guess as to his contribution. Open source projects can provide more information, but for most programmers there is no real motivation to participate in such projects.

AppEngine provides more motivation to the programmer, because he can more readily show his creation to other people without incurring any cost and there is always a chance that he will make some money. There are probably a lot of talented “almost founders” out there who would start a company, but perhaps lack some of the personality traits necessary to do so or found themselves in a situation where they need a steady income stream that simply isn't available for the founder of an early-stage startup. These individuals, and others, will make great pickings for Google.

Conclusion

Long term, in order for Google to grow, it has to attract more people to spend more time on sites displaying AdSense advertisements. Over the past few years Google has come out with countless new online services, most of which on still in beta, and none of which has yielded anything close to the monetization potential of their search business. AppEngine allows them to vicariously service the long tail without continuously expanding their already highly diverse R&D efforts. As a nice added bonus it will provide the opportunity to acquire future high-value startups before they are even real startups by simply hiring the developers and maybe tossing some stock options their way. On the flip side, I don't think AppEngine is going to have much effect on mainstream web application hosting. The API is too constrained and for a company with resources the ties to Google are most likely too tight. So I predict AppEngine will be more of a muted success for Google. The infrastructure built for it will be useful internally, it will help them get more sites up more quickly addressing eclectic needs without burdening employees, and it will provide a proving ground for future hires and possibly very early stage acquisitions. This could all add up to AppEngine being a very significant success, but it also means the success may out of the public eye.

What does I/O bound really mean?

2008-06-18T23:13:00.001-04:00

There's a lot of old folk wisdom out there that justifies the use slow languages and runtimes on the basis that the impact on performance doesn't matter. Here's a sampling of them:

Most applications are I/O bound so the performance of the programming language doesn't matter
The database does all the heavy lifting, so performance of the application code doesn't matter
Computer time is cheap compared to programmer time

Like most folk wisdom, these all have an element of truth. They are often brought up in discussions about the merits of strongly-typed compiled languages versus dynamic languages, and natively compiled languages versus virtual machine based languages versus interpreted languages. I could write about any one of them, and many more, but today I'll address I/O because of the “work” I've been doing on the WideFinder 2 project.

WideFinder 2

The original WideFinder project was, at least on first inspection, quite clearly I/O bound (well, if you had an input file smaller than your main memory...) The WideFinder 2 is a little better because it is a little more computationally complex, but not by much. The benchmark is really simple: process a big (42 GB) web server log file and report some basic statistics. In order to perform the benchmark, the program must parse the file, store information from each line on several maps, and finally extract some statistics out of them.

Tim benchmarked sequential block input on the test system at just shy of 150M/s. This means that the I/O alone required to process the 42GB file should take about 5 minutes, meaning that if the benchmark truly is I/O bound then the program shouldn't take much more than 5 minutes to run. Consequently, if we are to judge based on Tim's reference implementation of the WF2 in Ruby then it quite clearly isn't I/O bound.

I/O Takes CPU, too

If you look closely at the Bonnie benchmark results you'll notice that doing raw block I/O – meaning just reading files into a buffer – consumes almost 80% of the a single core of the CPU. That means that I/O alone comes pretty close to being bound by the CPU as well as being bound by the disk. In fact, experimentation uncovered that placing the system high load reduces maximum I/O throughput. In order to achieve maximum throughput, you actually have to ensure that you keep one core free to manage the I/O.

Application I/O is more than I/O

Another key factor is that what most application programmers think of as I/O involves a lot more than shuttling bits from disk into memory. For example, the Java and other unicode based platforms have to decode the character encoding of the file into the native character encoding of the runtime. In the case of the JVM, this not only requires that every byte be processed, but also frequently doubles the memory consumption of each character and requires the data be copied into a separate buffer. Furthermore, application code usually deals with files line-by-line in the form of some standard (often immutable) string object, thereby requiring yet another pass over the data. So when your code is simply iterating over lines in a file, it isn't really just doing I/O. A fair amount of CPU/memory bound work is required to deliver those nice, neat, unicode strings.

Large datasets change the rules

Memory management isn't free, and even with an industrial strength garbage collector it isn't always simple. A common practice with immutable objects is to have them share some internal state in order to avoid excess data copying. For example, when you take a substring of a Java string, the two string objects share an underlying character array. Often times this saves memory, and it changes generating a substring of a string from a linear time and space operation (with respect to string length) to a constant time and space operation. Unfortunately if the substring is much longer lived that the original string, and especially if it is much smaller, you end up with something that feels awful lot like a memory leak (I think it could be debated whether it is a leak or not).

Even if you're not carrying around a lot of excess baggage in the form of substrings, processing gigabytes of data consumes a lot of memory. In the case of WF2, a little bit of pretty much every line needs to be stored for the calculations at the end. The cast majority of my “debugging” time for WF2 was spent figuring out what JVM parameters will actually allow the program to finish without slowing to a crawl (pre-tuning there were points were it would spend 90% of its time in GC) or consuming every bit of memory available (at least a few WF2 solutions hog tons of memory).

All this means that when dealing with large files other parts of the system need to do more work, which takes away time that could be spent on “real” processing or on I/O (which we've already seen can be a CPU hog). Furthermore, I/O routines and routines commonly used along side heavy I/O (like regular expressions) must be very careful about their memory usage.

So is WF2 really I/O bound?

It depends. Go take a good hard look at the WF2 results page. If you look at Tim Bray's results you would conclude that no, WF2 clearly is not I/O bound. However, if you look at the top you'll see some very impressive numbers that indicate that WF2 indeed is I/O bound (side note: I really need to take a hard look at OCaml). Of course, you could argue that even in the OCaml case it really is CPU bound, because making the task take about as long as the required I/O saturated 8 cores and 32 hardware threads. Scanning down the list would seem to indicate that in most cases I/O does not represent a significant bottleneck, but then it's hard to really tell. The disk may not be the bottleneck, but the I/O routines within the libraries or runtime may be. Consequently, from the application programmer perspective, WF2 is I/O bound.

Redefining “I/O bound” and future impacts

For a long time “I/O bound” primarily referred to hardware or possibly operating system limitations. That was a useful definition, but it is time for it to change. Most software being developed today has a very tall stack of abstractions sitting between it and the hardware. Operating systems schedule I/O and have to split limited resources among many competing processes. Virtual machines sit on top of operating systems, isolating the programmer from the underlying OS and hardware. Libraries and frameworks isolate the programmer from the virtual machine and even other libraries and frameworks. I/O from the programmer's perspective is, or at least should be if he is working on top of good abstractions, that I/O is “everything that happens between when my program requests some data and when it receives it.” Consequently, libraries and runtimes should go to great lengths to ensure that being I/O bound is as close to its original meaning as possible. Prior to multicore systems becoming pervasive that was largely true, but today's I/O libraries fail to take advantage of them, and consequently force I/O into being a bottleneck when it should not be.

That's why in my Widefinder submissions I've worked to separate parallelized I/O into a library-like module. It quite clearly is not done, but it is relatively successful. I reused my the parallel I/O code that I developed for WF1 on WF2 without changing any of the logic. It doesn't provide many features, and it could use a fair amount of optimization and simplification (the line joining logic is an atrocity), but it works.

Multiprocess versus Multithreaded...

2008-04-09T21:10:00.005-04:00

...or why Java infects Unix with the Windows mindset.

Recently Paul Murphy, the king of the Sun zealots, blogged about Java bringing the Windows mentality to Windows, all the while slamming Java. In response, John Carrol, a Microsoft employee, rose to the defense of Sun's self-declared crown jewel. Talk about weird.

The funny thing is they are both right, although Murph's arguments are pretty weak.

A little history

Unix and Windows evolved with a very different definition of what the primary unit of isolation should be. On Windows, it is (or was) the node. Each Windows user (and DOS user before him) occupied exactly one node. The worst that could happen is the user destroys his own workspace, so interactive performance reigned supreme over system integrity. You have a node. You have a user. The node does what the user wants as fast as it can. Initially this applied to running a single application at a time, then to allowing several to be open at once but with the one in the foreground receiving primary resources, and finally to allow several applications to run simultaneously. Multithreading reigned king because it was lower overhead and focused on making that foreground process more responsive. Threads were optimized, while processes were neglected.

Unix evolved to be fundamentally multiuser, and its primary unit of isolation is the process. Unix systems were intended to be shared, so it was important that one user could not dominate over another. Furthermore, and slew of processes (daemons) all ran as the same under the same account, while providing services to multiple users, so in order for users to share processes must share. Unlike on Windows, one process crashing the entire system was not acceptable, because that would destroy multiple users' data. As a result, processes were designed to represent a strong level of isolation and heavily optimized to make sure people used it. Threads were largely ignored, or simply treated as processes with a shared heap space, because several cheap processes could simply be chained together to accomplish the same thing in a simpler manner.

The Unix Way

I want you to consider good old-fashioned CGI programs for a moment. Imagine one written in C. First, you may think "Oh my God, running a web application in a non-managed environment. The resource leaks! The memory leaks! The memory consumption of all those processes! Oh the horror!." Of course, you would be wrong. Repeating launching and terminating a Unix process is dirt cheap. Especially a simple program written in C. The OS will cache an image of the executable in memory which can be shared among invocations. The individual process can leak all the resources it wants, because as soon as it terminates all the resources will be automatically freed by the OS, not matter how incompetent the programmer. If the process fails to terminate your friendly neighborhood sysadmin can kill it without hurting any other process.

This method works for producing super-available applications despite incredibly crappy code. I've seen it, both in the for of CGI and in the form of much more sophisticated applications. It works. Users get upset about lost transactions, but the application as a whole almost never goes down.

Enter Java

Java took cheap Unix processes and made them expensive. To compensate, it provided primitives for multithreading. It provided a garbage collector to at least slow memory leaks. It turned all those transient application processes into one big JVM process not only serving all the transactions for a given user, but serving all the transactions for an entire application or even multiple applications. Java made it more difficult to make destructive program errors, but it also made the consequences much more severe. Your friendly neighborhood sysadmin is powerless against a runaway thread or a slow memory leak. All he can do is kill the process, bumping out all of the users, killing all of their sessions.

It's so bad, the process might as well be a node. Unix becomes Windows. The JVM is practically an operating system, but without all of the features of an operating system and a whole lot less mature.

Enter Java Frameworks

This is really what Murph was railing against, although he didn't name it and he conflated it with the core language by labeling "Business Java." Frameworks evolved for a myriad of reasons which are often summarized as "taking care of the plumbing to the developer can focus on the business logic." The "plumbing" is a lot of things, including managing certain resources and generally ensuring the application code executes within a well defined life cycle where it is unlikely to do damage. In other words, instead of giving the user a simple, uniform mechanism like a process to protect the world from his mistakes, he is given dozens of hooks where he can implement little snippets of focused and hopefully bug-free functionality. All this involves a lot of learning above and beyond "the Java you learned in school" (meaning the core language and libraries), putting a cognitive load on the programmer and additional runtime load on the machine.

Multiprocess versus Multithreaded

Most Unixes have evolved efficient threading, and Windows has come a long way in becoming a multiprocess, multiuser environment. Consequently, developers needs to be able to intelligently decide when to use multiple processes, when to use multiple threads, and when to use a hybrid approach. For example, Apache httpd has for quite a while now used a hybrid approach. One one hand on most operating systems threads involve less overhead than processes, so it is more efficient to use multiple threads than multiple processes. On the other hand multiple processes ultimately will give you better reliability because they can be spawned and killed independently from one another, so making a system that can run for months without stopping doesn't require writing a program that will run for months without stopping.

So how do you choose? My rule of thumb is to look at the amount of shared data or messaging required between concurrent execution paths and balance against how long the "process" (not OS process) is expected to live. Execution paths with lots of shared data or that are chatty will benefit from the lower overhead of threading, and threading allows you to avoid the complexities of shared memory or IPC. Of course, multiprocessing allows you to avoid the complexities of threading APIs, and there are libraries to address both, so the complexity issue could be a wash depending on your previous experience.

So why is Murph so wrong? Is JC right?

I think Murph wants to divide the world along nice clean lines. System programmers program in C. They don't need the hand-holding of managed runtimes or languages that treat them like impudent children. They do need lots of flexibility and lots of rope. Application programmers, on the other hand, need high-level abstractions that are close to the business domain that they are addressing. They need to be able to rapidly build software and rapidly change it as requirements evolve. They don't need lots of flexibility and should stay away from low-level details. So, in Murph's eyes, the problem with Java is that it doesn't do either particularly well. The managed runtime and object-orientation get in the system programmer's way, while the general-purpose nature of the language and mish-mash of libraries and frameworks just confuse application developers, or rather distract them from their true purpose. System programmers need C. Application developers need 4GLs.

The fatal flaw in Murph's reasoning is that it ignores the in-between. What happens when the systems programmer or 4GL creator fails to provide the right abstraction for the application developer? He's stuck, that's what happens. Software development is as much about creating abstractions as using them. Consequently, application developers need general-purpose languages.

Does Google Reader read GMail?

2008-03-05T21:54:00.003-05:00

Up until recently, all my "Top Recommendations" in Google Reader were related to IT, software development, math, and finance. This makes perfect sense, because that covers all the topics in my subscriptions. However, today I noticed the Google Reader suggested an RSS feed for a blog about local (kind-of) restaurants, clubs, bars, etc. This means that:

Google Reader has a decent idea about where I live
Somehow Google Reader figured out that I enjoy dining out

The best I can figure is that Google Reader is basing my recommendations on the contents of my email. While I don't have any feeds about such things, I do exchange emails with my wife and friends about making dinner reservations, where to go out to eat, etc. The other possibility is that it figured it out using my search history, except that the contents of my search history look pretty much the same as my subscriptions (I know, I'm a nerd). This is because usually I'm not logged into Google when I am searching. Consequently, I think it is reading my GMail.

Anyone else have any ideas?

Floating Points Stike CNN!

2008-03-03T17:20:00.003-05:00

Looks like developers at cnn.com need a lesson in floating point numbers:

Either that or the Democratic primary is truly too close to call...

Typesafe Ranged Integers in Scala

2008-02-18T22:19:00.006-05:00

For the past few weeks I've been working on a basic numeric library for Scala for eventual contribution to the Scalax project. My goal is to create an extensible, type-safe library that provides numeric types that are easy to use and more closely resemble their mathematical foundations than the primitive operations on which they are built. My initial focus has been on building a working rational numbers implementation with unlimited precision integers. However, today on the Scala mailing lists, someone raised the issue that Scala's use of primitive numbers doesn't belong in such a high-level language. When I read this, I thought "Hmmmm, my library helps with that."

Integer Underflow and Overflow

First, let's consider integer underflow and overflow. The standard Java/Scala integer type is a 32-bit twos-complement signed integer. That means it can representing numbers between 2147483647 and -2147483648 inclusive. Often times this is plenty range, so what we really want is for exceptions to be thrown when underflow and overflow. So consider the following:


scala> import scalax.math.Int32Domain._

import scalax.math.Int32Domain._



scala> val a: Int32 = 5

a: scalax.math.Int32Domain.Int32 = 5



scala> val b: Int32 = 7

b: scalax.math.Int32Domain.Int32 = 7



scala> a + b

res0: scalax.math.Int32Domain.N = 12



scala> a * b

res1: scalax.math.Int32Domain.N = 35



scala> val i: Int32 = 2147483647

i: scalax.math.Int32Domain.Int32 = 2147483647



scala> i + 1

java.lang.ArithmeticException: result exceeds maximum value: 2147483647

 at scalax.math.Int32Domain$Int32.checkRange(int32.scala:55)

 at scalax.math.Int32Domain$Int32.$plus(int32.scala:60)

 at .(:8)

 at .()

 at RequestResult$.(:3)

 at RequestResult$.()

 at RequestResult$result()

 at sun.reflect.NativeMethodAccess...

Magic! Overflow has been detected. Well, not quite magic. The way it works (and I'm sure it could work much, much better, I just through this together tonight) is that it converts the 32-bit integers into 64-bit integers prior to calculations, performs the calculations, then checks the result to ensure that it is within range. If it is within range, then the result is converted back into a 32-bit integer and returned. Between the usage of an object instead of a primitive and all this extra work for range checking, this class is probably at least an order-of-magnitude slower that using primitive Ints.

Bounded Ranges

Now let's consider bounded ranges. In order to accomplish this, we simply create an object that extends Int32 and overrides its minimum and maximum value.

scala> object SmallDomain extends scalax.math.Int32Domain { | override val max: N = 10 | override val min: N = -10 | } defined module SmallDomain scala> val d = SmallDomain.Integer(5) d: SmallDomain.N = 5

Now we have a domain that is limited from -10 to 10 inclusive. Attempting to mix integers from this domain with integers from other domains will yield a type error:


scala> i + d

:9: error: type mismatch;

 found   : SmallDomain.N

 required: scalax.math.Int32Domain.N

       i + d

           ^



scala> d + i

:9: error: type mismatch;

 found   : scalax.math.Int32Domain.Int32

 required: SmallDomain.N

       i + a

           ^

Even if you had a Int32 within the range of SmallDomain, you would still receive the type error. Also, as you can see, Int32 will not allow itself to be mixed with an integer from SmallDomain. If you look at the code (which I'll publish soon, I promise) for Int32Domain and its superclasses, you will see a lot of complex stuff involving mixins and type constructors. However, the end class is easily extensible by the user and still provides good type safety.

Rationals

I mentioned rationals at the beginning of this blog, so I thought I would give a little sneak-peak:


scala> import scalax.math.BigRationalDomain._

import scalax.math.BigRationalDomain._



scala> val a = Integer(3)

a: scalax.math.BigRationalDomain.IS = 3



scala> val b = Integer(7)

b: scalax.math.BigRationalDomain.IS = 7



scala> a / b

res0: scalax.math.BigRationalDomain.N = 3/7



scala> a.inverse

res1: scalax.math.BigRationalDomain.N = 1/3



scala> a.inverse * a

res2: scalax.math.BigRationalDomain.N = 1



scala> (a / b)^2345

res3: scalax.math.BigRationalDomain.N = 70687450412160609527952431393691553815800419127671886519112946722799601077076407951140254943159198319665943578284183744314587093153151823879346566151398437630838022610858501398173872472014103905434680267558985498302895510754430260294086995134629615707980341285332639084519209821403179213183556756416404920769037158823806045214292550723098516538040...



scala> a * b

res4: scalax.math.BigRationalDomain.I = 21



scala> Integer(3) / Integer(6)

res5: scalax.math.BigRationalDomain.N = 1/2

Notice how an integer times an integer equals an integer, but an integer divided by an integer equals a rational. This is because integer is a subtype of rational, because in all integers are rationals, but not all rationals are integers.

More to come soon!

Linguistic Success

2008-02-08T13:08:00.000-05:00

There's a new favorite pastime on the fringes of the Scala community. That pastime is blogging about aspects of the Scala language that will prevent it from being a "success" unless they are quickly addressed. "Success" is roughly defined as "widespread commercial use." A good metric might be: "How hard is it to find a job programming Scala?" The premise of the criticism usually revolves around one or more complicated, terse, or "foreign" (relative to the author) constructs that are common Scala, or at least favorites among frequent posters, and how these constructs will prevent "average" programmers from understanding Scala and thereby prevent commercial adoption. A recent favorite is symbolic function names (/: and :\ for folds).

The logic of this argument seems relatively sound. When choosing a technology for a project, it is very important to consider the availability of potential employees who know that technology. Forcing every new member to scale a potentially steep learning curve is a frightening prospect. I can imagine development managers lying awake at night fearing that their expert in some obscure technology will leave, and it will take months to replace him. It's a legitimate, although I think slightly exaggerated, fear.

That being said, I think it has little to do with the adoption of a new language. The majority of programmers simply do not spend their free time learning new languages. Many, maybe most, won't even use their free time to learn languages that they know have ready pre-existing demand. They learn when they are paid to learn, or when failing to learn will lead to immediate negative consequences for their career. I think the same can be said of most professions. Most people work because they have to, not because they want to.

Consequently, I think expanding beyond a core of enthusiasts is very difficult, if not impossible, simply be attracting people to the language. Right now some leading-edge Java people are taking a look at Scala, because they think it might be the next big thing in Java-land. These people are different than enthusiasts. Enthusiasts will learn a language for the sake of learning it. The leading-edge folks learn it as a high risk investment. If they can get a head start on the next big thing, it will be great for their careers (and businesses). These people constantly think "can I sell using this technology?" and "if I do sell it, while it come back to haunt me?" This is a very pragmatic perspective, and it is the perspective I take when I'm at work.

Confusing, odd-ball language features make the sell a lot harder. Pitching them as features increases personal risk.

But it doesn't matter.

Why? Because the vast majority of developers are not going to learn a new language because they want to, they are going to learn it because they have to. Not to mention that there are countless languages out there, so going after the enthusiasts and leading-edgers (who are mostly lookers anyway) is just fishing in an already over-fished pond.

So how does a language become a success?

Enough people use it for real projects. Let's say a consultant rapidly prototypes an application using the technology, and that application makes it into production. Now maintenance programmers have to learn that technology. Sure, it's complicated, but unlike the guy learning it on free weekends, the maintenance programmers have all-day every-day. It's hard to learn complex concepts a hour or two at a time, but these guys have all day, and the next day. It's hard to memorize something by looking at it a couple hours a week, but spend all day staring and it and it will click. Not to mention that their livelihoods depend on it. Any sort of "cowboy" development team can cause this to happen, and frankly such teams are pretty common.

So maybe one-in-five maintenance programmers actually like the technology, and admire the cowboys, so when they go get a chance to do new development, they use it, too.

The same thing can happen with products from startups. Let's say a startup builds a piece of enterprise software using Scala. They sell it to big, conservative companies by emphasizing the Java aspect. They sell customization services, too. And then it's back to the maintenance programmer, who has no choice.

Notice a pattern? The key to language success is making it powerful enough for a couple cowboys to do the work of an entire team in a shorter period of time. Selling fast and cheap is easy. If you have enough fast and cheap, the business people won't care if you are making it out of bubble-gum and duct-tape, because you are giving them what they want.

The key to success is making the reward justify the risk. Judging by what some people using Scala for real-world projects are saying, and my one hands-on experience, I think Scala offers it. It's just a matter of time before it sneaks its way into enterprises, just like Ruby has.

Programming Language Continuum

2008-01-21T21:35:00.000-05:00

Introduction

Ever since I started getting into less-than-mainstream programming languages, I've pondered how to go about classifying them according to their attributes in the hopes that it would yield insight into what an ideal programming language would be. There is the genealogical way that traces roots and influences, but that doesn't break down attributes or make any qualitative judgements. Here I intend to mostly frame the context for debate, rather than draw significant conclusions. I believe bringing some more structure to the discussion is necessary before much more can be gleaned from it.

So what I've done is attempt to break the essence of a programming language down into two dimensions:

Enforced Structure / Dynamism
Engineered Foundations / Mathematical Foundations

Here's a loose attempt at classifying some languages:

Enforced Structure vs Dynamism

Recent debates have focused heavily on the difference between statically typed and dynamically typed languages. I believe that this is a specific case of the more general issue of "how much structure should the programming language force on the programmer?" Today we see Java versus Ruby, but it could just as easily be Ada versus Lisp. On you side of the debate you have people who believe that heavily structured languages are essential for scaling and helping ensure correctness. One of my college professors once said (paraphrased) "the compiler is your friend, help it catch your errors for you." Also, a well defined and compiler checked structure can help scale programming projects up to large teams by ensuring that all team members are working to the same program structure. Finally, they point out the sophisticated tools that available for many statically typed languages, particularly refactoring tools, but also code generators and static validators.

On the other side of the debate you have dynamic language advocates. They claim that statically typed languages are too constraining and require more up-front design than is practical, especially given the vague and changing requirements typical of software development projects. Furthermore, robust code an be achieved through automated testing and by significantly reducing the amount of code required to deliver the required functionality. Finally, they point out the quicker feedback cycles that dynamic languages enable by shortening the change->compile->deploy->test loop to change->test. There was a time when this loop was actually figured into software development cost and schedule estimates, but today outside of very large projects it is simply a cognitive disruption.

Engineered vs Mathematical Foundations

Most of the mainstream programming languages have been "engineered" or "designed" to better enable some group of programmers to better achieve some objective. For example, Ada was engineered to enable the development of very large, complicated and highly reliable systems by huge teams. SmallTalk was designed to enable the construction of modular software in a more natural or "human" manner. COBOL was designed to enable business analysts to program. The list goes on and on, but the common theme is that most of these languages were designed or engineered with very specific design goals, and those goals were largely disconnected from strong mathematical foundations.

On the other side of the spectrum you see languages that are very strongly influenced by computer science theory. Lisp started out as an executable implementation of the untyped lambda calculus and has stayed fairly true to that origin. Haskell combines the typed lambda calculus with category theory and focuses on functional purity. Prolog is based on logic, and SQL on relational theory. What these languages offer, especially strongly typed ones like Haskell, is that they enable computer programs to be much more easily reasoned about by theorem provers (and similar) and therefore can provide a much higher degree of safety. To the initiated, they also provide much more natural and elegant abstractions.

Hybrid Languages

The idea of dynamic languages with option type annotations is often raised as a potential means to bridge the divide between the advocates of static and dynamic languages. Common Lisp provides optional compile-time type checking, but in practice is seems to be used mostly as an optimization in special cases rather than as a means of ensuring correctness. Some touted StrongTalk as an answer, especially when Sun released it as open source, but it seems to have sputtered out. There was much talk about adding optional type annotations to Python, but I believe (please correct me if I am wrong) it is still absent from Python 3000. So while optional static typing is a favorite debate topic, its not popular in the languages that have it and attempts to add it to languages that don't have yet to reach fruition, despite considerable effort.

A recent phenomena, or perhaps simply recently receiving attention, are hybrid languages that attempt to blend concepts from strongly-typed functional languages such as Haskell with more mainstream object-oriented underpinnings. In my opinion, Scala is probably the best of these, as it offers innovative OO features in addition to functional ones, but others such as F# and OCaml certainly deserve mentioning, as do no doubt countless others that I am unfortunately going to neglect.

Conclusion

I think that hybrid static/dynamic languages will never really become popular - or more accurately that the capability will not be extensively used in the languages that offer it. There are a couple reasons for this. Primarily, I think that making static typing optional almost completely eliminates the benefits of static typing. Second, I think the primary advantage of dynamic languages is that they allow partially formed thoughts to be quickly expressed in "working" (meaning running, not correct) code, and that static typing is a major barrier to this. I personally find doing exploratory programming in dynamic languages to be much more pleasant and productive, but once ideas are concrete I prefer the compile-time checks and completeness of static typing.

I personally believe that languages that blend the engineered structure of OO with mathematical formalism represent the future of programming. Scala and F# are here, and both Java and C# are gradually acquiring features from strongly typed functional languages. What's going to be interesting is how it shakes out. If you peruse the Scala mailing list archives, you will notice that there is a marked tension between those from an object-oriented (engineered) perspective who enjoy the extra power that functional programming provides them, versus those from a more pure functional programming background (mathematical). Ultimately, at least from a popularity perspective, I think the more OO approach will win, as historically languages engineered to provide specific advantages have won out over languages with robust mathematical underpinnings.

I hate Apple and HP

2008-01-21T07:49:00.000-05:00

A couple months ago I bought a new MacBook. For the most part I've loved it, but last night I ran into a problem.

When I bought my Mac, Apple was offering a $100 rebate on the purchase of a new printer to go with it. The sales guy pointed out that there are number of printers that cost around $100, so the printer would be essentially free. I chose an HP C4280 All-in-One. Look at that! If it wasn't for sales tax I would have made five cents off of the purchase. Well, you get what you pay for

As a printer it's worked fine. I didn't even need to install any drivers. I plugged it in and it just worked. Of course, that's what I expect from Apple. But last night my wife wanted to scan a document and make it into a PDF. I figured, "Ok, that should be easy." Boy was I wrong.

So I launch Image Capture on my Mac to scan the document. It tells me that I don't have any attached devices. Hmmm. I printed a few minutes ago. Why don't I have any attached devices? So maybe I'm using the wrong application. There's a "scan" button on the printer, so I press that, hoping that the right application will magically open up (see what Apple has done to me!). The printer thinks for a minute, and then tells me that it's not connected through USB. Well, of course it is, because I just printed over USB. I decide to do some Googling

It turns out that while the printer drivers come pre-installed with Leopard, the scanner drivers do not. It's a 192 MB download full of crapware. I hate Apple for making me think that I didn't need to install drivers, and then consuming a chunk of my Sunday evening installing drivers. They set an expectation and then disappointed. It would have been much better to just make me install all the drivers up front.

But why did I say it was full of crapware? Well, let's see. So I scanned the document as a PDF with text (so it has to do OCR) using "HP Scan Pro." That worked. Kind of. I did get a decent looking PDF document with the text correctly converted into text. I also got a completely locked up HP Scan Pro application, and I mean completely locked up. I tried to log out of my Mac, figuring that would clean up the crashed process. Nope! It sat there for a minute, then complained that an application wouldn't exit and asked if it should do it forcefully. I of course said yes, and then it just sat there for a few minutes longer. I got the same result from trying to shut down. At least when you tell Windows that it can violently kill, it violently kills the processes. Apparently MacOSX is too polite, or at least has more patience than I do.

That's another reason to hate Apple. It was worse than Windows, and using a product purchased from the Apple Store no less.

Fortunately I'm a Unix guy and I know how to violently kill processes.


su
ps -ef | grep HP
kill -9 pid1 (pidX is the process id of an HP process)
kill -9 pid2

Until they are all dead. That worked. Of course in the process of doing this I discovered that there are a couple HP processes running as root, which disturbs me to no end.

What I'd like to ask Steve Jobs is: How many Mac users would know to drop down to a terminal, su to root, and violently kill the processes? I just can't see your average non-techie Mac user doing that. Apple should really do a better job screening the products it sells with new computers.

Slightly Less Double (Im)precision

2008-01-02T22:49:00.000-05:00

Anonymous writes

You may want to try evaluating the polynomial using a different form. For example, given the polynomial: A*x^3 + B*x^2 + C*x + D one is often tempted to just enter it "as is". However it can also be expressed this way: ((A*x+B)*x+C)*x+D Generally speaking polynomials often work better using floating point this alternate way. Some programming languages/systems know this and convert the expression before evaluating it.

...and he is absolutely right. It makes the code of heck of a lot more efficient, too, because it eliminates the calls to Math.pow. That being said, it does not completely fix the problem. The polynomial line is a lot smoother, and the fitting algorithm yields a lower degree polynomial for the same mean error, but I still think the results are too fuzzy compared to the higher precision floating point. Here's a graph to show the difference:

Compared to the previous result:

Further improvement could probably be obtained by taking a close look at the QR Decomposition algorithm used to do the least-squares fitting.

In my opinion, the problem here is not so much the double-prevision floating points are bad. They are not. For many applications, especially with carefully crafted algorithms, they are great. They are certainly much higher performance than their higher-precision object-oriented kin. I'll warn you: Don't do high precision matrix operations with your MacBook in your lap - it gets really hot. The double-precision version finishes in a blink. It also takes a several orders of magnitude longer than using doubles. The problem is that, as an abstraction for real numbers, doubles are extremely leaky. Of course, this could be extended to any fixed-prevision, floating-point representation of numbers, depending the application.

Basically, I think in most applications doubles represent a premature optimization. Higher-precision numbers should be used by default, and then the precision reduced in order to improve performance, rather than doubles being used by default and then higher-precision numbers being considered if the programmer realizes that he has a problem due to lack of precision.

Of course, the problem is I don't know how precise is enough, because it depends entirely on the application. I'm tempted so say that, whenever possible, exact representations should be used. I've done a little research into it, and I'll do some more. There's tons of papers on the subject, but everything I've encountered so far seems to require intimate knowledge of floating points, the algorithm using the, and possibly the data being fed into the algorithm. That could help with library functions, such as matrix decomposition and solving, which could automatically scale up the precision of their internal operations in order to meet the expected resulting precision of the calling code, but that would still be leaky for "user-implemented" algorithms. What I really want is something that will work in the general case with reasonable performance characteristics, which can then be tuned for specific applications by reducing precision.

Open Source, Cost, and Enterprise Product Adoption

2008-01-02T20:13:00.001-05:00

This is a relatively common topic, and today is was raised on TSS, as a result of a blog by Geva Perry:

Are developers and architects becoming more influential in infrastructure software purchase decisions in large organizations?

...with an implied "as a result of open source software." It's an interesting question, and I think it can be generalized to: What effect does license costs have on the acquisition of enterprise software?

In considering this question, it is important to remember that:

In large organizations, money often comes in many colors, such as: expense, capital, and internal labor
The level of authority an individual has depends on both the amount and the color of the money involved
Certain colors of money are easier to obtain than others, and sometimes it varies dependent on the amount
Accounting rules, both standard and self imposed, effect what can and cannot be purchased with a given color of money

In a nutshell, the budgeting process for large organizations can be extremely idiosyncratic. Not only do the official processes vary, but individual personalities and budget cycles can have profound effects.

So the first effect the cost of a piece of enterprise software has is to limit the various buckets of money that can be used to pay for it. However, this can be a very complex process. Let's assume any given piece of software typically has the following types of cost:

One-time license cost (both for the application and support infrastructure, such as the OS and DBMS)
Recurring maintenance and support cost
Hardware cost (e.g. a server)
Internal labor for development and deployment
External labor for development and deployment

The lower the costs involved, the less approval is required. Driving down license costs pushes the initial acquisition decision closer to the users and/or developers. This is a big win for open source applications. It's probably a bigger win for application vendors. For example, most enterprise applications require a DBMS, such as Oracle. Oracle is not famous for being cheap. So let's say your potential customer can readily obtain $100k to spend on software licenses. If you are a software application company, do you want that money as revenue, or do you want 2/3 of it to go to Oracle and IBM?

I'll give you a hint. You want a department to be able to deploy your software without cutting a check to the big boys, but you want to be able to say "Yes, we support your enterprise standards" to the big-wigs in the IT department who think that there isn't a major conference for a piece of software, then it shouldn't be on the network. That way your product can be approved, and then the running it on Oracle can be deferred until "usage levels warrant it."

Hardware costs are even more interesting. At my employer, equipment that costs $5k or more is "capital," and less than that is expense. Capital is generally easier to obtain if (1) you know you need it a year in advance, or (2) it's the end of the year and there's still money laying around. It is impossible to obtain at the beginning of the year, when everyone thinks that they will actually spend their allocation, unless of course it was approved last year. Conversely, expense money is much more plentiful at the beginning of the year, when managers are still dreaming of sticking to their budgets, and becomes more and more difficult to obtain as reality sets in. So what's the point? Well, you want your product to require a small enough amount of hardware so that a first or second line manager can purchase it on expense without obtaining approval, but also have a recommended configuration that costs enough to be purchased on capital

This is interesting because big-iron Unix guys will often lament about how their systems have such a lower TCO than x86 Wintel or Lintel systems, so all the arguments about x86 systems being "cheaper" is bunk. What they are ignoring is that it is much easier to spend $5k on twenty small things (plus setup labor on each of those twenty items) than it is to spend $50k on one big item, because the $50k either has to be approved a year in advance or it has to wait until someone else's project falls apart so they can't spend the $50k. The "total" in TCO is completely ignored, because very few people think about the few hours that each of those servers requires to setup.

Now, about labor costs. Managers generally have at least some discretion over how their direct reports spend their time. If you actually think about it in terms of the fully burdened hourly cost of an employee, managers often have significantly more "budget" under their control by their means to direct how time is spent than they do for purchasing licenses and services. Again, this is a big win for open source.

The bottom line is that the best way to get your foot in the door is to have the lowest marginal cost of deployment as possible. I'll offer as evidence the countless wikis that have popped up around my workplace, very few of which are even officially approved.

Of course, this makes you wonder why the marginal cost of deploying a piece of enterprise software tends to be so high. Why aren't more vendors practically giving their software away for small deployments? Well, many do, such SQL Server Express and Oracle XE. But there's still more that don't. The problem is that it's really hard to get the total cost of initial deployment down to below the point where the bureaucracy kicks in, and once in kicks in it helps to be more expensive.

Yes, that's right, I said more expensive.

You see, these days one of the great ways to make your career in IT is to be a good negotiator. The combination of off-the-shelf software and outsources have shifted IT expenses from being dominated by internal labor to being dominated by procurement contracts. However, you don't build and illustrious career by negotiating $10k contracts. Likewise, once you pass a relatively small threshold someone decides that the project needs a "real" project manager, instead of just an "interested" manager or a technical lead, and project managers measure are unfortunately measure more by the size of their projects than the value that they deliver. (yes, that's right, screwing up a multi-million ERP implementation is better for your career than successfully deploying some departmental application under budget and on schedule)

In other words, once the signatures of additional people are required, you have to have something big enough for those people to consider it worth their time. So, if you are a software vendor, or an internal employee planning a deployment project, then you either need to go really small and viral or really big. Medium size projects are simply too hard to push through.

And, in my opinion, that's really a shame, because medium sized projects tend to have the best value proposition. Small ones involve too little of the organization to have a significant impact, and large ones become two unwieldy to meeting objectives. Projects need to be large enough to do things right in terms of technology and engage future users, but small enough have readily apparent benefits and incremental deliveries that provide real value (not simply "look, it's a login screen!").

Maybe it's different in other organizations, but somehow I doubt it. However, I'd be really interested in knowing what others' experiences are.

Double (Im)precision

2007-12-31T14:18:00.000-05:00

Most computer users have, at one time or another, received an odd result from a spreadsheet or other program that performs calculations. Most programmers know that this is because of the impedance mismatch between the most common way for computers to "think" about numbers (base 2) and the way most people and businesses think about numbers (base 10). This issue receives a fair amount of attention, probably because we've all (we being programmers) have had to explain to users why a piece of software can't seem to do arithmetic properly. If you're scratching your head right now, or want to know more, I suggest reading this FAQ about decimal arithmetic.

However, as I've long know but rarely contemplated, there if another form of floating point error that can cause significant problems. Standard floating point numbers only store so many digits of precision. The result is that if you add a very large number to a very small number, the very small number simply vanishes. Let me demonstrate:

scala> 10000000000000000.0 + 1.0
res62: Double = 1.0E16
scala>

The 1.0 simply vanished, because standard double-precision floating point numbers don't have enough digits to store the 1.0 part of such a large number. Doubles are an approximation, and that's fine, because often times all we're approximating things, anyway, and the roughly 15 decimal digits of precisions provided by a double is plenty, right?

Well, actually, no. It depends on what you're doing with them. A month or so ago my father convinced me that instead of spending my free time playing with AI problems and studying fringe programming languages, I should do something useful like predict stock price movements. Of course I can use AI and fringe programming languages to do this...

The first thing I decided to do was to smooth out stock price history and make it continuous by fitting a polynomial. So I wrote a quick polynomial class, grabbed Jama (a Java matrix library), downloaded some data, wrote a function to search for the appropriate degree, and this is what I got (supposedly with about 4% error):

Hmmm...that looks kind of funny. The blue line is the actual price. The red line is the polynomial, which has a degree of 44. That's a rather large degree, but certainly not enough to generate all those squiggles. Those squiggles are an artifact of double precision numbers not being precise enough to be used in calculating a degree-44 polynomial. They don't work that well for the matrix calculations that produce the polynomial, either.

I think that red squiggly line is a very good illustration of what happens when you don't pay enough attention to how your software works under-the-hood. Anyway, here's what the results look like using floating point numbers (courtesy of JScience) with 80 digits of precision (keeping the error at about 4%).

Looks a lot better, doesn't it? One interesting thing is that the resulting polynomial has a much, much lower degree than what was produced by the same algorithm using double precision numbers. With double precision numbers, 4% error was about as good as it could get with this dataset. However, using the higher-precision numbers it can go much lower. Below is a graph at about 2% error:

At this point you might be wondering why anyone would use double precision numbers for this type of thing, or perhaps thinking I'm a moron for trying. I certainly felt a little stupid. But using doubles is relatively common. Matlab and everyone's favorite Excel use doubles. Many of the other toolkits and libraries that I found do as well.

Overall I think I'm either missing something (because the use of doubles is so common), or I find this very frightening. I'm not an expert in this area. I know the doubles use much, much less memory and computational resources. They are also "just there" in pretty much all programming environments, so they are the default. Making arbitrary precision floating points work right wasn't a cakewalk, either. I spent the better part of a day tracing through my code, only to discover a bug in JScience. Also, once you have everything working, you have to figure out what precision to use. The default of 20 digits precision in JScience wasn't noticeably better than regular doubles.

Data Center Meltdown

2007-12-11T07:43:00.000-05:00

Denial and the coming “data meltdown” by ZDNet's Michael Krigsman -- Subodh Bapat, Sun Microsystems eco-computing vice president, believes we’ll soon see the first world-class data center meltdown. According to News.com: “You’ll see a massive failure in a year,” Bapat said at a dinner with reporters on Monday. “We are going to see a data center failure of that scale.” “That scale” referred to the problems [...]

Now let's think about that. How can a datacenter fail?

It can lose power for an extended period. It takes a lot of backup generators to keep a 50 megawatt datacenter humming.
A virus or worm can shut it down.
A natural disaster can destroy it or force a shutdown. Often times this is due to a power failure rather than destruction.
It can have its WAN/Internet connection(s) severed. This isn't quite catastrophic unless you're on the other side of the WAN.

Michael has pointed out that Subodh Bapat doesn't point to the expected cause of a major data center meltdown, he just says one is coming. That's because it's not really a matter of one cause. There are so many risks, and you multiply them by the growing number of data centers, and what you come up with is that there's bound to be a major failure soon. We just don't know what the precise cause will be.

Most of the threats involve a geographically localized destruction or disabling of the data center. This means you need off-site recovery, and it probably needs to be fast. That means you probably need more than recovery, you need one or more hot sites that can take over the load of one that fails. This is extremely expensive for a "normal" data center. I can hardly imagine how much it would cost for a 50+ megawatt facility. Basically what we have is too many eggs in one basket, with economies of scale pushing us to keep on putting more eggs in the same basket.

What surprises me is that Subodh Bapat didn't say, oh, well, Sun has the solution. Considering that Jonathan Schwartz put it forward over a year ago. Ok, well, he didn't exactly suggest Blackbox as a means of easily distributing data centers. But think about it. If you're a large corporation you are probably already geographically distributed. If you expand your data center in cargo-container sized units across the nation (or world), you are half..err..maybe one quarter of the way there. You still have to figure out how to make them be hot sites for each other, or at least recovery sites. But at least losses at any given site would be minimized.

Why isn't enterprise software sexy?

2007-12-09T16:16:00.000-05:00

Robert Scoble asks: Why isn't enterprise software sexy?

A couple of the Enterprise Irregulars and several commentors respond: Because it's supposed to be reliable and effective, not sexy.

I think the reasons are more fundamental than that. Consider:

Most enterprise software customers have mutual non-disclosure agreements with the software vendors.
Most bloggers have day jobs
Most companies do not want their employees violating the terms of contracts.
Most companies do not want their employees airing the company's dirty laundry in a public forum
Many of the most interesting pieces of information surrounding enterprise software involve dirty laundry.

Personally, I have two ground rules for blogging:

Keep it professional. No personal matters, politics, etc.
Keep my employer, coworkers, and my employer's customers and suppliers out of it.

Let's face it. Most IT and software development projects don't go right. The commercial software that you use doesn't perform half as well as the salesman said it would. Consultants have mixed motives, and more importantly aren't miracle workers. The internal team if often over extended and working outside their core area of expertise. Goals are unclear, completely undefined, or changing on a regular basis. Politics are everywhere on all sides.

This is the reality of business, and talking about it in the general case is OK. People read it, nod their heads, and this "Been there, done that, doing it again right now." But specifics are quite different. Specifics can lead to embarrassment, contract violations, and lost sales.

More people don't blog about enterprise software because it strikes too close to home. I don't think it has anything to do with whether enterprise software is sexy or not.

Update:

It just occurred to me that I probably wasn't very clear here on a few points. What is mean by "enterprise software" is enterprise application software, like SAP, Oracle's various applications, PeopleSoft, etc. I don't mean infrastructure software like DBMSes, application servers, operating systems, etc. There is plenty of good information freely available on infrastructure, and people blog about it all the time.

Also, if you look at a lot of the blogs that are out there for, for example, SAP, they are almost all too high level to be particularly useful. It's pretty easy to find platitudes about how you need the right team, buy-in, executive sponsorship, etc and how those (or a lack of them) caused an implementation to succeed or fail. That's all (for the most part) true but everyone already knows it. But there's not a lot of people (that I know of, please post links in the comments if I am wrong) out there posting technical discussions about implementations. Google for "ABAP programming blog" (ABAP is the programming language for SAP), and then do the same for Scala and Lisp. I bet there are more people earning their living off of ABAP than Scala and Lisp combined. Probably an order of magnitude more. So why aren't there more people writing about it? Ok, so Scala and Lisp are both interesting languages. So do the same for Ada and COBOL.

Update: December 10, 2007: Feedback on enterprise software

Enterprise software does receive feedback. Often times significant amounts in forms much better thought out than most blogs. The difference is that the feedback is private between the customer and the software provider. Occasionally it is shared among customers through conferences or other types of "user group" meetings.

If the software supplier will listen (including acting), then this can work fairly well for software that is already deployed. The problem is that there is no information solid information available to support purchasing decisions. There are no readily available sources of "tips and tricks" or "common pitfalls" for deployment or customization efforts. For example someone could write:

We've spent the last 3 months trying to make Foomatic run on top of Oracle. All the sales material touts the Oracle support. But then your deployment tanks, the consultants come in, and they ask you why the heck you aren't using SQL Server. The software is developed against SQL Server and then "ported" to Oracle, and the Oracle port never works right.

Fill in your favorite or least favorite infrastructure products there, the name of an enterprise application, and there you have some useful information. The sales material lies. Once you deviate from their default stack you are screwed. That's the type of information that would be useful - before buying the software or before trying to run it on your "enterprise standard." Not from an over-priced consultant.

Running Linux apps on a Mac using X

2007-12-09T10:58:00.000-05:00

John asks:

Please can you post something about how you set up and use X to run your linux apps from your mac? I've been using X to login and use my linux desktop on my mac laptop for a few things but what I would really love to know how to do is to run individual programs which I cannot get running on my mac or haven't got room for.

Certainly! I'll start from the beginning. The Linux distribution I'm using is Fedora Core 6. The instructions should be similar for any other Unix variant. I used the GUI administration screens to do the configuration (I know - LAME!) so that's what I'm going to use here.

1. Make sure your Linux box has a static IP address.

This step largely depends on your network setup, and technically isn't 100% necessary. In order to access your Linux box, you must either know its IP address or have a domain name for it that will be translated into an IP address. If you are on a corporate network there's a good chance that there's already a DNS entry for your Linux box so you just need to know its name. Here's what I did for my home network.

1.1 Login your router and reserve a range of IP addresses so that they will not be assigned out by DHCP.

Please refer to your router's manual for details on how to do this. Depending on your router you may be able to assign a static IP address explicitly to your Linux box based on its MAC address. I could not.

1.2 Configure your Linux box to use a static IP address.

Launch the network config utility. This will require the root password. Edit your ethernet adapter and configure it for a static IP address instead of DHCP. Choose an IP address within the range that you reserved in your router, or one that your network admin has provided.

2. Enable sshd on your Linux box.

You can do this using the "Services" applet or by editing your /etc/rcN.d (where N is the desired runlevel) scripts. Enable the service and start it. Notice that I am at runlevel 3. This is because I'm now running my Linux box in headless mode, so I just want it to boot up to a console login prompt, not a graphical prompt. If you your Linux box boots up to a graphical prompt, and you intend to keep in that way, then you want runlevel 5.

3. Setup a DNS entry on your Mac.

As root, edit your /etc/hosts file and add an entry for your Linux box. So open a terminal window and type:

  cd /etc
  emacs hosts

The line for "gondolin" is the entry that I added: Save the file by hitting Control-X Control-S, then exit emacs by hitting Control-X Control-C.

4. On your Mac, launch X and ssh as follows to your Linux box.

  ssh -X gondolin

The "-X" flag tells ssh to automatically setup your DISPLAY environment variable. Once you are logged in, simply type the name of the application that you want to run, followed by an ampersand.

5. Be careful about some applications.

Most applications work fine when started from the command line, but starting the full KDE or GNOME desktop sessions does not work properly for me. I'm pretty sure that's because on my Linux box they are configured to run locally. There are some applications, such as Nautilus and Konqueror that are setup (and least on my FC6 box) to plug themselves into the desktop manager session. This results in all sorts of weirdness when there is no KDE or GNOME session running. Nautilus tries to start a GNOME session, which brings up an unusable desktop, and Konqueror just acts weird. However, Nautilus works fine if you give pass it the "--no-desktop" command-line option. The following opens Nautilus in your home directory.

  nautilus --no-desktop ~/

That's it! Feel free to post any questions.

Adventures in Widefinding: Performance

2007-12-06T20:36:00.000-05:00

I've done some basic performance tests against:

Scala Actor-based parallel Widefinder
Scala serial Widefinder using a BufferedReader
Tim Bray's Ruby Widefinder

The test platform was my 2.2 GHz MacBook with 4GB of RAM using a 6 million line file. The times were as follows:

Scala Parallel:

real 0m14.588s
user 0m24.541s
sys 0m1.383s

Scala Serial:

real 0m20.095s
user 0m18.821s
sys 0m1.441s

Ruby:

real 0m14.301s
user 0m12.485s
sys 0m1.813s

The good news is that the parallel Scala version is noticeably faster than the serial version. The bad news is that it is roughly the same speed as the Ruby version, and takes significantly more CPU. The Scala versions are doing substantially more work, because they have to transcode the 8-bit ASCII contained in the input file into 16-bit Unicode strings. This requires a full scan of the data. I believe a fair amount of performance could be gained by combining the transcoding pass over the input with the line-splitting pass.

For those that are curious, the source code for the parallel widefinder is available here: the parallel IO code the actual widefinder code

Adventures in Widefinding: Complexity

2007-12-05T08:12:00.000-05:00

For the moment I'm going to ignore the complexity of my widefinder "under the hood," and just focus on the complexity of it at the top level. The following is Tim Bray's goal. The red asterisk indicates that the loop should be processed in parallel instead of in serial.

counts = {}
counts.default = 0

ARGF.each_line* do |line|
if line =~ %r{GET /ongoing/When/\d\d\dx/(\d\d\d\d/\d\d/\d\d/[^ .]+) }
counts[$1] += 1
end
end

keys_by_count = counts.keys.sort { |a, b| counts[b] <=> counts[a] }
keys_by_count[0 .. 9].each do |key|
puts "#{counts[key]}: #{key}"
end

So here's the first part of my Scala solution:

   val pat = Pattern.compile("GET /ongoing/When/\\d\\d\\dx/(\\d\\d\\d\\d/\\d\\d/\\d\\d/[^ .]+ )")
   val map = new ConcurrentHashMap[String, AtomicInteger]()
   for (file <- args; line <- LineReader(file)) {
       val mat = pat.matcher(line)
       if (mat.find()) {
         val s = mat.group().substring(23)
         map.putIfAbsent(s, new AtomicInteger(0))
         map.get(s).incrementAndGet()
       }
     }

Notice that this is not a map-reduce based solution. This is because I tried to make it look as similar to the original Ruby as possible. There are some minor differences due to the fact that regular expressions are not special in Scala the way they are in Ruby. The big, and in my opinion most intrusive difference, is that a ConcurrentHashMap has to be used to store the results, AtomicIntegers must be used for the counts, and that weird "putIfAbsent" call needs to be used for pulling counts out of the map.

So while the concurrency itself is implicit, and the code is certainly succinct, the programmer still needs to be very much aware of the fact that the block inside the for loop will be executed in a concurrent fashion. This is certainly less elegant than a pure functional approach such as map-reduce, where no synchronization would be necessary, but I also think it is less intrusive to a programmer accustomed to imperative programming.

Here's an ugly part. This is largely due to an impedance mismatch between Java collections and Scala collections. It would look a lot better if Scala had an equivalent to ConcurrentHashMap in its library. There's also probably lots of other ways to make it cleaner. I tried several different approaches and always ran into some problem.

    val array = new Array[(String, Int)](map.size)
    val iter = map.entrySet.iterator
    var i = 0
    while (iter.hasNext) {
      val e = iter.next
      array(i) = (e.getKey, e.getValue.intValue)
      i += 1
    }

And here's the final part, once the ugliness is done:

    quickSort(array)((e) => OrderedTuple(e))
    val limit = if (array.length < 10) array.length - 1 else 9
    for(i <- 0 to limit) {
      print(array(i)._2)
      print(": ")
      println(array(i)._1)
    }

Notice having less that ten results is cleanly handled, unlike in TB's code (unless Ruby magically ignores invalid indices).

Overall I would say I came pretty close to TB's goal without without requiring a fundamental change in programming methodology. I didn't alleviate the need for the programmer to be aware of concurrency, but I don't think that's possible. Sure, people can learn to program in ways that are fundamentally parallelizable, and that probably is what universities should start teaching, but that's going to require a major shift on of part of millions of programmers, or for several generations to retire and be replaced by ones trained in functional programming. Lots of cores are here NOW, so it's not practical to wait until skills catch up. We need to work with what we have.

Switch

2007-12-03T22:44:00.001-05:00

After about two years of running Linux-only (Fedora, to be exact) at home I've switched to a Mac. I wanted a laptop, needed a new computer desperately (the old one is almost 6 years old), didn't want Windows, and was tired of messing with Linux configuration stuff.

This weekend I bought a Macbook. So far I love it. I was hesitant about the keyboard, which is odd, but I actually like it. I was nervous about using a touchpad instead of a pointer stick, but somehow the touch pad on the Macbook works substantially better than the one on the HP I use at work. I was worried about quality problems...we'll see about that one. I just read about some Macbooks and Macbook Pros having defective harddrives, but the model number on mine is different.

So what have I done so far?

Booted the first time. Wireless worked flawlessly on the first try. I've spent way too much time making Windows PCs (my wife's, my work laptop, visitors' machines) work with my wireless network. One of my friends tried to make his Linux laptop work with it and after many hours never succeeded.
Installed Eclipse and the Scala plugin, played around with that.
Installed AquaMacs - IMHO much better than Emacs on Linux.
Surfed the net, poked around, reconfigured some stuff to my liking, etc.
Setup NFS mounts to my old Linux box. This was amazingly painless on both sides. The only hiccup was that I had to change my UID on my Mac from 501 to 500, which created some oddities before I logged out and back in, but nothing horrible. The whole process probably took about 15-30 minutes, compared to hours I spent to make Samba work properly with with wife's Windows XP Thinkpad.
Setup sshd on my Linux box and then ran XWindows applications on my Linux box from my Mac. This whole process took about 10 minutes, and the XWindows apps actually looked good and were very responsive. Possibly more responsive than running them locally. Note that this and the above are a tribute to both Fedora and MacOS X.
Upgraded my RAM from the stock 1GB to 4GB.
Ran my Scala widefinder from Eclipse. It spikes both CPUs once everything is cached. Puts both at about half if it has to read from disk.
Wrote this blog.

So all that is very positive. And the UI is so beautiful. The fonts all look just right...although if I didn't have good eyes I think a lot of them might be too small.

Ok, so what's wrong:

I haven't figured out the keyboard shortcut to switch between windows of an open application. Command tab switches between applications.
No page down, page up, home, end, etc keys on the laptop keyboard.
The caps lock key is WAY too big. Keys sizes should be proportionate to usefulness/frequency of use. Spacebar is huge. Enter and delete are big. Caps lock being the size of enter makes not sense.
I had to install ~200MB worth of updates fresh out of the box...over half of that for Leopard. Why can't a new computer to all up-to-date? Seems like that "genius" who sold it to me could have given me one that was up-to-date.
After the reboot for the Leopard updates, everything froze. Just a blue-grey screen with no cursor. That's a bad first impression. But I turned it off and back on again and everything was fine.
I had to install codecs for video various video formats. That's mildly annoying. Why can't they be preinstalled? It's not like I had to pay to download and install them. But what's more annoying is that the first link presented to me for XVid didn't seem to have any appropriate install files for Mac. I used DivX instead, which worked.

So overall I am very impressed. I think I'm going to keep my old Linux box around as a server and to run Linux-only stuff over X. If anything goes wrong I'll be sure to complain about it.

Adventures in Widefinding

2007-11-25T16:39:00.000-05:00

Over the past few weeks in my copiuos free time I've been trying to come up with a fast Widefinder using Scala Actors where the parallelization magic is hidden behind what looks like a nice friendly API. Based on timings on my oh-so-fast Athlon XP 1900+ I seem to have failed on the first account (Ruby is faster) and the second part requires some awareness of parallel programming. But I'm hopeful that when Tim runs it on the T5120 it will be competive with the other solutions, although I doubt that it will be the fastest. For those of you who don't want to listen to me ramble, here's a jar containing all of the class files needed to run my solution along with the Scala source code. It's so big because I put the Scala libraries in there for Tim so he wouldn't have to worry about CLASSPATH error or installing Scala. Ok, so why isn't it the fastest? What's the point? Well, first let me define what I think a good widefinder solution should demonstrate.

The "application code" should be similar in complexity and readability to Tim Bray's example in Ruby. Anything else should be hidden behind a general purpose API, preferably an out-of-the-box one.
It should be environmentally friendly. This means that it shouldn't hog all the available RAM and make other processes start paging. It should also be well behaved on a machine under load. This is not relative to input file size. It should ALWAYS be environmentally friendly.
It should maintain the abstractions to which programmers are accustomed. For example, it shouldn't bypass regexes or use non-standard string types. Also, if a language normally deals well with unicode and the potential for multiple encodings, it should deal well with unicode and multiple encodings as well.
The person running it shouldn't have to tell it about details like how many worker processes to spawn. It should figure it out based on its environment. Ideally the programmer shouldn't have to worry about it either.
It should be sufficiently performant on a single processor box.
It should run faster as more processors are made available.

I think my solution is reasonable according to all of these measure. Hopefully we'll see about execution on lots of cores shortly. #1 is a little tricky, because the using a concurrent map was tricky and there is a definite impedance mismatch between Java collections and idiomatic Scala. Depending on your perspective a map-reduce based solution would have been more elegant, but unless map-reduce becomes required learning for all professional programmers then I'm not so sure. #2 is one area where, in my opinion, many of the current leading solutions fall down. A favorite way of achieving easy parallel IO (well, IO on most disk can't really be done in parallel) is to spawn a bunch of processes (or threads) and have them each mmap a large chunk of the input file and process it. The issue with this is that, as Fredrik Lundh noticed (BTW - he has an excellent discussion - go read it), this can cause serious paging on some operating systems. Other solutions allocate buffers measured in megabytes for each worker thread/process. I personally don't see this as very environmentally friendly when only kilobytes are really needed. My solution reads the file sequentially using one set of buffers per worker (about 128k total per worker). Each worker reads in 32k and then passes the FileChannel to the next worker. #3 is the real kicker, and what kicked down the performance of Scala (and, I believe, any other JVM based solution). Java strings are unicode and based on 16 bit characters. The input file is ASCII and based on 8 bit characters. Consequently, a String-oriented solution on the JVM has to transcode the characters. Futhermore, it should be able to transcode the characters from any common file format, not just ASCII or UTF8. This turns out to take a lot of cycles, around 10% depending on the charset and the cost of some other functions. The good news is that each buffer can be transcoded in parallel. #4 is more about maintaining abstractions. My solution does it automatically, the other solutions don't seem to...although adding it probably wouldn't be a big deal. #5 is probably true of most of the solutions...or true if you substitute dual-core for uniprocessor, because that's what most of the people used to develop their solutions. In the case of my solution I think there is about a 30% performance penalty on a single processor box (that and transcoding are enough to make it slower than Ruby). #6 is interesting because this is an I/O bound task. Assuming the data is actually being read from disk (I believe it is cached in all or most of his trials), then this task should only be able to keep a small handful of processors busy. But that's not to say it isn't important. The reason it's important is because from the normal programmer's point of view, file I/O isn't just shuttling information from the disk to a buffer, it's everything that happens between him making the request and a string representing a line being returned. There's a lot of work that goes into making that string. Here's a list (more or less) for Java and Scala.

Read the data into a direct ByteBuffer.
Copy the data into a heap ByteBuffer**
Transcode the ByteBuffer into a CharBuffer
Find the characters that represent a line
Make a String from those characters

Your operating system probably uses something called readahead to asynchronously fetch the next N bytes of a file before you actually request it, on the assumption that you will. The Java or Scala library could asynchrously fill a fixed-sized queue of lines, assuming concurrency is cheap enough. I learned a lot in this excersise, but my two big takeways are:

Abstraction has a real cost in terms of CPU cycles, and existing abstractions in mainstream languages (ok, Scala isn't mainstream yet, but Java is) are not optimized for multi-core environments. This will need to change.
Abstraction has a big cost in terms of programmer cycles if the programmer wants something different. Without the source available from OpenJDK I would have been lost when I was trying to figure out why approaches that seem like they require less CPU work actually require more. The Client and Server VMs make a huge difference in performance that varies widely depending on file size and program structure. With the libraries, JVM, and OS all trying different things to make your code go faster it is extremely difficult to figure out exactly what is happening and why.

**I looked at the OpenJDK source and if you use NIO to read into a non-direct buffer, what actually happens is the Java library reads into an available direct buffer and then copies it into a direct buffer. This is essentially what happens with a regular FileInputStream as well. At first I thought I could speed things up by skipping the copy from the direct buffer to the non-direct buffer, but it doesn't. You see, decoders are optimized to use the array backing the buffer if it is available because direct array accesses are much faster than function calls. Array copies are done using low-level native code. Consequently, copying the direct buffer and the transcoding the in-heap copy is much faster than directly transcoding the direct buffer.

Why test parallelism on a simple function?

2007-10-10T06:46:00.000-04:00

On my last blog anonymous asked:

would a more expensive line-match-function make it more obvious if you are working in parallel?

I would say that one should be able to demonstrate that transparently supporting the potential for parallelism should be near free. If you can use a parallel algorithm to solve a problem that doesn't benefit much from parallelism with roughly the same or better performance characteristics as the serial code then it should be a lot better when you actually give it a more complex problem. Basically, parallelism should be free. A lot of people have commented on Tim Bray's blogs that his test is unsuited for demonstrating the benefits of parallelism because it is IO bound. Tim claims this isn't true, and I suspect there's some truth to that if you have really optimized IO, but I do think the benefits of parallelization for him problem are very limited. That being said, one thing that it he has clearly demonstrated is that parallelism isn't free. His "obvious" newbie solution in Erlang performed horribly and was considerably longer than the Ruby solution. Others have greatly improved the performance with extremely long, complicated chunks of code, but have yet to match Ruby. I find that really sad. So I would like to prove that parallelism can be almost free, meaning:

Leveraging it does not impose a significant additional cognitive load on the programmer.
Problems that are not effectively parallelizable should execute "about as fast" when parallel functionality is used as with serial code.

From an interface perspective I think I have it with the monadic interface to the file. I just need to work out some bugs or change the interface to make them go away. I'll write more on this when I've worked out some of the wrinkles. So that leaves the performance problem. One of the big challenges with parallelization is that spawning new threads or processes is very expensive, and synchronization is somewhat expensive, so it's very easy for the cost of parallelization to overwhelm the cost of the actual solution. The most straight forward way to address this problem is to not parallelize when the function is not complex enough or the input data set isn't large enough to justify it, but that is back to imposing a cognitive load on the programmer because he has to figure that out. Either that or always "start serial" and use runtime profiling tricks to detect if the problem is worth parallelizing, which sounds expensive put probably has merit. Another challenge is knowing how to divide up the problem to avoid excessive synchronization and/or messaging. When processing a file line-by-line, one could send each line out to be processed independently, but that requires a lot of messaging and synchronization if you don't have lock-free messaging. So really you want to break the problem into properly sized chunks and send each chunk as a message rather than simply use the most natural division. Figuring out how big a chunk should be (or how many chunks you should have) is a challenge because it is problem and runtime dependent. Again, this creates the potential to burden the programmer, use complex and potentially expensive runtime profiling, or somehow come up with a magic cheap hueristic. So you can either solve the problems above, or you can have sufficiently cheap parallelism that you don't need good solutions. Right now I'm going after the sufficiently cheap approach. What I have so far is a mapreduce-style function using Scala Actors that breaks a file into chunks of lines and sends them off to be processed by an Actors. I plan on adding a parallel foreach function that could be used for problems like Widefinder using a parallel hash map. Performance wise it's looking promising. Here's some numbers (using my 5+ year old machine): Serial:

Count: 185300 Serial: 11592 real 0m12.107s user 0m11.254s sys 0m0.784s

Parallel:

Count: 185300 Serial: 11722 real 0m12.225s user 0m11.441s sys 0m0.723s

As you can see the parallel code is slightly slower than the serial code. Across runs their times actually overlap a bit, but serial generally times to be a tad faster. One thing I've noticed is that the deltas between the serial and parallel implementations don't really grow - and to some extent shrink - with increasing input sizes. I believe this is because there is a fixed penalty for setting up the thread pool for the actors. This only has to be done once per process invokation, and appears to cost about 200ms on my machine. In other words, parallelization for file processing can be almost free. I actually think it could be better-than-free, even on a single processor box, if IO was more efficient. My current solution is using a BufferedReader to read in the file one line at a time. This means the IO is probably being done in a less-than-optimal way, and that a lot of work is being done in serial for each line (converting from 8bit ASCII to 16-bit Unicode strings, splitting it into lines). I'd like to use nio to read the file in a block at a time, and then let all this work be done in separate threads. I think then there would be a performance increase because one thread would be doing nothing but reading in buffers as fast as the OS and JVM and provide them, and others would be doing all the computation while the IO thread is blocking. But before that I'm going to get the interface cleaned up and solve the memory problem on large files.

Dangerous Monads?

2007-10-07T18:21:00.000-04:00

I've been trying to write a parallelized version of Tim Bray's Widefinder problem in Scala where the parallization is "hidden" in some library-like code so that the programmer can write something that looks as clean...nay...cleaner than Tim's Ruby code using Scala. I'm also trying to figure out what the heck a monad is, and thinking about how I'll have to use ugly, imperative Java IO classes, so I decided to write some classes to make a file look like a list of strings, with each element representing one line. One critical aspect of this list is that it is lazily generated, so you don't have the wait for the entire file to be loaded to start working with it. Another critical trait is that there are no "back references" from subsequent lines, so that if you no longer hold a reference to previous nodes in the list, those nodes can be garbage collected. The interface supports all the required methods for "for" comprehensions - map, foreach, filter, and flatMap. I think it qualifies as a monad, or at least is something close. I ended up with something where usage looked kind of like this:

def main(args : Array[String]) : Unit = {
  val pat = Pattern.compile("GET /ongoing/When/")
  for (file <- args; line <- Line.open(file) if pat.matcher(line).find) cnt = cnt + 1  }

Note that I'm just counting lines there, not performing the full Widefinder functionality. But still, that's pretty concise and easy on the eyes. The "for" comprehension is translated into calls to foreach. It works great for a lot of files, but it blows up with a OutOfMemoryError on large files. So why is that? I'll give you a hint, fully expanded it would look kind of like this:

args.foreach((file) => Line.open(file).filter((line) => pat.matcher(line).find).foreach((line) => cnt = cnt + 1))

Can you see the problem? No? Try this:

args.foreach((file) => {
 val firstLine = Line.open(file)
 firstList.filter((line) => pat.matcher(line).find).foreach((line) => cnt = cnt + 1))
})

Can you see it now? The problem is that there's a reference to the first line hanging around. Even if you don't declare the variable it's still there, lurking as the implicit "this" parameter for filter. That reference makes it so the first line is not collectable, and as a result none of the lines are collectable because they are all reachable from the first line. So the whole file is loaded into memory, resulting in an OutOfMemoryError. That seems pretty dangerous to me. So how can we solve this problem? Well, we have to make it so that references to lines disappear as we get done with them. There are a couple ways to do it. The obvious imperative way is the use a var and a while loop, but then you might was well use BufferedReader directly or use an iterator. The functional way is to use tail recursion, so you write:

def scanLines(line: Line, pat: Pattern, cnt: Int): Int = {
  if (line == EndOfFile) cnt
  else {
    val v = if (pat.matcher(line.value).find) 1 else 0
    scanLines(line.next, pat, cnt + v)
  }
}

...and call it for each file like this:

for(file <- args) cnt = cnt + scanLines(Line.open(file), pat, 0)

Notice that there is no val declaration holding the first line. This is critical, because if there is, it will run out of memory. So what do we do about it? Well, it would be easy enough to refactor methods like foreach that trigger immediate file traversal out of the normal interface and into a tail-recursive method on the companion object. Unfortunately that would break usage in for comprehensions, be inconsistent with other collection-like objects, and in general feel like poor OO. Another way to fix it would be to fix Scala so it supported full tail call optimization. Of course, that would also require adding full tail call support to the JVM. That way the unneeded "this" reference could silently disappear from the stack. This would also allow many methods to be expressed in a much cleaner way. For example:

  final def foreach(f: (String) => Unit): Unit = {
    def fe(line: Line): Unit = {
      if (line != EndOfFile) {
        f(line.value)
        fe(line.next)
      }
    }
    fe(this)
  }

Could be simplified down to:

  final def foreach(f: (String) => Unit): Unit = {
    f(value)
    next.foreach(f)
  }

For those of you who want to take a look at the code I have so far, here it is as an Eclipse project. I've tried to comment it a bit, but it's still a work-in-progress. There is a working (at least I think it works) mapreduce function hiding in there that allows lines to be parallel processed using actors. Unfortunately it is slower (but not substantially slower) than just processing the lines serially. But then I'm running it on an old uniprocessor PC, so maybe with more cores it would do better. If I get some free time at work I'll try it out on a multicore machine and see what happens, but I suspect that unless (or until) I hack together something that uses nio in an optimal way the task will remain IO bound...and even then it may remain IO bound.

The Tar Pit

2007-09-17T21:50:00.000-04:00

The editor of TSS has decided to run a series discussing The Mythical Man Month, by Frederick Brooks. Hopefully it will produce some good discussion. There are a lot of Agile advocates that hang out on TSS that really could use to (re)learn some of the lessons of software development. I make a point of rereading it every few years lest I forget the lessons learned by computing's pioneers. The first chapter - The Tar Pit - contains on of my favorite concepts, as illustrated by the graphic below (slightly changed from original): Programs Let me explain. A program is what we all have developed. It's simple piece of software that is useful to the programmer and/to some set of users who are directly involved in defining its requirements. Most bespoke departmental and a substantial portion of enterprise applications fall into this category. They are sufficiently tested and documented to be useful within their originating context, but once that context is left their usefulness breaks down quickly. In addition, they are not solidly designed to be extensible and certainly not to be used as a component in a larger system. Obviously this is a range, and I've really described a fairly well developed program - one almost bordering on a programming product. That script you wrote yesterday to scan the system log for interesting events that has to be run from your home directory using your user account in order to work is also just a program. Programming Products Moving up the graph, we hit programming product. In theory, all commercial applications and mature bespoke applications are programming products. In practice this isn't really the case - but we'll pretend because they are supposed to be and I increased the standard over what Brooks originally described. The big challenge with programming products is that, according to Brooks, they cost three times as much to develop than simple fully-debugged programs yet they contain the same amount of functionality. This is why it's so hard to get sufficient budget and schedule to do a project right. The difference between a solid piece of software and something just cobbled together is very subtle (you can't tell in a demo) yet the cost difference is quite astounding. Consequently, I think most commercial applications are released well before they hit this stage, and bespoke ones require years to mature or a highly disciplined development process to reach this point. Programming Systems Programming systems are programs intended to be reused as parts of larger systems. In modern terms, they are libraries, frameworks, middleware, and other such components that are all the rage in software development. Like programming products, programming systems are thoroughly tested, documented, and most importantly are useful outside of the context in which they were created. And, like programming products, according to Brooks they take three times as long to develop as a regular program. Developing programming systems for bespoke applications or niche use can be a tar pit all its own. For one, many programmers like building libraries and frameworks. The problems are more technically challenging, and there is no strange-minded user to consider. The programmer and his colleagues are the user. Programming systems are relatively common in groups that execute a lot of similar projects and/or that contain programmers who really want to build components. Programming System Products Amazingly, programming systems products are relatively common - even if there really aren't that many of them. As you've probably guessed, a programming system product has all the traits of both a programming product and a programming system. It is useful to a wide range of users and can be effectively extended and/or embedded for the creation of larger systems. It has complete documentation and is extensively tested. Where are these wondrous things? Well, you are using one right now (unless you printed this). Your operating system is one. It both provides useful user-level functions and a huge amount of infrastructure for creating other programs. MS Office is one as well, because it has a pretty extensive API. Most commercially developed enterprise systems should be programming system products, because:

They provide off-the-shelf functionality for regular users
Customers always customize them
They often must be integrated with other products
Simply integrating their own components would go better with a programming system

The problem is that they are not, because of: The Tar Pit Brooks didn't explicitly write this definition of The Tar Pit but I think he would agree. Put yourself in the position of a development manager at a startup or in a larger company about to launch on a new product. On on hand, you want to make the product as good as possible. You know that what you develop today will serve as the base for the company/product line for years to come. It needs to be useful. It needs to be extendable. It needs to be thoroughly tested and documented... It needs to be cheap and delivered yesterday. The differences between a programming system product and a simple programming product are far more subtle than the differences between a program and a programming product. But the programming system product costs a full NINE TIMES as much to develop as the program with essentially the same "outward functionality" - at least if you are a sales guy or a potential customer sitting in a demo. I think this is the struggle of all engineering teams. If the product is long lived, doing it right will pay major dividends down the line. But it can't be long lived if it is never released. It stands a worse chance if it comes out after the market is flooded with similar products (actually, that's debatable...). The ultimate result is a mish-mash of tightly coupled components that, as individuals, fall into one of the lesser categories but as a whole fall down. There is a documented API, but the documentation isn't really that good and the application code bypasses it all the time. The user documentation is out-of-date. Oh, and the application isn't really that general - hence why all the major customers need the API so they can actually make it work. Escaping the Tar Pit Ok, so if you develop a large system you are destined to fall into the tar pit because cheap-and-now (well, overbudget and past schedule) will override right-and-the-next-decade. You need a programming system product, but budget and schedule will never support much more than a program. So how do you escape it? Accept It Products that give the outward impression of being far more than they are often sorely lacking in conceptual integrity. If you are building an application - build it right for the users. Remember you can build it three times for the cost of building a programming system product. Maybe by the third time there will be budget and schedule for it. Or maybe, just maybe, you can evolve your current system. But pretending will just make a mess while wasting significant amounts of time and money. Partition It Some pieces of your system are probably more important than others. There are places where requirements will be volatile or highly diverse amoung customers - those are the places where you need a truly extensible system. You should also be able to reuse strong abstractions that run through your system. The code associated with those abstractions should be top-notch and well documented. Other pieces just need to be great for the users, while a few that remain need to be convenient for yourself to extend or or administrators. Open Source It Find yourself developing yet another web framework because what exists just isn't right? Open source it. This isn't really my idea. It's what David Pollak of CircleShare is doing with the lift web framework for Scala (actually, I'm guessing at David's reasoning, I could be wrong). The infrastructure for your application is essential, but it isn't your application. It is what Jeff Bezos refers to as muck. You have to get it right, but it's distracting you from your core mission. So why not recruit others with similar needs to help you for free? That way you don't have completely give up control but also don't have to do it alone. Theoretically the same could be done for applications. Many large customers of software companies have significant software development expertise - sometimes more than the software companies. I think it would be entirely feasible for a consortium of such companies to develop applications that would better serve them than commercial alternatives. But I have yet to convince someone of that...

Is implementation important to a startup?

2007-09-04T07:36:00.000-04:00

I'm not entirely qualified to answer this question, but here it goes. Taken from the Scala mailing list:

Amir Michail

On 9/2/07, Erik Engbrecht > ...

> All-in-all I would say Scala would be perfect for a small team of > extraordinarily smart developers, but I wouldn't turn your average Java or > C# programmer pulled off the street loose on it. Not because they couldn't > write working Scala code, they could, it would just be a more concise > Java/C#. But I wouldn't start a company based on programmers grabbed off > the street (or leased across the ocean), either. >

I actually don't think implementation is much of an issue for internet startups, particularly for Facebook apps. This is off topic, but I would be interested in knowing what you think of it: http://weblog.fortnow.com/2007/08/impact-of-facebook-platform-on-cs.html http://weblog.fortnow.com/2006/07/science-and-art-of-computation.html

So here's what I wrote (off-list) in response:

Amir, I'm not really qualified to comment on the skills required to write Facebook apps because not only have I never written one, I've never even accessed Facebook. However, I think one of the most effective ways of achieving long-term success for a business is to have a product that is in demand (obviously) and others find very difficult to replicate - or at least replicate to the point where people have difficulty deciding whether to use the new product or the old. The best way I can think of to do that is for the product to have an inherent internal complexity - meaning it requires either hard-core CS skills, substantial domain knowledge, or both to grok it. For example, Google is really an AI company. They don't actively publicize it (nor do they hide it), and I bet the majority of their employees aren't working on anything AI related, but ultimately that's what the company is - and that's why they'll stay ahead. Replicating the core of their business is simply too hard. It certainly could be done, but you'd need to get a sufficiently large group of self-motivated geniuses together who would both cooperate and have enough entrepreneurial spirit to not be lured away by Google. I'm not saying you can't build a successful startup simply by creating something cool and getting a lot of people to use it. You certainly can. In fact, I would say the vast majority of successful startups were built that way. But I also think the vast majority of startups don't have long-lasting products. They have products that fill a (possibly transient) need for a larger player and get acquired. They spend hundreds of thousands for maybe a few million dollars building something that would take a larger player >$10x plus months to replicate, not because the startup is better at engineering or product design - it may or may not be - but because the startup is 1 of 100 or even 1000 so the larger player would have to fund >10 initiatives a pick the somehow pick the best result in order to replicate what the startup did, and it can't do that because it can't release >10 similar products all at the same time without looking stupid to investors and confusing its customers. From what I've read about Facebook apps they are relatively easy to build. If you build a business around one, then essentially you are either trying to be that 1 in >100 that people latch onto long enough for a larger player to be acquired, or so are going to launch yourself on a never ending cycle of re-inventing your application as people duplicate it and trends change. Of course, that's not to say you can't have something really sophisticated at the core of your Facebook app. I'm sure you can. But if you do, implementation matters a whole lot. Implementation tends to lag theory by years if not decades. Your ability to implement is your competitive discriminator. As for the blog articles...well...I think the CS should remain more pure. CS is not programming, but programming is an essential skill for computer scientists (as I actually believe it is for most scientists, but in CS is is a much stronger need). So I think adapting CS to "Web 2.0" is a rather foolhardy exercise. By the time programs adapt we'll be on Web 4.0, so the programs will be behind the times and will have lost the theoretical goodness of CS. That's not to say those programs are bad ideas, I just don't think they should be labeled CS. It dilutes the brand, so-to-speak. I would say CS programs should offer far more electives that are cross-listed with other disciplines, such as business, economics, or the sciences. But these can't replace fundamental courses or even upper level technical electives, so they would need to be framed as to replace what my alma mater called "humanities requirements." -Erik

That's just my opinion, and to tell the truth my opinion has changed over the years. But this is closely related to the ongoing debate about whether a CS backrgound is or is not important for being a software developer. I actually think it is, but I also think a good CS program is overkill (in the CS theory and programming sense) for what most software developers do and grossly inadequate from a communications/requirements analysis sense.

Scala Code for GPS

2007-08-28T16:13:00.000-04:00

The link to the source code in the previous blog didn't work. I put it in the wrong directory. It's fixed now. You can get the code here: scala-gps.zip

Scala vs Lisp for GPS: Part I: Expressivity

2007-08-21T07:19:00.000-04:00

Introduction Before I found Scala I was looking for a language with the following characteristics:

Expressivity on par with Python or Lisp
Performance on par with Java
Has a REPL or at least an interpreter
Compiled
Object-oriented
Large number of modern libraries and frameworks
Cross platform, including think-client GUIs
Open Source

Now I've found Scala and I think I have my language, but unfortunately it's hard to tell about the expressivity without doing a real project and doing a real project involves a measure of risk. Instead, I decided to port some Lisp programs from Norvig's Paradigms of Artificial Intelligance Programming to Scala and compare them to the original Lisp programs. As as second step, I'll "Scala-ize" each program to be more idiomatic Scala (mostly increasing object orientation) to see the result. Finally, I'll attempt to do some sort of performance comparison. Background - What is GPS GPS stands for "General Problem Solver." The algorithm here comes from Alan Newell and Herbet Simon way back in 1957. The original attempt was to create a computer program that could solve any problem. It fell quite short of its goal, but the algorithm is still interesting and its expression in Lisp or Scala quite concise. Those of you familiar with planning problems will recognize the basic structure and the sample problems. For more information, see Chapter 4 of PAIP. The Algorithm A problem is described using a set of initial conditions, a set of operators that can change those conditions, and a set of goal conditions. Each operator has a name, a list of preconditions (conditions that most be true for it to be invoked), an add list (conditions it will add to the state when invoked), and a delete list (conditions it will remove from the state with invoked). Note that these conditions are simple. They are not based on on propositional or predicate logic. The GPS uses a technique called means-ends analysis. A brief explanation is contained here about half way down the page. In a nutshell, the algorithm tries to achieve each goal one at a time, until it fails to a achieve a goal or it has achieved all the goals. The preconditions for each action are achieved by recusively invoking the algorithm on them. For a detailed description of the implementation of the algorithm, see PAIP or look at the comments in my Scala code. Comparison of Implementations There are some substantial differences between the Lisp implementation and the Scala implementation. They are:

The Scala implementation is more explicitly structured. Some of the structure, such as the static typing, is forced by Scala. Others, such as using classes instead of conventions on list contents to distinguish between normal conditions and "executing conditions," are not forced by Scala but are simply easier and more natural.
The resulting plan is a list of operators rather than a list of lists obeying a convention. This is straightforward because "executing conditions" are a special class of condition and are explicitly tied back to the operators they represent.
The core algorithm in Scala is completely and explicitly devoid of mutable state. The Lisp solution makes only one small use of mutation in achieve-all, and that occurrence could easily be removed in the same was as it was from Scala. However, cons cells, and the lists they form, are mutable and therefore it is much more difficult to prove that the algorithm uses no mutable state.
The Scala solution required fewer utility functions. This is due to both the richer standard library and case classes.
The problem-definition DSL required significantly more code in Scala, especially in order to make it interpreter-friendly.
The syntax of the problem-definition DSL in Scala is statically checked. For example, you cannot use preconditions in the place of the add list. Achieving this took a fair amount of work, and I almost just went with a looser version that was equally easy to type and read but less validated.
In my subjective opinion, the Scala version is much easier to read. I find the fact that Lisp control structure like "if" implicitly return nil on failure if not "else" is provided to be quite confusing.

General observations:

At least for this problem (which didn't use macros), Lisp code could be almost directly converted to Scala.
Scala implicits make an effective substitute for special variables (i.e. defparameter) in Lisp.
Overall LOC count is too close to matter.
Lisp development is far more interactive that Scala.
The Scala compiler catches a lot of "stupid" mistakes that the Lisp compiler does not (but the Lisp compiler catches some, much more than Python, Ruby, et. al.), reducing the number of edit/run cycles by a fair margin.
Case classes are really useful. They allow you to add structure to your program without going to all the work of implementing all the support methods, such as equals, hashCode, toString, and unapply for pattern matching. Lisp is worse than Java et. al. because it has four different equals functions (eq, eql, equal, equalp) all with subtle (and not so subtle) differences. In Scala, if you are wise and don't have to deal with Java libraries (hah!), you pretend eq (reference equality) doesn't exist (indeed, pretending references don't exist, and null doesn't exist, seems like a good idea to me). In fact, I find case classes so useful, I think I'm going to write a Python metaclass so I can use them in Python, too.
I retract previous negative statements about pattern matching on lists. It's useful. I get it now. But I still wouldn't convert a string to a list just for pattern matching.

Updated - Finished point 6. Conclusion I'm not going to conclude anything yet. So far, Scala seems to be as expressive as Lisp, and its added structure and compiler definitely reduce the number of errors made while coding. However, this comparison was on a relatively simple piece of code and the Scala implementation was mostly a port. This means that I can't say one way or another whether the added structure of Scala would be a help or a hindrance to the early stages of flushing out code. Based on my experience with Python, I think without case classes the added structure would definitely be a hindrance. Keeping all the basic functions (comparison, hash, toString) up-to-date on rapidly changing objects is a real pain.

Syntactic Sugar for Composition/Delegation

2007-08-17T12:36:00.000-04:00

Composition/Delegation is a common pattern in object oriented software. There are a lot of different definitions floating around for both composition and delegation, but basically it amounts to this, as demonstrated in Java code:

class MyStringList implements List<String> { 
    private List<String> backingList;
    public MyStringList(List<String> backingList) {
        if (backingList == null) throw new NullPointerException();
        this.backingList = backingList;
    }
    public String get(int i) { return backingList.get(i); }
    public boolean isEmpty() { return backingList.isEmpty(); }
    // ... lots of other methods like the ones above
    public void add(String s) {
        if (s == null || s.length() == 0)
           throw new IllegalArgumentException();
        backingList.add(s);
    }
    // and some more slightly modified methods to complete List
}

So MyStringList is composed of backingList and it delegates most of its methods to it. Furthermore, in this case it is using backingList to implement the interface List. There are other ways to use composition and delegation, both together and separately, but this is the pattern with which I'm concerned. If I had full written out the code, the first thing you would notice is that there is a painfully large amount of boiler-plate code (the List interface requires 25 methods) to accomplish very little. If you know Java or a similar language, you would then probably think that it would be easier to use inheritance as follows:

class MyStringList extends ArrayList<String> {
    public MyStringList() {}
    public void add(String s) {
        if (s == null || s.length() == 0)
            throw new IllegalArgumentException();
        super.add(s);
    }
    // do something for the other add methods as required...
}

That's a lot less typing. It's also strongly coupled to ArrayList. Depending on what you're trying to do, that may or may not be a problem. For example, let's say you are developing a web application using Hibernate, and you want Hibernate to lazily fetch the contents of the list. The only way would be to extend Hibernate's list instead, thereby breaking any code you already wrote that assumed ArrayList and strongly coupling you to a specific ORM. The other problem is that Java only supports single inheritance, so you can only save typing for one interface. If you have several, you are out of luck. Trust me, these are not good things. So, with Java at least, you are stuck between a rock and a hardplace. You either get strong coupling or a lot of typing boilerplate code. If you don't believe me, ask Google. But problem is very solveable. On one hand there's mixins, but these introduce their own set of restrictions, oddities, and coupling. It would be better to add something simple that preserves the pattern in an easily understandable way while eliminating the boilerplate code. Delegation should be made part of the language. So instead of writing the initial piece of code, you would write:

class MyStringList implements List<String> { 
    private delegate List<String> backingList;
    public MyStringList(List<String< backingList) {
        if (backingList == null) throw new NullPointerException();
        this.backingList = backingList;
    }
    public void add(String s) {
        if (s == null || s.length() == 0)
           throw new IllegalArgumentException();
        backingList.add(s);
    }
    // and some more slightly modified methods to complete List
}

The delegate keyword tells the compiler that any methods from List that are not already implemented should be generated by delegating responsibility to the member backingList. This eliminates the boilerplate code without introducing excess coupling, reducing flexibility, or even being particularly confusing. Furthermore, this scheme could work in many languages. I'm not a compiler hacker, but concepts like this are always better with a demonstration. So I've thrown together some Python that enables this behavior. Code is here. It's far from production-quality. I'm sure people will find plenty of flaws. But it does demonstrate the concept (along with showing how easily extensible Python is.

Business Engagement and IT Project Failure

2007-08-14T22:45:00.000-04:00

CIO.com recently ran an article by the CIO of GE Fanuc regarding "functional engagement" (i.e. "the business" or more commonly "the users") and project failure. Michael Krigsman later posted a more succinct summary on his ZDNet blog. Here's a even shorter version:

Make sure a single business-side has significant capability, responsibility, and authority for project success.
Don't short-circuit important parts of the project
Make that person understands the "laws of IT" and defends them to his peers, subordinates, and superiors

#1 is just plain common sense. #3 amounts to establishing a scape goat for the inevitable failure caused by short-circuiting appropriate systems engineering or architectural activities. Notice that there is neither a definition of "failure" nor a definition of "success." I think it can be inferred that he's defining "failure" as "exceeding project or maintenance budget and/or schedule." Not once does he mention delivering real innovation to the business or even real value - just avoiding causing massive amounts of pain. Consider the following statement:

Enterprise platforms like Siebel, Oracle and SAP are not intended to be heavily customized. When going from a niche, custom application to Siebel, you need a strong functional leader to push back on every “Yeah, but” statement. They must start at zero and make the business justify every customization. Saying “no” to customization is bitter medicine for your business partners. They will make contorted faces and whine ad nauseum. But it is for their own good.

Let's think for a moment. Your customer (internal or external) wants to spend millions of dollars implementing a CRM (or ERP, PLM, etc.) package. Earlier, it went to the trouble of building one from scratch. That probably means it considers CRM to be an extremely important part of its business, and it expects to derive a competitive advantage from having a shiny new system. The best way to be competitive is to copy what everyone else is doing, right? Also, repeatedly receiving "no" as an answer will really make your customer want to take an active role in the implementation, right? Hmmm....somehow I don't think so. Introducing a strong impedance mismatch between the organization and the software it uses is failure. Standing in the way of innovation is failure. Mr. Durbin wants you to fail. There is actually a simple, albeit occasionally painful, solution to this problem: don't buy an off-the-shelf application that neither meets the business's requirements nor can be cost-effectively extended to meet them. First, you have to understand your business processes and requirements. I mean really understand them, not just understand the official process documentation that no one follows. All those winces and "yes buts" are requirements and process details that absolutely must be understood and addressed. Second, you do a trade study. This is a key part of systems engineering. Replacing enterprise systems is expensive, often prohibitively expensive, so do a thorough analysis. Take some of your key users to training sessions and write down every wince and vaguely answered question, because those are all either issues that will stand in the way to delivering value or will require customization. Finally, keep your pen in your pocket. Don't be tempted to write checks, buy licenses, and sign statements-of-work before your really understand the product. Just ignore those promises of discounts if you get a big order in before the end of the quarter. The next quarter isn't that far away, and the end of the fiscal year may even be approaching. The discounts will reappear then. Instead, make sure the vendor really understands the requirements and business process, and structure any contracts in a way that they must be met or the vendor will face significant penalties. It's amazing what comes out of the woodwork when you do this. All of a sudden that 3x cost overrun from the original projection is sitting right there in front of your eyes in the form of a quote, all before you've sunk any real money into the project. The purpose of engaging "the business" in an IT project is not to create a personal shield for all the deficiencies in the system you are deploying. It is to make sure you identify those deficiencies early enough in the project cycle to avoid cost and schedule overruns.

Minimal Software Development Process

2007-08-03T10:10:00.000-04:00

It's not uncommon for me to find myself in debates regarding what constitutes a sufficient software development process. On one side, there are the Agile folks who argue that code-and-fix, with user representatives determining what should be fixed. Of course they have lots of rules to regulate the code-and-fix, some of which are quite sensible and some of which are quite dubious, to make it appeal to closet process engineers. On the other side you have old-school developers who believe in such rarities as requirements signed in blood and requiring human sacrifice to alter. Ok, so perhaps I'm exaggerating a little bit. But that's how it often feels. So I'm going to propose my own process that is every bit as simple as what the Agile crowd pushes while being more all-encompassing than traditionalists. Here it is:

Define the problem
Define the solution
Apply the solution
Validate the result

Now you are probably thinking that this is nothing novel. I'm just using weird words for:

Develop requirements
Design and Code to the Requirements
uhh....Test?
Customer Acceptance Testing

Wrong! Even if you were more creative than me, or pulled out RUP's phases or anything like that. But that's expected, as I rarely see steps 1 and 4 completed. Let me explain. Define the Problem This is where most projects get in trouble. Their problem definitions looks kind of like this:

We need to rollout a corporate standard ERP system.
We need to web-based foo tracking database accessible to the entire corporation.
We need an automated workflow for the bar process.

I could go on-and-on. Sometimes these are followed by phrases like "will save X million dollars" or "will reduce cycle time by X%." Really the problem is someone said that a competitor was saving money by applying an automated workflow to the bar process in order to track foos in the ERP system with a web-based frontend, the company at hand doesn't have one, so that's a problem. Anyway, often times these statements are really masking genuine problems such as:

My old college roommate is an ERP salesmen and wants a new boat
We have a ton of foo, but no one really knows where it is or if it's being used. So we keep on buying more foo, even though we probably have enough. The problem is when we find so foo, the people with the foo always claim that they need all of it, even though often times they clearly aren't using it. We have some data, but it's massive and impossible to interpret. We need a way to find unused foo and prove that it is unused so that we can transfer it where it is needed.
Some cowboys in department X keep on ignoring the bar process. They think they are heros because it saves time and money upfront, but really they just end up creating costly, time consuming problems down the line (for me). I need a way for force them to follow the bar process, but it can't be too hard otherwise they'll convince upper management to let them ignore it.

So why is the difference important? Don't you just end up with the first set of statements as your project charter, anyway? No. A couple months ago I faced a situation similar to the second item. A consultant had (unfortunetly) convinced a couple senior managers that they wanted a big, fancy database integrated to half of our internal systems and requiring a whole bunch of data maintenance. Fortunately the consultant also directed them to me. They had tons of data, and had spent countless hours fiddling with spreadsheets trying to turn it into actionable information. Having failed, they decided they needed a huge database that would cost hundreds of thousands of dollars to develop and then require staff to keep up-to-date. They also needed something in about a couple weeks. So I poked a proded until I finally understood what they needed to know, what data they had, and what they needed to decide based on that data. Then I wrote a few hundred lines a Python to analyze the data and make pretty graphs, along with a couple dozen lines of VBA to stick the outputs of the Python program into a PowerPoint presentation. They were thrilled with the result. Hundreds of thousands of datapoints were transformed into actionable charts that even the most impatient executive could correctly interpret. This took me about 2 weeks effort. Their original requirements would have taken a couple man years effort to implement, and the result would not have solved their problem. Traditionalists would have wasted the time to implement the requirements (which were actually fairly well developed), or at least a portion of them. Agilists would have fiddled around for a while and achieved the same result. Now I'll admit that on the majority of projects it's the other way around. Understanding the problem makes that cost of the solution grow by an order-of-magnitude, rather than shrink. My guess is only 1 in 4 can actually be simplified by understanding the problem, and 2 in 4 become significantly more complex. But solid estimates that can be tied to solid business cases are extremely important. Delivering a cheap solution that doesn't deliver value is a waste of money. In my experience development teams assume that "the customer" or "the business" already understand their problem and are defining requirements that will solve it. When in reality, the problem is usually vaguely understood at best, and the description of requirements is every bit a design activity as coding is. Define the Solution This is where most of the traditional software engineering activities occur. You have a customer (or marketing) who has given you some high level requirements defining the general shape of the system, and then you go about gathering more detailed requirements, followed by architecture, design, code, and test. Or maybe you are agile so you do all of those activities at once and only bother writing down code (in the form of application code and test code). Either way, knowing the problem really helps. Some people probably object to lumping all of these activities under one heading because they take so much time. I would agree, but they rarely done entirely sequentially. Prototyping is every bit as valid of a method for eliciting requirements as interviews. Sometimes it is a lot more effective. Also, there are strong feedback loops among all of the elements. So really, they are all done pretty much at the same time. It just happens that requirements kick off the process and testing finishes it up. Others would object because "the completed system is the solution." Well, no. It's not. You don't really know if you have a solution until after you've deployed and run the system long enough for the business to adjust itself. Apply the Solution This is just another way to saying "deploy," plus all the other things you have to do like training. If you think of it at a really high level (too high for effective engineering), the organization is the problem, and you apply the software to the organization to see if the organization gets better. Validate the Result This is where you measure the impact of deploying the software on the problem so see if indeed the problem has been solved. I don't think anyone will disagree that a piece of software can meet all of its requirements and fail to make a positive impact. So you need to measure the impact of the deployed system. In practice, success is declared as soon as a piece of software that meets "enough" of its requirements is rolled out. This puts the organization in a very bad position, because if the software subsequently fails to deliver value, then the declaration of success and those who made it are called into question. In most cases the organization will just end up either ignoring the system or limping along until enough time has passed to call the system a problem.

More Efficient User Interfaces

2007-07-17T23:08:00.000-04:00

Over the weekend I ran into the following video about changing user user interface paradigms. I found the language based interface really interesting, but didn't much care for the ZUI. Unfortunately, the language based interface reminds me of old games from about the time personal computers became powerful enough to run Eliza-like software (for hackers, go here for code, and here for an easy environment on Windows). Basically you typed in "natural language" commands, and the characters were supposed to carry them out. Personally, I thought it was about the most awful way to play a game. Maybe in the past couple decades technology has progressed. It looks like it has potential. Anyway, the first thing that struck me was it reminded me of SciFi books where they describe any advanced computer use "programming," possibly because I largely stick to classic SciFi. Of course the vast majority computer users, who indeed perform relatively complex tasks, are not progammers. Not by a long shot. But I think the language-based interface concept could bring "programming" one step closer to the masses (whether that is good or bad is an excercise for the reader). The second thing I noticed was a stricking similarity to SmallTalk, only SmallTalk is a lot better. You see, if all of your software was inside of a SmallTalk image, then you could easily interact with it programmatically. Furthermore, SmallTalk's syntax and dynamic nature make it fairly approachable for those who have not been corrupted by years of experience with less lofty languages (in other words, me). Given a "humanized," if you will, object model I could see some real potential. At a minimum it would be a realization of much more componentized software. Alas, we can dream... The paradigm for such a system would be something like this: Someone builds an API that translates human-language like typed commands into Smalltalk code. It could quite possibly be an internal DSL. Then you build the interface so that an easy keystroke let's you "talk" to the computer by typing. AI would be optional, but I think essential for really advanced use by lay users. As time progresses, the user and the computer would learn more and more complex tasks - the user would essentially be programming the computer, but it would feel more like training. Ultimately this could facilitate much more efficient and sophisticated computer use. Maybe. There are counter points. Paul Murphy seems to think that everyone should learn keyboard shortcuts and Unix command-line utilities. While I agree in the utility of both, somehow I don't think the every-day computer user is ever going to do it. The more convincing counter point was made by my wife, an attorney, who wasn't even really trying to make a counter point. The exchange went something like this: Me: I saw this video the other day about changing user interface paradigms to consist of unified functionality instead of distinct applications. Her: Why would you want that? Me: Well, difference applications do different things, and so often times you have to use more than one to get it done. Her: Word is complicated enough already. Wouldn't that make it more complicated? Me: Yeah, that's why this guy advocated switching to text-based commands instead of menus and dialogs and stuff. Her: Huh? Me: You know how Word has a ton of menus, and those have sub-menus, and those launch dialog boxes with a bunch of tabs in them? Her: Yeah. It's confusing. Me: Well, if there were easy text commands that resembled natural language, then you could just tell the computer what to do and not worry about the menus. Her: Wouldn't that mean I have to learn all that? What's wrong with what we've got. It works. I know how to use it. Why change? People won't like the change. It will confuse them. Me: Well, how about intelligent search.... And go on to another defeat of the engineer. But that's the point. We dream of novel new things. We dream of users who care to really learn applications. We get people who want consistency. They've learned it, and they don't want to learn it again. So why is this important? Well, two reasons. One is that people are amazingly hampered by most application. By people, I mean everyone. How many of you have spent hours fighting Word or PowerPoint to get some document to look right? I know I've done it plenty of times. That's wasted time, and time is money. But there's a more important reason. I think we've hit a plateau in terms of technology innovation. We have all this shiny new processing power and networks, and most "innovation" seems to consist of thing like "social networking" (many were doing that a 1200bps or less years ago), sharing pictures (ditto), playing media (replacing TV/VCR isn't innovation), and other such pursuits that while may be very beneficial, hardly represent technology advancements. Why? There are a lot of reasons. I think one of them is that computers are so complicated already that getting a user to accept them doing something complicated is incredibly low. You can do it in specialized fields that have a technical leaning (science, engineering, finance, economics), but doing it for others is another ballgame. In the long run, in order to keep innovating, we have to be able to bring innovative software to people who today do not want it, because what they have today is complex enough. We have to change the user interface paradigm, and we have to do it in a way that doesn't scare people who already "know something" away.

Sun Ray Thin Clients

2007-07-16T22:24:00.000-04:00

Last week I made a comment on Paul Murphy's blog about how the thin-ness of Sun Rays is really up to interpretation. Today he's decided to dedicate an entire blog to explaining why I'm wrong, because he figures if I have an incorrect understanding of Sun Rays, then a lot of people have an incorrect understanding of Sun Rays. He's probably right, although I don't think my understanding is that far off base, and he's been kind enough to let me see a draft copy of his blog so I can get a head start on the response. Here's what I said:

Smart, Thick, Thin, Display
It's all word games. Depending on how you define "processing," there is processing going on. It still has to render graphics, translate keyboard and mouse events, etc. A SunRay is just a compacted Sun workstation of yesteryear without a harddrive and special firmware designed to work solely as an X-Windows server.
The problem is the attempt to make "smart displays" seem more fundamentally different from other similar solutions just muddies the waters. People like me groan because yet another term has been introduced that means almost the same as other terms that will need to be explained to the higher-ups. The higher-ups get confused and either latch onto it or, more likely, have their eyes glaze over.
Anyway, enough with our industry's incredible ability to make sure words are completely meaningless...
The problem with Sun Ray and other similar solutions is that they are really a local optimum based on today's technology and practices for a relatively narrow range of priorities. Change the priorities and the solution is no longer optimum. Introduce distributed computing techniques with the same low administrative overhead and they lose out entirely.

As far as I can tell, the first part is technically accurate. Older Sun Rays ran a 100Mhz UltraSparc II, had 8mb of RAM, and ran a microkernel. See here and here. Newer ones use an even beefier system-on-a-chip.

So the Sun Ray client is obviously processing something, and actually has a fair amount of processing power. Just because it is not maintaining any application state, doesn't mean it's not doing anything. Murph asserts that a Sun Ray is not an X-Terminal, but he'll have to explain the difference to me. He could be right...I don't know. It's been about 7 years since I've used a Sun Ray, but from what I remember it felt just like using Exceed on a PC under Windows, which is quite common at my employer. He did mention this:

Notice that the big practical differences between the Sun Ray and PC all evolve from the simplicity of the device in combination with the inherently multi-user nature of Unix. In contrast the differences between the Sun Ray and X-terminal arise because the X-terminal handles graphics computation and network routing -making it more bandwidth efficient, but marginally less secure.

But the Sun Ray quite clearly has a graphics accelerator and talks over the network, so while there is probably a subtle difference in there that I'm not grasping, it doesn't seem particularly marterial. But that's not really the meat of the debate, it's just a technical quibble over what consitutes processing and an operating system. He's dilluting the debate by calling Sun Ray's "smart displays" instead of "thin clients" and thus drawing a false dichotomy, and I'm doing the same by pointing at internal technical specs that have little to do with actual deployment. The real debate is: "Where should processing take place?" I'll give you a contrite answer - as close to the data as possible. Any computation involves a set of inputs and a set of outputs. It makes no sense to shuttle a million database rows from a database server to an application server or client machine in order to sum up a couple fields. It makes much more sense to do it where the data is, and then ship the result over the network. Likewise, if you have a few kilobytes of input data and several megabytes/gigabytes of results, it makes sense to do the computation wherever the results are going to be needed. So this is my first issue with the centralized computing paradigm. Right now I'm typing this blog in Firefox on Linux, and my computer is doing a fair amount of work to facilitate that interaction with Blogger. I've also got a dozen other Windows open. Most of the memory and CPU I'm consuming is dedicated to the local machine interacting with me, the local user. Only a couple pages of text are being exchanged back-and-forth with blogger. So why not let the Sun Ray run Firefox (and an email client, a word processor, etc.)? The new ones have the processing power. They probably would need $100 worth of RAM or so to keep a stripped-down Unix variant in RAM, which could be loaded from the network. Intelligent configuration could make the client smart about whether to run an app locally, on a server, or on an idle workstation down the hall. Murph gives seven reasons: 1. portability Murph asserts that with Sun Rays you gain portability, because you can halt a session one place and immediately resume it another place. I don't doubt that is true, but I don't see any technical reason why the same could not be accomplished with a distributed architecture. All that happens is your terminal becomes the processing server for a remote application. Remember, in Unix, there isn't a fundamental difference between a client and a server. I'm not going to address the laptop debate right now. Murph has made some very good arguments against laptops in the past based on the security concerns of them being stolen, despite strong encryption. I think he underestimates the value of laptops and is probably wrong, but there are a substantial number of people who could live with a "portable terminal" because their homes and hotels have sufficient bandwidth. 2. reliability This is where the distributed model really shines. In my experience, networks just are generally one of the less reliable portions of the computing environment, especially WANs and my own internet connection. A pure thin-client solution simply stops working when the network goes down. In the past, Murph has asserted that everyone needs network connectivity to work, so this doesn't matter. But in my opinion most professionals can continue working for several hours, possibly at reduced productivity, when disconnected from the network. That buys time for IT to fix the network before the business starts bleeding money in terms of productivity. Keeping processing local, along with caching common apps and documents, increases the effective reliability of the system. 3. flexibility Murph lists nothing that cannot be done with a locally-processing workstation. 4. security Don't use x86 workstations, especially running Windows. The security gains are from a more secure operating system on a processor architecture designed for security and reliability. Eliminating permanent storage from the client does buy some security, because there is then no way to walk out the door with all the data, but distributed processing doesn't preclude centralized permanent storage. There are, of course, substantial advantages to having local storage, like being able to make a laptop that can be used in an entirely disconnected fashion. But I think that's a separate debate. 5. processing power There's nothing about a distributed computing model that says you can't install compute servers. Heck, this is done all the time with Windows (both to Windows servers and more commonly to Unix servers). Murph's example of a high-performance email server has nothing to do with the thin-client architecture, and everything to do with properly architecting your mail server. 6. cost There aren't significant cost savings in terms of hardware when switching to Sun Rays. Hardware is cheap, and you can throw out a lot of pieces in the common PC to reduce the cost. In fact, I bet Sun Rays cost more because of the servers. I don't doubt that when effectively administrated they cost less to keep running than a Windows solution, but that's mostly because of Unix. I'll admit that it is probably cheaper to administer Sun Rays than my distributed model because I think it will require greater skill and discipline (meaning higher paid admins), so in abscense of detailed numbers I'll say it's a wash. 7. user freedom This is partially a consequence of using Unix instead of Windows, and mostly a consequence of changing culture. So as I said before, Sun Rays, and centralized computing in general, represent a kind of a local optimum for a given solution and today's practices. But I don't think they make a solid generalized approach. Distributed computing can be successfully with all the advantages of Murph's Sun Ray architecture using today's technology, it just isn't common. Now I've ignored the elephant in the room: Much essential software only runs on Windows, and the minute you introduce Windows into the mix (local or centralized), you start compromising many of the advantages outlined above. Of course, what good is a computing environment if it won't run the desired software? Consequently, I think it will be a long time before anything like this flies in most enterprise environments.

Creators, Hounders, and Processors

2007-07-02T09:47:00.000-04:00

There are three types of people in a corporate environment:

Creators
Hounders
Processors

These are really a continuous spectrum, and people can occupy more than one location on the spectrum, but I think those are the large buckets into which most people fall. I'm very tempted to say that creators are the people who produce most of the value, but that probably would be my creator-self talking. Creators are the people who create something of value from almost nothing. They are the engineers, scientists, researchers, and marketers who create the ideas that advance an organization. They are both the most coveted and most annoying employees, and generally compse a very small percentage of an organization. Within an IT organization, creators tend to be architects, analysts, and software developers; although most people in those roles aren't really creators. I'll talk about hounders later. Processors are the people who take something, apply some known method to it, and spit out something of greater value. In law, a litigator is most likely a creator. The guy who puts together your will is a processor. A processor's job is to keep things neat, complete, well organized, and most of all conformant to any important rules and regulations. Without processors we would live and work in total chaos. Processors are the people who take the mess produced by creators and turn it into something that is geniunely useful and widely appliable. They are the people who continually apply it so that is becomes part of our lives. In IT, QA people, system administrators, database administrators, application administrators, configuration managers, help desk staff, and countless others are generally processors. Management often wishes everyone (except them) could be a processor, because they are predictable and their work usually has immediately apparent value. Processors make up a very large portion of most organizations. So creators like shiny new things. They hate forms and anything else that seems to constrain their ideas. They only really believe in deadlines for other people, because creativity cannot be hurried, and often times even have trouble pushing deadlines on others because the last thing they want are half-baked ideas. They don't want to be bothered with the extraneous details required by processors. Processors often claim to believe in deadlines, and to be very predictable in the time it takes to process work. However, they exclude from this time they spend waiting for responses that the need from others. If you don't believe me, go see how many help desk tickets your IT organization has that are in a state like "waiting for user response," quite likely to a question like "Is your computer plugged in?" The result is processors are only concerned about deadlines when they can't blame someone else, and creators are prima donnas who can be bothered neither by deadlines nor by a processor's need for additional information. Consequently creators are the perfect scapegoat for processors (he hasn't responded to my email asking for more information), and processors for creators (I sent it to him last week, what do you mean he needs more information? I'm busy. It's his fault this is late, not mine.) Now enter hounders to solve this problem. They exist to overcome the impedance mismatch between creators and processors, and they may be as numerous as the other two groups combined. Salespeople are all hounders. Most managers are hounders. Everyone who emphasizes (or randomly inserts) the word "manager" in their role or title is a hounder. Hounders are the people who constantly talk about action items and religiously send out meeting minutes. They are also often the people who lack the technical skills to be creators and detail orientation to be processors. Just like you need some bacteria in your body, you need some hounders in your organization. But too many is a sign that your organization is diseased, as most don't directly produce anything. Also, without day-to-day observation, it can be very difficult to distiguish a hounder from a creator or processor, because they tend to confuse (intentionally or otherwise) making somebody do something with doing it themselves. And they tend to make organizational problems worse. Often times if the creators and the processors are having a really hard time communicating, it's because one or both sides has been allowed to become too extreme. When processors get in trouble, their first instinct is to create more rules for getting tasks out of their queue and off their clock. Creators, when they get in trouble, tend to avoid disclosing details, especially when they aren't yet sure of them. Consequently, all the hounder has to do is encourage these behaviors, and the hounder becomes (in the short term) more critical to the organization, because now the only place the processor can get his details is from the hounder, who either tricks the creator into providing them or takes responsibility for any problems that may arise. In extreme circumstances, processors may even stop communicating with other processors, by simultaneously declaring items in each-others' queues, making hounders necessary to make what should be a smooth interaction work. All three types are needed in any organization. When properly balanced they compliment each other. I've picked on hounders here, because I think they are the most opportunistic, but creators and processors can be quite detrimental as well when they gain too much influence. P.S. Now, you might be wondering what happens to the people who lack the technical skills and creativity to be creators, detail orientation and technical skills to be a processor, and the personality to be a hounder. Some fake it, usually by obscuring their lack of skill or creativity, for example by parroting something they heard/read or calling "buy IBM" an IT strategy. It's amazing how smart a person will think you are if you consisntely agree with them.

Random thought on functional programming

2007-06-27T00:06:00.000-04:00

Right now I'm trying to learn Scala and functional programming, particularly not using any mutable state. I'm going cold-turkey on mutable state. It's hard. I've noticed a few things:

It takes me forever to work out functions that build collections despite the fact that I can clearly envision to mutating-version of the algorithm
Once the functions actually compile, they tend to "just work," or at least any flaws are design flaws, not simple coding mistakes. This is very much like the Python experience, only it takes longer.
The functions continue to work, unlike the Python experience where a combination of edge cases and type errors generally crop up as the complexity of inputs increases

I'm not sure if this means I'm more or less productive. Right now I'd say probably not, but maybe I'll learn to "think functional" and stop thinking in terms of how I would mutate a collection to make it what I want.

Erik Engbrecht's Blog

Martin Odersky's Scala Levels

Learning Python

Learning Scala

Summary

Types of Project Failure

Subjective Objective Failure

Value Failure

Collateral Damage

Back to Trading Among Failure Types

StackOverflow and Scraper Sites

Analysis

Conclusion

Easier object inspection in the Scala REPL

So what exactly is an attribute?

Playing with Scala Products

Basic Usage

Dealing with Inheritance

Wrapup

Scala is for VB programmers

Scala Actors: loop, react, and schedulers

Concurrency Benchmarking, Actors, and sbt tricks

Custom sbt actions for benchmarks

Important variables

Improving Schedulers for High-level, Fine-grained Concurrency Frameworks

Empirical Evidence of the Problem

The Scope of the Issue

Key Characteristics of a Good Scheduler

The Performance Problem

ForkJoinPool in a nutshell

A Crack at Solving the Problem

Conclusions

Is the Market for Technical Workers a Market for Lemons?

What's a Lemon Market?

The Lemon Market for Technical Talent

What Technology Professionals can do

What Employers can do

Is there any hope?

But what about old fashioned networking?

Higher-Level versus Higher-Order Abstraction

What is an abstraction?

Higher-level Abstractions

Higher-Order Abstraction Take 1: The Mathematics of Fruit

Higher-Order Abstraction Take 2: Programming in Scala

Higher-Order Abstraction Take 3: Conclusions

Windows 7 Upgrade (so far)

Changing Tastes

Your Company's App

Pondering Actor Design Trades

Guarantees

Expressivity

Extensibility

Performance and Scalability

Parting Thoughts

I'm on Twitter!

Refactoring Scala Actors: Progress Update

State-machine Based Actors

Reworking MessageQueue

Fixing Schedulers

Closing Matter

McKinsey and Cloud Computing

Refactoring Scala Actors: Rethinking the Approach

Profiling the ExceptionBlob

Scala Actors versus the ExceptionBlob

Standard Actor loop

State-based Actor loop

Standard Actor recursive react

Actor States recursive react

Actor States reactWhile

Parting Matter

Google is Paranoid

Refactoring Scala Actors

Countdown to the U.S.S.R.

Languages Readability and Tool Support

The Costs of Generality

The General Solution

Generate Only Valid Permutations

Accumulating Numbers Instead of Lists

Long Set without Boxing

Special Purpose Set for Permutation Generation

Standard Actor `loop`

State-based Actor `loop`

Standard Actor recursive `react`

Actor States recursive `react`

Actor States `reactWhile`