Recent blog entries for cananian

3 Oct 2013 (updated 13 Nov 2013 at 03:08 UTC) »

Rust is not fast

There are plenty of safe high-level languages in the world; JavaScript, for example. Rust is different: it's supposed to be safe and fast.

But Rust is slow. (And its type system hates you.)

Rust is slow because there is lots of hidden indirection ("smart dereferencing") and other hidden costs (ref counting, etc). In low-level C code I can look at a line of code and know roughly how many (slow) memory accesses are present. Not so in Rust.

Further, Rust's type system leads to extra unnecessary copying, just to get your code to compile without massive refactoring of the standard library. When writing rusty-turtle I found myself having to add ~ or @ pointers to my types (forcing extra layers of dereferencing) just to work around the type system. Further, the APIs have a genericity problem: there are lots of duplicate methods, since &-pointers aren't truely generic/orthogonal. (And you will find yourself duplicating methods in your own APIs as well, in order to be able to pass in parameters with different reference types -- or else just throw up your hands and wrap an extra @ layer around everything.)

The ownership type system also fights against typical APIs like find_and_insert for maps, since you don't know (before you do the find) whether or not you will be giving up ownership of the parameter (in order to do an insert). So you just copy the inserted value, always! Cycles are cheap, right?

Rust is also slow because it is not built to be parallel. The language is concurrent, but this is a word game: in the past few years the terms have been redefined such that "concurrent" is (roughly) non-blocking cooperative multitasking (such is implemented by node.js and GNU Pth), and "parallel" is reserved for actually doing more than one thing simultaneously (whether on separate CPUs or separate cores of a single CPU). Rust's memory model doesn't help: there is no shared memory, and ownership types make fork/join parallelism difficult. All inter-task communication is explicit message passing, with the races that entails. (Perhaps I'm spoiled: the Cilk work-stealing nano/microscheduler is my benchmark for speed.)

Some possible improvements:

  • Get rid of smart dereferencing; make it clear when performance is impacted by memory references.
  • Fix bugs with small objects/ABI limitations to avoid unnecessary parameter wrapping.
  • Make & pointers truely generic (or invent a new pointer which is) and do template expansion/method splitting to generate the proper specialized version of the method automatically (although this will exacerbate existing problems with code caching).
  • Better support fast refcounting/fast gc (update coalescing, generations).
  • Support fork/join parallelism and work-stealing.

This post is written from my experience with Rust in May 2013. Some of these problems are known, and some may eventually be fixed. But it makes me wonder what the language is really supposed to be good at. There are already plenty of slow safe languages.

Syndicated 2013-10-03 07:52:59 (Updated 2013-11-13 02:12:03) from Dr. C. Scott Ananian

3 Oct 2013 (updated 13 Nov 2013 at 03:08 UTC) »

JavaScript in asm.js (and a little rust)

Over on twitter, Tim Caswell mentioned, "I think high-level scripting language on top of something like rust.zero would make for an amazing OS." and that set me off a bit. Twitter isn't a great place to write a reasoned discussion of programming languages or implementation strategies, so let's take a shot at it here.

As I've written about on this blog, I've been tinkering for years with TurtleScript, a small learnable JavaScript subset in the spirit of Alan Kay. Over in that twitter conversation David Herman mentioned rusty-turtle, my TurtleScript bytecode interpreter written in Rust. The rusty-turtle codebase includes a REPL which runs TurtleScript's tokenizer, parser, bytecode compiler, and standard library (all written in TurtleScript) through the Rust interpreter. It's quite cute, and I implemented much more of the JavaScript semantics than I strictly needed to (with the side-effect that the behaviors in the JavaScript wat talk now appear quite sane and sensible to me).

I wrote rusty-turtle as a personal warm-up: I was considering taking a job with the fine folks at Mozilla (OLPC having run out of money again) and wanted to understand the technology better. I described a number of further research projects I thought would be interesting to pursue in the rusty-turtle README, including cilk-style fork/join parallelism or transactional memory support (the latter being the subject of my thesis), and a JIT backend using rust's llvm library bindings.

But the true turtles-all-the-way-down approach would be to rewrite the backend using asm.js, which can be trivially JIT'ed (using llvm bindings). Then you've have an entire system from (pseudo-)assembly code up, all written in a consistent manner in JavaScript. To that end, I wrote single-pass type-checker/verifier for asm.js in TurtleScript, discovering lots of issues with the spec in the process (sigh). (I justified this as more "Mozilla interview preparation"! Besides, it was fun.)

Tim Caswell, to finally answer your question: I think that this "JavaScript all the way" system would make an amazing OS. The Rust stuff is just a distraction (except as needed to bootstrap).

In the next post I'll rant a bit more about Rust.

ps. In the end I over-prepared (!): Mozilla's feedback was that I seemed to "know too much about Rust to work on Servo" (Mozilla's experimental web layout engine, written in Rust). Mozilla seems to have reached that awkward size where it can not longer hire smart people and find places for them to contribute; new hires need to fit into precise job descriptions a priori. That sort of place is not for me.

Syndicated 2013-10-03 06:53:22 (Updated 2013-11-13 02:12:45) from Dr. C. Scott Ananian

Puzzles I worked on (MIT Mystery Hunt 2013)

Quick summary of MIT Mystery Hunt 2013 — didn't work on as many puzzles this year, between (a) Not Trying To Win (after writing last year's hunt), and (b) Zachary. Did quite a bit of work on the hunt-solving software; discovered that the current limits to Meteor's scalability are "less than team Codex".

Puzzles I particularly liked:

  • Time Conundrum (except for final extraction)
  • Too Many Seacrests
  • Tuva or Bust (for which I successfully used Prolog in anger)

Other puzzles i worked on:

  • Square Routes
  • The Maze (helped guide final extraction)
  • Czar Cycle (which we never solved)
  • Road Trip (final extraction, with alexp)
  • Space Monkey Mafia (final extraction, with alexp)
  • Diagramless Crossmusic (knew how it worked, but meh)

There were a lot of very interesting puzzle ideas in this hunt. Several of them would have made excellent puzzles, given a bit more focused editing. In particular I want to single out 50/50 and Diagramless Crossmusic as great ideas.

Thanks to the Sages for all their work over the past year. The Mystery Hunt is a ton of work to write, and it's all done for the love of the thing.

Syndicated 2013-01-25 04:16:28 from Dr. C. Scott Ananian

The Gashly-Hunt Tinies (MIT Mystery Hunt 2013)

A is for ADPHI, who ran out of Rs, B is for Better Luck assaulted by czars.
C is for Codex who expired half way, D is for Dataviz stumped by “Wordplay”.
E is for Eigenpirates who left for the beach, F is for Fangorn’s chaotic speech.
G is for Grand Unified Theory’s lost love, H is for herrings caught shifting through drugs.
I is for Illegal, Immoral, and awake; J is for Jones who plagued teams with hard snakes.
K is for Keypad which we did without, L is for Left—as an exercise or just out.
M is for Meteor misstressing trochee; N is for Ninjas searching etsy.
O is for Om Nom locked out of the vault; P is for Part blah blah Who is John Galt?
Q is for Quadragesima Magna Victi In Cratera; R is for Raucous collecting old lira.
S is for Setec humming tunes with 8-bits; T is for Too Long spent reading git hub commits.
U is for Unseen who got caught Up Late; V is for Victory after seventy hours straight.
W is for White Magic which we never solved; X is for Xerox: conundrums resolved.
Y is for You Not Going to Space; Z is for Zero hunts matching this pace.


AdPhi and Better Luck This Time are team names. “Czar Cycle” was a difficult puzzle involving the Cyrillic, Greek, and Roman alphabets.
Codex Zouche-Nuttall and Dataviz are team names. “Wordplay” was a cryptic crossword.
Eigenpirates and Fangorn Foureast are team names. “Chaotic speech” is a reference to the “Grandson of the Realm of Unspeakable Chaos”
Grand Unified Theory of Love is a team name. “Substance Abuse” was a puzzle involving caesar-shifted chemical names.
Illegal, Immoral, & Fattening is a team name. Indiana Jones was the name of a round whose metas involve solving very difficult snake puzzles, resulting in 3d knots which then needed to be identified.
Keypad was the name of the obstacle corresponding to the Erno Rubik round. Left Out and Left As An Exercise For The Reader are team names.
Meteor Lab is a team name. ”Trochees, etc“ was a puzzle involving trochees (pairs of syllables with the first accented, as trochee itself should properly be) and etsy.com
Om Nom Nom is a team name, as is the complete text of Atlas Shrugged, which starts with, "PART I: NON-CONTRADICTION; CHAPTER I: THE THEME 'Who is John Galt?'..."
“VICTI IN CRATERA MAGNA QUADRAGESIMA”,or “conquered in the great/super bowl 40” (ie, SEAHAWKS) was the final cluephrase in the puzzle “Caesar's Palace”. Raucous Raucous Rhinos is a team name. “Collecting old lira” refers to the scavenger hunt puzzle "De-Coins".
Unseen Gambit and Up Late are team names. Seventy hours is a very conservative estimate of hunt length, from a 2pm start on Friday to a noon Monday commencement of the final runaround.
White Magic was a meta puzzle in the Erno Rubik round. The Xerox machine featured prominently in the “Time Conundrum” puzzle, used to create another copy of the instructions so that the first could be sent back in time with the correct answer written on it...
“You Are Not Going To Space Today” was a first-round puzzle. This hunt was the longest hunt ever.

Syndicated 2013-01-23 00:37:10 (Updated 2013-01-23 23:19:46) from Dr. C. Scott Ananian

SDR 0.7

Happy Thanksgiving! Here's SDR 0.7 to celebrate the holiday. Version 0.7 incorporates a number of dance engine refactorings completed shortly after the previous release promised them, as well as (more recently) a number of new call and concept definitions (and test cases) inspired by the C4 calls I am currently studying. I also updated Google App Engine and Google Web Toolkit to the latest versions for the web app, although jMonkeyEngine is still stuck at 2.0 — we might get an Android version of SDR if I manage to rebase to jMonkeyEngine 3.0 for the next release.

Breathing the square properly is still a challenge. Other square dance programs only treat starting and ending formations, but SDR has to consider all of the intermediate positions along the dancers' paths. This leads to some very unusual formations being breathed. As mentioned in the notes for the last release, SDR formulates breathing as a solution to a mixed integer linear programming problem—but there are still a few bugs lurking which cause the constraint solver to blow up from time to time (especially from columns, for some reason). Hopefully I'll be able to dig into this for the next release.

Syndicated 2012-11-22 19:29:56 from Dr. C. Scott Ananian

21 Oct 2012 (updated 11 Jan 2015 at 15:08 UTC) »

Reading Project Talk (and slides)

An unruly tag team of OLPC folks gave a long talk on the Literacy Project today for attendees at this year's OLPC-SF Community Summit. It was streamed live on Ustream: Part 1 (Matt Keller, Richard Smith), Part 2 (Richard Smith, Ed McNierney, C. Scott Ananian, Chris Ball, questions from the audience). We've posted the slides: Matt Keller, Richard Smith, C. Scott Ananian.

You can try out some of the apps mentioned in the talk. Nell's Balloons and Nell's Colors will run in any reasonably-recent Google Chrome or Mozilla Firefox browser. They will also run as a Firefox webapp on Android devices, using the latest Firefox nightly for Android. For deployment we use a slightly-tweaked build of Firefox (adding expanded webapp storage quotas and the ability to use plugins from inside webapps), and a custom plugin to hook up the Funf logging framework. Source code is available on github: nell-balloons; nell-colors. In addition, Chris Ball's "Matching" app for Android is available: apk; source.

Syndicated 2012-10-21 22:51:05 (Updated 2015-01-11 14:53:31) from Dr. C. Scott Ananian

The Importance of Sensing Distance

At IDC 2012 in June, Arnan Sipitakiat and Nusarin Nusen discussed how they are using Robo-Blocks—a turtle robot and “tangible Turtle Blocks”—to teach problem solving and debugging skills to 5- through 12-year-olds.

One of the things I learned from their presentation was that children had difficulty reasoning about relative angles. The Robo-Blocks robot does not have any distance feedback on its motors, so “the result of a program will change depending on the roughness of the surface and the battery level of the robot.” They worked around this issue by developing a protractor tool to guide the children's reasoning about the relationship between the (arbitrary) numbers entered and the amount the robot turned, but some kids still had difficulty. The researchers “often had to insist on trying the protractor” and “some children preferred to keep increasing the turn amount even if a small decrease would have fixed the problem” resulting in programs that had the robot making multiple complete rotations before setting off in the correct direction. The kids were also dissatisfied with polygon-drawing tasks (“turtle geometry”) because the inaccuracies of open-loop control of the robot means that the polygons often didn't close completely, and “[t]his small error turned out to be unacceptable to children.”

So I designed the XOrduino turtle robot from the start to have distance sensors so that it can do accurate turns with closed-loop control. Here's a little video showing how they work in the current (A1.5 / B1) revision of the board:

Some bonus pictures of the speed sensor on the workbench:

  • The robot on the workbench with probes.
    Speed sensor test setup
  • Signal from the motor speed sensor. 5ms/div .5v/div. Motor is running at full speed, unloaded. Two dips are seen: the larger is from a piece of white paper glued to the rim of the gear; the smaller is from a spot made with a white paint marker (the paint didn't stick very well). White-out worked much better (as shown in the video above).
    Oscilloscope trace
  • Oscilloscope settings
    Oscilloscope settings

Syndicated 2012-08-22 16:29:11 (Updated 2012-08-22 16:48:46) from Dr. C. Scott Ananian

XO Turtle Bot drives around

Here's a first look at an XOrduino Turtle bot driving around:

I've checked out all of the functionality on the A1.5 board except the step-up voltage regulator now. I'm optimistic the B1 boards (being made now in Taipei) will be clean.

It will be great when we've got lesson plans written up so kids can learn how to control the bot with Turtle Blocks, and play with the different possible behaviors. Instead of just bumping around ("like a Roomba, except it doesn't vaccuum" a friendly 6-year-old beta-tester told me), you can trace patterns you design, or use the Scratch Sensor Board sensors to make the robot "afraid of sound", "attracted to light", or add your own sensors and behaviors.

Syndicated 2012-08-18 05:13:16 from Dr. C. Scott Ananian

"Hello, World" from XOrduino/XO Stick

Here's a quick look at the next versions of the XOrduino and XO Stick boards. These were assembled from a small quantity of "pre-B1" boards I had made at BatchPCB.

I've uploaded some more pictures to the XOrduino album as well.

Here's a little table relating the board versions pictured with those I've previously discussed.

Build XOrduino XO Stick
A1 v4 v5
This video v6 v7
B1 v8 v14

B1 is "the next run" of boards, already released to the fab house but not yet in hand.

The big feature added to XOrduino after A1 was a motor driver, to allow using the XOrduino as a Turtle robot. The big feature added to XO Stick after A1 was the shield form factor, allowing it to ride piggy back on the XOrduino. This makes it easier to share a single turtle robot with a classroom: there may be only one XOrduino robot base, but each student can have their own low-cost XO Stick "brains". They can take turns snapping their brains on top of the base to drive it.

I haven't finished testing all the functionality of these new boards yet, but it looks like I haven't made any major mistakes! Help still wanted with software, documentation, etc; send email to xorduino@gmail.com if you're interested.

Syndicated 2012-08-15 20:34:02 from Dr. C. Scott Ananian

XO Bot joins the XOrduino and XO Stick

Free things first: I've got parts for 20 copies of the "Mk I" XOrduino and XO Stick. I'm mailing them out for free (!) in exchange for your development help. Send me an email at xorduino@gmail.com describing what you'd like to do with the XOrduino/XO Stick, and your full mailing address. Best 20 or so get kits.

XOrduino A1

Here are some of the projects which you might be able to help with:

  • Assemble an XOrduino / XO stick with an 8-12 year old and document the process. What parts were tricky to solder? Where did polarity matter? How much of the function of the different devices did you find worth explaining? Photos or video of children assembling the device would be great for future publicity, with their permission. (We're not crazy: kids can repair XOs and solder.)
  • Test different configurations of the boards. What are the fewest components necessary for a functional XO Stick? What capacitors are really needed? What's the smallest number of components needed to get the arduino IDE to talk to the XOrduino? Then add the components for the Scratch Sensor Board functionality, and test that with this Arduino sketch (some minor porting required). Try out whatever Arduino shields/old Arduino code you have lying around, and see if there are any gotchas there. Document it all, take photos and video, let me know about bugs and pitfalls.
  • Write some killer education apps! These boards are meant specifically for teaching kids—take the Turtle Art with Sensors ideas as examples, and write up some lessons to teach science. Or take inspiration from the old school "fun with electronics" kits from Radio Shack and recreate some of the popular standbys: a burglar alarm for kids' tree fort, a light-sensitive alarm they can hide in their sibling's drawer, etc. Or a document how to program a robot (more on the robot below) with simple emergent behaviors—avoiding walls, turning toward light, fleeing loud sounds, etc. The Cubelets examples may give you ideas. Take photos and video.
  • Arduino support for the XO Stick. There are a number of projects which add support for the ATtiny85 and friends to the Arduino IDE (for example, this one). Ideally we'd like to make the XO Stick as Arduino-compatible as possible, so we can reuse the excellent Arduino IDE, etc. This involves (a) porting an arduino-compatible bootloader (like usbAspLoader-tiny), as well as (b) porting the Arduino libraries to match the pinout/peripherals of the ATtiny85 and ATtiny861 (this page is a good start).
  • Program an XO Stick from an XOrduino and vice versa. Ideally we'd like to bootstrap the initial chip programming, so that one programmed XOrduino (or XO Stick) can be used to put the initial bootloaders on the others. For technical reasons the XO Stick is probably best as a "clone tool": without interacting with the USB bus it would just copy its internal memory to another XO Stick. The XOrduino is a little easier, just a matter of adapting the existing Arduino sketches and documentation.
  • Debrick an XO from the XO Stick. The XO Stick can talk to the EC programming bus to recover a bricked XO; it can probably also reprogram OpenFirmware. We need to write a bit of code to make it pain-free and document the process. This would make the XO Stick a useful repair accessory for XO deployments.
  • Scratch/Turtle Blocks support for the XOrduino and/or XO turtle bot (see below).

Here's the exciting part two: I'm already working on the XOrduino and XO Stick "Mk II". The latest schematics/boards are in github (xostick, xorduino). The kits I'll be sending out this week correspond to the "A1" tag in those repositories; the "Mk II" revision is on the master branch.

The XO Stick gets a minor change with big implications: instead of using a 20-pin header matching the ATtiny861 pinout, I've widened the board to give the XO Stick a standard Arduino shield connector (and some prototyping area). This opens the way for a port of the Arduino IDE (mentioned above), but it also means that the XO Stick can be mounted on top of an XOrduino. In a cost-conscious classroom environment, this allows a teacher to buy/make one copy of the XOrduino with all of its fancy peripherals (scratch sensors, robot support) and then give each student a copy of the cheaper XO Stick. The students share the XOrduino and swap out their XO Stick "brains" on top to control it or use its peripherals. Mating the two boards also makes it straightforward to program an XO Stick from an XOrduino, or to use the XO Stick's prototyping area to hack together a shield for the XOrduino.

The XOrduino gets a more exciting feature (hinted at above) -- enough peripherals to become the XO Turtle Bot! This is a very low-cost turtle robot based on a Tamiya motor assembly. All of the extra robot components are optional—you can populate just the parts you want—but a classroom can now make their XOrduinos (or XO Stick + XOrduino base) into standalone turtle robots, controlled by Scratch, Turtle Art, or Arduino code. The XO Turtle Bot revision adds a motor driver, two bump switches, a simple 3-cell power supply, and rotation sensors for the motors to the XOrduino. (Arnan Sipitakiat and Nussarin Nusen in their Robo-Blocks presentation for IDC 2012 explained that children find "turn for two seconds" hard to understand; we include motor sensors so that we can "turn 90 degrees" instead.) And of course because the robot is based on XOrduino, you can add whatever other sensors you like and write arduino/Scratch/Turtle Blocks code for it.

XOrduino A1 board on top of Tamiya Twin Motor Gearbox.   XOrduino A1 plugged into USB port; prototype XO Turtle Bot in the background.

I'm excited about the potential of low-cost robotics and the Arduino platform for education. If you are, too, let me send you a kit so you can help out!

Syndicated 2012-08-02 06:39:39 (Updated 2012-08-02 07:14:11) from Dr. C. Scott Ananian

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