105363 items (97572 unread) in 19 feeds
Friends
(1021 unread)
2 Star
(84 unread)
John Carrino
(12 unread)
Comments for Josh the Outspoken
(296 unread)
Planet Matt
(595 unread)
Build
(68091 unread)
MAKE Magazine
(20292 unread)
Instructables.com
(35006 unread)
Hack A Day
(5017 unread)
Toolmonger
(7776 unread)
Heads
(716 unread)
Exploration Through Example
Stevey's Blog Rants
(34 unread)
Gibson Blog
(239 unread)
Adventures in Bloggery
(123 unread)
News
(27537 unread)
Ruby Inside
(922 unread)
fun
(207 unread)
Templar, Arizona
(207 unread)
Hi,
“Space-efficiency in protocol buffers is horrible for repeated-fields. Thus arrays are a problem and the only work around is store a binary blob.”
Note that protocol buffers now supports a packed representation for repeated fields of primitive types:
Ismael
Oops! I confused you with the other person writing a novel parsing tool in a very-high-level language that I’m watching on Github, Nathan Sobo, whose parsing system is Treetop (in Ruby).
Don't forget the IBM XL C compiler too
It's based on a GCC frontend, IIRC, so porting should be easy. But it's worth adding to your list if you are truly looking for a complete set.
I've so far managed to avoid using the PGI compilers personally, but I've heard that they are (were?) sufficiently quirky to provide a decent test of your portability.
If you were really paranoid you could aim for C89-compliance with a few very common C99 features (this is what we do in MPICH2). This mostly shouldn't matter though unless you want to run on machines that are just old or very exotic at this point. Older Sun compilers in particular can be a nightmare.
Also, even if you do manage to make your software truly C89 or C99 compliant, there's still a good chance that you will have to work around some compiler quirks somewhere using autoconf or something similar in your build system (unless your project is sufficiently simple and high-level). Just something to keep in mind.
-Dave
I recently came across perfect hashing (see [burtleburtle.net]). It’s not at all clear to me that this is necessarily a speed win versus the other hash table strategies you list, but it does avoid the issue of collisions entirely. I suspect the tradeoff is that finding a (possibly minimal) perfect hashing function for a given set of keys might be be tricky…
The pass Eugene mentioned is called ‘mem2reg’.
Actually using this method saves a lot of efforts because it’s not trivial to find where to insert these phi nodes.
@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?
Oh hey, I just noticed you’re the guy that’s writing Gazelle. Cool! My friend Matthew O’Connor told me about you when he paired with you when applying to work at Pivotal, and I’m watching Gazelle on Github.
It’s actually pretty easy to use GCC and dlopen as your JIT; see [lists.canonical.org] for a Python example. It does build a C extension for each arithmetic expression, but that happens automatically and transparently, and it only takes about a second on the really old machine I was using then. With a little more work (making a version of Python.h that doesn’t depend on the system header files, and provides just the definitions you need for the generated extensions, you could probably get it down below 10ms on a modern machine.
But if you’re calling this hash lookup from Python anyway, it’s silly to worry about any of the micro-efficiencies you’re talking about. Just use Python’s dict; you might be able to do epsilon better, but that will be swallowed up by the bytecode dispatch overhead and function call and return (on the order of 30-300 instructions per bytecode).
BTW, you left out a slight variation of linear probing: you make each hash bucket big enough to contain more than one item. Of course this doesn’t save you from having to deal with the case for where the entire hash bucket fills up, when you either need to use one of the other strategies to figure out where the next item goes, or expand the hash table.
@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.
Hey, uh, if lookup speed really trumps *all*, then I speculate that you should probably compile each set of keys into a machine-code subroutine expressing a balanced binary tree. The routine will contain N-1 compare-and-conditional-jump pairs for N keys, plus N key comparisons if it’s important to return an error when the key isn’t actually in the table. An immediate-compare-and-conditional-jump is 7 bytes on the x86, so about 9 of them fit into a 64-byte L1 cache line, and you execute 2 lg(N) + 4 or so instructions to look up one of N keys. (Possibly you’ll occasionally have an additional memory access to fetch another four bytes of the key, but I’m assuming not.) So if you have, say, 100 keys, you execute 16 or 18 instructions (and perform no memory accesses) to look one up and return the associated value.
A really straightforward way to implement this strategy (for integer keys) is to generate a C file with a switch statement in it, use GCC to compile it to a shared library, and then dlopen the shared library in order to call into it. (Alternatively you could use LLVM or GNU Lightning.)
The nearest hashing equivalent is “perfect hashing”, where you search for a hash function that hashes each key into a distinct bucket in a minimal-size hash table. gperf is a widely-available perfect-hash generator. I haven’t measured and so I don’t know which one of these is faster.
I’m curious, what made you decide to write a streaming protobuf implementation, versus sending a stream of protobufs embedded in another format?