Different types of overheads in software projects

I mentioned this concept on Twitter in a conversation with Miles Sabin and Eiríkr Åsheim last night, and it occurred to me I’ve never written up this idea. I call it my quadratic theory of software projects.

It’s one I originally formulated in the context of program languages, but I’ve since decided that that’s over-simplistic and really it’s more about the whole project of development. It probably even applies perfectly well to things that are not software, but I’m going to be focusing on the software case.

The idea is this: Consider two properties. Call them “effort” and “achievement”, say. If I wanted to attach a more concrete meaning to those, we could say that “effort” is the number of person hours you’ve put into the project and “achievement” is the number of person hours it could have taken an optimal team behaving optimally to get to this point, but the exact meaning of them doesn’t matter – I only mention to give you an idea of what I’m thinking of with these terms.

The idea is this: If you plot on a graph, with achievement on the x axis and the amount of effort it took you to get there on the y axis, what you will get is roughly quadratic.

This isn’t actually true, because often there will be back-tracking – the “oh shit that feature is wrong” bit where you do a bunch of work and then realise it wasn’t necessary. But I’m going to count that as achievement too: You developed some stuff, and you learned something from it.

It’s also probably not empirically true. Empirically the graph is likely to be way more complicated, with bits where it goes surprisingly fast and bits where it goes surprisingly slow, but the quadratic is a useful thought tool for thinking about this problem.

Why a quadratic?

Well, a quadratic has three parts. We’ve got \(y = A + B x + C x^2\). In my model, \(A, B, C \geq 0\).

And in this context, each of those three parts have a specific meaning:

The constant component (A) is the overhead that you had to get started in the first place – planning, familiarising yourself with the toolchain, setting up servers, etc.

The linear factor (B) is how hard it is to actually make progress – for example, if you’re developing a web application in C++ there’s an awful lot of difficulty in performing basic operations, so this factor could be quite high. Other factors that might make it high are requiring a detailed planning phase for every line of code, requiring a 10:1 lines of test code to lines of application code, etc.

The quadratic factor (C) is the interesting one – constant and linear overhead are in some sense “obvious” features, but the quadratic part is something that people fail to take into account when planning. The quadratic overhead is how much you have to think about interactions with what you’ve already done. If every line of code in my code-base affects every other line in my code-base, then I have to deal with that: every line I write, I have to pay an overhead for every line I’ve already written. If on average a line of code interacts with only 10% of the other lines in the project, then I have to pay 10% of that cost, but it’s still linear in the size of the code base (note: I’m implicitly assuming here that lines of code is a linear function of achievement. I think in reality it’s going to be more complicated than that, but this whole thing is an oversimplification so I’m going to ignore that). When you have to pay a cost that is linear in your current progress, the result is that the total amount of cost you’ve paid by a given point is quadratic in your current progress (this is because calculus).

To use an overused word, the quadratic factor is essentially a function of the modularity of your work. In a highly modular code base where you can safely work on part of it without having any knowledge of most of the rest, the quadratic factor is likely to be very low (as long as these parts are well correlated with the bits you’re going to need to touch to make progress! If you’ve got a highly modular code base where in order to develop a simple feature you have to touch half the modules, you’re not winning).

There are also other things that can contribute to this quadratic factor. e.g. the amount that you have to take into account historical context: If a lot of the reasons why things are done is historical, then you have a linear amount of history you need to take into account to do new work. These all essentially work out as the same sort of thing though: The fraction of what you’ve already done you need to take into account in order to do new things.

So here’s the thing: Your approach to development of a project essentially determines these values. A lot of different aspects will influence them – who your team members are, what language you’re working in, how many of you there are, how you communicate, whether you’re doing pair programming, whether you’re doing test driven development, how you’re doing planning, etc and etc. Almost everything you could call “development methodology” factors in somehow.

And if you compare two development methodologies you’d find in active use for a given problem, it’s going to be pretty rare that one of them is going to do better (i.e. have a lower value) on all three of these coefficients: Some approaches might have a lower constant and linear overhead but a remarkably high quadratic overhead, some approaches might have a very high constant overhead but a rather low linear and quadratic, etc. Generally speaking, something which is worse on all three is so obviously worse that people will just stop doing it and move on.

So what you end up doing is picking a methodology based on which constants you think are important. This can be good or bad.

The good way to do this is to look at your project size and pick some constants that make sense for you. For small projects, the constant costs will dominate, for medium projects the linear costs will dominate, and large projects the quadratic costs will dominate. So if you know your project is just a quick experiment, it makes sense to pick something with low linear and constant costs and high quadratic costs, because you’re going to throw it away later (of course, if you don’t throw it away later you’re going to suffer for that). If you know your project is going to be last a while, it makes sense to front-load on the constant costs if you you can reduce the quadratic cost. In between, you can trade these off against eachother at different rates – maybe gain a bit on linear costs by increasing the quadratic cost slightly, etc.

The bad way to do it is to automatically discount some of these as unimportant. If you just ignore the quadratic cost as not a thing you will find that your projects get mysteriously bogged down once you hit a certain point. If you’re too impatient to pay constant costs and just leap in and start hacking, you may find that the people who sat down and thought about it for a couple hours first end up sailing past you. If you think that scalability and the long-term stability of the project is all that matters then people who decided that day to day productivity also mattered will probably be years ahead of you.

Sadly, I think the bad way to do it is by far the more common. I’ll grant it’s hard to predict the future of a project, and that the relationship between methodologies and these values can be highly opaque, which can make this trade-off hard to analyse, but I think things would go a lot better if people at least tried.

Reading code by asking questions

Peter Seibel wrote a piece about code reading recently. It’s a good piece which meshes well with my experience of code reading, and it got me thinking about how I do it.

I think there are three basic tenets of my code reading approach:

The goal of code reading is to learn how to modify the code. Sure your ultimate goal might be to understand the code in some abstract sense (e.g. because if you want to use the ideas elsewhere), but ultimately code you don’t know how to modify is code you probably don’t understand as well as you think you do, and code you do know how to modify is code that you probably understand better than if you’d merely set out to understand it.
The meaning of code is inextricably tied with its execution. In order to understand code you need to be able to follow its execution. You can do a certain amount of this in your head by manually tracing through things (and you will need to be able to), but you have a machine sitting in front of you designed to execute this code and you should be using it for that. For languages with a decent debugger, you even have a machine sitting in front of you which will execute the code and show you its working. For languages without a decent debugger (or setups where it’s hard to use one), you can still get a hell of a lot of mileage out of the humble print statement.
Ask many small questions. Ignore everything you do not need to answer the current question.

Many people completely rewrite code in order to understand it. This is an extreme form of learning to modify it – modification through rewriting. Sometimes this is fine – especially for small bits of code – but it’s pretty inefficient and isn’t going to be much help to you once you get above a few hundred lines. Most code bases you’ll need to read are more than a few hundred lines.

What you really want to be doing is learning through changing a couple lines at a time, because then what you are learning is which lines to change to achieve specific effects.

An extremely good tool for learning this is fixing bugs. They’re almost the optimal small question to ask: Something is wrong. What? How do I fix it? You need to read enough of the code to eliminate possibilities and find out where things are actually wrong, and you’ve got a sufficiently specific goal that you shouldn’t get too distracted by bits you don’t need.

If you don’t have that, here are some other small questions you might find useful to ask:

How do I run this code?
How do I write a test for this code? This doesn’t necessarily have to be in some fancy testing framework (though it’s often nice if it is!). It can just be a script or other small program you can run which will tell you if something goes wrong.
Pick a random line in the codebase. It doesn’t have to be uniformly at random – a good algorithm might be to pick one half of a branch in a largish function in a module you’re interested in. How do I get that line to execute? Stick an assert false in there to make sure the answer is right. If there’s a test suite with low coverage, try finding an uncovered line and writing a test which executes it.
Pick a branch. What will happen if I invert this branch?
Pick a constant somewhere. If I wanted to make this configurable at runtime, what would I need to do?
Specific variations on “How can I break this code?”. e.g. in C “Can I get this code to read from/write to an invalid address?” is often a useful question. In web applications “Can I cause a SQL/XSS/other injection attack?” is one. This forces you to figure out how data flows to the system through various endpoints, and then if you succeed in finding such a bug then you get to figure out how to fix it.
How can I write a test to verify this belief I have about the code?
What would I need to change to break this test?

Revisiting an old voting system design

A while ago I designed a voting system which is basically how you apply random ballot to multi-member elections. To recap, here’s how it works:

You are voting to elect N candidates. Each voter selects N of the candidates who are running and lists them in order of preference. You then repeatedly select (with replacement!) a random voter and elect the candidate they most prefer who has not already been elected. Once you have done this N times, you have elected N candidates and your job is done.

I was thinking about this again recently, and I’ve realised that it’s a much better idea than I initially realised. In particular:

It is indeed strategy proof – you have no incentive to vote outside your true order (note: See edit below. This is wrong)
It has a very nice strong proportionality property
It can be used to patch the single biggest objection people have to my towards a more perfect democracy proposal.

That it’s strategy proof is essentially obvious: At each point you are performing a random ballot, which is strategy proof, for the set of people who have not already be elected. So you you should always be voting for your most preferred person who is not already elected. This means that if you prefer A to B then you should rank A higher than B – if A has already been elected, you will vote for B, if not you will vote for A.

Edit: Wrong! You need to take into account the effect of other peoples’ votes. Suppose there are three candidates A, B, C and we’re electing two of them. Suppose everyone other than me is voting in order A, C. Now, suppose that I really really hate C and think A is a little better than B. This means that I strongly want the set of elected candidates to be A and B. Therefore I should vote B, A. Conditioning on my being picked on the first round (if I’m not it doesn’t matter what I vote – my second round selection will always be B, because A was elected in the first round), if I put A first then we will end up with {A, C} with very high probability (whenever I’m not picked for the second round too) . If I put B first then we will end up with {A, B} with probability 1. Therefore I should put B first even though I would prefer A.

This example can be extended further so that I may not even vote for my top N candidates.

The proportionality property it has is kinda interesting. It has the following property:

Suppose some group fields at least N candidates. If x% of the population prefer every member of that group to everyone not in that group, that group will have an expected number of seats at least x% of N.

So, for example, if x% of the population fill out their ballot entirely with members of a single party, that party will expect to have at least x% of the elected seats.

Why at least x%? Because the remaining voters can mix it up by e.g. preferring some members of that group to people not in it, but some people not in it to some people in it. If no-one outside those core x% of voters vote for the group then the expected proportion is exactly x%.

Finally, the patch to the perfect democracy proposal: One of the biggest things people object to about it is that people with a strong mandate can still fail to be elected – even if you have 90% of the vote, that’s still a one in ten chance of not being elected. This significantly depletes the chances of having an experienced person who people love staying in power, which is a bit of a shame.

The nice thing about this system instead of that it is that it handles this case much better by giving each candidate multiple chances to get in. As a result, the probability of a candidate with a fraction \(p\) of the first votes getting elected is at least \(1 – (1 – p)^N\) (it may be more depending on the distribution of second and higher votes). So if they have 90% of the first votes, with N = 2 they have at least a 99% chance of getting in, with N=3 they have 99.9%, etc. With a more modest 50% of the vote, they have a 99% chance of getting it at \(N \geq 7\) seats.

So this is the fix: Rather than having a large number of single member constituencies, you instead have a smaller number of multi-member constituencies. 10 is probably a good number – it’s on the cusp of what is feasible to get people to vote on, but it means that anyone with at least 40% of the first votes is extremely likely to get a seat, and anyone with 50% of them is virtually certain to get a seat (about every 10-20 general elections you will expect one candidate in the entire house with 50% of the vote in their constituency to fail to get a seat).

It definitely complicates the initial proposal, but I don’t think it’s that difficult to get people to reasonably rank 10 candidates they like. A more difficult thing might be persuading people to go for multi-member constituencies.

Coinpocalypse

I’ve just experienced what is possibly the single worst piece of user experience I’ve had to interact with.

I go to top up my Oyster card. There are two machines. One has a long line in front of it, the other is empty because it’s cash only due to a broken card reader. I have plenty of cash on me, so I decide to skip the queue.

This, it turns out, is a mistake.

So first it asks me how much I want to top up. My options are helpful prefilled buttons of 10 through 50 or I can enter an amount. I try to enter an amount larger than 50, but it helpfully informs me that despite the ever growing costs of public transport in London it’s literally inconceivable that I could want more than £50 on my Oyster, so I’m not allowed to do that. Fine, I ask for £50. It tells me to give it the money.

I put in two £20s and hunt around for a £10, but I turn out to only have £20s (For some reason it does not occur to me until later that I could have just put in an additional £20 and got change). Can I just ask it to accept that? No. Oh well. I click “Go back” assuming it will keep my money and let me choose another option.

Nope. Apparently “Go back” means “Abort everything, go back to the very beginning”. Oh well.

But as I press go back and am returned to the beginning of this sad saga, there is an ominous “clunk” noise.

Which is then followed by the distinctive metallic rain sound of a shower of coins onto hard plastic as my nice, compact, £20 notes are converted into individual £1 coins.

“Oh you’re fucking kidding me” I exclaim, as I stare at the machine in disbelief. The lady next to me at the other machine gives me an amused smile. “Ha ha, sucker” she carefully refrains from saying. “Should have waited in the queue”. She completes her transaction and moves on.

Meanwhile I’m left with a giant pile of pound coins and an untopped up Oyster card.

I sigh dramatically and begin to feed the coins into the machine. You know those nice big coin hoppers they have at a lot of self checkout machines where you can just pour your coins into it? Oyster card machines don’t have those.

I gather up handfuls of coins at a time and start individually feeding them into the tiny coin slot. Clunk. Clunk. Clunk.

After £27 it decide it’s had enough and just starts spitting out any more coins I feed it. I can’t really say I blame it. I mean who the hell would want to have that many pound coins, right?

I press the go back button again. Metallic rain.

At this point, the machine has defeated me. I gather up my coins in two great big handfuls, cross the hall to the empty ticket hall and talk to the nice man behind the desk.

He looks bemused as I pass him my pile of coins, but is perfectly happy to count them up and put the money on my Oyster card. The entire transaction takes about two minutes.

The annoying thing is that as a programmer I know exactly the sort of dysfunctional processes that lead to this sort of thing. But, as a user, I sure wish they’d actually watched some people trying to use these machines with cash before they shipped them.

Now you too can have a magic bug-finding machine

…at least, you can if you write python (though I’ve already received some interest in porting this to other languages from people).

I’ve spent today hacking on a pure python testmachine library. It works rather nicely: It’s significantly less magical than hypothesis, gives you a lot more power and produces very clean output.

Here’s some example output, which finds an unbalanced tree:

    t1 = Leaf()
    t2 = Leaf()
    t3 = Leaf()
    t4 = t3.join(t2)
    t5 = t4.join(t4)
    t6 = t5.join(t1)
    assert t6.balanced()

And here’s the example program that generated it.

I’ve uploaded an initial version to pypi, but this should definitely be considered a “for you to have a play with” version rather than something that you should get annoyed with me if I break the API. I’m very much still experimenting with how this works, but initial impression is that the answer is “rather well”, and I’m not too unhappy with the core API.