BuffaloFeeds » Items by josh

Feeds

104649 items (96858 unread) in 19 feeds

Friends (992 unread)

• 2 Star (79 unread)
• John Carrino (12 unread)
• Comments for Josh the Outspoken (273 unread)
• Josh (34 unread)
• Planet Matt (594 unread)

Build (67517 unread)

• MAKE Magazine (20223 unread)
• Instructables.com (34656 unread)
• Hack A Day (4913 unread)
• Toolmonger (7725 unread)

Heads (712 unread)

• Exploration Through Example
• Paul Graham: Unofficial RSS Feed (112 unread)
• Stevey's Blog Rants (33 unread)
• Joel on Software (205 unread)
• Gibson Blog (239 unread)
• Adventures in Bloggery (123 unread)

News (27430 unread)

• Slashdot (25098 unread)
• Economist.com Global Agenda (1412 unread)
• Ruby Inside (920 unread)

fun (207 unread)

• Templar, Arizona (207 unread)

Items by josh

Comments for Josh the Outspoken

• 

  Comment on Refcounting immutable cyclic graphs by Josh

  Posted: January 25th, 2012, 9:15pm MST by Josh

  When a node is first created it is mutable (edges can be created or changed), but it does not own refs on nodes it points to, so the client of my library is responsible for keeping nodes alive through this first stage. When they client is ready they can “finalize” a set of nodes which does the SCC search and guarantees, from then on, that all reachable nodes are always kept alive.

• 

  Comment on Refcounting immutable cyclic graphs by Josh

  Posted: January 25th, 2012, 9:28am MST by Josh

  Because my objects are immutable once initialized, the graph is immutable also and I can find SCC at initialization time, not when a refcount is decremented to 0. I do have to search, but I can do the search only once per graph.

  This scheme wouldn’t work in most situations where GC or refcounting is used, but I have the luxury of an immutable object graph.

2 Star

• 

  Refcounting immutable cyclic graphs

  Posted: January 21st, 2012, 12:07pm MST by Josh

  Cycles are a thorn in the side of refcounting. But yesterday I discovered (or perhaps rediscovered) a simple, efficient scheme for refcounting cyclic graphs if the defs are immutable: find strongly-connected components and make all nodes in each SCC share a refcount. Beautiful.

  This relies on the graph theory result that if each SCC in a graph is replaced with a single node, the resulting graph forms a directed acyclic graph.

  I’m planning to use this scheme to refcount defs in upb (garbage-collection is a non-starter because I don’t want to have to track a global list of roots or force the client to periodically call a GC function).

• 

  Making Knuth’s wish come true: the x32 ABI

  Posted: September 26th, 2011, 5:34pm MDT by Josh

  Several years ago (though I can’t say exactly how many since it’s not dated) Knuth made the following complaint:

  A Flame About 64-bit Pointers

  It is absolutely idiotic to have 64-bit pointers when I compile a program that uses less than 4 gigabytes of RAM. When such pointer values appear inside a struct, they not only waste half the memory, they effectively throw away half of the cache.

  The gcc manpage advertises an option “-mlong32″ that sounds like what I want. Namely, I think it would compile code for my x86-64 architecture, taking advantage of the extra registers etc., but it would also know that my program is going to live inside a 32-bit virtual address space.

  Unfortunately, the -mlong32 option was introduced only for MIPS computers, years ago. Nobody has yet adopted such conventions for today’s most popular architecture. Probably that happens because programs compiled with this convention will need to be loaded with a special version of libc.

  Please, somebody, make that possible.

  I always thought this made a lot of sense. People have asked distro-makers for this before without a lot of success, but it looks like this is now being worked on by high-profile people in the Linux community. It is called The x32 ABI (see the LWN coverage for a more digestible description). It’s exciting because in some benchmarks this can outperform the x86-64 ABI by 10% or more. It’s a tradeoff — if you don’t need to address more than 4GB of memory, you can get faster programs because smaller pointers have better cache utilization. You’ll use less memory too.

  This could have been done in a way that operated nearly the same as “compatibility mode” (ie. running 32-bit binaries on a 64-bit CPU/OS), which would have required only minimal changes to the kernel/toolchain. But it looks like their plans are more ambitious: they want to be able to use the optimized SYSCALL64 instruction (which is “much faster” than int 0x80 according to H. Peter Anvin), and they’re looking at fixing other problems like 32-bit time_t. So it’s a more substantial effort, but it looks like there’s significant interest and momentum behind this.

  Thinking about how this would affect upb, my impression is that I could use my x86-64 JIT unmodified with x32, since it appears to have all of the same calling conventions. It has the same set of callee-save registers and the same set of registers for parameter transfer, and I think these are the main things upb’s JIT-ted code depends on.

• 

  Beating the compiler

  Posted: September 17th, 2011, 4:08pm MDT by Josh

  It’s been a while since I’ve posted about upb, but I’ve been busy improving it! I think the biggest achievement I can mention is that the core upb APIs (upb_handlers, upb_def, and upb_bytestream/upb_bytesink) are converging to the point where I’m comfortable with people starting to experiment with them. I’m not promising they won’t change at all, but I’m a lot more confident in their overall structure and semantics than I have been previously.

  Notably, I think upb’s deserialization is ready for casual and experimental use. Definitely don’t trust any data to it until it’s better tested, though. I won’t be releasing until things have converged a bit more (and are better tested).

  I gave a talk about upb at Google yesterday that was well-received. One question that comes up is “how are you beating the generated code from the protobuf compiler?” For the record, my JIT appears to be about 25% faster than Google’s protobuf release on a completely apples-to-apples test. It is a bit surprising, since my code has basically the same structure as protobuf’s generated C++ — I don’t invent any new optimizations or anything like that. I think it really comes down to generating better assembly than gcc is.

  We live in a day and age where common wisdom is that you can’t beat a good C++ compiler, or at least not by much, and I think this is probably true for 99% of use cases. But I was first inspired to think that I could beat the C++ compiler in this case by reading this mailing list post from Mike Pall where he explains why you can still beat the compiler for interpreter main loops. A protobuf parser is surprisingly similar to a byte-code interpreter main loop, so I thought I’d give it a shot.

  Below is just the simplest example I could dig up of a side-by-side comparison of my code vs. the compiler’s. What follows is the code to parse a single fixed64 value:

    ; upb JIT assembly:
    mov    rdx,QWORD PTR [rbx+0x2]    ; load fixed64 val out of buffer
    add    rbx,0xa                    ; advance buffer by 10 (2 for tag)
    mov    QWORD PTR [r12+0x40],rdx   ; store fixed64 value in message
    or     BYTE PTR [r12+0x1],0x4     ; set hasbit
    cmp    rbx,QWORD PTR [r15+0xaf8]  ; check for end-of-buffer
    jae    
    mov    rcx,QWORD PTR [rbx]        ; load next tag
    cmp    cx,0x1b0                   ; next field+wt in order?
    je     
  

  There’s not a lot left to cut away here. Compare with protobuf/gcc-generated code:

    ; protobuf/gcc code:
    mov    ecx,DWORD PTR [rbx+0x10]   ; load buffer end
    mov    rax,QWORD PTR [rbx+0x8]    ; load buffer
    sub    ecx,eax                    ; if (buffer_end_ - buffer_ 
    mov    rax,QWORD PTR [rax]        ; load fixed64 val
    mov    rdx,QWORD PTR [rbp-0x48]   ; load this
    mov    QWORD PTR [rdx],rax        ; store fixed64 val in this
    add    QWORD PTR [rbx+0x8],0x8    ; advance buffer
    or     DWORD PTR [r12+0x74],0x800 ; set hasbit
    mov    rdx,QWORD PTR [rbx+0x10]   ; load buffer end
    mov    rax,QWORD PTR [rbx+0x8]    ; load buffer
    mov    ecx,edx
    sub    ecx,eax                    ; if (buffer_end_ - buffer_ 
    cmp    BYTE PTR [rax],0xb0        ; check first byte of next tag
    jne    
    cmp    BYTE PTR [rax+0x1],0x1     ; check second byte of next tag
    jne    
  

  There is some poor register allocation going on here — gcc is repeatedly loading buffer_ and buffer_end_ even though it has plenty of registers to play with. All in all, gcc is generating over twice the number of instructions, over twice the number of loads, and more stores too. Note that this is taken from the middle of a very large C++ function with a big switch statement and a bunch of gotos, and I think it’s just difficult for a compiler to do good register allocation under these constraints.

  If the C++ compiler could know the difference between fast paths and slow paths and do the register allocation solely for the fast paths (spilling everything for the slow paths) it might have a better shot. But still I think it’s just a hard problem.

Comments for Josh the Outspoken

• 

  Comment on Addicted to hardware: new toy on the way by Josh

  Posted: August 26th, 2011, 6:47pm MDT by Josh

  I like it! Unfortunately it doesn’t work too well as a headless always-on box for two reasons:

  1. it loses its wireless connection sometimes and doesn’t automatically re-establish it for some reason. If I log in to it physically and click the wireless network again everything is fine, but that’s no good if you were planning to use it headless.

  2. it doesn’t want to boot up unless it’s connected to a display. so you can’t boot it headless.

  For these two reasons I don’t use it as much as I was expecting. But when I do use it it does just what I was hoping for.

• 

  Comment on upb status and preliminary performance numbers by Josh

  Posted: May 9th, 2011, 12:01pm MDT by Josh

  Will, that’s an interesting question but I doubt that Hotspot could generate code that is as good as mine. Not because I think I’m better at this than the Hotspot authors, but because I am compiling directly from a description of the .proto file into machine code. In the Hotspot case, the flow is more like:

    .proto file -> Java -> JVM byte-code -> machine code

  The fact that you have to go through Java and JVM byte-code first means that you are limited by what can be expressed in Java. For example, Java doesn’t even have unsigned types!

  In fact I think the JIT part is a bit of a distraction, because upb isn’t actually using any run-time information that isn’t available as part of the .proto file to begin with. So even the C++ protobuf compiler (which works ahead-of-time) has just as much information as upb’s JIT does. I’m JITting for convenience, not because I’m using any runtime information (well, at least not yet .

2 Star

• 

  Using dtrace on OS X to debug a performance problem

  Posted: May 8th, 2011, 2:28pm MDT by Josh

  I recently ported upb’s table-based decoder to use setjmp/longjmp-based error handling. I did this largely for code simplicity and readability, so that the non-error code-paths didn’t have to check for errors all the time. But unfortunately I noticed a dramatic 75% performance decrease. What was going on?

  A profile in Shark showed the majority of my time being spent in system calls, but didn’t make it clear which system calls were involved. It sounded like a job for dtrace.

  I used the following script to dump all the system calls that were being issued by my process:

  syscall:::entry
  /pid == $target/
  {
       @[probefunc] = count();
  } 

  I then ran this script on both my old (fast) benchmark and the new (unexpectedly slow) one:

  $ sudo dtrace -c ./old-benchmark -s trace.d
  
    exit                                             1
    fstat64                                          1
    ioctl                                            1
    write_nocancel                                   1
    munmap                                          93
    mmap                                            94
    getrusage                                     7728    
  
  $ sudo dtrace -c ./new-benchmark -s trace.d
  
    exit                                             1
    fstat64                                          1
    ioctl                                            1
    munmap                                           1
    write_nocancel                                   1
    getrusage                                      438
    sigaltstack                                 111773
    sigreturn                                   111774
    sigprocmask                                 223546

  Sure enough, the new version is making a ton of system calls that weren’t happening before, and they appear to be signal related. I investigated the manpage of setjmp/longjmp and found:

  The setjmp()/longjmp() pairs save and restore the signal mask while _setjmp()/_longjmp() pairs save and restore only the register set and the stack. (See sigprocmask(2).)

  The sigsetjmp()/siglongjmp() function pairs save and restore the signal mask if the argument savemask is non-zero; otherwise, only the register set and the stack are saved.

  I replaced my calls to setjmp/longjmp with sigsetjmp/siglongjmp, passing 0 for my signal mask, and the performance problems went away. Score one for dtrace.

Comments for Josh the Outspoken

• 

  Comment on upb status and preliminary performance numbers by Josh

  Posted: April 29th, 2011, 4:25pm MDT by Josh

  Thanks for the correction Russ. I was misled by the Wikipedia page about JSON.

  I think it is safe to say, though, that interpreting all JSON numbers as double-precision is sufficient to be a usable JSON parser, since that what common implementations do.

2 Star

• 

  upb status and preliminary performance numbers

  Posted: April 26th, 2011, 12:18am MDT by Josh

  The last few weeks have been very exciting for upb. On April 1 I checked in a JIT compiler for parsing protobufs, which one might think was an April Fool’s joke, but it’s real and the performance numbers so far have exceeded my expectations.

  Why JIT?

  Before I get to the numbers, I should explain what it even means for upb to have a JIT. If you’re not interested in the technical details, feel free to skip this section to go straight to the impacts and what this means for upb.

  So why a JIT? After all, protobufs are not an imperative language. You can’t write an algorithm in a .proto file. You can’t apply compiler techniques like SSA, strength reduction, tracing, or really any of the things you’d expect from a JIT on a platform like the JVM. There is no byte code or intermediate representation to speak of. So why would upb have a JIT and what on earth would it do?

  To review, a .proto file defines a schema for some messages. In this sense, it is comparable to JSON Schema or XML Schema.

  message Person {
    required int32 id = 1;
    required string name = 2;
    optional string email = 3;
  }

  To support forwards and backwards compatibility, we don’t make any assumptions about which fields we’re going to see or in what order. Instead, on the wire each field is preceded by its tag number. Logically, the serialized version is something like:

  - field number: 1, wire type: varint, value: 1
  - field number 2, wire type: delimited, value: "Josh Haberman"
  - field number 3, wire type: delimited, value: "jhaberman@gmail.com"

  If you were going to write a parser for this, you might create a table of fields, keyed by field number, and a main parser loop that looks something like this:

  while (!done) {
    int type = fields[get_field_number()];
    switch (type) {
      case WIRE_TYPE_VARINT:
        parse_varint();
        break;
      case WIRE_TYPE_DELIMITED:
        parse_delimited();
        break;
      // etc.
    }
  }

  We call this a “table-based parser.” We look up the type in a table of fields, and use that to branch to the correct value parsing function. There are minor variations on this, like using a function pointer instead of a switch statement, but it’s the same general idea. To see an actual program that implements this style of parser, check out my bare-bones 100-line protobuf parser that I wrote a few years ago: pb.c.

  In a way this resembles a byte-code interpreter, and the serialized protobuf resembles byte-code. For example, see the main loop of the Lua interpreter. It has a similar pattern where it extracts an opcode and uses that to branch into a giant switch statement.

  It turns out that if we generate code that is specific to one message type, and takes advantage of the fact that fields are usually encoded in order, we can beat this table-based parser significantly. Google’s main “protobuf” software has done this for a long time: their strategy is to generate C++ classes that are specific to a proto message type (like Person in the above example). This code has been highly tuned and optimized, and the generated parsing code looks something like this:

  while((tag = input->ReadTag()) != 0) {
    field_number = GetFieldNumber(tag);
    wire_type = GetWireType(tag);
    switch(tag) {
      // optional float field1 = 1;
      case 1:
        if (wire_type != FLOAT_WIRE_TYPE) goto error;
        input->ParseFloat();
        // Saves the switch() and type check branch if fields are in order.
        if (input->ExpectTag(2, DOUBLE_WIRE_TYPE)) goto parse_field2;
        break;
  
      // optional double field2 = 2;
      case 2:
        if (wire_type != DOUBLE_WIRE_TYPE) goto error;
  parse_field2:
        input->ParseDouble();
        // saves the switch() and type check branch if fields are in order.
        if (input->ExpectTag(3, INT32_WIRE_TYPE)) goto parse_field3
        break;
  
      // optional int32 field3 = 3;
      case 3:
      // [...]
    }
  }
  

  This code also has a big switch() statement at the top level, but the targets are field numbers instead of wire types. More importantly, each field’s case has a line like this:

  if (input->ExpectTag(3, INT32_WIRE_TYPE)) goto parse_field3

  This is key, because if the fields occur in order (which they usually do) then this branch will always be taken and it will be predicted correctly by the CPU. This can make a huge difference.

  While this kind of C++ code generation has benefited Google’s protobuf software in speed, I always found it inconvenient from a dynamic languages perspective. What dynamic language user wants to have to generate C++ code and link that into their interpreter? We’re not talking about a single C++ extension that you compile once: every single message you define in a .proto file generates different C++ code. So you can’t just apt-get install libprotobuf-python and be done with it, you have to generate C++ for every message that your specific app wants to use.

  This is where the JIT comes in. If we can generate machine code at runtime, we can get the speed benefits of the generated code without having to generate, compile, and link C++ into our interpreters or VMs. You could compile the library once, and after that you can dynamically load message definitions but still get the fastest possible parsing.

  Preliminary results

  I knew all of the theory I just described before I started writing a JIT. But theory is just that — theory. What would actually happen when I implemented a JIT?

  The results exceeded my expectations. I still am being somewhat cautious, because there are so many dimensions to any performance equation, and because benchmarks are not guaranteed to correspond to real-world performance. That said, here are my preliminary results. You can reproduce these by obtaining upb from GitHub and running make benchmarks followed by make benchmark (you have to define -DUPB_USE_JIT_X64 to get the JIT).

  Parsing an 80k protobuf into a data structure repeatedly,
  calling Clear() between each parse.  (proto2 == Google protobuf)
  
  proto2 table-based parser      38 MB/s
  proto2 generated code parser   265 MB/s
  upb table-based parser         340 MB/s
  upb JIT parser                 741 MB/s

  The results above are designed to be as apples-to-apples as possible. In other words, I disabled upb’s optimization that avoids memcpy() because Google’s protobuf doesn’t support it in its open-source release. I think the reason that even my table-based parser beats Google’s generated code here is because proto2 implements Clear() in a sub-optimal way that requires an extra pass over the message tree; see my comment in upb_msg.h for more info.

  Things get even better if we allow ourselves to drop the constraint of being apples-to-apples with proto2. upb is capable of stream-based parsing like SAX, whereas proto2 only supports a DOM-based approach where you parse into a data structure. If we include the performance numbers for stream parsing, and for DOM-based parsing that avoids memcpy, we get:

  upb table-based stream parser    420 MB/s
  upb JIT no-memcpy() DOM parser   870 MB/s
  upb JIT stream parser           1430 MB/s

  If you’re like me when I first saw these numbers, your jaw is on the floor at seeing almost 1.5GB/s doing stream parsing of protocol buffers. At this point we are 5x proto2′s highly optimized generated code.

  upb’s JIT isn’t complete and can’t handle all cases, but these performance numbers should still be valid because these benchmarks only used the parts of the format that are currently supported.

  So when can I USE it? And can I help?

  One reason I’ve avoided posting these extremely positive results so far is that I hate to get people excited about something that’s still not ready for users yet.

  Adding support for the JIT required making extremely large and intrusive changes to the core interfaces, like this 3000 line refactoring that had to be completed before I could write even the first line of the JIT. I need to have the flexibility to change core interfaces like this still, because the design is still converging. So as much as I wish I could say it’s ready to go, I still need to hold off on a real release.

  The good news is that the design is still making huge strides. In the last few weeks I’ve been refining my scheme for how upb will integrate into different VM’s and language runtimes, and I feel more confident than ever that the language bindings for Lua, Python, etc. will be some of the fastest extensions ever offered for this kind of functionality.

  As a preview for where this is going, I think that upb will even be usable as a JSON library, offering speed that is as good or greater than any existing JSON libraries. JSON can be directly mapped onto a subset of protobufs (JSON only uses double-precision numbers) and the protobuf text format is already extremely similar to JSON. So all the work I’ve done to optimize memory layout and dynamic language object access should apply.

  And while I’m really happy to get offers to help out, it’s still at a stage of design where I need to be doing most of the work. Working on upb generally involves pacing around my apartment deep in thought about all the requirements and use cases I want to satisfy and brainstorming a million different approaches until I converge on the the one that is the smallest, fastest, and most flexible. It’s hard work but I love it, and the more time that passes the more convinced I am that this is going to be big.

Comments for Josh the Outspoken

• 

  Comment on EINTR and PC loser-ing (The “Worse Is Better” case study) by Josh

  Posted: April 24th, 2011, 12:37am MDT by Josh

  Thanks for the comment! I agree that providing EINTR for applications that want it can possibly be useful. But I think the way it’s exposed in the API breaks the rule of “make simple things easy and hard things possible.” Since it’s very uncommon that a program wants to handle EINTR, I think it would be better to have separate versions of the functions (or a boolean parameter to these functions) that lets you enable EINTR only for calls where you want to handle it.

  // Standard write() call.  Will never return EINTR.
  ssize_t write(int fildes, const void *buf, size_t nbyte);
   
  // Interruptible write() call, may return EINTR.
  ssize_t interruptible_write(int filedes, const void *buf,
                              size_t nbyte);

  As it’s written, since SA_RESTART is a property of the signal handler and not of the interruptible system call itself, all such system calls are potentially interruptible, so they all have to handle EINTR.

2 Star

• 

  ARM architecture is mired in oppressive legalese

  Posted: April 18th, 2011, 11:36pm MDT by Josh

  My Efika MX Smarttop came and I’ve had some fun compiling upb for it and trying it out. I don’t have a pressing ARM use case yet, but I want to work ahead a bit and get familiar with the architecture so that when I do want to program for it I’m not starting from scratch.

  I went to the ARM website to get my hands on some documentation. I was prepared to buy physical books if that is their authoritative documentation, but it appears that they have PDFs for the architecture’s reference manuals.

  So far so good — this is on par with Intel which has a nice and easily accessible website where you can download any of their manuals in like 5 seconds. I’ve downloaded them and referenced them a countless number of times.

  But I get no such love from ARM. Strike 1: the ARM website won’t let you download the manuals unless you have registered first. Not cool ARM, not cool. I grudgingly give them my name, email address, company name, country, and state. And the website warns:

  Note: We recommend using your business email address to ensure you can access all your relevant services

  This is a vague but ominous warning that if you use a personal email address the registration might not work correctly.

  But fine, I go through with the registration. Now I can download the manual, right? Turns out no: first I have to accept a EULA! It begins:

  USER AGREEMENT FOR THE ARM ARCHITECTURE REFERENCE MANUAL

  THIS AGREEMENT (” AGREEMENT “) IS A LEGAL AGREEMENT BETWEEN YOU (EITHER A SINGLE INDIVIDUAL, OR SINGLE LEGAL ENTITY) AND ARM LIMITED (“ARM”) FOR THE USE OF THE ARM ARCHITECTURE REFERENCE MANUAL. ARM IS ONLY WILLING TO PROVIDE ACCESS TO THE ARM ARCHITECTURE REFERENCE MANUAL TO YOU ON CONDITION THAT YOU ACCEPT ALL OF THE TERMS IN THIS AGREEMENT. BY CLICKING “I AGREE” OR BY DOWNLOADING OR OTHERWISE COPYING THE DELIVERABLES YOU INDICATE THAT YOU AGREE TO BE BOUND BY ALL THE TERMS OF THIS LICENCE.

  This is all just to read some documentation. Not impressed. ARM, We’re off to a rocky start.

• 

  EINTR and PC loser-ing (The “Worse Is Better” case study)

  Posted: April 18th, 2011, 2:57am MDT by Josh

  Richard Gabriel’s 1989 essay Worse Is Better is a famous comparison between LISP and Unix/C that pops up from time to time and is guaranteed to spark a spirited discussion. The philosophical argument itself is not something I want to get into right now; I am interested in the technical content of the essay. What always bothered me about this paper is that I never fully understood Gabriel’s primary example of a dirty hack vs. “the right thing.”

  His example is “the PC loser-ing problem,” which he describes thus:

  Two famous people, one from MIT and another from Berkeley (but working on Unix) once met to discuss operating system issues. The person from MIT was knowledgeable about ITS (the MIT AI Lab operating system) and had been reading the Unix sources. He was interested in how Unix solved the PC loser-ing problem. The PC loser-ing problem occurs when a user program invokes a system routine to perform a lengthy operation that might have significant state, such as IO buffers. If an interrupt occurs during the operation, the state of the user program must be saved. Because the invocation of the system routine is usually a single instruction, the PC of the user program does not adequately capture the state of the process. The system routine must either back out or press forward. The right thing is to back out and restore the user program PC to the instruction that invoked the system routine so that resumption of the user program after the interrupt, for example, re-enters the system routine. It is called “PC loser-ing” because the PC is being coerced into “loser mode,” where “loser” is the affectionate name for “user” at MIT.

  The MIT guy did not see any code that handled this case and asked the New Jersey guy how the problem was handled. The New Jersey guy said that the Unix folks were aware of the problem, but the solution was for the system routine to always finish, but sometimes an error code would be returned that signaled that the system routine had failed to complete its action. A correct user program, then, had to check the error code to determine whether to simply try the system routine again. The MIT guy did not like this solution because it was not the right thing.

  The New Jersey guy said that the Unix solution was right because the design philosophy of Unix was simplicity and that the right thing was too complex.

  When I read this I always had a burning desire to know: how did the story end? How do modern operating systems resolve this problem — the “dirty hack” way or the “right way?” What part of our modern POSIX interfaces are affected by this question?

  There are several things that never made sense to me about this example. First of all, why would you need to abort a system call just because an interrupt occurred? I investigated the Linux source and it seems quite clear that interrupt handlers can return to either the kernel or userspace — whichever was running when the interrupt fired. So I don’t see why you’d need to “coerce” the system into “loser mode” at all.

  But let’s suppose you accept this as a given — we will assume that when a hardware interrupt occurs, you must exit to user mode. I still don’t see the difficulty in automatically re-invoking the system call. It’s true that invoking the system routine is a single instruction, but why is it that “the PC of the user program does not adequately capture the state of the process,” as Gabriel’s essay states? What other process state do we need to capture? The registers must already be saved when the syscall is entered, because they must be restored even with a completely normal syscall return. So if we want to re-invoke the system routine, it should be as easy as simply re-executing the instruction that made the system call. Right?

  The whole example confused me quite a lot until I had the idea to replace “interrupt” in the above description with “signal.” This is not such a stretch, since signals are essentially user-space software interrupts. With this small change, everything started to make a lot more sense. If a signal was delivered to a process that was currently inside a system call, that signal handler could invoke a system call itself, which would cause us to re-enter the kernel. I could easily see how the complexity of dealing with this could have led early UNIX implementors to simply abort the original system call before delivering the signal.

  But this is only speculation about what UNIX was like in the mid to late 80s when “Worse is Better” was written. I could be completely off the mark in this analysis — maybe returning to the kernel from a hardware interrupt handler really wasn’t implemented at that time. Or maybe saving user state really was difficult for some reason. I’d love to hear from anyone who has more historical context about this. But the essay contains an important clue that seems to reinforce my speculation that it’s actually about signals.

  UNIX and EINTR

  If we look closely at the “Worse is Better” essay, we get a strong clue about what the Unix guy in the story might have been talking about:

  The New Jersey guy said that the Unix folks were aware of the problem, but the solution was for the system routine to always finish, but sometimes an error code would be returned that signaled that the system routine had failed to complete its action. A correct user program, then, had to check the error code to determine whether to simply try the system routine again.

  As someone who has done a lot of Unix system-level programming, this sounds to me like it must be describing EINTR, the error code in Unix that means “Interrupted system call.” To give a quick description of EINTR I’ll enlist the help of my trusty copy of “Advanced Programming in the Unix Environment” by W. Richard Stevens:

  A characteristic of earlier UNIX systems is that if a process caught a signal while the process was blocked in a “slow” system call, the system call was interrupted. The system call returned an error and errno was set to EINTR. This was done under the assumption that since a signal occurred and the process caught it, there is a good chance that something has happened that should wake up the blocked system call.

  [...]

  The problem with interrupted system calls is that we now have to handle the error return explicitly. The typical code sequence (assuming a read operation and assuming that we want to restart the read even if it’s interrupted) would be

  again:
    if ((n = read(fd, buf, BUFFSIZE)) 
  

  This sounds an awful lot like the the New Jersey guy's approach from the story, which required a correct program "to check the error code to determine whether to simply try the system routine again." And there's nothing else in Unix that I've ever heard of that's anything like this. This must be what the New Jersey guy from the story was talking about!

  But note that in W. Richard Stevens' explanation this isn't some dirty hack! It's not a case of cutting corners that is justified by favoring implementation simplicity over interface simplicity. Stevens describes it as a deliberate design decision that gives users the capability to abort a long-running system call if you catch a signal in the meantime. Now you could easily see this as a rationalization of a dirty hack ("it's not a bug, it's a feature!"), but it certainly seems plausible that if you catch a signal while you're blocked on a long system call, the signal might make you decide that you don't want to wait for the long system call any more. Indeed, Ulrich Drepper claimed in 2000 that "Returning EINTR is necessary for many applications," though it would have been helpful if he had expanded on this point by giving some examples.

  Of course, the price we have paid for this capability is that we have to wrap all of our potentially long system calls in a loop like the example above. If we don't, our system calls can start failing and causing program errors whenever we catch a signal. You may think that you don't use any signals yourself, but are you sure that none of your libraries do? On the flip side, if you're implementing a library you can never know if the main application will use signals or not, so any library that wants to be robust will have to wrap these system calls in a retry loop.

  Since the vast majority of programs will always want their system calls to continue even when a signal is received, 4.2BSD (released in 1983) implemented support for automatically retrying most system calls that could previously fail with EINTR. To me this sounds exactly like what the MIT guy in Richard Gabriel's story was saying is "the right thing." In other words, Berkeley UNIX was already doing "the right thing" five years before "Worse is Better" was written!

  Modern POSIX APIs allow both behaviors (either restarting the system call automatically or returning EINTR) -- this is controlled by the SA_RESTART flag. The following program illustrates both behaviors:

  
  #include 
  #include 
  #include 
  #include 
  #include 
  
  void doread() {
    char buf[128];
    printf("doing read() into buf %p\n", buf);
    ssize_t ret = read(STDIN_FILENO, buf, sizeof(buf));
    if (ret  1) ? SA_RESTART : 0;
    sigaction(SIGHUP, &action, NULL);
  
    doread();
    return 0;
  }
  

  Here are the results of running the program three different times. I've bolded the parts where I typed to give the program input on stdin. You can also see where I sent the program a SIGHUP.

  $ ./test
  doing read() into buf 0x7ec7959c
  INPUT FROM TERMINAL
  read() for buf 0x7ec7959c returned data: INPUT FROM TERMINAL
  $ ./test
  doing read() into buf 0x7ef6659c
  received signal 1
  doing read() into buf 0x7ef66204
  INPUT FROM TERMINAL
  read() for buf 0x7ef66204 returned data: INPUT FROM TERMINAL
  read() for buf 0x7ef6659c returned error: Interrupted system call
  $ ./test give_me_sa_restart
  doing read() into buf 0x7eb7657c
  received signal 1
  doing read() into buf 0x7eb761e4
  INPUT FROM TERMINAL
  read() for buf 0x7eb761e4 returned data: INPUT FROM TERMINAL
  INPUT FROM TERMINAL AGAIN
  read() for buf 0x7eb7657c returned data: INPUT FROM TERMINAL AGAIN
  

  Conclusion

  You might ask "why all the fuss over a little example?" As I mentioned, my primary motivation in researching all of this was to get to the bottom of this issue and understand how it plays out in modern operating systems.

  But if we were going to take all of this information and reflect on the "Worse is Better" argument, my personal observations/conclusions would be:

  • The "worse" system (Unix) did indeed do "the right thing" eventually, even if it didn't at first. "Worse is better" systems incrementally improve by responding to user needs. Since users got tired of checking for EINTR, the "worse" system added the functionality for addressing this pain point.
  • The whole thing did leave a rather large wart, though -- all Unix programs have to wrap these system calls in an EINTR retry loop unless they can be absolutely sure the process will never catch signals that don't have SA_RESTART set. So there is a price to pay for this incremental evolution.
• 

  Addicted to hardware: new toy on the way

  Posted: March 31st, 2011, 2:50am MDT by Josh

  I’m addicted to hardware. I can’t stop thinking about all of the CPUs that currently exist, how they compare to each other, and how to write the fastest possible code on them. (Actually I want to learn FPGA programming too, in case they ever start bundling FPGAs with computers).

  A year and a half ago I bought a SheevaPlug which is a little ARM computer that’s hardly bigger than a wall wart AC adapter. It has USB and Ethernet and that’s about it (no display). Unfortunately when I tried to start playing with it again tonight I discovered it was bricked thanks to a faulty power supply, which is apparently a very common problem with SheevaPlugs.

  I was a bit sad about this, and I started looking for alternatives. I wanted something that runs on a non-x86 architecture and that I could stick in a closet and SSH to. I discovered that there is a new form factor of computers known as a nettop. I found a nettop that appears to fulfill my wishes perfectly: the EFIKA MX Smarttop made by a company called Genesi. It’s surprisingly capable for $129: it’s powered by an ARM Cortex-A8 800MHz CPU, has 512MB RAM, 8GB of flash, Ethernet, WiFi, Bluetooth, USB, and 720p video output through HDMI (with hardware-accelerated video decoding). Not bad for $129! And it has a maximum power consumption of 15W.

  So I ordered one — will look forward to seeing if it is really all it’s stacked up to be!

• 

  When a compiler’s slow code actually bites you

  Posted: March 19th, 2011, 4:26pm MDT by Josh

  A few days ago I posted GCC: the impressive and the disappointing where I looked at some cases where GCC produces not-quite-optimal code. One of the comments on that post was (emphasis mine):

  So, it seems like there is a much better way to give the compiler a shot at doing the right thing: [snip suggestion]. I think you will find the compiler will generate quite efficient code in this case, particularly if you look at the real execution overhead, rather than what the assembler looks like.

  This is a common attitude I encounter when I am discussing my attempts to optimize my protocol buffer decoding library upb. Programmers love to tell other programmers that they are prematurely optimizing, and most of the time they’re right. I’m sure to some people it seems ludicrous that I would be looking at assembly language output to determine whether it is efficient enough. For 99.99% of programs, it would be. But I’m working in one of those rare domains where it actually matters. And today I encountered pretty convincing evidence that the compiler’s bad code is actually affecting me.

  The compiler’s bad code in this case is an example of a bug I previously filed on GCC: struct returned by value generates useless stores. Though I had previously observed that bug only by inspecting assembly language output, today I had it show up on an actual profile as clear as day. Here is a screenshot from Shark (click to get full-size):

  

  To summarize, the compiler took the code:

  typedef struct {
    upb_flow_t flow;  // An enum defined elsewhere.
    void *closure;
  } upb_sflow_t;
  
  upb_flow_t upb_dispatch_startsubmsg([...]) {
    // [...]
    upb_sflow_t sflow = f->cb.startsubmsg([...]);
    if (sflow.flow != UPB_CONTINUE) {
      // [...]
    }
  

  …and turned that function call/test into this awful machine code (here in its Intel-syntax form):

    call   QWORD PTR [r12 + 16]
    mov    DWORD PTR [rbp - 64], eax
    mov    QWORD PTR [rbp - 56], rdx
    mov    rax, QWORD PTR [rbp - 64]    ; loads rax with data it already has.
    mov    QWORD PTR [rbp - 48], rax    ; stores rax into the stack a second time.
    mov    QWORD PTR [rbp - 40], rdx    ; stores rdx into the stack a second time.
    mov    edx, DWORD PTR [rbp - 48]    ; loads edx with data already in rax.
    testl  edx, edx
  

  ..and then (this is the important part) in an actual profile it shows up as being 43.4% of the execution time of a hot function in my program.

  This is not a slam against the GCC developers. GCC is a big and complex piece of software, and they have to prioritize all sorts of different bugs, feature requests, new hardware, etc.

  This is just a reminder to those who jump to dare-I-say “premature” conclusions about what is premature optimization: some of us really are working in domains where things like virtual function overhead, branch predictability, and the efficiency of the compiler’s code make a difference.

• 

  GCC: the impressive and the disappointing

  Posted: March 4th, 2011, 12:58am MST by Josh

  In my work on upb I’ve looked at a lot of compiler-generated assembly code. I frequently want to know how GCC will compile a certain block of code, so I’ll write a little test program in C and use objdump to look at the object file.

  Over two years of doing this, I’ve had many moments where I am pleasantly surprised at how smart the compiler is being. C compilers can figure out a lot. I demonstrated a few examples of this on stackoverflow.com — see here and here.

  But once in a while I am disappointed, because GCC doesn’t figure something out that I really wish it could. For example, I have a situation where I have a callback interface, but one of the parameters to my callback is something that a lot of clients don’t need. For convenience, I want to let them register a callback that doesn’t take the final parameter. But to be ANSI C, I can’t cast between the two callback types, I need to store the two possible callback types in a union. My quick test looked like this:

  // My two callback types -- the second takes an extra parameter.
  typedef union {
    void (*f1)(int);
    void (*f2)(int, int);
  } funcs;
  
  // I store "which" separately to track which type of callback was registered.
  void foo(funcs f, int which) {
    int a = 5, b = 10;
    if (which) {
      f.f1(a);
    } else {
      f.f2(a, b);
    }
  }

  Now on x86-64, parameters are passed in registers (thank god!), so there’s no actual reason to branch here. You might as well just always put both values in registers, because if we were calling “f1″ it will just ignore the register that’s holding the second parameter, or overwrite it which is fine too. The only reason we put the “if” in the C code was to be ANSI C compilant — according to the standard you can’t cast between function pointer types.

  But alas, GCC didn’t figure this out:

  0000000000000000 :
     0:	85 f6                	test   esi,esi
     2:	48 89 f8             	mov    rax,rdi
     5:	75 11                	jne    18 
     7:	be 0a 00 00 00       	mov    esi,0xa
     c:	bf 05 00 00 00       	mov    edi,0x5
    11:	ff e0                	jmp    rax
    13:	0f 1f 44 00 00       	nop    DWORD PTR [rax+rax*1+0x0]
    18:	bf 05 00 00 00       	mov    edi,0x5
    1d:	ff e0                	jmp    rax

  Notice it put a branch in there (“jne”) just to avoid putting the value 10 (0xa) in register esi for the one-argument path.

  It’s even worse if I give both functions one parameter, but of different types:

  typedef union {
    void (*f1)(int);
    void (*f2)(long);
  } funcs;
  
  void foo(funcs f, int which) {
    int a = 5;
    if (which) {
      f.f1(a);
    } else {
      f.f2(a);
    }
  }

  In this case, GCC again generates a branch, but both paths have identical code in them!

  0000000000000000 :
     0:	85 f6                	test   esi,esi
     2:	48 89 f8             	mov    rax,rdi
     5:	75 09                	jne    10 
     7:	bf 05 00 00 00       	mov    edi,0x5
     c:	ff e0                	jmp    rax
     e:	66 90                	xchg   ax,ax
    10:	bf 05 00 00 00       	mov    edi,0x5
    15:	ff e0                	jmp    rax

  Both branches simply move 5 into edi and jump to rax. There is absolutely no reason to branch here. Sigh.

  C compilers are smart, but have their limits. Another thing this demonstrates is how programming in C can be a bit constraining compared to assembly language. The only reason I’m jumping through these hoops to begin with is that C has very strict rules about pointer conversion: you can’t just go around casting one function pointer type to another, because you’ll get undefined behavior. But if you’re programming in assembly there is no undefined behavior, no worrying about aliasing, etc. The code I’m trying to get C to generate in a standards-compliant way would be trivial to write in assembly language directly.

  Of course in that case I’d have to implement the assembly language on every platform I wanted to target. In the end I’ll probably use the branchy version that the compiler will generate; the branch will probably predict pretty well, and more importantly for the real fast path for protobuf decoding I have a JIT on the way…

• 

  Gazelle being integrated into a syntax aware editor

  Posted: February 14th, 2011, 12:53am MST by Josh

  I’ve been meaning to post this for several days now: I was very excited to hear on the gazelle-users mailing list that Gazelle is being integrated into a syntax-aware editor called Kod. See the screencast for a preliminary demo.

  This is very exciting for me, because the premise that a text editor could use a real parser as you type was one of my major motivations for creating Gazelle. Most text editors clever pattern matching for the syntax highlighting, but since they aren’t real parsers they can get confused. More importantly, they can’t give you true syntax-aware completion. The notable exception is Java editors like Eclipse, which do this quite well, and I hear that Microsoft’s IDEs are good at it too. But I always wanted an editor where you could add new languages easily and have more ability to tinker with how this syntax information is used. I think it could open up so many doors.

  Given this, I was very excited when Rasmus Andersson from the Kod project wrote to the gazelle-users mailing list asking if Gazelle was a dead project, or if it was something he and his team should invest effort into integrating with Kod. I replied that it was definitely not a dead project, but that it is still subject to major change. That didn’t seem to dissuade him though, and I look forward to learning from their needs and folding their improvements back into Gazelle.

• 

  Gazelle/upb status

  Posted: January 28th, 2011, 11:35am MST by Josh

  It has been just over a year since I last posted, leading some people to rightfully wonder whether my projects Gazelle and upb are abandoned. The answer to that question is a resounding “no.” I am more motivated to complete Gazelle and upb than I have ever been, and I have been working on upb actively lately (here are my recent commits).

  However, if I’ve learned one thing over the last several years of working on Gazelle and upb, it’s that I am extraordinarily bad at knowing how close I am to being ready to release. I don’t want to make any predictions or promises. I honestly thought I was almost ready to release upb a year and a half ago, but I’ve almost completely rewritten it twice since then. Each time it gets significantly better and closer to being what I want it to be. Once I have a release I’ll describe more about the stages of evolution it went through and how each iteration was objectively better than the one before it.

  The core interfaces have gotten to a point where I’m really happy with them and feel no more need to rework them. I think they will continue to evolve incrementally, but not in a way that requires redoing them completely. Here are the most core interfaces — if you’re interested in upb, I recommend reading these headers. I’ve just added substantial comments to explain them, and more than anything these will give you a taste of what upb is all about:

  • upb_stream.h, the streaming interfaces for doing SAX-like tree traversal of protobuf data, and abstractions of fread()/fwrite(). These are probably the most important interfaces in all of upb, since all of the encoders and decoders are based on them.
  • upb_string.h, an immutable, length-delimited (instead of NULL-terminated), reference-counted string type.
  • upb_def.h, the data structures for a protobuf schema (.proto file) and routines for loading them.

  By the way, I also mean to write zero-overhead C++ wrappers around the above to give you C++ programmers a nicer interface at no cost.

  With those set, I have been rapidly getting everything building/working again. It’s a bit annoying to rewrite upb_def.c for the third time (literally) but it feels good knowing the interfaces are right.

  So I have renewed optimism that I’ll be releasing soon. And once I’m happy with upb, it’s back to Gazelle.

Josh

• 

  habes @ 2010-08-21T22:54:00

  Posted: August 21st, 2010, 3:54pm MDT by Josh

  Edit: See comments, I've changed my mind on this issue, but left my original writing here to show what my commenters are responding to.
  
  This mosque debate keeps coming up, and shows no signs of going away, so I feel the need to express my opinion.
  
  I'm somewhat distressed that my liberal friends who I usually see eye-to-eye with are almost all quite judgmental of the opinion that there could be any good reason to oppose this particular mosque on this particular site. There seems to be an overriding feeling that religious freedom demands that we not only allow this mosque to be built, but that we also give it our moral support.
  
  My feeling at the moment is that there's not any good basis to actually deny the legal right of the mosque to be built at ground zero, but that I would criticize the imam's decision to move forward with the project at this location. I would join the voices that urge him to move it elsewhere. As Pope John Paul told the Catholic nuns who were going to move into a building near Auschwitz and build a cross there, "keep the idea, move the address."
  
  If we agree that they have a legal right to proceed with the project (just as, by the way, their detractors have a legal right to protest outside it every day of its existence if they decide to) we can stop talking in terms of a religious freedom question and ask the more interesting question of whether it's a good idea that deserves our moral support.
  
  The self-stated mission of the Cordoba Initiative is to improve Muslim-West relations. But this building hasn't even been built yet and already the project is worsening Muslim-West relations. To build bridges and cultivate trust you have to be sensitive to the other side. What if a Christian organization built a center like this in a Muslim country, but put a picture of Muhammad on the side? It would be an instant fail, even if their genuine intention was to improve relations.
  
  I think the analogies are useful: an American cultural center at Hiroshima in 1954, or at Dresden? A German cultural center at Auschwitz in 1954, or on the beaches of Normandy? The analogies help because they take the "religious freedom" argument out of it. If we grant that the project is legal (thus satisfying religious freedom), it's becomes a question of whether the gesture is sensitive or not and whether we should give it moral support.
  
  I don't think it's unreasonable to petition the imam to relocate this center. The US is almost 4 million square miles in area. New York City alone is 500 square miles. Why must this center be built on the 0.000025% of the country where Islamic extremists attacked us? Why would a center devoted to building east/west relations want to evoke that memory which is still quite fresh in people's minds? Why does the imam resist a land swap arrangement, which could be the perfect compromise -- allowing the center to be built without causing offense to >50% of Americans -- without any explanation but that the project will continue according to plan? I just find it hard to believe that someone who is already creating such division and mistrust is going to build east/west relations once the project is actually built.
  
  Are there bigots who are opposing this just because they don't like Islam? Are there people who truly don't respect religious freedom? Probably. I haven't really read anything from people like that, but I'm sure they're out there. Don't let such people side-track the debate.
  
  The point is that this project is achieving the opposite of its stated goal by uncompromisingly moving forward with a plan that is insensitive to the very Westerners it is trying to build trust with. What they're doing might be legal, but I think it's a bad idea and this is why I oppose it from a moral standpoint, though I don't deny that they have the right to build it.

2 Star

• 

  Torn over the C++ question

  Posted: December 2nd, 2009, 1:17pm MST by Josh

  I am having a very difficult time deciding whether to go through with the C++ port of upb or to stay in C.

  I’ve ported about one third of upb to C++, on a branch, to see how it would turn out. It was a ton of work. Here are my current observations:

  • The C++ is cleaner, more readable, less error-prone code. It’s just a fact. Compare for yourself (C: upb_def.h, upb_def.c; C++: upb_def.h, upb_def.cc). This is due to numerous factors:
    • type-safe containers means fewer casts.
    • “public” and “private” keywords make it easy to separate the private parts of your interface, without having to specify in comments which is which.
    • namespaces and class scope mean that I don’t have to write out my identifiers like upb_fielddef_dothis(), I can just write DoThis().
    • real inheritance and member classes mean I don’t have to explicitly call all the right constructors/destructors, or write explicit casts for upcasts
    • destructors that are guaranteed to run on scope exit mean I can use RAII patterns like mutexes that automatically unlock when the scope is exited
  • The source got shorter; the portion I ported went from 1483 lines to 1133, or a ~30% reduction.
  • The binary got a LOT bigger. I had one function get literally 5x as big. I haven’t figured out why this happened yet. I used templates to make the table generic, but I was extremely careful to make sure that the template only generated a small amount of code — basically just the hash lookup routine, which is small (note: the hash function for strings was not templated or inlined). But another issue is that the C++ compiler appears to emit multiple copies of the same function in the same object file! For example, I found some virtual destructors emitted literally three times in the same file. Why is this?
  • I just heard back from a security guru from the Google security team, who said that C is often easier to audit than C++ because it’s easier to figure out what is actually going on, without having to dig through layers of abstraction. This surprised me (maybe it shouldn’t have, since Sam Quigley said the same thing in a comment on my last entry), but I was also a little bit relieved.

  I’m leaning towards sticking with C, for the following reasons:

  • C++ compilers aren’t very good at keeping things small, even when you are juducious with your use of templates.
  • C++ compilers are much more complicated that C compilers, and therefore not as ubiquitous or as easy to trust generally.
  • C isn’t harder to audit for security than C++, and may actually be easier.

  I’ll try to take some of the lessons I learned from my partial C++ port to make the C more readable.

Comments for Josh the Outspoken

• 

  Comment on Porting upb to C++? by Josh

  Posted: December 1st, 2009, 10:55am MST by Josh

  @Alejandro: Wow, I didn’t realize there was already someone wanting to use upb on an embedded platform! I definitely want to keep supporting your use case if I can. I think the best way forward will be for me to get a C++ to C translator like Comeau C++. Then I can keep writing in C++, but ship C files that you can build with a plain C compiler. Do you think that will work for you?

• 

  Comment on Porting upb to C++? by Josh

  Posted: December 1st, 2009, 9:30am MST by Josh

  @Alejandro: If you want to influence my decision, you should tell me why you don’t want me to. I definitely have resisted, but practical reasons are demanding that I do. But maybe you are thinking of practical reasons that I’m missing.

2 Star

• 

  Gazelle/upb status and plans (aka: On Releasing)

  Posted: November 28th, 2009, 6:24pm MST by Josh

  This summer my friends Ben and Mike gave me grief about never releasing anything. Their criticism is definitely valid to some degree. I’ve been working on Gazelle for about two years now, and upb for almost one. Gazelle has had four releases in that time, but they have mostly focused on moving Gazelle to where I think it ought to be, as opposed to releasing something hacky that people can actually use now. There is a class of problems that Gazelle is useful for now, but it is pretty small in comparison to the amount of work I’ve put in.

  I haven’t released upb at all yet, and my last message indicating I’m thinking of porting it to C++ will probably make skeptical readers think I’m moving farther away from a release rather than closer to one.

  Since I agree that my progress doesn’t look too promising to someone observing from the outside, let me say where I think these projects currently are, where they’re going, and when they’re likely to release.

  First of all, Gazelle is currently pushed on the stack until I have upb released. The reason is that I realized that Protocol Buffers are the answer to two big problems I was facing with Gazelle:

  1. byte-code format: right now the Gazelle byte-code format is LLVM’s BitCode, which is the format LLVM uses for storing its byte-code internally. I invested a lot into BitCode (you’ll notice my name is on the linked document), including writing a standalone encoder and decoder (230 lines of Lua and 856 lines of C, respectively). But this was before I worked at Google or knew about Protocol Buffers. Protocol Buffers are much easier to use because they have a formal schema (the .proto file) that can generate nice APIs and help you out with backward compatibility. Without a format schema, BitCode makes you resort to things like an ad hoc text file that describes the schema. This approach was showing its limits.
  2. parse tree format: I always knew I wanted Gazelle to be capable of generating parse trees in some kind of standard format. Protocol Buffers end up being a match made in heaven, since they are isomorphic to parse trees in a very deep way. Indeed, the ast system for the Elkhound Parser is very much like Protocol Buffers in that you define your parse tree format and it generates classes for representing your AST.

  Since Gazelle is gated on upb, the question then is: when will upb release? Why hasn’t it released already?

  A few months ago I was working on upb for 100% of my time at work. I had banked 20% time for a while, and I was also a bit burned out on my 80% project, so my manager very graciously gave me the liberty to work on upb for all of my working hours.

  During that time upb made progress in several areas. It got some better benchmarks and tests, and I fleshed out the upb compiler so that it wasn’t dependent on the official Protocol Buffers compiler for bootstrapping. Maybe most importantly, I worked a lot on the in-memory message format to figure out how to make it work well with dynamic languages.

  My goal during that time was to write a Python extension that a few initial internal-to-Google customers could use. The value proposition is that it would be API-compatible with what they were already using, but many times faster. I wrote said extension, which was incomplete (supported decoding only, not encoding), but looked complete enough to use for this case.

  By this time I was approaching the amount of time I could reasonably ask from my manager at work, so I had to tie up the loose ends and get it into my initial customer’s hands. I put all the pieces together and tried it out, but then ran into a problem; I hadn’t realized that this initial customer was using an old deprecated feature of Protocol Buffers called MessageSet. There was no way I could support MessageSet without significant changes. I was defeated for the moment. I had to take a break for a few months and re-devote my time to my 80% project.

  I mention this all just to illustrate that I do have actual customers that I am targeting, and I have had aggressive pushes to deliver something to those customers, but unfortunately my work wasn’t complete enough for them yet.

  This brings us up to now. In the last week or two, I have made several strides, including executing on part of a design that will get me MessageSet support. I have also developed an interface for a “pick parser”, which lets you pull only a small subset of fields out of a protobuf. This will be a big win for use cases that only need a few fields from a very large proto, and I have a customer internal-to-Google who is very interested in this interface.

  Meanwhile I’m very interested in trying to get the upb Python extension into AppEngine, because I think it could be a huge win there since users aren’t allowed to load custom Python extensions. This means that currently, people trying to use protocol buffers on AppEngine are limited to pure-Python extensions that are much slower than a C extension can be. But to get into AppEngine I will need to get a security audit, which is part of the reason I am leaning towards C++ at this point. I think C++ will make the code shorter and less gnarly (fewer casts), which should lead to easier verifiability. I converted one header file so far, and it got 38% smaller and much easier to read.

  I hesitate to make schedule estimates, but my main purpose is to impress on my possibly-impatient audience that:

  • I do have motivation to release.
  • I do have initial customers and initial use cases.
  • I am making progress.
  • I am currently focused on delivering (1) a pick parser, (2) a Python extension, (3) an easily-auditable code-base.
  • I look forward to being able to announce my first release!

  Yours,
  Josh

• 

  Porting upb to C++?

  Posted: November 28th, 2009, 1:53pm MST by Josh

  I am on the verge of trying something I never thought I’d do. I’m considering porting upb to C++.

  My reasons aren’t ideological, they are highly practical. Basically I am realizing that while object-oriented C is OK for a while, it’s very weak at inheritance. Inheritance in C involves a lot of casting, duplicated code and/or macros, and careful discipline. The main problems with this are:

  • the code gets longer and less readable
  • the code involves more possibly-unsafe operations like casts

  Both of these problems make the code ultimately more difficult to audit for security. And getting upb audited for security is something I plan to do very soon.

  I am coming to believe that porting to C++ would make upb smaller (in lines of code) and easier for verify for security. However, there are a few major disadvantages that are giving me pause:

  • there are still some contexts in which C++ is a no-go, like the Linux kernel, embedded systems that only have a C compiler (but no C++), or projects that want to stay C-only. Doing this port would make upb unsuitable for these contexts.
  • projects that are currently C-only would need to create C++ source files to call upb APIs, and will have to link in the C++ runtime
  • (possible) C++ could result in a larger binary.

  When I look at the downsides though, they don’t seem to pertain to my initial goals of making upb useful for Python, Lua, Ruby, etc. extensions, and for use inside Google. Being useful for really restricted embedded systems is a far-off use case. So it’s sounding like porting to C++ is the right thing to do.

  I hope it significantly reduces the line count, as I expect it will. That will make me feel better about giving up the minimalism of C. I will definitely be compiling with -fno-exceptions -fno-rtti -fvisibility-inlines-hidden on gcc. I also won’t be using any of the C++ standard library (not even <string>).

Josh

• 

  habes @ 2009-11-03T00:01:00

  Posted: November 3rd, 2009, 1:41am MST by Josh

  I'm sending a care package to a friend who is going through a crappy crappy time. Any ideas for cool/cute/weird/day-brightening things to put in there? I have my own ideas of course, but wanted to tap into the vast array for anything particularly creative...
• 

  habes @ 2009-08-23T11:51:00

  Posted: August 23rd, 2009, 1:35pm MDT by Josh

  Conservatives complain that the left "blames America first." I'm sure there are some on the left who are guilty of going too far in that direction, like saying that 9/11 is all our fault. But I just don't think these conservatives realize how damaging it can be to go too far in the other direction.
  
  I was surprised when I came across Glenn Beck's website The 9/12 Project -- I could agree with almost all of the project's principles. The only one I straight up couldn't agree with was "I believe in God and He is the Center of my Life" (why do conservatives insist on tangling government with religion?). The one that made me a little queasy is "America Is Good."
  
  To say "America Is Good," full stop, makes me queasy, not because I think America is bad or because I feel the need to "blame America first," but because it is a blank check. It is unqualified. Regardless of what we actually do our country is good, according to this attitude.
  
  To me that attitude leads straight to this quote from the elder George H. W. Bush:
  

  I will never apologize for the United States — I don't care what the facts are... I'm not an apologize-for-America kind of guy.

  
  "I don't care what the facts are," and in this case the facts were that a U.S. warship had just shot down a civilian Iranian airliner (Iran Air Flight 655) that was operating according to its scheduled flight plan. It was transmitting a "friend-or-foe" beacon indicating that it was a civilian aircraft. The U.S. ship launched the missiles from within Iranian territorial waters.
  
  If Iran had shot down a U.S. commercial airliner, we would have been very angry. And in fact, we were very angry when the Soviets shot down Korean Air 007 five years earlier, even though that aircraft had ventured into Soviet airspace due to a navigational error. Ronald Reagan said at the time:
  

  I'm coming before you tonight about the Korean airline massacre, the attack by the Soviet Union against 269 innocent men, women, and children aboard an unarmed Korean passenger plane. This crime against humanity must never be forgotten, here or throughout the world.
  
  [...]
  
  This was the Soviet Union against the world and the moral precepts which guide human relations among people everywhere. It was an act of barbarism, born of a society which wantonly disregards individual rights and the value of human life and seeks constantly to expand and dominate other nations. --Address to the Nation on the Soviet Attack on a Korean Civilian Airliner.

  
  
  If shooting down a civilian airliner is so bad (which it is), why do we refuse to apologize for it when we do it? Why does any American excuse the position "I will never apologize for the United States — I don't care what the facts are"?

2 Star

• 

  Wanted: a portable mutex and atomic refcount

  Posted: August 14th, 2009, 8:12pm MDT by Josh

  upb needs to have some lightweight thread-aware behavior. I’m leaving most synchronization up to users (individual messages will not be thread-safe), but there are a few central structures I need to make thread-safe and reference-counted.

  I need only the tiniest bit of functionality:

  • a portable mutex.
  • a portable atomic_t that lets me atomic_inc() and atomic_dec().

  We’re talking “lives in one single header” small. The mutex would just be wrappers around existing mutex implementations (pthreads, windows, etc), and since those routines typically take care of any memory barriers you need to safely read/mutate the shared state, I wouldn’t have to worry about that.

  The atomic type would have to be hand-coded and architecture-specific, since most threading libraries don’t provide one. The reason for providing this would be reference-counting. If you are reference-counting an immutable structure, then you don’t need to worry about memory barriers to ensure the consistency of that structure; if you’re reference-counting a mutable structure, then you’ll need to protect the mutable state with mutexes and acquire the mutex before freeing anything.

  The library (er, header file) should also support compiling everything to nothing if NO_THREAD_SAFETY is defined as a preprocessor symbol.

  Yes, that all sounds good. Tiny yet functional. I’ll be writing this very soon unless something exactly like what I’ve described happens to already exist.

Josh

• 

  habes @ 2009-08-10T22:56:00

  Posted: August 11th, 2009, 12:02am MDT by Josh

  ingdirect.com: "We gave our site a minor facelift. So if you notice anything different after you sign in, don't freak out. You're in the right place."
  
  youtube.com: "We are currently performing site maintenance. Be cool - we'll be back 100% in a bit."
  
  Did my bank seriously just tell me not to freak out? When did this happen? When did websites become my homeboyz?

2 Star

• 

  Wanted: a mailing list reader website

  Posted: August 10th, 2009, 11:33pm MDT by Josh

  There is tons of interesting discussion that happens on technical mailing lists. Mailing lists are the best snapshot of the state of a software project; they capture what current users are trying to do, where they’re succeeding, where they’re running into trouble, and what the current plans are for making things better.

  Unfortunately, there is still no good way (AFICS) to lurk on high-volume mailing lists. Your current options are:

  • Subscribe your personal email address to the mailing list. Pros: threads well, tracks “read” status well, easy to reply. Cons: too much overhead to subscribe to a new list (subscribe, confirm, set up mail filter), mail builds up as unread if you don’t read it for a while. Overwhelming for high volume lists. Not convenient when your level of interest in a list varies.
  • Read on gmane.org. Pros: threads somewhat well (new messages on old threads get lost, because the whole thread is sorted based on when its first message arrived), tracks your “read” status (but not across browsers or computers), easy to track a single list and only read what interests you. Cons: not easy to track multiple lists. There’s no top-level “what’s new on lists I care about” view. Not easy to reply (the built in editor makes you wrap lines yourself).
  • RSS feed from gmane.org. Pros: easy to track multiple lists, old mail doesn’t build up if I don’t read it for a while, lets me read mailing list posts alongside my other feeds. Cons: RSS is a terrible match for mailing lists. It doesn’t understand threads at all. No easy way to reply. Also, the gmane RSS feeds link you to the blog interface, which is equally terrible at threading.
  • The Lurker email archiver. I’ve been a fan of this project for a while. Pros: GREAT interface (check out this demo site), top-level page that summarizes threads and their activity, thread view that shows you replies according to both time and threading. Cons: you have to run it yourself (it’s a project, not a service), doesn’t remember what you’ve read, and no easy way to reply.

  What I would love is a website that would let me easily lurk on mailing lists. I’d love an interface like Lurker, but that I log into so that it knows what I’ve read. I’d want a top-level view that shows popular threads across ALL mailing lists I’m lurking on, not just one mailing list at a time. And I’d want the ability to easily reply to mailing list threads.

  If anyone knows a better way to get what I want, please let me know!

• 

  Giving up on AT&T style assembler syntax

  Posted: July 31st, 2009, 5:07pm MDT by Josh

  Until recently I had been pretty agnostic about Intel vs. AT&T style assembler syntax. I always noticed that people who had a strong opinion almost always preferred Intel-style, but I didn’t care too much one way or the other.

  gcc was my first real compiler, and this was back before binutils supported Intel syntax like they do now. So I read Brennan’s Guide to Inline Assembly (which I still reference frequently), and didn’t worry too much about it.

  One thing that always bugged me a little bit was how the instruction names weren’t exactly the same. AT&T made you put these suffixes on your instructions, so mov would become movl. The main problem with this is Googleability.

  But today what was previously an annoyance reached the level of being a serious problem. I was looking at an instruction listing and saw the instruction movslq. First I Googled for movsl (presuming that the “q” was a “quadword” suffix), but that yielded nothing. Then I tried Googling for movslq in its entirety, still nothing that seemed to define the instruction.

  When I did follow the link, what I discovered is that movslq in AT&T syntax corresponds to movsxd in Intel syntax. The moment I discovered this, it became quite clear to me that AT&T syntax was a dead end. “-M intel” will be my default parameter to objdump from now on.

Comments for Josh the Outspoken

• 

  Comment on Git needs a new interface by Josh

  Posted: July 31st, 2009, 10:55am MDT by Josh

  @Luca: If it was called “revert”, I wouldn’t mind having it throw away my local modifications. In fact I’d expect it! But the name is important — “checkout” just doesn’t sound like a destructive command. “checkout” is not destructive in cvs or svn. And it also has a lot of non-destructive uses, like switching branches. It’s just a UI minefield to have this one particular mode of the “checkout” command act like “revert”.

  I’m not too inspired to report this stuff to the Git developers, because my biggest gripes would require major changes to address (like renaming core commands). There’s no way they’d be receptive to that. Like I said, what I think Git’s UI needs is a revolutionary, not an evolutionary change.

  @Dave: Your point is taken about being confident about the merge. But I like the Perforce model here (can’t remember if CVS and SVN do this too), where it prompts you for each file that has conflicting changes, and asks if you want to merge right now or not. If you get cold feed about it, you can always decline to do the merge, then do the stash+apply thing manually. But going ahead with the merge (especially if the changes don’t have conflicts) is nearly always what I want.

  Good suggestion about git-mergetool — I should use that instead.

2 Star

• 

  Git needs a new interface

  Posted: July 30th, 2009, 2:38pm MDT by Josh

  I’ve been a git advocate for a while, and I use git in two different projects. I think git is an impressive technical accomplishment, but I think its interface (”porcelain”) is not ready for prime-time. I really hope some UI-focused person will design a “v2″ for the git interface so that someday git can be the obvious choice for version control for any project.

  Specific problems:

  “checkout” is a destructive command

  I seriously have no idea what Linus was thinking. It is insanity that:

  $ git checkout foo.c

  …will overwrite any local modifications you may have to foo.c without asking.

  You can’t merge upstream changes into your local, uncommitted modifications

  Suppose I cloned some repository and I started hacking it up. My changes are still hacky and not ready to be committed. Say a few days later I want to pull upstream changes, but without committing my hacky changes to my local repository:

  $ git pull
  remote: Counting objects: 5, done.
  remote: Compressing objects: 100% (2/2), done.
  remote: Total 3 (delta 0), reused 0 (delta 0)
  Unpacking objects: 100% (3/3), done.
  From /tmp/foo
     e726259..e20c51a  master     -> origin/master
  Updating e726259..e20c51a
  error: Entry 'foo.c' not uptodate. Cannot merge.

  Git is refusing to perform a merge of my local modifications with the upstream changes. It wants me to commit my local changes first. This is annoying. Every version control system I have ever used supports this, except Git. Asking me to commit my hacky changes is unreasonable; they’re hacky and unfinished. They might not even compile!

  Yes, I could do:

  $ git stash
  $ git pull
  $ git stash apply

  But why should I have to do this? CVS, SVN, and P4 don’t make me.

  Git’s merge conflict resolution workflow is unintuitive

  Continuing with the above example, now suppose I committed my local changes and then did a pull, but the changes were conflicting:

  $ git pull
  Auto-merged foo.c
  CONFLICT (content): Merge conflict in foo.c
  Automatic merge failed; fix conflicts and then commit the result.

  Ok, git is somewhat helpful here, I’ll fix the conflicts in foo.c and commit the result:

  $ vim foo.c
  $ git commit
  foo.c: needs merge
  foo.c: unmerged (f388ef85dd65c39e4c76f5e597d3b67f7d1a0726)
  foo.c: unmerged (6f4bf54585ae256236c0d6cfa9f114affb94313f)
  foo.c: unmerged (06c974ebbfc04394f4fad8a6dcb31e64866fa1bf)
  error: Error building trees

  Ok, maybe it’s obvious to experienced git users what my error is here, but git’s error message here is worse than unhelpful — it’s downright confusing. I think I’ve resolved the conflict, but all git can think to do is tell me is that “foo.c needs merge” and spit some SHA1’s at me. It gives me absolutely no help about what I need to do to fix the problem.

  Suppose that I want to resolve the merge by using either my version or their version verbatim (”accept mine”/”accept theirs”):

  $ git checkout foo.c
  error: path 'foo.c' is unmerged

  Again, unhelpful (and in this case, what I’m trying to say actually makes sense, git just won’t let me do it).

  Interface for working with the index almost universally confusing

  I understand the difference between the working directory, the index, and the committed tree pretty well. But I cannot for the life of me remember the difference between:

  $ git reset --soft
  $ git reset --hard
  $ git reset --mixed

  I can barely keep them straight while I’m reading the manpage. “Soft” resets HEAD but not the working directory or index. “Mixed” resets HEAD and the index, but not the working directory. “Hard” reset HEAD, the index, and the working directory.

  In conclusion, this isn’t meant to be an exhaustive list of problems with git’s interface, it’s more meant to be a microcosm. Git’s interface is not intuitive or easy to learn, and its error messages are not helpful. Which is too bad, because as I said I think Git is solid technology. I just hope someone writes a better porcelain for it. I’m not talking about evolutionary changes, I think the suite of top-level commands (checkout, branch, merge, pull, reset, commit, etc) needs to be redesigned from scratch.

• 

  The Perils of Writing Good Documentation

  Posted: July 30th, 2009, 1:41pm MDT by Josh

  I’ve been thinking about documentation lately, and I feel unsatisfied with the options I currently have available to me for writing and publishing documents. This dissatisfaction is not too well defined; I can’t put my finger on exactly what I want, but when I look at my options I’m not too excited about any of them.

  When I say “documentation,” I am talking about several slightly different things:

  • Project Homepage for projects like upb and Gazelle. The goal of a project homepage is to answer the question “what is this project and why should I use it?” It should also be attractive enough for a person to feel like this project is high-quality stuff. And of course it should point them to the relevant resources (downloads, source tree, bug tracker, etc). Good examples: [git-scm.com], [www.ruby-lang.org], [www.gazelle-parser.org].
  • Manuals for projects like upb and Gazelle. The goal of the manual is to provide both tutorial-like and reference-like information about how to use the software. Manuals have a lot of structure and are a bit more formal, since they are intended to precisely explain how the software should be used. They tend to track the software itself more closely than the other types of documentation, and are often even checked into the source tree. For example, Gazelle’s Manual.
  • Design discussions/rationale. This isn’t quite like a manual because instead of describing how the software works, they describe why the software is the way it is. What are the alternatives to your approach and why did you pick the one you did? What are the trade-offs? I don’t think we see as much of this documentation as we should in the open-source world, but one good example is the Python PEP process.
  • General articles about a particular subject. I mean to write some documents that explain the basic ideas of parsing in a more approachable way than most parsing literature. The literature can be a bit oblique, and I think I could do a good job of explaining it in a way that anyone can understand.

  The main options that I see available to me are:

  • Plain HTML. Even I have come to the conclusion that this isn’t a good choice any more. Too much work to write, too little flexibility, not enough bang for the buck. Of the four documentation kinds above, the only one it remotely makes sense for is the “Project Homepage” case, but even that is too much work for me. Creating the Gazelle homepage took too much work, and it’s not even that awesome.
  • Personal Wiki / MarkDown. By “Personal Wiki” I mean a wiki that you run yourself. I put this in the same category as MarkDown because the two tend to have the same advantages/disadvantages. The advantages are that you can get a reasonably attractive product with minimal effort, and they are fairly customizable. The big disadvantage is that no two markdown languages are compatible, and there are so many to choose from (seriously: MarkDown, ReStructured Text, Textile, AsciiDoc, and those are just the ones I know off the top of my head). It’s slightly scary to invest a lot into a format that is one of many possible contenders.
  • Hosted Wiki, like the Google Code wiki or the GitHub wiki. In this case hosting is taken care of, but you have less control over the look and more stuff cluttering your page. Also, I can’t figure out why, but something about the design of Google Code makes me totally uninspired to write any documents in its wiki. Another thing to note is that if a hosted wiki disappears (GitHub is only a startup, it could totally go under), it’s not clear what happens to your documents!
  • DocBook, which is a little better than a MarkDown scheme because DocBook seems to have gained some critical mass. Still, the DocBook people seem to have a mild-to-moderate case of XML-itis, and the DocBook homepage seems more concerned with spitting acronyms at you than telling you if DocBook is capable of something basic like theming your document in different ways.

  So as you can see, I’m not super satisified with any of my options. The Gazelle Manual uses AsciiDoc, which seems to work ok, and I would probably choose it again. I guess I’d be most inclined to choose either AsciiDoc or DocBook for writing general articles (I like this article about Python types and objects which was made using DocBook and is attractive).

  I can’t decide what to do for the Project Homepage or the Design Discussions case. I really want to have attractive Project Homepages, but I don’t have too much web design talent and HTML is too much work for me. For Design Discussions I guess I’m leaning towards the GitHub wiki just because it pairs with the project hosting nicely, though I am somewhat uncomfortable with the idea that GitHub could disappear one day, and that moving my documents from the GitHub wiki somewhere else sounds like a headache.

Comments for Josh the Outspoken

• 

  Comment on Gazelle is going to love SSE 4.2 by Josh

  Posted: July 20th, 2009, 11:59am MDT by Josh

  @Jeremy: right you are, thanks! Fixed.

2 Star

• 

  Don’t forget -march!

  Posted: July 20th, 2009, 1:46am MDT by Josh

  The -march flag itself is GCC-specific, but the general advice is universal: don’t forget to tell your compiler that it can take full advantage of your spiffy new CPU! I should know better but I’ve been forgetting to specify -march when compiling upb.

  Here’s an extreme example of why. Take an innocent-looking function like:

  int float_to_int(float f) {
    return (int)f;
  }

  Looks simple enough, right? Unfortunately, float -> int casts are stupidly expensive on x86. Without any -m flags, gcc compiles this to:

  sub      $0x8, %esp       ; allocate stack space
  fnstcw   0x6(%esp)        ; save floating-point control word
  flds     $0xc(%esp)       ; push floating-point param onto fp stack
  movzwl   0x6(%esp), %eax  ; move prev fp control word into %eax
  mov      $0xc, %ah        ; set rounding mode of control word to "truncate"
  mov      %ax, 0x4(%esp)   ; save it *back* to the stack
  fldcw    0x4(%esp)        ; set the floating-point control word to truncate
  fistp    0x2(%esp)        ; store integer from the fp stack to the stack
  fldcw    0x6(%esp)        ; set the fp control word back to what it was
  movzwl   0x2(%esp), %eax  ; read the value into eax (the return value)
  add      $0x8, %esp       ; give the stack space back
  ret

  This would be funny if it weren’t so sad. All these gymnastics are required because the cast is required to round down (according to the C standard), but that requires the x86’s floating point unit to be in a different mode than for most operations.

  Compiling exactly the same code with -msse2 allows the compiler to take advantage of an SSE-only instruction, and the above is replaced with:

  cvttss2si  0x4(%esp), %eax     ; convert value to integer with truncation
  ret

  The difference in this case is astounding. Hopefully this will motivate you never to forget the -march flag!

  The right thing to do in my case is compile with -march=core2. When I compile with -march=core2 or -msse3, the compiler to emits the not-quite-as-terse:

  sub     $0x4,%esp
  flds    0x8(%esp)
  fisttpl (%esp)
  mov     (%esp),%eax
  add     $0x4,%esp
  ret

  I’m really not sure why gcc prefers this version when sse3 is available. It seems to be more work than the sse2 version. I tend to believe gcc know what it’s doing here, but I’d love to learn why.

Comments for Josh the Outspoken

• 

  Comment on Amazing Tools: Massif, a heap profiler by Josh

  Posted: July 18th, 2009, 3:12pm MDT by Josh

  @bushman: I can’t remember exactly how I got the answer I wanted out of WireShark, it was a few weeks ago and I’ve lost the details already. I seem to remember there being a way to filter the list of captured packets by protocol type, which gave me exactly what I was looking for.

  I wish I had some secret answer to how I manage my time. The answer is very simply that I spend way, way too much of my nights and weekends (and even vacations, which is where I am right now) doing this stuff!

2 Star

• 

  Gazelle is going to love SSE 4.2

  Posted: July 18th, 2009, 3:09pm MDT by Josh

  SSE 4.2 includes text processing instructions. In the words of Ars Technica:

  Intel has added a number of new instructions to Nehalem and it has sped up others. The 4.2 version of Intel’s SSE vector extensions takes the x86 ISA back to the future just a bit by adding new string manipulation instructions. I say “back to the future” because ISA-level support for string processing is a hallmark of CISC architectures that was actively deprecated in the post-RISC years; typically, when a writer wants to give an example of crufty old corners of the x86 ISA that have caused pain for chip architects, string manipulation instructions are what he or she reaches for. But the new SSE 4.2 string instructions are aimed at accelerating XML processing, which makes them Web-friendly and therefore modern (i.e., not crufty).

  I chuckled a bit when I read this. I’m not very purist when it comes to hardware. If these instructions will make my parsers faster, then they sound great to me!

  The four new instructions are:

  • pcmpestri: packed compare of explicit length strings, returning index
  • pcmpestrm: packed compare of explicit length strings, returning mask
  • pcmpistri: packed compare of implicit length strings, returning index
  • pcmpistrm: packed compare of implicit length strings, returning mask

  The variants are as follows:

  • implicit length strings are NULL-terminated, explicit strings have an explicit length (ie. the whole input register).
  • they can return an index into the source string (if you were searching for something) or a mask (if you wanted to test each character of the input

  Both let you scan a 128-bit SSE register (treating it as either 16 8-bit characters or 8 16-bit characters) and perform all kinds of searches/comparisons. The instructions are configurable; you supply a control word that specifies all of the different variations of the instructions. For example, are the input values signed or unsigned, are we comparing against ranges or specific values, etc.

  The reciprocal throughput of these instructions is high (2 cycles) but the latency is annoyingly slow (9 cycles). This means that you have to wait nine cycles after issuing the instruction before you can use the result. It’s hard to think of too many useful things you can execute in parallel while you’re waiting for that answer. As a side note, these figures come from Intel’s Intel® 64 and IA-32 Architectures Optimization Reference Manual, which says that the latency number is a worst case estimate:

  Actual performance of these instructions by the out-of-order core execution unit can range from somewhat faster to significantly faster than the latency data shown in these tables.

  I’m not enough of a hardware geek to know what to actually expect.

  Still, that’s nine cycles to wait before getting a lot of really useful information. In addition to returning the index or mask, the instructions set several of the flags in useful ways.

  So what processors have SSE 4.2? Or in other words, how long will my impatient self have to wait to try them out? Apparently SSE 4.2 is available on Penryn, which is the second-gen Core 2, which debuted in 2007/2008. It uses a “45 nm process”, which I’m sure means something to hardware geeks but not to me. All I know is that it’s not the Core 2 that’s inside the MacBook Pro sitting on my lap. And of course SSE 4.2 is in the new Nehalem.

• 

  Site Overhaul / upb status

  Posted: July 7th, 2009, 12:11am MDT by Josh

  You’ll notice that the site has a new theme, a new title, maybe a little bit of a new attitude (being “josh the outspoken” isn’t all it’s cracked up to be). All this is in anticipation of upb’s release, and of a lot of follow-up work that I couldn’t be more excited about.

  A lot of people mentioned that my last theme didn’t handle preview correctly, which I agree was quite annoying — sorry about that! Unfortunately my new theme doesn’t have preview at all. Finding the perfect WordPress theme is harder than it seems.

  So as I mentioned I expect the first release of upb to come within the next week or two. It will only have parsing (not serializing), but most of the core functionality besides that is done. I expect that the core will stay relatively static, and all the enhancements/innovations will come from modules that are layered on top of that. For example, some of the things I have in mind are:

  • Extensions for every language known to man. The first ones will be Python, Lua, and Ruby (in that order). These will take some thought to get just right, because I want the memory management to be tightly integrated. In particular, I want protobuf objects in these languages to be able to reference string data from the original protobufs, but all be memory-managed appropriately.
  • Support for the Protocol Buffer text format.
  • An easy way to parse only selected fields. For example, I want to be able to say (in Python):

    time, url = logrecord.parse_fields(proto_data, "time", "url")

    This can be optimized out the wazoo, because you can skip all fields and submessages that you don’t care about, and you can stop parsing once you have the data you need.

  And of course, performance, performance, performance. I can’t wait to get my hands on some real profiles and see what my next optimization target will be.

• 

  Amazing Tools: Massif, a heap profiler

  Posted: July 6th, 2009, 11:54pm MDT by Josh

  I love the feeling of discovering an amazing new tool. It’s a pleasant surprise to have some task you want to achieve — one that you could do manually, given enough time — and find that some tool you didn’t even know existed will make the solution easy.

  Tonight I was working on the upb compiler (and upb’s first release is impending, by the way), and ran it under Valgrind as I frequently do to catch memory leaks. There weren’t any leaks, but I did notice that the program had allocated 80kb of memory over the course of its run.

  People who are less OCD than I would probably shrug off 80kb of memory. But intuitively 80kb sounded high to me given how much data this program was dealing with, and I wanted to know where all those allocations were coming from.

  I didn’t know off the top of my head how I might profile where my memory allocations were happening, but I had a hunch that Valgrind would be there for me. And sure enough, one of the tools included in Valgrind is Massif: a heap profiler.

  A few short shell commands later:

  $ valgrind --tool=massif ./upbc
  $ ms_print massif.out.17604 | less

  …and I had this call graph sitting in front of me:

  93.72% (74,243B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
  ->58.49% (46,336B) 0x40194E: upb_table_init (upb_table.c:34)
  | ->38.13% (30,208B) 0x4019E9: upb_strtable_init (upb_table.c:45)
  | | ->29.09% (23,040B) 0x40343A: upb_msg_init (upb_msg.c:44)
  | | | ->29.09% (23,040B) 0x402CEE: insert_message (upb_context.c:193)
  | | |   ->25.85% (20,480B) 0x402E80: addfd (upb_context.c:223)
  | | |   | ->12.93% (10,240B) 0x40263F: upb_context_init (upb_context.c:30)
  | | |   | | ->12.93% (10,240B) 0x40167C: main (upbc.c:195)
  | | |   | |
  | | |   | ->12.93% (10,240B) 0x403135: upb_context_parsefds (upb_context.c:283)
  | | |   |   ->12.93% (10,240B) 0x4016BA: main (upbc.c:198)
  | | |   |
  | | |   ->03.23% (2,560B) 0x402D56: insert_message (upb_context.c:203)
  | | |     ->03.23% (2,560B) 0x402E80: addfd (upb_context.c:223)
  | | |       ->01.62% (1,280B) 0x40263F: upb_context_init (upb_context.c:30)
  | | |       | ->01.62% (1,280B) 0x40167C: main (upbc.c:195)
  | | |       |
  | | |       ->01.62% (1,280B) 0x403135: upb_context_parsefds (upb_context.c:283)
  | | |         ->01.62% (1,280B) 0x4016BA: main (upbc.c:198)
  | | |
  | | ->05.82% (4,608B) 0x4046E0: upb_enum_init (upb_enum.c:14)
  | | | ->05.82% (4,608B) 0x402C35: insert_enum (upb_context.c:167)
  | | |   ->05.82% (4,608B) 0x402DBC: insert_message (upb_context.c:209)
  | | |     ->05.82% (4,608B) 0x402E80: addfd (upb_context.c:223)
  | | |       ->03.23% (2,560B) 0x403135: upb_context_parsefds (upb_context.c:283)
  | | |       | ->03.23% (2,560B) 0x4016BA: main (upbc.c:198)
  | | |       |
  | | |       ->02.59% (2,048B) 0x40263F: upb_context_init (upb_context.c:30)
  | | |         ->02.59% (2,048B) 0x40167C: main (upbc.c:195)
  | | |
  | | ->01.62% (1,280B) 0x402612: upb_context_init (upb_context.c:27)
  | | | ->01.62% (1,280B) 0x40167C: main (upbc.c:195)
  | | |
  | | ->01.62% (1,280B) 0x402629: upb_context_init (upb_context.c:28)
  | | | ->01.62% (1,280B) 0x40167C: main (upbc.c:195)
  | | |
  | | ->00.00% (0B) in 1+ places, all below ms_print's threshold (01.00%)
  | |
  | ->20.36% (16,128B) 0x4019C4: upb_inttable_init (upb_table.c:40)
  |   ->17.45% (13,824B) 0x403417: upb_msg_init (upb_msg.c:42)
  |   | ->17.45% (13,824B) 0x402CEE: insert_message (upb_context.c:193)
  |   |   ->15.51% (12,288B) 0x402E80: addfd (upb_context.c:223)
  |   |   | ->07.76% (6,144B) 0x40263F: upb_context_init (upb_context.c:30)
  |   |   | | ->07.76% (6,144B) 0x40167C: main (upbc.c:195)
  |   |   | |
  |   |   | ->07.76% (6,144B) 0x403135: upb_context_parsefds (upb_context.c:283)
  |   |   |   ->07.76% (6,144B) 0x4016BA: main (upbc.c:198)
  |   |   |
  |   |   ->01.94% (1,536B) 0x402D56: insert_message (upb_context.c:203)
  |   |     ->01.94% (1,536B) 0x402E80: addfd (upb_context.c:223)
  |   |       ->01.94% (1,536B) in 2 places, all below massif's threshold (01.00%)
  |   |
  |   ->02.91% (2,304B) 0x4046F5: upb_enum_init (upb_enum.c:15)
  |     ->02.91% (2,304B) 0x402C35: insert_enum (upb_context.c:167)
  |       ->02.91% (2,304B) 0x402DBC: insert_message (upb_context.c:209)
  |         ->02.91% (2,304B) 0x402E80: addfd (upb_context.c:223)
  |           ->01.62% (1,280B) 0x403135: upb_context_parsefds (upb_context.c:283)
  |           | ->01.62% (1,280B) 0x4016BA: main (upbc.c:198)
  |           |
  |           ->01.29% (1,024B) 0x40263F: upb_context_init (upb_context.c:30)
  |             ->01.29% (1,024B) 0x40167C: main (upbc.c:195)
  |
  ->07.98% (6,324B) 0x403AF1: upb_msgdata_new (upb_msg.c:158)
  | ->07.96% (6,308B) 0x403F05: upb_msg_reuse_submsg (upb_msg.c:241)
  | | ->07.96% (6,308B) 0x404497: submsg_start_cb (upb_msg.c:325)
  | |   ->07.96% (6,308B) 0x4056E8: push_stack_frame (upb_parse.c:288)
  | |     ->07.96% (6,308B) 0x4057ED: parse_delimited (upb_parse.c:316)
  | |       ->07.96% (6,308B) 0x405A91: upb_parse (upb_parse.c:369)
  | |         ->07.96% (6,308B) 0x4045BA: upb_msg_parse (upb_msg.c:352)
  | |           ->07.96% (6,308B) 0x404631: upb_alloc_and_parse (upb_msg.c:361)
  | |             ->07.96% (6,308B) 0x4030CA: upb_context_parsefds (upb_context.c:274)
  | |               ->07.96% (6,308B) 0x4016BA: main (upbc.c:198)

  This might look somewhat daunting if you’re not as deeply familiar with upb as I am. But it immediately told me what I wanted to know: almost 60% of the memory is being used by upb’s int->record and string->record hash tables. That seems a little bit high. And it’s being allocated right when the tables are constructed (upb_table_init), not as a result of a resize.

  Breaking open the code, I found a table minimum size that I had imposed as an attempt to limit the number of resizes. Resizes have a high overhead — in my hash table implementation, they result in everything being re-hashed and all the memory being re-allocated, so I had imposed a minimum size of 16 in my constructor:

  void upb_table_init(struct upb_table *t, uint32_t size, uint16_t entry_size)
  {
    t->count = 0;
    t->entry_size = entry_size;
    t->size_lg2 = 1;
    while(size >>= 1) t->size_lg2++;
    t->size_lg2 = max(t->size_lg2, 4);  /* Min size of 16. */

  When I inserted some print statements to compare how often this minimum was taking effect, I saw that there were tons of tables that were trying to allocate just a few (0-10) entries. With my minimum, they were always being allocated at least 16. And what’s more, in all these cases I knew up front how many entries I planned to insert! So there was no danger of a resize anyway.

  I removed this minimum size and the memory usage of my program dipped to about 55kb (from 80kb — a ~30% reduction!) That seems a bit more reasonable, though I’m sure it’s not the last of my efforts to make sure upb’s memory footprint stays small.

  Anyway, the point of this entry is that now I know about a new tool (Massif) that is at my disposal whenever I need it. It’s easy to use and requires almost no set-up. I can run it on a whim whenever I want to collect memory usage data. I have just become a little bit more resourceful.

  Valgrind has tons of spiffy tools of this sort that ship with it. I wonder how many people know about them.

  Another tool I had a similar reaction to was WireShark. I was experiencing a redirect loop bug in my browser and wanted to submit a useful report to the developers. The useful information here is the contents of all the HTTP traffic that was occurring during the loop. I fired up WireShark (as a first-time user) and found out relatively quickly how to sniff the network interface, capture my HTTP session, dump it at the HTTP layer (as opposed to the TCP layer or something else), and dumped it to a text file. Massively spiffy.

  Learn an amazing new tool today! And then tell me about it!

• 

  Books About Parsing

  Posted: June 26th, 2009, 9:52pm MDT by josh

  I’m in Portland this weekend and picked up a few more parsing-related books. I wanted to list them here, since I wasn’t previously aware they existed despite my intense interest in this field.

  

  The first is Selected Papers on Computer Languages, by Donald Knuth. I’m embarrassed to say that I wasn’t previously aware how much of the early theories and models about parsing come from Knuth. This book contains several of the original papers about the theories of LL(k), LR(k), etc:

  
  

  

  The second is The Theory of Parsing, Translation, and Compiling. Volume I: Parsing, by Alfred Aho and Jeffrey Ullman. If those names sound familiar, it’s because they’re the guys who wrote the Dragon Book.

  
  

  

  The last is Beautiful Code: Leading Programmers Explain How They Think. I had seen this book at various bookstores before but never felt compelled to look at it. But today I flipped through it and realized that many of the essays are about parsing:

  • A Regular Expression Matcher, by Brian Kernighan. “I suggested to Rob [Pike] that we find the smallest regular expression package that would illustrate the basic ideas while still recognizing a useful and nontrivial class of patterns. Ideally the code would fit on a single page. Rob disappeared into his office. As I remember it now, he emerged in no more than an hour or two with [these] 30 lines of C code.
  • Finding Things, by Tim Bray. Deals with searching logfiles with regular expressions.
  • Correct, Beautiful, Fast (in That Order): Lessons from Designing XML Verifiers, by Elliotte Rusty Harold. Deals with parsing/verifying XML, what more needs to be said?
  • Python’s Dictionary Implementation: Being All Things to All People, by Andrew Kuchling. Not about parsing, but about hashing, which I have quite recently been very interested in.

  
  

  

  And though I mentioned it once before, I just want to reiterate how awesome Parsing Techniques: A Practical Guide is. Your guidebook to the entire field of parsing.

• 

  μpb Status Update

  Posted: June 26th, 2009, 9:01pm MDT by josh

  I haven’t posted many status updates for upb lately. Sometimes that means I’m busy with other things, but right now it means I am working on it feverishly and can hardly stand to take a break from it.

  I’m extremely happy with how it’s shaping up. It’s getting more and more complete, and yet still staying quite “micro.” Notably, it just recently crossed 1500 lines of C (I don’t count auto-generated code in this), and it compiles to not quite 10kb of object code. Throw in the auto-generated code (reflection data that describes the types in descriptor.proto — this is what allows loading other proto definitions at runtime) and this jumps to about 16kb. Keep in mind that this effectively has all the major features of the main protobuf implementation (albeit packaged in different ways), but the main protobuf implementation is just over 1MB of object code!

  I still think I can reach the main protobuf implementation’s performance, or maybe even exceed it. I will consider the project a failure if I can’t get within 15% of its performance.

  Anyway, just wanted to be sure everyone knows I’m still alive and very much working on this. Now back to work.

• 

  Bit-fields in C99

  Posted: June 26th, 2009, 8:48pm MDT by josh

  Recently I came upon some spirited discussion on reddit concerning a blog post that discussed the use of bit-fields in C. As a quick refresher to anyone unfamiliar or rusty on bit-fields, they are a construct in C that lets you specify how many bits different members of a structure should be allocated:

  struct foo {
    unsigned int a:1;
    unsigned int b:2;
  }

  Without the bit-field specifiers (the “:1″ and “:2″ above) this structure would be at least four bytes long, and both “a” and “b” would be capable of representing integers from 0 to 65535. With the bit-field specifiers the structure is likely only one byte long, and “a” and “b” can only represent 0-1 and 0-3, respectively. Bit fields are a way to store many distinct values compactly inside a struct, to save memory.

  I am using bitfields in upb to store flags for whether each field is set or not. When I generate a structure definition for a specific proto type, code in the header file looks something like this:

  struct google_protobuf_DescriptorProto {
    union {
      uint8_t bytes[1];
      struct {
        bool name:1;  /* = 1, optional. */
        bool field:1;  /* = 2, repeated. */
        bool nested_type:1;  /* = 3, repeated. */
        bool enum_type:1;  /* = 4, repeated. */
        bool extension_range:1;  /* = 5, repeated. */
        bool extension:1;  /* = 6, repeated. */
        bool options:1;  /* = 7, optional. */
      } has;
    } set_flags;
    struct upb_string* name;
    UPB_STRUCT_ARRAY(google_protobuf_FieldDescriptorProto)* field;
    UPB_STRUCT_ARRAY(google_protobuf_FieldDescriptorProto)* extension;
    UPB_STRUCT_ARRAY(google_protobuf_DescriptorProto)* nested_type;
    UPB_STRUCT_ARRAY(google_protobuf_EnumDescriptorProto)* enum_type;
    UPB_STRUCT_ARRAY(google_protobuf_DescriptorProto_ExtensionRange)* extension_range;
    google_protobuf_MessageOptions* options;
  };

  (that’s from descriptor.h, which is automatically generated from descriptor.proto from the official protobuf implementation).

  I “union” the bitfield with bytes so I can set the bytes en-masse more efficiently. This seems like a really nice solution, because then client code that wants to test whether a field is set in a protobuf can write code like:

  if(fd->set_flags.has.message_type) {
     // ...
  }

  So unfortunately the commenters on Reddit were pretty down on bit-fields and the aforementioned article. The points they raised filled me with despair that I would have to abandon bit-fields. This is bad because the only real alternative I would have for this kind of code generation is to generate explicit getters and setters for each bit of each structure! The code would then immediately become quite uglified:

  if(google_protobuf_DescriptorProto_has_message_type(fd)) {
    // ...
  }

  Besides being longer and forcing you to re-type the whole name of the enclosed type, this approach forces you to generate lots of nearly-identical code and pollute the symbol namespace with tons of these useless functions that add no real value. I was bumming about this.

  But as I investigated the supposed problems with bit-fields, I became convinced that the problems were tractable and that I could in good conscience press forward with my plans to use them as intended.

  Here Be Dragons

  “Almost everything about [bit] fields is implementation-dependent.” –K&R, Section 6.9

  From my reading of the C99 standard, here are the guarantees you get (or don’t get) with bit-fields.

  1. Bit-fields will be packed as tightly as possible, provided they don’t cross storage unit boundaries: YES. From the standard: (6.7.2.1 #10):

  An implementation may allocate any addressable storage unit large enough to hold a bit-field. If enough space remains, a bit-field that immediately follows another bit-field in a structure shall be packed into adjacent bits of the same unit.

  The first part just means that the compiler can allocate any number of bytes to a bit-field, as long as it has enough bits. So if you write:

  struct foo {
    unsigned int a:8;
  }

  …a will be at least 1 byte long, but could be more. But the second part is where we get the nice guarantee that:

  struct foo {
    unsigned int a:1;
    unsigned int b:2;
  }

  …will always be packed into a single byte. sizeof(struct foo) could be greater than 1, but you are guaranteed that a and b are in the same byte.

  2. Bits are allocated low-to-high (or high-to-low): NO. This is not guaranteed by the spec, so an implementation could choose to allocate bits either starting at the high bit or the low bit of each byte. The following program will test an implementation to see which it is:

  #include <stdio.h>
  int main() {
    union {
      struct {
        unsigned int a:1;
        unsigned int b:2;
        unsigned int c:3;
      } bitfield;
      unsigned char ch;
    } u = {.ch = 0};
   
    u.bitfield.a = 1;
    u.bitfield.c = 7;
    switch(u.ch) {
      case 0x39: printf("Bits allocated LOW-TO-HIGH.\n"); break;
      case 0x9C: printf("Bits allocated HIGH-TO-LOW.\n"); break;
      default: printf("Oddball allocation: 0x%02hhx.\n", u.ch); break;
    }
    return 0;
  }

  My Goal

  What I am trying to do is create a C struct like the above, but also be able to perform data-driven reflection on that C struct based on generic routines like:

  INLINE bool upb_msg_is_set(void *s, int index)
  {
    return ((char*)s)[index / 8] & (1 << (index % 8));
  }

  This means that my reflection routines like the one above need to be able to mimic the implementation-defined bit ordering as described above. The routine above does not — it assumes that the bits are assigned from low to high. But a few #ifdefs should make the above not too difficult.

  Performance

  In theory, the ideal compiler should love bit-fields because they give it maximum information with which to optimize loads and stores. I see a lot of people claim that some compilers generate bad code for bit-fields, but that is a possibility with any construct you use. From what I can see GCC generates very good code for bit-fields.

  So my conclusion is that the hurdles of bit-fields are tractable, and unless some new information comes my way, I plan to move forward with my plan to use them.

Comments for Josh the Outspoken

• 

  Comment on one malloc to rule them all by josh

  Posted: May 11th, 2009, 12:38pm MDT by josh

  Good point Matt, though you make me realize I also forgot up-front overhead (6MB for tcmalloc) and how fast memory is returned to the OS (tcmalloc is not very good about this).

• 

  Comment on pbstream’s name by josh

  Posted: May 6th, 2009, 10:57am MDT by josh

  Jack: C doesn’t have namespaces, and pbstream/upb is written in pure C (not C++).

• 

  Comment on pbstream’s name by josh

  Posted: May 4th, 2009, 2:09pm MDT by josh

  Ooh, I think we may have a winner. I really like “upb”!

  Thanks everyone for your suggestions.

  Yes, it’s annoying that preview doesn’t work correctly on this blog. Sorry about that. I think it’s a bug in the style I’m using, but I’ve never taken the time to really dive in and figure out what’s wrong.

2 Star

• 

  pbstream’s name

  Posted: May 3rd, 2009, 9:09pm MDT by josh

  I hate naming things. I’m starting to realize that pbstream is outgrowing its name. That’s the one thing I always thought was brilliant about the iPod’s name. When the iPod started playing video it was no problem — it’s a pod! Why shouldn’t a pod play video? There’s no way to outgrow the name “iPod.” Brilliant.

  I had no such luck with pbstream. The tagline is currently:

  pbstream - a stream-oriented implementation of protocol buffers.

  It’s true that offering streaming semantics is one distinguishing feature of my implementation, but the way it’s growing it’s no longer really “stream-oriented.” It will offer both stream-oriented and structure-oriented semantics. Both will be equally supported/encouraged — it will be a matter of what best suits your needs.

  If anything, the number one distinguishing feature of my implementation is that it is minimal. It gives you a set of tools to use whatever paradigm is the right trade-off for you. It gives you building blocks to assemble as you see fit. There are never “riders” — things like memory management that you have to take along with the parts you really want.

  So what’s in a name? Desired characteristics:

  • Unique, reasonably Googleable.
  • Communicates that it is a protobuf implementation, and if possible communicates the philosophy described above.
  • The name (or a reasonable abbreviation thereof) makes for a nice prefix that can be appended to all my identifiers. Right now it’s pbstream_this and pbstream_that.

  Originally I just called it “pb” but that was a tad bit too generic. I slightly like “pblab” (communicates that it gives you building blocks for forging your own strategies), but I dislike the connotation that it is unfinished, unpolished, not production quality.

  Perhaps I could give it a name, but keep using “pb_” in my identifiers. It could also help me organize the names of the different parts. I could use names like:

  • pb_stream_parser_* for the stream parser.
  • pb_struct_* for the code that defines an in-memory structure.

  I kind of like that. But I still need a name for the package itself that is better than “pb”. Ideas?

• 

  “Hey! It’s been months! What happened?”

  Posted: May 3rd, 2009, 8:43pm MDT by josh

  …reads the latest comment on my last entry. It’s true, I’ve gone silent for a few months. Work on pbstream has languished. The answer to “what happened?” is a combination of a personal life that got crazy and a brick wall I hit in the design of pbstream. But I think I have resolved the latter of those at least and work is progressing again.

  So what is the brick wall I hit with pbstream? I had conflicting goals that I couldn’t figure out how to reconcile. One goal was to include as little policy related to memory management as humanly possible. In other words, if you’re using pbstream to store fully-parsed protobufs in memory — I’ll use the SAX vs. DOM analogy again, where this is the DOM case — then I want pbstream to not define any semantics for how the memory for that tree is managed. Is it reference-counted, garbage-collected, or is it just allocated/deallocated in one big chunk? Every runtime already has its own answer to this question. I don’t want to include a memory management strategy, which adds to the code size and complexity, just to have it be an annoying thing that you have to integrate into whatever runtime you’re already using.

  Or, as I said in a previous entry: Oh fantastic! Because definitely the one thing that my application doesn’t already have is a memory manager.

  On the other hand, I realized that I really do want the ability to pass an in-memory protobuf representation between language implementations. For example, if there’s a C library that conjures up some complex protobuf, I want to be able to pass that parsed in-memory protobuf to Python without serializing/deserializing. I want different runtimes to be able to look at this memory and make sense of it.

  So far so good. This alone doesn’t require memory management. But I also wanted two things that do pose a memory-management problem:

  • I wanted to pass protobufs between language implementations without copying.
  • I wanted one language implementation to be able to modify the protobuf that had been created by a different language implementation.

  The first is a problem because if you take a protobuf you created in C and pass it to Python, once that Python returns C has no idea whether Python has taken references to any of the protobuf’s data. If C frees the protobuf, Python could try to later read from the freed memory. If C doesn’t free the protobuf, the memory will leak. The fundamental problem is that C and Python have no way of cooperating to be sure the memory is freed only when the last reference that either of them holds is dropped.

  The second is a problem for a similar reason. Suppose you take a protobuf you created in C and pass it to Python, and Python wants to mutate that protobuf. Suppose the protobuf has a submessage, which is implemented as a reference to that other message. If in python you say:

  message.submessage = other_submessage

  …Python now has to decide what to do with the submessage that message already had. Should it free it or not? If you free it and C had a reference to it, C references freed memory. If you don’t free it and C doesn’t have a reference to it, it leaks.

  I fretted over the question of what to do about this for weeks. I didn’t want to give up the ability to pass protobufs between languages without serializing/deserializing. But I was loath to include the slightest amount of memory management code because of the implied complexity, run-time overhead, and code size effects. So everything ground to a halt while I tried to reconcile these conflicting desires in my head.

  At one point I convinced myself that the only way out was reference-counting. The in-memory protobufs themselves would contain one extra integer for the reference count, and the code would contain just these little extra reference count increments/decrements and checks. Then C and Python would both maintain reference counts to these shared data structures. For Python it would be a sort of two-stage reference counting, since the individual Python objects would be reference-counted, and when their reference count dropped to zero they would decrement the reference count of the shared protobuf structure one.

  Eww, Eww, EWW!! Now maybe you can understand a bit better why I haven’t gotten anything done for a while. There’s no way I could be very happy implementing this scheme.

  So quite recently I found a way to relax the sharing requirements just enough that I can get away with not implementing any memory management. My new strategy is:

  • language A can reference language B’s protobufs, but only for as long as B guarantees that all the references will continue to be valid. In most cases this just means that when B calls A and passes a protobuf, A can only reference B’s protobufs before it returns control back to B.
  • In general, languages cannot mutate each other’s protobufs unless they have some special arrangement with regards to memory management. I thought I really needed this capability in Gazelle, but I’m no longer convinced I do.

  So with that resolved, work is resuming, and I hope to have some results soon. I always hate making promises though, because I’m unwilling to press on when I don’t have a satisfactory answer to a question (as the last month demonstrates), and this can delay my progress long beyond my original intentions.

Josh

• 

  habes @ 2009-05-02T15:14:00

  Posted: May 2nd, 2009, 4:42pm MDT by Josh

  The Internet gets more amazing all the time, in ways that I'm not necessarily even paying attention to. So one day I'm thinking to myself "I wonder if the Internet can help me learn math," and to my great delight you can now watch video lectures from MIT, Stanford, Berkeley, and probably others. You can watch them anytime, you can shop around until you find the best professor, and you can work at your own pace.
  
  I always wished I had more time to take math and physics in college. Now I have the chance to fill in the gaps in my understanding. Currently on the docket:

  • Linear Algebra from MIT. I took Linear Algebra in college, but didn't come away with nearly as strong an intuition about it as I wanted to. For example, the first time I read the Wikipedia page on eigenvectors I was totally floored, because it has this picture that visually illustrates what an eigenvector is. I learned how to calculate eigenvectors, but didn't understand what they actually represent. This MIT course is taught by Gilbert Strang, who appears to be very good at explaining high-level concepts and cultivating intuition.
  • Differential Equations from MIT. I've never taken differential equations, and have almost no idea what they are or what they're used for, except that they're somehow closely tied to many physical phenomena. I'm interested because they seem to have some relation to the ultimate prize, which is:
  • The Fourier Transform and Its Applications. I've desperately wanted to be able to write programs that analyze the frequency content of sound since I was in high school. I'm currently working through the book Understanding Digital Signal Processing, which is very good, but I want a chance to hear it explained in video lectures also.
  • Computational Science and Engineering I. I don't understand entirely what this class is about, but it seems to be engineering-oriented and also covers Fourier Series.

  The only thing I need now is a little discipline.

2 Star

• 

  C Compilers

  Posted: March 3rd, 2009, 2:38am MST by josh

  So the more I work on pbstream (and I’m working on it quite a lot) the more obsessed I get with making it perfect. I’m no longer just out to just write some good software, my new goal is to utterly demolish this problem space with blindingly utter perfection. It’s going to be one of the best things I’ve ever done.

  So my latest OCD goal this quest is to make it truly 100% C99 compliant: compilable on the weirdest and most nontraditional target, and free of any undefined behavior. I like most people have spent several years lulled into the x86/GCC monoculture. It’s time for me to transcend that narrow-minded view.

  So I’ve set out to obtain every C compiler and lint tool I can possibly find, hoping that each one can show me even the smallest spot of imperfection that I can proceed to purge from my crystalline statements and declarations. I was ashamed to realize that I couldn’t even think of a time I had used a non-GCC/MSVC compiler in almost five years, and I didn’t know which ones were available to me. I am happy to say that I have eradicated some of that ignorance, and already have found some bugs that GCC didn’t show me!

  So what C compilers are out there? Here are some of the ones I came across:

  • Sun Studio, Sun’s C and C++ compiler. To my surprise, it is available for free. Includes a lint tool.
  • Intel C++ Compiler. You can obtain a non-commercial version for free if you absolutely, totally, cross-your-heart promise that you are not compensated in any way for your work. I have a vision of the Intel guys following around open-source developers at conferences and revoking them their non-commercial licenses at the first sign of any swag.
  • Digital Mars C and C++ compiler, which is freely available for Windows and DOS.
  • Visual C++ Express is a free download from Microsoft. Apparently has very poor C99 support though.
  • The Portland Group has a C and C++ compiler, but there doesn’t seem to be any way to use it without paying several hundred dollars.
  • Comeau has a C and C++ compiler that takes great pride in its standards-compliance. You just have to get over the curiously awful web page, which actually says “Bursting With So Much Language Support It Hurts!” No free use (though at $50, it’s not a big hurdle — I paid more for a parking ticket today. If only I hadn’t had six such parking tickets to pay. For parking on my own street. But that’s a story for another day). There is a web form (!) where you can paste your code and see error/warning messages though, which could be all you need to test standards-compliance.
  • SDCC, the Small Device C Compiler is a GPL’d C compiler that targets tiny embedded processors. I was looking quite forward to this one as a target that is wildly different from other C compilers. Unfortunately, though it has partial C99 support, it does not support 64-bit integer types, and I’m not quite willing tilt at that particular windmill of making pbstream portable to compilers without 64-bit integer support.
  • TCC, the Tiny C Compiler. Fabrice Bellard is an absolute bad-ass, but unfortunately TCC doesn’t seem to support much of C99 (it choked on a for loop that defined a variable).
  • Clang, the LLVM compiler. My version of Ubuntu doesn’t seem to have this available, and I always find LLVM a bit of a pain to compile and install from source, but I would like to try this when I get the chance.

  So this should be enough variety that I can feel confident making smug assertions about pbstream’s portability. Now the only question is whether I’ll shell out $50 for the Comeau compiler just for that added potential for portability smugness.

Comments for Josh the Outspoken

• 

  Comment on The art of hashing by josh

  Posted: March 1st, 2009, 5:34pm MST by josh

  @Kragen: while shelling out to the system is always a possibility, I’m really trying to stay within portable C99, and not make assumptions about the environment. A good model for what I’m going for is zlib: I think zlib is ubiquitous in large part because it makes absolutely no assumptions about your system. It even lets you swap in your own implementations of malloc and free

  For example, I want pbstream to be usable in embedded system. Here’s an example of a guy who’s in a situation I want to accommodate: GPB on non-Linux, non-Windows OS?.

  I hear what you’re saying wrt. just using Python’s dict. Although accommodating languages like Python, Ruby, Lua, etc. is one of my goals, I also want this library to perform well standalone, in cases where there is no other hashtable implementation available. Also, of my two hashtable use cases, the int->void* lookup that happens in the critical path of parsing is the more important one to me by far, and this happens at a layer below where you’d interface something like Python or Ruby.

  It makes me really happy that you’re independently interested in Gazelle! pbstream and Gazelle are actually soon to be intertwined: Gazelle needs a bytecode format and an AST serialization format (I mean to switch to protobufs from LLVM bitcode), and pbstream needs a way to parse .proto files. pbstream->Gazelle won’t be a hard dependency though — you’ll be able to load .proto definitions in binary form if you want.

  I’m afraid I’m drawing a complete blank on your friend Matthew O’Connor though, and I’ve never been associated with Pivotal. Is there something I’m forgetting?

• 

  Comment on The art of hashing by josh

  Posted: March 1st, 2009, 1:52pm MST by josh

  @Brian: there are many, many reasons that I hope to write up at some point. Basically I’m trying to implement protobufs in layers, where the lowest layer is blindingly fast and flexible. Say you have large protobufs (which a lot of people already do) and you want to just pull out the first value for field X. Existing protobuf libraries will make you parse the whole protobuf, copy it all into a separate data structure (malloc is expensive), just to get that one value! Mine will let you scan the protobuf for that value, and stop parsing when you find it.

  @Kragen: I should have said “lookup speed trumps all within the constraint that I don’t know the table at compile time. One of the things I’m trying to deliver is a Python API that doesn’t require you to build a C extension for each different proto type you want to parse (ick!).

  I’m considering adding a JIT using LLVM or similar sometime in the future — if I do that then I could do what you say.

2 Star

• 

  The art of hashing

  Posted: March 1st, 2009, 2:50am MST by josh

  It might sound strange for me to call hashing an art. After all, it’s about the most fundamental data structure we’ve got, after arrays, linked lists, and binary trees. It’s been studied extensively for fifty years. What amount of “art” could possibly be left in such a topic?

  I’ve learned to anticipate that there are dark and unstudied corners in even the most fundamental computer science topics. And hashing appears to be no exception. I’m investigating hashing at the moment because I need hash tables in a few places for my rapidly-developing Protocol Buffers implementation pbstream. So I wanted to take a quick survey of the state-of-the-art in hash tables, and implement a minimal hash table that suits my needs.

  What are my needs? If someone defines a protobuf like so:

  message Person {
required string name = 1;
required int32 id = 2;
optional string email = 3;
}

  …I need to build two hash tables for looking up fields: one keyed by number (1, 2, 3) and one keyed by name (name, id, email).

  You might say “why not just use an array for looking up fields by number?” Indeed that’s what I’ll do in most cases, but field numbers can be as large as 2**27 and needn’t be allocated densely. So gracefully degrading to a hash table is important (one practical reason why the field numbers might not be dense is if the client is using extensions). To get the best of both worlds I’ll follow Lua’s lead and have the field number table be a hybrid array/hashtable, where the size of the array part is such that it’s at least half full.

  My usage pattern for these hashtables is that I’ll build them once (when I parse a .proto file), then do lookups in the critical path of parsing. So insert time is practically irrelevant, but lookup time is extremely important, because it’s in my critical path. I’ll gladly trade some memory for fast lookups.

  So I figured I’d take a few hours to discover the state-of-the-art in hashtables, implement that, and be on my merry way. Unfortunately there doesn’t seem to be much agreement about what the state of the art even is!

  Let’s start with even the simple and most basic question: how big should a hashtable be? The literature differs here: some of it claiming that hashtables should have sizes that are prime numbers and some saying they should be powers of two.

  But once you’ve decided that, you’ve only just entered the jungle of collision-resolution strategies. There are a lot of them, and it’s not at all clear to me that the trade-offs are well understood. A list of ones I’ve come across, and my current understanding of what they mean:

  • linear probing: if your hash function is h(k), then a collision in T[h(k)] means you should also try T[h(k)+i] for i=1 to some limit.
  • quadratic probing: like linear probing, but also throw in a T[h(k) + i + j^2], to spread it out a little.
  • double hashing: like linear probing, but you scale the jumps by another hash function: T[h(k) + g(k)*i].
  • chaining: all entries that collide are in a linked list, so for lookups you search this list. chaining can be either internal (table entries have both values and links, links point to other locations in the table) or external (table is just pointers to the head of linked lists, inserts always allocate a new node).
  • cuckoo hashing: Wikipedia makes this sound like hashing’s best-kept-secret. You use two hash functions: if you do an insertion and the spot you want is taken, you kick whatever was already there out and put it in its alternate spot.
  • two-way chaining: use two hash functions (like cuckoo and double hashing), but you use the two hash values to find the two possible chains the value could be in.

  Few papers seem to offer a comprehensive account of the trade-offs between these. Some authors claim that linear probing is best on modern CPUs because of excellent locality (cache-friendly), but this paper [PDF] takes exception to that claim, saying that the better overall performance of double-hashing negates the cache effects. And indeed, none of the real-world implementations I found use linear probing.

  A quick survey of mainstream hashing implementations shows that they can’t agree on what’s best either.

  • Lua uses internal chaining with powers-of-two table sizes and “Brent’s variation” (so-named because of a 1973 paper called Reducing the retrieval time of scatter storage techniques — so much for caching-conscious schemes).
  • Ruby uses internal chaining with prime table sizes.
  • Python uses a custom probing scheme. You have to read the comments in the source file itself — they do more to make hashing sound like black magic than I possible could.
  • Perl appears to use external chaining, but its code is a bit hard to follow.

  Even if you decide on a collision strategy, you still have to decide on a hash function, and there are surprises lurking for you there as well. Conventional wisdom about hashing is that you want a hash function that randomly distributes the inputs to the outputs. But Python and Lua both hash integers to themselves (so h(5) = 5)!

  There are just a dizzying number of variations on hashing. Given my relatively simple use case (one-time construction, lookup speed trumps all) you’d think there would be a clear and obvious answer. But I don’t see one.

  Given my deep respect for Lua’s implementation, I’m tempted to just start with that and worry about trying to optimize it later. I’m slightly disconcerted with its focus on getting good performance even when the table is quite full, because as I mentioned for my use case I’ll gladly trade modest amounts of RAM for faster lookup. At least it’s someplace to start.

  But seriously, who knew that hash tables had so many variations, with no clear winner?

• 

  Microsoft Gazelle?

  Posted: February 22nd, 2009, 3:39pm MST by josh

  Looks like there’s another Gazelle in the herd. Microsoft Research has released a paper about a web browser called Gazelle:

  In this paper, we introduce Gazelle, a secure web browser constructed as a multi-principal OS. Gazelle’s Browser Kernel is an operating system that exclusively manages resource protection and sharing across web site principals.

  It’s easy to have my first reaction be annoyance. After all, I’ve been using the “Gazelle” name for over a year. For the same reason I was a bit annoyed when a BitTorrent tracker named Gazelle was released last year.

  Then I remember that my “Gazelle” isn’t all that discoverable, even for someone looking to do due diligence about this. For reasons I don’t fully understand, my Gazelle is not returned very high in Google search listings (proof that working at Google isn’t a guarantee of good search listings). Here are my search rankings for various search phrases:

  • gazelle software: result 83 (blog)
  • gazelle project: result 86 (blog)
  • gazelle program: result 89 (blog)
  • gazelle system: result 4 (project homepage)
  • gazelle download: result 34 (project homepage)
  • gazelle parse: result 1 (github), result 2 (project homepage)
  • gazelle parser: result 1 (project homepage)

  Conclusion: unless you already know Gazelle is for parsing, or you think to call it a “system,” it’s pretty impossible to find it by its name. The reason I tried “gazelle system” is because the HTML title and headline on the homepage is: Gazelle: a system for building fast, reusable parsers. And that seemed to pay off — it has a much higher ranking for that phrase.

  Guess I need to learn some search engine optimization. I should either use the words “project”, “software”, etc more on the homepage, or I should put them in a meta tag or something.

  Not that Microsoft would have decided to change the name of their browser thing, but being discoverable is good in general.

  In related news, I got the domain gazelle-parser.org, and replicated the homepage there, but I haven’t updated any links to point to it yet. Part of my vision for this site is that it will host a repository of known-good grammars, and let you parse snippets of text for these grammars through a web interface.

• 

  one malloc to rule them all

  Posted: February 20th, 2009, 6:12pm MST by josh

  Came across this on Reddit today:
  

  TLSF is a general purpose dynamic memory allocator specifically designed to meet real-time requirements:

  • Bounded Response Time . The worst-case execution time (WCET) of memory allocation and deallocation has got to be known in advance and be independent of application data. TLSF has a constant cost O(1).
  • Fast. Additionally to a bounded cost, the allocator has to be efficient and fast enough. TLSF executes a maximum of 168 processor instructions in a x86 architecture. Depending on the compiler version and optimisation flags, it can be slightly lower or higher.
  • Efficient Memory Use . Traditionally, real-time systems run for long periods of time and some (embedded applications), have strong constraints of memory size. Fragmentation can have a significant impact on such systems. It can increase dramatically, and degrade the system performance. A way to measure this efficiency is the memory fragmentation incurred by the allocator. TLSF has been tested in hundreds of different loads (real-time tasks, general purpose applications, etc.) obtaining an average fragmentation lower than 15 %. The maximum fragmentation measured is lower than 25%.

  So put another way, this malloc is fast, bounded in its response, and memory-efficient! Apparently it has no downsides. Just what I like to hear!

  That’s the crazy thing about malloc implementations. They all claim to be awesome in every way. So the burning question is: is this better than what I’m using today? I don’t know, but I’d sure like to!

  I think that malloc() is an under-appreciated source of slowness in many applications these days. Apple’s fantastic profiler Shark even has a malloc() tracing mode to help discover malloc-related sources of slowness in a program. From the link above:

  In today’s large and complex software applications, it is often informative to understand the scope and pattern of memory allocations and deallocations. If you understand how your software objects are being created and destroyed, you can often improve the overall performance of your application significantly, since memory allocation is a very expensive operation in Mac OS X, especially for large blocks of memory. If your program suffers from memory leaks, Malloc Trace is also a good way to identify locations in your program that may be the culprits.

  I wish I had real data about this, but I strongly suspect that the reason that Firefox (for example) slows down the longer it’s open is because malloc() calls start taking longer and longer. Have you ever noticed that after you’ve had Firefox open for a long time, even just opening a new blank tab takes a second or two? What does opening a new tab have to do but allocate memory?

  So personally I’d love to be running a real-time and O(1) malloc() on my desktop. And the web page claims that it’s not only real-time but “real fast,” which is even better.

  This made me think of Jason Evans, author of jemalloc, which he wrote for FreeBSD to scale better across multiprocessors (since malloc() can be a source of contention). He was also working with the Firefox guys to have Firefox 3 use jemalloc, though I’m not sure if that happened or not.

  In any case, Jason Evans seems to have come to the conclusion mid-last-year that using red-black trees (an O(lg n) data structure) in jemalloc was a mistake and that he should have gone with O(1) (as TLSF above does). And it sounds like he eventually changed jemalloc to use O(1) algorithms instead. From his blog entry Overzealous use of my red-black tree hammer:

  Once Firefox was successfully using jemalloc for all memory allocation, I started doing performance tests. Memory usage differences were minor, but jemalloc was consistently slower than OS X’s allocator. It took a lot of profiling for me to finally accept the hard truth: jemalloc was spending way too much time manipulating red-black trees. My first experimental solution was to replace red-black trees with treaps. However, this made little overall difference. So, the problem was too many tree operations, not slow tree operations.

  After a bit of code review, it became clear that when I fixed a page allocation bottleneck earlier this year, I was overzealous with the application of red-black trees. It is possible to use constant-time algorithms based on linear page map data structures for splitting/coalescing sequential runs of pages, but I had re-coded these operations entirely using red-black trees. So, I enhanced the page map data structures to support splitting/coalescing, and jemalloc became markedly faster. For example, Firefox sped up by as much as ~10% on JavaScript-heavy benchmarks. (As a side benefit, memory usage went down by 1-2%).

  In essence, my initial failure was to disregard the difference between a O(1) algorithm and a O(lg n) algorithm. Intuitively, I think of logarithmic-time algorithms as fast, but constant factors and large n can conspire to make logarthmic time not nearly good enough.

  I’m not sure if the changes he made mean that jemalloc is now real-time, but I would be interested to know. I would also be quite interested to see benchmarks between all the mallocs floating around. The ones I know of are:

  • TLSF
  • jemalloc
  • dlmalloc (Doug Lea’s malloc, been around forever)
  • ptmalloc2 (Doug Lea’s malloc, extended to support per-thread arenas. Default allocator for glibc2.3?)
  • TCMalloc (Google’s malloc, claims to be 6x faster than ptmalloc2)
  • nedmalloc (claims to be faster than tcmalloc)
  • Hoard, also claims to be very fast

  I think an open-source malloc benchmark that compared all of these under tons of different scenarios would be so so awesome to have. Everyone claims their malloc is the fastest. What is the truth? It could be that different implementations excel in different scenarios. After all, malloc performance has several dimensions:

  1. size of the allocations
  2. how the allocations are distributed across threads (for thread-safe allocators)
  3. current size of the heap
  4. max size the heap has had
  5. number of operations that have been performed (eg. how long has the app been open?)

  And consequently there are several factors to measure:

  1. speed of each operation (obviously)
  2. worst-case performance
  3. memory fragmentation
  4. locality (if allocations that happen closely in time are also close in space, they will be more cache-friendly)

  So dear college students who are interested in systems and want to do something awesome: create an awesome, open-source malloc benchmark suite!

Josh

• 

  habes @ 2009-02-16T14:13:00

  Posted: February 16th, 2009, 3:15pm MST by Josh

  What are the chances that two nuclear submarines accidentally collide in the middle of the ocean in the same month that two satellites accidentally collide in the middle of space?

2 Star

• 

  Static Lua

  Posted: February 9th, 2009, 12:52pm MST by josh

  Following up on my last post, here’s what I’d like to do someday (read: in the future. not now).

  I’d like to create a language that is as much like Lua as possible, but adds just enough to make it static and type-safe. Specifically:

  1. all variables must be defined before use.
  2. all variables and function parameters must have a type specified. though it would support “auto” that can infer the type from the initializer. there would be typenames for all of lua’s built-in types, and classes would have names too.
  3. there would be a “class” construct. just enough to let you specify the class name, parent class, maybe abstract interfaces you implement, and then a class definition inside curlies.
  4. inside a class definition, you would define your instance methods with the same syntax that you declare faux instance methods in Lua today.
  5. inside a class definition you can also put instance variables.
  6. class methods and instance variables can be public, private, protected, etc.
  7. objects would show up as a “userdata” in Lua, which would let you use them just like regular Lua faux classes, except that referencing nonexistent fields would throw an error.

  The benefits would be:

  1. Static Lua and Lua could operate seamlessly.
  2. Static Lua would have much better performance because (1) type checks would be performed at compile time instead of runtime, (2) property accesses could be array offsets instead of hash table lookups, and (3) all types are known at compile time so the compiler could generate much more optimized code.
  3. Static Lua would have all the benefits of static languages, and Lua would have all the benefits of dynamic languages. But they would both be runtime-loadable, and could both be JITted using LLVM.

  And to Java people who would say that I’m re-inventing the JVM, I would like to remind you that I happen to actually care about memory footprint, startup time (scroll all the way to the bottom to find Groovy), and having a lightweight (small, easy-to-distribute) runtime embeds nicely and plays well with others. Maybe the right implementation of Java would be what I’m looking for, but I’m not that interested in a joining a language community that has demonstrated for 15 years that it has no regard for such things.

  I’m a die-hard minimalist, and will never be satisfied building on top of runtimes that do not have the same appreciation for minimalism. There’s a reason zlib (for example) is absolutely everywhere you look today. It’s the tiniest and most unobtrusive C library you could possibly imagine for doing compression. There is absolutely nothing about it that can make anybody say “it has great functionality, but [I only have 64k of RAM]/[I need to compress 1TB streams with much less than 1TB of RAM]/[I need to have control over all memory allocation]/[I need to be able to impose hard limits on its resource usage].”. No matter what you’re doing, zlib is there for you, because it imposes the absolutely minimal amount of requirements on whatever is embedding it.

  I want the same to be true for Gazelle, my protobuf implementation, and pretty any software I’m writing for the ages.

Comments for Josh the Outspoken

• 

  Comment on Disappointment by josh

  Posted: February 9th, 2009, 11:51am MST by josh

  Thanks for chiming in Matt — actually part of the reason I wrote this entry was in hopes that you’d offer your insight about it. I think that with a combination of the strategies you mention as well as just a tiny bit of metaprogramming that only lets you assign to a predefined list of keys, I can get enough of what I need that I’ll be satisfied that the compiler can grow but stay understandable. Or maybe I’m just telling myself that because I have no other real choice at this point.

  A statically-typed language that lets you load run code on the fly as easily as today’s scripting languages seems totally possible, especially now that LLVM is getting so good. I think there’d be a market for this, especially if it was paired with a dynamic language that worked together with it (a la Java and Groovy, but without the enormous and high-overhead virtual machine).

2 Star

• 

  Disappointment

  Posted: February 9th, 2009, 3:14am MST by josh

  I have spent the entire weekend hacking on Gazelle and I have to say I’m somewhat disappointed in my results.

  I was looking quite forward to Gazelle-hacking this weekend. There is so much I want to do — so many things completely designed in my head that only need to be typed out. Specifically:

  • fixing all the open issues on Google code (thanks to everyone who has reported issues!)
  • making Gazelle self-hosting.
  • operator-precedence parsing.
  • integration with protobufs — this is how ASTs are going to be supported (it’s a beautiful fit!)
  • work on my in-progress protobuf implementation

  I’ve been itching to work on all these things, and had the free time this weekend to do it.

  So I sat down Friday night and looked at the first Google Code issue I intended to fix: Regex declaration are not taken into account if declared after they are used. When I thought about the right way to solve this problem, I realized that I needed to bind symbols lazily. If I’m parsing a grammar file and I see:

  a -> b;

  If “b” hasn’t been defined yet, I don’t know if it’s going to be a rule or a named regex. So I need to put a placeholder in “a” definition that I can bind later, once I know what “b” is.

  And when I thought about ways to do that, an intuitive feeling came over me that I’ve reached a point with the Gazelle compiler that I need to start imposing a bit more structure and discipline. Don’t get me wrong, I’m proud of the compiler’s code in many ways. It’s got lots of useful comments and a pretty good design. But when you’re using a dynamic language like Lua that gives you functions but not classes, you find yourself writing things like this:

  if fa.is_nonterm(self._transitions[1][1])
— …
end

  What is this table nested two deep? What does indexing into [1][1] mean? You just tend to get these tables where the knowledge about what the structure means is all implicit. Here’s the worst example I found (this one I’m *not* proud of). This expression occurs in the middle of a string concatenation:

  gla_state.rtn_paths:to_array()[1].prediction[2].rtn.name

  What are all of those intermediate data structures about? Well, if you search in the source file for “prediction” you find the answer:

  obj.prediction = {predicted_edge, predicted_dest_state}

  Ok, so this “prediction” thing is just a sort of ad-hoc tuple of (edge, dest_state), so the prediction[2] index above was pulling out the predicted dest state. But that wasn’t at all obvious from the call site.

  Another thing that tends to happen with a language where adding properties is easy (like it is in Lua) is that you start attaching properties to objects in random places. Especially with the Gazelle compiler where there are all these graph data structures floating around that are related to each other in various ways, you’ll be writing some code and find that you just need a reference to this one other related object. Like you’ll have a handle to a state in a graph, and you want a reference to the graph itself. So you’ll find someplace else in the program where the state had a reference to that graph, and just slip in a quick little:

  state.graph = graph

  …and presto, your other code can now just read state.graph and you’ve got what you need. Everybody’s happy!

  Except that having too much of this stuff accumulate can make your program hard to reason about. What are all the properties that these state objects ever have? Where are these properties added? When can you count on them being set? Is this the right list of properties for this object? Are the properties all orthogonal, or are some of them redundant? These questions are very difficult to answer when you have random code setting and reading properties in a dynamically-typed language like Lua.

  For this reason I’ve got to respectfully disagree with Steve Yegge about the attractiveness of the properties pattern. The biggest bummer about it is that there’s no place that you write down the list of properties for each type and what they mean. Without that, it’s hard for other people to get the high-level picture about your program’s design, and it’s hard for you as the program’s author to think about the design of the program and how it should be refactored.

  So I had an intuitive feeling that now was the time to introduce a little bit more structure. And my idea was to implement a very small subset of Ruby’s object model in Lua. Lua is a lovely language in that it gives you primitives that give you the tools you need to do a pretty convincing job of implementing whatever object-oriented model you like. And I’m a big fan of Ruby’s object model.

  So I sat down on Friday night, thinking this would take me a few hours of hacking, after which I could move on to the work I really wanted to do (the list I mentioned above).

  I’m a chronic underestimator, but this instance was pretty extreme. All in all, I spent about 20 hours on this problem this weekend. And while I finished what I set out to do, the performance is so disappointing that I’m not sure I’ll stick with it.

  My primary goals were:

  1. encapsulation. I want to know that an object’s instance variables are only modified in methods of that object. as a program grows, you’ve got to have lines you can draw around chunks of code and say “I can reason about this code in isolation without worrying that its state can be mutated in unexpected ways.”
  2. inheritance. I was using the OO scheme that’s explained in the Lua book, but it’s really bizarre in some ways. for example, to derive from a class you create an instance of it, which becomes the subclass (!?), and then you add methods to it and use it to construct other instances.
  3. a well-defined set of properties for each object. I want this list somewhere so I can docment it and reason about it, and I want to prevent typos

  With Ruby as my inspiration, I took a first go at it on Friday night until about 3AM. My first iteration supported properties even: if you said foo.bar = 5, that would turn into a foo.set_bar(5) call. I got it working, but it was super complex. I really wanted to keep the complexity down.

  I went through about two more iterations before arriving at this:

  object.lua (read the comments at the top of the file for more explanation and usage).

  Rather happy with the interface at this point, I started porting a lot of the compiler’s classes to this new object system. This was an extremely long and painful process, and the final result was this diff:

  700 lines of pain.

  It would have all been worth it except for the horrible moment when I ran my unit test suite and saw this:

  $ time make test
[...]
real 0m2.361s
user 0m1.889s
sys 0m0.070s

  Compare this with almost the same test suite directly before the port:

  $ time make test
[...]
real 0m0.633s
user 0m0.500s
sys 0m0.043s

  A 4x slowdown is just more than I can swallow for this.

  So I’m very sad to say that after an intense weekend of hacking, I’m pretty much back where I started, except for the experience of having written a small subset of Ruby’s object model in Lua. It’s very nice to use, but it’s just too slow. And a time profile doesn’t have too much low-hanging fruit.

  I still need a way to manage complexity as the compiler grows. I think my next iteration may be to just create a list of properties for each object and prevent assignment to any property that’s not on the list. I won’t get encapsulation with this scheme, but at least I’ll get a list of properties for each object, which will give me more a way to reason about the design of my objects. For example, just looking at the latest version of compiler/fa.lua is illuminating, because all of the objects have attr_accessor/attr_reader/attr_writer for all the properties that they are ever assigned. Before this change, I would have had no easy way of telling you this information.

  Still, the weekend has been a disappointment. I don’t so much enjoy any of this object system hacking for its own sake, especially when I have so much truly useful and ground-breaking work just on the tip of my tongue! I want to find a solution that I’m satisfied with, so I can get it over with and get back to real work.

  I have to say, sometimes I really think that what I want is a lightweight, embeddable strongly typed language. Sure, it’s nice when you’re writing little programs not to have to specify the structure of your program with lots of classes, type, and prototype declarations. But when your program grows to a certain size, the ability to impose structure can be extremely freeing, because explicit structure implies predictability. Predictability that when you get called, you’ll get called with the right number of arguments of the right types. Predictability that the contents of your objects are what is specified in your class definition, no more and no less. Predictability that when you’re implementing an interface, you implemented all the methods that were pure virtual in the base class (because if you hadn’t the compiler would have yelled at you).

  I’m using Lua because it’s a language that has a very small and efficient implementation, and also has implementations for other runtimes like the JVM. If there was a statically-typed language with these same characteristics, I would be tempted to use that instead. It could probably be more efficient too, because statically-typed languages can do offset-based member lookup instead of having everything be hash table lookups.

  But like I said, I’d much rather stop talking about all of this and get back to parsing. But I want to find a strategy for managing the growing complexity of Gazelle’s compiler.

Comments for Josh the Outspoken

• 

  Comment on Ruby 1.9.1 released by josh

  Posted: January 31st, 2009, 11:50pm MST by josh

  @Paul: I LOVE that you brought up specific arguments — seriously. This discussion just got some actual substance.

  I also like your examples. With regard to your first example, if it’s taking that long (and I could replicate the experiment) then it’s clearly counting from the beginning each time, which will clearly be inefficient. But that’s to be expected because it’s UTF-8.

  With regard to your attempt to help Ruby out, it appears from reading my 1.9 Pickaxe book (which you couldn’t have done because I’m guessing you haven’t bought it) that the reason for the error is that Ruby wants you to specify little-endian or big endian. Again, this makes sense if you think about it a bit, because Ruby’s exposing the fact that internally, it’s always storing the data as a set of ordered bytes. So you’ll get more luck if you do this:

  ruby19 -e “‘abc’.encode(’UTF-16LE′)”

  You can see a list of all the encodings that are loaded by default by doing this:

  ./ruby -e ‘Encoding.list.each {|enc| puts enc.name}’

  When I replicate your experiment with it encoded as UTF-32LE, it runs in 50 seconds on my machine. Which is clearly sub-optimal — the equivalent program using ASCII on Ruby 1.8 takes under a second on my machine. Not sure why the performance disparity — there’s certainly nothing preventing the implementation I described, which would make every encoding-specific operation about as expensive as a C virtual function call. Hopefully they will optimize this in the future.

  So you’ve demonstrated that the Ruby 1.9 implementation of multiple encodings is not currently very efficient. I don’t think you’ve demonstrated that it’s confusing (though it still might be, I don’t have the experience to say).

  But one performance-related characteristic of the Python approach is that you always pay the cost to transcode into Unicode first. So take a program that does nothing but count the number of characters in a file. Python will always run the entire file through a transcoder first, then perform the len() operation on Unicode internally. Using the Ruby model, it could conceivably perform the least amount of work possible — nothing but an algorithm optimized to do len() on the input byte data directly, for whatever encoding the input is in. The cost to read data from the outside world into a string is essentially a memcpy (unless you want to do validation up-front). With Python you always pay a transcode up-front, unless your data is already in Python’s internal format (UCS-2? UCS-4? UTF-8? Some mixture? I don’t actually know what Python does here, and would be interested for more info.)

  So I think that in the end, Ruby’s approach actually has *greater* performance potential, though I can’t vouch for whether it’s currently optimized very well.

• 

  Comment on “Unicode is not an encoding” by josh

  Posted: January 31st, 2009, 8:39pm MST by josh

  @Carl: Your noun vs. adjective stuff is making a distinction that the Unicode standard itself does not make. The Unicode standard speaks of “The Unicode character encoding,” speaking in reference to the character set, not the byte-encoding:

  “The Unicode character encoding treats alphabetic characters, ideographic characters, and symbols equivalently, which means they can be used in any mixture and with equal facility.”

  also:

  “The Unicode Standard specifies a numeric value (code point) and a name for each of its characters. In this respect, it is similar to other character encoding standards from ASCII onward.”

  According to you, the above statements are nonsense, because the they concern the character set, not the byte-encoding. And yet this is straight out of page 1 of the standard. You’re going to have to admit that there’s some latitude in terminology here, unless this list of people who “don’t know the difference between an encoding and a character set” includes the Unicode Standard 5.0, page 1.

  I’m quite aware of the difference between a character set and a character encoding, when this specific distinction is drawn. Python is only capable of representing Unicode characters internally, which means that round-trips from encodings that are not injective onto Unicode will be lossy.

• 

  Comment on Ruby 1.9.1 released by josh

  Posted: January 31st, 2009, 7:20pm MST by josh

  @Paul: You suggest that I reserve judgment and yet you appear to have made up your mind.

  I don’t think there’s any requirement that the regular expression engine be “equally powerful for all encodings.” If it’s just as powerful for Unicode as Python is (which I suspect it is — I’m sure all regular expression implementers who want good Unicode support are reading this these days), but less powerful for other encodings, it still has Python beat.

  Without having looked at a single line of any of these implementations, I feel fairly confident in claiming that the performance difference is roughly one indirect branch per operation you want to perform in time, and one byte per string of space. Because the implementation is: store the encoding as 1-byte integer into a table of encodings, and then dispatch the operations by doing a table lookup into the table of encodings and branch to the appropriate implementation for the string you’re currently manipulating/inspecting.

  “I mean sure: if there is NO COST then it’s great to have more options. But when did you ever see an engineering decision where one option gave you more flexibility at NO COST and yet competent engineers consistently (with one or two exceptions) make the opposite choice?”

  I think that western engineers are very prone to treating text encoding as a problem solved completely by Unicode. Which I will agree it mostly is, but I think it fits perfectly into the engineer mentality to subscribe to a solution that very much looks as though it has exhaustively solved a particular problem.

  I think your best point is the one about complexity/predictability when it comes to using the APIs. But I somehow doubt that it will add much more complexity than the text/bytes distinction that both languages already had to introduce to support encodings properly. I will be interested to get more experience on this point however.

• 

  Comment on Ruby 1.9.1 released by josh

  Posted: January 31st, 2009, 5:35pm MST by josh

  @all the “unicode is not an encoding” people:

  [blog.reverberate.org]

  @troelskn: What makes Unicode the only sane way to store data in memory? As long as the support for a particular encoding/charset includes the operations you need (count characters, extract an individual character, extract substrings, etc). what is so insane about storing data in its native encoding, annotated with what encoding it is? You can always dispatch these operations to the proper implementation based on the native encoding.

  @Paul: your point is taken, but it’s never too late for other cultures to go down their own path because the current crop of software isn’t doing it for them. For example, haven’t I heard rumors about China and Russia working on their own operating systems? I know it’s not for any reason having to do with Unicode, but the point is just that the world’s a big place with lots of people who have totally different perspectives than us.

  “Risk” is probably the wrong word, since it will probably never keep your software from becoming popular or succeeding. But it might keep it from being useful to someone at some point, because they really want to not be stuck with what to them are the downsides of Unicode.

  I guess the point is, why commit when you don’t have to? I haven’t studied Ruby’s charset/encoding support in depth, but it appears to demonstrate that you don’t have to.

  @Carl: your arguments boil down to “the problems with Unicode are not important because they are not important to me.” Not very convincing. Also, you say that Python 3.0 supports “arbitrary encodings.” It may be able to transcode from arbitrary encodings, but this transcoding is not lossless if everything is Unicode internally.

2 Star

• 

  “Unicode is not an encoding”

  Posted: January 31st, 2009, 5:11pm MST by josh

  A lot of people commented on my last entry with the “Unicode is not an encoding” retort. This is apparently a pedantic point that people love to make to prove that they know more about internationalization of text than you do.

  The first such comment:

  Unicode is not an encoding - It’s a charset. It’s also the only sane way to represent characters in memory.

  I’ll see your pedantry and raise you one. Unicode is not only a character set, it’s actually a character set and three associated encodings. I will refer you to the Unicode Standard 5.0, section 2.5:

  The Unicode Standard provides three distinct encoding forms for Unicode characters, using 8-bit, 16-bit, and 32-bit units. These are named UTF-8, UTF-16, and UTF-32 respectively.

  These three encodings are part of the Unicode standard, and thus are part of Unicode.

  I will furthermore refer you to the first sentence of the standard:

  The Unicode Standard is the universal character encoding standard for written characters and text.

  I will furthermore refer you to two paragraphs later, which speaks of “The Unicode character encoding.”

  I will furthermore point out that the word “encoding” or “encode” appears 10 times in the opening section of the standard, while the word “set” (or “character set”) appears exactly once, and is in fact referring to ASCII (”the ASCII charcter set”), not Unicode.

  If the Unicode Standard itself is allowed to refer to Unicode inclusive as an “encoding,” then I am too. Though I hate to deprive the pedants of a point that they love correcting other people about.

Comments for Josh the Outspoken

• 

  Comment on Ruby 1.9.1 released by josh

  Posted: January 31st, 2009, 12:58pm MST by josh

  @chromatic: regular releases are great for development transparency. But Perl 6 was announced nine years ago! It has been in development for approximately one third of my life. There is no more reason to believe it will be finished in the next year than in any of the last nine. On the contrary, each year it isn’t finished makes it more likely (at least IMO) that it never will be.

  I’m sure you’re doing very good work, I just think that Perl 6 got too big and too complicated to be able to sustain itself.

• 

  Comment on Ruby 1.9.1 released by josh

  Posted: January 31st, 2009, 10:27am MST by josh

  @Joe: Yes, that’s true (that only one thread runs at a time in Ruby and Python), but I don’t think that either language its is on its way to ditching its global lock. Python tried and rejected fine-grained locking because all the locking/unlocking slowed down single-threaded code by 2x.

  Yeah, the benchmarks are a bit old, but I don’t get the impression that Ruby has undergone a lot of optimization work since YARV was merged. And Python 3000 is actually slower than Python 2.x, though only by about 10%.

  @Nathan: I did end up buying the PDF pickaxe book, and it’s 1.9 coverage is pretty good, except that there doesn’t seem to be a comprehensive “what’s new in 1.9.x” list anywhere. Then again, the book is only in beta, so perhaps this will appear before the final version.

2 Star

• 

  Ruby 1.9.1 released

  Posted: January 31st, 2009, 1:57am MST by josh

  Ruby 1.9.1 was released today. You wouldn’t know it from the version number “1.9.1″ but this is a big deal in the Ruby community. It’s the Python 3000 of Ruby, except it’s an even bigger deal than that because it’s not only a bunch of backward-incompatible language changes, but it’s also a totally new implementation with much better performance than the Ruby 1.8.x line.

  I’m glad to see this release, because I was starting to worry it would never happen, sort of like Perl 6. Now that Perl 6 has become the Duke Nukem Forever of programming languages, I was worried that Ruby 2.0 (oops, 1.9.x now) was going to suffer the same fate, and cause stagnation in the Ruby community.

  But now it’s out, and the performance number show it still lagging behind Python a bit, but significantly faster than Ruby 1.8. It also apparently has native threads, which Ruby 1.8 did not.

  I like Ruby quite a lot as a language. But I’m finding it harder to buy into its culture and its future. One major example is the documentation (or lack thereof) that accompanies this release. Being that this is a major release with major improvements and backward-incompatible changes, you would expect a great deal of information about what has changed. But here is what the “NEWS” file (their release notes) looks like:

  NEWS

  This document is a list of user visible feature changes made between releases except for bug fixes.

  Note that each entry is kept so brief that no reason behind or reference information is supplied with. For a full list of changes with all sufficient information, see the ChangeLog file.

  Changes since the 1.8.7 release

  See doc/NEWS-1.8.7 for changes between 1.8.6 and 1.8.7.

  Compatibility issues

  • language core
  • New syntax and semantics
  • Block arguments are always local
  • New semantics for block arguments
  • defined? and local variables
  • Parser expects that your source code has only valid byte
    sequence in some character encoding. Use magic comments
    to tell the parser which encoding you use.
  • New semantics for constant definition in instance_eval
    or in module_eval.

  And so on, for pages and pages. This list is meaningless to anyone who isn’t already familiar with the changes that have been happening in Ruby 1.9.x. There’s simply no way to know what any of it is talking about. Now the top of the file claims that the ChangeLog has rationale and reference information, but take a look for yourself: it isn’t any better.

  Not to mention that there appears to be absolutely no documentation accompanying this release. No documentation about the language, no documentation about the libraries (it’s probably possible to generate some using rubydoc, but no pre-built version appears to be available anywhere), just none. The one document that’s included about writing extensions makes absolutely no mention of threads, despite the fact that Ruby now has threads (which presumably extension writers have to deal with somehow).

  And while one would like to think that it’s just a matter of time, my experience with Ruby libraries is that you come to expect very sparse and under-documented stuff like this.

  Like I said, this is disappointing to me, because Ruby is my favorite language of its kind. I’ve written a lot of Ruby. Hell, at Amazon I started what I called the “Ruby Revolution,” and poured tons of time and energy into it. But although Matz has designed a very nice language, the support structures around that language seem more and more amateurish the more I think about them.

  I mean, I’m just one guy, and Gazelle has approximately zero users at the moment, but I still write up descriptive release notes and have an extensive manual.

  But for a more fair comparison, look at Python 3000. Look at its list of what’s changed since Python 2.6, for which every changed references a more detailed “Python Enhancement Proposal” which gives rationale and yet further references to discussion. And look at its list of documentation: a tutorial, a language reference, a library reference, detailed information about extending and embedding, and more. It makes Ruby’s lack of documentation even more stark.

  To be fair, the Pickaxe book has always been Ruby’s unofficial manual, and it appears that the Ruby 1.9 version of the book is already in “beta”. I think I’ll buy a copy just so I can have some idea of what the heck is going on with Ruby 1.9

  But it’s still hard to shake the feeling that Python is more mature, and a safer bet.

  A bet for what you ask? I have another project (something impractically big and ambitious) kicking around in my head for which something like Ruby or Python is the right answer. And I’ve been trying to decide which way to go…

  Update: I did just think of one significant difference between Ruby 1.9.x and Python 3000. The difference has to do with character encoding. Python has taken an “everything is Unicode” approach to character encoding — it doesn’t support any other encodings it doesn’t support any other character sets internally, which means that round-trips from any encodings that are not injective onto Unicode are lossy (revised to speak more precisely, since many people took the wrong meaning from my original wording). Ruby on the other hand supports arbitrary encodings, for both Ruby source files and for data that Ruby programs deal with.

  This is one issue about which Ruby seems like the somewhat safer bet. “Everything is Unicode” seems fine to us westerners, but apparently isn’t not as favored by people from Japan. I can’t find a reference now, but the two biggest reasons seem to be that Japanese characters all get blown up to 2 or 3 bytes or something, and Han Unification which means that unless you get the font right, a Japanese character can get displayed as the corresponding Chinese character with the same meaning.

  But regardless of the reasons, putting all your eggs in one encoding basket (as Python has done) seems less future-proof than supporting arbitrary encodings, as Ruby 1.9.x does. +1 Ruby.

• 

  BeOS

  Posted: January 26th, 2009, 1:53am MST by josh

  Things I’d do if I had more time, entry #417:

  Find out why BeOS R5 doesn’t boot on qemu and fix it. It runs fine if you get it booted (or so Michael Crawford, from the link, claims), it just can’t boot off the CD!

  Why? BeOS is still the only desktop environment I’ve used that is responsive. By “responsive” I mean “has a GUI that doesn’t start getting sluggish or spinning a beach ball when it gets busy.” It’s a travesty that in 2009, you can still make almost any browser grind to a halt by simply visiting a 100MB file (haven’t tried Chrome, so maybe it’s the exception). The whole GUI freezes just because there’s a bunch of data getting downloaded and parsed!

  BeOS wasn’t like that. On circa-2000 hardware it was more responsive than any environment I’ve used before or since.

  It’s the one piece of evidence I have that GUIs don’t have to be these sluggish beasts.

  And I want to relive it.

• 

  Gazelle 0.4 released!

  Posted: January 21st, 2009, 12:45pm MST by josh

  I’m am very excited to announce the release of Gazelle 0.4! The most notable change in this release is that Gazelle can again handle whitespace. But there are many other changes that put Gazelle well on the path from being a toy to being a tool. See the ReleaseNotes for all the details.

  Next up for Gazelle 0.5: operator-precedence parsing and the ability to build parse trees. Following up on my earlier post about Bitcode and Protocol Buffers, I’ve wholeheartedly decided to go the Protocol Buffer route, not only for the bytecode itself, but also for parse trees and abstract syntax trees. More about this later.

Comments for Josh the Outspoken

• 

  Comment on C and C++ are CRAZY! by josh

  Posted: January 21st, 2009, 12:31pm MST by josh

  @Alex: Yes, if there’s a maximum nesting depth, you’ve moved from undecidable to merely exponential. But this is a good point.

  @orl: look at my blurb in the sidebar!

Josh

• 

  habes @ 2009-01-20T22:38:00

  Posted: January 20th, 2009, 11:40pm MST by Josh

  So here I was, watching the inauguration, getting distracted for a moment and not paying attention, when all of the sudden, this:
  
  
  
  I know I have a weird sense of humor, but when he said "when the red man can get ahead, man" (with the little pointy finger) I bust up laughing, uncontrollably, for a good 30 seconds.

2 Star

• 

  C and C++ are CRAZY!

  Posted: January 20th, 2009, 9:54pm MST by josh

  I’ve learned a lot of crazy things about C and C++ in the last few years, as far as parsing goes. The one that’s always blown me away the most is that parsing C++ is undecidable: you can’t properly parse C++ without doing template instantiation, but template instantiation is turing-complete.

  But every time I think I’ve gotten to the point where C and C++ can’t faze me anymore, I find something new. Like this, from the Wikipedia article about operator precedence in C and C++:

  The binding of operators in C and C++ is specified (in the corresponding Standards) by a factored language grammar, rather than a precedence table. This creates some subtle conflicts. For example, in C, the syntax for a conditional expression is:

  logical-OR-expression ? expression :
  conditional-expression

  while in C++ it is:

  logical-or-expression ? expression :
  assignment-expression

  Hence, the expression:

  e = a ? b : c = d

  is parsed differently in the two languages. In C, this expression is parsed as:

  e = ((a ? b : c) = d)

  which is a semantic error, since the result of a conditional-expression is not an lvalue. In C++, it is parsed as:

  e = (a ? b : (c = d))

  which is a valid expression.

  WHAT?? I had to try this out and determine whether it was true or some crazy Wikipedia anonymous editor who was trying to drive me mad. So I wrote the simple test program:

  int main() {
    int e = 1, a = 2, b = 3, c = 4, d = 5;
    e = a ? b : c = d;
    return e;
  } 

  …and attempted to compile it first with gcc as a .c, then with g++ as a .cc, and sure enough:

  $ gcc -o /tmp/test /tmp/test.c
  /tmp/test.c: In function 'main':
  /tmp/test.c:4: error: lvalue required as left operand of assignment
  /tmp/test.c:4: error: expected ';' before 'return'
  $ g++ -o /tmp/test /tmp/test.cc
  $

  The world is insane. Luckily Gazelle will be the sword in your right hand, your weapon against a world that conspires against your sanity.

  Incidentally, it’s more and more clear that C++ is not a superset of C. Though it’s true enough that most people using the language don’t have to care, for language implementors the differences are significant.

• 

  The joy of cross-platform development

  Posted: January 18th, 2009, 12:40am MST by josh

  Only when you develop cross-platform do you get the joy of using both the best profiler ever and the best memory debugger ever.

• 

  Gazelle *not* in the browser

  Posted: January 15th, 2009, 10:55am MST by josh

  Scratch what I said the other day. Delivering a Gazelle IDE as a web application was this great attempt-to-be-forward-thinking dream that I clung to for a while. But yesterday in the wake of the news that Qt is going LGPL I gave it another look. And I have to say, the debate is over, the Gazelle IDE will be a standalone, cross-platform application written using Qt.

  Why? Because it’s the answer to all the problems I posed before (of which there were many):

  • The Gazelle compiler (wrtten in Lua) can run right there in-process, because the IDE can link in the Lua interpreter.
  • The Gazelle runtime (written in C) can be linked in and run right there in-process, and be way faster than a JavaScript implementation would have been.
  • Graphviz (written in C) can be linked in and run right there in-process.

  It also answers several other problems I hadn’t even explicitly posed.

  • Web applications don’t have access to the local filesystem. Desktop applications naturally do.
  • Web applications are limited by the performance of JavaScript (a high-level, garbage-collected language). C++ applications have better performance (and I plan for the Gazelle IDE to have a lot of graphics going on).
  • Qt has a really awesome support for, well, pretty much everything. Creating scene graphs that support hover, onClick, drag&drop, good drawing, animation, everything I was thinking about seems to be well-supported.

  I’m still trying to be sure that Qt applications feel sufficiently “native” on Windows and Mac. But unless that’s a big disaster, Qt looks like the best path to my goals.

Comments for Josh the Outspoken

• 

  Comment on LLVM Bitcode vs. Protocol Buffers by josh

  Posted: January 13th, 2009, 12:17am MST by josh

  @Chris K: yes, the fact that all values are tagged with a key in protocol buffers does give it nice forwards and backwards compatibility. It’s also true that if you’re using repeated fields as an array you’ll pay 1 byte per array element, which could be as bad as 100% overhead (if your array is bytes) or as low as 12% overhead (if your array is int64s).

  @simon: I want to stay 100% C so that the binaries stay as small as possible (currently 20k compiled) and impose as few requirements on the host platform as humanly possible. You can call C from anything (like even Objective C or LLVM Assembly Language). To me staying 100% C is a no-holds-barred way to be as useful as possible in as many weird situations as possible.

  @Dave: Cool, though my intention is to write it in such a way that there is no code generation, so that it can be used by bindings to higher-level languages like Perl, Python, Ruby, etc. So my intended design differs a little from the existing C implementation.

  @Eric: thanks man. I had fun at Amazon and definitely remember coming across your name in association with good things!

2 Star

• 

  Gazelle in the browser

  Posted: January 12th, 2009, 8:35am MST by josh

  While I’m on a roll with these blog entries, I thought I’d share just one more secret that’s been kicking around in my head for a while. I desperately want to see a Gazelle development environment that runs in your web browser.

  I first had this idea when I visited the excellent regular expression reanimator. It’s this beautiful little visualization that runs in your browser and shows you how a DFA transitions in response to text. And all you have to do to use it is click that little link!

  My dream is that you can develop your grammars interactively. You type rules and as you type you see little graphs build themselves up, state by state. You add a kleene star and you see the extra transitions add themselves to the existing graph. You put some sample text in another textarea and watch it start syntax-highlighting itself as you add the rules to properly recognize its structure. Or you can develop your own syntax highlighting color schemes by typing syntax highlighting rules and again seeing them incrementally take effect on a block of sample text.

  None of these ideas are brand-new. ANTLR of course has ANTLRWorks, which is an IDE for developing ANTLR grammars. But I feel that having this on the web would really lower the barrier to entry and make it accessible to more people. And despite how people poo-poo JavaScript and HTML, the web is not such a bad platform these days — especially now that SVG support is getting really good. SVG is the perfect tool for drawing graphs, styling the nodes in various ways, and having them do useful things when you hover/click on them.

  So anyway, I really want this. But the hurdles to making this happen are great!

  • Gazelle’s compiler is written in Lua. No real way to run Lua in a browser right now. Possible options for doing this in the future: a Lua -> JavaScript compiler, a Lua VM written in JavaScript, porting the Gazelle compiler to JavaScript, running the Lua interpreter inside NativeClent, and running the Lua interpreter inside Alchemy.
  • Gazelle’s runtime is written in C. Possible options: port the runtime to JavaScript, run it inside Alchemy, or run it inside NativeClient.
  • The Graphviz graph layout package is also written in C. Possible options are the same as the Gazelle runtime. I was seriously considering porting just the layout algorithms to JavaScript and had even started the port, but have recently been realizing how CPU-intensive these algorithms are even in C. In JavaScript they could only be slower. With Alchemy they would be slower than pure C, though it’s hard to say how much. With NativeClient they would run at native speed.

  So it pretty much looks like I’m stuck waiting for either Alchemy or NativeClient to be prime-time. While I could always run all this software on the server and AJAX the results in constantly, I don’t think that would provide a smooth enough user experience (not to mention the load it would put on my server — these algorithms are kind of expensive).

  As far as Alchemy vs. NativeClient: Alchemy will be slower (2-10x according to them) since it compiles your C/C++ to the Flash VM instead of to machine code, and it will require the Flash plugin. NativeClient will run at roughly native speeds, but will require a plugin download (most people will have flash already) and one that has potentially scary security implications if the NativeClient guys made any mistakes.

  Time to play with Alchemy and see if I can get it to work! And hope that NativeClient makes a lot of progress in no time!

• 

  Playing with LLVM

  Posted: January 12th, 2009, 1:15am MST by josh

  For no reason in particular I decided to dig into LLVM today. I decided to try out its assembly language by writing a line count program in it (I chose this problem since I had previously written an optimized x86 version using SSE). This was of course significantly trickier than I initially expected and took me several hours to figure out.

  SSA took some getting used to. I understood the basic idea before but had never worked with it. The surprising thing is that you don’t get registers, which means that to do something as simple as the “i++” of a for loop you have to:

    %current_i_val = load i32* %i
    %new_i_val = add i32 %current_i_val, 1
    store i32 %new_i_val, i32* %i

  In this example, “%i” is the address of a stack variable where “i” lives. I have to load the current value, increment it, and store it again.

  This load/modify/store business made me uncomfortable because it felt really inefficient. You just have to trust that when LLVM does register allocation that it’s smart enough to know that it doesn’t actually have to do the load/store each time.

  I was also surprised that LLVM assembly language is more strict that real assembly languages about the structure of each function. Each function has a series of “code blocks” and each code block must begin with a label and end with a “termination instruction.” As an example, here’s a function definition and the first two blocks in that function:

  ; Returns the number of newlines found in a buffer.
  define i32 @count_newlines(i8* %buffer, i32 %bufsize) {
    ; Local variables.
    %i = alloca i32
    %num_lines = alloca i32
  
    store i32 0, i32* %i           ; Initialize to zero.
    store i32 0, i32* %num_lines   ; Initialize to zero.
    br label %loop  ; can't just fall through to %loop
  
  loop:
    %i_val = load i32* %i
    %is_done = icmp uge i32 %i_val, %bufsize
    br i1 %is_done, label %done, label %continue_loop

  So you can’t just put labels anywhere willy-nilly, you only get one label at the beginning of the block. The termination instructions are mostly branches of various sorts. Basically this means that you can’t just “fall through” to the next label without branching — if you want to proceed to the next block you have to explicitly end your current block by branching to the next one. So in this sense the order of the blocks as you write them in the file is insignificant — the only significance is the first one, which is automatically run when you enter the function.

  Once you write your LLVM assembly language, you can assemble it with llvm-as, and then either run it with “lli” (which will JIT+run it) or compile it to x86 assembly with “llc” and then assemble it with gcc.

  $ llvm-as wc.ll
  $ lli wc.bc 
  638818
  $ llc wc.bc
  $ gcc -o wc wc.s
  $ ./wc 
  638818

• 

  LLVM Bitcode vs. Protocol Buffers

  Posted: January 11th, 2009, 11:40pm MST by josh

  In a comment to a previous entry, Emmanuel Castro asks:

  You chose the LLVM bitcode format for Gazelle instead of Google Protocol Buffer.

  Is there any reason, or was it just because you made the choice before Protocol Buffer was available.

  Protocol Buffer seems to have a better language support (C , Java, Python).

  This is a good question. The easy answer is that I chose LLVM Bitcode before Protocol Buffers were available. But the harder questions are “would I make the same choice today?” and “should I port Gazelle at some point to use Protocol Buffers (or something else) instead?”

  Being quite familiar with both formats (I’ve implemented both), I thought I should take a moment to compare/contrast the two. These two formats target a really similar use case (compact, binary encoding of arbitrary data) but have some significant differences.

  Data Definition/Schema:

  With protocol buffers, you lay out your schema in a .proto file that looks something like this:

  message Person {
    required string name = 1;
    required int32 id = 2;
    optional string email = 3;
  
    enum PhoneType {
      MOBILE = 0;
      HOME = 1;
      WORK = 2;
    }
  
    message PhoneNumber {
      required string number = 1;
      optional PhoneType type = 2 [default = HOME];
    }
  
    repeated PhoneNumber phone = 4;
  }

  Having a formal schema means that generic protobuf tools can generate code with nice classes/structures that mirror the schema. Generic tools can also pretty-print Protocol Buffers given the .proto file.

  With Bitcode, on the other hand, there is no formal schema. Schemas are informally specified in some mixture of documentation (here’s LLVM’s and here is Gazelle’s) and code. This means that generic Bitcode tools have much less information to go on for things like code generation or pretty-printing.

  The lack of a schema system isn’t inherent to Bitcode, and one could easily be added. But given the status quo of it not having one, Protocol Buffers are the clear winner here.

  Space efficiency

  Both Protocol Buffers and Bitcode are quite concerned with space efficiency, but Bitcode is a bit more extreme about it. Specifically:

  1. Bitcode files are considered a stream of bits rather than a stream of bytes. Bitcode is the absolute only format I have ever encountered that does this. This leads to greater space efficiency (since you can encode a boolean value using only 1 bit, for example), but is more expensive to encode/decode since you have to be shifting and masking a lot. I don’t have any data about how significant this is.
  2. Bitcode allows you to define “abbreviations”, which allow you to define bit-by-bit what your records will look like. You can define an abbreviation that says: “a 1-bit integer (a boolean) followed by a five-bit integer followed by a variable-bit-rate integer where each chunk is four bits.” Using this facility you can optimize your records to use exactly as many bits as they need, with none wasted! But it takes a lot of work and foresight on the application developer’s part to get the most of this.

  So the general idea is: Bitcode is smaller, but probably takes more CPU and more work on the application developer’s part. But unfortunately I have no measurements about how much smaller or how much more CPU or how much more work.

  Data Model

  The Protocol Buffer data model is: each protocol buffer is a series of key/value pairs. Any of the values can itself be a protocol buffer, which provides hierarchy. The values can be any of 10 integer types, float, double, boolean, UTF-8 string, or raw bytes. Any of the keys can repeat if the .proto file says they can.

  person {
    name: "Harry"
    age: 42
    likes_color: "blue"
    likes_color: "green"
    vehicle: {
      make: "Toyota"
      model: "Prius"
    }
  }

  The Bitcode data model is: files are a series of data records, and data records can be nested inside blocks to provide hierarchy. Each data record has a code and a series of integers:

  [DataRecord code=5, 3, 9]
  (this next record might be ASCII values for "Hello",
   but there's no string type so we don't know)
  [DataRecord code=8, 72, 101, 108, 108, 111]
  [block id=9]
    [DataRecord code=4, 6, 5]
    [block id=10]
      [DataRecord code=8, 8, 1]
    [/block]
  [/block]

  Clearly there is less semantic information at the Bitcode level, which means that generic Bitcode tools can’t show you as much. Most notably, Bitcode has no notion of a string. And since there are no keys to the records in Bitcode, everything is dictated by the order of the records in the file and the order of the integers within the records. This means that Bitcode will be more space-efficient if all of your records have the same set of fields. On the other hand, if your records have a large number of possibly optional fields but each actual record uses only a few, then Protocol Buffers will be more space efficient.

  Both formats are capable of seeking over sub-records/blocks that you aren’t interested in parsing.

  Adoption/support

  I haven’t been following the spread of Protocol Buffers too closely (which is a shame since I keep meaning to finish my C implementation), but it’s almost certainly more widely adopted than Bitcode, which has never really been marketed at anything other than LLVM. This is definitely a concern, because I ended up having to implement Bitcode myself. This ended up being a significant diversion for me — it took me many weeks and a lot of frustration, and despite being only about 1000 lines of code, it was subtle and difficult to get right. I would have much rather used an existing library, but LLVM’s Bitcode library was C++ and I wanted to stay 100% C.

  Conclusion

  So on every count except space efficiency Protocol Buffers seem to be a win. If I was doing it again I might choose Protocol Buffers instead. I’d still like to see the degree to which Bitcode is more space-efficient, because space-efficiency is quite important to me.

  I still have a half-implemented C protocol buffer library sitting around, and hope that someday I’ll get around to finishing it. Once I have that, I may consider porting Gazelle’s bytecode to use protocol buffers instead.

• 

  The importance of being earnest

  Posted: January 11th, 2009, 6:36pm MST by josh

  While I’m at it, I wanted to take a moment to recognize that I’ve too frequently made claims that are unsupported or premature. The worst example of this was when I claimed to have found an algorithm that computes LL(k) for all k (this is undecidable — my algorithm turned out to be a heuristic). In other cases, what I’ve written is technically true but misleading: for example, in claiming that Gazelle is “more powerful” than ANTLR, this was not taking into account many features that ANTLR has that Gazelle currently does not, like semantic and syntactic predicates.

  I’m not proud of this. I’d like to take the opportunity to make a commitment to putting those days behind me. I am extremely proud of Gazelle and what I think it brings to the table, and I’ve tried to consistently acknowledge my debts to prior work, especially ANTLR. Indeed, in the Gazelle manual I say:

  Gazelle’s algorithm takes a great deal of inspiration from ANTLR, the LL(*) parser generator written by Terence Parr. While Gazelle seeks to augment the theory that Terence developed, the foundations of Gazelle are strongly based in ANTLR’s achievements. Like ANTLR, Gazelle is a top-down parser that models its lookahead as possibly-cyclic state machines. Gazelle’s algorithm for generating this lookahead is based on ANTLR’s algorithm.

  Still, I clearly need to be much more careful not to jump to conclusions, and be less susceptible to bravado. If Gazelle is as good as I think it is, its capabilities should speak for themselves.

• 

  Looking to 0.4

  Posted: January 11th, 2009, 6:11pm MST by josh

  Given that whitespace has been relatively painless to implement, I think I’ll tackle a number of smaller things I’ve been meaning to do before releasing 0.4. Like whitespace-handling, these are things that prevent Gazelle from being more than a toy until they’re addressed:

  1. when Gazelle encounters a parse error, it should report it to the API in a sane way instead of doing assert(false) or just printing a message to stderr and aborting
  2. Gazelle should provide line and column information to the API (this is more complicated than it might sound — read the Wikipedia article on “newline” and the Unicode recommendations on Newline for some of the complications)
  3. Gazelle’s C API should be namespaced (with gzl_ or somesuch on all the identifiers) instead of polluting the global namespace with functions called things like “parse”
  4. a “make install” target, so that you can just type “gzlc” for the compiler instead of “. lua_path; ./compiler/gzlc”

  These sound like a good set of goals for a 0.4 release. I may drop a few or think of a few others.

• 

  Gazelle handling whitespace/comments

  Posted: January 11th, 2009, 6:10pm MST by josh

  I’m digging back into Gazelle after a several-month dormancy. If you happen to be someone who syndicates my commits, either directly or via your GitHub news feed (don’t laugh — I have 18 “watchers” on GitHub!) you’ll notice a flurry of commits from the last few days. I’ve been working on whitespace handling, and progress is refreshingly brisk: I have things pretty well working after only a few days of work.

  Whitespace handling was for a long time the biggest thing preventing Gazelle from being actually useful. I had a whitespace-handling mechanism back in 0.1, but had to rip it out in 0.2 because it was naive and premature. It’s back now, and while it looks mostly the same from the user’s perspective, it’s totally different under the hood.

  Here’s the current picture of a JSON grammar, using the new whitespace facility:

  // Grammar for JSON, as defined at json.org.
  
  @start object;
  
  object   -> "{" (string ":" value) *(,) "}";
  array    -> "[" value *(,)              "]";
  
  str_frag -> .chars=/[^\\"]+/ |
              .unicode_char=/\\u ([0-9A-Fa-f]{4})/ |
              .backslash_char=/\\[ntbr"\/\\]/;
  string   -> '"' str_frag* '"';
  
  number   -> .sign="-"?
              .integer=/ 0 | ([1-9][0-9]*) /
              .decimal=/ \. [0-9]+ /?
              .exponent=/ [eE] [+-]? [0-9]+ /? ;
  
  value    -> string | number | "true" | "false" | "null" | object | array;
  
  whitespace -> .whitespace=/[\r\n\s\t]+/;
  
  @allow whitespace object ... number, string;

  It’s the @allow statement at the end that triggers the whitespace facility (which are more generally called “subparsers”). That statement means that any time the parser is inside an object (eg. all the time), but not inside a number or a string, whitespace can appear anywhere. More specifically, for all states in such rules, the @allow statement defines a “whitespace” transition back to the same state.

  As a result, the rule graphs start looking like this:

  

  All the whitespace transitions are a little bit annoying to look at, and I’ll definitely have to tweak the visualization to show them in a nicer way. But this gives you an idea for what’s going on.

  What’s nice about this scheme is that you get to specify the whitespace rules in a simple way (”whitespace is allowed everywhere except in these certain rules”), but then the whitespace becomes a part of the same grammar data structure and is analyzed by the same algorithms as everything else.

  It’s worth mentioning that this design is significantly different than the traditional design, which is to have a separate lexer simply discard whitespace and comments before they ever hits the parser. The lovely thing about doing it my way is that the whitespace becomes a part of the parse tree (if you want it to — you’ll be able to turn this off). This means:

  1. round-trips from text -> parse tree -> text are lossless
  2. therefore programs can operate on the parse tree to do whitespace-preserving transformations
  3. programs can also analyze the parse tree with regard to how it follows style rules
  4. programs like doxygen that consider comments and whitespace significant could operate on a Gazelle parse tree
• 

  Gazelle v0.3

  Posted: November 30th, 2008, 1:40pm MST by josh

  Things have been pretty quiet here lately. All I can say about that is “life happens!” But I’m very pleased to announce that I am ready to release Gazelle 0.3! The download link is on the Gazelle homepage.

  See the Release Notes for what has improved since the last release. The gist of is it that the compiler is a lot more robust: it catches more error cases and will never hang due to errors in the input. There is also explicit ambiguity resolution, which makes it possible to resolve the ambiguous “if then else” case explicitly. And this is all accompanied by a large test suite, since this grammar analysis is difficult and subtle.

  The biggest remaining problem that keeps Gazelle from being practical is still the lack of whitespace handling. And this is exactly what the next release will fix.