Code Fatigue: Performance Edition

It’s a truth universally acknowledged that sometimes you have to compromise your coding practices in order to eke out more performance.  However, I think it’s not appreciated how often just writing code well actually results in better performance.  For instance, I’ve seen more systems that would be faster with a more normalized schema in my career than systems that were crying out for denormalization*,

Let’s see how the two implementations of triangular number calculation from the last post compare in terms of performance.  In my unscientific testings:

  • The naive recursive algorithm calculates (t1 25000) in about 3 milliseconds.
  • The threaded sequence processing algorithm calculates (t2 25000) in about 5 milliseconds.

Well, it’s not looking good for readable code right now.  Although the fact that t1 can’t calculate (t1 26000) without blowing the stack indicates that it has bigger problems. 

Jean-Louis suggests an alternative: the tail-recursive implementation**

(defn t3 [n]
(loop [n n result 0] (if (zero? n) result (recur (dec n) (+ result n)))))

Let’s compare this to the original r1 in terms of readabilty:

  • We’re now using clojure functions zero? and dec, which requires a bit more clojure knowledge but reduces noise (and hence code fatigue)
  • We’re using a well-known accumulator pattern.  This doesn’t impose a cost on anyone familiar with how recur is used.
  • We’re still dealing with a branch and a recursive statement that interact.  On the other hand, the recur expression now only goes two deep.
  • We’ve got to keep track of positional parameters.  Not really 

So, in terms of readability, it’s better than t1 but we’d still prefer t2.  However, the figures speak for themselves: t2 can calculate (t3 25000) typically in about 1.5 milliseconds.  As I said at the start, sometimes the most elegant solution isn’t the fastest.  I doubt I could squeeze much more out of the sequence processing approach, although in the real world the application of fork-join reducers may outperform any explicit TCO solution.  However, is it possible to create a much faster implementation if we simply allow ourselves to assume more knowledge?  This time, though, we need more knowledge of our business domain (mathematics) than of our programming environment.

(defn t4 [n] (/ (* n (inc n)) 2))
(defn t4threaded [n] (-> (inc n) (* n) (/ 2)))

That calculates (t4 25000) in 0.1 milliseconds.  Needless to say, it can handle numbers much larger than any of the other implementations without breaking a sweat.  From a readability perspective, again, it’s excellent providing you have the required background knowledge.  The last example may feel like cheating, but the truth is that solutions like that are pretty common in the real world: insight into your problem area can radically simplify your code and improve your performance.

SIDEBAR:  I’m afraid I’m having trouble with the comment system on this site.  My apologies if this is affecting you (it isn’t affecting everyone).  It’s certainly affecting my ability to respond in anything other than a full post.

*although there is a special circle of Hell reserved for key-value pair implementations on SQL

**I should point out this differs stylistically from Jean-Louis’ original implementation, but the performance characteristics are the same.

Code Fatigue

Let’s say you needed to calculate the triangular number of n.  The triangular number of 4 is (1+2+3+4).  Which of the following implementations would you consider the more readable?

(defn t1 [n] 
(if (= n 0)
(+ n (t1 (- n 1)))))
(defn t2 [n] 
(->> (inc n)
(range 0)
(reduce +)))

If you answered t1, I’m willing to bet that by “readable” you meant “requires less experience to read”.  I’m going to argue that this is a bad way of evaluate readability.  Let’s assume for the moment that your command of Clojure is perfect, what are the challenges to comprehension then?

  • The first has a recursive step
  • The first has a branch
  • The first contains an expression that goes three deep.

Worse, each of these interact, meaning you have to hold them in your head all at once.  If you’re trying to solve a problem significantly harder than computing triangular numbers, sticking to “basic” code results in significant more lines of code and significantly more of these things that you have to simultaneously track.  Whilst each individual component is easy enough to parse, the overall effect is fatiguing.  This is bad news for humans, because they’re bad at maintaining mental function whilst processing large numbers of minor items.

Favour High Level Code

Let’s now assume that everyone has excellent command of the language we’re using.  What impedes readability in these circumstances?

  • The longer you need to track the value of a variable, the harder it is to understand.*
  • The more levels of control flow you need to track, the harder it is to understand.
  • The less code you can see on your screen at once, the harder the code is to understand.
  • The more times you see the same code expressions repeated with possible minor variations, the harder it is to understand.

Writing basic code in any language favours the comprehensibility of a single over the comprehensibility of the whole.  Not only that, but since each construct contains the possibility of error, using a basic style is much more likely to result in bugs.  A much better set of guidelines for writing readable code would be:

  • Use values close to their definition.  Make it clear that they are out of scope after that point.
  • Favour standardised control flow constructs such as reduce in Clojure and LINQ in C# over writing everything in terms of branches, loops and recursion.
  • Favour concise code over verbose code
  • Aggressively eliminate common sub-expressions

And next time trying to evaluate code readability, take the effects of fatigue more seriously and don’t worry as much about trying to compensate for lack of experience.

Technorati Tags: ,

*If it’s global and mutable, your chances of tracking it are nil unless you’re extremely disciplined.  Action at a distance is very hard to read and extremely error prone.

Clojure: Stages of Enlightenment.

I’ve tentatively identified seven stages of enlightenment in Clojure sequence processing.

  • Uses recursion
  • Uses recur
  • Uses loop/recur
  • Uses Clojure API functions such as filter and map
  • Uses reduce
  • Uses all Clojure API functions and understands implications.  At this point you can consider yourself a 4clojure 1st Dan.
  • Uses clojure.set as well

There may be higher levels, but Jay Fields hasn’t blogged about them yet.

Technorati Tags:

Sexism in IT

Let’s talk about Larry.  If you’re lucky, Larry isn’t in your team.  But he’s in a team you work with.  You find yourself trying to avoid dealing with that team because there’s a good chance you’re going to end up working with Larry.  Larry is a pain in the neck.  It’s not that he’s incompetent, he just doesn’t seem to care.  Nothing he puts together works, and when it does work it requires settings he forgot to tell you about.  Larry is the bottom tier of men in technology.

And yes, he’s a man.  90% of people in technology are.  What would happen if it was only 50%?  Well, frankly, Larry would be out of a job.  In his place would be a better woman.  Don’t get me wrong, there’s plenty of women out there as useless as Larry, but in a 50/50 world, they wouldn’t have a place in technology either.

We Are The 50%

Let’s talk about how we got to this point.  Women cannot be considered an “educationally disadvantaged minority”*, so we don’t have that excuse.  Computing was 90% male in 1967, when female participation in the workforce was much lower than it was today.   That was after a sexist purge of women programmers in the 1950s.  The gender ratio of computer science graduates in 1984 was 60/40.  So we’ve slid back from the 50/50 dream really quite dramatically.

It’s hard to avoid the conclusion that we (men) are fostering an environment that is subtly hostile to women.  I could spend all day adding to that particular list of links.  We need to stop.  Yes, we, meaning you right there and me right here.  I’ll be honest, it’s hard not to have a sexism bias when everyone you work with is a man.  That means the job is harder, not that it’s meaningless.

Full disclosure: I’ll admit that I’ve always been aware of this issue, but haven’t regarded it as my problem until the birth of my daughter.  It shifted my perspective quite dramatically.  I don’t aspire for her to follow in her father’s footsteps, but it offends me that chances could be denied her because of stupid rubbish like implicit sexism.  We can do better.  Moreover, we need to stop thinking of this as a problem that women have and we don’t.  The exclusion of women in the tech workforce affects us all and we’ve all got something to gain: better co-workers than Larry.  They probably won’t be as brilliant as Grace Hopper but, frankly, neither are we.

Unless, of course, you consider yourself to be in the bottom half of male programmers by ability.  Then you probably want to be as sexist and unwelcoming as possible.

*The observant will notice they’re not even a minority.

Post Script:  If you haven’t read Reg Braithwaite’s article about his mother, you really should.

Technorati Tags:

Clojure Macro: defn-curried

So, the winner of the first Clojure Macro Challenge (magic partial) is Rich Hickey.  Check out the macro defcurried on line 132.  I don’t imagine for a moment he read this blog, it’s just that expressing the reducers library without it would have been an exercise in frustration and obfuscating syntax.  However, his implementation is a bit special-case; it only produces the curried version and only curries on the last parameter.  So I decided to rip off his code and see whether or not I could come up with a more general solution:

(defn- curry 
[[params1 params2] body]
(cons (vec params1)
(if (empty? params2)
(list (apply list 'fn (vec params2) body)))))

(defn do-curried [symbol to-fn params]
(let [result (split-with (complement vector?) params)
[[name doc meta] [args & body]] result
[doc meta] (if (string? doc) [doc meta] [nil doc])
body (if meta (cons meta body) body)
arity-for-n #(-> % inc (split-at args) (to-fn body))
arities (->>
(range 0 (count args))
(map arity-for-n)
before (keep identity [symbol name doc])]
(concat before arities)))

(defmacro defn-curried
"Builds a multiple arity function similar that returns closures
for the missing parameters, similar to ML's behaviour."
[& params]
(do-curried 'defn curry params))

(defmacro fn-curried
"Builds a multiple arity function similar that returns closures
for the missing parameters, similar to ML's behaviour."
[& params]
(do-curried 'fn curry params))

Incidentally, this was written in the LightTable InstaRepl, which is excellent for developing this kind of abstract hack.  The one feature it’s missing is proper destructuring support.  If you take a look above, you’ll see an identifier “result” that only really exists to allow the InstaRepl to process it more easily.

Anyway, I hope someone finds this useful.  I know I will.  After using ML/F#, writing functions that return other functions feels like an anti-pattern.

Best Practices and The Dunning-Kruger Effect

I was recently witness to an interesting twitter exchange between Stu Herbert and Dan North on the subject of development practices.  It occurred to me that the disagreement was fundamentally that they were addressing different groups.  Stu felt that the term “best practices” implied “optional” to too many people who should be using automated testing.  Dan, on the other hand, dislikes the term best practices because it’s devoid of context.

As Dan explained in an old Oredev talk (watch it if you haven’t), the problem with best practices is that their purpose is to drag people at the start of the Dreyfus model up to competency.  However, there’s a downside: enforcement of best practices exerts a drag on people beyond the competency stage.  From an expert’s point of view, everything is optional and is simply a matter of cost benefit analysis.  The problem is, good advice for experts is lousy advice for novices and vice versa.

I Don’t Understand It, So It Must Be Easy

The Dunning-Kruger effect is an observation that, the less competence you have at something, the easier you think it is.  I suspect it’s about to be renamed the “Apple Maps” effect.  Here’s where we really hit Stu’s problem: pretty much everyone thinks they’re an expert, except possibly for the experts.  Everyone with a stand up meeting is an authority on lean and agile.  I’ve seen team after team in my career who thought they had the experience to determine whether or not automated testing was appropriate to their project when not one of them had even tried it.  (In fairness to these teams, most uncoached first attempts at TDD are disasters.)

An Idiot Is Someone Who Doesn’t Know What You Learned Last Week

So, how do you push teams like this along the path of skills acquisition?  Well, usually, you proclaim that something is The One True Way and convince them that, by doing these things, they will be superior to other teams that haven’t embraced The Truth.  Despite having an element of the cargo cult about it, this will actually be true.  You’ve managed to circumvent the DK effect for a while, but it’s not gone.  As with all cognitive biases, they’re never, ever, gone.

If you haven’t ever used an IoC container, TDD or CI, I pretty much guarantee that trying them will make you a better developer.  Usually in ways that you’ll find hard to explain to people who haven’t.  If you’re stuck in the tar-pit, Scrum and other prescriptive agile methodologies will get you further along the path of understanding how to deliver value.  But any rules-based understanding is only half the journey.  Once we’ve climbed the hill, we’re still only at the competent stage.  All too often, we’ve set up camp.  If you walk in any direction, we’re going down again.  But anyone who cares to look can see beautiful mountains in the distance.  Let’s go visit them.

Self Diagnosis

The story of how this blog went down is short. (I rushed something and made a mistake).  The story of how I got it back up is epic. (Anyone who thinks Microsoft tools are easy to set up may be interested in some timeshare opportunities I’ve got available for a limited time only.)  However, a small but crucial part was played by this page.  It’s extremely boring: it just checks that Lucene has the permissions it needs to work.  The page above could have been achieved by a log file, but making it visible front and centre had a great advantage: I could use it to show my service provider what the problem was and give them a way to check that they’d fixed it. (Before this point, it was trial and error.)  It’s amazing how many systems fail when they’re misconfigured without telling you what the configuration problem is.  Diagnostics aren’t about data, they’re about communication.

Technorati Tags:

Live Diagnostics

Anyone who looks out from .NET from time to time will know that our libraries are missing quite a lot that other platforms take for granted.  A decent embeddable web server is one.  Thankfully, the Nancy team have addressed this issue with the Nancy self-hosting engine.  It’s far from the fastest thing on the planet, it’s no substitute for IIS, and it’s not going to give the authors of Jetty any sleepless nights, but it does hit one sweet spot that is close to my heart: live diagnostics.

You see, even if you do your logging and your alerting well, these diagnostics are after the fact and rarely contain detailed enough information to solve certain kinds of problems.  These are the problems where you need to know what’s going on right now and why?  There’s two reasons for this:

  • Typically you don’t have live access to the in-memory structure of the application
  • There’s just too much information. You need some way to drill down.

The too much information problem is serious.  Quite simply, you can’t sensibly log the level of detail for every last transaction you sometimes wish you had for just one or two.  The in-memory problem is so large many don’t even notice it’s there.  Rather than take a look at what their program is doing, they accept that they’re just going to have to theorize about what state it is in and how it got there.  An embedded web server solves both problems.  You might be thinking that this kind of quality control can be achieved by unit testing, and you’d be right, except that you wouldn’t have captured the amount of time it takes to develop a test when you’re not sure what’s wrong.  I recently (successfully) put an automated trading system live, and I would estimate that 40% of the test suite was developed with the aid of the live diagnostics the system provided.

Next time you’re writing a back-end service, try embedding a small web server that just prints up a single page of information about what’s happening.  Once you’ve had a taste, I’m sure you’ll find it addictive.

Technorati Tags: ,

First Impressions of Visual Studio 2012

I’ve used VS2012 for a couple of days now and have been pleasantly surprised.  It’s a lot faster than VS2010, which was an appalling piece of engineering.  The dark theme, my personal preference, is basic but pleasant.  It doesn’t quite make its way everywhere: property pages, for instance are not only dark theme unaware but 100% as ugly as they were in previous version.  The new event log is gorgeous and I’m hoping it’s going to prove useful.

On the other hand, it doesn’t exactly feel finished.  Autocomplete on symbols pops under the function documentation tooltip, a bug that seems to have sailed straight past beta testing.  They’ve also added a well-meaning feature to look up help on exceptions that just doesn’t reflect the way that exceptions are actually implemented in the .NET Framework.  For instance, if you’re having a problem connecting to SQL Server, it’ll send you straight to the general SqlException page.  To fix this, they either need to make the feature smarter, or make exceptions in .NET a lot more specific. 

Oh yes, and unless you read English in a different way from the rest of the human race, you’ll want to read the contents of this page pretty much straight after booting it for the first time.

Technorati Tags: ,

Free Software vs Open Source

Richard Stallman has long said that open source software isn’t the same thing as free software.  Indeed, he’s spent a lot of time educating people about the distinction.  A distinction about which, frankly, few of us care.  Most of us admire his principles, but then get back to producing software for corporations and, as long as it’s open source, it’s fine.

Part of the point is that it’s free at the point of use.  Yes, there are many other advantages, but the simple fact that you just have to say to your manager “can we use this” rather than having to deal with a purchasing decision makes a huge difference to the time to market of anything you build with open source.  It’s not really about whether the price is $100 or $10,000, it’s just plain harder to get commercial software adopted.  Of course, people are always trying to find a loophole in the terms of these licences.  TiVo is the obvious example, which GPL3 addressed.  Even then most firms didn’t worry about the GPL.  Despite the FUD, if you just wrote internal applications and weren’t selling the software to third parties, the terms didn’t make much of a difference.

Then the web opened the mother of all loopholes.  You could run GPL software on the server, and it wasn’t considered “distribution”.  Who’s doing this?  Well, Google for one.  So, the AGPL was born,* that includes the products of your code.  So, you can’t use an AGPL PDF generation software component in your web stack without everything becoming subject to the AGPL’s requirements.**

Again, there are people trying to make money out of open source software.  However, the AGPL provides a new opportunity: the terms are so unacceptable to most firms they might well prefer to pay for the software.  The AGPL is the first license that’s likely to be free as in freedom but not free as in beer.  The phrase “open source and free software” is turning into “free software versus open source”.

People trying to develop commercial open source have a legitimate beef with the community.  So it’s not a surprise to see that some have decided to monetize their reputation*** and have been quite upfront about their reasons for doing so.  Now, you might think “what’s the problem?  No-one’s forcing you to use it.”  And you’d be right, both RavenDB and Lamson can be quietly ignored.  Nonetheless, it’s a pity open source has lost the likes of Zed Shaw.

Somewhat more problematic are the projects that have migrated licenses, like nServiceBus.  nServiceBus isn’t even a library, it’s a framework that most likely extends into most parts of your business critical code.  If you want to upgrade, and the chances are than any successful project will eventually, you’re going to be paying.  The first, and the second one, is free.  The third… well, it’s not gonna cost you anything like as much as BizTalk.  Maybe your manager won’t notice that the “free” library now costs money, but if he does, he’s likely to be asking much harder questions the next time you want to use a “free” library.

You could say that some of us have been leeching off the amazing work done by amazing developers and expecting a free ride for too long, and you’d be right.  Maybe open source software is fundamentally subject to the tragedy of the commons.  But RMS warned us: open source is not the same as free software. 

*I should point out for the sake of accuracy that the original AGPL in fact predates GPL3.

**This isn’t an idle example, iText has moved to AGPL.

***For the record, I think the arguments in the Oracle vs Google case suggest Oren’s understanding of “derivative work” is defective.  Unless Oracle wins, in which case he’s right on the money.