Older blog entries for mbrubeck (starting at number 113)

Android 2.0 ships with V8 JavaScript engine

Google has not yet released most of the Android 2.0 source code, but they did publish source for a very small number of components, including a WebKit snapshot. I was very excited to see that the snapshot includes Google's V8 virtual machine! (Previous Android releases used Safari's JavaScriptCore/"SquirrelFish Extreme" VM.) But without the rest of the source tree, there was no way to build and run this on a real Android phone. The SDK includes a binary image that runs only in the qemu-based emulator.

Today I got to try out a Motorola Droid. Here is how its browser compares to Android 1.6 on my HTC Dream (Android Dev Phone / T-Mobile G1) in the V8 Benchmark Suite (version 5):

Test Dream Droid Change
Richards 13.5 15.6 16%
DeltaBlue 5.23 12.9 147%
Crypto 13.2 10.9 -17%
RayTrace 10.9 80.1 635%
EarleyBoyer 23.5 74.7 218%
RegExp did not complete 16.5
Splay did not complete did not complete

Some tests (Richards, Crypto) see little or no improvement, while others (DeltaBlue, RayTrace, EarleyBoyer) are dramatically faster. Just for comparison, let's run the same benchmark on Safari 4 (JavaScriptCore) and a Chromium 4 nightly build (V8) on a Mac Pro:

Test Safari Chromium Change
Richards 4103 4640 13%
DeltaBlue 3171 4418 39%
Crypto 3331 3643 9%
RayTrace 3509 6662 90%
EarleyBoyer 4737 7643 61%
RegExp 1268 1187 -6%
Splay 1198 7290 509%

The precise ratios are different, but the same tests that showed the most improvement from Android 1.6 to 2.0 also show the most improvement from Safari to Chrome. Based on this plus the source code snapshot, I'm pretty sure that Android 2.0 is indeed using V8.

This is exciting news. It makes Droid the first shipping product I know that uses V8 on an ARM processor, although V8 has included an ARM JIT compiler for some time now. For mobile web developers (like me), it means we're one step closer to having desktop-quality rich web applications on low-power handheld devices.

Final thought: Although the Motorola Droid is still 100 times slower than Chromium on a Mac Pro, it's actually faster at some benchmarks than IE8 on a low-end Windows machine, or Firefox 2 on hardware from just a few years ago.

Syndicated 2009-11-06 08:00:00 from Matt Brubeck

Compleat: Programmable Completion for Everyone

Compleat is an easy, declarative way to add smart tab-completion for any command-line program. For a quick description, see the README. For more explanation and a brief tutorial, keep reading...


I'm one of those programmers who loves to carefully tailor my development environment. I do nearly all of my work at the shell or in a text editor, and I've spent a dozen years learning and customizing them to work more quickly and easily.

Most experienced shell users know about programmable completion, which provides smart tab-completion for for supported programs like ssh and git. (If you are not familiar it, you really should install and enable bash-completion, or the equivalent package for your chosen shell.) You can also add your own completions for programs that aren't supported—but in my experience, most users never bother.

When I worked at Amazon, everyone used Zsh (which has a very powerful but especially baroque completion system) and shared the completion scripts they wrote for our myriad internal tools. Now that I'm in a startup with few other command line die-hards, I'm on my own when it comes to extending my shell.

So I read the fine manual and started writing my own completions. Over on GitHub you can see the script I made for three commands from the Google Android SDK. It's 200 lines of shell code, fairly straightforward if you happen to be familiar with the Bash completion API. But as I cranked out more and more case statements, I felt there must be a better way...

The Idea

It's not hard to describe the usage of a typical command-line program. There's even a semi-standard format for it, used in man pages and generated by libraries like GNU AutoOpt. Here's one for android, one of the SDK commands supported by my script:

   android [--silent | --verbose]
   ( list [avd|target]
   | create avd ( --target <target> | --name <name> | --skin <name>
                 | --path <file> | --sdcard <file> | --force ) ...
   | move avd (--name <avd> | --rename <new> | --path <file>) ...
   | (delete|update) avd --name <avd>
   | create project ( (--package|--name|--activity|--path) <val>
                     | --target <target> ) ...
   | update project ((--name|--path) <val> | --target <target>) ...
   | update adb )

My idea: What if you could teach the shell to complete a program's arguments just by writing a usage description like this one?

The Solution

With Compleat, you can add completion for any command just by writing a usage description and saving it in a configuration folder. The ten-line description of the android command above generates the same results as my 76-line bash function, and it's so much easier to write and understand!

The syntax should be familiar to long-time Unix users. Optional arguments are enclosed in square brackets; alternate choices are separated by vertical pipes. An ellipsis following an item means it may be repeated, and parentheses group several items into one. Words in angle brackets are parameters for the user to fill in.

Let's look at some more features of the usage format. For programs with complicated arguments, it can be useful to break them down further. You can place alternate usages on their own lines separated by semicolons, like this:

  android <opts> list [avd|target];
android <opts> move avd (--name <avd>|--rename <new>|--path <file>)...;
android <opts> (delete|update) avd --name <avd>;

...and so on. Rather than repeat the common options on every line, I used a parameter <opts>. I can define that parameter using the same usage syntax.

  opts = [ --silent | --verbose ];

For parameters whose values are not fixed but can be computed by another program, we use a ! symbol followed by a shell command to generate completions, like this:

  avd = ! android list avd | grep 'Name:' | cut -f2 -d: ;
target = ! android list target | grep '^id:'| cut -f2 -d' ' ;

And any parameter without a definition will just use the shell's built-in completion rules, which suggest matching filenames by default.

The README file has more details of the usage syntax, and instructions for installing the software. Give it a try, and please send in any usage files that you want to share! (Questions, bug reports, or patches are also welcome.)

Future Work

For the next release of Compleat, I would like to make installation easier by providing better packaging and pre-compiled binaries; support zsh and other non-bash shells; and write better documentation.

In the long term, I'm thinking about replacing the usage file interpreter with a compiler. The compiler would translate the usage file into shell code, or perhaps another language like C or Haskell. This would potentially improve performance (although speed isn't an issue right now on my development box), and would also make it easy for usage files to include logic written in the target language.

Final Thoughts

Recently I realized that parts of my work are so specialized that my parents and non-programmer friends will probably never really get them. For example, Compleat is a program to generate programs to help you... run programs? Sigh. Well, maybe someone out there will appreciate it.

Compleat was my weekends/evenings/bus-rides project for the last few weeks (as you can see in the GitHub punch card), and my most fun side-project in quite a while. It's the first "real" program I've written in Haskell, though I've been experimenting with the language for a while. Now that I'm comfortable with it, I find that Haskell's particular combination of features works just right to enable quick exploratory programming, while giving a high level of confidence in the behavior of the resulting program. Compleat 1.0 is only 160 lines of Haskell, excluding comments and imports. Every module was completely rewritten at least once as I tried and compared different approaches. This is much less daunting when the code in question is only a couple dozen lines. I don't think this particular program would have been quite as easy to write—at least for me—in any of the other platforms I know (including Ruby, Python, Scheme, and C).

I had the idea for Compleat more than a year ago, but at the time I did not know how to implement it easily. I quickly realized that what I wanted to write was a specialized parser generator, and a domain-specific language to go with it. Unfortunately I never took a compiler-design class in school, and had forgotten most of what I learned in my programming languages course. So I began studying parsing algorithms and language implementation, with Compleat as my ultimate goal.

My good friend Josh and his Gazelle parser generator helped inspire me and point me toward other existing work. Compleat actually contains three parsers. The usage file parser and the input line tokenizer are built on the excellent Parsec library. The usage file is then translated into a parser that's built with my own simple set of parser combinators, which were inspired both by Parsec and by the original Monadic Parser Combinators paper by Graham Hutton and Erik Meijer. The simple evaluator for the usage DSL applies what I learned from Jonathan Tang's Write Yourself a Scheme in 48 Hours. And of course Real World Haskell was an essential resource for both the nuts and bolts and the design philosophy of Haskell.

So besides producing a tool that will be useful to me and hopefully others, I also filled in a gap in my CS education, learned some great new languages and tools, and kindled an interest in several new (to me) research areas. It has also renewed my belief in the importance of "academic" knowledge to real engineering problems. (I've already come across at least one problem in my day job that I was able to solve faster by implementing a simple parser than I would have a year ago by fumbling with regexes.) And I'll be even happier if this inspires some friends or strangers to take a closer look at Haskell, Parsec, or any problem they've thought about and didn't know enough to solve. Yet.

Syndicated 2009-10-30 07:00:00 from Matt Brubeck



This site is powered by Jekyll and based on styles and markup by Tom Preston Werner. Comments are run by Disqus and hosting is by Dreamhost.

Before starting this site, I had an Advogato diary for writing about software. I also have a personal journal (mostly interesting to my friends and family).

Syndicated 2009-10-28 07:00:00 from Matt Brubeck

11 Mar 2009 (updated 5 May 2010 at 22:24 UTC) »

position:fixed in Android Webkit

Good news for mobile web developers! In the latest development build of Android ("cupcake"), WebKit supports iPhone touch events and CSS3 animations/transforms. This means that Richard Herrera's iPhone fixed positioning hack will soon work on Android too.

The WebKit CSS Animation demos also work, but lack of hardware acceleration in Android makes them painfully slow compared to the iPhone.

5 Mar 2009 (updated 5 Mar 2009 at 22:04 UTC) »

Async Map and Fold in JavaScript

My latest experiment is an implementation of asynchronous/parallel "map" (and other array functions) in JavaScript and Oni. Oni is a "structured concurrency language" embedded in JavaScript. For my source code and commentary, see oni-map at GitHub. You can leave comments at GitHub too.

All this time reading Real World Haskell must really have warped my brain if a simple testing framework for a JavaScript program has got me thinking about higher-order functions and concurrency semantics...

Bash Completion for the Google Android SDK

If you're developing for Android, try out the bash script I wrote to add tab-completion for the "adb" command-line tool.

MapReduce with Parallel Make

Ted Gould’s post about transcoding music files using Make got me thinking about combining Make and RecordStream into a barebones MapReduce framework. As a demonstration, I wrote a partial solution to Tim Bray’s Wide Finder challenge, to calculate hit counts from web server logs.

More details (and code).

24 Nov 2008 (updated 24 Nov 2008 at 23:08 UTC) »

The Timeless Way of Building: Diagnosis and Repair

Architect Christopher Alexander's A Pattern Language is well known among programmers as the inspiration for the Design Patterns school of thought, but for some reason his other books are less widely read. My mother and father are both architects—"real" ones, not "software architects." :) My own amateur interest in the subject led me to read several of Alexander's books over the past couple of years.

The Timeless Way of Building is the first volume of an open-ended series. (A Pattern Language is the second.) It is in this book that Alexander first lays out the idea of a pattern language. More importantly, he explains an entire theory and practice of design and construction, of which the pattern language is only one piece.

Another piece of the Timeless Way is the practice of diagnosis and repair. Rather than a detailed plan of future projects, Alexander prefers to maintain a diagnosis of current problems. Each new project must be targeted at fixing these existing problem in the system: "At every moment we use the defects of the present state as the starting point for the definition of the new state" (p. 485). Alexander's goal is to create a type of spontaneous growth and order that is possible when change is incremental and decision-making authority is decentralized.

Alexander was hired to produce a new type of master plan for the University of Oregon campus. The result was published as the third volume in the "Timeless Way" series: The Oregon Experiment. In it, he writes again about diagnosis and repair:

It is still not clear where global order will come from, without a master plan.… How is the problem solved in an organism? Essentially, the problem is solved by a process of diagnosis and local repair.… The master plan tells us what is right for the future. The diagnosis tells us what is wrong for the present. (p. 146–148)

In software, the same problems and conclusions have led to "agile" processes, which emphasize incremental change and flexible planning. But I haven't seen any software companies adopt a consistent practice of "diagnosis"—keeping track of what's wrong or unsatisfactory with the current system. This extends beyond defect tracking; it should include a constantly updated list of code that, although it works, is hard to understand, difficult to change, or otherwise likely to cause problems. (This should be easy to generate—every programmer knows certain parts of their code base that they dread working on for one reason or another.) This knowledge can then guide new development to include "repair" and address such problems before they become defects. I've applied this on a small scale to my own work, and now I wish I had used it at Amazon, where my team spent much more time maintaining and improving old code than writing new code.

Flip Video Ultra on Linux

My Flip video camera arrived yesterday, and I'm quite happy with it. It does everything it's supposed to: starts up fast, records and plays back through an astoundingly simple interface, and mounts as a USB mass storage device. The videos play back perfectly on my Ubuntu 7.10 system, and Kino can import and edit them if ffmpeg is installed.

I did have some problems using the camera with a Windows XP laptop. The Windows program stored on the camera failed to start up, saying that "E:\SYSTEM\VIEWER\PD\settings\pathsInfo.txt does not contain a valid list." The firmware updater from the Flip web site failed with a similar error. Finally I found the Flip Video Program installer, which fixed both of those problems. (It took me a while to figure this out, so I'm documenting it here in case other Flip owners have the same problem.)

26 Nov 2007 (updated 26 Nov 2007 at 16:43 UTC) »

PDF on Kindle

I've seen plenty of good commentary on the Amazon Kindle. Robert Love's hands-on review and follow-up cover both Linux-hacker and regular customer views. But there's one question that I haven't seen answered elsewhere: Why doesn't the Kindle support PDF natively?

I think the answer is simple: The Kindle's 800×600 e-ink screen has too few pixels to render a typical PDF file readably, and its refresh rate is too slow for comfortable scrolling. The only practical solution for most PDFs is to extract the text and convert it to a reflowable format like HTML (which Kindle users can do with Amazon's $0.10 wireless service or free PC-based service). The US$700 iLiad (with 64% more pixels) is much better for PDF reading, but will still run into trouble with some files. It seems that the current generation of ebook readers comes with a decision—cheap, e-ink, or PDF: choose any two.

The refresh problem is one reason I'm not sold on e-ink. I'm curious to compare the Kindle screen to my XO laptop, which seems like an interesting compromise between normal LCD and e-ink displays.

Disclaimer: I work for Amazon, but I don't know anything about the Kindle except what I learned from the user's guide and from playing with one at the office.

104 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!