Sambal

When I was looking for a C lower-bound algorithm — after I wound up writing it myself — I realized that there was an implementation in STL.

A Detour into STL

STL, in case your programming life is lived under a rock labeled “C#”, is an awesome set of template routines for C++, for having collections, iterating over them, applying functions, and generally making C++ achieve about a tenth of the power of a language like Lisp or perl.

I’m kidding. A little.

Anyway, the cool thing about STL is that it can achieve a lot of the power of a dynamic language by using templates in clever, innovative, and (critics say) scary and evil ways. For example, not taken at random, the concept of iterators exists in STL. An iterator is a sort of generalized pointer, where (at minimum) the operations ++ and * are defined on it. If the iterator is bidirectional, then the operation — is also defined. If the iterator is random-access, then the operations +(int) and -(int) are also defined. A bare pointer is an example of a random access iterator.

So fine, we’ve built up a formalism for describing pointers and things that act like pointers but are less useful. What’s the point? The point is, through the magic of templates, you can write code that takes advantage of the features of a random-access iterator but degrades gracefully to a weaker iterator (e.g., bidirectional or forward-only), and so you can write algorithms that work on both a vector and a doubly-linked list, but give you the best available scaling for free. Not only that, this selection operates at compile-time and incurs no runtime penalty.

Sounds like magic? It is! Here’s how the advance function is implemented in STL, using python-y pseudocode:

def advance( i, n )
  case i.class of ForwardIterator
    while( n-- ) i++
  case i.class of BidirectionalIterator
    if( n >= 0 )
      while( n-- ) i++
    else
      while( n++ ) i--
  case i.class of RandomAccessIterator
    i += n

At a later date I’ll probably go into the gory details of how this selection is done in C++ at compile-time. Not because it’s not well explained at the SGI STL site and in many fine books. But because pushing the concepts out of my head into words makes them clearer in my mind. (Anyway, in brief, an ancillary type hierarchy of tag types is defined, and the compiler’s rule of selecting the most-derived matching template is exploited.)

Back to Lower Bound

For the moment let’s get back to lower bound, which is how we got here in the first place. The algorithm finds the furthest iterator in an ordered range that is still less than some test value. My naive guess as to the implementation was:

def lower_bound( l, u, v )
  case i.class of RandomAccessIterator
    # some variation of binary search
  case i.class of ForwardIterator
    lastgood = l
    while( *l < v )
      lastgood = l++
    return lastgood

So if we have a random-access capable iterator, where advancing the iterator any number of steps was O(1), we would use binary search, which gives us an overall running time of O(lg n). But if advancing the iterator n steps cost O(n), then we would use the naive linear search algorithm, for an overall average running time of O(n) and an expected cost of n/2 when the value is drawn from within the range [*l, *u).

But that’s not what the algorithm is at all. And to the strangeness (but correctness) of that, I will have to return another time, because right now I have to get to work.

When I started contracting, I had just dropped out of grad school and was doing everything on a shoestring. I think we took an advance on my in-laws credit card just to buy me a machine, and my wife (who was still a grad student at that time) bought Visual Studio 6.0 Professional Edition at the Cal student store so I’d have something to hack with.

I had a copy of Wage Slave No More, which was new at that time, just published the previous year, so I learned how to set up a sole proprietorship and get a fictitious business name and business license and everything. Back in the day when some but not all of this information was available online, and you still had to (gasp) phone people.

I also read various books about business, mostly geared at middle-managers in large businesses or wannabe Donald Trump imitators. I read Rich Dad, Poor Dad. I read a lot of junk about real estate investing. I don’t think I read a lot of books aimed at small business owners or solo practitioners.

But that’s what I wound up being: not quite a real small business owner, which typically means someone with, like, inventory and premises and all that jazz. And I’m not quite a solo practitioner because our business is a partnership between me and my wife, and not just in the “You do the work, honey, and I’ll do the bookkeeping and reception” division of labor that some couples seem to adopt. We aim to be working together on each line of code that we produce and deliver to clients. We achieve that in practice I’d guess about 80% of the time, and the remaining 20% is divided between me haring off in some wild direction and occasionally bringing back some value, random open-source hackery, sysadmin work, and blogging.

So from time to time I’ll write about what it’s like to have a small software shop with no intention of growing and tell some of the stories. We’ve been up and down over the years… I think the low point was when we had agreed to buy a house, and the three months worth of client invoices that were due between the purchase agreement and the closing just kept on being due until a good two months past the closing. And then we took the money and… well, that’s best left for another time.

But accounting — or rather, bookkeeping — is where I’m going next.

I only learned how to use precompiled headers recently — even though I remember reading this paper about how to do it back in the late 90’s. It seemed like too much effort, then, and my then-blazing fast Windows NT 4.0 machine didn’t seem to need the help.

Somehow, ten years later with a dual-core CPU that’s ten times as fast, ten times as much RAM, and an effectively infinite amount of disk (1 TB on two disks), it became important enough to do. And my build times went down by a factor of three or more.

Setting up precompiled headers for the first time

1. Decide whether this project is going to use precompiled headers with C files or C++ files. You can’t do both, so pick the file type that there is more of.
2. For now let’s assume you are doing precompiled headers for C++ files.
3. Organize the project’s source files directory into three folders: CPP Files, C Files, and Precompiled Header. You can have subfolders under those if you want, but you must have those three folders at top level, and no C or C++ source files that are not underneath them. All C++ files that will use precompiled headers go into CPP Files. The file stdafx.cpp (the precompiled header file) goes into Precompiled Header. All other source files, typically only .c files, go into the C Files folder.
4. Select ‘All Configurations’.
5. Go to project settings, select the entire CPP Files folder, and on the C/C++ tab select “Precompiled Headers” from the Category: dropdown. Choose “Use precompiled header file (.pch)” and fill in “stdafx.h” in the “Through Header:” box.
6. Select the entire Precompiled Header folder, and without changing tab or category, choose “Create precompiled header file (.pch)” and fill in “stdafx.h” in the “Through Header:” box
7. Select the entire C Files folder, again without changing the tab or category, choose “Not using precompiled headers”
8. Close project settings.
9. Open the file stdafx.cpp and ensure that it only contains one line: #include "stdafx.h"
10. Open each file in the CPP files directory and ensure that the first non-comment line in that file is #include "stdafx.h". Anything before the inclusion of the precompiled header will be cheerfully ignored by the compiler. I just verified this by including a syntax error at file scope before and after the precompiled header. This failed:

    
    #include "stdafx.h"
    Microsoft is cool
    

    while this succeeded:

    
    M1cr0s0ft suxx
    #include "stdafx.h"
    

11. Now you can proceed to move headers from the .cpp files into the precompiled header. As a rule of thumb, put all system headers (angle brackets) into the precompiled header file. Put non-system headers into the precompiled header if they are used by more than about 25% of the files in the project. Or you can obsessively time and retime rebuilds until you find the optimal distribution of headers.
12. Now do Build | Batch Build and choose Rebuild All. The build will appear to stall on the first C++ file, because it is precompiling the headers. Then the build of each successive file will be very quick.

Maintaining precompiled headers

When you add a new C++ file to your project, Visual Studio will helpfully select the other option from the precompiled header area — “Automatic use of precompiled headers”, also known as the evil option. As far as I can tell, this causes Visual Studio to randomly trash the precompiled header file.

This is more than merely irritating; it can introduce a circular dependency that breaks the build and makes it impossible to run your program in the debugger. If file A.cpp depends on the precompiled header in the correct way, but file B.cpp is added and depends on (and rebuilds) the precompiled header in the evil way, Visual Studio will do the following on a Rebuild All:

 compile precompiled header as per A.cpp (correctly)
 compile A.cpp
 compile precompiled header as per B.cpp (evilly and brokenly)
 compile B.cpp
 link

Then if you try to run, it notices that a dependency of A.obj is newer than A.obj, notably the .pch file. If you have incremental linking turned on, you’ll just get the “One or more files are out of date or do not exist.” dialog but the project will run.

If you later modify A.cpp and try to build to run in the debugger, then you get the message

c:\users\client\project-work\file.cpp(1) : fatal error C1852: 'DebugU/project.pch' is not a valid precompiled header file


The only cure for that is to do another Rebuild All.

There is a way to avoid this problem. It is the path of righteousness: when you add a file to a project that uses precompiled headers, you must ensure that it gets the “Use precompiled header file” option.

Deciding what to put in your precompiled header

Using precompiled headers is a sort of a devil’s bargain, really, because in order to get the speedup from using them, you wind up including the header in many more translation units. That’s not actually too painful in terms of speed, and it works great as long as you only include system headers in your precompiled header source file (stdafx.h).

Once you start including project header files, however, a change in that project file will cause the precompiled header to be invalidated, which will cause all the object files that depend on it to be invalidated, which forces you to effectively rebuild your whole project.

That’s fine if half your project depended on that file anyway. But it turns out not to be too painful even when it doesn’t because precompiled headers are such a big win. On one client project (40k loc, C++), a full rebuild with precompiled headers takes 20s, of which building the precompiled header is 4.5s. The full rebuild without precompiled headers takes over four minutes. Here’s a graph:

So even though we spend up to 5 seconds precompiling the header, it pays off dramatically, cutting the overall compile time by a factor of 10.

That’s not the fairest possible comparison. I haven’t spent any time tuning the header includes of the non-pch build, so I’m certainly including some headers unnecessarily into translation units that don’t need any of the things declared in those headers. I could probably spend a good half hour hunting them down, trying to make the build as tight as possible. Or I could turn on precompiled headers, get a nearly free tenfold increase in build times, and spend the half hour hacking.

In my last post about python, I included the following ruby code to give an example of how to get a list of all the classes named “Test.*” but not “TestSlow”:

fastTests = []
ObjectSpace.each_object( Class ) { |x| fastTests << x.to_s if x =~ /^Test/ }
fastTests.delete(”TestSlow”) 

But this is ugly. The Ruby Way(tm) should be to do it in one line, right? Surely there is some idiomatic way to filter a collection — .select should do it.

But you can’t apply .select to the result of each_object(). In fact the return vale of each_object is a fixnum, not an array, and you only have access to the object list through the block.

But you can’t return a value out of a block, either. You can alter existing variables in scope, but the routine you passed the block to gets to determine its own return value.

I spent a little while hacking on a way around this limitation using exceptions as an additional return mechanism. It was evil and it didn’t work.

So I created the following function that executes a method which takes a block parameter and returns the results of iterating it as an array –

def unpack( method, args )
  a  = []
  method.call( args ) { |x| a << x}
  return a
end

With that in hand, you can get the available classes into an array, then filter them like this:

  fastTests = unpack( ObjectSpace.method( :each_object ), Class ).select do |x|
    # starts with test but is not testSlow
    x.to_s =~ /^test/ and not x.to_s == "testSlow"
  end

Or in many other clever ruby ways, surely.

But why isn’t that functionality built in? If you don’t pass an argument to each_object, it will iterate over all the currently active objects, which could yield a very large array. Forcing the user to use a block instead of blindly dumping the object references into an array is probably an attempt to be kind to the user, to prevent his shooting himself in the foot. But it yields the decidedly un-rubylike code that starts off this entry, with the explicit initialization of the target array.

By the way, I checked to see how it’s done in Test::Unit, written by someone who’s at least ten times more expert in ruby than I am, and it’s the same idiom:

        def collect(name=NAME)
          suite = TestSuite.new(name)
          sub_suites = []
          @source.each_object(Class) do |klass|
            if(Test::Unit::TestCase > klass)
              add_suite(sub_suites, klass.suite)
            end
          end

Maybe you could come up with something evil by creating a custom filter class and overriding the === method — which is how the each_object method is filtering what gets passed to the block. But it’s a little disappointing that there’s no simple builtin way to turn an iterator into a list.

I recently wrote a small internal program in python to automate our client’s builds: run everything overnight, collect the output, and generate some rudimentary web pages It wound up being 250 loc for the program, split into about three files; and 500 loc for the tests. I spent about 2-5 days on it, part time. Just enough to give me a feel for what the language is like.

And I don’t like the language. I know that python is supposed to be the cool language, and perl is ugly line noise. And ruby? I don’t know what people have against ruby. But python is so sexy they even use it to teach the Intro to Computer Science course at Harvey Mudd now.

I hate the way formatting structures control flow. I hate that even in XEmacs in python-mode, I was fighting with it to get the right indentation (which means the right semantics). I hate that I can’t define an empty class or method. Several times I started to write a test, realized I wanted to run something first, and left it stubbed out as

  def testHTMLLine:

Well, you can’t do that. You need to do:

  def testHTMLLine:
      pass

At that point I’ll bring my own curly braces.

I hate that it’s dynamic, but not dynamic enough. I had a set of tests, collected into about five test cases. One set of tests was slow (10 seconds) because it actually tested connecting to the CVS server, checking out a project, building it, etc. The rest of the tests finished in under a second. I wanted to define a test suite that contained all the fast tests only, so I could shorten my test-code-test cycles.

Simple and evil solution: enumerate the test cases that are fast. Evil because I have to remember to update the list if I add a new fast test case. So create a suite at module level like this:

fastTests = ["test.TestParseOutputLog", "test.TestDirClass", "test.TestSystem" ]
fastSuite = unittest.TestLoader().loadTestsFromNames( fastTests )

Clever and dynamic solution: enumerate all the tests but remove the slow ones.

# NOTE: not actually python, this DOESN'T WORK
fastTests = __thismodule__.Classes.remove( "SlowTest" )
fastSuite = unittest.TestLoader().loadTestsFromNames( fastTests )

I couldn’t figure out how to easily enumerate all the classes in the module I was in. While loading the module, some of the things which get set up eventually (the module object, for example) are not yet available to me. Look, I know it’s possible because the unittest.main() routine knows how to enumerate all the classes which are descended from unittest.TestCase. But it’s not trivial to do. In ruby you could do something like

fastTests = []
ObjectSpace.each_object( Class ) { |x| fastTests << x.to_s if x =~ /^Test/ }
fastTests.delete(”TestSlow”) 

where you could filter on name (starts with Test) and file (if necessary), and then remove the slow one. This isn’t about dynamic vs. static languages, it’s about user experience. In C you know you can’t do reflection, and when a unit test framework like cxxtest depends on perl or Python being installed, that’s fine. But because it’s possible in Python — but obscure and ill-documented — it becomes an annoyance.

The documentation is horrible. Over the last ten years my first recourse when looking for API documentation has been my friend Google. The Python documentation, even though it’s all free and available online, seems to be deliberately poorly organized and indexed. What I was hoping for was a quick cheat sheet on how to do a common thing (string interpolation). What I found was proposals to change or extend Python in varying mutually incompatible ways, in order to make it easier to do string interpolation. And this experience was repeated over and over as I dug through the language, library, and ancillary documentation looking for the Python way to do the things I needed.

Finally, Python doesn’t live up to its hype. How can it support functional programming when expression if (as opposed to statement if) was only added as a language feature in version 2.5? Even C has it!

Perhaps I have this all wrong, and Python is the best language EVAH. In the spirit of Strong Opinions, Weakly Held I welcome corrections and arguments in the comments.

We use BackupPC for our backups, both on our site and at $CLIENT. It’s a great onsite backup tool, really brilliantly done, and I recommend it to anyone who has small office multi-PC backup needs.

BackupPC can connect to clients in a variety of ways, the most useful being rsync and SMB (windows networking). All our machines are on rsync and most of $CLIENT’s are on SMB, just because it was easier to use the networking that was already set up than to install rsync on 20 machines.

Recently we switched a key computer to rsync because it had been having problems with SMB. I got most of the files being backed up but there was a problem with the Documents and Settings directory, which is, um, important. So I hacked on the config files for a while and couldn’t get it to work. I eventually split all but the Documents and Settings directory into its own host so at least that stuff (accounting databases) would be being backed up.

It turns out that the problem was one character in the host’s rsyncd.conf file. This may be fixed with new versions of rsync, but just for your information you will get a ‘chdir error’ if there’s a trailing backslash in your path, like this:

[docs]
path = C:\Documents and Settings\

but everything works fine if the backslash is gone, like this:

[docs]
path = C:\Documents and Settings

Blogging from my wife’s BlackBerry here… while I’m watching the kids outside. Should be fun!

I recently ran into a work problem where I had to find, in a sorted array, the largest entry smaller than my input number. You can approach this as a binary search problem, and I did at first. When Google couldn’t find a good implementation in C, I wrote one of my own, even to the point of coding up test scaffoling in the style of Programming Pearls.

But then I recognized that the problem was actually called “finding the lower bound”, which gives better search results. There’s even an implementation in STL that I could use in my target application. More on that later.

Anyway, about a week later I’ve spent so much time thinking about the damn algorithm I haven’t even put it in the target code yet!

Read the rest of this entry »

Background is necessary. In one episode of Dora the Explorer (that’s a children
s TV show), Dora finds a dinosaur egg which hatches. They help the baby dino get back home, all the while singing the Baby Dino song. With verses like:

Who’s got the biggest footsteps around?
BABY DINO!

Unfortunately this song is strangely catchy. So we find ourselves singing it. And we screw with the words.

Who’s got the rottenest liver around?
BABY WINO!

Who’s got the smallest tax-cuts around?
BABY RINO!

I was particularly pleased with that one. But Kaija was upset by it, and wanted to know what I was talking about. Explaining Republican In Name Only seemed beyond the scope of the situation, so I started on taxes.

“See, taxes are when the government steals your money. So tax cuts are when they steal less of your money, so the cuts are good.”

She frowned thoughtfully.

“Government bad. Taxes bad.”

And in that moment I knew I was going to Hell.

Fucking mouse.

Lame cat who won’t catch the mouse, even when the mouse is pointed out to said cat with a flashlight.

Fucking mouse running around my desk, on the floor and on top of the desk too.

This is a big flashlight.

Hmmmmmmm…

WAP WAP WAP WAP WAP

One dead mouse.

The Magician of the Ivory Tower brought his latest invention for the master programmer to examine.

I followed a link labeled “Threads are evil” to this paper (pdf, few hundred k) by the Edward Lee, who is no less than the chair of the EECS department at the University of California, Berkeley.

The thrust of the paper (which is more than two years old) is that threads are a bad model for parallel execution because they make it hard to prove things and reason about programs. I’m not trying to make him sound unreasonable, but there it is. Actual excerpt:

That is, given a pair of multithreaded programs (p₁, p₂) and another pair (p₁^‘, p₂^‘), when are these two pairs equivalent? A reasonable extension of the basic theory defines them to be equivalent if all interleavings halt for the same initial state and yield the same final state. The enormous number of possible interleavings makes it extremely difficult to reason about such equivalence except in trivial cases (where, for example, the state B^** is partitioned so that the two programs are unaffected by each others