Linear time suffix tree construction

I needed (well... really really wanted) a linear-time online suffix tree for a project (linear time construction, specifically), and since that sort of thing isn't off-the-shelf it took some time and wrangling to put one together. I eventually started from scratch three times before I got the solution I wanted (i.e. one which is actualfax linear time construction and which always builds a correct suffix tree).

I implement advanced and specialized data structures and algorithms for fun, but I found Ukkonen's algorithm for online linear time suffix tree construction challenging to implement correctly, and it took some hours. It's not too hard to get an implementation to *usually* work, but if you want it to *always* work, there are a number of cases you have to consider carefully. I tend to try to work from original papers - read what the designers had to say and go from there. This is usually very effective, and I get a strong grasp of the problem and the author's solution, but with this paper a number of steps and cases were omitted. I was disappointed to discover this and it took time to determine what was missing and fill in the gaps in a manner consistent with the algorithm designer's intent. Here's Ukkonen's paper: https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Eventually I looked around the net to see how other people have dealt with this, and sure enough it does seem other people have encountered this before. Some explanations are out there on the net, and some implementation are available, some of which may work. Others definitely don't. I'm pretty confident in mine - certainly, it did everything I needed it to do, and passes a variety of tests.

This is a fast algorithm, though it dances around memory a lot - there's no cache awareness, no effort towards memory locality, that kind of thing. And the expansion over space is pretty dramatic: the in-memory suffix tree is likely to be many times larger than the original document, depending on its entropy. I'm noodling on ways to improve this, arranging the tree to reduce cache misses so it's even quicker to build and perhaps a bit more compact in memory overall.

The linear time suffix tree is here on GitHub, along with some other things I've had fun building: a union find, a burst true, burst sorter, tries, a cuckoo hash, etc. Enjoy.

Challenge

Challenges can be big and architectural or big and in the details. Here's an example of one sort of thing I like to do, which is here - that's a C# implementation of a Cuckoo Hash. I used a three-table approach, which allows my drop-in replacement for .NET's default hashmap to be substantially more memory efficient - using about half as much memory to hold the same amount of data with the same access patterns. That means a single server can store twice as much data, so for many applications you'll need half as many servers. At scale, that's a big savings, all for focusing some effort on one little data structure. Also in that project there's an implementation of a burst sort, the only one for .NET last I looked, which is the fastest known way to sort lots of strings in memory - my implementation is about 50% faster than quicksort, the default string sorting algorithm. For certain applications that's a gigantic savings. For most purposes, the default is good enough. I care about when it's not. To get these kinds of results you have to worry about things most programmers ignore, if they know about them at all, like cache lines and instruction pipelining. But I've always felt that to accomplish great things, you have to know how things work all the way down.

Burst Sorter in C#

I wrote a preliminary Burst Trie implementation for Burst Sorting strings. It's available via MIT license on GitHub. At this point it's running about 30% faster than Array.Sort() for sorting arrays of strings representing all English words in Shakespeare's plays; its relative performance will vary depending on the number of strings you're sorting, but generally the larger the set the better off you are using a burst sort than a more traditional sort.

The built-in System.Array.Sort() method in .NET uses quicksort, heapsort, or insertionsort depending on the data; burst sort can beat these due to its cache-locality awareness.

I used these materials to learn about burst tries and burst sorting; I am indebted to their authors:

Cache-Conscious Sorting of Large Sets of Strings with Dynamic Tries
Burst Tries, A Fast, Efficient Data Structure For String Keys
Engineering BurstSort: Towards Fast, In-Place String Sorting

Please note that this code may not be exactly production ready for you: your mileage may vary and I'm continuing to work on it. I did not consult any existing source code; this is written from scratch. If you want to use it, make sure it behaves the way you expect. Feel free to reach out to me at pmcculler@gmail.com to ask questions or provide feedback, and of course, you can do the fork/pull thing on GitHub.

Up next for this project are some more correctness tests (yes, there are tests now!) and exploring various performance improvement possibilities, including sub-bucketing as described by Sinha and Wirth in their Engineering BurstSort paper, use of unsafe code, and implementing a Patricia burst trie (as far as I know, nobody has done that), and a number of minor todos scattered throughout the code.

There may be a pretty obvious question which is something like "if you're that concerned about performance, why are you using C# and not C/C++?"

1. Most performance improvement comes from algorithmic improvement, not point-optimization. Example: running a loop N times instead of N^2 times is better and better the bigger N gets, even if you make each iteration substantially more efficient in the N^2 version.
2. After the .NET JIT compiler gets done with the IL, similar code is approximately as fast in C# as in C++. You're free to argue with me on this but it's not going to be fruitful; we're talking a few percentage points, not 3x differences. I'm reasonably cautious about avoiding obvious problems here.
3. People use C#. A lot. C++ is great but it can be a bit of a bear for some problems, so it's handy to have this.
4. There doesn't appear to be any C# implementation available anywhere else, so there is novelty value.
5. I get to do whatever I want with my time. ;)

Patrick

Posting a couple of basic text tools: suffix array, trie

I extracted a couple of data structures I made for some personal projects and put them on GitHub.

One is a basic suffix array, another is a basic trie. Maybe they will be useful to you.

I'll add more over time or if asked - I have various other things here, like a patricia trie, a fractal trie compressor, a shortest common superstring / supersequence calculator. The SCS algorithm was actually kind of fun to build; getting it to run in a reasonable period of time was tricky. I wrote it to create a superstring for an extended English dictionary of 240K words, and it takes about 20 minutes to do that (unparalleled).

My greedy algorithm superstring of a 2,457,521 character dictionary is 1,858,802 characters long, about 75% of the simple concatenation. Greedy algorithm results are usually within a small constant multiple of the optimal shortest superstring, according to widespread research, so the optimal might be 1/3rd as large, but it won't be 1/9th. Don't really have np-complete time on whole dictionaries to make sure though.

The superstring was so I could compress tries a little more than patricia and fractal will allow alone; instead of holding a string of characters in each node, there's a pointer into a dictionary superstring and a length. There's a tradeoff in cache locality of course. In practice it didn't actually save much memory - the patricia node character runs were generally too short. I think real space savings would appear if I created a superstring for all node contents instead of all original words. There's not a lot of room for improvement with 240K-word tries, so I haven't done that yet. All English words from the Google 2012 corpus is going to be another story.

"...I have not done interviews for quite a while was hoping to get some guidance/advice from you on the best approach."

I am well and hope you are too!

Here's my general approach when I'm looking.

• First thing I do is pull out a copy of Programming Interviews Exposed and work through the examples. Makes my mind sharp for interviews and helps substantially when I'm asked coding questions. 
• Update LinkedIn & resume with current position, including all the latest appropriate buzzwords. 
• Update past work in resumes & LinkedIn so it uses cutting edge words that weren't in use at the time, like 'big data' in 2005 or something like that. 
• Update LinkedIn every day in some way so it comes up in recruiter searches (LinkedIn is actually a first stop for most recruiters at this point). 
• Look at what contacts are doing and ask about opportunities. Probably have to ask a LOT of people, and honestly the careers page of their company's website is probably a better source of information. May be able to get a referral in though, getting through the first step of the gauntlet automatically. 
• Look at the start-up scene in the Seattle area, several ways to do this. 
• Check out the major companies with local presence such as Facebook, Twitter, etc and see what they are up to, submit to anything looking good. 
• Contact any recruiter who's written to me or I've worked with before and let them know I am available starting soon or now (they love immediacy). 
• Look at the boards i.e. http://careers.stackoverflow.com/
• Sign up with TheLadders. See if they still have a free resume assessment service, that was useful (cursory, not the whole assessment, but a gloss that I found useful).
• Consider getting a premium LinkedIn account. Seeing everyone who visited me and the like was nice when I was looking.
• Stay relaxed and focused during interviews. People are there to judge you, yes, but you never have to see them again. Who cares what they think. You're getting interview practice, free coffee, and the possibility of a new job. All good things, no downsides that you don't bring to the table yourself.
• Consider practicing an interview with someone, even a family member.

I always consider the first interview I have when i'm looking to be a loss - it's rarely a good outcome. Just getting into the groove of it. So maybe interview at a place you're not terribly interested in, for a job you're overqualified for, if you can get such an interview.

People look for 'passion' as much as for skills. I don't know why or what this means, except showing some excitement for new techniques and talking about ways you innovated or at least really cared about working on some product. Highlight all the best things, there's no reason not to. Think about this ahead of time.

That's all that comes to mind. I wish you luck! There's a killer market for great devs out there, so as long as people recognize that you have the skills and a passion for making products awesome, I suspect it will work out well.

A new book: epistemology and metaphysics

In case you wondered what I do with my spare time, I wrote a new book. It's called "What Am I?" and it explores essential ideas in epistemology and metaphysics through a simple fantastical parable. It's lighthearted and should be a quick, fun read that will make you laugh and think.

What Am I? - on Amazon

Feedback graciously welcomed.

Patrick

A better and easier work life

Many people are unhappy at work. It doesn't have to be that way; a few key behaviors and perspectives will make your work life better and easier.

• Take pride in your work.
• It's sad when you don't. Those of us who care notice.
• If you can't bring yourself to care about your work, quit.
• Fulfill your responsibilities.
• Among other things, it hurts other people when you don't. Not just you.
• Only sign up for work you are sure you can do.
• If you feel obliged to sign up for things you can't do, quit.
• Do not take responsibility for anything that is not in your purview or the responsibility of a direct report.
• If you are held accountable for others' failures, quit.
• Do not feel responsible for others' failure to do their work unless they report to you. You must be able to assume that other people will do their jobs.
• If this is not practical in your role, quit.
• Do not ever lie.
• Lying is: intentionally creating or persisting in another person a view of the world that does not match reality. This conceptual error may be harmful to them, and you should not presume to know what will hurt others and what will not.
• It's disgusting. You're not a four year old. (If you are a four year old, write me at pmcculler@gmail.com and we'll take it up offline).
• A poorly considered work estimate is usually a lie.
• If you feel obliged to lie, quit.
• As a manager, your team is your work product.
• Make them powerful.
• You categorically cannot be successful when your team is not.
• If you are not rewarded for just and only this, quit.
• Tell people what you are doing and how it is going.
• If you're not regular and explicit, you are misleading them.
• Expect and reciprocate cooperation.
• Cooperation is expected and necessary and should be natural and easy.
• If cooperation is painful, quit.
• Coordinate with your broad team to make sure all scenarios and processes actually work.
• If no one cares, quit.
• Do beat yourself up over failures, exactly until you get the message.
• You are the only one who can do this effectively.
• Get better at your work over time.
• The straight odds of being in the top 1% of your field are 100:1. Do you work 100x harder than 1% of your colleagues? 50x harder than 2%?
• Use your curiosity.
• Things you don't know are always the ones that wind up hurting you.
• ... and helping you.
• Look for a better way.
• The odds you're doing it the best way you can with the resources you have are miniscule.
• If your manager insists that you do it badly anyway, quit.
• Prompt for and accept feedback.
• Most of the feedback you get will be clandestine, implied, or third hand. Find it.
• If you never receive any positive feedback, quit.

You've noticed many "if... , quit." imperatives. Yes. You can be successful, and life doesn't have to be horrible. Work to improve your situation, but remember that you are in an environment that is also a self-perpetuating system. Not all environments will respond to your sincere, thoughtful, and persistent attempts to improve them. Ultimately, you can control yourself, not your environment, but you can and should look for better environments to inhabit, thrive in, and improve.

The 300x Challenge

Could you be 300x more productive?

Although the usual sources are apocryphal, the evidence is clear that individuals and teams vary in productivity over similar domains by 1,000% or more. Supposedly, Google has calculated an individual difference of up to 300x between average and maximum productivity in technologists (such as software engineers).

A 300x difference is worth a pause. This sort of difference would imply that a maximally productive software engineer (in the Google model) could accomplish in one year what an average engineer would require three centuries to complete. A gross oversimplification, but illustrative.

We should find out what causes it, as you can imagine what it would be worth to create productivity like that. Any large company should be willing to spend billions to broadly implement such a change. So what could cause this enormous difference? A real answer requires careful measurement, but there's some value to a conjecture and narrative to get us started looking in the direction of an answer.

I tend to think in terms of teams of engineers working together, so I'm going to switch the focus from the individual to the team, and apply the same productivity amplitude. This seems appropriate.

Here are my raw thoughts on the matter. A 300x team:

1. Never builds anything they don't have to.
2. Rapidly constructs working software.
3. Avoids distraction.
4. Changes direction without friction.
5. Does not spend time resolving bugs.
6. Does not redesign and rebuild software unless they have to, and they almost never have to.
7. Perfectly distributes tasks to the most qualified team members.
8. Ships software instead of sitting on it.

How could it be done?

1. Never builds anything they don't have to.
• Because they use third party software whenever possible.
• Because they know what's available.
• Because they invest time in learning.
• Because they have a broad network of advisers.
• Because they have the budget to buy software.
• Because integrating third party software is easy by technical means and policy.
• Because they delegate or contract out everything they don't strictly have to build.
• Because they only work on the most important problems.
• Because they have a crystal clear understanding of what's needed.
• Because they understand the purpose of the product.
• Because they understand the customer.
• Because they have a perfect feedback loop.
• Because they have an expert product manager.
• Because they do not spend time on anything not strategically critical.
• Because they understand the strategy.
• Because there is a clearly articulated strategy.
• Because there is a strategy.
• Because there is an expert strategist.
2. Rapidly constructs working software.
• Because they adopt good designs quickly.
• Because they are expert designers.
• Because they get assistance from professionals and domain experts.
• Because they networked.
• Because it's facilitated.
• Because there's a facilitator.
• Because they understand the problem domain.
• Because they draw on a deep pool of atomic concepts.
• Because they have deep computer science knowledge.
• Because they write working code quickly.
• Because they are expert coders.
• Because code once written is always known to work properly.
• Because it's thoroughly, automatically tested.
• Because they invest in testing.
• Because the team includes testing specialists.
• Because code reviews.
• Because the team trusts itself.
• Because integration is simple, quick, and painless.
• Because components are not developed in isolation.
• Because they have all the skills they need.
• Because strong hiring.
• Because investment in skill acquisition.
• Because product design leans on existing strengths.
3. Changes direction without friction.
• Because they ignore sunk costs.
• Because they can change or reset development environments instantly.
• Because they have the most advanced dev and test environments available.
• Because they invest in tools and environments.
• Because they keep their eyes on the prize, not the intermediate terrain.
• Because they measure themselves.
• Because they have a target.
• Because they can pick up new ideas quickly.
• Because they have strong fundamentals.
• Because they have training, coaching, and mentoring support.
• Because strong management.
• Because they teach themselves and each other.
• Because strong hiring.
• Because trust.
• Because they quickly abandon dead ends.
• Because they watch for them.
4. Avoids distraction 
• Because production problems are minimal.
• Because specialists can deal with production problems.
• Because there are few to no production problems.
• Because the software works.
• Because testing.
• Because not taking shortcuts.
• Because there are early warnings before problems become expensive to fix.
• Because the software has built-in monitors.
• Because they use they use the most advanced monitoring and alerting systems available.
• Because it's trivial to deploy and un-deploy.
• Because they focus on the problem domain.
• Because office life is easy.
• Because office politics are minimal.
• Because disputes are resolved immediately.
• Because facilitation.
• Because strong hiring.
• Because strong advocacy.
• Because everything but excellence is flexible.
• Because they organize their continuous experiences around efficiency.
• Because they use absolutely minimum process.
• Because unnecessary process is periodically stripped.
• Because they classify process as necessary or overhead.
• Because professionals need little process.
5. Does not spend time resolving bugs.
• Because there are no bugs.
• Because they were caught in design.
• Because design review.
• Because collaborative design.
• Because they invest in design.
• Because they were caught in development.
• Because collaborative development.
• Because testing.
• Because there's a minimum amount of software that could have bugs.
• Because they built the minimum amount of software.
• Because developers take every bug personally - but forgive themselves.
6. Does not redesign and rebuild software.
• Because they designed it to meet strategic goals.
• Because meeting strategic goals usually requires new software.
• Because the team prefers patching to rebuilding.
• Because they know that rebuilding is usually more expensive.
• Because they never forget anything.
• Because communication.
• Because written communication.
• Because simplicity.
7. Perfectly distributes each task to the most effective team member.
• Because planning and adaptation.
• Because the team knows its skill structure.
• Because the team passes work items around without friction.
• Because trust.
• Because it's facilitated.
• Because status is transparent.
• Because trust.
8. Ships software instead of sitting on it.
• Because they release all the time.
• Because it's almost dangerously easy to release.
• Because they are confident it will work.
• Because testing.
• Because they care about customer happiness.

That's quite a list. Some of the items may be unachievable. Is it enough? Could an 'average' team become 300x more productive if all these were abundantly, lavishly true? Could a team of 4 developers, with a support network of product managers and associated staff, finish in one year what it would take Joe/Jane Average SDE and staff a thousand years?

Fractal tries: the compression algorithm

This is a description of the algorithm for transforming patricia/radix tries into much smaller fractal tries.

Here is a patricia trie that encodes the words Cry, Car, Cart, Dry, Dart, Hart, Hi, Hit, Far, and Fart.

The algorithm runs in a single depth-first traversal. It creates a lookup table, then attempts to calculate a hash for each node in the tree. A node's hash exactly accounts for its entire subtree (it and all its descendants). Here are the first steps illustrated:

Now our table has a hash and reference for one subtree, [RY].

(There's an extra dashed red line here you should ignore.)
Graying out the finished parts and moving along, it continues to try to calculate a hash for C node by descending to its next child (node that while I never show more than two children on these diagrams, thus left/right, tries can have any number of nodes, so it's really 1st child, 2nd child, 3rd child, and so on). This leads it to the T leaf and then it ascends:

 Now it has stashed the whole AR:T subtree; while not shown, the hash includes the fact that there is a word termination at the AR node; this prevents non-terminating but otherwise similar subtrees from matching it later. The algorithm continues to complete the C node subtree, then moves on to D node:

Where at this point it encounters the first entire subtree match with a previously encountered subtree. It abandons the "repeat" subtree and moves the parent node's pointer to the tabled subtree, leaving it looking like this:

And we have pruned away a leaf of the trie without sacrificing any knowledge of its structure. Now we'll skip ahead again. We're pruned away an ART node and a T node, and then we have an opportunity to prune an entire subtree:

We find in our table that the AR:T subtree under F exactly matches the AR:T subtree under C, so we immediately redirect. We recurse to the top of the tree and drop the auxiliary table. Then the final trie looks like this:

This trie has the same word structure we started with, and no additional elements in memory. The original patricia trie has 22 letters in 14 nodes. The final trie has 13 letters in 9 nodes. For large tries, the space savings can become quite substantial, sometimes a 3x to 5x difference.

Squeezed tries: fractal compression for words

In this post I explain fractal tries, why I needed to design them, and how they work, with a link to rough prototype code.

Recently I was exploring the new art of culturomics (word crunching, really) and went to load Google word data sets into memory so I could screw around with them. Immediately this presented a problem, because there are a lot of words in Google's word lists. Example: they have 28,771 words that begin with Q. I want to do fancy letter magic, but it's hard to even fit these words into a reasonable amount of memory, much less organize and search them. So I did the obvious and built a trie.

For the sake of quick testing, I used a data set a little smaller than Google's, "Yet Another Word List", with a respectable 264,061 words including 2,457,521 letters. The obvious method of storing these words in memory is like so:

With that arrangement, all letters are represented for all words; it's a simple array of strings of letters. A straightforward, traditional trie arrangement improves on the situation. It uses 586,511 nodes with 1 letter each. Here's a chart that shows how tries store words; on the left is a complete trie for the word "car" alone, while on the right is a complete trie for the words "car, cat, cart, and dart" as in the example above:

In this data structure, all words share as much of their prefixes as they can. A word is indicated in the trie by either ending at the bottom, or having a checkmark/flag to that effect. With such a data structure, you can quickly check for the presence of a word, or reconstruct the whole word list if you choose to.

So there's certainly a savings in terms of total number of letters stored, 76.1%. Unfortunately, each node to node link requires memory, so we actually wind up losing over half a million bytes of RAM compared to just storing them in an array. On the positive side, many different operations such as searching are pretty quick on this data structure. But I needed to fit more words into less memory, so I moved on to another data structure, this time writing a patricia trie, aka radix trie. Here's a chart that shows how patricia tries store the same words used in the previous example:

This chart is not drawn to scale. ;)

In a patricia trie, 'lonely' nodes are minimized. Whenever possible, nodes in the tree that don't need to be separated are collapsed into single nodes with more than one letter in them. This means we store just as many letters as in a regular trie, but we use fewer nodes. In this case, the patricia trie uses the same 586,511 letters but stored in 325,845 nodes, so there is less overhead. We can actually start to see space savings at this point, but not very much.

It seems a little silly to say it this way, but it's truthful and important to note that the purpose of a data structure is to preserve the structure of data. Words are structured in such a way that they frequently share prefixes, so the trie preserves this structure while saving memory space by 'folding together' the beginnings of each word. Each individual word is still represented and recoverable because all the paths through the trie from the root end in a real word.

Words often start the same way (car, carb, carbuncle, carbuncles) but they also often end in predictable ways (preserve, reserve | rested, bested, feasted | least, beast). This highly repetitive structure lends itself to 'folding together' as well. That lead me to the data structure I built next. Since it depends on eliminating self-similar branches all across the trie, I'm calling it a fractal trie (arguably this is an unfractal trie, but whatever):

The first two tries look just like patricia tries, because those word sets do not share suffix structure. With the third fractal trie, we see the trie re-uses an existing node rather than branch out to a new one. The fourth trie shows this continued. But fractal tries can fold over entire suffix trees. For example:

This fractal trie makes extensive re-use of both prefixes and suffixes. The trick, if you like, is in creating such structures in a reasonable amount of time. After consulting with a friend, Ian Bone, I found a method that runs in O(n) linear time. (It's entirely possible that he actually told me how to do this, but I was too dense to realize it at the time, and had to struggle with it for another couple of hours anyway. Thank you Ian.)

When applied to the yawl word list, an implementation of fractal tries creates 65,333 nodes including a total of 145,271 letters. That's a 94% savings in letters stored over the flat string array, and even including the overhead for 65,333 nodes it means a substantial memory space savings when implemented in any reasonable language. (yeah... lots of popular languages are not reasonable in this sense.)

I expect someone else has created data structures like this, and at some point I'll track that down and post an update here with a name and references. In the meantime, I'm happy I designed a data structure that meets my needs. I slammed together a prototype in C#, which due to memory overhead is not a reasonable language for compressing with tries. In C++ it will be much more space efficient by default, there are a variety of optimizations available, and I'll clean up the API.

Write Code to Forget: 15 Relatively Specific Tips

[This is a rewritten and much improved version of a previous, now excised entry.]

A professional programmer builds up a large body of code, hundreds of thousands of lines.

Code has a strangely unpredictable lifespan. Off-the-cuff code can sometimes live and breathe for decades, while other carefully planned and meticulously constructed code may never see sunlight. As long as it lives, or might come back to life in a product some day, you or some hapless programmer that follows you will have to live and deal with it.

Your body of code - call it your corpus - demands time and attention. Every day, week, or month, its maintenance needs pull away a little of the time that you could otherwise spend on exciting new software. As the body gets larger, it demands more and more time. How much more is largely under your control - you can build it upfront to either rest easy, or come to life and harass you constantly. Like zombies.

Take a simple measurement, such as the number of seconds you spend per line of code in your corpus per month. Probably a small fraction of a second, so it might take 50 or 100 lines to add up to one second per month. That's time you don't get back and can't spend on more interesting things. You could actually measure this, but it's only necessary to understand that you could measure it, and the phenomenon is real. Your body of code siphons your available time.

Some of that siphoned time is simply wasted. When you must revisit code you've already written, and you're not actually adding features, it's wasted. Examples include:

• Bug fixes
• Technical debt payment
• Code cleanup, reformatting, etc.
• Re-familiarizing yourself with the code
• Patches and security improvements
• Adding unit tests
• Adding support for integration tests, new test frameworks, etc.
• Nailing boards to the windows so zombies have something to take apart while you whack at them semi-helplessly with baseball bats, chairs, cashmere sweaters, etc.

Some time spent on the corpus is valuable and not wasted. Examples of useful time include:

• Strictly adding new features
• Teaching the code to someone else
• Automated static analysis

As you can see, I think there are few legitimate reasons to revisit code. My rule of thumb is "if it's creating new value for customers - and not in the form of fixing mistakes - it's productive". Otherwise a revisit is just a distraction you might have prevented; the code base 'coming back to life' to attack your productivity.

The more likely a body of code is to cause wasted time, the higher its 'zombie factor'.

Low Zombie Factor Coding Practices

Assume the next programmer will not be as smart as you are, so code for slightly-dumber-than-you. This has the effect of producing code with a lighter cognitive load, so programmers can interpret and manage larger chunks of code in situ. That makes it easier to maintain and extend over time. When you return to look at the code you wrote after 16 months, you'll be happy you made it easier to understand, too.

Use unit tests. If you can't prove your code works, it does not work. There's really no need to defend this position, so I won't. For goodness' sake, if you're not writing unit tests, start writing them the next time you open up your IDE. Write a primitive test. You don't even need a framework. You'll feel good immediately.

Consider test-driven development. This technique is not as widely followed as unit tests, and experienced developers often tell me that they know perfectly well how they need to build a class, interface, etc., so building it piecemeal is a waste of time. That's a compelling argument. Still, many report success and happiness with this.

Give code to the customer as soon as possible. This is a powerful idea, wrapped up in a methodology sometimes called continuous delivery. It minimizes the "shelf life" of code - how long it sits around doing nothing for customers - which customers appreciate and costs less. It also exposes problems quickly. The longer a particular problem is buried, the more it's going to distract you to fix it. Corpses rot. Or corpuses. You get it.

A corollary to giving out code as soon as possible is to optimize your build and deployment process. If it takes a week to build, test, and distribute your product, it really doesn't matter that it took you 90 seconds to find, fix, create tests for, peer review, verify, and check in a fix. You'll be whacking at that zombie for a very long time.

Anticipate and circumvent threading problems. Avoid threading any time you can. Use patterns such as Immutable Objects to minimize exposure to thread interaction issues. Have an expert evaluate your threading code. And defensively put in synchronization even if you don't plan to multi-thread. Yeah, there's a slight performance penalty. Consider this question carefully: are you worried about that?

Branching considered harmful. Use techniques such as the Null Object pattern to minimize the paths and forks your code can take. Each fork is something your unit tests might miss, and each path potentially unused, or rarely used. Rarely used code paths breed bugs.

Permanently kill off dead code. Bugs love to breed in this stuff. If code isn't doing anything, if it's commented out... aggressively get rid of it. Your source control system will hold onto it on the remote chance you'll want to use or consult it again, which, honestly, you won't.

Manage comments as well as the rest of your code. Delete comments which describe something patently obvious - they unnecessarily add to a reader's cognitive load and have to be maintained. Keep and expand comments which explain references to unavailable source, non-obvious or legacy techniques, names of fundamental patterns used, and comments used by parsers and static analysis. Ruthlessly destroy outdated or incorrect comments, even in code you don't feel you own. They waste serious time and cause bugs.

The compiler is your best friend. Do everything you can to let it help you find bugs. If you're bypassing the compiler, or using loose types when you could be easily helping the compiler help you with stricter types, just stop that. Loading a dynamic type? Anything that references a class as a string name is totally not OK. Just don't do that, unless you also build a static analyzer that verifies it will continue to work forever.

Design your software before building it to whatever extent is possible. Model your design with tools that help you prevent further re-work in the future, such as threat modeling and failure mode analysis. It's surprisingly quick and easy and your software is better for it. That's a good deal.

Assume failure. Any given operation may fail, and your code should be robust enough to recover, isolate, report, or appropriately ignore as many failure modes as possible. Things go wrong when software runs, so assume that everything which could go wrong will. I.e., you won't be able to open that file you just created (thank you virus scanners), or your allocation of a 4-byte heap variable will fail. Plan ahead for these things.

When totally unexpected things happen, your software will thrash and die anyway. A failure mode you have to consider is that the software you built is flawed in unknown ways. When unexpected, unrecoverable problems happen, do yourself a huge favor and make it trivial to pinpoint and reproduce errors. Use exceptions, logging, transactions. Label your error messages with GUIDs. Use every technique you've ever heard of, and innovate on this, so when your corpus does come alive, you know exactly where to shoot it so you can re-bury it and move on quickly.

Use machines to help you test and find bugs. You, or a dedicated tester, will not write tests that hammer every possible input into a non-trivial method or program. You just don't have time. So buy yourself some extensive coverage by investing in fuzz-testing technology.

Fear and avoid zombie-awakening patterns and and interfaces. Some software, such as document parsers, are both difficult to get right and security problems waiting to happen. Design your software not to need them, or if you do need them, write as little code as possible. Take off-the-shelf, well-tested, trusted software components and use those. Of course, you should be doing this anyway. Do it double for anything known to cause problems in general or for which your experience tells you that you, your team, or your organization are more likely than average to get wrong somehow. Then assume it's badly broken and put fences and barbed wire around it, metaphorically speaking. Unless you have fences and barbed wire readily available, then feel free to go literal.

Write software you can forget about, that isn't going to come back from the grave and interrupt the awesomely cool and revolutionary stuff you really should be working on. Because you're good, really good, and wasting your time is criminal.

Patrick

5 Résumé Details to Never Read Again

Any manager who works for a growing company, especially in the tech sphere, knows that hiring is an ongoing task. You have new needs to fill, people leave for greener pastures, or you just finally fired an incompetent employee. You sigh, imagining the stack of résumés looming in your near future.

You know that it’s illegal to discriminate when hiring—against women, people of a certain color or religion or age, and more. “I’d never do that,” you think. Alas, even the best of us have trouble keeping subtle discrimination at bay, putting any hiring manager at risk of a lawsuit or simply narrowing the talent pool unnecessarily. So here’s how to keep bias out of your hiring decision.

Studies show that nearly everyone has biases, and that we usually don’t know we have them. These biases harm our decisions and may be the root of subtle but real and even pervasive discrimination. They often operate below the surface of conscious thought, so you may not even be able to detect them as they happen.

Problematic biases start with the first things you learn about a candidate, usually in the résumé, and may stop you from going any farther. Without ever noticing it, you might reject one résumé and proceed to interviews, but accept another otherwise identical résumé—identical but for a few details that trigger associations and biases best kept away from your decision. You may lose out on great candidates before you even get started.

The best protection against accidentally discriminating, inappropriately or illegally, is never knowing the information in the first place. Sure, at some point you will inevitably know the race and probably the sex and approximate age of a candidate, but the longer you avoid knowing it the better and clearer your decisions will be. With a little preparation, you can avoid it from the point of first contact.

How? Take some information out of every résumé before you look at it. Of course you’ll have to draft someone else to do this, or ask your sources or candidates to do so. The benefit is that you won’t see bias-triggering information before you’ve made a decision on whether to proceed with a candidate, and what’s more, stripping out that irrelevant information will help the important things come into focus.

You or a third party can redact résumés in common electronic formats such as Word and PDF documents without much difficulty. Word documents can be directly edited and saved. For PDFs, in Adobe Reader you can highlight a section of text, right-click on the selection, choose properties, and change the highlight color to black. The data is still technically in the document, but all you need to do is hide it from sight. Place a comment next to the text with any substitution you want to make, as suggested below.

Here are five kinds of information that often appear on résumés that you can safely remove before seriously examining them.

Name

Names are packed with information about sex and ethnicity, social class, age, and more. Studies demonstrate that people form ideas about a person’s likeability and the tendency to hire based on just a name. You don’t need to know any of this to make sound decisions, so replace names with neutral random identifiers.

Citizenship

Unless you legitimately require particular citizenship, it’s illegal to discriminate based on nationality. More obviously problematic than names, the information is nonetheless often stated or easily inferred from many résumés. Remove it when you can.

Of course there’s no hiding the fact that IIT Madras is in India and Ecole Polytechnique Fédérale de Lausanne is in Switzerland. Attending school in a country doesn’t mean you’re a citizen, but it’s an easy assumption to make because it’s usually true. It’s valuable to know that a candidate attended a prestigious school, but you might substitute “top 50 school” or “top 500 school” to learn what you need to know to make a sound decision.

Year of graduation

Ageism is an insidious aspect of the workforce and manifests strongly in the recruiting process. While it’s common and usually appropriate for candidates to say how many years of experience they have with the techniques or technologies relevant to the job, it is never necessary to know, when looking at a résumé, exactly when a person graduated. It’s too easy to infer age. While an older candidate may have recently graduated with a germane degree, he or she is more likely to have obtained a degree long ago, and the graduation year is a dead giveaway. Ask for a year of graduation later, when you need to conduct a background check.

Specific dates of employment

Specific dates show gaps. Readers notice gaps in employment history automatically, and that leads to speculation. A year-long or multi-year gap could be a sign of time off to raise children, indicating the candidate’s familial circumstances. It might also indicate unemployment due to any number of other reasons, but how could you know which it is by looking at dates on a page? You’ll find out later if you need to; at the résumé-reading stage, you don’t need to know, and it could mislead you. List the length of time in each position instead.

Religious and political clubs and affiliations

Candidates frequently list outside or personal activities on their résumés, typically at the very end. They may be intended to show good citizenship, or even some relevant experience, such as leadership, by running a club or campaigning for a political party. While possibly interesting, these personal activities are too likely to trigger biases on religious, political, ethnic, or other grounds. Especially relevant experience should be in the main body of the résumé, so it’s probably best to remove this section entirely.

Wrap up: Promoting sound decisions

Removing extraneous information reduces the risk of discriminating against applicants. Without this data, subtle or invisible biases don’t have a chance to harm your decision making ability, and with less text to read and think about, the most salient elements stand out. A short checklist like this one makes the redaction process quick and easy, increasing the clarity of your résumé analysis at minimal cost. 

New book available

Apress published my book in November, How to Recruit and Hire Great Software Engineers.

http://www.amazon.com/dp/143024917X

I put in much of what I've learned to be effective, and why, and I hope you find it very useful.

Don't Build Software

If you're a software construction specialist like me, you've written code for thousands of hours. You're good at it. You should be: after all, it's your job. Sort of.

Let's look at it from the perspective of the customer.

(Now you're the customer.)

There is an unavoidable problem with building software: it's slow, expensive, and error-prone. It usually takes longer than you want - good luck getting anything at all quickly. You have to hire expensive employees - a single senior software engineer will easily set you back $100K+ in salary alone - and managers to hire and feed them.

Once you've waited a very long time and paid huge sums of money, there's a fair chance the software you asked for will be delivered. You might not get it at all. Should you get it. it is quite likely that there are bugs in it, only a fraction of which are known. In other words, there are an unknown number of problems of unknown severity in the software you ordered.

(Now you're a software construction specialist again.)

Put it that way, and building software starts to sound like a bad idea. It's the kind of thing you'd only do as a last resort, when all else has failed or no other options are available: not doing the business it would support, supporting the business with more people, or buying existing software, for example.

When you're a software builder, understandably everything starts to look like a problem that can be solved by building software. But it's not the case, and it's important to investigate alternatives before committing yourself, and your customer, to an expensive and lengthy project.

If you've done your diligence and you still believe that building software is the right solution, you should build as little as possible, because everything you build will be expensive, take a long time, and have bugs. More on that in an upcoming post.

Test Driven Anything

A lot more people talk about test-driven development than practice it. Certainly I've talked more than I've done, but I've done nonetheless. And it's so successful that I want to do more.

If tests tell you that code works, and test tells you that features work, and tests tell you that security works... how about the root of all of those? How about your architecture?

It's no stretch to say your should test your architecture - as it's constructed. But how about in the design phase? You should surely be able to test your design. So start your design by writing tests, then build a design that passes them.

Example architecture tests:

The system handles 200,000 concurrent sessions. [yes/no]
Sessions can drop off at any time without warning, and no customer data is lost. [y/n]
Scaling from 200,00 to 500,00 can be accomplished in 3 days (or 3 minutes...) with no programming. [y/n etc.]
The system is resistant to denial of service attack within these constraints and in these scenarios...
The system can be deployed into a third-party cloud due to structure, configuration, data handling...

Once you have a suite of tests (classically, these are requirements, but from a different perspective) you can work with test engineers and other designers to put the system design against these tests, telling you upfront whether your design, implemented correctly, is very likely to pass physical implementations of these tests.

Once you're reasonably certain you have the right design and the right tests (I think you'll discover more tests as you design to fit the tests you have already) then you can start buildingt the tests immediately - working system to follow shortly.

This is also a perfect time to build your threat model and tests for it.

Pragmatic Complexity Analysis for Software Developers

This article is geared towards the sort of complexity analysis you may be asked to do in interviews, so it is fairly superficial, but should also be accurate. Complexity theory is, of course, a vast field of its own, but in practice, most software engineers use only a small part day to day. What an engineer needs to know is how expensive an algorithm is. Understanding complexity lets you critique and revise algorithms in a sensible manner, a particularly useful skill for programmers.

Fortunately, you can learn all you really need to know about basic analysis in a few minutes.

Complexity is expressed in relation to the size of input. For sake of argument, let's consider set of input data such as A = { } and B = { 1, 2, 3 }. When we're talking about input as a variable (could be A, B, or whatever) then we'll call it X.

Time Complexity by Example

Constant Time: Algorithm a:     O(1)

a(X) = { return 199; }

a(A) = 199;
a(B) = 199;

This is just shorthand. In other words, algorithm a(X) always returns 199.

Algorithm a, given input X, always does the same amount of work. The expense of the algorithm - how much time and space it requires to work - is constant and invariant. It does not vary according to the size of the input. This is expressed in Big O notation as O(1).

Time complexity of a(X) = O(1).

In fact, anything done the same number of times regardless of the size of the input takes constant time. Let's consider algorithm a1:

a1(X) = { k = compute 200 trillionth digit of pi; return k; }

This is an example of a time-consuming calculation. Despite its impracticality, it doesn't vary according to the size of the input so it's constant time. (A hint here is that X is never referenced in the function, but it's possible to reference X and still have constant time; maybe covered later.)

Time complexity of a1(X) = O(1).

Linear Time: Algorithm b:        O(n)

b(X) = { for each element of X, add the element value to variable k; return k; }

In other words, b(X) adds up every element of X and returns the total.
b(A) = 0;
b(B) = 6;
Etc.

Let's look at the expense of running the algorithm; how much effort the machine running the algorithm goes through to finish the algorithm's calculations. We can express this in steps.

For set A, algorithm b does nothing. "For each element" occurs zero times because there are zero input elements. Steps = 0.

For set B, algorithm b takes three steps. "For each element" occurs once for each element in the input. Since there are three elements in the input, there are three steps. To be terribly pedantic, here's more detail:

Step 1: add X[0] to k
Step 2: add X[1] to k
Step 3: add X[2] to k

It's easy to see that algorithm b takes one step for every element in its input. This is a direct, linear relationship. We call it linear time. Expressed in Big O notation, this is O(n), "n" being the number of elements in the input. In our examples, n(A) = 0, and n(B) = 3.

Time complexity of b(X) = O(n).

Of course, this isn't all that algorithm b does. Algorithm b also does these things:

Step 0: create variable k and set it to 0
Step 4: return k

Crucially, algorithm b always does these things, invariant to the number of elements in its input. As a result, these steps are done in constant time, and if an algorithm is more complex than constant time in any way, we disregard its constant time elements. We could say that the time complexity of b = O(n) + O(1), but in practice we don't. This reminds me of the +C result in integrals.

Sometimes an algorithm has a chance of stopping early. For example, Algorithm b1:

b1(X,j) = {for each element of X, if its value equals j, return its position k; }

In other words, look though the input until you find j, and then return its position.

Consider b1(B,j). With j = 1, the algorithm takes one step. With j = 3, algorithm b1 takes three steps.

Even in the case of an algorithm short-circuiting right away, we actually consider complexity in the worst case scenario. You must ask yourself the question, "What could possibly go wrong?" And then make the assumption it will take as many steps as it possibly could. It's pessimism for fun and profit.

Time complexity of b1(X) = O(n).

Quadratic Time: Algorithm c:     O(n^m)

c(X) = { for each element of X, add the value of every other element to variable k; return k; }

A high level statement of an algorithm can hide the details of the approach; since an algorithm is an exact set of instructions, not the idea of a set of instructions, here’s enough detail for us to work with:

c(X) =
For each element e1 in X,
For each element e2 in X, except element e2,
Add e2 to j
Add j to k
Return k;

c(A) = 0;
c(B) = 12;

For input set B, these are the steps taken:

Step 1: add X[1] to j
Step 2: add X[2] to j
Step 3: add j to k
Step 4: add X[0] to j
Step 5: add X[2] to j
Step 6: add j to k
Step 7: add X[0] to j
Step 8: add X[1] to j
Step 9: add j to k

It is of course no coincidence that there are 9 steps, 3 elements in B, and 3^2 = 9. Since we're vising each element as many times are there are elements, the number of steps is n times n, or n^2.

Time complexity of c(X) = O(n^2).

Algorithms a, b, and c indicate that one rule of thumb for finding complexity is to look at the loops. Each nested loop (over all elements) increases the exponent of time complexity by one.

No loops = n^0
1 loop = n^1
2 nested loops = n^2
m nested loops = n^m

Logarithmic Time: Algorithm d:      O(log(n))

d(X,j) = { search ordered input X for element value j and return its position k; }

Our implementation of algorithm d will be a binary search. This search probes input X at diminishing intervals to isolate the position element value j must be. In this case we are executing a loop, but not over all elements of the input (for sizeable inputs, anyway).

Quick summary of binary search: check the value of the middle element k of the input set. If it is equal to the target value j, return k. If it is less than j, repeat this operation with the set of input from k to the end of the input. If it is greater than j, repeat this operation with the set of inputs from the start of the input to k. If the set of inputs is at any time empty, return error value (j not found).

The number of probes to either find j or determine that j is not in the input X is the base 2 logarithm of n, the number of elements in input X.

Time complexity of d(X,j) = O(log(n))

While there is a loop in this algorithm, we do not visit each element to complete the loop. For temporal complexity this loop counts as log(n) Within a set of nested loops it counts for less than n; for example, an algorithm that does a binary search, but at each probe loops through the entire input X, has a time complexity O(log(n) x n). This is often written (O)(n log(n)).

Linear Time Part 2: Algorithm e:       O(n+m)

e(X,Y) = { add the sum of every element of X to the sum of every element of Y; return sum k; }

This can be implemented in terms of algorithm b, which sums input.

e(X,Y) = { k = b(X) + b(Y); return k; }

The complexity of this algorithm is best expressed in terms of both X and Y. In standard notation it would be O(n+ m), where n = the number of elements in X and m = the number of elements in Y. This is still considered linear time.

Time complexity of e(X,Y) = O(n+m)

Once you start passing functions as arguments, you can compound complexities for fun and profit.

Exponential and Factorial Time:       O(2^n), O(n!)

Many other exciting complexity types exist, of course.

…And that should pretty much get you through interviews and day to day life.

Tenate Quaestionem: Deconstructing a Simple Coding Interview Question

I have had the pleasure of interviewing at a few companies recently and one thing about my coding-problem-solving style struck me as worth mentioning and explaining. Having conducted quite a few interviews myself (300 or so) I appreciate when candidates make a concerted attempt to understand the problem posed. Perhaps this is because it's something I do myself (we hire people like ourselves, unfortunately, and quite unconsciously) but I also think it's a good practice.

Here's a thorough example.

An engineer asked me to "write a method which takes two Date parameters and returns true if the first is one month after the second, otherwise false". (Lightly paraphrased.) He said I had the freedom to assume that Date objects have convenience methods I might need. Obviously, I immediately wrote

bool IsSecondDateOneMonthLater(Date a, Date b)

{
return a.IsOneMonthEarlierThan(b);
}

And just as obviously he said that was stretching it too far. So I concentrated on learning the true nature of the problem, because it was greatly underspecified. I needed to know many things about what the method was really supposed to do and how it should behave for its customers. I started asking questions.

Are the Date objects in the same calendar?

Motivation: a lot of rules and heuristics would be needed to transform one Date into a compatible calendar so I could do the calculation; assuming the transformation is possible; also assuming that it's really a valid thing to do.

Answer: yes.

Are they in the Gregorian calendar?

Motivation: I know this calendar best. Other calendars may have eccentricies I don't understand well, or which are difficult to calculate. More further down.

Answer: yes.

Are the Date objects guaranteed to be valid? For instance, could one Date be set to a strange day such as February 55th, or be set before the beginning of the calendar, such as Gregorian year 1210?

Motivation: determine how much error checking I must do. If dates will not let themselves be initialized or set to invalid states, then I can count on them to be in sane states.

Answer: yes.

Are the dates in the far future or far past?

Motivation: I'd like to know if I need to worry about special circumstances such as the distance between two years being too large to fit in some number types, or being so close to a boundary that overflow or underflow become a problem. For example, if there are more than 2^64 years between the dates, then I need a special number type to contain and manipulate them. Is it likely I'll be asked to work with dates more than 1.8 * 10^19 years apart? I don't know what this method is used for, so I don't know. It could be for cosmological modeling.

Answer: the dates are in the near future, don't worry about it.

What is a month?

Motivation: It could be a solar, lunar, or calendar month. The time of day could be important, or not. The location could be important, or not. Examples: 8:15AM January 2 and 8:16AM February 2 might, or might not be a month apart, that's a policy decision. I did not ask about location (translating to time zone) but I should have. Due to the dateline, the same GMT, in local time, could be on different days. If location is not a factor, or the Dates are normalized to GMT, I don't have to worry about that. I should have asked that, but didn't. My error.

A month could reasonably be a lunar month. That's a lot more complex, and if so I need to know whether the Date objects have enough information to make this determination.

Answer: the same day number in the next month is the only deciding factor.

Are leap years a factor?

Motivation: This helps clarify his intention. February 2 to March 2 is a month regardless of the varying number of days, right?

Answer: no.

At this point I am a little unsure of this definition, because it means that there's no second date that could be one month from October 31st, ever, there not being a November 31st in any year in the Gregorian calendar. But I run with it, so I write some examples, then write something quite like this code:

bool IsSecondDateOneMonthLater(Date a, Date b)

{

// check that a and b are both not null

// for randomly selected close dates, this is most likely to fail first, so try it first

// to save time.

if (a.Day != b.Day)
return false;

if (a.Month == 12) // December, special case
if (b.Month != 1)
return false;

if (a.month != 12)
return (a.Year == b.Year)
else
return (a.Year == b.Year -1);
}

Now, if it hadn't been an interview, I might have made this code a bit neater, such as:

{
return ( (a.Day == b.Day)

&&( b.Month == 1 ? (a.Month == 1) : b.Month == a.Month)

&& (b.Month == 1 ? (a.Year == b.Year -1 : a.Year = b.Year) );
}

or this:

{
if (a.Day != b.Day)
return false;
if (b.Month== 1)
return (a.Month == 12 && a.Year == b.Year -1);
else
return (a.Month == b.Month && a.Year ==b.Year);
}

They both have their own charm. But it was an interview, and I wrote for simplicity and ease. Writing code on a whiteboard is unnatural, so if I can save brain cycles, I do. I ran the code through my test cases, it worked, and I declared it done.

These questions are summarized - I rephrased a few to make sure I and the interviewer both understood, repeated the question back to him, and asked a few miscellaneous questions. I am sure it added up to 15 or 20 questions. I doubt it was always obvious why I was asking, and sometimes I explained. There's time pressure in interviews.

Is this what the interviewer wanted, or did he want me to just make a bunch of assumptions and bang out some code? I asked whether he felt I was over-analzying the problem or should hurry through it, but he said no. I don't know whether he was being polite or this was his actual expectation. Regardless, I did it my way, and I solved the problem. The end solution was trivial. Getting there was not.

That's a lot of my job. Taking complex problems, usually vague and under-specified, and turning them into clear problems that can be solved, then solving them (or showing someone else how to). Usually fairly simply, but not always. The not-always has led to a number of patents, but that's another story.

comment on Shannon

Claude Shannon was a genius. His paper A Mathematical Theory of Communication is remarkably easy to understand and it remains a major part of modern information theory. I reread it the other day and thought I would share.

http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html