Moonbase

Just a quick note that I’ll be making an appearance on tomorrow night’s Linux Link Tech Show at 8:30PM Eastern Time.

I’ve noticed lately that some web application frameworks seem to encourage the practice of automatically putting database transactions around view/controller execution. This may seem like a convenience, but it encourages precisely the wrong way of approaching transactions— at least if your application ever does anything else besides interact with the database. Yes, you’ll want to use transactions when your views or controllers are using the database, but in some cases having a transaction over the entirety of view/controller processing is far too coarse-grained.

See, there are two basic principles to bear in mind when working with a transactional store:

1. Minimize transaction size and length.
2. Avoid performing non-transactional IO during a transaction.

Minimizing transaction length not only saves resources, it also improves throughput and reduces the likelihood of creating conflicts with other transactions.

However, you do also need to be prepared for the case where conflicts occur. I see an awful lot of code out there which assums that transactions always succeed, and this is dreadfully wrong—if there is writing going on, you basically always need to be prepared for the possibility of a transaction being aborted due to a conflict.

In many cases the appropriate way to recover from a conflict is to retry the aborted transaction after a short delay; repeated conflicts are typically typically with some kind of exponential backoff and a bit of randomness introduced to keep retrying transactions from butting heads too much.

And retrying is one place where the second rule comes in: if you did a whole bunch of non-repeatable IO during the course of the transaction, then you’ve pretty much just screwed yourself.

I’ll give an example of what I saw yesterday which got me thinking about writing this post:

A web application was set up to automatically put a database transaction around each request. One of the functions of this web application is to accept browser file uploads, updating some bits in the database before and after the upload takes place. A consequence of this is that the application would have a transaction held open for the entire duration of the upload—which could be minutes or even hours. This ties up resources associated with the transaction, creates the potential for other transactions to block (to the extent that pessimistic concurrency control is used by the database), and lastly creates a great deal of potential for update conflicts to occur.

And at that point, what happens if the transaction does fail? Since an upload transaction included reading the entire file from the browser, we can’t easily retry it: the browser is only going to send the file once.

The correct solution in such a case is to use multiple, finer-grained transactions during the course of processing the request. Those transactions would be shorter-lived than a mega-transaction spanning the entirety of view/controller processing, are less likely to provoke update conflicts, and can be individually retried when conflicts do occur.

So I’ve been getting mail to the effect that Ruby 1.8’s concurrency primitives are still all screwed up even as recently as 1.8.6p111, and that fastthread is consequently required to get things to work reliably.

I find that really frustrating, as I was hoping that once fastthread was merged with 1.8 as the new thread.rb, I could get out of the fastthread business altogether and rely on the 1.8 maintainers to deal with it, but unfortunately things don’t seem to have worked out that way.

I think what I may do this point is re-enable fastthread for all 1.8 versions, and hope that Ruby 1.8, as a Ruby implementation, goes away sooner rather than later.

I’ve been plugging it elsewhere, but I’m really enjoying multi-instrumentalist Sophie Madeline’s album LOVE.LIFE.UKULELE, and I figured I should give it a plug here. It’s the sort of quirky, poignant thing that I really get into. You can listen online at the above link, and bandcamp also has an option to purchase high-quality downloads at a price of your choosing.

Also, here’s an interview with Sophie, complete with bonus song. And her single The Stars.

fastthread has pretty much outlived its usefulness at this point; it is no longer really necessary on the most recent versions of Ruby 1.8, and things depending on fastthread is actually a hinderance on JRuby and Ruby 1.9 and so forth. A number of gracious people have contributed patches to make fastthread installable as a noop package on those platforms, and before that I actually prepared fastthread 1.0.3 last June, but it was never packaged.

Worse, Mongrel’s SVN also appears to have lost the revisions I originally pushed to it (which I know I did, because the revisions had git-svn revnos). So, I’ve put fastthread up on github and have released 1.0.3 myself.

I’ve been away from blogging for a while due to various life complications and other commitments, but I’m back now, and I’ve got quite a bit to write about.

Watch this space.

For you.

BAMAN PIDERMAN

Interview with Dali

(Both these gems are by Alexander Butera; I hope we get to see more from him in the future!)

I don’t have a whole lot to say about science blogger PZ Myers’ public desecration of an allegedly consecrated host. I think it is fair to take him at his word that he does not seriously entertain the idea that a piece of bread could by divine fiat become the Body of Christ (which brings to mind Christ’s response the first time people started sticking nails in it ). In any case, that much is between him and God, and I generally wouldn’t expect a non-Catholic to have a Catholic perspective on the issue.

What I do hope most people would recognize is the basic immaturity of the act, even from a strictly secular point of view: in such terms, it’s akin to a grade-schooler taking from another child the special sandwich the child’s mother had prepared for him and grinding it into the dust because it was “stupid”. Of an adult academic, such an act would suggest an exceptionally poor standard of public behavior. That Myers’ act was carefully premeditated, and that the intended recipients of the Eucharist place an even higher value on it, that only makes that issue worse.

I realize that Myers had taken it upon himself to act in retaliation for threats made by a few of my co-religionists in an unrelated Florida incident. But if certain people are acting like vindictive children, an adult response does not mean similarly immature behavior, and an adult response most certainly does not mean taking it out on an entire religious group.

Update: Based on the replies I am getting, it seems that there are four issues which I need to clear up.

First, Myers (at least if his own claims are to be believed) didn’t simply obtain a wafer of the same sort of bread which is used in Catholic rites (which, absent any confusion, nobody would really care about), he specifically sought out a wafer that had actually been in the posession of the Church and had been consecrated by a Catholic priest.

Second, there isn’t a legitimate way to remove a consecrated host from the Church’s custody. The Church does not relinquish custody of a host distributed at Mass until it has actually been eaten. To this end, Catholic churches train their staff—ushers, priests, deacons, and extraordinary ministers—to observe and ensure that the consecrated hosts distributed are consumed on the spot as intended (even if, as this incident shows, they are not always adequately vigilant).

Third, even if the removal of the host in this case might have constituted petty theft (or grand theft, if the “buy it now” price on that one eBay auction is indicative of the monetary value of consecrated hosts), I’m deliberately avoiding legal considerations. From a simple, human, secular standpoint, the basic issue is that it’s inappropriate for a mature adult to take an article of extreme sentimental value to its intended recipients and destroy it in public as a deliberate act of spite.

Fourth, the original threats Myers was retaliating against were directed at a kid in Florida, not him personally. Professor Myers read about this in the media like the rest of us, and decided to take it upon himself to strike a blow for … something. (As far as I can tell, his two main accomplishments so far have been to provoke some of the same morons to start sending him threats, and to offend an awful lot of uninvolved Catholics.)

I think this article can speak for itself:

The military trainers who came to Guantánamo Bay in December 2002 based an entire interrogation class on a chart showing the effects of “coercive management techniques” for possible use on prisoners, including “sleep deprivation,” “prolonged constraint,” and “exposure.”

What the trainers did not say, and may not have known, was that their chart had been copied verbatim from a 1957 Air Force study of Chinese Communist techniques used during the Korean War to obtain confessions, many of them false, from American prisoners.

...

“What makes this document doubly stunning is that these were techniques to get false confessions,” Levin said. “People say we need intelligence, and we do. But we don’t need false intelligence.”

...

The only change made in the chart presented at Guantánamo was to drop its original title: “Communist Coercive Methods for Eliciting Individual Compliance.”

Apple’s announcement of their Grand Central technology sounds interesting, but it’s pretty light on details. Here’s my wild guess, based on the intersection of what they’ve hinted at and what I would do if I were in their shoes: my guess is that they’re integrating support for fine-grained scheduling (as in e.g. TBB) into the OS scheduler, which would enable smarter global decisions about things like work balancing and cache warmth.

Think M:N threads with better kernel support, but minus the usual attempt to make the “userspace” portion of the scheduler preemptive. If they’re smart, they’ll also include non-blocking/asynchronous equivalents of standard blocking APIs, though in principle with sufficient kernel support they could also permit tasks to use some blocking operations in more transparent ways.

I guess we’ll see how good my guess was in a year or so.

The Museum of RetroTechnology is a compilation of various “steampunk-type” technologies which were or are in use in the real world.

(Hat Tip: Nathan)

(On YouTube)

The Rebellion Within is a long but really fascinating and somewhat surprising look at the origins and recent development of Jihadist organizations since the 1970s.

(Hat Tip: Tim Bray)

There was a lot of buzz about WiiWare on the message boards when it first came out, as if it were something with a low barrier to entry comparable to, say, Microsoft’s XNA.

It’s not, okay guys? WiiWare is just an alternate distribution channel for Wii games, complimenting pressed discs in stores. Since WiiWare games are necessarily smaller in scope and the distribution mechanism doesn’t involve the same financial commitments as discs, Nintendo will certainly approve titles for WiiWare that wouldn’t be worth their while to approve as a UPC to go on shelves, and perhaps will also be willing to take a little more risk with developers who have less proven experience, but that’s about the extent of the difference to regular Wii development.

That said, if you’re an indie game development company leasing commercial office space, with some published titles under your belt (or at least a wildly popular flash games site), and for some inexplicable reason you managed to get that far without knowing where to look for these things, the Nintendo SDSG has a list of requirements and an application form posted on their website.

I hope that helps clear up any confusion.

Harley Davidson supposedly puts a lot of care into the sound of their motorcycle exhaust systems. What if a Harley exhaust system or three were rigged to a pipe organ to supply the nice low notes you can’t normally get?

My brilliant friend Nathan took some time to simulate the result using the Aeolus organ simulator to record a performance of BVW540 (a Bach Toccata and Fugue in F Major) using the “Harley stop”.

After Andrea O. K. Wright’s wildly popular (popular as in she had to schedule a second session after the first one literally overflowed with people) RailsConf talk it seems like now is a good time to give an update on my plans for the Omnibus Concurrency Library, especially after I’ve neglected it for so long.

At this point, the next version of the library is likely to be a complete rewrite, licensed under an MIT-style license similar to Rubinius’. It will aim to support at least the following Ruby implementations, with others following as time and interest permit:

• Ruby 1.8
• Ruby 1.9
• Rubinus
• JRuby

Portability

Presently, only JRuby presents opportunities for improved parallel performance with Omnibus’ thread-centric implementation; under Ruby 1.8, 1.9, and Rubinius, performance will necessarily be equal to or less than single-threaded performance. Why support them at all? There are two main reasons:

The first reason to support green-threaded Ruby implementations is for the sake of portability, allowing the same program that runs under JRuby on a multi-core behemoth from Sun to scale all the way down to a single-CPU machine running Ruby 1.8 with its green threads.

Secondly, concurrent programming abstractions are often convenient ways to structure programs even on single-processor systems. (If they weren’t, nobody would ever bother with Ruby 1.8’s green threads.)

Additionally, the concurrency picture for some of these Ruby implementations is not necessarily bleak in the long-term: Rubinius already permits taking advantage of multiple threads per process in separate VMs. A future version of Rubinius may offer more fine-grained multicore support, and a future version of Omnibus may find ways to exploit things like the existing per-VM multicore support, or even include support for fork-based parallelism for some purposes.

Organization

Rather than Omnibus remaining a monolithic library, I’m also going to be breaking things up in order to enable individual components to be released as separate gems (and hopefully in a more timely fashion):

• concurrent – “omnibus” gem which pulls in the others as dependencies
• concurrent-actors – Actors for Ruby
• concurrent-futures – Futures for Ruby
• concurrent-joins – Join calculus for Ruby
• concurrent-parallel – Parallel algorithms and parallel extensions to core/stdlib classes (corresponding roughly to TBB parallel algorithms)
• concurrent-primitives – Grab-bag of simple primitives like channels
• concurrent-selectable – Semaphore and a few other primitives which can be waited on using existing event-based IO libraries, or just IO.select (DONE)
• concurrent-sequential – Force strict sequential execution of asynchronous tasks, even in the face of multiple threads or reentrancy. Don’t laugh, it’s useful.
• concurrent-tasks – Task-oriented parallelism (similar to TBB tasks)

Major Changes and Incompatibilities

One of the major changes coming is that the library will handle asynchronous tasks (e.g. from futures, or joins) by dispatching them to a TBB-like task scheduler instead of simply spawning a new thread for each task. In most cases this means that the creation of continuation tasks is the preferred alternative to blocking, although there will still be provisions to support blocking tasks. The largest effect of this change will be the elimination of transparent futures from the core library, since they have the effect of causing arbitrary tasks to block, and have consistently been the most difficult feature of the library to implement portably anyway.

There will also be some less drastic, but incompatible, changes to the rest of the existing APIs. In particular, parallel algorithms will take grain sizes rather than a count of threads to spawn, and the actor API will be modified to match the current Rubinius API more closely.

Timeline

Especially since Omnibus is a spare time project for me at the moment, I can’t commit to a timetable for the new release, but at the moment I’m aiming to have the new release out in 2-3 months. Watch this space.

(Incidentally, feel free to contact me if you’re interested in funding some aspect of Omnibus development. I am committed to finishing Omnibus regardless, but obviously paid projects have to take precedence.)

I’ve been meaning to blog this for a while…

Tony Arcieri and I devised an object protocol that any object acting like an actor in Ruby ought to implement in order to interoperate with our actor implementations. It is implemented, more or less, in both Revactor and the Rubinius actor implementation, and I plan on refitting Omnibus actors to satisfy it as well.

(Interoperate, here, means simply to be capable of receiving messages from any code which observes this protocol, and also having the ability to participate in linking and supervision tree relationships with other objects implementing the protocol. Protocol is meant in the Smalltalk sense of the term, which is essentially a “duck type”.)

Anyway, here is some pseudo-Ruby sketching out the protocol in all its glory. It consists of four methods:

protocol Actor
  # Submits the given message to this actor's mailbox.
  #
  # Messages submitted to a dead actor are silently ignored.
  #
  def <<(message) ; end

  # Notifies this actor that other_actor has linked with
  # it.  It represents "half" of the linking process,
  # merely instructing this actor to add other_actor to
  # its set of linked actors if it has not already been
  # added.  In order to link two actors (we'll call them
  # a and b), an actor implementation should perform:
  #
  #  a.notify_link(b)
  #  b.notify_link(a)
  #
  # If an actor receiving a link notification is dead,
  # when its implementation permits it should respond
  # to other_actor's link attempt by calling:
  #
  #   other_actor.notify_exited(self, reason)
  #
  # (See the description of notify_exited for
  # discussion of exit reasons.)
  #
  # Aside from dead actors responding with exit
  # notifications every time, notify_link should be
  # idempotent:  repeated attempts to link the same
  # actor should have no additional effect.  An actor is
  # either linked or it is not; there is no notion of
  # "link count".
  #
  def notify_link(other_actor) ; end

  # Notifies this actor that other_actor has unlinked
  # from it.  It represents "half" of the unlinking
  # process, and merely instructs this actor to remove
  # other_actor from its set of linked actors if the
  # set of linked actors currently contains it.
  #
  # Similarly to linking, an actor implementation
  # should perform unlinking as follows:
  #
  #  a.notify_unlink(b)
  #  b.notify_unlink(a)
  #
  # Unlike link notifications, an unlink notification
  # sent to a dead actor has no extra effect.
  # 
  def notify_unlink(other_actor) ; end

  # Notifies this actor that other_actor has died, either
  # by exiting normally or as the result of an error.
  # If the dead actor exited normally, reason should be
  # nil, otherwise it should be an object which
  # stringifies to a description of the error (often an
  # Exception object, but even a simple string is
  # allowed).
  #
  # When an actor dies, it should call notify_exited on
  # all of the actors linked to it *at its time of death*
  # in order to notify them that it has exited.
  #
  # How an actor responds to the reciept of an exit
  # notification is outside the scope of this protocol,
  # although it is suggested (not required) that the
  # default behavior be for the receiving actor to
  # terminate itself, as that is most useful behavior
  # for implementing supervision trees.  However, it
  # is permissible for implementations to ignore exit
  # notifications.
  #
  # Exit notifications sent to an actor that is itself
  # already dead should always be silently ignored.
  # 
  def notify_exited(other_actor, reason) ; end
end

Beyond that, the protocol places no requirements on the scheduling or concurrency properties of the actor represented by an object implementing this protocol—it need not even be an actor in the usual sense.

atomic_ops is a library of portable primitives for building lockfree multithreaded programs in C, by Hans Boehm of libgc fame. The basic atomic operations portion of the library is MIT-licensed, although it also includes a GPLed addon library which provides nearly lockfree stacks and a lockfree malloc implementation.

Update: Hans Boehm wrote to say that the older distributions are to be avoided in favor of the copy of the library in the libgc tree, which he has been keeping more up-to-date. It is available from libgc CVS at:

:pserver:anonymousbdwgc.cvs.sourceforge.net:/cvsroot/bdwgc/libatomic_ops-1.2@

libatomic_ops also appears to be available in many Debian-based distributions as libatomic-ops-dev, in a version based on the last official release but with a lot of additional patches.

(This is a follow-on to my post The Adobe Flash Player Deadlock)

I’ve been very pleased to see that, after my original post on March 9, many of my criticisms have been addressed, and I’ve learned that some were simply founded on poor communication. Let’s run through some of them.

Criticism: There is no way for the general public to report flash player bugs.

Originally, your options for reporting bugs were posting comments on a certain blog, or filling out the Adobe feature request form at http://www.adobe.com/go/wish. The blog wasn’t particularly encouraging since few of the issues raised there got addressed or even received a positive response (I’m also not linking to the blog because towards the end the exchanges between frustrated Linux users and a beleaguered Adobe project manager make both sides look needlessly bad).

I had also not been aware of the wishlist form as an accepted avenue for reporting bugs, but the current version of the page makes that a little more clear and easier to find in a search on Adobe’s site. However, the wishlist form still isn’t very ideal. Rather than a black hole to send “wishes” into, I’d really been hoping for a public bug tracker where you can actually see the fate of your problem report. Even Sun, in their most obnoxious days, had such a thing for Java.

Thankfully, as of April 8, Adobe finally has a public bug tracker for flash: http://bugs.adobe.com/flashplayer.

This criticism is now completely addressed.

(Many thanks to Marnen for filling me in on this point.)

Criticism: Adobe is not devoting sufficient resources to the Linux Flash player for it to remain viable.

I had based this criticism on Adobe’s public statements and history so far. After an initially promising release of Flash 9 (Linux Flash had previously languished buggily at verison 7 for an extended time), subsequent Flash 9 releases were increasingly infrequent and full of new regressions. Adobe was supposedly going to make a big push for Linux with the release of AIR, but when Adobe actually released AIR 1.0 in February, they omitted support for the Linux platform since (according to the AIR FAQ at the time) they had to “wait on the core Flash Player’s support for Linux to be finalized.” All these things together painted a very ominious picture for the future of Flash on Linux.

On March 30, however, Adobe released an alpha version of AIR for Linux, showing that they were making a serious effort to support the platform. I suspect that the reason for the falloff in Flash 9 support is the result of Adobe reallocating programming resources to Flash 10/AIR, although it would be nice if Adobe publicly announced their plans the same way that they did for 64-bit Photoshop, so people wouldn’t be left to conclude that, absent released software, they didn’t have any serious plans at all.

This criticism is probably unfounded to the extent that Adobe is doing the best they reasonably can as long as they are not accepting outside help by opening development of their own player (which itself would require a significant initial investment of resources that Adobe may not have).

However…

Criticism: There is no finalized release of the Flash player for Linux which is stable enough to use for development work.

It’s still the case that the latest Flash Player 9 takes out my browser multiple times an hour if I use it heavily (FlashBlock has helped mitigate this issue for casual use). Since Linux is my preferred development platform, there’s no way I could see myself developing for it until this changes.

(A few people have asked me why I think Adobe has to be altrustic and expend resources supporting Linux. They don’t, of course. But then I don’t have to be altrustic and bend over backwards to develop for an RIA platform that doesn’t have good support for the development platform I normally use either. Remember that the original post was about why I personally didn’t want to develop for Adobe’s platform.)

For now this criticism remains unaddressed, although with the alpha release of AIR for Linux I have hope that it might be addressed this year.

Criticism: Adobe is putting up roadblocks for open source Flash player implementations.

Even when Adobe finally published specifications for the flash format, they carried restrictions which prevented using them to implement your own flash player. Interviews with Adobe employees in the past had also indicated that Adobe was concerned about retaining control of its platform. Worse, in March they had announced their intent to make DRM part of the flash platform, introducing an additional obstacle for Open Source players.

However, just this month (May), Adobe launched the Open Screen Project and removed the restrictions on the use of their specifications. Some have called this a PR stunt, since the way it worked out Adobe hadn’t relaxed the restrictions on the specifications until all the information published in them had been reverse-engineered by the developer community anyway. However, I think calling it a PR stunt misses an important point—the Open Screen Project is specifically a signal that Adobe is no longer directly hostile to alternate Flash Player implementations.

This criticism is largely addressed; DRM remains an issue on the horizion, but Adobe’s public stance against non-Adobe players has clearly changed.

Criticism: Adobe doesn’t consider broad platform support for Flash to be important.

Historically, aside from Flash Lite (which is fairly different to the regular Flash platform), Adobe’s official support for Flash has mostly extended to PPC OS X and x86-32 OS X and Windows. There’s been the rather flaky and inconsistent support for x86-32 Linux (and the zombie-like revival of some version of the PPC Flash 7 plugin for the Wii), but that’s about it. The thing is, until you are able to support a certain number of platforms, the incremental cost of supporting each additional platform is extremely high. There’s essentially a knee in the graph, and Adobe is still quite far from reaching it.

As Sun discovered with Java, truly broad platform support is really only possible with an open source implementation of the platform. The community-developed zero-assembler Hotspot has enabled the JVM to be brought to a wide variety of new platforms which didn’t have Sun Java before with extremely little initial effort, and soon may start leveraging LLVM for cross-platform JIT performance. Flash will not be able to catch up in terms of platform support until at least one solid open source implementation of the Flash platform is available. On the evidence of the Open Screen Project, and their previous open-sourcing of the Tamarin runtime, I think Adobe finally realizes this.

I think this criticism was unfounded. Their release of Tamarin in November ought to have been a clue to me that they were waking up about this.

Job stress had really gotten to me the past couple months, to the point where I really didn’t have the time or energy to blog. Now that I’ve made some needed changes, I’ve got quite a lot of ideas piled up to blog about. I will try to pace myself and do it in small chunks, to avoid a yeggesplosion.

I’d had grandiose plans for a series of blog posts over the Triduum this year, but I never finished Good Friday’s post in time and it was downhill from there. Eh well. However, while I’m neither Anglican, Episcopal, nor a great fan of Rowan Williams, I recently read the sermon he gave this past Easter Sunday and thought it was unusually good. It’s no longer Easter, but it’s still the Easter season, so I may as well share:

The Archbishop of Canturbury’s Easter Day Sermon

This is the awesomest ad:

Monster – Legs

(Update: see Adobe Does Not Suck for an update on these criticisms.)

I don’t use proprietary software very often; one of the few pieces of proprietary software that I do use with some frequency is the proprietary Adobe Flash Player plugin. On a daily basis, it reminds me why I try to avoid proprietary software in the first place.

One illustrative point: I’m sure most people who have used the plugin on Linux experienced occasional browser lockups when exiting a page which used Flash. I experience it frequently, and everyone I’ve asked has had the same issue. It’s been a problem with the 9.0 releases of the plugin for a long time, but Adobe’s never done anything about it. Either they don’t know, or they don’t care.

I can’t rule out not knowing. I’d love to report the bug, but Adobe doesn’t provide an obvious way to do that without going through their “complimentary product support” channels—which require a registered Adobe product. All I want to do is put in a PR! Most open source projects are more receptive to bug reports (and that isn’t saying much).

Of course, if I did put in a PR I couldn’t really be more specific than “the flash player sometimes deadlocks when tearing down a plugin instance, locking up the entire browser.” I don’t have the source available to me to examine the issue in any more detail, and the EULA I agreed to when installing the plugin is rather stringent about reverse-engineering, so it’s not like I could legitimately go in with gdb to see what the deal is either.

This is hardly the only annoyance, either. Non-IA32 platforms have been left in the dust for a long time, and in recent revisions of the 9.0 plugin for Linux, there’s at least an additional livelock, worsening memory leaks, and severe performance regressions in the video pipeline. (Incidentally, if you’re having memory problems with Firefox, try removing the Flash plugin and see the kind of difference it makes.)

If the Flash plugin were open source and the worst issues had remained unresolved for this long, I’d try to resolve some of them myself. I’ve got a decent amount of experience with concurrent programming, and more likely than not the issues are fairly straightforward. This is not because I feel any special obligation to Adobe to do their work for them. I’d be doing this for my own sake, and for the sake of the other people who have to deal with this stuff all the time.

Thanks Adobe; you’ve managed to alienate another developer. I’m going to stick to authoring software and content for platforms whose vendors don’t play these kinds of stupid control games, so I don’t lock my own users into your twisted little world. Sun’s entirely open platform is looking much better these days, and they’ve finally got people working to address the gross deficiencies of Java applets that gave Flash its opening in the first place. I’ve done Flash development in the past—the reason Flash dominates right now is not because it’s great platform to use and develop for, but rather only because the alternatives have been so much worse. That circumstance is, thankfully, beginning to change.

Garritan has put together an online version of Rimsky-Korsakov’s classic book on orchestration. With commentary on the original text, and the ability to play back score fragments and follow along in your browser if you have Flash, it’s a really awesome resource.

PantoGraph is a prototype 3d rendering engine that outputs SVG and is implemented as a Blender Python script.

(Hat Tip: BlenderNation)

My PGP keys expired recently; the new public key is available from the usual place. The fingerprint of the new key should be E829 4985 45A1 5870 7239 A6FF 1293 0555 EF78 AF6E.

Those with whom I’ve been maintaining key trust relationships, see me offline about signing.

On YouTube

SoundManager 2 is a rather nice BSD-licensed JavaScript library which employs a small Flash shim to provide a straightforward JavaScript API for sound playback.

Use responsibly, kids.

Intel’s go parallel subsite on DevX has a rather nice article up about designing threaded applications. Highly recommended.

I’d also suggest browsing around the go parallel section itself; it’s not bad reading even if it has an (understandable) bias towards Intel tools and technologies.

(Hat Tip: Jeff Turcotte)

There’s a new interview with me up on InfoQ about Ruby concurrency, Rubinius, and the Actor Model.

Happy New Year! Today is the first day of the seventh year of the second millennium, and the Solemnity of Mary, Mother of God. Pace!

Zed Shaw writes about what makes the lua project work. I think he’s dead on, because it matches my own experiences very well. I think one of the reasons that Inkscape is as succesful as it is is that we work very hard to foster a “collaborator-style” community and integrate newcomers into that culture.

A Google Tech Talk by Hans Boehm.

(Thanks Bob!)

Merry Christmas!

Yes, it’s exactly what it says on the tin.

Introduction

Discussions of multithreaded programming and the Java Memory Model often get bogged down in discussion of complex compiler optimizations. I don’t think it needs to get that complicated—if all you want to do is write correct multithreaded programs, there’s a pretty simple mental model you can follow.

How to Think about Memory

Each thread has its own view of memory such that two threads can disagree on the contents of the same field. Writes made to a field by one thread may bleed through and become visible to others, but they may also appear only transiently, in the wrong order (even before they are “supposed” to happen!), or not at all. This is permitted for performance reasons.

However, Java does provide a few specific ways for threads to reliably communicate writes to one another…

The Tools at Your Disposal

There are five ways to explicitly ensure that one thread’s writes up to a certain point will be visible (and in the right order!) to other threads. Each one uses a particular sort of language primitive as a rendezvous for a writing thread to “publish” its writes, and for other threads to “receive” them:

Note that for the rendezvous to happen, it must be the same thread, the same field, or the same monitor on both the “publishing” and “receiving” sides.

Really, at all levels of abstraction, all correct concurrent programs share a particular characteristic: threads do not communicate with each other at all except when they mutually agree to communicate at common rendezvous points. Any truly unilateral attempt at communication (like Thread.suspend) is inherently unsafe.

Applying Your Knowledge

Let’s say we’ve got a class like this:

class Counter {
    private int count = 0;
    public synchronized void increment() {
        count++;
    }
    public synchronized int getCount() {
        return count;
    }
}

Making increment synchronized ensures not only that the increment of count (which involves a read and then a write of the modified value) isn’t disturbed, it also ensures that the modified value of count is “published” where other threads can potentially see it.

Likewise, making getCount synchronized ensures that the thread “receives” any “published” changes to the value of count when the method body is entered.

Both synchronized declarations are necessary for this code to work as expected. Of course, since getCount is simply reading a single int field (which is already an atomic operation), there is another way to approach this:

class Counter {
    private volatile int count = 0;
    public synchronized void increment() {
        count++;
    }
    public int getCount() {
        return count;
    }
}

This means that increment will “publish” twice: once when it writes to count, and once when it exits the synchronized method. This has no ill effects and only a very minor peformance penalty.

getCount only “receives” once: when it reads count. Since it is not synchronized by a monitor, concurrent calls for getCount do not have to wait for each other to complete. This can result in improved performance for readers.

Note that, had increment performed any writes to other fields after the write to count, those writes would not be safely visible to callers of getCount; the second “publication” which happens upon existing the synchronized method is via the object’s monitor, not the volatile field.

The Consequences

If you do not properly coordinate the “publication” and “reception” of writes between threads that share fields, then your program will fail transiently. It is more likely to do so under production load on high-end hardware than it is during testing on your development machine.

You don’t want that. Neither does your boss.

Further Reading

The JSR 133 FAQ goes into more detail about the memory model itself. Like the Memory Model document, it goes a little more into the effects of specific kinds of optimizations.

One Last Thing

If you ever do get dragged into a discussion of compiler and runtime optimizations, it’s important to remember several things:

1. Disassembling .class files doesn’t tell you much about what will happen at runtime: javac performs very few optimizations, leaving most of them up to the interpreter and JIT compiler.
2. While the interpreter and the JIT compiler are prohibited from performing certain optimizations like reordering dependent reads or writes, the CPU itself is not.
3. A few CPU architectures can and will reorder dependent memory operations and get away with it—unless you are writing improperly synchronized programs.
4. Still, today’s hardware is often fairly forgiving about multithreading. As we’ve run out of room to scale “up” and have to scale “out” instead, future hardware will have to sacrifice that forgiveness for increased concurrent performance. Unless you want to rewrite all your code in five years, do it right the first time.

One Other Thing

Try using the classes in java.util.concurrent and java.util.concurrent.atomic before rolling your own custom solutions using synchronzied and volatile. The java.util.concurrent classes are likely to be both correct and as fast as possible while still maintaining correctness (which is seldom easy to achieve). They’re built on top of the basic primitives themselves, so they have similar characteristics: for example, writing to a java.util.concurrent queue “publishes” to the queue’s readers.

As the use of Swing with JRuby is becoming increasingly popular, are there any good Swing resources out there directed at Ruby programmers? If not, I may have to take a stab at writing some material…

So, I was thinking today—what makes a programming language a scripting language? There are three characteristics which seem to be typical:

1. Most normal use of the language does not involve an explicit (user-visible) compilation phase
2. Expressions or statements are valid top-level productions in the language’s grammar
3. The language has a very rich (and possibly somewhat domain-specific) standard library

Any good counterexamples? That is, are there any languages commonly considered scripting languages which do not meet all three criteria? Conversely, are there languages which are not commonly considered scripting languages which do meet all of them?

Here’s a brief overview of how I set up and use git-svn to commit to JRuby.

Initial Setup

If you want the whole history of JRuby, branches and all, just do:

git-svn clone -Ttrunk/jruby -ttags -bbranches --username mental https://svn.codehaus.org/jruby jruby

...which will create the directory jruby and clone the entire repository history into it, then check out a working copy from trunk. I typically just work with individual branches, though. My own initial setup was just to work with trunk:

git-svn clone -Ttrunk/jruby --username mental https://svn.codehaus.org/jruby jruby

You don’t actually need the whole history, but it is occasionally incredibly convenient to have, and once you clone you’re mostly stuck.

My username is actually the same locally as it is remotely, so I didn’t need to use the --username option; I just included it for completeness.

Day-to-day Operation

Before starting, I make sure I’m on the right git branch and have no uncommitted changes. Then I can make sure that I have current version of the mirrored Subversion branch I want to work against (here, remotes/trunk):

git-svn fetch -i trunk
git-rebase remotes/trunk

Then I can just git-commit to my heart’s content. When I’m ready to push my changes back to Subversion, I can just run:

git-svn dcommit -i trunk

If there are any conflicts with new changes in Subversion, it will fail and you will need to fetch and rebase again (resolving the conflicts manually —see the git documentation) before you will be able to commit to Subversion. I usually do this proactively, to make sure that I have a chance to test the commits in their rebased form.

Topic Branches

Sometimes I have a number of things I’m working on at once. In those cases I’ll create a topic branch to work on a feature separately, rather than working in a regular persistent branch like master:

git-checkout -b topic/thingy-feature remotes/trunk

At this point topic/thingy-feature becomes the current branch and the procedure works the same as above. Once I’m done working on the feature I usually switch back to one of the “regular” branches and delete the topic branch with:

git-checkout master
git-branch -d topic/thingy-feature

Combining Commits

If I’ve been working in git for a while without commiting to Subversion, I may have a non-trivial sequence of commits saved up (I tend to commit in small increments as I work), where only the final one really reflects a working state. To collapse them into a single commit before dcommitting, I can fetch/rebase and then do:

git-reset --soft remotes/trunk
git-commit -c ORIG_HEAD

I usually don’t need to do this as I try to integrate frequently with trunk, though.

Merges and Non-Linear History

Linear histories are trivial, but merges and Subversion don’t really get along. This extends to git-svn as well. That’s material for another post, however.

I’ve been listening to pianist-composer Sean Mahnken’s album Patterns for the past couple days and I’m enjoying it quite a bit. You can hear some of the songs on his web site.

Erez Petrank has quite a lot of interesting garbage collection projects and papers up on his projects page.

Now that I’ve discoverd StumbleVideo, I guess I’m not getting much practical done tonight. While nowhere near as good as One Rat Short, here are a few other selections I liked:

• Moutons – fluffy sheep! underwater!
• I Lived on the Moon – a girl versus the angry sun gnomes
• Over Time – puppets cope with loss
• The Pier – a fisherman gets more than he bargains for (n.b. slightly gory)
• 9 – the last of his kind, number nine prepares to face down the creature that killed the others

(Over Time is probably my favorite.)

I discovered One Rat Short via Stumbleupon Video today; it has to be one of the best-made animated shorts I’ve seen in a very long time.

I really hope we get to see more from Charlex Films in the future.

Thanks to quite a lot of readers writing in, I now have a much better picture of what’s going on with charging my new phone. There are really two considerations when charging a device via USB:

First, not all USB ports are prepared to power devices (like charging phones) with high power requirements. There are various levels of peak power consumption defined by the USB specification, so it’s necessary to match the device to an appropriate USB host which can meet its specific power requirements.

Secondly (and this is evidently my real problem), many Motorola devices specifically check whether the USB port belongs to a Motorola-manufactured device; this is signaled by shorting certain pins, as documented here. Phones may also ignore this hardware check and charge from a regular USB port if the host computer has special software installed which responds with the Motorola “secret handshake”; a Linux machine running moto4lin appears to be sufficient for this purpose.

I had to urgently replace my phone recently, and decided to get a Motorola V195s since it had no camera (a requirement imposed by my job) and in my particular situation was only about $9 after rebate. It’s not a great phone, but I needed a phone quickly which could reliably make calls.

One thing I was pleased to find, however, was that the phone charged via its mini-USB port. Yay! No more worrying about losing the wall dongle.

Or so I thought. I spent the entire day trying to get it to charge from various USB charging dongles and USB ports on different hubs and computers. I even checked the voltage/current ratings on the Motorola-provided charger against the other USB chargers and they matched. Other USB devices even charged fine with the Motorola charger. But the Motorola phone only charges with Motorola’s “special” USB wart.

That is absolutely assinine.

My next phone will be a Neo 1973.

This is a quick post to ensure that the RSS and Atom formatting bug is really fixed. Let’s see! Ideally, the below should have multiple levels of indentation:

bindInputContext :: (WidgetClass w) => w -> Dispatcher -> IO InputContext
bindInputContext widget dispatcher =
  do stateRef <- newIORef $ ContextState {
                              activeModifiers = 0,
                              canvasWidget = castToWidget widget
                            }
     mapM_ ($ (inputHandler dispatcher stateRef))
           [onButtonPress   widget     ,
            onButtonRelease widget     ,
            onKeyPress      widget     ,
            onKeyRelease    widget     ,
            onEnterNotify   widget     ,
            onLeaveNotify   widget     ,
            onMotionNotify  widget True]
     return $ InputContext stateRef

I’d not poked around the religion area of Wikipedia for quite a while, but the The Assumption of Mary article is actually not too bad. April 15th, The Feast of the Assumption of the Blessed Virgin Mary, falls on Wednesday this year, and it’s a Holy Day of Obligation for Catholics in the United States and most other places.

The Fauxharmonic Orchestra is a digital orchestra directed by Paul Hentry Smith which offers its services to orchestral and chamber composers at rates much cheaper than hiring a real orchestra. Really amazing stuff.

(Hat Tip: Anarchaia)

My New Leg is an online diary about the process and experience of getting a prosthetic leg, by Steve Kurzman.

Uniplate is a very simple and elegant library for generic data structure traversals and transformations in Haskell.

(Hat Tip: Anarchaia)

Twibright Optar is an encoding for storing data on printed pages; it can fit about 200k on a single A4 page. While the current implementation is still immature, I think it has a lot of potential in the field of digital archiving because it is Open Source and therefore relatively future-proof.

(Hat Tip: LWN)

Intel’s open-sourced their spiffy Thread Building Blocks library, which very nicely abstracts most of the crappy parts of working with explicit threads. GPLv2, with the runtime exception (so non-GPL software can use it). Good show, Intel.

Just so I can get this out of my system once and for all, I figured I may as well show how one could safely implement a spin buffer as described in the DDJ article (minus the lack of synchronization).

First of all, here’s the original implementation of SpinBuffer from the article:

[I’m going to have to apologize in advance for the lack of code indention in the RSS and Atom feeds—it’s the result of a bizzare Hobix (or REXML?) bug I’ve yet to track down; until it’s fixed you’ll need to read the original post to see the correct formatting.]

public class SpinBuffer {
    private static final int MAX_SIZE = 1000000;
    private Object[][] m_bfr = new Object[3][MAX_SIZE];

    private boolean[] m_busy = new boolean[3];
    private int[] m_count = new int[3];
    private int[] m_ptr = new int[3];

    private int m_pBuf = 0;
    private int m_cBuf = 1;

    /** Creates a new instance of SpinBuffer */
    public SpinBuffer() {
        m_busy[0] = m_busy[1] = true;

        m_busy[2] = false;
        for ( int i=0; i<3; i++ ) {
            m_ptr[i] = m_count[i] = 0;
        }
    }
    public boolean put(Object o) {
        int next = (m_pBuf+1)%3;

        if ( m_ptr[m_pBuf] < MAX_SIZE ) {
            // add to the buffer
            m_bfr[m_pBuf][m_ptr[m_pBuf]] = o;
            m_ptr[m_pBuf]++;
        }
        else
            return false;
        // check if next buffer is free
        if ( !m_busy[next] ) {
            m_count[m_pBuf] = m_ptr[m_pBuf];
            m_ptr[m_pBuf] = 0;
            m_busy[next] = true; // acquire
            m_busy[m_pBuf] = false; // release
            m_pBuf = next;
        }
        return true;
    }
    public Object get() {
        Object o = null;

        if ( m_ptr[m_cBuf] < m_count[m_cBuf]) {
            o = m_bfr[m_cBuf][m_ptr[m_cBuf]];
            // remove the reference
            m_bfr[m_cBuf][m_ptr[m_cBuf]] = null;
            m_ptr[m_cBuf]++;
        }
        else {
            // check if next buffer is free
            int next = (m_cBuf+1)%3;
            if ( !m_busy[next] ) {
                m_busy[next] = true; // acquire
                m_ptr[m_cBuf] = 0;
                m_count[m_cBuf] = 0;
                m_busy[m_cBuf] = false; // release
                m_cBuf = next;
            }
            //else, waiting for consumer
        }
        return o;
    }
}

The idea is that we have three buffers: at any given time, one buffer is being written to, one buffer is being read from, and the remaining buffer is either full and waiting for the reader to consume it, or empty and waiting for the writer to populate it. The reader and writer work around the ring of three buffers in one direction, as the role of “free” buffer migrates around in the opposite direction, providing “give” so that the reader and writer don’t have to work exactly in lock-step.

In this scheme little synchronization is required since the reader and writer are never using the same buffer at the same time. Unfortunately, little synchronization is not the same as none, and the lack of care for synchronization in the code above means that its behavior simply isn’t guaranteed by the Java Memory Model.

The spin buffer concept is possible to implement “properly” with sufficient attention to synchronization, however. It’s a weird data structure with annoying properties, so I’d still recommend using something like ConcurrentLinkedQueue instead, but…

NOTE: I ran out of time to work on this tonight, so what follows is a draft which I haven’t compiled or tested yet. I’ll post any needed corrections later, but I won’t mind if you leave me a comment when you spot something wrong.

/**
 * A class implementing a (fast?) non-blocking queue for communication
 * between one producer and one consumer thread.  Internally, it
 * employs the exchange of fixed-capacity buffers; when the producer
 * fills one buffer to capacity, it is exchanged with the consumer
 * thread for a fresh buffer.  Similarly, when the consumer empties a
 * buffer, it is returned to the producer thread in exchange for a
 * newly populated buffer.
 *
 * Since the queue is non-blocking, it is necessary for both the
 * producer and consumer to poll.
 */
public class SpinBuffer {
  private Gate gate;
  private Buffer consumer_buffer;
  private Buffer producer_buffer;

  /**
   * Initializes a "spin buffer" with internal buffers of the
   * given capacity; the capacity determines how many objects can be
   * added to the queue by the producer before they are available
   * to the consumer.
   */
  SpinBuffer(int capacity) {
    if ( capacity < 1 ) {
      throw new IllegalArgumentException();
    }
    gate = new Gate(new Buffer(capacity));
    consumer_buffer = new Buffer(capacity);
    producer_buffer = new Buffer(capacity);
  }

  /**
   * Adds an object to the queue, exchanging buffers with the consumer
   * if the current buffer is filled.  Returns true if the object was
   * successfully added, or false if the current buffer was filled and
   * the consumer wasn't ready to receive it yet.
   *
   * The object cannot be null.
   *
   * Should be called only by the single producer thread.
   */
  public boolean put(Object o) {
    if ( o == null ) {
      throw new NullPointerException();
    }

    boolean success = producer_buffer.put(o);
    if (!success) {
      Buffer next = gate.producerSwap(producer_buffer);
      if ( next != null ) {
        producer_buffer = next;
        success = producer_buffer.put(o);
        assert success;
      }
    }
    return success;
  }

  /**
   * Tries to force an immediate exchange with the consumer, so long
   * as the current buffer is not empty.  Returns true if the exchange
   * succeeded or the buffer was empty, false otherwise.
   *
   * This is useful when, for example, the producer has no more objects
   * to provide.  As there's no other way for the consumer to
   * distinguish between the producer having an unfilled buffer and
   * there simply being no more data, end-of-data should be indicated
   * in-band by a special object.  Signalling end-of-data out-of-band
   * requires additional synchronization.
   *
   * I think this is a better solution than the original article's idea
   * of requiring the client to write MAX_SIZE nulls.
   *
   * Should be called only by the single producer thread.
   */
  public boolean flush() {
    boolean flushed = false;
    if (!producer_buffer.isEmpty()) {
      Buffer next = gate.producerSwap(producer_buffer);
      if ( next != null ) {
        producer_buffer = next;
        flushed = true;
      }
    } else {
      flushed = true;
    }
    return flushed;
  }

  /**
   * Retrieves an object from the queue, or null if one is not yet
   * available (e.g. because the producer is still in the process of
   * populating a new buffer).
   *
   * Should be called only by the single consumer thread.
   */
  public Object get() {
    Object o;
    o = consumer_buffer.get();
    if ( o == null ) {
      Buffer next = gate.consumerSwap(consumer_buffer);
      if ( next != null ) {
        consumer_buffer = next;
        o = consumer_buffer.get();
        assert o != null;
      }
    }
    return o;
  }

  /**
   * This class implements a fixed-capacity buffer which accepts up to
   * a certain number of objects (its capacity) via the put method,
   * after which it should be emptied via the get method to reset it
   * before more objects can be added.
   *
   * I know this is weird.  Maybe I should have just used a ring
   * buffer...
   */
  static private class Buffer {
    private Object[] contents;
    private int head = 0;
    private int tail = 0;

    Buffer(int capacity) {
      contents = new Object[capacity];
    }

    /**
     * Adds an object at the head of the buffer and advances the head,
     * returning true if successful or false if the object was not
     * added because there was no more room to advance the head.
     */
    public boolean put(Object o) {
      assert o != null;
      assert tail == 0;
      if ( head < contents.length ) {
        contents[head++] = o;
        return true;
      } else {
        return false;
      }
    }

    /**
     * Removes and returns the object at the tail of the buffer,
     * advancing the tail.  Returns null if there are no more objects
     * in the buffer, at which time it will be ready to accept
     * more.
     */
    public Object get() {
      if ( tail < head ) {
        Object o = contents[tail];
        contents[tail] = null; // don't litter
        tail++;
        return o;
      } else {
        head = tail = 0;
        return null;
      }
    }

    public boolean isEmpty() {
      return head  tail;
    }

    public boolean isReady() {
      return head  0;
    }
  }

  /*
   * A Gate object provides a safe way for the producer and consumer
   * threads to exchange buffers; each thread passes in the buffer
   * it’s finished with and gets a fresh buffer in return; the
   * exchange is made only if a fresh buffer has been made available
   * by the other thread.
   *
   * This is the only part of the code where the two threads
   * communicate. Isolating that code here makes correctness easier
   * to reason about; it can be modeled by a simple state machine
   * whose initial state is (null, consumed):
   *
   * (null, consumed)  → producerSwap → (populated, null)
   * (null, consumed)  → consumerSwap → (null, consumed)
   * (populated, null) → consumerSwap → (null, consumed)
   * (populated, null) → producerSwap → (populated, null)
   *
   * Since consumer_next is volatile, the consumer thread’s read of
   * consumer_next ensures that the producer’s writes up to the
   * point where the producer wrote to consumer_next happen before
   * the consumer’s read.
   *
   * Similarly, the producer thread’s read of producer_next ensures
   * that the consumer’s writes up to the point where the consumer
   * wrote to producer_next happen before the producer’s read.
   *
   * Note that this doesn’t work under the original version of the
   * Java Memory Model (prior to Java 5), since it underspecifies
   * volatile.
   */
  static private class Gate {
    // note that these are volatile!
    volatile private Buffer consumer_next;
    volatile private Buffer producer_next;

    Gate(Buffer initial) {
      assert initial != null;
      // prime with a buffer for the producer to take
      producer_next = initial;
    }

    /*
     * Called by the producer thread to exchange buffers; receives the
     * buffer the producer has populated and returns a new, empty
     * buffer to populate if one is available.  Otherwise, does
     * nothing and returns null.
     /
    public Buffer producerSwap(Buffer populated) {
      assert !populated.isEmpty();
      Buffer next = producer_next;
      if ( next != null ) {
        // note the order of these assignments!
        producer_next = null;
        consumer_next = populated;
      }
      return next;
    }

    /*
     * Called by the consumer thread to exchange buffers; receives
     * the buffer the consumer has consumed and returns a buffer
     * with more objects to consume if one is available.  Otherwise,
     * does nothing and returns null.
     */
    public Buffer consumerSwap(Buffer consumed) {
      assert consumed.isReady();
      Buffer next = consumer_next;
      if ( next != null ) {
        // note the order of these assignments!
        consumer_next = null;
        producer_next = consumed;
      }
      return next;
    }
  }
}

Recently, my attention was directed to an article in June’s issue of Doctor Dobb’s Journal; it describes an implementation of thread-safe FIFO queues, “spin buffers”, which supposedly yields better throughput than standard alternatives like java.util.concurrent.ConcurrentLinkedQueue. However, I didn’t get far into the article before I read some text which raised a big red flag:

One approach [to addressing synchronization overhead] is to minimize

As described, this is a profound “free lunch violation” in the same class as perpetual motion machines, free energy devices, and the water-powered car: you need some kind of synchronization (memory barriers and atomic operations, if not also locks) when communicating between threads. Without it, the compiler and CPU are free to make all sorts of alterations to your code and its memory effects which can cause failures in multithreaded situations.

Synchronization isn’t just about keeping two threads from touching the same data at once; it’s also the only guarantee that your code will actually work the way you wrote it outside the confines of a single thread.

Looking through the source code (available from the issue’s downloadable source code archive as spin.txt and spin.zip) confirms my worst suspicions: there are no memory barriers involved whatsoever. Sadly, it’s quite easy to fool yourself into believing that a piece of code works in a concurrent setting, because concurrency bugs are notoriously difficult to test for. Even worse, the author tested on a single extremely forgiving hardware configuration (a single hyperthreaded x86 CPU), and his test program checked nothing besides counting the number of objects read from the queue.

So, please, don’t use this code, especially not in anything important. It’s fast because it throws correctness to the winds. Stick with code like ConcurrentLinkedQueue which has been extensively peer-reviewed.

Update: A number of readers have written me, repeating the author’s assertion that there aren’t any problems with a single reader and a single writer, because synchronization is only necessary to prevent conflicting updates. That simply isn’t true on modern systems: unless you employ proper synchronization, there are subtle problems which can arise when two threads simply communicate. The Java Memory Model FAQ gives a good overview of the issues involved.

Update: Bill Thies points out that, while you do need memory barriers for proper synchronization (which the article’s author failed to use), neither atomic operations nor locks are necessary for writing a single-reader/single-writer queue if you do it right.

The TV Tropes Wiki is a massive catalog of the devices and conventions modern audiences are familiar with. Despite its name, it covers not only television, but film, video games, comic books, and many other media besides. As a writer, it’s like the best thing ever.

But be warned; TV Tropes can ruin your life!

While I’m on the topic of energy profiling, the 2000 paper Source Code Optimization and Profiling of Energy Consumption in Embedded Systems is an interesting read.

As energy consumption becomes an increasingly serious concern, we’ll start to see techniques like these migrating up from embedded systems work into the “mainstream”. If you want an actual prediction: my money’s on preliminary support for power profiling in Valgrind within the next five years.

I guess this satisfies another one of the “predictions” I recorded in last year’s post, The Next Ten Years in Programming:

We will see the beginnings of hardware and software infrastructure for

Like many of my “predictions”, it’s knowingly made a few years too late: there have been power profiling tools and hardware cropping up since the turn of the millennium at least; it’s just a question of when they become mainstream.

By the way, Delimited Continuations in Operating Systems is a very nice paper. The paper’s introduction alone is worth the price of admission, as it begins with the most cogent explanation of continuations I’ve ever read. One annoyance: the CC monad used doesn’t appear to be available as a nicely packaged library anywhere.

You may also enjoy the rest of Oleg’s site, as there’s lots of great material on a broad variety of programming topics there.

Generic zippers for pure-functional transactions. Just wow.

(Hat Tip: Anarchaia)

Alias Clio delves into the subtleties of irony, courtesy of Fowler’s Modern English Usage.

(Hat Tip: Eve Tushnet)

As the stone of ancient Greek and Mesoamerican monuments was often richly painted (contrary to how we are used to seeing them today), so too was the stone of medieval churches. See also the light show at Amiens.

K-Sketch is a simple (unreleased, sadly) application for creating proof-of-concept animations in realtime.

Check out the demo video (Quicktime; WMV is also available).

(Hat Tip: Mike Sloan)

The notes from Advanced Graphics Programming Techniques Using OpenGL, a course from Siggraph 2000 covering quite a lot of valuable material about ways to get the most out of OpenGL graphics, are available online. Definitely worth a look!

Why I’m not a fan of 24. (Or Justice Scalia, for that matter.)

No going outside:

Children are so cocooned by their parents that they rarely venture far from home and have little concept of space, volume and how the world actually works, David Willetts, the shadow education secretary, said yesterday.

No human contact:

All touching — not only fighting or inappropriate touching — is against the rules at Kilmer Middle School in Vienna. Hand-holding, handshakes and high-fives? Banned. The rule has been conveyed to students this way: “NO PHYSICAL CONTACT!!!!!”

This seems like the perfect way to raise a generation of profound neurotics.

I wish I could say these were relatively isolated phenomena, but I remember this sort of silliness beginning even late in my own High School career (e.g. bringing a plastic butter knife in your lunch could land you a suspension under the knife ban, and the school incrementally approaching a state of continuous lockdown), and by most accounts it’s only gotten worse since.

The String Tripod is a very simple, inexpensive, and portable camera stabilization device which works well with your camera’s image stabilization in lieu of a true tripod.

Steven C. Dollins offers a page of Handy Mathematics Facts for Graphics.

(Hat Tip: Anarchaia)

Buckytree is an implicit data structure for O(NlogN) spatial sort and O(logN) spatial search of dimensional objects.

In other words, it’s an efficient way to sort and find objects based on the regions of space they occupy.

(Hat Tip: Anarchaia)

The Prioritizer is a handy little web-based tool for helping you work out your personal priorities over a list of up to fifteen items.

(Hat Tip: John Bintz)

Wolfgang Heidrich’s PhD thesis is a very interesting read, particularly section 6.3.1 which describes how to implement shadow maps in the absence of the OpenGL shadow mapping extension using the alpha test.

Jos Stam’s 1997 paper, Aperiodic Texture Mapping, explains how to build infinitely non-repeating textures from a set of 16 predefined tiles. I know a lot of games which could have afforded to use this technique.

Spin Ink has made some very nice wallpapers for those of you with multi-head (well, dual, mostly) setups. Check them out!

Given how much I’ve been bitching about the paucity of robust open source computational geometry libraries lately, I was very pleased to discover the GNU Triangulated Surfaces Library: it does pretty much everything you might want to do with a triangulated surface.

... (which was never that good to start with) owes much to the replacement of analysis with speculation.

As-Rigid-As-Possible Shape Manipulation is the paper which introduced the technique used by Adobe for the Puppet Tool in After Effects. It is a significantly better approach for shape tweening than that taken by e.g. Flash (or even Synfig), and I think (in combination with inverse kinematics for the manipulation of the control points) it is the future of 2d animation.

(There is a web site with a demo video here)

I’m not really a fan of the whole Stan Lee/Kirby lot, but…

If you’re a fan of Stan Lee and Jack Kirby’s epic run on the Mighty Thor, you’ve heard (and maybe even share) the complaints about the inking style of Vince Colletta. Well, now is your chance to put your ink where your mouth is and have some fun re-embellishing a select page of Kirby’s dynamic artistry!

Reinking Thor

Just a quick note that I’ve released the first version of my Omnibus Concurrency Library for Ruby. See the release announcement for details and what currently passes for documentation.

Downloadables are on RubyForge and the library is also available via RubyGems as the concurrent gem.

A prose fragment inspired by an actual conversation.

Nick straightened the table with both feet, generating a loud honk as the leveler feet scraped over the linoleum.

“Video and sound were not practical when I started on the web,” Nick observed.

“Eh, the bandwidth just wasn’t there,” said Matt.

Nick raised his eyebrows earnestly. “Indeed, even pictures were frowned upon as too expensive.”

“Well, I suppose they’re hardly essential,” I said.

Nick paused. “Sometimes I would get word documents from the sysadmin about how my text was using too much bandwidth, and that I try to write more concisely.”

Matt snorted with suppressed laughter.

I grimaced. “Lovely.”

There was a loud “PANG” as the vending machine in the hall outside disgorged a beverage.

I picked up the thread again. “Concision is a lost art, sadly.”

“People tend to write about it more than do it,” Nick said, setting his cup down definitely.

“Yeah, it’s great to see long articles about the virtues of concision,” Matt said, illustrating with his hands.

”’Use less words,’” I quipped.

Matt laughed.

“Moment,” I said as I dragged my laptop off the table to balance it on my knees. “I am so going to blog that.”

“The thing—” I glanced up again to find him looking at me. “The thing I was laughing at, though, is that it should be ‘Use fewer words.’”

“Oh. Hmm,” I said, and looked down at the laptop again. “It’s posted. I think I’m going to leave it the way it is.”

Matt leaned back in his chair, looking up. The back cushion shifted with a faint sound of vinyl on wood. “I suppose it could mean you’re using lesser words. Shorter ones. Sort of.”

“Okay, maybe I will fix it.” More typing. “There.” I turned the laptop around to face him.

Matt leaned forward over the table and frowned. “Huh. Loses a bit of its zing, doesn’t it?”

“Yeah…”

There was a long silence.

“I’ll put it back the way it was,” I said.

Use less words.

If you’re buying carbon offsets, beware of scams.

E.M. Forster’s 1909 story, The Machine Stops, was one of the first science fiction stories I read growing up, and it’s had a profound effect on my imagination since. I was delighted to find it online again recently—and, as someone else observed, yes, it really was as good as we remembered.

Here it is.

Reading it today, a most uncanny things about the story lies in many of the things it seems to anticipate, given that it was written before YouTube, before instant messaging, before the Internet, before television or nuclear weapons, before the electronic computer, before intercontinental flights, before even commercial air traffic, a few years after the debut of the very first broadcast radio program, and less than a decade after the Wright Brothers’ first experimental flights.

Tom Simon writes on modern expectations about the length of novels and its deleterious effects on the form. Full ACK.

Well, I’ve been back from LGM for a couple days now, but it’s taken me about that long to recuperate. I’ll try and catch up on various things, blogging included. Look out for my LGM report, some more concurrency stuff, as well as a follow-up on replies to certain recent posts.

On Jabber the other day, njh pointed out the Wikipedia page for a recentish BBC documentary. I’ve not seen it yet, but it looks sort of interesting.

The argument I’ve heard from some atheists runs thus: the goal of science is to offer explanations for (in the sense of providing a viable model for) physical phenomena. In the past, such models were often religiously derived, but the scientific models have been consistently more successful. Therefore, religion is no longer necessary.

However, such a conclusion betrays a fundamental misunderstanding of what religion is. Religion stems from the pervasive human sense that:

1. There is a supernatural.
2. We are alienated or separated from it in some way.

Consequently, it represents an attempt to reconnect with the supernatural, an understanding reflected in the word’s etymology (re+ligare; to re-connect). While both of these impressions are often provoked by encounters with nature (witness the prevalence of early nature religions), explanations of physical phenomena are at best a secondary concern.

Even if one goes so far as to believe that religion is a harmful accident of our natural development, the fact that religion has been an aspect of the human experience for so long and so universally suggests that the strength of the religious impulse should be treated with a healthy respect. To offer science as a replacement for religion is to invite the involvement of powerful and deeply ingrained sentiments which can only result in sloppy thinking about science.

Here’s one way to attack incrementally turning a class into a generic, template version:

class PiecewiseSBasis {
public:
  PiecewiseSBasis() {}
  PiecewiseSBasis(SBasis const &sb) { /* ... */ }
  PiecewiseSBasis &operator=(PiecewiseSBasis const &other) {
    /* ... */
  }
  // ...
};

PiecewiseSBasis operator+(PiecewiseSBasis const &a,
                          PiecewiseSBasis const &b);

First, convert the class into a specialized template:

template <typename F> class Piecewise;

template <>
class Piecewise<SBasis> {
public:
  Piecewise() {}
  Piecewise(SBasis const &sb) { /* ... */ }
  Piecewise &operator=(Piecewise const &other) {
    /* ... */
  }
  // ...
};

typedef Piecewise<SBasis> PiecewiseSBasis;

PiecewiseSBasis operator+(PiecewiseSBasis const &a,
                          PiecewiseSBasis const &b);

Note how the class name inside the template has become Piecewise, the name of the class template. Next, we move all the members into the main template and discard the specialization:

template <typename F>
class Piecewise {
  Piecewise() {}
  Piecewise(F const &f) { /* ... */ }
  Piecewise &operator=(Piecewise const &other) {
    /* ... */
  }
  // ...
};

typedef Piecewise<SBasis> PiecewiseSBasis;

PiecewiseSBasis operator+(PiecewiseSBasis const &a,
                          PiecewiseSBasis const &b);

At this point we can begin incrementally replacing PiecewiseSBasis with Piecewise<SBasis> in the remainder of the code, until we no longer need the typedef. Finally, you can inline functions as needed:

inline Piecewise<SBasis>
operator+(Piecewise<SBasis> const &a,
          Piecewise<SBasis> const &b)
{
  // ...
}

...and then incrementally make them generic, too:

template <typename F>
inline Piecewise<F>
operator+(Piecewise<F> const &a, Piecewise<F> const &b)
{
  // ...
}

This trick isn’t appropriate for every situation, but when it works it can get you over that initial refactoring hump real nicely.

Well, just when I thought I was done with fastthread, it turns out that the version of fastthread merged into Ruby 1.8.6’s thread library had a couple serious bugs. So, here’s a new version of fastthread which can serve as a hotfix until the next Ruby release.

• fastthread-1.0.gem
• fastthread-1.0.tgz

Thanks to Sylvain Joyeux for finding the problems!

So, you’re interfacing your C++ classes with some C library, and you’d like to wire a C callback to some C++ method. You’ve got a method:

void SubClass::setFoo(int) throw(SomeException);

but the callback prototype the C library gives you is just:

int (*DumbSetter)(int, void *);

So, okay, you write a wrapper function to use as the callback:

int wrap_setFoo(int value, void *data) {
  BaseClass *base_instance = static_cast<BaseClass *>(data);
  SubClass *instance = static_cast<SubClass *>(base_instance);
  try {
    instance->setFoo(value);
    return 1;
  } catch (SomeException) {
    return 0;
  } catch (...) {
    std::cerr << "Unexpected exception in callback; exiting\n";
    abort();
  }
}

There are two important things to note here:

1. if the data pointer wasn’t cast directly from SubClass * to void *, but was instead cast to a superclass (BaseClass) first, you’ll need to reverse the process when casting away from void *, as shown here.
2. you can’t let C++ exceptions escape into C functions; they have the potential to wreak havoc on the C stack. If we get an exception we’re not already prepared to handle, we have to do something rather than let it escape. Aborting is one option; using the C API’s error reporting facilities are another.

So, okay. That wasn’t too bad. But now let’s say you’ve got many different setFoo, setBar, setBaz, setHoge, ... setXYZZY member functions, in many different classes. That’s a lot of copy and pasting…

Provided they all share the same signature, however, you can use C++ templates to automate the generation of the wrapper functions. Here’s how:

template <typename Base, typename T, void (T::*setter)(int)>
int wrap_setter(int value, void *data) {
  Base *base_instance = static_cast<Base *>(data);
  T *instance = static_cast<T *>(base_instance);
  try {
    (instance->*setter)(value);
    return 1;
  } catch (SomeException) {
    return 0;
  } catch (...) {
    std::cerr << "Unexpected exception in callback; exiting\n";
    abort();
  }
}

As noted earlier, if you know for sure that the object pointer was originally cast or coerced directly to void * from T *, then you can leave off the intermediate cast to Base *, and the Base argument. If not, however, Base * must be the original type that was converted to void *.

So, anyway, there’s the template. At this point, you can register a callback for SubClass::setFoo as &wrap_setter<BaseClass, SubClass, &SubClass::setFoo>, rather than needing a separate &wrap_setFoo. setBar, setBaz etc. all work similarly, without writing any additional wrapper functions by hand.

Update: Murray Cumming points out that a double cast isn’t strictly necessary unless multiple inheritance is involved. I elected to include it here because omitting the intermediate cast when it is needed is a problem the compiler can’t catch. Better safe than sorry.

More importantly, however, he also reminded me that casting from the base class to the subclass using static_cast<> will not work when there is virtual inheritance involved (the compiler will alert you of such cases). To deal with them, you would need to use another version of the function template which used dynamic_cast<> for the second cast.

This interesting interview with Sister Judith Zoebelein, head of the Vatican’s web group, has been making the rounds lately.

Among other things, I’m rather glad to learn they’ve finally ditched IIS in favor of Apache:

Trying 212.77.1.246...
Connected to www.vatican.va.
Escape character is '^]'.
HEAD / HTTP/1.0

HTTP/1.1 200 OK
Date: Sat, 24 Feb 2007 01:21:16 GMT
Server: Apache/1.3.31 (Unix)
Last-Modified: Mon, 09 May 2005 11:14:21 GMT
ETag: "1cd-143b-427f460d" 
Accept-Ranges: bytes
Content-Length: 5179
Connection: close
Content-Type: text/html

Connection closed by foreign host.

(Hat Tip: Whispers in the Loggia)

See, this finally sunk in today: monads are a way of writing DSLs in functional settings. Haskell’s do-notation serves much the same role for DSLs as Ruby’s block notation does. With monads, the semantics of the DSL are determined by how you define bind and return, supplemented by the other functions you’ve defined in the monad.

The Structure of Man is an anatomy course in video form, available on DVD-ROM and YouTube (courtesy of the author).

It seems to be pretty highly recommended, but I’ve not had a chance to really check out any of the videos yet.

Russ Cox writes:

This is a tale of two approaches to regular expression matching. One of them is in widespread use in the standard interpreters for many languages, including Perl. The other is used only in a few places, notably most implementations of awk and grep. The two approaches have wildly different performance characteristics … The trends shown in the graph continue: the Thompson NFA handles a 100-character string in under 200 microseconds, while Perl would require over 10^15 years.

Pretty much all modern regular expression implementations have the same problem. Thompson NFAs were introduced by Ken Thompson in the late 1960s.

Whoops.

Some days, when it comes to programming, it seems like we’ve forgotten more than we’ve ever learned. Another example: take the pool of programmers out there today, and find me one who understands binary arithmetic and bitwise operations. Sure, plenty still exist, but you’ll have to look for them…

(Hat Tip: Lambda the Ultimate)

Well, maybe not too surprising. Need -fglasgow-exts, obviously.

import Data.Typeable
import Data.Dynamic

class IShape a where
  width  :: a -> Int
  height :: a -> Int

data Shape = forall a. (Typeable a, IShape a) => Shape a

instance IShape Shape where
  width (Shape a) = width a
  height (Shape a) = height a

upcastShape :: (Typeable a, IShape a) => a -> Shape
upcastShape = Shape

downcastShape :: (Typeable a, IShape a) => Shape -> Maybe a
downcastShape (Shape a) = fromDynamic $ toDyn a

LambdaVM is a translator from Haskell to JVM Bytecode, based on GHC. YES!

It should be possible to follow Brian’s progress on his blog. Go give him some encouragement!

fastthread 0.6.4.1 is out, featuring two bugfixes:

1. the rb_bug() from stale wait queue entries is fixed
2. there’s no longer an uninitalized variable warning on load

• fastthread-0.6.4.1.gem
• fastthread-0.6.4.1.tgz

(fastthread is also available from RubyForge, courtesy of Zed and the nice folks at mongrel.)

I’m hoping this will be the next-to-last release of fastthread, since its code has tentatively been merged into ruby_1_8, replacing the existing thread.rb, but we’ll see how things go.

Communicating Sequential Processes (i.e. sequential processes which communicate), aka CSP, is a formalism for dealing with the interaction of concurrent processes. It’s been used as the basis for the concurrency APIs of environments like Plan 9 and the Occam language.

Tony Hoare’s excellent book, Communicating Sequential Processes, which introduces and develops the concept, is now available online, free of charge.

Tim Bray summarizes the recent Berkeley survey of trends in parallel computing.

I suppose this is also an opportunity for a first assessment of my own prognostications. Sounds like some of my predictions about parallelism and the treatment of power consumption are looking pretty promsing, while other assumptions (that locks would continue to play a significant role behind the scenes) are probably pretty off-base.

Rrresume 0.1 is a Ruby tool for generating resumes customized for specific positions, selecting from a tagged list of skills, etc. that you provide it with.

The JSR-133 Cookbook dissects the hows and whys of the Java memory model in great detail. A must-read for implementors of VMs for any language.

(Hat Tip: Nick Sieger)

André Pang gave a highly acclaimed talk at LinuxConf.au this year, entitled Concurrency and Erlang; his slides and some supplementary links are now available online.

If concurrency interests you, check out his links section; there’s a lot of meat in there regarding many different languages (not just Erlang).

(Hat Tip: Lambda the Ultimate)

fastthread 0.6.3 is out! The only significant change is that the ConditionVariable class has been made compatible with any mutex class that obeys Mutex’s public interface. This is probably the penultimate fastthread release (the last release will occur after fastthread is merged into 1.8).

• fastthread-0.6.3.gem
• fastthread-0.6.3.tgz

Have at it, kids.

Too little water isn’t a good thing either. In his latest JonesBlog entry, BW Jones segues from a (mercifully circumspect) story about his kidney stone to the wonders of Open Source medical imaging.

Well, it turns out that fastthread was crashing due to a bug in the Ruby interpreter (see bug #7974). 0.6.2 works around the problem by expanding the critical section and using rb_define_class rather than rb_class_new.

• fastthread-0.6.2.gem
• fastthread-0.6.2.tgz

Mega thanks go to Young Hyun, who came up with test cases to help me track this one down.

Here’s a look at five different concurrency models in Ruby, some whose Ruby implementation is entirely hypothetical, and others which I have implemented in some form or another in the past. We’ll be using a simple threadsafe queue with two operations (get and put) as our example.

My purpose here is not to demonstrate their relative advantages or disadvantages—this particular example is overly generous to mutexes and a little unfair to transactions—but rather to convey the general idea of how each of these concurrency techniques is used in practice.

For concurrency models which do not inherently involve queueing, queues will be represented as linked lists made of two-element arrays (in lieu of a built-in Pair class). So, for a list cell, the first element ([0]) will be the value of that list cell, and the second element ([1]) will be a reference to the next cell in the list.

Mutexes and Condition Variables (from Ruby stdlib)

require 'thread'

class MutexQueue
  def initialize
    @lock = Mutex.new
    @ready = ConditionVariable.new
    @head = nil
    @tail = nil
  end

  def put( obj )
    pair = [ obj, nil ]

    @lock.synchronize do
      tail = @tail
      if tail
        tail[1] = pair
        @tail = pair
      else
        @head = @tail = pair
        @ready.signal
      end
    end
  end

  def get
    @lock.synchronize do
      @ready.wait @lock until @head
      head = @head
      rest = head[1]
      if rest
        @head = rest
      else
        @head = @tail = nil
      end
      head[0]
    end
  end
end

This is how you have to do it today.

Futures (after Alice)

require 'concurrent/futures'

include Concurrent::Futures

class FutureQueue
  def initialize
    promise = Promise.new
    @tail = Ref.new promise
    @head = Ref.new promise.future
  end

  def put( obj )
    new_promise = Promise.new
    promise = @tail.exchange new_promise
    promise.fulfill [ obj, new_promise.future ]
  end

  def get
    @head.modify { |pair| pair[1] }[0]
  end
end

Futures act as placeholders and transparent proxies for a pending result. Trying to do anything with a future extracted from a Promise blocks until the promise is fulfilled, at which point the future pretends to be the object passed to Promise#fulfill.

Importantly, Ref#modify sets the value of a ref to a future for the result of the given block (which is passed the old value of the ref) and also returns the old value of the ref.

Software Transactional Memory (after Harris et al.)

require 'concurrent/stm'

include Concurrent::STM

class STMQueue
  def initialize
    @head = Ref.new nil
    @tail = Ref.new nil
  end

  def put( obj )
    pair = [ obj, nil ]

    atomic do
      tail = @tail.value
      if tail
        tail.next = pair
        @tail.value = pair
      else
        @head.value = @tail.value = pair
      end
    end
  end

  def get
    atomic do
      head = @head.value
      atomic_retry unless head
      rest = head[1]
      if rest
        @head.value = rest
      else
        @head.value = @tail.value = nil
      end
      head[0]
    end
  end
end

Note that atomic_retry blocks until another thread updates one of the transactional objects read anywhere up to the point where the transaction was retried (in this particular case, just @head). That prevents the transaction from actually retrying until something has changed which might allow it to make more progress than before.

Actors (after Scala)

require 'concurrent/actors'

include Concurrent::Actors

class ActorQueue < Actor
  Put = Message.new :obj
  Get = Message.new :origin

  def initialize
    super do |recurse|
      actor_receive Get do |get|
        actor_receive Put do |put|
          get.origin.actor_send( put )
          recurse.call
        end
      end
    end
  end

  def put( obj )
    actor_send( Put.new( obj ) )
  end

  def get( &cont )
    actor_send( Get.new( Actor.current ) )
    actor_receive( Put ) { |put| cont.call put.obj }
  end
end

Note that if this actor implementation used “heavyweight actors” (one thread per actor), or took advantage of Ruby’s callcc, the explicit continuation passing would be unnecessary; as it is, every actor_receive unrolls the stack back to the message loop, taking an explicit continuation as a block, just as in Scala.

It’s not uncommon for real actor code to wait on more than one type of message at a time, with a different continuation for each pattern. The API shown here accepts multiple arguments to actor_receive, but that still means an extra round of pattern matching in the body of the continuation.

Perhaps there’s a better way of doing actors in Ruby.

Joins (after Cω)

require 'concurrent/joins'

include Concurrent::Joins

class JoinQueue < Join
  async :put
  sync :get, :arity => 0

  chord :get, :put do |obj|
    obj
  end
end

Yes, really.

The idea is that you define method bodies responding to particular combinations of methods — chords — which may be called from various threads. sync methods wait for a matching chord to be invoked. async methods are non-blocking, simply recording the fact that they were called. Calls to both method types will be queued if they go unmatched, hence queued calls to :put form the basis of our queue.

Since :get is synchronous, the result of the block becomes its return value. Both synchronous and asynchronous methods can contribute chord arguments, but since here :get has no arguments (arity zero), only :put contributes an argument to the block.

Conclusion

Notice that a common feature of all of these models is not only the ability to do something atomically, but also the ability to perform an (atomic) blocking wait for some condition to be satisfied. Both ingredients are necessary for a successful concurrency model.

Hopefully this gives you a basic idea of what it would be like to program with these concurrency models in Ruby. The 'concurrent/*' libraries don’t really exist yet, but maybe someday…

Addendum

As noted in the introduction, comparing the advantages and disadvantages of the various models soley on the basis of the examples above can be a bit misleading. Here’s a follow-on example which illustrates what I mean:

Problem:

Given the following routine:

def get_two( a, b )
  [ a.get, b.get ]
end

How can you modify the code to ensure that get_two will never consume a value from one queue without consuming a value from the other?

Solution for STM:

Rewrite get_two as follows:

def get_two( a, b )
  atomic { [ a.get, b.get ] }
end

Solution for the rest:

Exercise for the reader…

Here’s a gem from Paul Johnson about the relationship between composable code and productivity.

Surprisingly, program state generally is a source of non-composability. Mutable state is actually another form of manual memory management: every time you over-write a value you are making a decision that the old value is now garbage, regardless of what other part of the program might have been using it.

Men in a state of decadence employ professionals to fight for them, professionals to dance for them, and a professional to rule them.

—G.K. Chesterton, Twelve Types

You’ll need an SVG-enabled browser (e.g. Firefox 2.0), but this SVG clock by Tavmjong Bah (using some gear-generation code by Aaron Spike) is just fricking cool!

A memory barrier, in the sense we’ll concern ourselves here, is an instruction which forces both the CPU to ensure that any preceding reads and/or writes (depending on the type of barrier) are completed before continuing. On most SMP architectures, locking primitives must use them in order to guarantee that client code will have a consistent view of memory after entering or leaving a critical section.

Since the compiler can also reorder reads and writes on its own, it’s often necessary to use memory barrier instructions via inline functions with annotations to force appropriate behavior on the part of the compiler.

Paul McKenny’s 2005 article in Linux Journal, Memory Ordering in Modern Microprocessors, Part I is a good introduction to the properties of contemporary hardware which make the use of memory barriers necessary.

Update: Part II, which describes the behavior of specific architectures, may be of particular interest to the writers of JIT compilers.

Blasphemy is an artistic effect, because blasphemy depends upon a

—G. K. Chesterton, Heretics

The literature-map is a comparative map of authors. Enter an author’s name, and it shows you a cluster of similar authors. The closer an author’s name appears to the selected author, the more likely they are to have fans in common (maybe you!).

It’s a spinoff of gnooks, which is interesting in its own right.

I’ve not had time to mess with my Ruby STM implementation in a while, but in case anyone’s curious, what I’ve got is available from this git repository:

http://moonbase.rydia.net/software/ruby-stm/ruby-stm.git

I guess this was partly prompted by the recent ruby-talk mention of STM in Rubinius ... I don’t know whether my STM library is exactly what they’re looking for, but I’d hate to see work duplicated if it’s close.

Ah, one issue I have to deal with now that there can be mutex-using code in flight at the time fastthread is required: the replacement of the classes needs to happen atomically. Hence fastthread 0.6.1.

• fastthread-0.6.1.gem
• fastthread-0.6.1.tgz

Fastthread 0.6 is out, which should address the trouble folks have had with the require order. Fastthread now replaces rather than modifies the original classes.

Oh, and that means it’s now compatible with RubyGems again!

• fastthread-0.6.gem
• fastthread-0.6.tgz

Thanks Eric and Ezra!

Merry Christmas, everyone!

Another ultraminor release; this one fixes a dumb type error and tries to match stdlib’s semantics more closely in the case of recursive lock attempts.

• fastthread-0.5.3.5.gem
• fastthread-0.5.3.5.tgz

Thanks for the heads-up, Blaine!

Okay, yet another compile fix, this time so it builds against latest ruby_1_8. You know the drill.

• fastthread-0.5.3.4.gem
• fastthread-0.5.3.4.tgz

Thanks for the report, Kirk!

• fastthread-0.5.3.3.gem
• fastthread-0.5.3.3.tgz

I’ve just released 0.5.3.2 which should fix compilation on Windows.

• fastthread-0.5.3.2.gem
• fastthread-0.5.3.2.tgz

Thanks for the fix, Luis!

• fastthread-0.5.3.1.gem
• fastthread-0.5.3.1.tgz

Thanks for the catch, zimbatm!

I’ve just released fastthread 0.5.3, which is mostly a bugfix release—SizedQueue has been horribly broken in many of the prior releases, but I think this one finally puts the bugs to bed.

• fastthread-0.5.3.gem
• fastthread-0.5.3.tgz

Today’s annoyance: if you inquire about a range of revisions for a path which no longer exists in the most current revisions of the repository, SVN simply says the path doesn’t exist instead of giving you information about the revisions in the range which do exist. This necessitates an annoying binary search to find the last revision which does exist so you can trim your range and try again.

Annoying when you just need to look at the output of svn log, that is. Many scripts for automating things in svn simply don’t take this case into account, and fail.

Chris Neukirchen writes a very good article about abstraction, its importance, and the ways in which education can and can’t address its development as a skill.

Being able to abstract is the most important thing, because it multiplies our brain power. Alexandre Borovik writes in the draft for Mathematics under the Microscope:

In our conscious and totally controlled reasoning we can process about 16 bits per second. In activities related to mathematics this miserable bit rate is further reduced to 12 bits per second in addition of decimal numbers and to 3 bits in counting individual objects.

It is completely obvious that we need to fit big ideas into these few bits to be successful thinkers, by omitting what’s irrelevant.

iGo’s power adapters looks like an interesting way to deal with “wall wart hell”. Anyone had experience (good or bad) with their products?

The PLRE is a search engine dedicated to programming language research, based on Google Coop.

Thanks Botty!

Decided to post this here for the benefit of others.

In response to a question I asked on the cairo list last year, Ross McFarland responded with instructions on how to link against a special development version of a library rather than the one installed on your system. The most important bit is this:

you can set the following:
    PKG_CONFIG_PATH=$HOME/local/lib/pkgconfig
    LD_LIBRARY_PATH=$HOME/local/lib
    export PKG_CONFIG_PATH LD_LIBRARY_PATH

and then configure modules to install as such:
    ./configure --prefix=$HOME/local

Thanks Ross!

Note: this works best with libraries which use pkg-config.

fastthread is a library which replaces the synchronization primitives defined in stdlib’s thread.rb (Mutex, ConditionVariable, Queue, and SizedQueue) with optimized versions which:

• are much faster (in the non-contention case, speed comparable to direct use of Thread.critical or Thread.exclusive)
• don’t leak memory (the stdlib implementation of Mutex manages to trigger worst-case behavior of a memory leak in Array)

To use it, simply require 'fastthread' before you require 'thread'. Provided you don’t muck with thread.rb’s internals, your code should work with no additional modification.

0.4 is primarily a robustness/bugfix release. There is both a gem and a tarball available:

• fastthread-0.4.gem
• fastthread-0.4.tgz

Doing some Win32 programing for $work at the moment, and once again I’m faced with the prospect of straddling several different API sets to get the job done properly (and portably, in the sections that don’t NEED to do anything Windows-specific). One of the most annoying things is having to deal with all the different sorts of file handles available.

This article has helped me navigate those murky waters:

Koen Claessen’s classic paper demonstrates the use a monad transformer to add (cooperative) concurrency to many ordinary monads.

(Hat Tip: Anarchaia)

Haskell’s type classes have always bugged me; they’re useful, but they feel like an awkward hack. On the other hand, ML modules have always struck me as too fiddly and verbose to be useful. The authors of this paper try to meld the best of both worlds.

Abstract

ML modules and Haskell type classes have proven to be highly effective tools for program structuring. Modules emphasize explicit configuration of program components and the use of data abstraction. Type classes emphasize implicit program construction and ad hoc polymorphism. In this paper, we show how the implicitly-typed style of type class programming may be supported within the framework of an explicitly-typed module language by viewing type classes as a particular mode of use of modules. This view offers a harmonious integration of modules and type classes, where type class features, such as class hierarchies and associated types, arise naturally as uses of existing module-language constructs, such as module hierarchies and type components. In addition, programmers have explicit control over which type class instances are available for use by type inference in a given scope. We formalize our approach as a Harper-Stone-style elaboration relation, and provide a sound type inference algorithm as a guide to implementation.

(Hat Tip: Anarchaia)

(Not having actually played yet…)

The Bad: The player (in most instances) has been replaced by a very small shell script.

The Good: You get to write the shell script.

Learned about Soulseek today. That’s an interesting concept for matching up people with similar tastes. There’s a Unix client in Python as well.

Update: A reader reports that pysoulseek is a dead project, and recommends its successor Nicotine+ instead.

Update: latest version of fastthread is 0.6.1

I’ve made the latest version of my optimized locking work available as a gem and a tarball:

• fastthread-0.1.gem
• fastthread-0.1.tgz

In its current incarnation, it’s a ‘fastthread’ library which you require before ‘thread’ (e.g. on the commandline via -r); it essentially replaces the existing Mutex, ConditionVariable, Queue and SizedQueue classes with faster versions, giving any applications using the existing standard locking primitives a speed boost (and a cure for the nasty memory leaks in the stdlib versions of those same classes).

Next, I will add replacements for Mutex_m, Sync, and Sync_m. After that, and after the optimized classes get considerable field testing, I will look at turning all of this into a patch to Ruby itself, replacing the current stdlib locking stuff.

A git repository for keeping up with the latest fastthread developments is available here:

http://moonbase.rydia.net/software/optimized-locking/optimized-locking.git#fastthread

So, now that Open Source developers are returning to the JVM, how long before we see something like IKVM to run CLR bytecode on the JVM? I ask since now that Sun’s releasing the Java 7 libraries under the same license as GNU Classpath, mono with IVKM should soon be able to run Java programs just about as well as Sun Java, in addition to all the usual software for the CLR. It seems like it would be in Sun’s best interest for someone to address that asymmetry.

Ruby’s ObjectSpace is one of those things like Thread.critical that is used by critical things, but is a bear to implement and therefore aggravates Ruby implementors quite a lot.

So far as I can tell, there are three main uses for it in the wild:

1. Find all descendants of a class.
2. Find all instances of a class.
3. Weak/”serializable” references (via ObjectSpace._id2ref)

Are there any others? As with Thread.critical, it is facility perhaps too general for its own good. If we can find other ways to address those needs which is is actually used to address, we can reasonably think about removing it.

Update: the issue is specifically that ObjectSpace is impossible to implement efficiently when you don’t control the GC. As a consequence, JRuby (for example) provides an -O option to turn it off for performance. In the case of Thread.critical, it’s actually impossible to implement reliably on the JVM or with concurrent POSIX threads.

So, it’s a question of either making such features of the language optional (on a de-facto basis if nothing else), or finding replacements which we can guarantee will be available on all Ruby implementations.

I much prefer the latter option, keeping portability of Ruby programs across different implementations.

Adam Sternbergh says in New York Magazine what I’ve been saying for years: to be satisfying, narratives need a definite end and a definite underlying reality.

The destination makes the journey.

Just ran across an excellent reading of Robert Service’s The Cremation of Sam McGee. The video’s fitting, albeit nothing spectacular, but the audio … ohh. It’s wonderful.

It isn’t so much that pure functional programming is inherently slow, but rather that we’re still learning how to do things efficiently with it.

It seems that in 2001, Chakravarty and Keller moved us just a little further along:

This paper introduces a new approach to optimising array algorithms in functional languages. We are specifically aiming at an efficient implementation of irregular array algorithms that are hard to implement in conventional array languages such as Fortran. We optimise the storage layout of arrays containing complex data structures and reduce the running time of functions operating on these arrays by means of equational program transformations. In particular, this paper discusses a novel form of combinator loop fusion, which by removing intermediate structures optimises the use of the memory hierarchy.

We identify a combinator named loopP that provides a general scheme for iterating over an array and that in conjunction with an array constructor replicateP is sufficient to express a wide range of array algorithms. On this basis, we define equational transformation rules that combine traversals of loopP and replicateP as well as sequences of applications of loopP into a single loopP traversal.

Our approach naturally generalises to a parallel implementation and includes facilities for optimising load balancing and communication. A prototype implementation based on the rewrite rule pragma of the Glasgow Haskell Compiler is significantly faster than standard Haskell arrays and approaches the speed of hand coded C for simple examples.

It’s a shame this stuff takes half a decade to really start circulating.

(Hat Tip: Anarchaia)

Since Thread.critical will be going away with Ruby 1.9 (not to mention the pain it’s been for other Ruby implementors), I decided to remove the main reason most programs use it: the fact that stdlib’s Mutex is slow.

Most of Mutex’s performance problems come from two sources:

1. It involves a lot of Ruby method calls
2. It uses a dynamically sized array to maintain its wait list

To that end, I:

1. Rewrote Mutex in pure C (big savings)
2. Switched to using a double-headed linked list (O(1) get and put)
3. Used a per-mutex memory pool for list entries (so malloc overhead doesn’t kill us)

The end result is actually faster than using Thread.critical directly! Even Mutex#synchronize, with its block call, is faster than the typical:

saved = Thread.critical
Thread.critical = true
begin
  # ...
ensure
  Thread.critical = saved
end

Here’s a git repository where you can check out my work:

http://moonbase.rydia.net/software/optimized-locking/optimized-locking.git

I’ve also put up a snapshot tarball for the git-disinclined.

I’ll be working on condition variables next. If they also turn out fast, then purging most explicit uses of Thread.critical from stdlib may become a real possibility.

uri-relative is a little library which adds relative URI manipulation to Ruby’s URI::Generic class. It’s modeled a bit after the facilities provided by Java’s URI class.

Anyway, I’ve still got to implement URI::Generic#relativize, but aside from that it should already be useful.

Well… just this once. It’s a rather interesting quiz.

Kwangkeun Yi of Seoul National University’s School of Computer Science and Engineering revisits Robert Harper’s classic “Proof-Directed debugging” article in the Journal of Functional Programming. This time, with much simpler examples.

(Hat Tip: Lambda the Ultimate)

Neil Gaiman writes on the importance (and ease) of setting up a will to take care of your literary estate.

The fact is that your copyrights are likely to outlive you. Unless you take special action, they may well end up in the hands of people who do not share your beliefs or philosophy.

But this isn’t just an issue for writers—software is also subject to copyright. Programmers need to take care of this stuff too.

On the Haskell Wiki, learn about best practice for creating a new Haskell program or library.

(Hat Tip: Anarchaia)

The brilliant sigfpe has hand-illustrated a nmber of common monads. It’s great to have a mental picture of these things, and I think I finally understand monad transformers, to boot.

Consider this a public service announcement: your code could very well be broken.

Ben Maurer has an article about edge cases in C#’s Math.abs. However, it’s not merely some weird C# thing.

The trouble is this: the range of signed twos-compliment integers (read: most integer types in nearly all languages) are larger on the negative than the positive side. For example, a signed 16-bit integer ranges from -32,768 to 32,767, just as a a signed 32-bit integer ranges from -2,147,483,648 to 2,147,483,647.

The practical upshot? Within the range of every particular fixed-precision integer type there is a negative number which has no positive equivalent. For such numbers, integer abs() and even negation are essentially undefined.

This has been the source of a lot of bugs.

If you’re writing in Ruby or another language with automatic Bignums, you’re okay (but watch those C extensions…). Everyone else? Check your code!

Incidentally, while you’re checking your code, here are two previous “public service” articles, drawing attention to two other widespread bugs:

• Your Binary Search is Probably Broken
• Double-Checked Locking Considered Broken

P.S.: code written in Ruby is also immune to the binary search bug, again because of automatic integer embiggening. At this point, I think designing a new scripting language without a builtin bignum type and automatic promotion would be simply irresponsible.

Hints for computer system design is an article written by Butler W. Lampsen and published in the ACM Operating Systems Review in 1983. Its wisdom, however, is timeless.

For shame!

Actually, most of these are part of grey-box/white-box tests, so that’s not really so bad. Still, though…

(Hat Tip: Anarchaia)

The Loose Change 2nd Edition Viewer Guide is an invaluable resource when watching Loose Change.

In Search of the One True Layout is a careful documentation of the various methods available for doing flexible pure-CSS layouts in the absence of uniform browser support for CSS tables. Destined to become a classic, it also seems to be somewhat regularly updated with implementation notes and reader contributions.

Position is Everything is a pretty cool site in general, by the way.

Sigh. It seems like, when it comes to religious reporting, it’s getting harder to tell the difference between laziness, incompetence, and malice on the part of the UK press. Most recently, it’s the BBC Panorama special on the ostensible unveiling of a “secret vatican document” issued by Cardinal Ratzinger (now Pope Benedict) supposedly sheltering clerical abusers of children and adolescents.

Amy Wellborn does a nice job of treating the topic, including the fact that the “secret” document in question had been openly published after being issued in 2001, and also taking a look at what the document actually says.

Now, there certainly are a few cardinal bishops who have held on to their positions by supressing evidence of their wrongdoing, and done a lot of damage to their flock and the Church besides (those familiar with the landscape of the Catholic Church in the US probably know who I’m talking about). If only some investigative journalists would pay some attention to them rather than trying to manufacture news about Cardinal Ratzinger…

Former Slashdot editor pudge checks RFK’s sources. Jaskeet Sekhon, one of the statistical experts who worked on the DNC’s Ohio voting report claims:

RFK’s article is misconceiving, socially damaging and simply wrong—much

(As an aside, Sekhon does believe that the butterfly ballot fiasco cost Gore the election in 2000. His report looks pretty damning, though I’m admittedly not a statistician.)

But also, in a way I think this may be becoming a useful distraction from our current, much graver problem: easily manipulable electronic voting machines. Going on about Ohio without addressing electronic voting is a bit like arguing over who forgot to change the batteries in the smoke detector last week while you’re still living in a wooden fire trap stuffed to the ceiling with oily rags.

While butterfly ballots and partisan influence in the allocation of voting machines may invite convenient incompetence, electronic voting is a playground for active malfeasance, and I’ve no particular reason to trust the Republicans or the Democrats. (It’s nice being an independent.)

In the wake of Bush’s interview with Matt Lauer, Rod Dreher comments on the administration’s posturing over torture.

Lackadaisy is a manic tale of bootleggers and mayhem in Prohibition-era St. Louis, told with cute cartoon kitties.

Anko at Munkey Film has a writeup on making your own tripod light probe mount.

(Hat Tip: MAKE)

I guess everyone saw this coming. I guess I’d rather integrated browser support anyway though. Just—it kind of sucks for Internet Explorer users.

Let’s be as succinct about this as possible: Metal Wolf Chaos is a video game, wherein the President of the United States straps on a mecha suit to overturn the military coup orchestrated by his former Vice-President (who sports an Evil Villain Beard that would make Al Gore envious).

Here’s the Video.

Best quote (towards the end, as our tank-chucking President clings to the side of a launching spacecraft):

Nothing is pointless! And the reason is—because I am the President of the great UNITED STATES OF AMERICA! YEEEEAAAAAAAAAAAAHHHH!

Only in Japan.

According to Reuters, Pope Benedict XVI and his formal doctoral students have unexpectedly decided to publish the proceedings of this year’s Schuelerkreis, where the topic was evolution. A yearly open-ended discussion between the former professor and his students on a chosen topic, the Schuelerkreis has no special religious significance, though hopefully it should prompt some much-needed philosophical discussion.

Since the Reuters article does do a better job than most of summing up the Church’s position on these things, I think it’s worth quoting at length:

Unlike creationists who oppose the theory of evolution, the Catholic Church does not read literally the Biblical account of God creating the world in six days.

Benedict and Schoenborn have said several times over the past year that intelligence in the form of God’s will played a part in creation and that neo-Darwinists who deny God any role are drawing an ideological conclusion not proven by the theory.

They say they use philosophical reasoning to conclude that God created the world, not arguments which intelligent design supporters claim can be proven scientifically.

“There’s a controversy in the United States because there is a lack of awareness of a thing called philosophy,” said [Father Joseph Fessio, S.J., an attendee], whose Ignatius Press publishes Benedict’s books in English.

The only minor quibble I have with the reporter’s summary is that while the Church doesn’t interpret the first chapter of Genesis “literally” in the colloquial sense of the word (i.e. the way Fundamentalists generally do), nor in a way that would appear to conflict with science, She does take it very seriously, and not soley as a spiritual metaphor. If you’re interested in a more thorough treatment of that subject, I might recommend Reading Genesis with Cardinal Ratzinger, which I linked to in an earlier post.

TSE3 is a GPLed MIDI sequencer engine written in C++.

Just the fact that this has been attempted gives me a lot of hope for the future of graphic narrative in the US.

(The endorsement by Stan Lee is kind of a kick in the teeth, though, given that his superhero fixation is one of the reasons it’s so hard to market non-superhero comics today in the first place.)

Nick Lowe’s The Well-Tempered Plot Device is a classic essay on how not to write SF/Fantasy.

Here we go. A well-regarded Latin course that is actually available in book form, at reasonable prices: Lingua Latina. I might actually try this one.

Erin Kissane writes on what makes an about page work.

(Hat Tip: Anarchaia)

Here are four Open Source 3D engines:

1. Ogre3D – LGPLed, OpenGL/D3D
2. Irrlicht – ZLIB-licensed, OpenGL/D3D
3. Sauerbraten – ZLIB-licensed (plus restrictions on sample content), OpenGL
4. Crystal Space – LGPLed, OpenGL

Most have rudimentary physics support. For more sophisticated rigid body physics, it should be possible to integrate them with one of the open source physics engines, among which are:

1. Bullet – ZLIB-licensed
2. Open Dynamics Engine – BSD-licensed

There is also OPAL, which is a somewhat physics-engine-neutral wrapper around other physics engines, providing high-level features like motors, sensors, joints, etc.

So, the next time you need an engine for an interactive 3D project, have a look at this list and ask yourself whether you really need to license a proprietary one.

Update: a reader also points out Apocalyx, a GPLed 3D engine based on OpenGL. The GPL (versus LGPL) license might be a problem for non-GPLed projects, but GPLed projects may find it useful.

Update: We’ve got rendering and physics covered above, but it’s probably also worth hightlighting OpenAL, an LGPLed library for 2D and 3D audio, which has been used by a number of well-known commercial games.

One of those moments today where I regret living in the US: my cellphone goes off, and bystanders start making Al Queda jokes because the ringtone has a mostly pentatonic scale.

I’m sure everyone’s seen one of those long-exposure photographs where someone’s used a glowstick or a flashlight to “draw” on the image plane— but what if this technique were used for animation? Here’s what that looks like.

Awesome. (Thanks Brandon!)

Archbishop Chaput of Denver has written a really excellent article for the Denver Catholic Register about the Christian-Muslim conflict: crucial to reconciliation is reciprocal honesty and repentance, in particular a willingness to acknowledge history.

As I’ve written before, Christianity is not a Western innovation. The Middle East was Christian long before it was Muslim, and its mass conversion to Islam was not a peaceful one.

(Hat Tip: Insight Scoop)

The Travel Insider has a nice FAQ about unlocking your GSM phone.

Stack machines are cool and all, but doesn’t having the stack destroy any chances for parallelism, since it serializes any computations that work with it?

Update: I am, of course, referring to the recent interest in pure stack machines on Slashdot and so forth. The trouble with pure stack machines is that they make it much harder to do instruction reordering, parallel instruction execution, and optimistic execution, techniques which are used to great effect architectures which use registers in addition to a stack.

brothercake’s svgIR is a promising script to replace text with SVG graphics in an accessible and cross-browser fashion. Unfortunately, it doesn’t appear to work in Firefox yet, even though it should in principle.

So, I’m in the mood for some prognostication today. Assuming the whole notion of programming isn’t rendered irrelevent by Singularity (hah!), a new Global Dark Age, or the Second Coming, here’s what I think we can expect to see in the next ten years:

1. Energy considerations will begin to dominate computing.
   • The notions of optimizing for speed and optimizing for power consumption will begin to converge.
   • Energy efficiency will become a selling point for all “consumer” computing devices (not just battery-dependent ones).
   • We will see the beginnings of hardware and software infrastructure for energy accounting similar to that available for CPU time. This includes profilers.
   • Fine-grained billing for use of computer resources will make a little bit of a comeback. People will still prefer flat rates.
   • “Ubiquitous” computing will become popular in developed regions, but energy economies of scale (and a desire to avoid contact burns from high-powered portable devices) will be a selection pressure towards a network of just-dumb-enough nodes and centralized computers.
   • Many things will turn out to be cheaper to do than to simulate.
2. Restricted access to hardware will become an increasing problem for Open Source (and everyone else too).
   • Microsoft will enter IP cross-licensing agreements with selected hardware vendors for the computing devices it manufactures. These vendors will subsequently be unable to release documentation or Open Source drivers for any hardware which uses the cross-licensed IP.
   • Widespread implementation of “Trusted Computing” will make who gets to determine what software can run on a particular piece of hardware a major issue. There will be a battle over whether mainline gcc should include support for code signing.
   • Because of remote attestation, people may find themselves carrying separate, otherwise redundant, devices in order to communicate with different “domains of trust”.
   • The workarounds necessary to function in such an environment will open many new avenues for social engineering attacks.
3. Having exhausted the “do everything in sequence as fast as possible” avenue, systems designers will try to attain performance by becoming increasingly parallel and asynchronous.
   • Declarative programming languages will become the more efficient option over imperative ones, not so much as a result of powerful new optimization techniques, but rather because hardware and software environments will become more suitable to declarative approaches and less suitable to imperative approaches.
   • The management of many resources programmers (and even users) are accustomed to managing manually will become abstracted and automated out of necessity. Locks will be the first victim. However, a careful understanding of the way in which they are managed behind the scenes will be necessary to avoid pathological cases.
   • Again out of necessity, optimistic resource management techniques will become an increasingly popular area of research, to be followed by frantic research on how to mitigate or avoid the worst-case scenarios introduced by the use of optimistic strategies.
   • The C/C++ family of languages (which includes Java and C#) will eventually experience a crisis as they become increasingly inefficient on the contemporary hardware. C++ will attempt to solve it by introducing more template libraries. C# will attempt to solve it by becoming a concurrent ML dialect. Java will attempt to solve the problem by pretending there isn’t one. C will attempt to solve the problem by not caring.
   • Ruby will mutate into something resembling Erlang, hopefully without losing its Ruby-ness.
   • Perl 6 will be well-suited to the new environment, but will have difficulty overcoming the fact that it really, really freaks people out. It will also never be finished, although that fact will not stop people from writing useful programs in it.
   • Some problems will not parallelize well, even on a quantum computer.

Some of these things are obvious, some are silly… and some are already happening. We’ll check back in a few years to see how I’m doing.

Portal looks like a very, very, interesting HL2 mod. Simply being able to stitch two bits of space together with an arbitrary portal is really quite powerful, and evokes some of the things I played with in the Lunar 8 scripts, but taken to the extreme logical conclusion.

Well, I’m back from DDC. In my opinion the conference itself left something to be desired, but I got to meet some great people and hang out with rejon and Bryce and that was awesome.

Adventure in Prolog is a rather decent online book covering introductory-level Prolog. In particular, I like how it explains the general operation of a Prolog interpreter—a thing most other introductory texts fail to do clearly.

I think it’s important that a tutorial convey enough information for a reasonably skilled programmer to write a working (if not efficient) implementation of the language subset covered.

So far:

1. Ruby STM: First Round
2. Ruby STM: Round Two
3. STM Deadlocks
4. Ruby STM: Round the Third
5. Misplaced Optimism

Another feature I’d wanted for my Ruby STM library was the ability to assign a timeout to a (sub-)transaction. It’s obvious enough how to do this for transactions, but sub-transactions? Well, what does a timeout on a sub-transaction mean, anyway? And how would you implement it?

One of the chief difficulties is that a transaction can be retried arbitrarily many times. Say the sub-transaction times out, but the parent transaction retries. Should the sub-transaction be retried? Probably not—but if not, how do we associate a particular section of code with a sub-transaction? If so, do we simply restart the clock? What about reentrancy? Are any of those behaviors really useful?

Then I went back and reread Discolo, et al. As usual, seeing the problem formulated in Haskell made it a lot clearer— in the paper, the type of pollSTM is ArrayBlockingQueueSTM e -> STM (Maybe e), whereas the type of pollTimeoutSTM is ArrayBlockingQueueSTM e -> TimeDiff -> IO (Maybe e). In other words, timeouts don’t compose. You have to assign a timeout to an entire transaction, or not at all.

On the other hand, the concern I had in part two—that timeouts would require special treatment by the transaction scheduler—turned out to be unfounded. It’s true that transactions can block on each others’ locks, but they won’t do so for long periods of time. If a transaction needs to block for long periods (i.e. due to a retry), then it will release all of its locks and allow other transactions to proceed. As a result, something like the naive implementation of timeouts I had originally proposed should work just fine:

def timeout( duration )
  timed_out = Atomic::Variable.new
  Thread.new { sleep duration ; timed_out[] = true }
  Atomic.atomic do
    result = nil
    if Atomic.retries? { result = yield }
      Atomic.retry unless timed_out[]
      raise Atomic::TimeoutError
    end
    result
  end
end

The only additional requirement is a bit of logic to raise an error if someone attempts to call timeout from within an existing transaction.

Here’s a wonderful exhibition by Japanese artist Hajime Emoto: The Museum of Fantastic Specimens. Each carefully preserved grotesque is lovingly handcrafted from paper, modeling paste, and bamboo—think Fiji Mermaid meets Lovecraft (particularly this room).

(Hat Tip: Pink Tentacle, whose summary is very helpful for those who cannot read Japanese)

This series looks rather interesting. I like the blend of 2d and 3d conventions.

Earlier:

1. Ruby STM: First Round
2. Ruby STM: Round Two
3. STM Deadlocks
4. Ruby STM: Round the Third

For Round Two, I identified optimistic concurrency control as a desirable feature for our STM implementation. In a nutshell, optimistic concurrency control means avoiding locks in favor of methods to passively detect whether a transaction reads inconsistent data during its execution, and retrying it if so. In this sense, GHC’s STM implementation is entirely optimistic; it uses a versioning scheme to detect if one transaction has conflicted with another. Meanwhile, Ennals’ C STM implementation (after which my STM library was originally patterned) uses locking for writes, but an even more optimistic strategy for reads.

The trouble with optimistic strategies is that validation only at the end of a transaction isn’t sufficient, becuase one of the possible outcomes of working with inconsistent state is an infinite loop. On the other hand, validating the transaction at every read (which would prevent the loop) is prohibitively expensive. Additionally, the loop might not involve any transactional operations (involving only local variables, say) which would otherwise provide us an easy foothold to perform periodic validation. So, we are faced with periodically interrupting the transaction at arbitrary points to ensure that it is still valid, and that requires the connivance of the scheduler.

Sadly, hooking into Ruby’s thread scheduler isn’t an easy option for a pure Ruby library, or even for a C extension. As a result, Ruby STM will remain entirely lock-based for now. Next time, we’ll take a look at timeouts, which turn out to be easier than expected to implement in some ways, but much more difficult in others.