Software Optimization - one approach

Performance optimization comes in many flavors. My preferred methodologies come in two: architecture and profiling. The architecture aspect means being involved with high level design and always looking for opportunities to remove bottlenecks. In the case of graphics, it may mean knowing when to say No to artists (not very often). As one example of where this is important, at a previous company where I worked, the artists were constantly trying to put in the largest files possible simply because they often have very little awareness of the costs of using large graphics or audio files. Compression helps (mp3 or tiff) but we ended up with one tiff that was 21 megs in our pipeline which simply made our game unrenderable (roughly 1500x1500, 24bit). We failed on our education effort and it continued to happen over the course of months simply because this type of thing is the last sort-of-thing an artist is interested in. Ultimately, in the Maya plugin, we popped-up an error when users had an image over 100k. This helped, but they found ways to work around the system. Finally, as part of the build system, we failed the build when resources that were too large (audio and graphics which were treated by different size constraints) were submitted into Perforce. Our build system always told us which checkins were the one's to 'break the build' so this became much easier to fix the art, identify the problem early (rather than late in production), and educate the artist involved.

Architecture, can be more than designing clever pipelines tho. It can mean identifying areas of the game which require LOD, if you need it at all. It means packing all LOD models in a way to allow fast replacement (stored key-framed, all models in in one data blob, or whatever), identifying when to compress and when to not compress, defining hot-swapable textures (GUI usually), and so on. In most cases, you are attempting to keep as much data as possible in RAM (faster than DVD) as possible to provide performance and balance that with the performance constraints of decompression or moving too much data around.

Profiling is an easier issue but one of my favorites and I try to do it often. This is a simple matter of never optimizing anything until the need arises. This is in sharp contrast to architecture optimization which tries to prevent optimization bottlenecks up front. When performance drops, optimization is never far away. You begin with a small dose of profiling and nearly all compilers provide some form of profiling. This can mean instrumenting the code with timing blocks (instrumenting the code) when profilers are inadequate. Ultimately, after a few hours, or sometimes days, performance bottlenecks are identified. Most of these are poor loops like a bubble-sort, code that is called repeatedly to look up a value better stored in a hash, complex values calculated rather than stored at compile-time, large case statements (state trees do this), and so on. Once these are identified, fixing them is usually easy. Most of the time, it becomes an algorithmic choice trading an N^2 problem for a logN type of problem. A neat example of this is a recursive version of Fibonacci versus a looping one. The following two algorithms have starkly different run-time performance based on the way that they are implemented:

This first one runs in N time meaning that even for large values of 100 or more, this runs about the same speed.

int        fibonacci1 (int n)
{
    if (n<1)
        return 0;
   
    int        _1 = 0;
    int        _2 = 1;
    int        total = 0;
   
    for (int i=2; i<=n; i++)
    {
        total = _1 + _2;
        _1 = _2;
        _2 = total;
    }
   
    return _2;
}

That isn't true here at all. This code is understandable, works, and is dramatically slower and it slows exponentially as N^2.

int        fibonacci2 (int n)
{
    if(n < 2)
        return 1;
    return fibonacci2 (n-1) + fibonacci2(n-2);
}

Most optimization usually boils down to architecture choices and algorithmic ones. Once in a while, I have the unique pleasure of writing assembly code, but it's been about four years since I have, and I'm afraid I've grown a bit rusty. In the mean-time, I'll stick to higher level stuff.

Cool little sizeof tricks

Here are a few little tricks for sizeof arrays.

Firstly, the sizeof operator typically returns the sizeof an array in bytes. Let's say that we have the following snippet:

int    array[20];
int x = sizeof (array);

// x = 80

Working from there, we can easily find out the number of items in an array.

#define ArraySize(a) sizeof(a)/sizeof(a[0])

int num = ArraySize(array);

// num = 10

Lastly, what do you do if you need the number of elements in an array that is a member variable of a struct or class? Here we need an instance of a variable to access its member variables so we declare a pointer to 0 and access its array member. Normally, this might produce strange results, but during compile-time, this works fine.

struct dummy
{
    int array[10];
};

#define MemberArraySize(a,array) (sizeof(((a*)(0))->array)) / (sizeof(((a*)(0))->array[0]))
int num = MemberArraySize(dummy, array);

// num = 10

Function pointers

Pointers to functions

How one uses a pointer to a function is detailed below, but why do we do it is a good place to start. There are two common reasons for using pointers to functions and many more uncommon reasons.

1) State machine changes. A good way to manage FSM (finite state machines) is to change their functionality at runtime. Take the following two functions that take a monster class as a parameter.

class Monster;
typedef void (*UpdateFunctionPtr) (Monster*);

void    UpdateFn1 (Monster*monster)
{
  // ...
}
void    UpdateFn2 (Monster*monster)
{
   //...
}

class Monster
{
public:
   UpdateFunctionPtr     FunctionPointer;
};

Now the runtime application can make decisions based on state or data to change how an instance of the Monster class manages its updates. For example:

Monster monster;
if (... )
   monster.UpdateFunctionPtr = & UpdateFn1;
else
   monster.UpdateFunctionPtr = & UpdateFn2;

...

(*monster.UpdateFunction)(& monster);

Be very careful here. More than once, I have missed the asterisk before the function call.

All of this may seem like overkill since classes are meant to manage their own state and call the appropriate functions when things change.

However, it is common to do this for callback functions, timers, and other objects meant to call a method once their timer expires or an event fires. This brings us to reason 2.

class Timer
{
public:
   UpdateFunction     FunctionPointer;
   void    Update()
   {
       if(currentTime-BeginTime > totalTime)
       {
           (*FunctionPointer)(...);
           isExpired = true;
       }
   }
};

This code can be made generic with the use of templates or delegates.
//-----------------------------------------------------

Pointers to member functions

The basic concept is that you should have a class with functions that you can access (public, but not required), an instance of that class, and another class which knows very little about which functions to call. This is where syntax can really hurt. Note here in the Different class, the typedef to the function pointer contains an asterisk before the generic typedef name.

class Different 
{
public:  
 void Function1TakingTwoParameters(int x, int y);
 void Function2TakingTwoParameters(int x, int y);
 
 typedef void (Different::*FuncPtrTwoParams)(int, int); 
}; 

Now it's often pointless to do use member function pointers unless you have a design that separates the function invocation with a delta time meant to provide a callback. Other things may be a design separating interface from implementation.

//--------------------------------------------------------------------
class SetupCallingFunction
{
public:
 SetupCallingFunction( Different* diff, Different::FuncPtrTwoParams fnPtr )               : differ (diff), functor (fnPtr)
 {
 }
 
 void SomethingHappens()// timer or something else
 {
  (differ->*functor) (1, 1);
 }
 Different::FuncPtrTwoParams functor;
 Different* differ;
};

This probably looks a little confusing. Basically, we have a pointer to an object "differ" and therefore must use the arrow syntax. Then we have a pointer to some member function of differ which we invoke with the asterisk. This block must be enclosed by parenthesis, or it will not compile. Then the last piece is the list of parameters which is what you should expect. This is how this class above is used:

Different differ;
SetupCallingFunction  caller (&differ, &Different::Function1TakingTwoParameters);

Module isolation

Henry Ford was the first to take the concept of modularization into the full production cycle. He took the concept of building pieces of a whole into mass production and showed that by isolating the work performed by different people into smaller types of work, the quality improved, the productivity increased, and and slow downs in production could easily be dealt with. This also dramatically increased profitability.

Module isolation fits under this concept of building parts that you later assemble. But what is a module? This is a chuck of code that is a single set of behaviors. In C, this is usually a single C file and a matching header file. Similarly, C++ follows this model but may allow multiple classes in a single header or cpp file. In Java or C#, this is usually defined in a single file which is a class file.

So, what's the point of modules? Some people with whom I have worked often wonder why modularization even matters. "You don't really need that: just make all objects part of the same system so each object has ready access to other objects."

In one of the code bases in which I have recently worked, around 35% of the code base is directly inside of a global object; let's call that object global_app. This object controls the flow of all processing like updates, rendering, which entities are displayed, gui changes, etc. It also contains hooks into most other systems like rendering, gui, animation, etc. These hooks are in the form of callbacks, timers, and so on. As a result, all systems in this global_app are fundamentally intertwined and non-separable. Unit testing is nearly non-existent and bugs are tenacious, difficult to reproduce, and impossible to isolate. Most development is done inside the application on new systems which are instantly intertwined into the system and soon become difficult to test or separate. This slows development and no system truly is stable. There is also an air of mystery about the code base where strange interactions happen that are nearly impossible to foresee and very hard to understand.

In this system, the only stable code is truly the low-level stuff which is not intertwined. But, it doesn't have to be like this.

The previous codebase I helped develop was built on the basis of completely isolated code modules... and I mean isolated. This asynchronous messaging model has many benefits. Modules could be threads, simple sub-modules, classes within an existing module, or however you find most efficient. This makes the code very flexible, extensible, and configurable. There was a fundamental system constructed for sending messages between modules without breaking threading isolation so using special care for data (i.e. concurrency concerns) was completely unnecessary. The messages had a certain size constraint, but basically, you could send nearly any data to another module but not access any other module directly.

All modules had access to the "game" object during their update cycle but they had no awareness of other modules. In fact, they couldn't know when or how any message being sent was delivered. There are no hooks from one part of the system into any other. All of the messaging was configured in a setup module that controlled the flow of communication between modules. Code modules then opened all of their mail during their update, processed that mail, prepared new messages to send, and returned. These modules could then contain other sub-modules and thus animation and locomotion could both be handled in the same module. All of this is gained at no measurable performance overhead and in most cases, leads to a faster runtime.

In this system, modules for code could be tested in isolation. You could construct a minimal game with only a few other modules and link your new module to it. You could make sweeping changes to your own module without any chance of breaking someone else's module (very little chance really). In most cases, we could easily have junior programmers working side-by-side on code without too much concern because they could work in isolation from everyone else and could not break the game. Obviously, this way of development led to a very stable codebase.

Quality and flexibility are two of the main benefits of this modularization. For me, testability and provability are also important keys that you gain because you can readily test modules in isolation or in unit tests with very simple test harnesses. This model is very similar to the language called Erlang. Recently, Microsoft has added support for this development paradigm to .Net with something called Axum.

I sure hope that Ubisoft Vancouver does well and for my part, I say that engine model is brilliant.

What Mickey Kawick brings to the table

Describe what you would be doing in your next position. This is often a very broad description and it’s quite possible that your actual next position will differ from this quite a lot. The intent of this question is to understand your current goal as you understand it so please include your thoughts regarding tasks, studio environment, and projects.

I would be a team lead of a core tech team in change of tools, communications (real-time data manipulation of the run-time), core libraries (like STL), and others. This collection of technologies would extend eventually to include other game technologies like audio, graphics, math, physics, animation and locomotion, and most basic 'systems' work. I have written code and tools for all of these categories.

The key here is leadership and I have managed small teams before. But when I manage, I bring something special to the workplace: employees feel needed and rewarded when working for me, employees enjoy coming to work when they work for me, employees are empowered to make decisions and are encouraged to bring their best ideas forward for other team members to evaluate. I use a combination of basic coaching techniques to not only motivate, not only encourage, but inspire employees to greatness.
I manage a small team of Boy Scouts here in BC (as I did in Texas) and I've helped manage baseball. The children normally are there because their parents want them to be. So a coach needs to find a set of encouraging words for each, a set of challenges that each can achieve, and a team to build besides.
Technology comes and goes, but people are really what matters and I make sure that people who work for me know it.

What do you consider to be your strongest (work-related) skills?

I'll list these topically to be as terse as possible.
Technical: C++/C, Math (a broad range most of the time), C#, software architecture, full-product life-cycle, unit-testing (one of the more important things that I bring to the table), unparalleled debugging skill, optimization and performance analysis.
People: motivation, conflict resolution, delivering bad news, soliciting feedback, team building (hiring, role assignment , and teamwork), career management and guidance.
Business: scheduling, business design patterns (firewall, sacrificial lamb), reports and dailies, contracts, managing 3rd party relationships, business plans.

Quicksort algorithm

This is the fastest non-destructive sort known and given how sorts must work, this is likely to be the fastest sort ever.

// sort everything inbetween `low' and `high'
void quicksort(int arr[], int low, int high)
{
   int i = low;
   int j = high;
   int y = 0;

   int z = arr[(low + high) / 2];// comparison value

   do // partition
   {
       while(arr[i] < z) i++; // find high element ... 
       while(arr[j] > z) j--; // find low element ... 

       if(i <= j) // swap two elements 
       {
           y = arr[i];
           arr[i] = arr[j];
           arr[j] = y;
           i++;
           j--;
       }
   } while(i <= j);

   // recurse to smaller subsets until everything is sorted
   if(low < j)
   { quicksort(arr, low, j); }

   if(i > high)
   { quicksort(arr, i, high); }
}

Shell sort algorithm

This is almost as fast as quicksort in most cases. Attempts to make this faster failed including a test and early out.

void ShellSort (int array[], int num)
{
   int inc = num/2;
   while (inc > 0)
   {
       for (int i=inc; i < num-1; i++)
       {
           int temp = array[i];
           int j=i;
           while (j>= inc && temp < array [j-inc])
           {
               array[j] = array[j-inc];
               j -= inc;
           }
           array [j] = temp;
       }
       inc = inc/2.2;  // note the subdivision value which could be 2, but 2.2 is better
   }
}

Decreasing maintenence through formatting

How important is formatting to the development process? Is aligning function names with tabs important?

It's startling how much a difference a little white-space can make in the readability of a header file. Here we have the identical class in two different scenarios. Notice how much quicker the class on the left makes sense to you and how much more quickly you can assess it's usefulness to you. As a quick test, look at the class on the right... does it allow networking? Does it write to a database? Now look at the class on the left... does it render? Which member variable stores position?

If you try to answer the questions posed above, you will find that the class on the left is almost instantly interpreted and almost a brain-dead exercise. The class on the right is almost excruciating to read. Now you might think that no programmer on Earth would ever write the code on the right, but sadly, you'd be wrong: just a few weeks ago, I ran into this exact scenario where I was put in charge of similar, nightmarish code and told to not make any changes. This example isn't even long, around 30 lines where the code I had was over 80 lines.

Without color highlighting, this situation is slightly harder for reading both cases, but in many cases, all types will be types internal to the company and thus color highlighting won't be displayed.

By aligning all functions as I have done on the left, much like you would see in a spreadsheet program (or a phone book), you can easily ascertain the functionality of this class. This dramatically improves the time to find the "right" class to do the work you need. While this doesn't affect the experienced programmer who knows the code base, new hires become almost instantly productive. Studies in code reuse and programmer productivity (HP, IBM, MS, et al) have all shown that well-aligned code can increase programmer productivity in general, not just for new hires. The extra white-space in between functions and between functions and their return values makes a huge difference. I would suggest that both are about the same in importance.

Please, for the sake of all programmers who follow you, including yourself, follow the white space example on the left.

//------------------------------------------ class AI_Bot : public StellarObject { public: AI_Bot (); void Clear (); BotState GetBotState () const; BotTarget GetBotTarget () const; UUID GetPlayerTarget () const; //--------------------------------------- virtual void Setup (); virtual void Draw (); virtual void Update (GameData&); //--------------------------------------- protected: bool CheckForTransition () const; void BeginTranition (); bool IsInTransition () const; void ResetState (); void UpdatePosition (); void IsPossibleToInterruptCurrentState (); BotState myState; BotTarget myTarget; uint32_t timeOfLastStateChange; BotState transistioningState; UUID playerTarget; Vector destination; SpaceStation* baseDestination; SpaceStation* homeDestination; BasicProjectile* selectedWeapon; }; //------------------------------------------

//------------------------------------------ class AI_Bot : public StellarObject { public: AI_Bot(); void Clear(); BotState GetBotState()const; BotTarget GetBotTarget()const; UUID GetPlayerTarget()const; virtual void Setup(); virtual void Draw(); virtual void Update(GameData&); protected: bool CheckForTransition()const; void BeginTranition(); bool IsInTransition()const; void ResetState(); void UpdatePosition(); void IsPossibleToInterruptCurrentState(); BotState myState; BotTarget myTarget; uint32_t timeOfLastStateChange; BotState transistioningState; UUID playerTarget; Vector destination; SpaceStation* baseDestination; SpaceStation* homeDestination; BasicProjectile* selectedWeapon; }; //------------------------------------------

Concurency on modern hardware

Multi-threading is a challenge for most programmers. Just the basics in threading are a little confusing. Then there is the challenge of thinking about shared resources, memory, thread-contention, cache coherency, memory bus stalls, and starvation. I'd like to briefly discuss each of these topics to create a sense of familiarity for the reader.

Overview:
What is the point of concurrency? Why use multi-threading? So how does it all fit together?

Al of these are valid questions and I'll start with the simplest question first: what is the point of concurrency.
Concurrency exists to take advantage of fast hardware. It does so often by putting different applications on different pieces of hardware. When multiple pieces of hardware are not available, it staggers the execution of applications allowing each to run for a short period. The basic idea is that CPUs are available so the OS will try to move applications around to make each appliaction run faster.

Concurrency also exists to add the appearance of "stability". What can happen in OSs that don't support concurrency is the appearance that an application is 'hung' and not executing properly. You have probably seen this in Windows from time to time when you log into a website and the browser never returns. Many things can cause this like long-waits, a program caught in an endless loop, or even a bad memory access. In any case, the program hangs. Without concurrency, the entire computer would lockup, not just your program and then you'd spend more time rebooting.

We'll discuss the other two questions throughout the rest of this discussion.

Basics:
Processes [Wiki] are the equivalent of a computer program. These are usually applications but if you bring up your Activity monitor (or Task manager), you'll see a lot of processes running which are not visible applications. These are often things related to networking, the OS, time applications, and so on. There are other things called cron processes, batch processes, and drivers which also take up CPU time but don't always appear in your Activity monitor. Each process has its own memory, performance characteristics, needs for the file system, and many other characteristics which have the potential to interfere with other processes. The differences between a thread are subtle and beyond the cope of this discussion: just consider them to be the same for now.

Concurrency [Wiki] allows us to take advantage of multiple pieces of hardware when available. When not available, all modern OS's allow multi-threading which is similar. The concept is one of allowing your CPU to execute multiple processes simultaneously. When the hardware is available, such as a Dual core Pentium or a Six core XBox360, each process can execute on a separate piece of hardware and stay out of the way of other processes, theoretically. The reality is much more complex. When hardware is not available (only one CPU for example), then the OS will stagger execution of programs making them take turns. Process1 will work for a while, then the OS will interrupt Process1 to allow Process2 to run a little bit. After a short time, the OS will interrupt Process2 and continue running Process1. This is a highly simplified example, but illustrates the basics of what all modern OSs must do.

Interrupt [Wiki] is a hardware-driven change of direction. Basically, an interrupt is like a telephone and no matter what you're doing, when that phone rings you stop and answer the phone. An interrupt usually comes from some external hardware and notifies the CPU that something has changed. In modern CPUs, this is most often a timer that tells the CPU that a certain amount of time has elapsed and this is often the cue for the CPU to change from one process to another. Even when multiple CPUs are available, the interrupts are going crazy telling the CPUs that a file has finished loading, that a DMA has completed, that a timer has gone off, or that a user has hit a key on the keyboard.

Kernel [Wiki] is the low-level code that makes determinations about which process has a chance to run every time it receives an interrupt. It routes events, suspends processes, and makes timing choices.

Process dispatch or allocation has to do with putting processes on different pieces of hardware (CPUs) for execution. This is a decision made by the OS (OSs make algorithmic choices, not true decisions) and can be overridden by configuration files. In fact, on the XBox360, you can specify on which CPU any threads will be created. Many other OSs allow similar dispatch models and configuration capabilities.

Parallel computing [Wiki] allows us to setup situations where a single task can be completed by different processes running simultaneously, often on different CPUs or chips. This is typically accomplished by the concept of scatter-and-gather where a single task is subdivided into multiple smaller tasks, the results are computed on different CPUs, and then the results are pulled together into a final result by one of the CPUs.

Race conditions [Wiki] specify some of the basic problems with threading and concurrency in general. These happen when two processes compete for the same resource and can lead to deadlock or starvation. In either case, things don't work as planned and can cause some processes to stall or not execute at all.

Synchronization [Wiki] is the traffic cop that you need to put into place to make all of this work. Basically, synchronization objects work directly with hardware to control who is accessing any given resource at any given time. This can be a piece of memory, a file, or even a section of code that only one process should execute at a time. These synchronization objects are all similar and are built on the concept of atomics which are CPU-level operations that can be executed in a single clock-cycle (very fast).

Memory bus [Wiki] is the access to RAM and can be a major bottleneck in computers with multiple CPUs.

Why use multi-threading?
Concurrency is hard. Even very experienced programmers can have great difficulty managing 'wait states', synchronization, performance problems, and design. This makes the justification of the effort to do multi-threading even more tenuous. Still, it's hard to argue with the ability to do things twice as fast (or more with more hardware). Also, the appearance of an application that responds to user interaction while opening and reading a file increases the likelihood that consumers will consider your software more professional and stable.

Other considerations are things like allowing your application to do two things simultaneously are useful since a user can only type so quickly. If you consider a word processor, it can look up words as you type, spell check, grammer check, and auto save. All of this is managed through multi-threading. Gone are the days where you had a separate step of spell-checking before printing your document (does anyone but me still remember those days?)

Also, other applications like MSN Messenger, AIM, and others allow you to stay connected to the internet while typing, adding smiley faces, and updating friend-status. In a manner of speaking, all of this is just plain magic.

How does it all fit together?
Most OSs offer a method that looks like this:
bool CreateThread (FunctionPointer, StackSize, PriorityLevel);

This can take a variety of parameters, but often it takes a stack pointer (just a pointer to RAM or a RAM size request), a pointer to a function or some code, and a priority for the thread. That's all there is to the OS support. The rest is up to you. You need to manage the synchronization but the OS will usually do the rest. Some specialized hardware has special Macros or methods to allow you to tell the OS where to put the thread (which CPU), but generally, you don't worry about such things.

A critical determination is the priority. Another may be the stack size. Let me explain why these are important. The priority affects the Kernel and helps the OS decide whether to allow a process or thread run. All threads having equal priority means that the Kernel simply let's each run in turn in a round-robin manner. Once a thread has higher priority than others, it has the potential to prevent other threads from running very much (called starvation) but can also mean that a small piece of code that you want to run quickly will receive as much of the CPU as the Kernel will give it. Low priority threads run "in the background" and can accomplish tasks with little effect on user experience. For most purposes, you should set your threads to "Below normal" thread priority unless you are certain that you don't mind affecting the user experience.

The stack size can be important too depending on what you are doing. The stack size affects stack frame which is the amount of memory available for a series of function calls available on the stack, not the free store. Every time you call a function, the current function you are in must push its data onto the stack and then load up some values which are also pushed onto the stack for inside the new function. If you are using recursion, this size can grow rather quickly. You will probably need a minimum size of 4K, but plan on needing a lot more like 16k or maybe as much as a meg is you are sorting some large dataset.

There are a few synchronization tricks and foibles to watch for and I will detail the half dozen of these in a future blog. For now, just remember to use the mutex, use it in any access to a resource or variable that you have, and use it very close to the access, not in the earliest access case or broadly. Code for this often looks like this:

void SomeBigMultithreadedClass::Foo()
{
   m_Mutex.Lock();
  
   // do something expensive like allocate RAM, access a file, etc.

   m_Mutex.Unlock();
}

Many more details will come in my next blog.

Binary search - finding a value quickly in a sorted array

Given an array of items, that are sorted, the fastest way to search through them is using a Binary Search. The time to search in log (n) so that for 1000 items, there are only ~10 loops, to search 1,000,000 items, we only have 20 loops, and to search through 1 billion items is only about 30 loops. This is very fast and does return a -1 if it can't find the proper item.

My loop here takes an array of integers but any type that accepts the < operator will work. The idea is not to return the searched for value, but to return its index.

int BinarySearch (const int* pSortedArray, int lengthSortedArray, int valueToFind)
{
   int Begin = 0;
   int End = lengthSortedArray-1;
 
   while (Begin <= End)
   {
       int Middle = (Begin + End) / 2;  // compute pivot point.
       if (valueToFind > pSortedArray [Middle])
       {
           Begin = Middle + 1;   // repeat search in top half.
       }
       else if (valueToFind < pSortedArray [Middle])
       {
           End = Middle - 1;          // repeat search in bottom half.
       }
       else
       {
           return Middle;   // return found item
       }
   }
   return -1;     // failed to find value 
}

Breadth first walking of a binary tree

While not rocket science, breadth-first walking of a binary tree is not intuitive at all. Most people need depth-first tree walking and that is often done with recursion or by using a local stack implementation. This is because you work from the top of the tree down to the bottom and then back up zip-zagging through the nodes, and pushing nodes onto the stack as you go. Breadth-first walking is a lot different because you are essentially walking the tree from left to right, then down to the next level. Typically, you are simply outputting the contents of the tree, but this does have other uses too.

Just the basics
Let's specify a simply set of requirements and see how we met those for outputting a binary tree in breadth-first order.

• It must output the contents of each node in breadth-first order.

Well, that's fairly easy. By walking the tree using a queue, instead of a stack, we can easily solve this problem. The first thing we setup is the push into the queue. This is often called enqueue but in my version of stl, it's push. We ignore the fact that if someone passes us a NULL head, we'll crash since that is a dummy mistake but you can add an assert if you find it necessary. This will be our first node that we'll print. Before printing, we'll add the left and right nodes to the queue.

Now here is the confusing part for me: how does it walk the tree just by sticking nodes into the queue? Well, here's how. Let's start with this tree. This is a balanced tree, but this algorithm works for all binary trees.

So in the code, first we push the top-most node, 0, into the queue. Then we pop it off to work with it. From 0, we grab it's left node, 1, and push that into the queue, then we push 2. Now the queue only contains 1 and 2. We print the contents of 0, then move to the next node. Then 1 is popped off of the top, and it's children are added. Then we print the contents of 1, and then move to the next node... 2. Rinse and repeat.

void PrintTreeDepthFirstStacked2 (BNode* head)
{
queue ; Queue ;
Queue.push (head);

 while (Queue.empty () == false)
 {
     BNode* currentnode = Queue.front ();
     Queue.pop ();

     if (currentnode->left)
     {
         Queue.push (currentnode->left);
     }
     if (currentnode->right)
     {
         Queue.push (currentnode->right);
     }

     cout << currentnode->Value << ",";
 }
 cout << endl;
}

A little more advanced
Nothing fancy, but let's add another requirement.

• Print a new line at the end of every level in the tree.

So this means that we need to detect the end of a line and then output a newline. How do you know when you've reached the end of a level? We can't just rely on the left and right because if we do that, we'll have a lot of false-positives. Let's look at an example: if we start from node 1 and we add left-right and output a newline, we'll we putting out a newline after 3 and 4 which doesn't suit our requirements. What we need is a sentinel or NULL node.

This is how it works. First we shove a NULL node into the queue after our head. Then everytime we run into a sentinel, we push another sentinel into the tree. Let's work this out. After the first node, 0, we detect a sentinel. We do need to be sure that we don't repeat adding sentinels forever, so we perform a simple test at the end of the queue. If we aren't at the end, we add a sentinel node. Later in the code, we output a newline if the sentinel was detected. Let's walk this a bit and see what happens.

From 0, we output it and move to the next node. It is a sentinel, so we add another sentinel which will come after the children nodes 1 and 2. Out current queue contents are: 1, 2, sentinel. Now we print a newline, and then move onto the children of 0. 1 comes around and we add it's children and we loop to 2, add it's children. In the next loop, we have the sentinel. This means that we add another sentinel, and print a newline. The sentinels are signals for more sentinels until we come to an empty queue. Look at how clean and simple the code can be.

void PrintTreeDepthFirstStacked (BNode* head)
{
   queue <BNode*> Queue ;
   BNode* sentinel = NULL;

   Queue.push (head);
   Queue.push (sentinel);

   while (Queue.empty () == false)
   {
       BNode* currentnode = Queue.front ();
       Queue.pop ();

       if (currentnode == sentinel)
       {
           if (Queue.empty () == false) // when we get to te end,
                               // we don't want an infinite repeating queue
           {
               Queue.push (sentinel);
           }
       }
       else
       {
           if (currentnode->left)
           {
               Queue.push (currentnode->left);
           }
           if (currentnode->right)
           {
               Queue.push (currentnode->right);
           }
       }
       if (currentnode == sentinel)
       {
           cout << endl;
       }
       else
       {
           cout << currentnode->Value << ",";
       }
    }
}

Casting shadows in 3D

The effort required to cast a shadow of a polygon onto another is far simpler that you may realize. All polygons are composed of vectors and for the sake of simplifying this discussion, I will only talk about creating a shadow on the ground which we will assume is flat. This isn't much harder for uneven surfaces, but it involves some polygon-on-polygon clipping which we'll discuss some other time.




So for this discussion imagine a polygon floating up in the air above the Y-plane (the plane that rotates freely around the up vector). Here we have a single polygon floating above the y-plane and we'd like to figure out what it's shadow would look like. Note that all we have is the polygon and the up vector for information.











We can deconstruct the polygon into individual vectors, create a polygon from that and move it on top of the ground. From this new polygon, we simply fill it with some alpha-blended color and we have a shadow.












Here I've shown an individual vector and this is what it might look like. You will be surprised at how little math this takes. Once you have the shadow vector, you do need to translate it into the space directly under the vector which can be done using my earlier finding a point closest to a triangle.


Here is the code for creating the vector of the shadow.

Vector    GetInPlanePortionOfVector (const Vector& vect, const Vector& PlaneNormal)
{
float height = (vect.Dot (PlaneNormal));
Vector shadow = vect - height * PlaneNormal;
return shadow;
}

Bitshifting an array of u8's

I had an interesting problem come up the other day where we needed to bitshift an array by more than 8 bits. Basically, given an array, can you bitshift the entire thing? This doesn't make much sense with signed values, so be sure to use unsigned values.

The only real approach has to do with figuring out the real shift amount. If you are shifting across multiple bytes (say 48 bits to the left), then you need to jump ahead in the array to grab the bits and put those into the current set of bits. If you shift all of the current bits off, that isn't a problem; the bit just disappear.

So the code for this looks like the following. It's pretty simple code but there are a few edge cases. We need to be sure that we don't try to read beyond the end of the array and we also need to 0 out bytes that should no longer have values after the shift.

void ShiftLeft (unsigned char* array, int count, int NumBits)
{
   int JumpGap = NumBits / 8;
   assert (NumBits>0 && JumpGap < count);
   NumBits = NumBits % 8;
 
   count -= JumpGap;// stop slightly early.
   for (int i=0; i<count; i++, array++)
   {
       *array <<= NumBits;
       *array += (*(array+JumpGap+1)) >> 8-NumBits;
   }
   if (JumpGap < 1)
   {
       *array <<= NumBits;// shift the last char
       array++;
   }
   else
   {// fill the end with 0's. We've shifted too many bytes.
       for (int i=0; i<JumpGap; i++)
       {
           *array = 0;
           array++;
       }
   }
}

When testing this code, I had to output the bit state and the code for that looks like this:

void OutputBitstate (const unsigned char* array, int count)
{
   for (int i=0; i<count; i++)
   {
       unsigned int value = array[i];
       for (int j=0; j<sizeof (char)*8 ; j++) // show as bits
       {
           if (value & (1<<7))
               cout << 1;
           else
               cout << 0;
           value <<= 1;// shift the bits off the top.
       }
       cout << " ";
   }
   cout << endl;
}

Finding memory stomps - strategies

Tracking down a memory stomp is long tedious work. Still, there are a few basic strategies that can help. Suppose you had a crash in your application which occurs after the launch or your application 1/10 of the time after anywhere from 10 to 15 minutes. Using the debugger, it appears hat a memory stomp occurs on apparently random elements of a 10000-element linked list. How would you track down this bug?

Most strategies involve instrumenting the code in some fashion and by the nature of random crashes, is likely to change the circumstances under which your memory stomp occurs. Be sure to check the before and after changes to make sure that you still see the stomp before attempting to track it down. There is no one-size-fits-all solution for memory stomps but watching your memory is a good strategy.

Before I talk about the strategies, we must cover the most common cause of memory stomps: uninitialized pointers and memory overwrites. Uninitialized pointers are becoming more rare because most people know how important this is but basically, this amounts to someone trying to use memory that was never allocated (or a pointer that we never assigned). The memory overwrite problem occurs when someone does a memcopy with too many elements writing beyond the end of a block of allocated memory.

It turns out that most of the strategies listed here capture both circumstances.

Move the stomped memory
This strategy means keeping the allocation in place but keeping the memory you want to use somewhere else. Basically, you want to allocate dummy memory that you can check for stomping periodically in the same memory location as the original stomped memory. If you check this RAM for stomping, you are more likely to track down the circumstances that cause the stomp. Just make sure that your application checks this RAM for any changes and that this check is run often. This will slow your application somewhat, but if it is just a raw block of RAM, it'll be extremely fast to check.

Memory segmentation strategy
Windows allows threads to run in their own memory space meaning that allocation by one thread are not necessarily usable by other threads. By moving some of your code into other threads, you are partly preventing the memory stomp. More importantly, when you application goes to overwrite that memory, Windows will barf because that memory is no longer available and you will get a "segmentation fault". You will know exactly when the stomp occurs.

Heap movement strategy
Memory stomps usually occur because your memory management scheme is home-grown and most of your RAM is managed. This means that you performed a huge allocation at some point and dolled out portions when people requested it.

Now, the first, and easiest, thing to do is look at your heaps. Which heap appears right before the stomped-on heap? That is a good place to start. Put some sentinel values in that heap (0xA5 works nicely, every other bit set) which you can examine readily. Now run your application and when it crashes, look at a few memory locations close to the maximum addresses in that heap. Do they still contain your sentinel values? If not, then that memory heap is also being stomped, and you just don't see the bug. But if you know who uses that memory heap, then you know whom to bang over the head.

If things aren't arranged this way in your application, consider making it so because this memory "shell game" allows you to move heaps around until you can find the offending subsystem and narrow the problem. Finding memory stomps can take a long time.

Memory sentinel strategy
Your allocation scheme can be modified, with very little effort, to include an extra byte or two at the beginning and end of each memory allocation. Most allocators do this anyway, you just may not know it. This is easy to see in the debugger by using new where you know the memory originates and looking at a few bytes preceding the pointer returned. Most allocators store between 16 and 80 bytes of extra info for every allocation you do. This helps keep extra data like who allocated it, on which thread, how many items (new item[num]), and so on. The minimum needed is a size parameter for the memory delete to know how much RAM to free at destruction time.

You can do something similar by adding a small chunk of misc data at the beginning and end of each allocation. Then, when deallocations are performed, you can check to make sure that these sentinels are still valid and throw and exception if they are not. Eight to sixteen bytes are a good starting point or for small block allocators, 2 bytes is best. Remember that all memory returned should be on 4-byte, or 8-byte, boundaries depending on bus bit width.

Third-party tools
Bounds checker is a good tool for helping track memory stomps. Usually, the instrumentation of the code that bounds checker does masks the problem, but this can still be a fabulous tool for tracking memory stomps and the performance can be minimal with a few minor settings changes.

Walking the memory
The stomped memory is being victimized by another portion of your application. But catching the criminal has been elusive, so one way is to periodically walk the RAM and report changes. You know approximate time when the stomp occurs, so see if you can turn on/off the "stomp checker" and just walk the RAM looking for important changes like bad pointers or whatever. This will slow your application a lot, but it can throw an exception as soon as it "sees" any changes and thus you can narrow down who is giving you grief.

Using some combination of these should allow you to track down memory stomps. Don't give up and never accept that the bug mysteriously 'disappeared'. The sooner you find it and squish it, the sooner you can get onto coding more fun things.

The balanced tree

The AA tree is the 'cool' alternative to the red-black balanced tree. Balanced trees are a great way to guarantee the minimal run-time impact when searching for a particular node in your binary tree. The typical run-time complexity of a binary tree is O log(n) but if the tree is unbalanced, a worst case scenario could mean that your tree has linear run-time or O (n). A balanced tree means O log (n) insert, search, and delete. Technically, because an average is the most likely scenario, the typical run-time is O log(n)/2, but complexity measurements usually ignore constant multiples.

This AA tree is very fast, and lightweight. It is also more cache friendly because of the fact that it operates almost entirely in one function when adding nodes to the tree and when removing nodes. In addition, it is quite small. I have included a copy-and-paste solution below for this slick algorithm. Have fun with it.

template <typename type>
struct AABinaryNode
{
type Data;
AABinaryNode* Left;
AABinaryNode* Right;

int Level;

AABinaryNode () : Left (NULL), Right (NULL), Level (0)  {}
AABinaryNode (const type& e) : Data (e), Left (NULL), Right (NULL), Level (0)  {}
AABinaryNode (const type& e, AABinaryNode* l, AABinaryNode* r) : Data (e), Left (l), Right (r), Level (0)  {}
~AABinaryNode () {}

};
template <typename type>
AABinaryNode <type>*
RotateWithLeftChild (AABinaryNode <type>* k2)
{
AABinaryNode <type>* k1 = k2->Left;
k2->Left = k1->Right;
k1->Right = k2;
return k1;
}
template <typename type>
AABinaryNode <type>*
RotateWithRightChild (AABinaryNode <type>* k1)
{
AABinaryNode <type>* k2 = k1->Right;
k1->Right = k2->Left;
k2->Left = k1;
return k2;
}

//*******************************************************
//*******************************************************

template <typename type>
class AATree
{
public:
AATree ();
~AATree () {FreeTree (Root); delete NullNode;}

bool  Insert  (const type& x) {return Insert (x, Root);}
bool  Remove  (const type& x) {return Remove (x, Root);}

const type& FindMin  () const;
const type& FindMax  () const;

const type& Find  (const type& t);
bool  WasFound () const {return CurrentNode != NullNode;}

void  Clear  () {FreeTree (Root); Root = NullNode;}
void  IsEmpty  () const {return Root == NullNode;}

void  Display  (bool WithLevels = false) const;
private:
AABinaryNode <type>* Root;
AABinaryNode <type>* NullNode;
AABinaryNode <type>* CurrentNode;// result of the last search

void  Skew (AABinaryNode <type>* & t);
void  Split (AABinaryNode <type>* & t);

void  FreeTree (AABinaryNode <type>* t);
bool  Insert (const type& x, AABinaryNode <type>* & t);
bool  Remove (const type& x, AABinaryNode <type>* & t);

const AATree& operator = (const AATree& );// disable the operator
};

//*******************************************************

template <typename type>
AATree <type> :: AATree ()
{
NullNode = new AABinaryNode <type> ();
NullNode->Left = NullNode->Right = NullNode;
NullNode->Level = 0;

Root = NullNode;
}

//*******************************************************

template <typename type>
const type& AATree <type> :: FindMin  () const
{
AABinaryNode <type>* Walker = Root;

while (Walker->Left != NullNode)
{
 Walker = Walker->Left;
}
return Walker->Data;
}

//*******************************************************

template <typename type>
const type& AATree <type> :: FindMax  () const
{
AABinaryNode <type>* Walker = Root;

while (Walker->Right != NullNode)
{
 Walker = Walker->Right;
}
return Walker->Data;
}

//*******************************************************

template <typename type>
const type& AATree <type> :: Find  (const type& x)
{
NullNode->Data = x;
CurrentNode = Root;

while (CurrentNode->Data != x)
{
 if (x < CurrentNode->Data)
 {
  CurrentNode = CurrentNode->Left;
 }
 else
 {
  CurrentNode = CurrentNode->Right;
 }
}
return CurrentNode;
}

//*******************************************************

template <typename type>
void
AATree <type> :: Display  (bool WithLevels) const
{
const int MaxLevels = 24;
AABinaryNode <type>* Stack [MaxLevels];
int StackTop = 0;

Stack[StackTop++] = Root;
while (StackTop > 0)
{
 --StackTop;// reduce the stack
 AABinaryNode <type>* Node = Stack[StackTop];// pop
 if (Node->Right != NullNode)
 {
  Stack[StackTop++] = Node->Right;
 }
 if (Node->Left != NullNode)
 {
  Stack[StackTop++] = Node->Left;
 }
 if (WithLevels)
 {
  cout << Node->Data << " - " << Node->Level << ", ";
 }
 else
 {
  cout << Node->Data << " ";
 }
}
cout << endl;
}

//*******************************************************

template <typename type>
void
AATree <type> :: Skew (AABinaryNode <type>* & t)
{
if (t == NullNode)
 return;

if (t->Left->Level == t->Level)
{
 t = RotateWithLeftChild (t);
}
}

//*******************************************************

template <typename type>
void
AATree <type> :: Split (AABinaryNode <type>* & t)
{
if (t == NullNode)
 return;

if (t->Right->Right->Level == t->Level)
{
 t = RotateWithRightChild (t);
 t->Level++;
}
}

//*******************************************************

template <typename type>
void
AATree <type> :: FreeTree (AABinaryNode <type>* t)
{
if (t != NullNode)
{
 FreeTree (t->Left);
 FreeTree (t->Right);
 delete t;
}
}

//*******************************************************

// insert item x into aatree rooted at t
// if x is duplicate, return false

template <typename type>
bool
AATree <type> :: Insert (const type& x, AABinaryNode <type>* & t)
{
if (t == NullNode)
{
 t = new AABinaryNode <type> (x, NullNode, NullNode);
 t->Level = 1;

 return true;
}
else if (x < t->Data)
{
 Insert (x, t->Left);
}
else if (x > t->Data)
{
 Insert (x, t->Right);
}
else
{
 return false;
}

Skew (t);
Split (t);
return true;
}

//*******************************************************

template <typename type>
bool
AATree <type> :: Remove (const type& x, AABinaryNode <type>* & t)
{
bool ItemFound = false;
AABinaryNode <type>* DeletePtr;
AABinaryNode <type>* LastPtr;

if (t != NullNode)
{
 LastPtr = t;
 if (x < t->Item)
 {
  Remove (x, t->Left);
 }
 else
 {
  DeletePtr = t;
  Remove (x, t->Right);
 }
 // remove if at bottom of tree
 if (t = LastPtr)
 {
  if (DeletePtr != NullNode && x == DeletePtr->Item)
  {
   DeletePtr->Item = t->Item;
   DeletePtr = NullNode;
   t = t->Right;
   delete LastPtr;
   ItemFound = true;
  }
  else
   ItemFound = false;
 }
 else if ((t->Left->Level < t->Level - 1) ||
    (t->Right->Level < t->Level - 1 ))
 {
  --t->Level;
  if (t->Right->Level > t->Level)
  {
   t->Right->Level = t->Level;
   Skew (t);
   Skew (t->Right);
   Skew (t->Right->Right);
   Split (t);
   Split (t->Right);
  }
 }
}
return ItemFound;
}

//*******************************************************
//*******************************************************

Performance to Productivity to Results

Basic programming skills in the software engineering world are not going to take you very far. I still wonder why software engineering interviews focus on bit flipping, linked lists, walking a binary tree, and so on. Even slightly more advanced topics like design, polymorphism, and serializing data aren't all that helpful because it limits you to the 'what do you know'. These types of questions are all about raw memorization and some intellect, but do not capture the essence of what engineering is.

Engineering is about results. It is about crafting an idea into something. Raw performance (i.e. how fast or much code you write) tells us very little about how productive you are and certainly speaks nothing about your ability to deliver a complete tool, system, networking solution, database integration solution, or whatever. It tells us if you know the basics and if you can sling some code.

So the question becomes: what is the difference between performance and productivity? How do I increase my performance? Productivity? How can I get better results?

Performance
Performance in software development is measured differently by everyone and metrics are hard to come by. These are often related to some form of number like Lines-of-code-written, Bug fix-rate, number of files checked in during a day, or some other easily recorded numeric value. These are also very easy to inflate by adding functions that are never called, fixing easy bugs or making bugs and later fixing them, or by 'refactoring' code. If you don't think people cheat this way, nearly everyone does in the right circumstances (everyone I have worked with does, but maybe the reader does not).

Performance is most often related to the ability to "crank out code" and find cool solutions to atomic problems, i.e. problems that aren't strongly related to bigger problems.

Productivity
Productivity is a different measure entirely and is a far more useful way to measure someone's value to an organization. This is best illustrated in "integration" and "submission" where any piece of code, data, art, music, or whatever can easily be put into the final product. Productivity most often means tools, pipelines, and efforts at reducing code redundancy.

Productivity also means working with others. Rare indeed, is the lone programmer who manages productivity by himself/herself. This is where you recognize the usefulness of your boss who should be actively coordinating your efforts with other people, teams, and outside vendors. This is also where one gives up the idea that s/he is the "best programmer on the team" and embrace that s/he can learn something from nearly everyone. This is really where a person begins to add value to a company.

Measuring this human quality is no harder than measuring someone's ability to code. Simple questions of product lifecycle, useful management structures, and seeing how someone interacts during an interview often reveals the ability of that person to work on a team and to work toward a solution with others rather than trying to solve the whole thing himself/herself.

Results
The process of shipping a product is so different than actual product development, that it belongs in a separate category called finaling. This can mean some long hours, sleeping under your desk, and some intense debugging sessions. The pressure is on and people often ask themselves a few weeks into the process if they will ever see the sun again. I certainly have become a lot whiter during these sessions.

Putting an application in a shippable state means tracking every conceivable bug, integrating the latest version of the third-party library, and communicating with everyone on the project very regularly.

This phase is another area that is fairly easy to measure beforehand or during interviews. Simple questions like "tell me about a finaling disaster that you've seen" or "tell me what really worked on your last finaling experience" help to provide depth of experience. Other keys are how well a person prepares for finaling, does s/he know what a TSR (TRS) is (vendor requirements before submission or lot cheks), does s/he see the value of a zero defect rate, and so on.

Conclusion
These three factors are the key differences between junior, mid-level, and senior-level engineers. They amount to coding, integration, and finaling and deeply illustrate a person's ability to forecast, demonstrate, and recognize new needs before they arise. When looking to your staff and looking for leadership, this is often a good place to look. It's one thing to be able to tell people what to do and it's another thing to be able to recognize the train before it hits you. Senior people can do both.

Aligning teams

In recent years, I've come to understand the concept of alignment which I now realize is the cornerstone of any productive enterprise. Certainly in engineering efforts, alignment of company ideals, team management, and individuals should mean that everyone is working toward the same team goals. This factor is naturally assumed at all companies because "everyone is on the same page" but the fact is that even well-aligned companies rarely have everyone "on the same page." Alignment comes from communicating ideas, goals, ideals, and needs from top to bottom and back to the top again. The top-down communication is generally assumed at all companies, but the bottom-up rarely is. Basically, fomenting a company philosophy of open-dialog between parties leads to better products, easier work life, and a happier staff.

My intent here is to define alignment in more certain terms and to provide a framework for discussion and analysis.

Alignment
There are several great articles and books on this subject [Strategic Alignment: Leveraging Information Technology for transforming organisations] and these have more to do with "straightening out" IT such that it more tightly meets the business objectives. This involves governance and defining key organizational objectives and filtering those down into the organization such that the IT is transformed. Quoting Wikipedia: Business/IT alignment is an ongoing process that will optimize the relational mechanisms between the business and IT organization by working on the IT effectiveness of the organization in order to maximise the business value from IT.

Clearly this is a little myopic. More and more organizations rely on IT to perform larger slices of their businesses and many companies are built around IT delivering new products, especially IT-based companies (e.g. Microsoft, IBM, Qualcomm). In addition, this concept can be defined more broadly to include other engineering sciences and how they bring value to a company.

Team
A team is loosely defined as a set of people working in an organization separated by a few levels of management from the executive staff. Their objectives are often that of engineering and creative enterprises that indirectly add to the earnings potential of the company.

How do businesses view engineering
Engineering is the lifeblood of most companies shipping products these days and business is beginning to realize that these people are some of the most important people to a company's product-line and long-term growth.

For many engineers in the trenches, they feel saddled with the dogma that IT or Engineering is an expense. Basically, they feel that they exist to suck money out of the company. Few companies would explicitly recognize this fact, but at its basest level, this is the view. This can make engineers feel petty and makes their lives feel futile unless they realize that nearly all employees are viewed in the same light, except perhaps for the CEO and the executive management depending on who you ask. Basically, human capital is an expense and it is generally the most largest part of any company's business expenses.

So, on the topic of alignment, we can already see that an engineer's view of his place in an organization is probably misaligned with that of the leadership team of that organization, the extent to which is defined by that management. There is a lot to be said for companies that respect individuals who pore over tomes of technical specifications attempting to meet some product description or bridge requirement. This leads to better alignment at the onset of a relationship and fosters a mood of "partnership" which we'll discuss in some detail later.

Aligning the goals of the engineers with those of the company can mean that the engineer feels more able to approach management with technical "concerns" helping management to align better with clients. This cycle of communication leads to adjustments to contracts, money changing hands, and better client relationships meaning more future contracts.

Unaligned engineering goals can mean fewer interactions between engineers and management. This often leads to missed deadlines with little or no explanation, products that are poorly designed or don't meet requirements, and broken promises with clients. This nearly always leads to fewer future contracts and less capital.

Incidentally, these concepts apply to a lot more than just engineering.

How engineering views management
This point of view is often fraught with misconceptions. Engineers rarely think of the CEO or the executive staff as idiots, but they often do feel very disconnected with the goals that the executive staff set for the company. Some of the reasons lie with the fact that company execs often view the world in margins and bottom lines while responding to investor concerns. This set of business-related objectives rarely maps well to engineering objectives. In addition, engineering is all about process and planning and what engineers fail to realize is that business is generally all about that too. This leads engineers to believe that they are following more 'noble' principles or at least different ones on a daily basis when in fact, the principles are the same.

In most cases, engineers simply view management as too unconcerned with the engineering concerns to rely on management to help them solve problems. In other words, if managers don't understand, then an engineer often feels too busy to explain it to them. This is part of where misalignment is perpetuated. This is not where misalignment begins however.

Partnership
Making people feel engaged and involved with the decision-making of any company is quite a difficult task. By involving people in multiple discussions, many meetings, and feedback systems allowing them to feedback to management all costs money and does not ship a product any faster.

Let me say this: companies who have put partnership programs in place tend to outperform competitors by large margins. These companies include Apple, Rockwell, Hewlett Packard, and Microsoft just to name a few. Many of these programs aren't great, but their attempts to engage the employees in quality, ideas for improving the business, and money making opportunities all serve to build a sense of partnership. Partnership is one of the many tools for keeping teams aligned and here are a few of those strategies.

• Open team discussions that are brain-storming sessions and everyone must offer something.
• One-on-one discussions every few weeks between team-lead and employee to see what is happening on the shop floor.
• Product improvement incentives.
• Employee rewards programs.

Vision statements
Setting the course for your company is all about providing a "thought framework" allowing people a basis for discussion and a mantra to rally around. Ones that you may have heard are "Quality is job one", "We focus on the customer's needs", and "Why go anywhere else." It also makes clear the company's self view which helps employees align with where they stand within an organization.

A vision statement is the bedrock of a company's beliefs and can be a good set up for planning meetings and other discussions. Having multiple statements is often a bad idea but having one or two company ideals helps keep people aligned with overarching company views and smooths many discussions when employees lose focus on the needs of the company.

In spite of their ability to be trite, many of the motivation posters are positive reinforcement for the expectations that any company has when it comes to setting goals and teamwork. Companies that post a few of these posters around the office in most major rooms build morale and foster collaboration, depending on the posters chosen. Companies should consider which traits that they care to foster and find appropriate posters, mantras, and vision statements to help their teams focus.

Each team should also have a distinct flavor or character from other teams. This may mean another mantra on top of that provided by the company, differently colored jerseys, or even a team name. In any case, most employees fight with the constant personal battle to be part of something larger than themselves, but also to be distinct and team differentiation is one way to make people much more comfortable within an organization.

Engagement
An employee who sees some of his own personal goals as being the same as the company's goals is engaged. This means that the employee has aligned himself to the goals of the company. This is a fairly common occurrence at most companies and certainly worth considering. The majority of employees when starting a new job take a wait and see approach to seeing how the company behaves and whether or not s/he can see himself working there long term. Fostering a sense of engaging the employee and encouraging employee ideas will build better team members, better teams, a better company, and ultimately better products. Not too surprisingly, many engineers find themselves engaged in such a way that they are often thinking about engineering issues outside of work.

The overwhelming majority of employees do not enter into a working contract with any sense of insubordination or malice. Disengagement is one area that breeds feelings of distrust and malice. When employees feel that they are not aligned with the company, even ethically misaligned, the employee can become disengaged and recovery from this mental state is often difficult or even hopeless. If an employee begins to see the company as not serving customer needs, disingenuous in their claims or mantras, dishonest in their dealings, or capricious in their dealings with employees, the employee most often becomes disengaged. These areas fall into a business ethics discussion and are not really part of an alignment strategy, but these kinds of company 'misdeeds' will sabotage any efforts a company may make regarding alignment and "keeping employees on board with the company vision."

Another area that leads to disengagement is fear. Most employees have a certain level of fear built in which usually manifests as respect for superiors and working well with others. Few employees run amok in a company out of this sense, at least at some level. But fear works on even stout minds and eventually creates a fear-engagement. This is a "watch your back" mentality which courses through the company and undermines individuals and entire teams. People lose the ability to create, being too focused on keeping their jobs to do their jobs effectively. The causes of this type of disengagement are corporate bullying, financial losses at the company, the announcement of job cuts, and other factors which affect the welfare of he employee. Often, just seeing a good coworker be fired is enough to disengage the employee.

Defining goals
General goals are easy to define but hard to maintain. Keeping the company's mantra foremost in the employee's minds is never easy and falls along the lines of constant reminding. The basic rule of management is to be prepared to repeat everything you say at least 5 times. With that in mind, there are a few strategies for making sure that the company-wide goals are well understood by all.

Quarterly reviews of employee status is fairly common and this is a great time to repeat the basic company tenets and mantras. This is also a good way to make sure that the employee is attempting to hit that mark and if s/he is aligned with the company goals.

Most business theorists agree that the CEO sets the tone for the company and should speak periodically to remind everyone what the goals of the organization are. These company meetings serve to be a sound board for filtering information down to employees and keeping the company aware of recent developments, recent promotions, cash flow issues, strategies for the company, and the overall goals for the period.

However, an added step that works is to involve employees in these meetings. Home Depot employs this strategy to great effect by a once-monthly meeting called "Breakfast with Bernie". Bernie is one of the founding partners of the company and they utilize a network broadcast to all stores in the company on a Sunday morning. Part of the meeting is dedicated to feeding down status to the entire company. Another part is a Q&A with employees at different stores. A person is chosen from a few stores (usually 2) and a live question is posed to Bernie. This illustrates open lines of communication between upper mgmt and the employee. It also involves the employees creating lines of trust.

Nearly all people know what a goal is. But a goal loosely defined is a goal misinterpreted, particularly in engineering. All engineers are smart individuals, but they cannot know exactly what the intent of management, customers, marketing, and others desire. They will do their best, and they will naturally assume that once they hear the request/requirement as it is handed to them, they understand it. They are usually wrong, of course. The best way to keep everyone working toward the same goals is periodic review and this is where SCRUM can aid us. Keeping clients and engineers talking helps greatly.

Safe to fail
When things don't go well, people can easily fall into the blame game. In fact, this is so common, it is basically an expected human failing. To help keep focused on company goals, discourage the blaming of others for minor mistakes, the harsh criticism of poorly worded emails, and the acrimony that may come from a strangely worded question during a team meeting. We all do these things from time-to-time and while some level of criticism is appropriate, any openly public display of ridicule is likely to shut future doors of communication for all who witness it.

Missed deadlines are a constant source of aggravation for management as they try to mitigate disaster with their clients, yet making this a major source of concern or ridiculing engineers for under estimates will cause them to push away and not offer to do any extra work. Part of being an engineer is dreaming about what can be and making it happen, but engineers often become mired down in the minitue of the integration that they forgot to estimate. Often, effort is underestimated and this is the nature of engineering, but a correct strategy of biweekly deliverables, or partial SCRUM, means that any overages are caught early, that the work is more easily estimated, and that everyone understands what is at stake. This creates alignment upward promoting communication that can easily be managed by team leads, sales staff, and even the executive staff reporting to the board of directors.

Managers who understand the engineering process of requirements capture, architecture, design, implementation, integration, debugging, and maintenance can become a serious partner in the relationship between marketing, executive staff, and engineering. Making a safe-to-fail policy also means not jeopardizing anyone's job due to a missed deadline or failed attempt at a task. Most big gains in the world in engineering come with many failed attempts. This does not mean allowing a bridge to collapse is acceptable, but if early prototypes collapse and computer simulations fail to work, this should be considered part of the process, not the end of an engineer's job.

Flat management structure.
Too many layers: this is the bane of many an engineer. How does s/he communicate with the management staff and feel connected to the goals of the executive staff with so many layers of management? This is a huge problem at most larger companies where at least 3 layers exist between the CEO and the engineer. There are a few strategies for dealing with this issue.

The once a month (or once per quarter) meeting of the CEO to the entire company helps to keep people's minds on the company's goals. Team-related goals that are discussed every few weeks helps to keep employees "on board" with the monthly mention of company goals. The suggestion box can help, but this level of effort is so trivial most people ignore it unless the company is over a certain size.

Letting people approach their boss's boss without question and without retribution is the surest way to guarantee that people can feel that the layers of management are less important to the overall importance of communication within the company. This is a true "open door" policy and allows the sharing of ideas, reevaluation of a review that seems unfair, and even discussions about the communication within the company. Allowing people to leap-frog at least one level of management and encouraging that from time-to-time means that managers are slightly more busy, but that's why they become managers.

Conclusion
There is plenty to say about creating an atmosphere of alignment in your company, but this blog should provide a framework for getting started.

I'll go into fixing your company's broken alignment in my next blog.