Friday, December 31, 2010

The Brain Teaser: Full Solution

This is part 6. After the fold I show the complete solution for assembling The Brain Teaser.

The Brain Teaser: Assembly hint

This is part 5. After the fold I reveal one hint -- the blind spot that initially prevented me from assembling the puzzle given the manufacturer's solution.

The Brain Teaser: The manufacturer's solution

This is part 4. After the fold, I show the solution provided with the puzzle. If you also received the puzzle in its original packaging, you should already have this solution page.

Disassembling The Brain Teaser

This is part 3. After the fold, I show how to finish disassembling the puzzle.

Tuesday, December 28, 2010

Unlocking "The Brain Teaser" puzzle

This post is part 2 of several posts documenting the solution to the ECO Game Brain Teaser puzzle. For the benefit of anyone who only wants hints, in this post and the following most of the post will be 'after the fold'.

Monday, December 27, 2010

The ECO Game "Brain Teaser REMUE-MÉNINGES" wooden puzzle

Update: If you arrived here via a web search, you might want to see all posts about the puzzle. Click on this link to see the brief form of all six posts in reverse order, showing this post last and the final complete solution first. Don't worry if you are only looking for hints, the brief form of the posts don't reveal any solutions. I've written the posts such that you should be able to get only the hints you are looking for, when you are ready for them.

This is part 1 of six parts.

Santa left a fun wooden puzzle in my stocking this year. Whatever packaging the puzzle was in was recycled with all of the other packaging and wrapping paper that accumulated that morning. All I have now is the puzzle itself, and small slip of paper that has the solution to the puzzle. That slip of paper identifies the puzzle as The Brain Teaser / REMUE-MÉNINGES, with brand names ECO GAME and Relaxus. It provides the domain name, but I have searched that site and could not find any links to the puzzle. I conjecture that Relaxus is only the U.S. distributor and that the original manufacturer is French. If anybody reading this knows more details please leave a comment.

The puzzle looks like this:

Only one view of the puzzle is shown above but you should be able to get clear picture of the overall structure from the one view because of its many symmetries. There are three rectangular blocks with square cross sections that form a natural set of xyz axes. Rotate the puzzle 90 degrees about any of the three axes and you get the same shape.

This puzzle (like others in the genre) is two puzzles in one. First, you have to solve how to disassemble the puzzle. Then, you have to solve how to reassemble it. Disassembly is by no means trivial, but I was able to figure it out after a couple minutes. There is one trick to unlock the puzzle and then it almost falls apart. When I had figured out the trick, I impulsively decided to quickly disassemble the puzzle completely without making any attempt to understand the topology. My thought was that I wanted to tackle the second puzzle without 'cheating'. In the back of my mind I knew that if I got stuck, I could just use the solution page.

Later that day I sat down and spent about 20 minutes trying to solve the puzzle. It became clear that it wasn't going to be easy. I set it aside, and then spent another 20 minutes later in the evening, and then again the next day. I explained to my 5 year old daughter that for some problems I need to tackle them over several days and let my brain work on the problem while I sleep. By the morning of December 27th, I had 'slept on' the puzzle for a couple nights, but was still basically stuck. I debated with myself whether to give it another couple days, but decided to give in and take a peek at the solution page.

It turned out the solution page was pretty skimpy. I spent a few minutes trying to follow the instructions only to find myself reaching a dead end where the instructions seemed to be wrong. It took me another 10-15 minutes of head-scratching to figure out what was missing from the instructions that allowed me to go astray. During that time I did a quick web search and didn't find any links to hints or solutions. Since I have a little spare time this week I decided document the solution. I will attempt to structure this documentation so that anyone who is just looking for hints can get them without being exposed to the complete solution. After the fold for this post I'll provide one hint for anyone who hasn't figured out how to disassemble the puzzle.

Thursday, January 7, 2010

Code Smells

My favorite tumblelog trivium (which is where I saw the links to the commentary on Shu Ha Ri that inspired this blog) just posted a link to Private Methods are a Code Smell, where Kent Spillner proclaims:
Private methods are a code smell. They should be moved to collaborating classes and made public.
His reasoning is interesting and concise and I highly recommend it. However, I also disagree, and think it is worth a post to explain why.
First, let's look at one independent definition of what  a code smell is. The Wikipedia entry says:
In computer programming, code smell is any symptom in the source code of a program that possibly indicates a deeper problem.
Given this exact definition, I have to say that Kent is correct. However, it is because the word possibly in the definition leaves a rather large loophole. Yes, there are times when private methods should be refactored as Kent states, extracting them as public methods of collaborating classes. But I read Kent's post as taking a stronger stance. It is as if he almost titled his post Private Methods Considered Harmful. Of course, I may be mistaking his intentions, but let me pursue this anyway.

Recall the three phases of acquiring mastery: Shu Ha Ri. In the Shu phase, a beginning programmer must try to strictly adhere to solid foundational principles or rules. In the Ha phase, the programmer explores the boundaries of the rules, and learns when it is justifiable to break the rules. In the Ri phase, the programmer becomes free of rules, and simply does what is correct in the given situation.

There are many possible principles of programming. Beginning programmers should start with a small number of simple principles, such as: member data should always be private. This is an excellent principle for a Shu programmer to follow. A Ha programmer might experiment with occasions to violate the principle, but will probably learn through experience that every violation of the principle is a mistake.

Let's now consider another candidate principle: member functions should always be public. This candidate principle is close in spirit to Kent's proposed code smell, but Kent didn't state the code smell this way, and for good reason. This would be a bad principle to impose on a beginning programmer. Beginning programmers should follow principles that lead them to avoid repetition, develop an appreciation for encapsulation, and learn how to create narrow interfaces. But more importantly, beginning programmers should learn the principle to keep it simple.

But Kent didn't propose a fundamental principle. He proposed a code smell. So is it a good code smell? Consider the first five examples on the Wikipedia page I linked to earlier:
  • Duplicate code: identical or very similar code exists in more than one location.
  • Large method: a method, function, or procedure that has grown too large.
  • Large class: a class that has grown too large, see God object.
  • Feature envy: a class that uses methods of another class excessively.
  • Inappropriate intimacy: a class that has dependencies on implementation details of another class.
These are all excellent code smells that are appropriate to teach to Shu level programmers. The private method code smell is another beast entirely. I can see how it might be a good code smell to give to Ha programmer, posing it as a learning exercise: Consider private methods as a code smell, and the recommendation to refactor them into public methods of collaborating classes. Is this a good universal rule? If not, what are the exceptions to the rule?

A Ha programmer who spent a few weeks with this exercise will very likely come out of the exercise as a better programmer. But if they conclude that the rule is a good universal one with very few exceptions, then I suspect they aren't yet nearing the Ri phase of programming. Your humble 4-dan programmer thinks private methods should only be considered a smell in the presence of other smells, i.e. the decision to refactor one class with private methods into two or more collaborating classes with public methods shouldn't be prompted by the presence of private methods alone.

Another of my posts might apply here: The Siren Call of Abstraction. In that post, I warn that programmers often fall into a kind of trap, where they are seeking a kind of purity through abstraction and generalization. The concept of code smells is a useful one, but I sometimes wonder if the art of programming doesn't also need a concept we might call purity smells.

One favorite principle of mine is: avoid speculative complexity. This principle deserves its own essay, but let me just say here that many programmers fall into a trap of speculating about future requirements of their applications, and attempt to design their applications so that those future requirements will be easy to implement when the time comes to do so. Programmers who have become enamored with refactoring might be inclined to do premature refactoring, which might be nearly as big as a mistake as doing premature performance optimization. I love refactoring as a tool, but for some time now, my refactoring has always been driven by the pragmatic concerns of doing what it takes to achieve my project's near term goals. With this style, there are a number of code smells that I find natural and intuitive, but calling private methods a smell seems a bit forced.

Friday, October 30, 2009

4 Dan debugging

So, a 4 Dan programmer must have some pretty awesome debugging skills, right? I've done most of my programming for the last 8 years or so on Linux using GCC and GDB, so I should have intimate knowledge of the full power of GDB, right?

Wrong. In fact, my knowledge of GDB is probably just a small subset of the things you might find in a GDB cheat sheet. Hmm, maybe I should check that assumption. I'm feeling lucky, what is Google's first link for gdb cheat sheet? Ahh, it is a tutorial page on Ok, I just skimmed that page and here is my list of commands I commonly use:
  1. gdb -e name-of-executable -c name-of-core-file
  2. bt
  3. up number
  4. down number
  5. list
  6. p variable-name
  7. quit
There are two more gdb commands that I use regularly that are not on the cheat sheet:
  1. thread apply all bt
  2. thread number
That's pretty much it. Yes, I vaguely remember a few other commands and can find them using the help command, but I hardly ever use those commands. Note that I nearly always invoke gdb on a core file, and since I almost never debug a running program, I don't use breakpoints, watchpoints, single stepping, etc.

Let me state up front that I sometimes have real feelings of inferiority over my knowledge of debugging tools. I've known other programmers who were strong designers/programmers but who seemed godlike (to me) in their mastery of debugging tools and I have to admit that I have been envious. Yet I've been on teams with programmers like that and my productivity was comparable or better.

So, do I just write perfect code that never needs to be debugged? Absolutely not. I typically invoke gdb several times a day, sometimes dozens of times. Are you ready for me to reveal my secrets?

Ok, here they are: 
  1. assert() is your friend.
  2. Make your assumptions explicit in your code (see #1)
  3. Don't fall into the trap of believing something to be true without evidence.
There, that's basically it. So, how does it manifest in the way I work? Well, as I said I invoke gdb several times a day or more. Most of the times that I invoke gdb, I do so because a program has just terminated due to an assertion that I put in the code. I run gdb with the core dump, look at the stack trace (or possibly several if the code is multithreaded), and probably examine some variables. I do this to figure out where my previous assumptions where incorrect. This generally leads directly to the fix and probably prompts me to add some more assertions.

Sometimes my program terminated for some other reason than an assertion. Then my job is to look at the stack trace and figure out what assertions I should add that will cause the program to instead terminate with an assertion. Most of the time this is relatively easy to do.

As a quick aside, the various Agile programming methodologies put a big emphasis on unit tests. Note that assertions are a kind of unit test.

There are more to assertions than just assert(). It's very useful to understand the concepts of precondition, postcondition, invariant, etc. Understanding these concepts will help you not only in choosing good assertions to use in your code, but how to better structure your code. However, I've think I've said enough about assertions for this post.

Returning to the three points above, let's look at points 2 and 3. Point 2 is almost redundant. It connects points 1 and 3. Point 3 says to make sure you have evidence to support your beliefs about the functioning of your code. Point 1 gives you the mechanism for  obtaining that evidence from your running code. Point 2 simply says just do it.

So the real key concept that must be mastered is the final one. A master programmer must be a kind of zen skeptic. You must never let your beliefs about reality outweigh the evidence that reality gives you, and you must be actively asking reality to give you evidence. You must always seek evidence with an open mind.

A few days ago I read a delightful post by Paul Buchheit titled Applied Philosophy, a.k.a. "Hacking". Paul opens by saying:
Every system has two sets of rules: The rules as they are intended or commonly perceived, and the actual rules ("reality"). In most complex systems, the gap between these two sets of rules is huge.
Paul goes on to discuss how hackers of various kinds exploit the gap in various systems and gives several great examples in different domains. But lets see how we can apply his statement to the problem of debugging.

Computer programs have a great deal of complexity. There is complexity that the programmer puts into the program through her use of programming language constructs. There is complexity that the compiler puts into the program by turning the program into machine code. There is additional complexity that arises from the data the program consumes, the internal state of the program as it evolves. And finally, if the program is multithreaded, there is additional complexity that arises from the complex timing relationships between the threads.

The human mind is amazing in its ability to understand complex systems, but we have to recognize that our understanding is always an imprecise model of reality. We create beliefs about how complex systems work and these beliefs are necessarily dramatic simplifications. So, there is a gap between reality and our belief about reality. To be able to debug complex computer programs we must be aware of that gap and apply various methods to minimize the gap. Or to at least minimize the negative consequences of the gap. We can do that using concrete tools such as assertions, but the biggest gain comes from having a good understanding of the limitations of our own minds.

We can (and all of us do) have bugs in our thought processes that can hold us back in our ability to design, implement and debug. We begin the path to mastery when we begin to debug our own thought processes.

Thursday, October 29, 2009

Spin Locks

In my post Multithreading And Atomic Integers I briefly introduced atomic integer operations and GCC's built-in functions for them. In this post and the next I want to discuss spin locks that can be implemented using the GCC built-ins.

First, consider a very simple implementation of a spin lock:

class SpinLock
    SpinLock() : mWord(0) {}
    void Lock() { while (!__sync_bool_compare_and_swap(&mWord, 0, 1)); }
    void Unlock() { mWord = 0; }
    int mWord;

To use this SpinLock, allocate one that is visible to all threads, and then in each thread do something like this:

extern SpinLock gLock;
void Foo()
    ... critical section here

This SpinLock class allows only one thread into the critical section at a time. It does it using just one bit of an atomic integer -- the code would work fine if mWord was declared as a char. If more than one thread wants into the critical section, one will be allowed access, and the others will spin in a very tight loop. Each spinning thread will burn CPU cycles (and memory bandwidth) until it acquires the lock.

It's worth spending a moment here to consider when spin locks are appropriate. One rule of thumb is that you should only use spin locks if you are willing to limit the number of active threads to the number of cores on your machine. Futhermore you should know that your application is going to be the only process consuming significant CPU cycles on the machine. If you use spin locks, you want it to be highly improbable that the kernel will suspend a thread while it holds a spin lock.

If you are willing to limit the number of active threads to the number of cores, you probably have threads that are primarily CPU bound. If the threads are primarily I/O bound, you are probably better off using mutexes and creating more threads than cores. But note that I am not saying that your application can't do I/O. I have an application that reads a large volume from disk yet is clearly CPU bound. It uses one thread per core and all threads add data into shared data structures. The application performs much better (as measured by the rate that it consumes the data) when using spin locks instead of mutexes.

As a final consideration, if you are going to be able to use spin locks, you probably are using lots of them. If you have only one global mutex, you don't want to replace it with a spin lock. Spin locks work well when they are fine grained and dispersed throughout a large data structure. Perhaps you have a large graph data structure and need a critical section whenever you update any link of this data structure. Each link would then need its own mutex or spin lock. If you have millions of these links then spin locks can be a great choice. The probability of contention on any one link is probably very small and it is likely that the critical sections are short in term of CPU cycles. If you tried to use a Posix mutex for every link, you might find that the memory footprint is prohibitive -- one Posix mutex requires 40 bytes on the Linux platform I use. A spin lock can use as little as one byte.

Let's return to the implementation above. There is one subtle problem with this implementation: if multiple threads contend for the same lock, there is nothing to ensure fairness. Suppose thread A obtains the lock and starts doing the work of its critical section. While it is doing the work, first thread B, then thread C attempt to obtain the lock. Since B was 'first in line', it would be unfair for C to be the thread granted the lock next, but that quite possibly will happen.

If this kind of fairness is a serious requirement for a given application then that application probably shouldn't be using spin locks. But we can implement a spin lock class that ensures fairness. Here is one possibility:

class FairSpinLock
    typedef unsigned char Byte;
    FairSpinLock() : mReserved(0), mReleased(0) {}
    void Lock() { Byte resv=Add(&mReserved); while (Add(&mReleased,0)!=resv); }
    void Unlock() { Add(&mReleased); }
    static Byte Add(Byte* val, Byte x=1) { return __sync_fetch_and_add(val, x); }
    Byte mReserved;
    Byte mReleased;

Here we use two different atomic integers. Both are single bytes and we only use the Add operation, which is defined using __sync_fetch_and_add(). The first byte mReserved is a running count of how many reservations have been made. The second byte mReleased is a running count of how many acquired locks have been released. A thread holds the lock when it finds that all prior reservations have been released. It holds the lock until it releases its reservation.

There is beauty in the simplicity of this implementation. Note that both counters wrap around. But wrap around is not a problem since we only check for equality. Using bytes means we are limited to no more than 255 pending reservations. Just make sure you don't use this code as is on your machine with 256 or more cores.

So far we have only considered simple mutual exclusion. But there are cases where you want to allow multiple readers as long as write operations are excluded. These are called read/write locks. A write lock is a mutual exclusion lock as we have discussed so far. While a thread holds a write lock, no other thread can obtain either a read or a write lock. A read lock excludes other threads from obtaining a write lock, but allows other threads to obtain concurrent read locks.

So, can we implement read/write spin locks? Yes, we can, but I'm going to save that for a future post. It is a fun exercise to try to implement a read/write spin lock, so you might want to try before reading my follow-up post. First start with the FairSpinLock implementation and extend it, while keeping the fairness feature. Then see if you can implement a read/write lock using a single atomic integer instead of two. I don't know how to do this while still ensuring fairness, but I have a working implementation with a single atomic integer that does not ensure fairness. I'll discuss both implementation in the follow-up post.

Friday, October 23, 2009

The Siren Call of Abstraction

To be a great programmer you must master the use of abstraction. I don't care how big your brain is, if you can't abstract away details, your code will get bogged down in them. To a large degree, modern languages are all designed to help programmers with tools for managing complexity through powerful abstractions.

I know some good programmers who are quite productive despite having mostly low-abstraction tools in their tool set. For example, I know programmers who implement almost any collection of objects using linked lists, with the link implemented as a next pointer embedded inside the object, something like this:

class SomeObject
    SomeObject(SomeObject* next) : mNext(next) {}
    SomeObject* Next() const { return mNext; }
    SomeObject* mNext;

This is a fine choice for some problems, but it is a suboptimal choice for most problems. One pragmatic reason is that objects implemented this way can only belong to one collection at a time. The bigger problem comes simply from coupling together the two concepts of Object and Containment. If the programmer sees the next pointer as just another attribute of the object, then the methods of the object will probably blur the different operations, with one line of code manipulating the object's state, and the next line of code manipulating the container state, and no clear demarcation between the two fundamentally different abstract operations.

But what does this have to do with The Siren Call of Abstraction? Well, good programmers can be productive despite not having mastered the use of abstraction. But being obsessed with abstractions can be a major hindrance to productivity. A couple different posts crossed my RSS feed today that made me think about this topic.

First, Joel Spolsky wrote recently about the virtues of Duct Tape Programmers. He sings the glories of programmers who get the job done with simple tools analogous to duct tape and WD-40, and ridicules programmers who love multiple inheritance. As usual Joel is a fun read.

But Joel only ridicules some caricature of a programmer. DPP's tweet today was about a specific programmer and is far more damning, so much so that I feel sorry for the subject of his scorn.