Universal answer about optimization

When reading through questions on Stackoverflow.com related to optimization ("is X faster than Y"), I often want to reply with the same answer, regardless of what the question was about:

When optimizing you should always follow these steps:

• Don't optimize until you have a nice, clean, and working version of your code.
• When you have a version which is nice and clean, decide if it is fast enough.
• If it isn't fast enough, measure its performance. This step is important for two reasons. If you don't measure you won't (1) know the impact of any optimizations you make and (2) know where to optimize.
• Optimize the hottest part of your code.
• Measure again. This is just as important as measuring before. If the optimization didn't not improve things, revert it. Remember, the code without the optimization was clean, nice, and working.

Using git-svn for cross-platform development

I do a lot of cross-platform development, mostly Windows and Linux. Being able to build and test on multiple platforms before pushing changes to other people is crucial in order to avoid build and test failures. Git is almost the ideal tool to do this, but since we are using Subversion at work (that won't change in the forseeable future), I've been trying out git-svn to see if it is up to the task.

A typical work-flow goes like this:

1. Update local source tree with new changes from central repository
2. ... hack hack ...
3. Build and test on Linux
4. Transfer local changes to a Windows machine
5. Build and test on Windows machine
6. Fix problem which only shows up on Windows
7. Transfer changes back to Linux machine
8. Commit all changes to central repository, confident that everything builds and runs on both Linux and Windows.

The tricky parts are the "transfer changes from machine A to machine B" without committing to the central repository. I've tried several solutions to this (source code on a network share, "manually" copying the sources (for various values of "manually")), but none of them really flew. I always ended up committing to the central repo anyway. Fortunately we have a fairly low-traffic repo, and I can usually fix broken things before breaking anyone elses build.

(For the rest of this post, I'm ignoring Subversion branches, even if git-svn does handle Subversion branches as well as could be expected.)

Now, using git-svn isn't completely unproblematic either. In an ideal world, I would like to be able to both push and pull to/from the central repo from both machines A and B as well as push/pull between them, but git-svn does not support that. The translation of git commits and their Subversion counterparts has to be done in a single place, or havoc will ensue. In practise, this means that we have a single repo where we run git-svn. This repo can be pulled from, but should not be pushed to (or git-svn will get confused when trying to pull new changes from the central Subversion repo), nor should we pull from any other repo into it. The exact reasons for this is the topic for another post.

How do we then get our changes back into the git-svn repo if we cannot push or pull into it? The solution is to use the command "git format-patch". This command creates a patch-set containing a set of changes. "git format-patch origin" will create a patch for all changes present in the local repo, which is not present in the "origin" remote, so if I on the Windows box pull from the Linux machine, I can do "git format-patch origin" to get all the local commits I've made which I need to apply to the repo on the Linux machine (the git-svn repo) and from there committed to the central Subversion repo.

Once the patches have been transferred to the Linux machine (this can be done in many ways, I just copy the .patch files over a network share), they can be applied using "git am *.patch". This will apply the patches and commit the change. Conflicts are resolved just as normal git conflicts.

The workflow then becomes:

1. Bring in new changes from the central Subversion repo: git svn rebase
2. ... hack hack ...
3. Pull changes to Windows machine: git pull
4. Build and test on Windows
5. Fix eventual problems on Windows
6. Generate patch set to bring back changes to Linux: git format-patch origin
7. Copy patch files back to Linux
8. Apply changes: git am *.patch
9. Commit things back to Subversion: git svn dcommit

It is still a bit cumbersome, but the benefits are several:

• I can produce commits which I have tested on both Windows and Linux.
• I can use "git rebase -i" to edit/reorder the commits before finally pushing them to Subversion. This makes it easy to produce clear and concise commits.
• I can use "git gui" to commit partial files. I can include a single added line from a file with hundreds of other changes in it. This also helps in produce commits which are easy to understand.

In short, git and git-svn allows me to write better code.

Git rocks!

When I started using Git for my home hacking projects I mostly liked it because it was easy to set up a server via ssh without having to do a full Subversion setup and it was something I wanted to learn. I never really imagined that the distributed stuff would come in handy. Today, the remote machine I usually push/pull against was down, and I needed to sync a bunch of stuff down to my laptop. With Subversion I would have lost; ending up with manually copying files. With Git, it was as easy as

laptop$ git clone hacks hacks.git --bare
homepc$ git remote add mylaptop ssh://[user]@[host]/hacks.git
homepc$ git push mylaptop

Done. Happy, happy!

SCons and VMWare

VMWare has been using SCons for a year now and are actually pretty happy about it. I would have thought that they would complain more about performance, though.

CruiseControl

Sometimes you stumble across a tool you wish you had started to use several years ago. A tool which solves (or at least simplifies) a lot of the problems you have when you're developing software. CruiseControl is such a tool; and I had had it on my radar for a couple of years but never gotten around to actually start using it until a few weeks ago.

CruiseControl (or one of its cousins: CruiseControl.NET, CruiseControl.rb) is a tool used to support Continuous Integration, a software development practice which is characterized by frequent commits (usually at least once a day), and regular automated builds several times per day. We haven't gotten around to adopting CI completely, but CC is still a great framework to take care of your automatic build. Here are some highlights:

• It has nice web dashboard for monitoring the state of the builds. It tracks the time each build takes, and when a build is in progress it estimates time left based on the previous build.
• It is easy to configure.
• It can automatically trigger builds when commits are made to the source repository.
• It can automatically send mails to all users which have participated in the last build (i.e. have commited code since the last successful build). If you want it to it can send mail to everyone for every build, but with several builds per day that quickly becomes annoying.

If you aren't using CruiseControl for your automatic building, you should do so. Now.

Xcerion

Xcerion is a new Swedish startup which is working on a "internet operating system", something which runs entirely inside your webbrowser. The market-speak on their website gives the impression that it will revolutionize the computer industry and bring down Google and Microsoft and the same time. That is, of course, not true. They will be absorbed by either long before that happens.

I tried to get some hard details about what they're actually doing, but details are scarce, and any information I could get hold of is full of market-speak. Things like the following sounds like something Dilbert's boss would say:

"Given that everything is defined in XML creates enormous synergies and unleashes the innate power of XML,"

I'm not sure why they push XML so hard. XML is an underlying code/data representation, and will not cause any magic to happen by itself. XML may very well be the best choice of a representation, but it is not a silver bullet.

The fact that all applications are written in XML rings a big, fat, warning in my head. We've heard several claims over the last 20 years about new technologies which will render "traditional programming" obsolete, but we're still here writing code in C++, Java, Erlang, Ruby, Python, etc. What's the common denominator of the 20 most popular programming languages today? Their source code is written using text editors. Yes, some text-editors are most advanced than others, but we're still writing code. Practical, general purpose point-and-click programming won't be here for years.

XML is not designed to be human-editable. This forces you to have top-notch graphical editors on top of everthing, and that is not an easy task. Many have tried and failed (the Eclipse plugin.xml editor is a good example; it is not a bad editor, but it doesn't scale very well for non-trivial XML).

But then again, if Xcerion can deliver on their promises and replace the traditional desktop OS with a system which is light-weight, fast, runs everywhere, and fun to program (sort of like on the old Amiga days), I'm all for it. But I can't help but feeling sceptical about the whole thing.

Xcerion, please prove me wrong.

Writing a toolchain plugin for CDT (or: things not to use XML for)

I'm currently in the process of implementing support for a compiler toolchain for Eclipse/CDT. This means writing a large chunk of XML code describing how the toolchain works (what tools there are, what kind of inputs they take, what options they take, what build configurations are available, and so on). A typical standard thing to do when you want to use CDT with a compiler other than GCC.

Eclipse/CDT is very flexible when it comes to supporting other kind of toolchains; anything which can be broken down to a series of external programs which which interact to produce output from a given set of inputs. You can implement a toolchain for creating PDF files from LaTeX input, although this has little to do with C/C++ development. This great flexibility is actually the first warning flag. Yes, flexibility is a good thing, but the user's have to be able to wield it as well.

Most of the toolchain is defined in the plugin.xml. This is where all tools, configuration, projects type, options, etc. are defined. This is actually the second warning flag. My plugin.xml is at 2000 lines and counting, and I haven't really done anything complicated. A bunch of options, two different project types, two build configurations, and 4 tools (c-compiler, c++-compiler, linker, assembler). Yes, I could probably break out much of this in separate plugins, but that seems a little overkill.

CDT has a system for inheritance among elements in the toolchain definition file. I can define a common base class for my C and C++ compilers, and define C++-specific options in a subclass. What CDT does is basically to paste a primitive inheritance system on top of XML. It works like this:

<option
  id="com.foo.bar.option.parentOption"
  isAbstract="true"/>
<option
  id="com.foo.bar.option.subOption"
  superClass="com.foo.bar.option.parentOption"
  ... />

This may sound great at a first look, but it quickly turns out to be hopelessly inadequate. It's ok to do small things this way, but when you have three different tools with similar set of options you need a way to be able to share these in a more flexible manner.

One of my favorite programming principles is DRY: Don't Repeat Yourself. While writing CDT toolchain definitions you have to break this rule so many times, it's almost physically painful. For example: each XML element has to have a globally unique identifier, and it has to be specified in full in the element itself. In the plugin.xml file which contains my toolchain definition, 25% of the lines includes the reverse-DNS name ("com.foo.bar.plugin", for example) used to make sure that the identifier are globally unique.

There is an option for my compiler which takes 20-30 enumerable values (the target cpu type). To specify this, I have to write an XML element for each of these values:

<enumeratedOptionValue
  command="--cpu FOOBAR1"
  id="com.foo.bar.plugin.toolchain.compiler.generic.option.cpu.FOOBAR1"
  name="FOOBAR1"/>

Instead of allowing me to have a simple list of all cpu types and generate each option, I have to manually (cut-n-paste) expand the enumeration value definitions.

I think it would be better to write the toolchain definition in Java instead. The idea of defining things in the plugin's plugin.xml file is to let Eclipse know things about plugins without having to load the plugin itself, but does this include details about which options my compiler takes? If plugin.xml just defined the entry point classes for my toolchain in the plugin.xml file, I could define the toolchain by creating the appropriate Java objects. This would allow me to use the full power of Java's inheritance system and I can store option metadata (such as the number of available cpu types) in a way most suitable for my needs.

MFC Sucks. Badly.

I've done a fair amount of GUI-programming over the last 10 years, and there are a lot of toolkits out there of varying quality. None of them stand out as "excellent" in my eyes, but there is one which stands out as particularly lousy. MFC.

MFC is a patchwork of old (and in many cases non-existing) design, backward-compatibility fixes, API limitations, bad documentation, and bugfixes. Just to take a few examples:

• The OnVScroll() method which is called when a window's vertical scrollbar changes only gets the position as a 16-bit integer. 32-bit integers are supported, but you need to call GetScrollInfo() to get it.
  
• OnVScroll() gets a pointer to a CScrollBar control, but this pointer is unusable (and in most cases NULL). Instead, you need to call GetScrollInfo() to get a reference to the scrollbar.
  
• CListCtrl can be used as a "virtual listview", i.e. you specify the number of lines and a callback which is invoked each time the view needs the data for a given row. Useful when you need a large number of rows and fetch data on demand (such as displaying memory contents). However, it refuses to use more than 100 million elements. And, yes, this is then power-of-ten kind of million, not the power-of-two you might have expected in case the widget uses a part of the 32 bit index integer for tagging or such. And all documentation on this, including web articles and code samples consider 100 million to be "huge" and "enormous". If you have a 32-bit integer as index, why can't I have 2^32 entries in the view.
  
• You can't set CListCtrl's vertical position by setting the position on the scrollbar.
  
• If you want to change colors in individual cells in a CListCtrl(), you must implement your own drawing function from scratch. There is no way to enhance the list control's own implementation. You might as well reimplement the entire list control from scratch (which many people seem to have done.)
  
• There is no way (short of black magic and sacrificing green goats) to get CListView to use another implementation of CListCtrl. There are lots of variants of CListCtrl on the web, but exchanging the one ClistView uses is easier said than done.
  
• I needed to add a text-display window below my CListView which was to display details about the selected row. This required 4 (!) extra classes with ~500 LOC. Compare this to XMonad, a tiling X11 window manager implemented in about the same amount of code. But they used Haskell, not MFC. ;-)
  

Yet Another Annoying Thing About Visual Studio

I'm getting more and more annoyed by Visual Studio for every day I use it. Today's annoying thing is broken .sbr files.

Visual Studio has the annoying habit of leaving broken .sbr files around. I'm not sure when or why they appear, possibly when a build is interrupted. When bscmake at a later point tries to read these broken files, it croaks and causes the entire build to fail.

Every single other compiler in the world has the good sense of not leaving incomplete files on disk when exiting. But not Microsoft's. And it's not like this is a new bug; a quick check on google showed that this bug has been there at least since 2000.

Redirecting output from compiler/linker in Visual Studio 2005

I ran into an "interesting" (i.e. very annoying) problem today. I was in the process of figuring out a way to know if two Windows executables or DLLs are different. Just comparing them byte-for-byte does not work; the output cl.exe is not identical even if the incoming source code is.

So I tried to use dumpbin /disasm and compare the two disassembly listing, which worked nicely. I then wrote a little Ruby script to add as a post-build step in Visual Studio:

require 'digest/sha1'
require 'tempfile'

inputfile = ARGV.shift
IO.popen("dumpbin /disasm #{inputfile}") do |io|
Tempfile.open(File.basename(inputfile)) do |tempio|
 while io.gets
   if $_ =~ /.*Dump of file.*/
     next
   else
     tempio.write($_)
   end
 end
 tempio.rewind
 File.open(inputfile + ".sha1", "w") do |outio|
   outio.puts Digest::SHA1.hexdigest(tempio.read)
   puts "Wrote SHA1 signature to #{outio.path}"
 end
end
end

but to my surprise, dumpbin insisted on passing its output to the Visual Studio output window instead of through stdout and into my Ruby program. WTF?!

I started to dig. What could possibly cause dumpbin.exe to bypass stdout/stderr when run from inside Visual Studio? I fired up Process Explorer during build and studied the environment variables of cl.exe. Is there any magic going on here? The following environment variables caught my eye:

VCBuildHelper_CancelEvent
VCBuildHelper_Command
VS_UNICODE_OUTPUT

Knowing that Google Is Your Friend, I got a few hits, which gave me a hint about Unicode output being handled differently depending cl.exe is executed outside or inside Visual Studio. It turns out that people has compiler wrappers such as STLFILT which went mad when the output from the compiler disappeared.

Was it really so difficult for Microsoft to anticipate this problem? Piping output from a compiler or linker isn't a very odd thing to do. And how necessary is it to be able to have Unicode error messages? And why didn't they fix stdout/stderr to be able to handle Unicode? -- which would have been The Right Solution to the problem in the first place.

What happens during ExitProcess()

"The Old New Thing" is an excellent blog if you want to know things about Windows which is not in the documentation. Such as how ExitProcess works:

"Exiting is one of the scariest moments in the lifetime of a process. (Sort of how landing is one of the scariest moments of air travel.)"

The quest for a real build system, part 1

I've been looking for a "real" build system for quite some time, something which allows me to correctly and completely specify the relationsships between all elements of my program in a compact and easy-to-maintain sort of way. I didn't think it would be so hard, but apparently it is.

Take Visual Studio, for an example. If I build an executable in directory A and also want to copy it to B, the only way to do that (except for possibly creating a special project for the task) is to add a post-build step which copies the executable from A to B. However, there is no way to make Visual Studio guarantee that the executables actually is copied. If the copy-step fails, it will never be executed again unless the executable itself is rebuilt. Since Visual Studio does not know (or care) about what happens in a post-build step, it is impossible to know if all post-build steps in a project actually succeeded. In other words, post-build steps are useless for anything related to the actual build process.

SCons does this right. Its specification files are Python programs and you can manipulate nodes in the dependency graph exactly as you wish. Given that you've specified your dependency graph correctly, you can actually run scons and it will rerun exactly those commands necessary to bring your targets up-to-date. As a result, you really don't need a "clean" command (even if there is one).

Unfortunately, SCons has serious performance issues and does not scale well for very large systems. But sometimes I'm willing to pay a lot of performance for actually doing correct builds.

I've been using CMake at work for some time, and it has some nice features which makes it the best there is at the moment. The fact that it can generate Visual Studio project files, while still giving command-line people like me a Makefile is a big plus.