Finding awesome developers in programming interviews
Posted on: 2010-09-13 18:00:00

In a job interview, I once asked a very experienced embedded software developer to write a program that reverses a string and prints it on the screen. He struggled with this basic task. This man was awesome. Give him a bucket of spare parts, and he could build a robot and program it to navigate around the room. He had worked on satellites that are now in actual orbit. He could have coded circles around me. But the one thing that he had never, ever needed to do was: display something on the screen.

Some people have a knack for asking the right questions to spot awesome developers in a job interview. Other interviewers dread it, come in with their tail between their legs, ask a few questions from the Internet and just go along with the group decision. But interviewing is an essential skill for most developers. A bad hire has terrible long term consequences, because eventually a sub-par employee may bring others into the organization. On the other hand, unfairly excluding an awesome candidate also hurts.

A programming interview includes at least three parts. In part I, we prove any assumptions we have after reading the resume. In part II, we get a sense for how much true experience the candidate has. Finally, we test this experience using a few spot checks and a coding question.

Part I: Testing assumptions from the resume

Once I was intervewing a candidate along with a fellow co-worker. When it was done, I thought the candidate had done okay, but not brilliantly. My co-worker, on the other hand, seemed angry. "He lied about technology X. He obviously has not worked with it. Definately a no-hire." Technology X was not even important to us. "If he lied about that," my co-worker went on, "I don't trust anything else on the resume."

Candidates should use the resume to portray themselves in a positive light. (See The Completely Honest Resume). However, there is a line where this positive portrayal becomes misrepresentation. In the example above, I wasn't as concerned as my colleague, because I already assume that everything on the resume is false until proven otherwise. If the resume says, "expert in technology X", then I will assume that the candidate merely knows the name of technology X. If the resume says, "Worked in a group that created a multi-threaded stock trading platform," then I will assume that the candidate merely chose the colours for the background. I used to be less strict until I met the guy with 10 years of experience who couldn't write code. If someone says that they wrote the text formatter in OpenOffice, or has a Ph.D, it is easy to make assumptions about their skills. Assume nothing. All must be tested.

For each relevant item on the resume, I first try to get a sense of what the candidate actually did. Then, I get him or her to prove it by talking about it.

  • Created a real-time operating system as a course project.
    How large a group did you work in? A group of 15? Oh, okay then, what specific part did you work on? The message queue? Great! Can you describe what happens when a high priority task sends a message to a low priority task?
  • Developed from scratch an audio transfer protocol for wireless security systems.
    How large was your team? Just you? Wow, how did you test it? Why didn’t you use RTP?
  • Fixed bugs in the XYZEngine.
    Can you describe a bug that you found particularly challenging, and how you fixed it?

Part II: Finding true experience

Having more experience is a good indication of awesomeness. Experienced developers have made mistakes. They know when, and when not to apply design patterns. They have a sixth sense about what part of requirements will probably change, and what part will probably stay the same. They know when to be lazy and when to be pedantic. It is true experience which makes the gap between awesome and mediocre programmers so wide.

But not all experience is the same. It is certainly possible for someone to gain solid skills in a couple of years, simply by working on lots of different things, writing and rewriting countless lines of code, and making many mistakes. On the other hand, it is also possible for someone to spend a decade writing one-line changes to a single project, without learning anything new.

Finding hidden time

There are lots of great developers who started coding when they were in their second year of university. By the time they get out of school, they will have had a few years of experience. On the other hand, some awesome developers started learning their art at an early age. I know several people who wrote some non-trivial programs in their teens or earlier. This information is nowhere to be found on their resume, and must be coaxed out during an interview.
  • Why did you get into the software development field?
  • What's the first programming language that you ever learned?

Density of Experience

Many awesome programmers do all of their coding at work. These are great, well, rounded individuals that you should definitely hire. However, doing personal programming projects outside of work or class is a pretty good indicator of awesomeness. A candidate with personal programming time simply has more flight time under his or her belt, and will be better for it. No personal projects? These other indicators will also count for some points:

  • Working on smaller teams or groups.
  • Working on a wide variety of projects
  • Detailed knowledge of several layers of abstraction on a large project
  • Being the main contributor in a group project

Part III: Verifying experience

After gaining a sense of the candidate's true level of experience, it is important to verify that experience testing their programming abilities. A few minutes of time is completely inadequate for a true test, but that's all that's available. We can get an idea of the breadth and depth of knowledge of the candidate by asking questions about different areas of software development. Of course your perception of the candidate's skills will be biased by your own experiences. You cannot judge the correctness of answers in topics that are unfamiliar to you. That's why there are several interviewers.

The specific topics depend on the job requirements. Nevertheless, some example areas are:

  • data structures and algorithms
  • multithreading
  • bit manipulation
  • memory allocation
  • objects and inheritance, design patterns
  • recursion
  • compilation and how computers run programs

Each area that I choose has a selection of basic questions (“What’s a semaphore?”). These are so basic that if the candidate has done any work at all in the area he or she would be able to answer. Each area also has some more detailed follow-up questions. The way in which a candidate answers can prove or disprove awesomeness. For example something is amiss if you ask a seasoned embedded programmer to convert 0x4c to binary, and they start by writing down 4 x 16 + 12.

The Coding Question

Usually, after all of the above, I have a very good idea whether the candidate will pass or fail, but the coding question removes all doubt. It is so important, that even phone interviews are not exempt. To be useful, a coding question requires careful thought and planning before the interview. Asked the wrong way, the response will be useless.

First, one must choose a question based on what the candidate has had experience with. You may have a clever problem that becomes easy if you think of converting everything to intersecting 3D planes. Save it for the lunch hour with your colleagues. If the job does not involved 3D graphics, candidates would be unfairly excluded.

The question must be precisely worded. "Write a function to shuffle a deck of cards" is woefully ambiguous. Provide the function header and avoid misunderstandings, which are all too common. If you are not careful, the candidate will answer a harder or easier problem than the one you asked. The harder one is nice, unless it causes him or her to freeze up. The easier one provides no information. To prevent a huge waste of time, ask for a verbal outline of the solution after a few minutes, to check if the candidate is on the right track.

The influence of the order of questions

The order in which you ask questions can profoundly influence the thought processes of the candidate. For example, I used to ask question about hash tables when I thought the candidate knew about them. Later on in the interview, I would ask a coding question that had nothing to do with hash tables. Candidates would invariably decide to use a hash table in their implementation, with the keys being unique, consecutive integers starting at 0. If I avoided talking about hash tables, the candidates would instead choose to use an array.

Candidates are also strongly influenced by you in their choice of language. For example, if you say the job primarily involves Java, every candidate will swear that, by golly, Java is his best and favourite language to work in. He will choose to use it for all coding questions, realizing too late that he can't remember how to declare variables in the language he is "best" at.

Avoid language bias

It's terribly easy to be biased toward a specific programming language that you use at your company. By fixating on a particular tool, you throw away a lot of awesome developers. Do not try to determine if the candidate awesome at programming in C or Java or whatever. Instead, you should be trying to find out if the candidate awesome at programming in the language that he or she knows best.

Going further

The guidelines above do not address everything. They focus on experience, and they might miss awesome developers that have little experience, but a lot of innate ability. In particular, interviewers may want to test problem solving ability using puzzles that don't require any coding.

The interviewing technique that I have described here is based on proving a hypothesis, probability, and gut instinct. The hypothesis is that the candidate is an awesome developer. What traits does an awesome developer have? You cannot directly measure those traits, so you have to instead ask: What is the probability that the candidate has those traits given that he or she can answer a particular question quickly? It is not possible to assess a candidate within an interview with 100% success, but by asking thoughtful questions, you can come close.

Further Reading

More...

Compress your JSON with automatic type extraction
Posted on: 2010-08-16 21:00:47

JSON is horribly inefficient data format for data exchange between a web server and a browser. For one, it converts everything to text. The value 3.141592653589793 takes only 8 bytes of memory, but JSON.stringify() expands it to 17. A second problem is its excessive use of quotes, which add two bytes to every string. Thirdly, it has no standard format for using a schema. When multiple objects are serialized in the same message, the key names for each property must be repeated, even though they are the same for each object.

JSON used to have an advantage because it could be directly parsed by a javascript engine, but even that advantage is gone because of security and interoperability concerns. About the only thing JSON going for it is that it is usually more compact than the alternative, XML, and it is well supported by many web programming languages.

Compression of JSON data is useful when large data structures must be transmitted from the web browser to the server. In that direction, it is not possible to use gzip compression, because it is not possible for the browser to know in advance whether the server supports gzip. The browser must be conservative, because the server may have changed abilities between requests.

Today, let's tackle the most pressing problem: the need to constantly repeat key names over and over. I will present a Javascript library for compressing JSON strings by automatically deriving a schema from multiple objects. The library can be used as a drop in replacement for the methods JSON.stringify() and JSON.parse(), except that it lacks support for a reviver function. In combination with Rison, the savings could be significant.

Download it here

Suppose you have to transmit several thousand points and rectangles. JSON might encode them like this (without the comments):

[
    { // This is a point
        "x": 100, 
        "y": 100
    },

    { // This is a rectangle
        "x": 100, 
        "y": 100,
        "width": 200,
        "height": 150
    },

    {}, // an empty object

    ... // thousands more
]

A lot of the space is taken up by repeating the key names "x", "y", "width", and "height". They only need to be stored once for each object type:

{
    "templates": [ ["x", "y"], ["x", "y", "width", "height"] ],
    "values": [ 
        { "type": 1, "values": [ 100, 100 ] }, { "type": 2, "values": [100, 100, 200, 150 ] }, {} ]
}

Each object in the original input is transformed. Instead of listing the keys, the "type" field refers to a list of keys in the schema array. (The type is 1-based, instead of zero based, and I will explain why later). But we are still repeating "x", and "y". The rectangle shared these properties with the point type, and there is no need to repeat them in the schema:

{
    "templates": [ [0, "x", "y"], [1, "width", "height"] ],
    "values": [ 
        { "type": 1, "values": [ 100, 100 ] }, { "type": 2, "values": [100, 100, 200, 150 ] }, {} ]
}
We prefix each key list in the schema with a number. This number is the one-based index of a prior schema which is prepended to it to form the combined list. Zero means the empty object, which is why we use one-based indicies.

But we can still go a little further. Instead of having a separate "type" field in each object, we stick the type as the first element of the values array.

{
    "templates": [ [0, "x", "y"], [1, "width", "height"] ],
    "values": [ 
        { "values": [ 1,  100, 100 ] }, { "values": [2, 100, 100, 200, 150 ] }, {} ]
}

Finally, since we are trying to save space, we rename our properties, and stick in a format code so we can detect that compresed json is used.

{
    "f": "cjson",
    "t": [ [0, "x", "y"], [1, "width", "height"] ],
    "v": [ { "": [1,  100, 100 ] }, { "": [2, 100, 100, 200, 150 ] }, {} ]
}

Automatic type extraction

The hard part is finding the objects which share sets of keys. It sounds a lot like the Set Cover problem, and if so, an optimal solution is NP-complete. Instead, we will approximate the solution using a tree structure. While we are building the value array, when we encounter an object, we add all of its keys to the tree in the order that we encounter them.

At the end of the process, we can traverse the nodes of the tree and create the templates. Nodes which represent the end of a key list (shown in gray) must have entry in the key list. Although not illustrated here, nodes with multiple children are also points where the the child object types inherit from a common parent, so they also get an entry.

The astute reader will realize that the final schema depends on the order that we inserted the keys into the tree. For example, if, when we encountered the rectangle, we inserted the keys "width" and "height" before "x", and "y", the algorithm would not find any common entries.

It is possible to gain more efficient packing by using a greedy algorithm. In the greedy algorithm, before we begin, an initial pass through all the objects would be made to build a list of unique object types. Then when it comes time to insert keys into the tree, they are first sorted so that the ones which occur in the most unique types are inserted first. However, this method adds a lot of extra processing and I feel the gains would not be worthwhile.

Real world savings

Here is an actual document from my web site, Zwibbler.com. Click on "Transform" to see how CJSON compresses it vs. JSON.






Download

Download the CJSON code here.

Further reading

More...

JZBUILD - An Easy Javascript Build System
Posted on: 2010-08-03 08:30:00

I love languages where you need years of experience to write code that works, and languages where if you don't do everything exactly right, you will shoot yourself in the foot. (See my article "C++: A language for next generation web apps"). Naturally, I love javascript.

Fortunately, Javascript has tools that will help catch bugs before you run it. One is JsLint. Following Douglas Crockford's crazy rules eliminates many cross-browser compatablility problems, and it syntax-checks the code too. The Google Closure compiler performs static analysis of the code to catch a few more problems, and as a bonus it will compress and obfuscate your code for you.

JZBUILD is a build system to simplify the process.

Download jzbuild.py

git clone http://github.com/smhanov/jzbuild.git

Like any of the other dozen javascript build systems, JZBUILD will:

  • Run all of your javascript through a built-in copy of jslint for error checking.
  • Concatenate files together and feed them into the Closure compiler or YUI compressor, without sending your code over the web.
  • Process include directives. JZBUILD resolves dependencies so your files will be included in the proper order.
  • Include files from other folders. For example, you might have a folder full of re-usable javascript components that are used in several projects. JZBUILD will let you pull these files into your current project.

JZBUILD is designed to be easy to use.

  • JZBUILD only requires python and Java to run. If you don't have another tool that it needs, it will download it automatically.
  • You don't need any configuration file. By default, JZBUILD will process all files in the current folder.
  • JZBUILD includes built-in "externs" for the closure compiler, so it will work with projects that use the jquery javascript library. It includes other tricks to make the compiler work on your code.
  • It works on Linux and Windows

Tutorial

Although this example is in Windows, JZBUILD works equally well on Linux.

Suppose you have a folder full of javascript files -- eg, foo.js, and bar.js.

 Directory of H:\demo

07/29/2010  09:25    <DIR>          .
07/29/2010  09:25    <DIR>          ..
07/29/2010  09:26              8392 foo.js
07/29/2010  09:26              2303 bar.js
               2 File(s)           10293 bytes
               2 Dir(s)     377,483,264 bytes free

Run JsLint on them:

jzbuild.py

Run JsLint and concatenate them together into MyWebApplication.js:

jzbuild.py --out MyWebApplication.js

Run JsLint and compress them using the YUI compressor into MyWebApplication.js. The YUI compressor will be downloaded for you.

jzbuild.py --out MyWebApplication.js --compiler yui

Run JsLint and compress them using the Google closure compiler into MyWebApplication.js. The compiler will be downloaded for you.

jzbuild.py --out MyWebApplication.js --compiler closure

Included files

JZBUILD processes include directives by searching the current folder and any included files. Suppose foo.bar contained a line like this:

//#include <bar.js>

And bar.js contained a line like this:

//#include <MyUsefulFunctions.js>

Where MyUsefulFunctions.js is in the folder ../shared. Then you can compile your whole web application by specifying only "foo.js" on the command line:

jzbuild.py --out MyWebApplication.js --compiler closure -I../shared foo.js

The -I option says to search the given path for input or included files. JZBUILD takes a list of input files on the command line. It reads each of them and processes included files as well, and sticks all of them together before sending them to the output file.

Note: It is incorrect to say JZBUILD "includes" files. The files are only included once, no matter how many times you specify "#include". This directive will be renamed "@require" in a future version.

Advanced Usage

When it starts, and you didn't specify "--out" on the command line, JZBUILD will look for a file named "makefile.jz" in the current folder.

Example makefile.jz

Here's an example makefile.jz. In it, we specify two projects to build. The "release" project will use the closure compiler to create MyWebApplication.js from "foo.js" and all files that it includes, searching in the folder "../shared" for any included files. It will also prepend "license.js" to the output.

It also specifies a second project, called "debug". The "debug" project contains the option "base: release", which means to inherit all the settings from the "release" project.

When this makefile is in the current folder, you can build a specific project by specifying its name on the command line. For example, to build the release project, use:

jzbuild.py release
// You can use comments in a JZBUILD makefile.jz. The file format is exactly like
// JSON, except that quotes and commas are optional.
// A file is an object of projects. Each project produces one output file.
// When you invoke JZBUILD you must specify a project to build unless there
// is only one in the file.
{
    // Here is a project description. You only need one project but we will
    // define several for completeness.

    // You can give a project a name. You can use it to refer to the project
    // from other projects.
    release: {
        // The output file will be created from the input files. It is a
        // string with the path to the output file.
        output: MyWebApplication.js

        // 'input' is an array of input files. You should use only the filename
        // and not the path. When jsbuild starts it will automatically find
        // the files it needs from the include path. It will also expand this
        // list based on any //#include  directives.
        input: [foo.js]

        prepend: [license.js]

        // The include path specifies an array of paths to search for files.
        // It always includes the current folder.
        include: [../shared]

        // The compiler specifies the compiler to use. The default compiler is
        // 'cat' which simply appends files together. The other
        // option is 'closure' which refers to Google's closure compiler. If
        // you do not have the closure compiler JZBUILD will download it for
        // you. However you will need to have Java installed to use it.
        compiler: closure

        // Here are the options to the closure compiler.
        compilerOptions: [
            --compilation_level ADVANCED_OPTIMIZATIONS
            --warning_level VERBOSE
        ]
    }

    // Here is a second project.
    debug: {

        // This project is special because it inherits all the properties from
        // its parent project. It specifies the parent by name.
        base: release

        // Here we override the options to the closure compiler to include
        // pretty-printing so we can easily see what it is doing.
        compilerOptions: [
            --compilation_level ADVANCED_OPTIMIZATIONS
            --warning_level VERBOSE
            --define=ENABLE_DEBUG=true
            --formatting PRETTY_PRINT
        ]
    }
}

Goodies to make the Closure compiler work properly

Built in externs

An externs file is built in to JZBUILD, so you can use the jquery library with the closure compiler, and it will give you useful warnings when you call the functions with the wrong parameter types.

@export annotation

A painful reality (and the whole point) of using the advanced compilation mode of the closure compiler is that it renames everything, so if you need to refer to a property of an object from HTML then it won't work unless you "export" it as described here.

JZBUILD makes this easy using the @export annotation. For example:

//@export MyGreatObject
/** @constructor */
function MyGreatObject()
{

}

//@export MyGreatObject.prototype.dostuff
MyGreatObject.prototype.dostuff = function()
{

}

When the compiler is set to "closure", the above will cause JZBUILD to add the required exports to the code. Specifically:

window["MyGreatObject"] = MyGreatObject;
MyGreatObject.prototype["dostuff"] = MyGreatObject.prototype.dostuff;

License

The JZBUILD system is open source. It is released to the public domain. However, it contains portions of code that fall under other licenses. The full license information is found in the source code.

More...

Pssst! Want to stream your videos to your iPod?
Posted on: 2010-07-17 22:24:56

Do you have:

  1. a recent iPod touch, iPad, or iPhone
  2. a wifi network at home
  3. a folder full of videos on your Windows PC?

I'm looking for alpha testers for this Windows app I just made:

Simply install it from BansheeStreamerSetup.exe and run. Then it will give you an address to go to on your iDevice. Go there and you will see all of your videos scanned from your Windows home folder. You can play them and skip parts and everything.

There is no configuration, and no user interface of any kind yet. Just a big log file that you can copy and send to me if there are problems.

Try it out now! I just tested on Windows 7 and XP. it even works, slowly, on my EEE PC.

Since it is an alpha version it will expire in a couple months and you will require a new version.

This is different from alternatives for three reasons. First, it doesn't need a special app to be installed on your iPhone. The format it uses is already supported by the built-in media player.

Secondly, it doesn't use any extra storage on your computer. It converts the videos only when requested and doesn't store any intermediate results on disk.

Finally, it has no options to set or buttons to press. At first I did this to save time coding it, but now I'm thinking I'll leave it that way. It's not trying to be another itunes. Just start it and it's working. You can't get any easier to use.

PS: I would really appreciate it if someone who has access to the mediastreamvalidator tool from Apple could tell me what it says about my streams.

More...

"This is stupid. Your program doesn't work," my wife told me
Posted on: 2010-06-19 10:31:12
The HSV colour wheel, based on barycentric coordinates, is my favourite colour selection device. It discourages picking unnatural looking saturated colours. Instead, it gives the realistic designer colours more space in the triangle. That's why I chose it for Zwibbler.com, my online Javascript sketching application.

I was working on the drawing tool one evening and my dear wife happened to start using it to draw stuff. I watched her and asked her to change the colour of what she had drawn to blue.

More...

The simple and obvious way to walk through a graph
Posted on: 2010-06-03 08:00:00

At some point in your programming career you may have to go through a graph of items and process them all exactly once. If you keep following neighbours, the path might loop back on itself, so you need to keep track of which ones have been processed already.

function process_node( node )
{
    if ( node.processed ) {
        return;
    }

    node.processed = true;

    var i;
    for( i = 0; i < node.neighbours.length; i++ ) {
        process_node( node.neighbours[i] );
    }

    // code to process the node goes here. It is executed only
    // once per node.
}

The code works, but it only works once! The next time you try it, all the nodes will already be marked as processed, so nothing will happen.

Here's a neat trick that elegantly solves the problem. Instead of using a boolean flag in each node, use a generation count.

var CurrentGeneration = 0;
function process_node( node )
{
    if ( node.generation == CurrentGeneration ) {
        return;
    }
    
    node.generation = CurrentGeneration;

    var i;
    for( i = 0; i < node.neighbours.length; i++ ) {
        process_node( node.neighbours[i] );
    }

    // code to process the node goes here. It is executed only
    // once per node.
}

function process_all_nodes( root )
{
    CurrentGeneration += 1;
    process_node( root );
}

It's simple and obvious right? So why didn't I think of it in eight years?

More...

Asking users for steps to reproduce bugs, and other dumb ideas
Posted on: 2010-05-27 21:00:00

A common misconception about software development:

  1. When a bug occurs, users will it into a tracking system with detailed information on how to reproduce it.
  2. A developer walks through the given steps to reproduce the issue, finds the problem, and submits a fix

That's based on several bad assumptions. Most users will not bother to enter bugs into your system. It is an unselfish act of altruism to enter a bug report. The user knows that it could be months, or even years before the bug is fixed, but she needs to be finished with your app by 5pm today.

The second problem is that many bugs are not reproducible. Maybe the bug depends on something the user was doing, the fact that she always clicks on the okay button instead of pressing enter, or because she installed a printer driver that replaced part of the OS with a modified, out of date library. Maybe your application is the first thing she uses in the morning while the hard drive is still chugging and 99 other programs are trying to update themselves at the same time.

Even worse: sometimes the problem just goes away on its own.

It's tempting to dismiss bug reports that you cannot reproduce. As a developer, you have enough work to do. The least they can do is tell you how to reproduce the problem then you'll have a chance at fixing it. Thousands of open bugs are closed or left to languish for years because they cannot be reproduced.

Refusing to fix a serious problem until you have reproducible steps is a cop-out excuse for lazy developers, who would rather get back to working on the physics engine for that secret flight simulator easter egg. That excuse might work for non-commercial software, but in the commercial software business, it will lose customers and get you fired.

How to fix non-reproducible bugs

Use a logging system

The best way to fix non-reproducible issues is to have adequate logging in the first place. Whenever the user does something, selects a menu, clicks "cancel", or inhales, record that action somewhere. Keep the file small, so the old parts scroll away. Take care to scrub anything that would violate privacy. Then, when a problem occurs, you can ask the user to attach the log file to the problem report.

You can use a well designed log as input to a test framework. You can then automatically reproduce the issue as many times as you need to test the fix, and ultimately make it part of your regression test suite.

Otherwise, fix by inspection

In 1981, Mark Weiser studied how experts debug software. The very best programmers create a mental slice of the program, so they only have to think about a few functions at a time. Weiser defined a program slice as the minimal program that still reproduces the problem. He developed an automatic method for finding the program slice to make debugging easier.

Unfortunately, thirty years later we are still doing things manually, and debugging requires lots of creative detective work. Use source control to ensure that you are looking at the same version of the software that your customer is using. Work backwards from the error message, keeping careful notes of the reverse call graph. If the X variable was set, what were the possible values of Y? Could this else clause have run? It's grueling work, and it takes days, but at the end of it, you will have a list of potential paths through the system that caused the error. And now you can methodically fix each one of them, without ever having reproduced the problem.

Sometimes, though, you will find that the problem logically could not have happened. In that case, you can either add more logging, or detect and recover, or do both.

Otherwise, detect and recover

Okay, so you had adequate logging. You've mentally traced through the source code for days. You've written additional tests for different theories and failed to reproduce the problem. The only way it could have happened is if a hole in the universe opened up and changed the laws of physics for a moment, or cosmic rays rewrote some register values. You will just have to detect and recover.

If slow memory leak causing the application to crash after three weeks, make sure your application restarts itself every few hours. If your complicated data structure somehow gets into an inconsistent state, write a function to go through and fix it after every single change. You get the idea.

Detecting and recovering from a mysterious bug is sometimes the only way to turn a major show-stopper into a minor annoyance. It is not the final solution, but it is a way to give you more time to find the real cause.

Get to it

The next time you get a serious bug that you can't reproduce, don't close it. Fix it, as if your job depended on it.

More...

Creating portable binaries on Linux
Posted on: 2010-04-29 18:55:31

Distributing applications on Linux is hard. Sure, with modern package management, installing software is easy. But if you are distributing an application, you probably need one Windows version, plus umpteen different versions for Linux. In this article, we'll create a dummy application that targets the following operating systems, which are commonly used in business environments:

  • Windows Server 2003
  • Windows XP
  • Red Hat Enterprise Linux 3
  • Red Hat Enterprise Linux 4
  • Ubuntu 6.06.2
  • Ubuntu 8.04
  • Ubuntu 9.10

As evidence that the problem is hard, try downloading Firefox. It fails to start on many of the above platforms, due to missing libraries.

The sample application

The sample application is called plookup (download source and all binaries). It runs from the command line and takes a hostname, looks it up and prints out the IP address. Ignoring the security flaws, it has several monkey wrenches thrown in that make it hard to port to different versions of linux:
  • It uses C++, which causes headaches when dynamically linking
  • It uses socket functions, which cause migraines when statically linking

Will distributing source code solve the problem?

In theory, distributing source code seems to be an easy way to get around the problem, assuming your end user 1) has administrative access, 2) can install a compiler 2) knows how to run a configure script, 3) has the technical knowledge to interpret the output of a configure script and download the appropriate dependencies, 4) has technical expertise to resolve conflicts in library versions.

In other words, it's a completely unreasonable solution for software written for normal human beings.

Building on Windows

With the appropriate build flags, you can produce software on Windows 7 that will run on all versions of windows since Windows 95. By defining WINVER and some other macros, you'll be warned at compile time if you're using a feature that will break your program on earlier versions.

CL /EHsc /Feplookup.exe /DWINVER=0x0400 /D_WIN32 /D_WIN32_WINDOWS=0 /D_WIN32_IE=0x0400 wsock32.lib *.cpp
We're done with Windows. On to Linux!

Static linking on Linux FAIL

Static linking has gained an undeserved reputation for being portable. But see what happens when you try to create a statically linked version of plookup:

steve@ubuntu:~/plookup$ g++ -static -static-libgcc -o plookup main.cpp
/tmp/ccMhUffR.o: In function `hostlookup(std::basic_string, std::allocator > const&, std::basic_string, std::allocator >&)':
main.cpp:(.text+0x15): warning: Using 'gethostbyname' in statically linked applications requires at runtime the shared libraries from the glibc version used for linking

It defeats the purpose. The warning isn't kidding, either. Your app might run fine for months, then all it takes is one update and it will crash. Even if you didn't use any socket functions, you might have other problems.

Note: If you statically link using the GNU compiler, then according to the L-GPL you have to also distribute your object files so the end-user can possibly re-link them to another version of the C libraries that they could have modified. Because your customers love hacking on strcat in their spare time.

Dynamic Linking

I built and tested the sample application on many different platforms. This table summarizes the results of the experiment.

Build on Red Hat EL 3 Build on Red Hat EL 4 Build on Ubuntu 6.06.2 g++3.3 Build on Ubuntu 6.06.2 g++4.0 Build on Ubuntu 8.04 Build on Ubuntu 9.10
Runs on Red Hat EL 3? Yes No Yes No No No
Runs on Red Hat EL 4? No Yes No Yes Yes Yes
Runs on Ubuntu 6.06.2? No Yes No Yes Yes Yes
Runs on Ubuntu 8.04? No Yes No Yes Yes Yes
Runs on Ubuntu 9.10? No Yes No Yes Yes Yes

Analysis

There are two classes of systems. Those with libstdc++5.0 (Red Hat EL 3), and those with libstdc++6.0 (All others). If you build on a system with one version, your application will only run on systems which have that library.

Ubuntu 6.06.2 is a special case. It does not have libstdc++5.0 by default, but you can add it by installing and building with g++3.3. That makes Ubuntu 6.06.2 a great build environment for portable binaries.

Linux Standards Base

Linux Standards Base (LSB) has an excellent utility that will predict which versions of Linux your application won't run on. But I had some problems using the rest of their toolchain:

  1. It's not clear what you have to download to use their toolchain.
  2. It's not clear how to use their toolchain (Hint: It's a wrapper around gcc)
  3. Their toolchain doesn't work with recent versions of gcc
  4. Once I finally found a distribution that would work with the lsb tools, it did not produce a portable application.

I spent six hours on LSB one weekend and gave up.

Summary

To distribute binaries on Linux,
  • Dynamically link the standard libraries
  • Produce one binary using g++3.3 for older systems
  • Produce another binary using g++4.0 for newer systems
Hopefully in time the situation will improve. According to the FAQ on libstdc++ 3:
The GNU C/C++/FORTRAN/ compiler (gcc, g++, etc) is widely considered to be one of the leading compilers in the world. Its development has recently been taken over by the GCC team. All of the rapid development and near-legendary portability that are the hallmarks of an open-source project are being applied to libstdc++.

If you liked this you'll love:

More...

Bending over: How to sell your software to large companies
Posted on: 2010-04-16 18:00:00
This post also appears, with my permission, on A Smart Bear, with additional editorial comments by Jason Cohen, founder of Smart Bear Software.

More...

Regular Expression Matching can be Ugly and Slow
Posted on: 2010-03-13 11:00:00
If you open the first few pages of O'Reilly's Beautiful Code, you will find a well written chapter by Brian Kernighan (Personal motto: "No, I didn't invent C. Who told you that?"). The non-C inventing professor describes how a limited form of regular expressions can be implemented elegantly in only a few lines of C code.
/* match: search for re anywhere in text */
int match(char *re, char *text)
{
   if (re[0] == '^')
      return matchhere(re+1, text);
   do { /* must look at empty string */
      if (matchhere(re, text))
         return 1;
   } while (*text++ != '\0');
   return 0;
}

/* matchhere: search for re at beginning of text */
int matchhere(char *re, char *text)
{
   if (re[0] == '\0')
      return 1;
   if (re[1] == '*')
      return matchstar(re[0], re+2, text);
   if (re[0] == '$' && re[1] == '\0')
      return *text == '\0';
   if (*text!='\0' && (re[0]=='.' || re[0]==*text))
      return matchhere(re+1, text+1);
   return 0;
}

/* matchstar: search for c*re at beginning of text */
int matchstar(int c, char *re, char *text)
{
   do { /* a * matches zero or more instances */
      if (matchhere(re, text))
         return 1;
   } while (*text!='\0' && (*text++==c || c=='.'));
   return 0;
}

More...

More Posts

Email
steve.hanov@gmail.com

Other posts by Steve

Yes, You Absolutely Might Possibly Need an EIN to Sell Software to the US How Asana Breaks the Rules About Per-Seat Pricing 5 Ways PowToon Made Me Want to Buy Their Software How I run my business selling software to Americans 0, 1, Many, a Zillion Give your Commodore 64 new life with an SD card reader 20 lines of code that will beat A/B testing every time [comic] Appreciation of xkcd comics vs. technical ability VP trees: A data structure for finding stuff fast Why you should go to the Business of Software Conference Next Year Four ways of handling asynchronous operations in node.js Type-checked CoffeeScript with jzbuild Zero load time file formats Finding the top K items in a list efficiently An instant rhyming dictionary for any web site Succinct Data Structures: Cramming 80,000 words into a Javascript file. Throw away the keys: Easy, Minimal Perfect Hashing Why don't web browsers do this? Fun with Colour Difference Compressing dictionaries with a DAWG Fast and Easy Levenshtein distance using a Trie The Curious Complexity of Being Turned On Cross-domain communication the HTML5 way Five essential steps to prepare for your next programming interview Minimal usable Ubuntu with one command Finding awesome developers in programming interviews Compress your JSON with automatic type extraction JZBUILD - An Easy Javascript Build System Pssst! Want to stream your videos to your iPod? "This is stupid. Your program doesn't work," my wife told me The simple and obvious way to walk through a graph Asking users for steps to reproduce bugs, and other dumb ideas Creating portable binaries on Linux Bending over: How to sell your software to large companies Regular Expression Matching can be Ugly and Slow C++: A language for next generation web apps qb.js: An implementation of QBASIC in Javascript Zwibbler: A simple drawing program using Javascript and Canvas You don't need a project/solution to use the VC++ debugger Boring Date (comic) barcamp (comic) How IE <canvas> tag emulation works I didn't know you could mix and match (comic) Sign here (comic) It's a dirty job... (comic) The PenIsland Problem: Text-to-speech for domain names Pitching to VCs #2 (comic) Building a better rhyming dictionary Does Android team with eccentric geeks? (comic) Comment spam defeated at last Pitching to VCs (comic) How QBASIC almost got me killed Blame the extensions (comic) How to run a linux based home web server Microsoft's generosity knows no end for a year (comic) Using the Acer Aspire One as a web server When programmers design web sites (comic) Finding great ideas for your startup Game Theory, Salary Negotiation, and Programmers Coding tips they don't teach you in school When a reporter mangles your elevator pitch Test Driven Development without Tears Drawing Graphs with Physics Free up disk space in Ubuntu Keeping Abreast of Pornographic Research in Computer Science Exploiting perceptual colour difference for edge detection Experiment: Deleting a post from the Internet Is 2009 the year of Linux malware? Email Etiquette How a programmer reads your resume (comic) How wide should you make your web page? Usability Nightmare: Xfce Settings Manager cairo blur image surface Automatically remove wordiness from your writing Why Perforce is more scalable than Git Optimizing Ubuntu to run from a USB key or SD card UMA Questions Answered Make Windows XP look like Ubuntu, with Spinning Cube Effect See sound without drugs Standby Preventer Stock Picking using Python Spoke.com scam Stackoverflow.com Copy a cairo surface to the windows clipboard Simulating freehand drawing with Cairo Free, Raw Stock Data Installing Ubuntu on the Via Artigo Why are all my lines fuzzy in cairo? A simple command line calculator Tool for Creating UML Sequence Diagrams Exploring sound with Wavelets UMA and free long distance UMA's dirty secrets Installing the Latest Debian on an Ancient Laptop Dissecting Adsense HTML/ Javascript/ CSS Pretty Printer Web Comic Aggregator Experiments in making money online How much cash do celebrities make? Draw waveforms and hear them Cell Phones on Airplanes Detecting C++ memory leaks What does your phone number spell? A Rhyming Engine Rules for Effective C++ Cell Phone Secrets