Older blog entries for wingo (starting at number 407)

inside full-codegen, v8's baseline compiler

Greetings to all. This is another nargish article on the internals of the V8 JavaScript engine. If that's your thing, read on. Otherwise, here's an interesting interview with David Harvey. See you laters!


Today's topic is V8's baseline compiler, called "full-codegen" in the source. To recall, V8 has two compilers: one that does a quick-and-dirty job (full-codegen), and one that focuses on hot spots (Crankshaft).

When you work with V8, most of the attention goes to Crankshaft, and rightly so: Crankshaft is how V8 makes code go fast. But everything goes through full-codegen first, so it's still useful to know how full-codegen works, and necessary if you go to hack on V8 itself.

The goal of this article is to recall the full-codegen to mind, so as to refresh our internal "efficiency model" of how V8 runs your code (cf. Norvig's PAIP retrospective, #20), and to place it in a context of other engines and possible models.

stack machine

All JavaScript code executed by V8 goes through full-codegen, so full-codegen has to be very fast. This means that it doesn't have time to do very much optimization. Even if it did have time to do optimization (which it doesn't), full-codegen lacks the means to do so. Since the code hasn't run yet when full-codegen compiles it, it doesn't know anything about types or shapes of objects. And as in other JS engines, full-codegen only compiles a function at a time, so it can't see very far. (This lets it compile functions lazily, the first time they are executed. Overall syntactic validity is ensured by a quick "pre-parse" over the source.)

I have to admit my surprise however at seeing again how simple full-codegen actually is: it's a stack machine! You don't get much simpler than that. It's shocking in some ways that this is the technology that kicked off the JS performance wars, back in 2008. The article I wrote a couple years ago does mention this, but since then I have spent a lot of time in JSC and forgot how simple things could be.

Full-codegen does have a couple of standard improvements over the basic stack machine model, as I mentioned in the "two compilers" article. One is that the compiler threads a "context" through the compilation process, so that if (say) x++ is processed in "effect" context, it doesn't need to push the initial value of x on the stack as the result value. The other is that if the top-of-stack (ToS) value is cached in a register, so that even if we did need the result of x++, we could get it with a simple mov instruction. Besides these "effect" and "accumulator" (ToS) contexts, there are also contexts for pushing values on the stack, and for processing a value for "control" (as the test of a conditional branch).

and that's it!

That's the whole thing!

Still here?

What about type recording and all that fancy stuff, you say? Well, most of the fancy stuff is in crankshaft. Type recording happens in the inline caches that aren't really part of full-codegen proper.

Full-codegen does keep some counters on loops and function calls and such that it uses to determine when to tier up to Crankshaft, but that's not very interesting. (It is interesting to note that V8 used to determine what to optimizing using a statistical profiler, and that is no longer the case. It seems statistical profiling would be OK in the long run, but as far as I understand it didn't do a great job with really short-running code, and made it difficult to reproduce bugs.)

I think -- and here I'm just giving my impression, but fortunately I have readers that will call my bullshit -- I think that if you broke down basic JavaScript and ignored optimizable hot spots, an engine mostly does variable accesses, property accesses, and allocations. Those are the fundamental things to get right. In a browser you also have DOM operations, which Blink will speed up at some point; and there are some domain-specific things like string operations and regular expressions of course. But ignoring that, there are just variables, properties, and allocations.

We'll start with the last bit. Allocation is a function of your choice of value representation, your use of "hidden classes" ("maps" in V8; all engines do the same thing now), and otherwise it's more a property of the runtime than of the compiler. (Crankshaft can lower allocation cost by using unboxed values and inlining allocations, but that's Crankshaft, not full-codegen.)

Property access is mostly handled by inline caches, which also handle method dispatch and relate to hidden classes.

The only thing left for full-codegen to do is to handle variable accesses: to determine where to store local variables, and how to get at them. In this case, again there's not much magic: either variables are really local and don't need to be looked up by name at runtime, in which case they can be allocated on the stack, or they persist for longer or in more complicated scopes, in which case they go on the heap. Of course if a variable is never referenced, it doesn't need to be allocated at all.

So in summary, full-codegen is quick, and it's dirty. It does its job with the minimum possible effort and gets out of the way, giving Crankshaft a chance to focus on the hot spots.


How does this architecture compare with what other JS engines are doing, you ask?

I have very little experience with SpiderMonkey, but as far as I can tell, with every release they they get closer and closer to V8's model. Earlier this month Kannan Vijayan wrote about SpiderMonkey's new baseline compiler, which looks to be exactly comparable to full-codegen. It's a stack machine that emits native code. It looks a little different because it operates on bytecode and not the AST, as SpiderMonkey still has an interpreter hanging around.

JavaScriptCore, the WebKit JavaScript engine, is similar on the surface: it also has a baseline compiler and an optimizing compiler. (In fact it's getting another optimizing compiler soon, but that's a story for another article). But if you look deeper, I think JSC has diverged from V8's model in interesting ways.

Besides being a register machine, a model that has inherent advantages over a stack machine, JavaScriptCore also has a low-level interpreter that uses the same calling convention as the optimizing compiler. I don't think JSC is moving in V8's direction in this regard; in fact, they could remove their baseline compiler entirely, relying instead on the interpreter and the optimizing compiler. JSC also has some neat tricks related to scoping (lazy tear-off); again, a topic for some future article.


The field is still a bit open as to what is the best approach to use for cold code. It seems that an interpreter could still be a win, because if not, why would SpiderMonkey keep one around, now that they have a baseline compiler? And why would JSC add a new one?

At the same time, it seems to me that one could do more compile-time analysis at little extra cost, to speed up full-codegen by allocating more temporaries into slots; you would push and pop at compile-time to avoid doing it at run-time. It's unclear whether it would be worth it, though, as that analysis would have to run on all code instead of just the hot spots.

Hopefully someone will embark on the experiment; it should just be a simple matter of programming :) Until next time, happy hacking!

Syndicated 2013-04-18 15:45:20 from wingolog

thoughts on blink

So Chromium forked WebKit again! You've probably seen some articles on it already, but Alex Russell's piece is pretty good.

In retrospect the split was easy to see coming, but I can't help but feel bittersweet about it. The announcement and Alex's article both cite technical reasons for the fork, but to me it seems to be ultimately a human failure. So the Chromium team saw problems in WebKit and agreed on a solution that will help them achieve their goals faster: that's great! But why were they unable to do so within WebKit itself?

There are technical differences, yes, but those could be resolved by human action (as they now will be, by humans, under the Blink aegis). No, to me the fundamental problem was a lack of the conditions for consensus within the WebKit project, and for that there is ample blame to go around.

In the best of events this split will end up with both Blink and WebKit as more technically consistent, nimble projects. I would also hope that this split serves as a wakeup call to some of the decision-making processes within WebKit. However it is easy to be pessimistic in this regard -- the Apple-Google dynamic has been great for WebKit as an open project, opening up discussions and collaboration possibilities, especially among folks that don't work for the two major corporations. Both projects will have to actively make an effort to remain open, because passivity will favor the structural tendency to work in-house.

I should probably mention the obvious thing, that Igalia will work with both projects, of course. We'll get our WebKit patches into Blink, and vice versa. The message for customers doesn't change much, either -- most customers have already chosen a particular WebKit port, and those that used Chromium will now use Chromium on Blink.

For those projects that haven't chosen a WebKit port yet, the fundamental decision has always been WebKit2/JSC versus Chromium/V8, and that hasn't changed too much from this announcement. It's true that WebKit2 is a less mature multi-process implementation than Chromium, but it is getting a lot of investment these days, so it's fair to assume that technically that the two approaches will work just as well within a few months. The same goes for JSC versus V8.

Finally, a meta-note. Sometimes these press releases catch us up in their whirlwind and we're left with a feeling of anxiety: "Google just released AngularJS, now I need to rewrite all my apps!?" Well, maybe ;) But I find a bit of dispassion is appropriate after a piece of news like this. Good luck to both both projects, and see you on the mailing lists.

Syndicated 2013-04-04 06:43:17 from wingolog

sexuality and sexism

Greetings, dear readers. Today's article is not about compilers, but about the people that write and run compilers. Like me, and like you.

I write a lot about programming here because it's interesting to me and it makes me happy, but that's not the extent of my desires as a human. Among all the things, and perhaps even foremost among them, is the desire to live in a more beautiful world: a world of making and sharing, of nature abloom, and of people too: a world, in short, full of life.

Part of that life is sexual, and how wonderfully, playfully, rightfully so. But the world as a whole would be better if we kept sexuality out of programming and other male-dominated pursuits.

The reason for this is that sexuality (for example, in the form of sexual jokes) among a group of men creates a kind of "boy's club" atmosphere in which people that aren't in the straight male majority feel uncomfortable. A "boy's club" has a virtual "no girls or queers allowed" sign on it. It's just not a comfortable place to be, for non-club-members to be.

Of course, sometimes being uncomfortable is good. But being uncomfortable because of your gender is not one of those cases. And even, it must be said, sometime it goes beyond discomfort to danger -- conferences that women do not attend for fear of groping; things that women cannot say for fear of rape threats. There is no hyperbole here. It is an astonishing, indignation-provoking injustice.

How did it get this bad?

As usual, through small steps. One of the first is widespread toleration of unrelated sexuality in male-dominated fields: boy's clubs. So I think that we all -- and especially men, and especially people with respect within a community -- should actively discourage any of these factors that lead to "boy's clubs". A joke that "I'd fork that project" is not OK. It would be fine if it were just a lame joke; but it's not fine because it's part of this whole "boy's club" thing.

Incidentally, there is a name for the structural tendency to favor one gender over another in a group that isn't "boy's club", and it is "sexism". Sometimes people dismiss sexism in programming because, you know, "show me the code", but this misses the broader picture. I personally have profited immensely from the personal connections I have made at the many conferences that I have attended. I've even put up with some "boy's club" jokes on the same level as "fork-that-repo". I think a woman would find it more difficult to make some of these connections, and so would not end up producing the patches I do.

So, friends, if you are with me in recognizing this structural injustice called sexism, a stain upon our community of compiler hackers and users, I think this is an occasion in which imperative programming is acceptable and even appropriate. Learn to recognize "boy's clubs" and work constructively against them. Sex and tech is usually a bad idea, so point this out when you see it -- especially if you are a man -- and support others who do the same.

Syndicated 2013-03-26 20:07:10 from wingolog

on generators

Hello! Is this dog?

Hi dog this is Andy, with some more hacking nargery. Today the topic is generators.

(shift k)

By way of introduction, you might recall (with a shudder?) a couple of articles I wrote in the past on delimited continuations. I even gave a talk on delimited continuations at FrOSCon last year, a talk that was so hot that thieves broke into the the FrOSCon video squad's room and stole their hard drives before the edited product could hit the tubes. Not kidding! The FrOSCon folks still have the tapes somewhere, but meanwhile time marches on without the videos; truly, the terrorists have won.

Anyway, the summary of all that is that Scheme's much-praised call-with-current-continuation isn't actually a great building block for composable abstractions, and that delimited continuations have much better properties.

So imagine my surprise when Oleg Kiselyov, in a mail to the Scheme standardization list, suggested a different replacement for call/cc:

My bigger suggestion is to remove call/cc and dynamic-wind from the base library into an optional feature. I'd like to add the note inviting the discussion for more appropriate abstractions to supersede call/cc -- such [as] generators, for example.

He elaborated in another mail:

Generators are a wide term, some versions of generators are equivalent (equi-expressible) to shift/reset. Roshan James and Amr Sabry have written a paper about all kinds of generators, arguing for the generator interface.

And you know, generators are indeed a very convenient abstraction for composing producers and consumers of values -- more so than the lower-level delimited continuations. Guile's failure to standardize a generator interface is an instance of a class of Scheme-related problems, in which generality is treated as more important than utility. It's true that you can do generators in Guile, but we shouldn't make the user build their own.

The rest of the programming world moved on and built generators into their languages. James and Sabry's paper is good because it looks at yield as a kind of mainstream form of delimited continuations, and uses that perspective to place the generators of common languages in a taxonomy. Some of them are as expressive as delimited continuations. There are are also two common restrictions on generators that trade off expressive power for ease of implementation:

  • Generators can be restricted to disallow backtracking, as in Python. This allows generators to yield without allocating memory for a new saved execution state, instead updating the stored continuation in-place. This is commonly called the one-shot restriction.

  • Generators can also restrict access to their continuation. Instead of reifying generator state as external iterators, internal iterators call their consumers directly. The first generators developed by Mary Shaw in the Alphard language were like this, as are the generators in Ruby. This can be called the linear-stack restriction, after an implementation technique that they enable.

With that long introduction out of the way, I wanted to take a look at the proposal for generators in the latest ECMAScript draft reports -- to examine their expressiveness, and to see what implementations might look like. ES6 specifies generators with the the first kind of restriction -- with external iterators, like Python.

Also, Kiselyov & co. have a hip new paper out that explores the expressiveness of linear-stack generators, Lazy v. Yield: Incremental, Linear Pretty-printing. I was quite skeptical of this paper's claim that internal iterators were significantly more efficient than external iterators. So this article will also look at the performance implications of the various forms of generators, including full resumable generators.

ES6 iterators

As you might know, there's an official ECMA committee beavering about on a new revision of the ECMAScript language, and they would like to include both iterators and generators.

For the purposes of ECMAScript 6 (ES6), an iterator is an object with a next method. Like this one:

var p = console.log;

function integers_from(n) {
  function next() {
    return this.n++;
  return { n: n, next: next };

var ints = integers_from(0);
p(ints.next()); // prints 0
p(ints.next()); // prints 1

Here, int_gen is an iterator that returns successive integers from 0, all the way up to infinity2^53.

To indicate the end of a sequence, the current ES6 drafts follow Python's example by having the next method throw a special exception. ES6 will probably have an isStopIteration() predicate in the @iter module, but for now I'll just compare directly.

function StopIteration() {}
function isStopIteration(x) { return x === StopIteration; }

function take_n(iter, max) {
  function next() {
    if (this.n++ < max)
      return iter.next();
      throw StopIteration;
  return { n: 0, next: next };

function fold(f, iter, seed) {
  var elt;
  while (1) {
    try {
      elt = iter.next();
    } catch (e) {
      if (isStopIteration (e))
        throw e;
    seed = f(elt, seed);
  return seed;

function sum(a, b) { return a + b; }

p(fold(sum, take_n(integers_from(0), 10), 0));
// prints 45

Now, I don't think that we can praise this code for being particularly elegant. The end result is pretty good: we take a limited amount of a stream of integers, and combine them with a fold, without creating intermediate data structures. However the means of achieving the result -- the implementation of the producers and consumers -- are nasty enough to prevent most people from using this idiom.

To remedy this, ES6 does two things. One is some "sugar" over the use of iterators, the for-of form. With this sugar, we can rewrite fold much more succinctly:

function fold(f, iter, seed) {
  for (var x of iter)
    seed = f(x, seed);
  return seed;

The other thing offered by ES6 are generators. Generators are functions that can yield. They are defined by function*, and yield their values using iterators:

function* integers_from(n) {
  while (1)
    yield n++;

function* take_n(iter, max) {
  var n = 0;
  while (n++ < max)
    yield iter.next();

These definitions are mostly equivalent to the previous iterator definitions, and are much nicer to read and write.

I say "mostly equivalent" because generators are closer to coroutines in their semantics because they can also receive values or exceptions from their caller via the send and throw methods. This is very much as in Python. Task.js is a nice example of how a coroutine-like treatment of generators can help avoid the fraction-of-an-action callback mess in frameworks like Twistednode.js.

There is also a yield* operator to delegate to another generator, as in Python's PEP 380.

OK, now that you know all the things, it's time to ask (and hopefully answer) a few questions.

design of ES6 iterators

Firstly, has the ES6 committee made the right decisions regarding the iterators proposal? For me, I think they did well in choosing external iterators over internal iterators, and the choice to duck-type the iterator objects is a good one. In a language like ES6, lacking delimited continuations or cross-method generators, external iterators are more expressive than internal iterators. The for-of sugar is pretty nice, too.

Of course, expressivity isn't the only thing. For iterators to be maximally useful they have to be fast, and here I think they could do better. Terminating iteration with a StopIteration exception is not so great. It will be hard for an optimizing compiler to rewrite the throw/catch loop terminating condition into a simple goto, and with that you lose some visibility about your loop termination condition. Of course you can assume that the throw case is not taken, but you usually don't know for sure that there are no more throw statements that you might have missed.

Dart did a better job here, I think. They split the next method into two: a moveNext method to advance the iterator, and a current getter for the current value. Like this:

function dart_integers_from(n) {
  function moveNext() {
    return true;
  return { current: n-1, moveNext: moveNext };

function dart_take_n(iter, max) {
  function moveNext() {
    if (this.n++ < max && iter.moveNext()) {
      this.current = iter.current;
      return true;
      return false;
  return {
    n: 0,
    current: undefined,
    moveNext: moveNext

function dart_fold(f, iter, seed) {
  while (iter.moveNext())
    seed = f(iter.current, seed);

I think it might be fair to say that it's easier to implement an ES6 iterator, but it is easier to use a Dart iterator. In this case, dart_fold is much nicer, and almost doesn't need any sugar at all.

Besides the aesthetics, Dart's moveNext is transparent to the compiler. A simple inlining operation makes the termination condition immediately apparent to the compiler, enabling range inference and other optimizations.

iterator performance

To measure the overhead of for-of-style iteration, we can run benchmarks on "desugared" versions of for-of loops and compare them to normal for loops. We'll throw in Dart-style iterators as well, and also a stateful closure iterator designed to simulate generators. (More on that later.)

I put up a test case on jsPerf. If you click through, you can run the benchmarks directly in your browser, and see results from other users. It's imprecise, but I believe it is accurate, more or less.

The summary of the results is that current engines are able to run a basic summing for loop in about five cycles per iteration (again, assuming 2.5GHz processors; the Epiphany 3.6 numbers, for example, are mine). That's suboptimal only by a factor of 2 or so; pretty good. Thigh fives all around!

However, performance with iterators is not so good. I was surprised to find that most of the other tests are suboptimal by about a factor of 20. I expected the engines to do a better job at inlining.

One data point that stands out of my limited data set is the development Epiphany 3.7.90 browser, which uses JavaScriptCore from WebKit trunk. This browser did significantly better with Dart-style iterators, something I suspect due to better inlining, though I haven't verified it.

Better inlining and stack allocation is already a development focus of modern JS engines. Dart-style iterators will get faster without being a specific focus of optimization. It seems like a much better strategy for the ES6 specification to piggy-back off this work and specify iterators in such a way that they will be fast by default, without requiring more work on the exception system, something that is universally reviled among implementors.

what about generators?

It's tough to know how ES6 generators will perform, because they're not widely implemented and don't have a straightforward "desugaring". As far as I know, there is only one practical implementation strategy for yield in JavaScript, and that is to save the function's stack and the set of live registers. Resuming a generator copies the activation back onto the stack and restores the registers. Any other strategy that involves higher-level control-flow rewriting would make debugging too difficult. This is not a terribly onerous requirement for an implementation. They already have to know exactly what is live and what is not, and can reconstruct a stack frame without too much difficulty.

In practice, invoking a generator is not much different from calling a stateful closure. For this reason, I added another test to the jsPerf benchmark I mentioned before that tests stateful closures. It does slightly worse than iterators that keep state in an object, but not much worse -- and there is no essential reason why it should be slow.

On the other hand, I don't think we can expect compilers to do a good job at inlining generators, especially if they are specified as terminating with a StopIteration. Terminating with an exception has its own quirks, as Chris Leary wrote a few years ago, though I think in his conclusion he is searching for virtues where there are none.

dogs are curious about multi-shot generators

So dog, that's ECMAScript. But since we started with Scheme, I'll close this parenthesis with a note on resumable, multi-shot generators. What is the performance impact of allowing generators to be fully resumable?

Being able to snapshot your program at any time is pretty cool, but it has an allocation cost. That's pretty much the dominating factor. All of the examples that we have seen so far execute (or should execute) without allocating any memory. But if your generators are resumable -- or even if they aren't, but you build them on top of full delimited continuations -- you can't re-use the storage of an old captured continuation when reifying a new one. A test of iterating through resumable generators is a test of short-lived allocations.

I ran this test in my Guile:

(define (stateful-coroutine proc)
  (let ((tag (make-prompt-tag)))
    (define (thunk)
      (proc (lambda (val) (abort-to-prompt tag val))))
    (lambda ()
      (call-with-prompt tag
                        (lambda (cont ret)
                          (set! thunk cont)

(define (integers-from n)
   (lambda (yield)
     (let lp ((i n))
       (yield i)
       (lp (1+ i))))))

(define (sum-values iter n)
  (let lp ((i 0) (sum 0))
    (if (< i n)
        (lp (1+ i) (+ sum (iter)))

(sum-values (integers-from 0) 1000000)

I get the equivalent of 2 Ops/sec (in terms of the jsPerf results), allocating about 0.5 GB/s (288 bytes/iteration). This is similar to the allocation rate I get for JavaScriptCore, which is also not generational. V8's generational collector lets it sustain about 3.5 GB/s, at least in my tests. Test case here; multiply the 8-element test by 100 to yield approximate MB/s.

Anyway these numbers are much lower than the iterator tests. ES6 did right to specify one-shot generators as a primitive. In Guile we should perhaps consider implementing some form of one-shot generators that don't have an allocation overhead.

Finally, while I enjoyed the paper from Kiselyov and the gang, I don't see the point in praising simple generators when they don't offer a significant performance advantage. I think we will see external iterators in JavaScript achieve near-optimal performance within a couple years without paying the expressivity penalty of internal iterators.

Catch you next time, dog!

Syndicated 2013-02-25 16:17:25 from wingolog

opengl particle simulation in guile

Hello, internets! Did you know that today marks two years of Guile 2? Word!

Guile 2 was a major upgrade to Guile's performance and expressiveness as a language, and I can say as a user that it is so nice to be able to rely on such a capable foundation for hacking the hack.

To celebrate, we organized a little birthday hack-feast -- a communal potluck of programs that Guilers brought together to share with each other. Like last year, we'll collect them all and publish a summary article on Planet GNU later on this week. This is an article about the hack that I worked on.


Figl is a Guile binding to OpenGL and related libraries, written using Guile's dynamic FFI.

Figl is a collaboration between myself and Guile super-hacker Daniel Hartwig. It's pretty complete, with a generated binding for all of OpenGL 2.1 based on the specification files. It doesn't have a good web site yet -- it might change name, and probably we'll move to savannah -- but it does have great documentation in texinfo format, built with the source.

But that's not my potluck program. My program is a little demo particle simulation built on Figl.

Source available here. It's a fairly modern implementation using vertex buffer objects, doing client-side geometry updates.

To run, assuming you have some version of Guile 2.0 installed:

git clone git://gitorious.org/guile-figl/guile-figl.git
cd guile-figl
autoreconf -vif
# 5000 particles
./env guile examples/particle-system/vbo.scm 5000

You'll need OpenGL development packages installed -- for the.so links, not the header files.


If you look closely on the video, you'll see that the program itself is rendering at 60 fps, using 260% CPU. (The CPU utilization drops as soon as the video starts, because of the screen capture program.) This is because the updates to the particle positions and to the vertices are done using as many processors as you have -- 4, in my case (2 real and 2 threads each). I've gotten it up to 310% or so, which is pretty good utilization considering that the draw itself is single-threaded and there are other things that need to use the CPU like the X server and the compositor.

Each particle is has a position and a velocity, and is attracted to the center using a gravity-like force. If you consider that updating a particle's position should probably take about 100 cycles (for a square root, some divisions, and a few other floating point operations), then my 2.4GHz processors should allow for a particle simulation with 1.6 million particles, updated at 60fps. In that context, getting to 5K particles at 60 fps is not so impressive -- it's sub-optimal by a factor of 320.

This slowness is oddly exciting to me. It's been a while since I've felt Guile to be slow, and this is a great test case. The two major things to work on next in Guile are its newer register-based virtual machine, which should speed things up by a factor of 2 or so in this benchmark; and an ahead-of-time native compiler, which should add another factor of 5 perhaps. Optimizations to an ahead-of-time native compiler could add another factor of 2, and a JIT would probably make up the rest of the difference.

One thing I was really wondering about when making this experiment was how the garbage collector would affect the feeling of the animation. Back when I worked with the excellent folks at Oblong, I realized that graphics could be held to a much higher standard of smoothness than I was used to. Guile allocates floating-point numbers on the heap and uses the Boehm-Demers-Weiser conservative collector, and I was a bit skeptical that things could be smooth because of the pause times.

I was pleasantly surprised that the result was very smooth, without noticeable GC hiccups. However, GC is noticeable on an overloaded system. Since the simulation advances time by 1/60th of a second at each frame, regardless of the actual frame rate, differing frame processing times under load can show a sort of "sticky-zipper" phenomenon.

If I ever got to optimal update performance, I'd probably need to use a better graphics card than my Intel i965 embedded controller. And of course vertex shaders are really the way to go if I cared about the effect and not the compiler -- but I'm more interested in compilers than graphics, so I'm OK with the state of things.

Finally I would note that it has been pure pleasure to program with general, high-level macros, knowing that the optimizer would transform the code into really efficient low-level code. Of course I had to check the optimizations, with the ,optimize, command at the REPL. I even had to add a couple of transformations to the optimizer at one point, but I was able to do that without restarting the program, which was quite excellent.

So that's my happy birthday dish for the Guile 2 potluck. More on other programs after the hack-feast is over; until then, see you in #guile!

Syndicated 2013-02-16 19:20:14 from wingolog

knocking on private back doors with the web browser

I woke up at five this morning with two things in my head.

One was, most unfortunately, Rebecca Black's Friday, except with "Monday" -- you know, "Monday, Monday, gettin' up on Monday, hack, hack, hack, hack, which thing should I hack?", et cetera.

The other was a faint echo of Patrick McKenzie's great article on the practical implications of the recent Rails vulnerabilities. In particular, he pointed out that development web servers running only on your local laptop could be accessed by malicious web pages.

Of course this is not new, strictly speaking, but it was surprising to me in a way that it shouldn't have been. For example, Guile has a command-line argument to run a REPL server on a local port. This is fantastic for interactive development and debugging, but it is also a vulnerability if you run a web server on the same machine. A malicious web page could request data from the default Guile listener port, which is a short hop away from rooting your machine.

I made a little test case this morning: a local port scanner. It tries to fetch http://localhost:port/favicon.ico for all ports between 1 and 10000 on your machine. (You can click that link; it doesn't run the scan until you click a button.)

If it finds a favicon, that indicates that there is a running local web application, which may or may not be vulnerable to CSRF attacks or other attacks like the Rails yaml attack.

If the request for a favicon times out, probably that port is vulnerable to some kind of attack, like the old form protocol attack.

If the request fails, the port may be closed, or the process listening at the port may have detected invalid input and closed the connection. We could run a timing loop to determine if a connection was made or not, but for now the port scanner doesn't output any information for this case.

In my case, the page finds that I have a probably vulnerable port 2628, which appears to be dictd.

Anyway, I hope that page is useful to someone. And if you are adding backdoors into your applications for development purposes, be careful!

Syndicated 2013-02-04 08:47:09 from wingolog

an opinionated guide to scheme implementations

Hark, the beloved programing language! But hark, also: for Scheme is a language of many implementations. If Scheme were a countryside, it would have its cosmopolitan cities, its hipster dives, its blue-collar factory towns, quaint villages, western movie sets full of façades and no buildings, shacks in the woods, and single-occupancy rent-by-the-hour slums. It's a confusing and delightful place, but you need a guide.

And so it is that there is a steady rivulet of folks coming into the #scheme IRC channel asking what implementation to use. Mostly the regulars are tired of the question, but when they do answer it's in very guarded terms -- because the topic is a bit touchy, and a bit tribal. There's a subtle tension between partisans of the different implementations, but people are polite enough not to avoid controversial, categorical statements. Unfortunately the end result of this is usually silence in the channel.

Well I'm tired of it! All that silence is boring, and so I thought I'd give you my opinionated guide to Scheme implementations. This is necessarily subjective and colored, as I co-maintain the Guile implementation and do all of my hacking in Guile. But hey, to each folk their stroke, right? What I say might still be valuable to you.

So without further introduction, here are seven recommendations for seven use cases.

The embedded Scheme

So you have a big project written in C or C++ and you want to embed a Scheme interpreter, to allow you to extend this project from the inside in a higher-level, dynamic language. This is the sort of thing where Lua really shines. So what Scheme to use?

Use Chibi Scheme! It's small and from all accounts works great for static linking. Include a copy of it in your project, and save yourself the headache of adding an external dependency to something that changes.

Embedding Scheme is a great option if you need to ship an application on Windows, iOS, or Android. The other possibility is shipping a native binary created by a Scheme that compiles natively, so...

The Scheme that can make a binary executable

Sometimes what you want to do is just ship an executable, and not rely on the user to install a runtime for a particular Scheme system. Here you should use Chicken or Gambit. Both of these Schemes have a compiler that produces C, which it then passes on to your system's C compiler to generate an executable.

Another possibility is to use Racket, and use its raco exe and raco dist commands to package together a program along with a dynamically-linked runtime into a distributable directory.

The dynamically linked Scheme

What if you want to extend a project written in C, C++, or the like, but you want to dynamically link to a Scheme provided with the user's system instead of statically linking? Here I recommend Guile. Its C API and ABI are stable, parallel-installable, well-documented, and binary packages are available on all Free Software systems. It's LGPL, so it doesn't impose any licensing requirements on your C program, or on the Scheme that you write.

The Scheme with an integrated development environment

What if you really like IDEs? For great justice, download you a Racket! It has a great debugger, an excellent Scheme editor, on-line help, and it's easy to run on all popular platforms. Incidentally, I would say that Racket is probably the most newbie-friendly Scheme there is, something that stems from its long association with education in US high schools and undergraduate programs. But don't let the pedagogical side of things fool you into thinking it is underpowered: besides its usefulness for language research, Racket includes a package manager with lots of real-world modules, and lots of people swear by it for getting real work done.

The Scheme for SICP

Many people come by #scheme asking which Scheme they should use for following along with Structure and Interpretation of Computer Programs. SICP was originally written for MIT Scheme, but these days it's easier to use Neil Van Dyke's SICP mode for Racket. It has nice support for SICP's "picture langauge". So do that!

The server-side Scheme

So you write the intertubes, do you? Well here you have a plethora of options. While I write all of my server-side software in Guile, and I think it's a fine implementation for this purpose, let me recommend Chicken for your consideration. It has loads of modules ("eggs", they call them) for all kinds of tasks -- AWS integration, great HTTP support, zeromq, excellent support for systems-level programming, and they have a good community of server-side hackers.

The Scheme for interactive development with Emacs

Install Guile! All right, this point is a bit of an advertisement, but it's my blog so that's OK. So the thing you need to do is install Paredit and Geiser. That page I linked to gives you the procedure. From there you can build up your program incrementally, starting with debugging the null program. It's a nice experience.

You and your Scheme

These recommendations are starting points. Most of these systems are multi-purpose: you can use Gambit as an interpreter for source code, Racket for server-side programing, or Chicken in Emacs via SLIME. And there are a panoply of other fine Schemes: Chez, Gauche, Kawa, and the list goes on and on (and even farther beyond that). The important thing in the beginning is to make a good starting choice, invest some time with your choice, and then (possibly) change implementations if needed.

To choose an implementation is to choose a tribe. Since Scheme is so minimal, you begin to rely on extensions that are only present in your implementation, and so through code you bind yourself to a world of code, people, and practice, loosely bound to the rest of the Scheme world through a fictional first-person-plural. This is OK! Going deep into a relationship with an implementation is the only way to do great work. The looser ties to the rest of the Scheme world in the form of the standards, the literature, the IRC channel, and the mailing lists provide refreshing conversation among fellow travellers, not marching orders for a phalanx.

So don't fear implementation lock-in -- treat your implementation's facilities as strengths, until you have more experience and know more about how your needs are served by your Scheme.


Just do it! You wouldn't think that this point needs elaboration, but I see so many people floundering and blathering without coding, so it bears repeating. Some people get this strange nostalgic "Scheme is an ideal that I cannot reach" mental block that is completely unproductive, not to mention lame. If you're thinking about using Scheme, do it! Install your Scheme, run your REPL, and start typing stuff at it. And try to write as much of your program in Scheme as possible. Prefer extension over embedding. Use an existing implementation rather than writing your own. Get good at using your REPL (or the IDE, in the case of Racket). Read your implementation's manual. Work with other people's code so you get an idea of what kind of code experienced Schemers write. Read the source code of your implementation.

See you in #scheme, and happy hacking!

Syndicated 2013-01-07 13:43:35 from wingolog

corps: bespoke text codecs

Happy 12/12/12, peoples! In honor of repeated subsequences, today I'm happy to release a new set of compression tools, Corps.

Corps is a toolkit for generating custom text codecs, specialized to particular bodies of text. You give it an example corpus to analyze, and Corps can generate codecs based on what it finds.

For example, if you want to develop a compression algorithm that operates on JavaScript source text, you probably want to use a special code to represent the multi-character sequence function.

I say "probably", because in reality you don't know what substrings are most common. Corps uses the Re-Pair algorithm to build up an optimal token set. This algorithm treats all characters in the input as tokens, and recursively creates composite tokens from the most common pair of adjacent tokens, repeating the process until there are no more repeated pairs of tokens. For full details, see "Off-Line Dictionary-Based Compression" by Larsson and Moffat.

Corps is mostly useful for creating special-purpose fixed codecs based on a dictionary generated by its offline analysis. Although pre-generated codecs often do not compress as well as adaptive codecs like the one used by gzip, fixed codecs are typically faster as they can use the fixed code table to generate optimized encoders and decoders. Corps currently generates encoders in C and Scheme, and decoders in C, Scheme, and JavaScript.

Special-purpose codecs can also provide some interesting properties, such as the ability to decompress a substring of the original text.

get source

Corps is written for Guile version 2.0. See http://gnu.org/s/guile for more information on Guile and how to install it on your system.

To build Corps from git, do:

git clone git://gitorious.org/corps/corps.git
cd corps
./autogen.sh && ./configure && make && make check

You can install using make install, but it's often more convenient to just run corps uninstalled, using the env script.

stinky cheese

Corps includes a simple command-line tool called corps. For full documentation, run corps help. You can run it uninstalled by prefixing the ./env from the build tree.

As an example, say you want to build a database of wikipedia pages on cheese. Let's fetch a page:

$ curl -s 'http://en.wikipedia.org/wiki/Maroilles_(cheese)' > cheese
$ ls -l cheese
-rw-r--r-- 1 wingo wingo 43123 Dec 12 15:12 cheese

Now we analyze it to determine common substrings:

./env corps extract-all cheese > cheese-tokens

This generates a list of (string,frequency) pairs. An extract-all token set is usually quite large. We can pare it down to something manageable, the 500 most common substrings:

./env corps extract-subset cheese-tokens 500 cheese > 500-tokens

With this dictionary, we can huffman-code the page:

$ ./env corps encode -t 500-tokens -m huffman cheese cheese.huff
$ ls -l cheese.huff
-rw-r--r-- 1 wingo wingo 18060 Dec 12 16:09 cheese.huff

Well that's pretty cool -- it's less than half the size of the source text. We can also pare down this set of tokens to an appropriate number of tokens for a bytecode, and try doing a byte-encode of the file:

$ ./env corps extract-subset 500-tokens 254 cheese > 254-tokens
$ ./env corps encode -t 254-tokens cheese > cheese.bc
$ ls -l cheese.bc
-rw-r--r-- 1 wingo wingo 22260 Dec 12 16:19 cheese.bc

It's larger than the huffman-code, not only because of the smaller dictionary, but also because a bytecode is less dense. In practice though a bytecode is good enough while being very fast, so we'll continue with the bytecode.

Now let's generate a C encoder and decoder for this token set.

$ ./env corps generate-c-byte-encoder 254-tokens > encoder.inc.c
$ ./env corps generate-c-byte-decoder 254-tokens > decoder.inc.c
$ cp ~/src/corps/corps/decoder.c .
$ cp ~/src/corps/corps/encoder.c .
$ gcc -o decoder -O3 decoder.c
$ gcc -o encoder -O3 encoder.c
$ ls -l encoder decoder
-rwxr-xr-x 1 wingo wingo 13192 Dec 12 16:23 decoder
-rwxr-xr-x 1 wingo wingo 31048 Dec 12 16:23 encoder

Nice! We could use the corps tool to decode cheese.bc, but to vary things up we can use our zippy C decoder:

$ ./decoder < cheese.bc > cheese.out
$ cmp cheese.out cheese && echo 'excellent!'

The performance of the C encoder is pretty good:

$ for ((x=0;x<1000;x++)) do cat cheese >> megacheese; done
$ time gzip -c < megacheese > megacheese.gz
real	0m1.418s
user	0m1.396s
sys	0m0.016s
$ time ./encoder < megacheese > megacheese.bc
real	0m0.523s
user	0m0.480s
sys	0m0.044s
$ ls -l megacheese*
-rw-r--r-- 1 wingo wingo 43123000 Dec 12 17:03 megacheese
-rw-r--r-- 1 wingo wingo 22370002 Dec 12 17:04 megacheese.bc
-rw-r--r-- 1 wingo wingo 11519311 Dec 12 17:04 megacheese.gz

Gzip gets better compression results for many reasons, but our quick-and-dirty bytecode compressor does well enough and is quite fast. The decoder is also quite good:

$ time ./decoder < megacheese.bc > /dev/null
real	0m0.179s
user	0m0.160s
sys	0m0.016s
$ time gunzip -c < megacheese.gz > /dev/null
real	0m0.294s
user	0m0.284s
sys	0m0.008s

Amusingly, for this text, gzipping the bytecoded file has quite an impact:

$ gzip -c < megacheese.bc > megacheese.bc.gz
$ ls -l megacheese*
-rw-r--r-- 1 wingo wingo 43123000 Dec 12 17:03 megacheese
-rw-r--r-- 1 wingo wingo 22370002 Dec 12 17:04 megacheese.bc
-rw-r--r-- 1 wingo wingo   175246 Dec 12 17:12 megacheese.bc.gz
-rw-r--r-- 1 wingo wingo 11519311 Dec 12 17:04 megacheese.gz

It so happens that byte-compressing the original text allows it to fit within the default gzip "window size" of 32 KB, letting gzip detect the thousandfold duplication of the source text. As a codec that works on bytes, gzip tends to work quite well on bytecoded files, and poorly on bit-coding schemes like huffman codes. A gzipped bytecoded file is usually smaller than a gzipped raw file and smaller than a gzipped huffman-coded file.


I'll close with a link to the 254 most common substrings in one corpus of JavaScript code that I analyzed: here. I have a set of patches to integrate a codec optimized for JavaScript source into V8, to try to reduce the memory footprint of JS source code. More on that quixotic endeavor in some future post. Until then, happy scheming!

Syndicated 2012-12-12 16:57:56 from wingolog


silence on the wire

It's been pretty quiet in this electro-rag, and for a simple but profound reason. I don't know about all of Maslow's hierarchy of needs, but for me there is definitely a hierarchy between housing and anything else.

Thing is, my partner and I drove up to Geneva almost three months ago, but we only moved in somewhere permanent last week. Everything was up in the air! Sublets and couches and moving vans and storage units. All the things in all the places.

In a way it should have been liberating, but I reckon I'm just a homebody: someone who likes to have a spritual and physical base to come back to. It's the classic introverted/extroverted "where do you get your energy" thing -- in private, or in society? Of course it's both, but for me the private side is important and necessary.

society, nations, states

Incidentally, October made ten years since I left the US. I lived in Namibia for a couple of years, moved to Spain in 2005, and as you know, left for Switzerland in September. In that time, a third of my life, I have not been able to vote for my local government. Representative democracy isn't very democratic, of course, but not even having that nominal connection to collective decision-making is a bit unmooring.

In Spain I have what is called "EU long-term residency". In 2003, the EU standardized visas for "third-country nationals": folks like me that do not have citizenship in a EU country. After 5 years, you automatically get country-specific "long-term residency", and can optionally apply for "EU long-term residency" (as I just did), which has the additional benefit of being transferable to other EU countries.

The idea of EU long-term residency was to make third-country nationals have the same rights as EU citizens, but several restrictions placed on the agreement by individual nations make it not very attractive compared to full nationality. EU citizens have the right to move around the EU, whereas third-country nationals have to apply to do so.

And in many countries, you can get nationality just as easy as long-term residency. In France for example, you only have to wait 5 years to be able to apply for nationality. In Spain, if you come from a Latin American country, you only have to wait 2 years (in theory; I have heard of unreasonable delays). As that is not my particular case, I would have to wait 10 years to get Spanish nationality, making this "EU long-term residency" attractive. However if I move away from Spain officially, I would have to "start over".

Man. The EU. What a bizarre institution. I think few normal citizens can describe the structure of the the EU -- you know, what's the deal with the parliament and the commisioners and the president and the central bank? The operations of the EU have very little to do with democracy. The tenuous accountability of the Members of European Parlaiment is mostly to political parties rather than to the people. Finance in rich countries basically runs the bank. The commission seems to run itself, with limited accountability to the governments of member states. To the extent that the EU is a democracy, it is its weakest form: vast, physically removed from its constituency, composed of representatives of representatives.

and yet

It's been interesting to see the contrast in Switzerland. Switzerland has its own currency, protectionist trade policies, and a smattering of EU-à-la-carte. So, yes, it is relatively easy for EU citizens to move to Switzerland, but on the other hand it's quite difficult if you are a "third-country national" like myself.

Switzerland is also very local. Most legislation involves the citizens directly, via referendum. The other day, voters here just approved a new constitution, by simple majority, for Geneva. Contrast this to the EU, which centralizes its power more every year.

There are good things and bad things about this. I suppose that specifically, it's mostly good for the Swiss, neutral for EU nationals, and worse for third-country nationals. Policies that enable local agricultural and industrial production are great for local workers, businesses, consumers (with Swiss salary), and the environment. These policies are quite difficult to have in the EU. Even the existence of the Swiss franc is great for local decision-making power, although its policies are mostly controlled by finance.

On the other hand, the immigration policy is quite reactionary, often bordering on xenophobia. In the EU, the institutions were able to achieve some limited forms of freedom of movement of persons, including third-country nationals, in exchange for the freedom of movement of capital. No such arrangement has been made in Switzerland. (They'll happily take your capital, of course.)

As you probably know, I mostly identify as an anarchist, a kind of libertarian socialism that is suspicious of hierarchical power structures. So Switzerland has its attractions in that sense. But I've had discussions with folks arguing that the EU has actually been the emancipatory institution, in contrast to reactionary governments, and there is something there. For all its decentralized, democratic principles, women did not get the right to vote in Swiss federal elections until 1971, and the last canton (local government) held out until 1990, when it was forced to allow women to vote by a federal court.


There's no way around it: Geneva stinks of money.

An illustration, if you don't mind. When we first came here to visit in August, we got out of the car, went to a cash machine, and tried to get out 120 francs (approximately 120 dollars, or 100 euros). No. The minimum amount was 100 francs, and the next was 200. Well, OK. We got 200. It came out in two bills. The machine did not dispense any lower denomination. There was nothing wrong with that machine; it was marked as only dispensing 100-franc bills and higher.

On the other hand, unlike Spain, all shopkeepers carry around fat bankrolls and are quite happy to break a 100, even on a 50 cent purchase. You can do that only if you can find something that costs that little, of course.

If you walk around the center of town, it's designer tailors, caviar bars (not kidding), and private banks. It is truly disgusting. It makes me think of a butcher's counter: bleach covering a faint smell of blood, but without the redeeming earthiness. Perhaps this is just a personal analogy though.

That's the macro-level. Of course there are normal folks here too, but that's tempered by the cost: things are in general really expensive here. Starbucks drip coffee for 5 dollars. You can easily spend 70 dollars a person at a normal restaurant. A normal one-hour tram ticket is 5 dollars. Etc.

From what I can tell, the cost of things is not a problem if you have a Swiss salary. I'm in something of an irregular state: an American with Spanish residency, working for a Spanish company, living in Geneva (but actually France). Administrativia aside, it has been quite a shock coming from Spain to here. In Igalia, the cooperative I work at, we try to pay everyone the same when everything is going well, but when the budget is a little tighter salaries get scaled down to something approaching "the cost of living" (whatever that is).

We had to open a whole new round of discussions about how to determine compensation after I moved here. Geneva just didn't fit in anyone's conception about what was reasonable! It raises all kinds of issues: what does it mean to work in a cooperative with people in all different kinds of places? What does fair and equal compensation actually mean in San Francisco and A Coruña and Madrid and Geneva, and how do you calculate it? It looks like we've come to an interesting and probably unique solution there, so perhaps more on that as discussions progress.


Of course it's strange to come to this capital of, well, capital with these values, but here I am. You end up talking about money a lot. Of course you need a place to put your money and take it out. For an anarchist I've got a lot of bank accounts: Spanish, Swiss, French, and US somewhere... For all the new EU regulations, cross-border ATM fees still make it attractive to have an account in the place where you need to withdraw money.

Same thing with mobile phone companies. As I said, we ended up moving to France. The rent is a lot cheaper, it's more compatible with our residency permits, and it's still only a 25 minute bike or tram into the center of Geneva so it's not totally in the boon-docks. But this makes me carry around two phones because I cross the border all the time, and then of course there's the old Spanish SIM I need to do something with. I've done the PIN-to-PUK dance multiple times, because I can't remember so many numbers.

It's a pretty strange identity to have: to have a house in France, but feel attached to Switzerland. It's tough to catch the dominant social story, of who is the "us" in this place. It's problem with Geneva in general, transient city that it is.


Well, this post grows long, and it's mostly a rant, right? And I needed to rant and be done with it. But I don't want to be too negative. We have an actual house, with a garden, and we're going to plant things and compost and such. It's warm and cozy inside and there are snowy mountains about, and there's a cosmopolitan city within a close if brisk bike ride. I have a French grocery store five minute's walk away. It's a dark season, but there is cheese and wine enough to carry me through to springtime :) So things are good. I'll still rant, but things are all right.

Bon. Catch you internauts later. Next time, with code!

Syndicated 2012-12-05 23:16:13 from wingolog

quasiconf 2012: lisp @ froscon

Are you a Lisper, in the big-tent sense of the term? You within a day's transport of St. Augustin in Germany? Well shucks, have I got a thing for you: Quasiconf, a lisp sub-conference of FrOSCon, held next weekend (25-26 August 2012).

The full program isn't quite out yet, but they invited yours truly to talk there, and talk I will. In fact I'll talk thrice: they gave me 90 minutes, so I'll do three little presentations.

In the first, I'll finally give that talk I've been threatening to do for years, about why delimited continuations are the bee's knees, how they can be implemented, and what kind of lovely code they enable. The example will be a small memcached server and client.

Next I'll talk about things that implementing JavaScript has taught me about Scheme implementations. They were very surprising lessons to me, so I hope they will entertain the attendees. No spoilers, though!

Finally, now that Guile 2.0 has been out for a year and a half or so, it's a good time to look back at what worked well and what didn't. If you are even remotely interested about what it takes to maintain and enhance a mature language implementation, this will be an interesting talk for you. I'll also take the opportunity to summarize the progress on the development branch, which will probably be Guile 2.2.

So that's the thing. It's somewhat of a late announcement, but hey, if you can go, it's pretty much free and should be an interesting get-together. See you there!

Syndicated 2012-08-15 21:34:25 from wingolog

398 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!