Thursday, September 24, 2009

Evil Considered Harmful

(and in other news, fire is hot, water is wet).

Perhaps I should rephrase the title, and explain that what I mean to say is that "Evil (should be) Considered Harmful". Not evil itself, which is of course harmful by definition, but the use of the term is harmful in engineering discourse.

The wiki definition is "Evil, in many cultures, is a broad term used to describe what are seen as subjectively harmful deeds that are labeled as such to steer moral support." (emphasis mine, of course). Contrast this with terms like "argument", or "logic", or "proof".

In engineering, it's intended to sum up in a single word some combination of bad practices. But what it really does is to suppress thought. It's not terribly well-defined, so what I mean by it may not be what you mean by it. But in general, when I say it about a design or practice, you and all Right-Thinking-Developers are expected to eschew that design or practice without even thinking about it.

Because of the "without thinking" aspect, its use is therefore contrary to the spirit of engineering.

Friday, September 4, 2009

When Can You Say "Test Complete"? (lessons from CodeJam - part 2)

The qualification round for CodeJam 2009 is past, and I've qualified for round 1.

But more importantly, I encountered something which I hope will teach me something... once I figure out what I can learn from it.

The lesson concerns testing.

A bit of background:
In CodeJam, you get a problem statement, which includes a few simple test cases and their expected results. Then there's two sets of data: the small, and the large. To check your results from those, you must upload them (and for the large, you get only one chance).

In this year's CodeJam qualifiers, I got all three problems right for the small input set, but for two of the problems, I failed on the large set.

But to the lesson: I wrote unit tests for everything I did in the CodeJam. My tests covered not only the sample input/outputs they gave, but also specific tests reflecting my understanding of the problem statement and my implementation of my solution to it.

I was therefore unsurprised when for each problem, my "small" input set results were judged to be correct.

But I was really stunned when it turned out that one one, but two of the large input sets had issues.

These issues are not like the one I had on one of the practice problems. These are clearly caused by a much subtler flaw in my implementation. Well, perhaps not too subtle. It might be as obvious as if I'd built a car for which the brakes did not work while the car was turning left... and then run a series of tests on it, all of which passed, and then had the problem surface on the real roads with real users.

Specifics: Watershed

My result set for the large dataset for the Watershed problem was wrong because the method responsible for assigning watershed code letters failed to meet the left-to-right, top-to-bottom ordering requirement on one of the test cases in the large input set.

Remember: it had worked for the examples in the problem statement, it worked for my suite of unit tests, and it worked for the small input set. So somehow, there was a pattern of input data which demonstrated a flaw.

To be able to diagnose this after the qualification round, I downloaded someone else's solution, and without looking at their code, compiled and ran it to generate an output set I could compare with mine.

Specifics: Welcome to CodeJam

For the Welcome To CodeJam problem, my implementation again worked for the examples, my unit tests, and the small input set.

But while processing the large input set, it went into an infinite loop. There's a particular configuration of input characters on which my recursion logic fails - it gets midway through the input, then (correctly) fails to find the next character in the target, but then for some reason, the backtracking fails to work properly. It backtracks to a position it had been in before, so that it loops forever.


Clearly, there's something to be learned from this (other than the obvious - write better code), and that's to write better tests. But how, exactly, to do that, that's a harder lesson.

For the Watershed problem, I'm not entirely sure, but I do think it's likely that I could have looked for configurations of altitudes which *might* have confused my algorithm in this way. I can create one now, but of course I've seen the example which had this effect.

However, for the Welcome To CodeJam problem, I'm completely at a loss as to how I could have created a test to catch this. I tested nearly three dozen cases, explicitly looking for backtracking behavior. None of them turned up this problem.

So the challenge is to figure out how to write better tests - tests which will enable me to say "code complete". And of course, to do so under the time stress of competition.

Monday, August 31, 2009

When Is Optimization Premature?

Avoiding premature optimization is one of those lessons you hear about, and use, but once in a while you forget.

I (re)learned this while working on one of the Project Euler problems.

From my analysis of the problem, it seemed clear to me that the solution would fall in a particular range of the input space. So clear that I set up my program to only examine that range, so clear that even when I got the wrong answer, it took me several minutes to realize that I'd made an assumption, and that it needed to be revisited.

Of course, the trick is always in the details: when is optimization premature, and when is it necessary to get to the solution in time?

This last point was struck home to me with great clarity, because for the very next problem, I didn't optimize early, I didn't take the obvious shortcut, and it blew the time up enormously. There's a huge difference between ON, OlogN, ONlogN and ON** for large values of N.

So when in the development process should optimizations and shortcuts be considered?

Friday, August 28, 2009

Project Euler

Something else I'm doing lately - for fun, to stretch myself, and also incidentally to practice for the CodeJam) is to work my way through the problems in Project Euler.

I haven't gotten very far yet (just fourteen problems as of today), since most of my time today is being spent on prep for an interview next week - for which I'm brushing up on JavaScript and MySQL. More thoughts on those as I come across them.

Observations from CodeJam (part 1)

I've been working my way through the problems from CodeJams past, and discovered something quite by accident.

Due to having made an error I couldn't solve by mere inspection, I got one of the practice problems wrong, and couldn't see the error. My solution worked for the two published input/result sets, but for the downloaded test case, it failed. But of course, the way their engine works, I couldn't see what was wrong.

Eventually, I caved: I downloaded the source from one of the people who got it right, and without looking at their source, used it to generate a solution data set I could compare with mine, so that I could zero in on the source of my problem.

Since there are never any "smart mistakes", it naturally turned out that I had done something doltish. I had suckered myself into using ints instead of longs for a series of calculations (since both the inputs and results were guaranteed to be relatively small (like less than a million). And because of that, some of the intermediate steps in the calculation were yielding wrong answers due to overflow.

Okay, lesson (re)learned: just because the inputs and outputs are small, that doesn't mean that the values in intermediate steps are also small.

But then, curiosity set in, and I looked at the code, and something struck me about it.

So I pulled down several other solutions from top placers. And they all show the same thing:

They're not "doing it right". That is, they're not following anything like current thinking about program design.

Where I (and probably you) tend to have a couple of classes, small testable methods (and the JUnit tests to test those methods), the handful of top performers whose code I've examined tends to fall more in the "one single main" style of coding.

I obviously can't decide that they are inferior coders: they got it right, very fast. But that's exactly what I'd have thought if I'd encountered code like that in a design review or on a bug hunt.

I'm not sure yet what lesson to draw from that, but it's an interesting observation.

Thursday, August 27, 2009

Taking myself literally (though not too seriously)

A few days ago, I wrote to a friend that my reaction to the economic downturn has been to work on making myself more competitive.

I've decided to take myself literally, and compete.

I have registered to compete in the Google CodeJam competition. I've been working through the problems from last year, and at this point it's pretty clear to me that I'll make it through the qualifier, at least.

Beyond that is anyone's guess: it's a tough competition, and I could easily get hammered.

My highest aspiration is to win a t-shirt, but that's a pretty lofty goal: they give t-shirts to the top 500 scorers in round 2 (which is actually the third round, if you include the qualifier).

Last year they had over 7,000 entrants, so getting a t-shirt means beating roughly 6,500 other programmers - most of whom are far more recently out of school than I am. And I won't have to beat them just once, but twice - once to get into Round 1, and once to get the t-shirt at the top of Round 2.

Like I said, it's a lofty goal. But aspirational goals are good for the soul, they say, or at least for your skill level.

Tuesday, August 25, 2009

Detestable Techscreen Questions

I've been interviewing lately, and as you might expect, some questions get repeated by many questioners. Some make sense, if you're trying to give the candidate a softball question to put them at ease.

Frequently repeated softball (perhaps even T-ball) questions include things like "Describe the difference between Java's public, private, protected, and default access levels" and "What's the difference between an ArrayList and a Vector".

But some questions I really hate getting. Of these, one which stands out is "Java's parameter passing: by value or by reference?"

It's not that I don't know the answer. I do. The problem is that most people who ask the question don't know the answer. It's one of those things that everybody knows, but what most people know is wrong.

You see, the standard, everybody-knows answer is: "primitives by value, objects by reference". Clear, simple, and brief. Altogether an admirable answer, except that it's wrong.

Not completely wrong, but subtly and importantly.

Here's why: in reality, all parameter passing in Java is by value.

That answer confuses people who quite rightly notice that given an object as parameter, a method can make changes in that object which are available to caller once the method has returned. Which proves that the method has a reference to the object. True, but it's a copy of the calling method's reference, which is very important.

You see, pass-by-reference is not the same as passing a copy of a reference value.

That's why I said it was a subtle difference. The reason I said it was important is that the fact that it's a copy means that although the method can make changes to the state of the object by use of its public methods, it cannot replace or delete the object.

I don't mean that you can't write the code - it's not a compiler-enforced immutable value. It's quite legal to write:

public void theMethod (SomeObject obj) {
obj = new SomeObject(...);

But on return from theMethod, caller still sees the original object. This is because the method was operating on a copy of the reference.

It's why you can't write a swap(obj a, obj b) method in Java. Or rather, you can write it, but it fails: on return, a is still a, and b is still b.

In the end, it's almost a no-win question. I obviously can't give the wrong answer, but it's all too common that when I give the right, complete answer, the interviewer hears what they think is the wrong answer and stops listening or can't comprehend the explanation.

You might think that's not very likely, but sadly, this is more likely than you'd like to hope: I know for a fact that at least once I failed to get a position because the interviewer didn't like my answer. The feedback I got through a former colleague was short and pungent: The techscreener, to whom I gave the explanation above, reported that: "He(that's me, kids) seemed sharp, his experience is perfect, he communicates well, but then it turned out that he doesn't even know how Java passes parameters. We're going to pass.".

And this misunderstanding is pernicious. Even Neil Gafter (who you'd think would know better) said in a 2003 interview that "for reference types, they are already passed by reference", which is subtly wrong.

For interviews, I've settled on the following:

Most people will say "primitives by value, objects by reference".

But really, that depends on how you're using the phrase "pass by reference".

If you mean the formal CS sense, then all parameter passing in Java is by value (or by copy, if you prefer). But for Objects, the value of which you get a copy is the caller's variable's reference to the object.

This means that you can operate on the object in the method by accessing its public methods and members, but you cannot replace it.

It's still too long, but it's true and should at least not trigger the automatic mind-closing reflex. I hope.