The Fugue

This monster keeps popping up and my rant switch has been flipped.

Google Research Blog has a post about how "nearly all binary searches and mergesorts are broken" because this can overflow:

int mid = (low + high) / 2;

Boy, have I got news for you. Computers are finite. If you put big enough numbers in, you will have overflow problems, period. Binary search and mergesort are no more broken than a+b or x*y or any other arithmetic operation in every program you have ever written.

All we have here is the need to recognize the limits of your computation. If you need to support big numbers, you can then deal with overflow. That might mean using 64-bit integers, or if you have just a little bit of overflow you can use some creative arithmetic and/or casting. The fun is endless, take it from a DSP programmer (overflow is an omnipresent concern in DSP programming).

So no, everybody's binary search and merge sort implementations are not broken. The algorithm is certainly not broken; theoretical discussion on algorithms is purposefully distanced from implementation concerns like how many bits you're working with, unless that happens to be the theoretical focus. So the textbooks and pseudocode are also not broken. The only thing that's broken is that some of us have forgotten that computers have limits, and we're surprised when all of a sudden the computer does what it was designed to do when the limits are reached.

It's official! I am one of the recipients of Google's Summer of Code grant. That means I get paid $4500 to improve Ardour according to my proposal over the summer. Combined with the GAANN fellowship I've received this means I can spend most of the time this summer writing code for Ardour and studying for quals.

My proposal was to modify Ardour so that plugins can be applied to regions instead of just tracks, both for realtime processing and bounced to disk. This is a feature I have sorely missed in Ardour, as it is an important tool for making electronic music and musique concrete efficiently. The other half is to add undo/redo serialization of the current undo system to allow unlimited undo across program instances.

I'm really excited for this opportunity. It will be my first serious involvement with a big and important open source project as a developer. I've often told myself I needed to get involved with one, and now I have an ideal opportunity to do just that.

There are two other SoC recipients for Ardour. One is adding basic MIDI recording and playback, and the other is doing a Windows port.

Ladies and Gentlemen, I bring you ruby/audio 0.1.1. This is primarily a bugfix release, but you fill find a few documentation and feature enhancements as well. Enjoy!

I don't know whether to be jumping for joy or throwing things across the room for living without this knowledge for so long.

~/.irbrc is a really nifty file. I should take the time to explore its possibilities sometime. But where does one find out the irb tricks like that one, and this one? If you know please enlighten us!

Here's my current ~/.irbrc:

IRB.conf[:AUTO_INDENT]=true

# ri
def ri arg 
  puts `ri #{arg}` 
end 

class Module 
  def ri(meth=nil) 
    if meth 
      if instance_methods(false).include? meth.to_s 
    puts `ri #{self}##{meth}` 
      end 
    else 
      puts `ri #{self}` 
    end 
  end 
end

# vim: filetype=ruby

I had my lunch handed to me today because some C DSP code I had written was wrong:

/* M is the size of the buffer, 
 * w is the base pointer, 
 * p is the pointer into the buffer */
void wrap(short M, short *w, short **p)
{
if (*p < w || *p >= (w + M))
    *p = w + (*p - w) % M;
}

What I did not realize is that the % operator in C does not wrap negative numbers into the positive range like you would expect if you were a mathemtician. i.e. -7 % 8 == -7 in C, where in mathematics -7 = 1 mod 8.

I can hear you now: "Didn't you test it, you fool?" Well, yes, I tested the algorithm in Ruby, where mathematics hold true:

rb(main):001:0> -7 % 8
=> 1

How was I to know the C version was braindead?

So which is right? Well you can probably guess my bias by now. But inquiring minds want to know, and no other type reads this blog so I did some research.

First, the mathematics. Wolfram has a dizzying explanation. Search for modular arithmetic for any number of treatments of the subject. Too lazy for that? Fine, look at your watch. If it's 10:05 and you go back in time 10 minutes, is it -5 past 10? Arguably so ("5 to"), but most people would agree that it's actually 9:55 by canon.

Now for the C argument. The 1999 ISO C Standard says:

If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.

So my compiler is fine. It's C that's broken. Before C99 the use of % on negative numbers was IMPLEMENTATION DEPENDENT, which if you know anything about C history means they didn't think it through well enough, or they made a decision based on speed or ease of implementation. The C99 definition was probably chosen either for ease of implementation or for the most common case. Not exactly good enough to convince me.

Naturally, there's no going back now, so if you find yourself possibly needing to do modular arithmetic on negative numbers in C, be sure to add again if negative:

/* M is the size of the buffer, 
 * w is the base pointer, 
 * p is the pointer into the buffer */
void wrap(short M, short *w, short **p)
{
if (*p < w || *p >= (w + M))
    *p = w + (*p - w) % M;

if (*p - w < 0)
    *p += M;
}

Here's a coherent post to the gcc-help list about the subject. Now, I don't want to hear anyone saying that % is the modulus operator from now on. It's the remainder operator.

I am in the process of migrating my blog to Typo. Blosxom has served me well, but I think it's time I joined the ranks of cool blogs and allowed people to comment, trackback, etc. Blosxom can do all that, but it's not very much fun.

Blosxom's strength is its simplicity. When I wanted a simple blog, it was perfect.

Now, getting typo to work was not a walk in the park. I'll walk you through what I had to do.

First, you have to get typo and install it. I hear rumors that version 4 release is imminent, so I grabbed the svn version. Next, make a database and set up config/database.yml. Now you can run script/server -e production and point your browser at http://localhost:3000/ and give it a whirl.

I tried the RSS and atom converters in db/converters but I wasn't satisfied with the results. So I wrote a blosxom converter, which I will contribute. If you can't find it feel free to contact me.

The hard part was getting typo to run under a subdirectory in my mixed apache/lighttpd setup. All fugal.net sites are running through Apache. My rails apps run through lighttpd, with apache's mod_proxy. So, you have to configure apache, lighttpd, and rails each in turn.

Apache Configuration

    ProxyPass               /typo http://127.0.0.1:81/typo
    ProxyPassReverse        /typo http://127.0.0.1:81/typo
    <Proxy *>
        Order allow,deny
        Allow from all
    </Proxy>

Lighttpd Configuration

The normal lighttpd stuff, and then:

$HTTP["url"] =~ "^/typo(/|$)" {
    server.indexfiles = ("dispatch.fcgi")
    server.document-root = "/srv/www/typo/public/"
    server.error-handler-404 = "/dispatch.fcgi"
    server.errorlog = "/srv/www/typo/log/error.log"
    accesslog.filename = "/srv/www/typo/log/access.log"
    fastcgi.server = ( ".fcgi" => (
        "typo" => ( "min-procs" => 1, "max-procs" => 1,
            "socket" => "/tmp/typo.fcgi.socket",
            "bin-path" => "/srv/www/typo/public/dispatch.fcgi",
            "bin-environment" => ( "RAILS_ENV" => "production" ),
            "idle-timeout" => 120
            )
        )
    )
}

You don't need strip-request-uri, because we'll take care of the typo/ prefix in rails.

Rails Config

Add this to config/environment.rb:

    ActionController::AbstractRequest.relative_url_root = "/typo"

Finally, and this was the real stink, you have to help lighttpd find files in public/. Lighttpd gets a request for http://hans.fugal.net/typo/foo.html which is a static file in public/, and so it looks in the document root to find /typo/foo.html, which means it looks for /srv/www/typo/public/typo/foo.html, which doesn't exist. This is easy to fix:

    cd /srv/www/typo/public
    ln -s . typo

et voilá! You should be up and running.

For more reading see http://znark.com/blog/articles/2005/12/11/got-typo-working and http://blog.lighttpd.net/articles/2005/11/23/lighttpd-1-4-8-and-multiple-rails-apps.

I quickly ran some unscientific bench^Wlogmarks (3 or 4 samples after stabilization at the CLI with my friend time) for camping vs. just erb/cgi vs. just markaby vs. my current blosxom blog (with 10 entries):

time ruby -rrubygems -e "require 'camping'"  # about 0.5 seconds
time ruby -rcgi -rerb -e ""                  # about 0.05 seconds
time ruby -rrubygems -e "require 'markaby'"  # about 0.2 seconds
time blosxom.cgi >/dev/null                  # just under 0.3 sec
time fugue.rb >/dev/null                     # just over 1 sec

The blosxom and fugue runs dealt with the same 10 posts and produce almost to the angle-bracket the same HTML. It looks like to me that I should think about doing my super-simple blog without the overhead of a framework, even one as small as camping, and go with straight markaby or erb for the template.

Camping does fine once it's loaded, but I don't really want 20 megabytes of virtual memory being wasted just so the 5 people out there reading my blog can get it in less than two seconds. As it is I'm trying to find ways to prune rails/apache/etc. memory usage. I think I have an idea, too.

So apparently a lot of this time is startup time, but a lot of the time this startup stuff is the same over and over. I started thinking about one master process that somehow subthreads the rails/camping sites, but that gets messy and who knows when a global variable or some other rogue will really mess things up. Not to mention environment. But wait, I don't care about memory usage when it's actually doing something - it's the perpetual waste of RAM that I'm concerned about. Why don't I have N bootstrap processes that have done the equivalent of require 'rails' or require 'camping' and are ready to load the appropriate ruby script on-demand and then die gracefully after the page is served. I get precise control over how many processes are hanging around, the wasted RAM between requests is much less per lingering process than with a full-blown fastcgi app, and you get fast service.

Well, there's at least one problem: most page loads will have a bunch of requests all at once, so maybe it would be better to have the bootstrap process load up a fastcgi process that can serve the rest of the requests and die after a few seconds of idle time.

If you have thoughts on this scheme, let me know. Yeah, I know I don't have comments, so you'll have to do it the old-fashioned way. If my subconcious doesn't churn something up in the next few days/weeks I might just whip it up.

In usability and UI design theory there's this concept of affordance. We say the button affords clicking, or the metal plate on a door affords pushing. Well the latest Firefox .dmg for OS X (Firefox 1.5) strives to make the already dog-simple installation process (drag the .app into /Applications) even easier:

Doesn't that look great? It just begs you to drag it into the Applications folder. There's only one catch: that's not the Applications folder! That's a background image. It's completely worthless. It gums up your mind and prevents you from installing it on autopilot while you try to figure out why you can't just drag it onto that Applications folder.

In my case the confusion was exacerbated because I had recently come across a .dmg that used the same tactic, except they had a symlink to /Applications in there so it actually was dog-simple to install, instead of just looking that way.

10 points for style, -20 for stupidity.

With the announcement of the first Friday from the Pragmatic Programmers, which is Rapid GUI Development with QtRuby, I got really excited. I used QtRuby a little bit back when it was brand-spanking new, because I've used Qt more than once in the past (C++) and I think it is an excellent toolkit. I figured that this PDF book signalled that QtRuby was finally ready for prime time.

It is with great sadness that I report it is not so, at least not for me. It may well be solid enough for serious work. Since it is in Debian now, it may well be the easiest toolkit path on Debian-based Linux. It may have better documentation and a really cool PDF book from the Pragmatic Bookshelf. But it is nigh unto impossible to install on OS X. It claims to be able to, but the extremely complicated instructions fail to tell you what to do when this strange smoke thing fails to compile.

On the other hand, FxRuby is now much easier to get on OS X (and Linux) than it has been in the past. Install Fox (with DarwinPorts on OS X or apt-get on Debian), have rubygems (you do, don't you?), and type gem install fxruby. Nice. It's not native OS X, but it's installable. I managed to get some semblance of OS X nativity with Tk, but I seem to gravitate away from Tk for some reason. I haven't tried ruby/gnome2 yet on OS X. I hear good things about wxRuby, but I have found it also is impossible for mere mortals to install it on OS X.

If I write a GUI app, I want it to have minimal requirements of installation by users. Right now I'd be happy to rely on DarwinPorts/Fink and gems to do the heavy lifting, but asking users to go through an excruciating manual compilation process that fails inexplicably just won't cut it.

Ruby on Rails is really nifty. That's a huge understatement, but it's late and I don't have time to evangelize.

One nifty thing about rails with an un-nifty name is the has_and_belongs_to_many keyword. It is long and awkward, and it is also mentally awkward. For example:

class Recipe < ActionRecord::Base
  has_many :ingredients
  has_and_belongs_to_many :cookbooks
end

Since when did a recipe have a cookbook, or a cookbook belong to a recipe? No, sorry, this is a terrible name. I appreciate the desire to make it read in a natural language sort of way, but trying to english-ize complex relations like this is the sort of thing that gets you in trouble in AI classes and other places where relations are important. Like, say, relational databases. Anyone who has the ability to consciously create a many-to-many database table (as opposed to unconsciously cut-and-pasting one) will know what many_to_many means, and his brain will happily fill in the gaps to read out "Recipe has a many-to-many relationship with cookbooks."

I like that I have very few things in Rails to rant about, but I have never been known to hold back my rants. ;-)

Oh, I almost forgot the solution, which was the whole reason I decided to blog it! Thanks to Jamis for figuring out just what the best way to do this is. Append this to the end of config/environment.rb:

class ActionRecord::Base
  class << self
    alias :habtm :has_and_belongs_to_many
    alias :many_to_many :has_and_belongs_to_many
  end
end