Eager Future

I just put up the common-lisp.net project page for Eager Future, a library for concurrent programming with composable, eager futures (see this LtU discussion of what that means).

Eager Future is a rewrite of Marijn Haverbeke's PCall library (I've blogged about PCall and extending it with support for composition before). Unlike PCall, Eager Future executes futures eagerly, which lets you use the futures composition mechanism for soft real-time programming.

Gelernter

Two years ago I posted a review of Nicholas Carriero and David Gelernter's How to write parallel programs. Today I came across an Edge roundtable discussion with David Gelernter (via Patrick Logan).

The entire discussion is fascinating, and I recommend reading up more on Gelernter's work if you are not familiar with it before watching the interview.

For me, there were three new insights from the roundtable:

• Message passing is the assembly language of distributed systems.


• Databases are a way to communicate through time. Networks are a way to communicate through space. Both are symmetrical. The point of Linda was to unify them.


• The most powerful computers today are botnets. Botnets are also on the leading edge of distributed systems techniques.

In the second video, Gelernter discusses Lifestreams. It's amazing how closely FriendFeed, Twitter, and the new Facebook are all following the roadmap established by Lifestreams over a decade ago.

Parenscript tricks and parallelism

The new version of Parenscript features a user-definable obfuscation facility. Among other amusing things, it can be used (due to JavaScript's under-utilized support for Unicode identifiers) to make your code Asian:

(ps:obfuscate-package "LAMBDACHART"
  (let ((code-pt-counter #x8CF0)
        (symbol-map (make-hash-table)))
    (lambda (symbol)
      (or (gethash symbol symbol-map)
          (setf (gethash symbol symbol-map) (make-symbol (string (code-char (incf code-pt-counter)))))))))

LAMBDACHART> (ps (defun foo (bar baz) (+ bar baz)))
"function 賱(賲, 賳) {
    賲 + 賳;
};"

Unrelated, I recently found Marijn Haverbeke's PCall library for parallelism in Common Lisp. The library provides futures (called 'tasks') as parallelizing mechanism, and thread pool (the library is based on bordeaux-threads) management facilities to tweak how the futures are actually executed.

Unlike MultiLisp, which implemented the same futures-based parallel model, there is no macro provided to evaluate a function's arguments in parallel before applying the function to them. That seemed to be a popular facility in the parallel research Lisp systems of the 80s, probably because it is a no-brainer once you consider the Church-Rosser theorem, however upon some reflection and a little coding that construct proves to be not very convenient.

I think the futures approach to parallelism is the most widely useful model available today. It shares all of the conceptual benefits of its cousin delayed/lazy evaluation: futures are declared and used explicitly in the code, without forcing (pun fully intended) any contortions in the control flow of the code using those futures. If you can write a function, then you can define a task that can be executed in parallel.

The model doesn't handle concurrency control beyond the synchronization provided by joining/forcing the future, so if your tasks share state (although you should be writing your code to do the synchronization in the code making and consuming the tasks, so that they don't share state), you'll need to do the synchronization yourself (this is where you take advantage of locks provided in bordeaux-threads).

One interesting thing about the library is Haverbeke's extreme pessimism about native thread overhead (the default thread pool size is 3). On many systems that is certainly justified, but apparently some half-decent OS implementations exist. I'm interested in doing some benchmarks with SBCL using NPTL threads on an AMD64 box to see what kinds of numbers are reasonable.

Memory doubts

Patrick Logan recently posted a note expressing misgivings about the promise of transactional memory:

I can see someone making the argument in some domain I don't usually work in that shared memory threads are better than shared nothing message passing for performance reasons. Some hard-real time scenario (I think I was real tired when I wrote that. Must have been thinking back to the days when I'd get into "Is automatic garbage collection practical?" debates. Nobody has those anymore, do they? Because I've got some real good arguments for GC.), some huge number crunching scenario, etc. where every byte and every cycle has to count in the extreme. But the irony then is that STM seems far more suited to a language like Haskell, which is also unlikely to be suited for these performance scenarios.

My only fear is that for the masses including myself, we need *simple* mechanisms, and the fewer of those, the better. Shared nothing messages seem to scale up, out, and down. STM seems more complicated, and an incomplete solution, and only a solution for shared memory. No thanks, at least until bigger brains than my own can show me why I should change my mind. They seem sidetracked on this one.

With regards to transactional memory, the "performance argument" doesn't even need to be brought up - the second biggest objection to transactional memory (the first being that it is different than what's currently being used), is that even in the best case of no contention, there is a large overhead penalty imposed versus code using manual synchronization. Of course in the worst case you would have to throw out a whole bunch of transactions' worth of work and start again.

When it comes to scalability, transactional memory is just as limited as any other kind of transactional system. Published benchmarks already show a performance plateau on some of the larger Sun servers, and those have less cores and probably a much lower CPU-speed to memory latency (and bandwidth) ratio than any kind of upcoming 80-core Intel chip.

If anything, out of all available approaches message-passing is by far the fastest that can be implemented. Cache-coherency protocols introduce delays and seriously limit scaling in the number of processors in an SMP system, and even atomic instructions are so expensive that I've heard the overhead means that some of the lock-free datastructures currently being worked on don't perform well compared to the lock-based ones they are supposed to be replacing.

However, I would not by any means call transactional memory complicated. In fact it is the easiest approach to concurrency available for those who are used to traditional imperative programming. This is by no means a good thing, since without needing to understand concurrency people will inevitably write "concurrent" programs that won't scale or worse (it's not too hard to imagine a transactional system where performance suddenly drops off a cliff when you add processors because transactions are now being aborted all the time).

A final comment I want to make is to go back to considering objection #1 to transactional memory. While the state-of-the-art in distributed systems research is advancing well, the state of experience in actually implementing them is lagging much further behind, to the point where many people have a very misguided view about what's hard and what's not in programming distributed systems. This applies even to those doing the former, since most distributed systems researchers simply don't have the time to do anything but research (it's a very exciting time for the field, and large rewards will go to those who publish first). This was illustrated in an incident a while ago where a research professor in the field whose work and talents I otherwise highly respect told a class that message passing was too difficult for programmers and that they would prefer to use locks and semaphores to program, so how can we implement those in terms of the former? Of course I had to object. I suspect there are and will be a lot of similar arguments repeated over and over, and the familiarity card will be brought out again and again.

If someone does it to you, point out the fact that out of all software, only a very small amount is written with lock-based concurrency, and out of all those programs, only an insignificant percentage is actually written to be real parallel software (as opposed to multi-threaded GUIs and network servers). In this case, the familiarity card is really worth far less than it seems.

Software Transactional Memory

I promised in an earlier post to discuss software transactional memory, so today I've decided to present a paper written by Andrew Seniuk and me for Lisa Higham's distributed algorithms course. The contains an overview description of STM, discusses implementation approaches of a few current systems, provides proofs of several properties of the DSTM implementation, and highlights possible pitfalls that can occur in transactional code. During the time Andrew and I were working on the paper, there was a lot of excitement in the blogosphere of the potential of STM, and I think it is important to highlight the problems that will be encountered when use of software transactional memory gets more widespread - both to help people avoid them, and to deflate some of the "silver bullet" hype that I think STM has received. Enough rambling, here's the link to the paper:

http://vsedach.googlepages.com/stm561.pdf

How to write parallel programs

I recently finished reading through Nicholas Carriero and David Gelernter's How to write parallel programs (available free online), a hidden gem on parallel computing published in 1990. Most books about distributed and/or parallel computing that I've come across are banal junk (no, no one needs another book about MPI) - How to write parallel programs contrasts sharply.

I suspect a major reason why parallel programming is considered difficult today is that most people don't have any conceptual feel for the space of possible parallel problem-solving approaches. Most educational material presents a fragmented view of models and paradigms; the vast majority of books focus on a single system or approach. The majority of programmers, not having delved into the breadth of the parallel computing literature, simply are not aware that there exist alternatives that may make their parallel problem-solving tasks much easier.

In light of this, the key insight of How to write parallel programs is distilling parallel programming into three distinct, conceptual paradigms for coordination in parallel problem-solving. It may come as a surprise (I promise I won't provide any more spoilers) that DCOM, CORBA, RMI or any other object-oriented "remote method call" junk is not one of them. Which brings me to a tangent where I rant about the whole idea of "remote method invocation" being beyond stupid by managing to get both message-passing in object-oriented programming and the basic assumptions about distributed systems completely wrong. More people should listen to Deutsch and Kay.

How to write parallel programs is intended to be a textbook, and that means algorithm analysis, which frequently leads to surprisingly practical insights about distributed systems, such as load-balancing considerations, dealing with IO bottlenecks, and even using time complexity analysis to (inadvertently) find faulty nodes. Examples are written in C-Linda (an implementation of Gelernter's tuplespaces). Following the arguments and doing the exercises is well worth the time.

I'm going to end this post with a request for help from the readers: I am trying to track down a copy of a paper referenced in the book: R. Abarbanel and A. Janin. Distributed object management with Linda. Research report, Apple Computer, Cupertino, CA, September 1989. If someone has a copy or can obtain one (any old-school Apple employees reading this?), please get in touch.