Adam's Tech Thoughts

RIP dmr

2011-10-13T16:31:00.001-07:00

Dennis Ritchie has passed away, and the world is a lesser place for it.


#include <stdio.h>

int main(void) {
   printf("Goodbye, dmr, and thanks for everything\n");
   return 0;
}

High-Level Hadoop

2011-02-14T17:41:00.000-08:00

At a high level, map reduce converts an input record to one or more output records, and then combines those output records into the final output records. The way that it does this can seem like magic, since so much of it is handled by the framework. Hopefully, this will demystify some of what's going on.

You start by configuring the job with a Configuration. The configuration tells Hadoop things like the location of your input, where to put your output, what class implements your mapper and reducer, and how the input and output are formatted.

The input formatter and its record reader take the input file (or files) and split them into records that are passed to the map class.¹

For each record that the record reader produces, map gets called once to produce an output record. Those records get stored in memory for awhile, and then written to disk when memory runs low or the map-phase is finished.²

Once the mappers are done, their output gets sorted by its key, so that the records group together by key. Then those records are split up by key and sent off to reducers (all of the values for any given key will go to the same reducer, though).

The reducer then gets called with a key and all of the values for that key (as an Iterator). The reducer then does its thing with the values and writes them to its Context, which will send them to the output formatter, which deals with persisting the results.

Footnotes:

_{1. The files in HDFS are split into chunks and replicated across the cluster. For performance, Hadoop will try to run the mappers on the same machines that house the blocks of the file. Unless you're writing your own input format, this will be transparent to you.}

_{2. You can also add a combiner, which does the same thing as the reducer and, in fact, can be the same class as your reducer. Adding one can potentially improve performance dramatically by drastically reducing the amount of data that has to be sorted and distributed to reducers}

Know When to Fold 'Em

2011-02-06T08:05:00.000-08:00

The Map & Reduce approach to dealing with large data sets, as implemented in Hadoop, has its background in functional programming, where both are used to manipulate the elements of a collection. Specifically, map is used to transform one element from the collection to some other type, for example to turn a string representation of an integer into an actual integer. Reduce, on the other hand, is used to combine all of the elements of the collection into a single result (which may, in turn, be another collection).

With just these two “primitives”, you can do a lot of powerful number crunching (or string manipulation, as the case may be), but what if you've got a lot of data coming in constantly and you need to be able to answer questions quickly? (Hadoop tends to have the throughput of a delivery truck full of hard drives and the latency of a delivery truck full of hard drives)

First, let's tackle the delivering-results-quickly part of the problem. Traditional RDBMS' handle this by building indices on the data for the fields that are most frequently searched. Fortunately, there's absolutely nothing that says that we can't do that with Map-Reduce. By building indices with map-reduce, we can then answer questions (that we know about ahead of time) about the data much more quickly. We can also calculate things like sums and averages on the data, so that answering analytics questions is just a simple value lookup.

Now, on to the constant influx of data problem. In functional programming, reduce has a “sister” function called fold that does the same thing as reduce except it takes a starting value to reduce (or fold) into. With fold, you can take the results that you calculated earlier and incorporate them into the new data (or vice versa). So, right now you may be thinking, “Well hello Mr. Fancy Pants. I've got news for you pal, Hadoop doesn't support fold, just reduce!” This is where the relationship between fold and reduce comes in (warning, LISP-like pseudocode follows); (fold startingValue list) has the same effect as (reduce (cons startingValue list)). We can take advantage of that equality by having a mapper that generates the previous run's results as input to a reducer, which combines it with the new data's results.

Not Your Type

2011-01-26T14:14:00.000-08:00

Not too long ago, I was asked by a friend why I like Scala's type system and how it helps develop software faster (relative to dynamically typed languages, like Ruby). The short answer is that it doesn't; the slightly longer answer is that that isn't the point. An effective type system is more about making the computer help you get your code right, because throwing $125,000,000 down the drain when one person uses metric and the other English units looks bad on the next budget request.

I suspect that most detractors of type systems are doing so from the perspective of weak type systems (like Java's), which really does get in the way as much, if not more, than it helps. A more powerful type system (e.g. Haskell's or Scala's), however, can actually make it a compile error to make some subtle errors. As an example, here's some Scala to make Velocity a type defined by Meters/Seconds:


class Meters(val dist : Float) {
   def /(time : Seconds) : Velocity = { new Velocity(dist/time.magnitude)}
}

class Seconds(val magnitude : Float)

class Velocity(val magnitude: Float) {
   override def toString() = magnitude + " m/s"
}

class Feet(val magnitude : Float)

With that definition, you can define something of type Meters, divide it by something of type Seconds and get a Velocity. Ok, so far so good, but that doesn't seem to be that helpful... until you find that you can not multiply the Meters by a typeless unit or accidentally by Feet! Now, you may be thinking, "Hey, that's still getting in my way! I have a parameter in Feet and I don't want to bother changing it to meters!" That's where the second trick up Scala's sleeve comes in, by providing a way to implicitly convert from Feet to Meters.

By adding this little snippet of code:

implicit def feetToMeters(feet : Feet) = new Meters(feet.dist * 0.3048F)

we can now divide Feet by Seconds and get Velocity in meters / second!

So now, these two statements print the same value:

println(new Meters(1000)/new Seconds(60))
println(new Feet(3280.8399F)/new Seconds(60))

And helping avoid turning a Mars Orbiter into a Mars Crasher is just one more reason why I really like Scala.

QuickBuzz

2011-01-08T19:03:00.000-08:00

A few of my friends use FizzBuzz to screen candidates, and that's a good thing because it's really good at weeding out the completely incompetent. The problem comes when you need someone who's more than just competent, you need someone who actually knows something. In those cases, I propose using Quick sort as a 2nd level FizzBuzz problem (or even a replacement for FizzBuzz). Quick sort is simple enough that it can be implemented in almost no time and almost no code by anyone who knows their programming language. It also has the benefit of opening the door for follow-on questions, like how do you avoid the algorithm taking n^2 time if the list is in order or what do you do if the list is too big to fit into main memory.

The New Alchemy

2011-01-05T17:12:00.000-08:00

Software development has given rise to entirely new alchemists, with entirely new approaches, including the "Powerful Process" and "Magical Language" schools. The one thing that both of the schools have in common is a belief that there exists some incantation or ritual that will transmute incompetent developers into great developers. They'd be better served trying to turn hydrogen into gold, since that's at least physically possible (if horrifically impractical). Let's look at these schools a little closer and we'll see why ITIL and CMMI (and a lot of "agile" processes!) are incompatible with Agile, and why Paul Graham was right and wrong about LISP being a secret weapon in software development.

Arcane Rituals: The Powerful Process School

Acolytes of this school believe that if they can just find the one true process and follow it with sufficient rigor that it will guarantee that they will be guaranteed success in all of their software development endeavors. The holy grail of this school would be to find the process that lets them say, with a high degree of certainty, that it will take x person weeks to build a particular system, regardless of who comprises their development team. In effect, magically turning even incompetent developers into highly productive developers. It's this fixation on process over people that makes them ideologically incompatible with Agile. Sadly, even many proponents of Agile fall prey to these beliefs. You can tell if an "Agilist" has joined this school by observing their response to failed projects. If the response is to defend the process by saying, "You did it wrong! You didn't do thing x as prescribed by the process!", then you know you've met an agile alchemist.

Occasionally, processes are put into place that do succeed in making the composition of a team a minor factor in how long it takes to develop software. Unfortunately, this isn't accomplished by improving the worst developers, but by dragging everyone down to their level. There is some good news, though! The best developers aren't held down at severely depressed productivity for long; they leave and make predicting the outcome of future efforts easier by leaving them with no chance of success.

Words of Power: The Magical Language School

Developers are often counted amongst the acolytes of this school, constantly searching for the programming language, IDE or new technology that'll make hard problems easy to solve and easier to implement. That's certainly understandable, since a lot of things in software development are really hard and many developers love tinkering with new things. Certain commercial entities exacerbate the problem to profit from the sales of books, tools, and software by hyping every new thing that comes along. Unfortunately for developers (and fortunately for snake-oil salesmen), some problems are just hard! No tool or language will ever make the intrinsically hard problems easy, at best they can stay out of the way and let the easy parts of the problems be easy.

Earlier, I mentioned that Paul Graham was right and wrong about LISP being a secret weapon, and you may be wondering just how that could be. To be sure, LISP is a very powerful language, very well suited to extending with powerful DSLs and someone comfortable with it could be extremely productive. That said, LISP alone isn't enough to make one team an order of magnitude more productive than another. What does let LISP make teams significantly more productive is that it's a great filter. Requiring LISP automatically rules out everyone other than really good developers. Since LISP is not a language that's a sure-fire path to a job, only people who actually care about software development know anything about it. Adding to that, LISP has a fairly high barrier to entry, by requiring an understanding of functional programming and recursion. Basically, any team that's using LISP is most likely a 10x team, and that is the secret weapon.

So, if neither languages or processes can work the magic, what _can_ we use to improve our odds of success at software development? The answer is simple; hire really good developers who work well together. Then tell them what you need them to do, and work with them to clarify any issues that come up and to make sure that they know when needs are changing as soon as possible.

Infinite sequences in Java

2010-10-23T07:16:00.000-07:00

One of the interesting features in a lot of functional languages is lazily evaluated infinite sequences. Java lacks any explicit syntax for creating sequences, however the Iterator interface combined with generics lets us implement just such a feature, though it's obviously not as clean or succinct as in some languages.

As an example, here's an implementation of an "infinite" sequence of 64-bit integers.


package blog;

import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;

public class Sequence 
   implements Iterable<long> {

  private long value;

  public Sequence(long start) {
      value=start;
  }

  public Sequence() {
      this(0L);
  }

  public Iterator<long> iterator() {
      return new LazyIterator();
  }

  public List<long> take(int toTake) {
      ArrayList<long> retVal = 
         new ArrayList<long>(toTake);
      for(int i = 0; i < toTake; ++i) {

      public boolean hasNext() {
          /* Always return true, because this 
             sequence is "infinite" */
          return true;
      }

      public Long next() {
          // store where we are
          long retVal = value; 
          // Move on to the next value
          ++value; 
          // auto-boxing will turn it into a Long
          return retVal; 
      }

      public void remove() {
          throw new UnsupportedOperationException();
      }
  }
}

This technique is also useful for parsing documents or in other situations where generating the entire list would either take too long or too much memory.

The Fizz-Buzz Challenge!

2010-10-22T17:42:00.000-07:00

One of my friends asks all interviewees to implement Fizz Buzz as part of a programming interview and, sadly, many people trying to pass themselves off as programmers can't implement it.

The basic idea is to print out the integers from 1-100, if the number is evenly divisible by 3 also print "Fizz", if it's evenly divisible by 5, also print "Buzz" and if it's evenly divisible by 15, print "FizzBuzz".

There are a ton of possible implementations, most of them painfully obvious and straightforward, so here's the challenge. 1) What's the shortest program that you can write to solve the problem and 2) what's the "fastest" (in terms of fewest number of operations, no sane solution should take more than a few milliseconds to execute and very nearly all of that is I/O).

My shortest in terms of lines of code was 5 lines of code (not counting curly-brace only lines), with 300 conditionals, 100 increments and 200 modulus operations. Fewest instructions had 6 conditionals (could have been none, but that would've cost an extra 75 lines of code) and 100 increments (no other operations), but at a cost of 27 lines of code.

More algorithms and surprises

2010-10-19T18:03:00.000-07:00

Testing the intersection problem using a HashMap turned up some more interesting numbers. In spite of that being an O(m+n) algorithm (m to build the hash map, n to check for intersection) like the linear probing, it was still significantly faster than the linear probing, even with the time to sort the two arrays removed. The HashMap based intersection did have the disadvantage of taking about an extra 3% memory.

Another surprise came from the fact that sorting the two arrays was just a very minor part of the runtime for the linear intersection, even though it should be m*log(m) + n*log(n), as opposed to the intersection's m+n time. I suspect, though I'm not certain, that that is due to locality and caching, since the sort operates on one array at a time, so the processor is better able to pre-fetch the needed data. Either that or Josh Bloch, Neil Gafter & John Rose have magical programming powers, which I'm also not ready to rule out quite yet.

Algorithms and surprises

2010-10-18T12:59:00.000-07:00

The other day, there was a question on StackOverflow that basically boiled down to, "Why is my O(n*n) algorithm running so slow?" What the individual was trying to do was find all of the elements in one array that exist in another array. It didn't take long for someone to post that the person should sort the lists and iterate over them once, but that got me thinking. Would it be faster to do a linear traversal, or would doing a binary search back and forth between the two lists be faster? It seems like it should be, since it's O(log(n)) to find the next term, instead of a potential O(n), but I wanted to make sure. The answer was surprising, to say the least. The O(n*n) algorithm was by far the slowest, but the fastest turned out to be the linear traversal.

Cumulative times (in ms) for 100 iterations of each of the approaches were (for input arrays of size 1,000, 2,000, 4,000, 8,000, 16,000, 32,000 & 64,000 elements respectively):

O(n*n): [52, 174, 727, 2698, 10648, 42516, 171441]

Linear: [43, 36, 74, 161, 332, 718, 1484]

Binary Search: [28, 41, 87, 182, 385, 825, 1727]

Actually looking at the data (all arrays populated by a call to Random.nextInt) revealed the answer. None of the binary searches were allowing the index for either array to jump by more than 2 or 3 entries at a time, meanwhile the linear approach wasn't examining more than 2 or 3 entries before finding the value (or a higher value to force a switch to the other list). The element being sought being so near the lower-end of the array made the binary search evaluate many more elements than the linear search.

The take-home from this test is that it's important to test your assumptions when it comes to performance. Intuitively, an algorithm with an expected runtime log(n)*log(n) should be much faster than one with an expected runtime of 2n, but actual data distribution may make it not so.

More on The Myth of SLOC

2010-08-28T17:21:00.000-07:00

Wow, this has been a LONG time coming, but between finishing up my MS in CS and work I've been a bit busy.

SLOC and other metrics, like coupling and complexity metrics are just proxies for the only "metric" that really matters. The best name that I've got for this metric is "clarity of intent". It's nothing Earth-shattering or particularly easy to measure, but it's what really matters. It all boils down to how clearly does the code that you've written express what you want the code to do?

Clarity of intent is why we name our variables things like "numOrders" instead of "doggie". A lot of languages fall short in this regard, in different ways. Java, for example, makes you repeat yourself a lot like in the declaration for an ArrayList; ArrayList al = new ArrayList()

Other languages (in particular, dynamically and "loosely" typed languages) tend to fail in the other direction, leaving you with declarations like

something = doSomething(someThingy);

In my opinion, this is one of the biggest failings of a lot of the dynamic languages like Javascript and (at least the last time I checked) Ruby. Functions and procedures take one or more "thingies" and there's no easy way to say, in code, "This thingy must have bark() and playDead() methods". Sure, you can say in comments, "Hey, if this thing can't bark and playDead, I don't want it", but there's no way to have the compiler check that for you.

A lot of languages, like Java, go too far in the other direction, though, and say "This thingy must extend/implement Doggie" when what you really want to say is "This thingy needs to have behavor similar to a Doggie, but if you happen to have a Rubber Duckie that behaves like a Doggie, that's cool too".

A good language will let you say very clearly what the prerequisites are for a method and makes it clear what you intend to do (with features like list comprehensions or map/filters instead of dealing with iterators for everything).

Two approaches to products

2010-08-28T16:58:00.000-07:00

There are, or at least seem to be, two distinct approaches to developing products. The first is to develop products that people need, whether they know it or not. These products may not be pretty or particularly fun, but they are the things that you absolutely need, whether you know it or not. People almost never love the products produced by companies who follow this path, but they'd be lost without them. This is what Google does, and it's why some of their products change everything and others flop completely.

The other approach is to build beautiful products. The kind of things that people love and feel they absolutely HAVE to have. These products may be "game changers", but they rarely make any really major impact on the world (not counting the obvious commercial impact). Apple falls firmly into this category. They can produce a product that's laughably inferior, but it's so blasted pretty that people will rush and line up to spend massive amounts of money to buy it. It's as rare for products in this category to not be huge commercial successes as it is for the products to meaningfully change the world or anyone's life.

The Myth of SLOC

2008-05-15T16:46:00.000-07:00

Ah, that old favorite metric, Lines of Code, all the ubiquity of a spork and slightly less useful. Since we all (hopefully) know that SLOC is a useless metric, the obvious question is why would anyone use it? The simple answer is that it's so easy that a drunk chimp can calculate the metric!

As an example of why SLOC is useless, imagine two programmers at different companies implementing a paging functionality. Specifically, both programmers need to determine whether a next button and a previous button should be displayed. Programmer A produces the following code:


   String n,p;  
   if(x&&y) {
      n="enabled";
      p="enabled";
   } else if(x&&!y) {
      n="enabled";
      p="disabled";
   } else if(!x && y) {
      n="disabled";
      p="enabled"; 
   } else if(!x && !y) {
      n="disabled";
      p="disabled";
   } else {
      n="disabled";
      p="disabled";
   }

Wow, 16 lines of code! Programmer A's been pretty productive. Programmer B, on the other hand, came up with:


   String next = hasNext ? "enabled" : "disabled";
   String prev = hasPrev ? "enabled" : "disabled";

Wha? Only two lines of code? What a slacker! Oh, wait... both ultimately have the same effect! In fact, on closer examination, we find that Programmer A's code actually reduces the value of the code base! In case you're wondering how adding functionality could reduce value, consider the cost of maintenance. Those 16 lines, including a logically impossible else clause, will have to be read and understood by some poor soul if that file ever needs to be changed. Since none of the variables have meaningful names and the boolean clauses are more complicated than necessary, understanding Programmer A's code will take significantly longer.

So, if more lines of code aren't better, doesn't that mean that expressing the same thing in fewer lines of code is better? Turns out that the answer is a resounding... not necessarily. I'll expand on that a bit more in the next post, including touching on the myth that fewer lines of code implies fewer bugs.

Dev102.com Programming Challenge 3

2008-05-14T18:36:00.001-07:00

Programming Challenge 3 at Dev102.com is to find an element in a mxn matrix whose rows and columns are sorted in ascending order. A quick and easy way to do this is to perform a binary search in the first column to find the row with the highest value that is less than or equal to the value for which you're searching. Then, perform a binary search in that row to find the element.

If that didn't find the element, then do the same thing except perform the binary search on the first row and then the column. You can actually use information from the first run to limit the size of the size of the column, but the performance improvement will (in general) be relatively small.

The runtime for this is O(log m + log n)

Dev102 Programming Challenge 2

2008-05-06T18:37:00.000-07:00

Programming Challenge #2 at Dev102.com is to find an efficient way to reverse the bits in a 1000x1000 byte image. Assuming you can afford 256 bytes for a cache, one really fast general-purpose way to implement this is to create an array with an entry for each possible value of a byte, storing the reversed bits of the byte. For each byte in the image, you can then look the reversed bits nearly instantly. The runtime of the algorithm is O(n) with a trivial constant multiplier.

This algorithm, by the way, is insanely easy to make run in multiple threads and should run extremely fast on a multi-core SIMD processor.

The Only Process You'll Ever Need

2008-05-06T17:38:00.000-07:00

Scrum, CMM-I, ITIL and countless others. It seems that for every developer, there are half a dozen software development methodologies and processes. Some are lightweight, some are heavyweight and some are stupid-weight, producing orders of magnitude more documentation than code.

So, you may be wondering, why are there so many different processes? The answer is that everyone's looking for that one, magical process that'll make software development predictable and repeatable. Unfortunately, I don't have that magical process to give you, in fact, I seriously doubt that it even exists. What I do have for you however is a process without which your development efforts are guaranteed to fail. The process that I have for you is a very strict process, far more strict, in fact, than most heavyweight processes, but it requires no more documentation than your handwritten notes to yourself.

I won't keep you in suspense anymore. This super-process is none other than the scientific method. In case you're not familiar with the scientific method, here are the highlights.

Consider the problem
Gather data
Formulate a hypothesis (an educated guess about how to solve the problem)
Test your hypothesis
Use the information from testing your hypothesis to accept, reject, or refine the hypothesis

The scientific method is useful at all stages of software development, but it is particularly useful when debugging, which is frequently the most difficult part of development. Before fixing a bug, any bug, take some time to apply the scientific method. Think about the bug and what the implications of it are. Don't jump straight into the fix, spend some time to make sure your fix will really fix the problem and not just mask the symptoms. Figure out how you'll test that your fix actually works without breaking anything else, and then test the fix. If it works, commit the fix and do the dance of joy!

Good luck and enjoy your coding!