hand|paper|lake

Been listening to a lot of Johnny Cash lately.

I suspect that by the end of the week my dog’ll have died, the truck will’ve up and broke and my server will break my heart.

Pass the whiskey and the ammunition.

…that revisiting it can be embarrassing.

So, I’m tasked with creating some detail views of some of the example graphs in the thesis, as the summary bits are rather tiny, and it’d be nice to do so. I have a browsing application that plots the graph and allows for some zooming and panning. It’s an OpenGL GLUT app, because it’s really easy to build this sort of bare-bones app, even though in this case I’m only doing a 2D orthographic projection.

Nevertheless, the panning had issues — the mouse wasn’t synched properly and pulling and pushing the image around was inconsistent. The zoom was similar and it didn’t work consistently between large and small graphs.

So, I thought about it a little bit, as I need a more precise tool now that I want to create these images. I discovered that the translation operation I was performing was using window units instead of viewport units. I felt like a tool. One doodle and one equation later and it works properly.

The zoom had the same solution, but in this case the thinking is different — I thought about the zoom as pushing the image 20px out on each side — that’s a reasonable unit (I’m not looking for continuous zoom), and mapped the pixel to viewport co-ordinates that way.

Partnering these subtle revisions with a revision of my regular cairo-based PNG renderer means that I have great anti-aliased zoomed-in versions of my graphs. Which is all good. But that I didn’t implement these really rather simple transformations correctly in the first place just has me shaking my head. Ah well.

I was looking at the Tufte-style LaTeX package and followed the discussion back to this link. The book is entirely remarkable. With no text aside from numbers, this book communicates LEGO-based engineering designs with symbols and arrows. Pulleys, differentials, train-drives, screw-drives, re-directing shafts, and so forth. The photographs are top-notch and the exposition clear and progressive. It’s also the sort of reference I’ve been looking for in terms of Technic LEGO. I’m not a terribly good engineer, but I can copy. This provides some boilerplate for a large number of useful mechanical ideas.

Impatience drives new features; this is always been true.

The graph drawing code is positively ancient now, especially some components of it. Nevertheless, there’s the occasional thing that needs to be done with it, and the modular design has enabled a lot of that with minimal extra work. For example, the crunching part of the software used a central configuration file. For multiple runs in parallel, this doesn’t work so well, so I’ve updated the configuration file loader to check the directory that holds the pre-processed files for a configuration file. If there is one, then it’s used. Otherwise, the default central config file is used — a backwards-compatible feature that doesn’t break anything.

One of the sticking points for doing some of this work has been that the pre-processor slows down dramatically for very large graphs. This is a serious problem — I really didn’t think the preprocessor should be spending a couple of hours crunching through a 150K node, 500K edge graph. While I didn’t do a lot of profiling, like a good programmer, what I did put in was a little bit of status output to indicate what stage of processing the file was at. I noticed initially that a huge chunk of time was spent just loading in the XML — a libxml call. I was using the DOM model calls, and it didn’t scale at all. So, knowing a little more about XML processing now than I did a couple of years ago, I wrote a GraphML loader that achieves the same goal using a SAX processor and cut the runtime by an order of magnitude.

This little trick left me occluding a bug in my graph generating scripts. GraphML files have two main element types — nodes and edges. Since my GraphML loaders only cared about edges, any errors in the nodes would be overlooked. My supervisor’s implementation, however, starts with the nodes, and so he noticed the error with my GraphML files.

The second optimization is a little harder to explain, and I’m not sure why it worked or was needed. What I had noticed was that the pairing-off process that happens in the Perl preprocessor to create the coarse graphs was dishing out pairs rather slowly for large graphs. At least, more slowly than I would have expected. The routine loops through the set of nodes that haven’t yet been paired off, selects one at random and then one of its neighbours, using a hash containing the edges of the graph. I altered this to be a fixed-length loop iterating through a Knuth-shuffled array of keys to the edge hash instead, and for some reason it works a helluva lot faster. Without detailed profiling, I don’t know if I’m wasting cycles or loop iterations somewhere or what, but the speedup is pretty dramatic.

…doesn’t add enough value.

I spent nearly 45 minutes trying to figure out why the second table using the supertabular module was busted. A more careful reading of the instructions included with the module indicate that several variables are set from the point of definition onwards, meaning, I suppose, that they need to be overwritten in the next table, otherwise they will be re-used. Sigh.

If I were to make the supertabular module better, I’d ensure that the variables for table header, footer, etc. would reset after the close of the tabular environment that it uses behind the scenes.

At the very least, however, I’m getting the document to look like what I need it to — grids of graphics look good and show up properly on the Figures list. A couple of instances where I had to mangle table-like floats and environments have been replaced using the subfig environment and show up more cleanly, even though the code is a bit more intense.

It’s almost getting to the point where I’m looking for more of a continuous build-like environment for the document, especially during the debugging runs.

Now that M$ is offering to share their Office file formats, it seems like documents of most sorts are really some sort of virtual file system.

Why not make it official and write a FUSE module to mount it? Not that it’d be useful, but it could be done, I s’pose. And practicality never stopped anyone anyways.

Seth Godin’s blog had a link to a great UK public service message. The point could not have been better made.

Well, it’s not much of a stretch, but after Shroom’s NaNoWrimo entry from 2006, I thought it was kind of neat. Check it out.

…or maybe a common folk tale…  

49%