User Experience Revisited


I started a new job this week, working at HBO. After nearly 13 years at a software company, it’s invigorating to be at a content company. The challenges are completely different. The acronyms are new. The focus is on user experience.

One of my favorite books is a collection of essays by Joel Spolsky called User Interface Design for Programmers. Although some of the examples are dated, the key concepts are still relevant.

In preparation for some work my team will be doing on UI, I’ve been reading the online version of Joel’s book. I was struck by his axiom of all UI design: A user interface is well-designed when the program behaves exactly how the user thought it would.

It reminded me of my personal pet peeve of UI design — keyboard entry. I avoid the mouse whenever I can, because (like many software engineers) I’m more efficient when my hands stay on the keyboard. Now consider most websites. They’re often designed for the mouse as the primary form of input, even for things that require the keyboard, such as user names or address forms.

When you go to a banking or credit card site, what’s the first thing you do? You enter your user name. Yet how many sites default the keyboard focus to the user name field? The number is far short of 100%.

Takeaway: when you’re designing UI, consider all your users, and behave the way the user expects.

The challenge with Joel’s axiom of UI design is that all your users are different. One good solution that I learned at Microsoft: create a small suite of user profiles and test against those profiles. For example, you might have a profile that describes a student user, a pro user, and a business user.

And if you’re developing a new website, set the initial keyboard focus to the user name field.

Posted in Computers and Internet, UI | Tagged | Leave a comment

Fun with Powers of Two


Recently I needed to know the maximum number of decimal digits in a 64-bit unsigned integer. I put together this handy table as a reference.

Value Decimal Decimal Digits
2^8 256 3
2^16 65,536 5
2^32 4,294,967,296 10
2^64 1.8 x 10^19 20
2^128 3.4 x 10^38 39
2^256 1.16 x 10^77 78

As the exponent doubles, the number of digits tends to double. If you remember than a 32-bit number has at most ten decimal digits, then it’s easy to remember that a 64-bit number has at most twenty decimal digits, and so on.

Here’s another useful trick involving powers of 1024.

n Power of 2 Decimal Think Decimal Digits
1 2^(10n) 1024 1 thousand (10^3) 3+1
2 2^20 1,048,576 1 million (10^6) 6+1
3 2^30 1,073,741,824 1 billion (10^9) 9+1
4 2^40 1.1 x 10^12 10^12 12+1
5 2^50 1.1 x 10^15 10^15 15+1
6 2^60 1.2 x 10^18 10^18 18+1
7 2^70 1.2 x 10^21 10^21 21+1
8 2^80 1.2 x 10^24 10^24 24+1
9 2^90 1.2 x 10^27 10^27 27+1
10 2^100 1.3 x 10^30 10^30 30+1
n 2^(10n) ~10^(3n) ~10^(3n) (3n)+1

Given a number that’s a power of 1024, i.e. 2^(10 x n), where n is positive integer, the maximum number of decimal digits in the equivalent value is (3 x n) + 1. For instance, for 2^20 = 2^(10 x 2) = 1,048,576, the maximum number of decimal digits is 7, because n is 2 and (3 x 2) + 1. This is true for all values of n through 97 (2^970), so this trick will be handy for a few years to come :)

Using this formula, here’s how you would quickly approximate the maximum number of decimal digits required for a 64-bit integer. Round up 64 to the nearest number divisible by 10 (70). Divide by 10 (7). Multiply by three and add 1 (7 x 3 + 1) = 22. Nice!

Posted in C++, Computers and Internet | Leave a comment

Auto Pilot


I was recently working on a small programming project, and decided to fully embrace the new C++11 keyword auto. Auto allows the compiler to deduce types. The canonical example is:

// before C++11
for( vector::const_iterator i = begin(c); i != end(c); ++i )

// with C++11
for( auto i = begin(c); i != end(c); ++i )

The compiler knows that i is an iterator based on the return type of begin(). The compiler can examine the usage of i to determine that i should either be a const or non_const iterator. The example shows two important things: 1) how much easier it is to read, and 2) how the programmer no longer has to worry about the type of c changing. If the type of c changes to a different container, or even a C-style array, the code will continue to compile correctly.

Here are a few observations from my initial experience using auto:

  • I used auto somewhat more than expected. Out of 737 lines of code, auto appears on 58 lines (8%)
  • Of those 58 lines:
    • 17 instances were for loops (29%) similar to what I showed above
for( auto i = 0u; i < len; ++i ) // common use
    • The 41 remaining instances were variable declarations (71%). Here are some examples.
// casts
auto c = static_cast<char>( tolower( letter ) );
auto p = reinterpret_cast<unsigned int*>( pData );

// typical assignments
auto len = s.length();
auto i = lower_bound( begin(c), end(c), toFind );
auto isFound = ( i != end(c) );
const auto& item = *i;
auto result = QueryPerformanceCounter( &li );
auto seconds = millisecs / 1000.0;

// typical copy constructors
auto nextItem( item );

One of my concerns was that I would miss seeing the obvious “type-ness” of variables, but that fear was mostly unfounded. The type is almost always immediately obvious. It’s certainly obvious with casts. It’s obvious when the variable name was appropriately named, such as isFound (boolean!) and len (integer!). In fact, there was only one place where I could have used auto that I chose not to — a function that established some connections between items.

void CrossConnectNodes( size_t i, size_t j )
{
    Node* pNodeI = nodeList[i];
    Node* pNodeJ = nodeList[j];

    pNodeI->CrossConnect( pNodeJ );
    pNodeJ->CrossConnect( pNodeI );
}

The Node declarations could be auto, but Visual Studio Intellisense (VS 2012) doesn’t (yet) allow you to jump to the definition of the Node class if you use the auto keyword. I suspect Microsoft will address this in the future.

I’m a fan and will be using auto on future projects. Once Visual Studio Intellisense fully supports auto, then I can completely endorse auto everywhere.

For even more recommendations on why auto is a good idea (efficiency, guaranteed initialization, and correctness), see Herb’s GotW #93.

Posted in C++ | 4 Comments

Move Construction, part IV


In my previous post, we discussed std::move(), a new function which is actually just a cast and has no performance overhead. It’s good to recall the problem we’re trying to solve.

v.push_back( Texture(...) ); // copy from a temporary

In the scenario above, we create a temporary texture object, then we create another texture object in the v container, copy the temporary to the container, then tear down the temporary Texture. If the Texture object is expensive to create or copy or destroy, then the code above generates performance overhead we’d like to avoid.

With move constructors in C++11, we can make the code above run supremely fast by swapping the guts of the temporary object directly into the vector, completely avoiding copying bits. The move constructor for Texture looks like this:

Texture( Texture&& rhs ) : // move ctor
   mpBits( std::move( rhs.mpBits ) ),
   mSize ( std::move( rhs.mSize  ) )
{
   rhs.mpBits = nullptr;
}

It’s clear from this code that we have a move constructor. There are two key elements that tip off the reader: the && rvalue reference notation and the std::move() function.

It’s important that all move constructors take a non-const rvalue reference. The reason is because we’re actually changing the internals of rhs. We’re extracting the contents — in this case mpBits. We need to set mpBits to nullptr so that when the destructor for the rhs temporary object is run, we won’t actually free the memory, since we’ve transferred ownership of that memory to a new object.

Secondly, recall that std::move() is simply a cast to an rvalue reference. Assuming mSize is an integer, the line

mSize ( std::move( rhs.mSize  ) )

is equivalent to:

mSize( rhs.mSize )

So why use std::move() at all? Two reasons:

  • std::move() tells the reader the intent. We are moving, not copying. In the case of PODs, moving and copying are equivalent, but that’s an implementation detail. Move constructors are new syntax, and one of the best ways to highlight that syntax is with std::move() notation.
  • std::move() continues to work properly should the element being moved from change to a non-POD type at some point in the future. If mSize is changed to a LargeNumber object, std::move() will ensure that the LargeNumber move constructor is called. If std::move() was not in place, we’d end up calling the LargeNumber copy constructor, which could be slower.

One of the delights of move constructors and std::move() is that you can introduce them into your code base gradually. If you call std::move() on an object that doesn’t have a move constructor, that’s OK. Due to the reference binding rules in C++11, you will simply end up calling the copy constructor. You may not get the best performance, but your code will still be correct. In the future, when you (or somebody else) adds a move constructor, your code will just run faster.

Similarly, you can add move constructors to your objects today. If the calling code doesn’t yet implement std::move() (in std::vector, say), that’s OK. The correct thing will still happen, and when you upgrade to code that enables std::move(), you’ll automatically get better performance.

Finally, some tips that summarize everything we’ve learned about move constructors:

  • Upgrade to C++11 compilers and libraries for free performance, since all standard containers, algorithms and objects are move enabled.
  • Ensure move constructors always take a non-const rvalue reference.
  • std::move is required because named objects are always lvalues.
  • Use std::move to explicitly eviscerate objects in the move constructor, even if those objects are (currently) PODs.
  • Step through new move constructors in your debugger to validate that move constructors are actually being called when you expect. Getting move constructors right can be tricky when you’re first starting out.
  • You can begin implementing move constructors in your own objects starting in low-level libraries or in high-level code — your choice. Implementation can be gradual.
  • If you implement a move constructor for an object, make sure you also implement move assignment.
  • The moved-from object will still have its destructor called. Ensure it is left in a safe state.
  • Returning expensive objects by value is more reasonable from a performance standpoint than in the past, because any temporary results can be moved from.
  • Avoid returning const T objects. Const objects cannot be moved from. Move constructors always take non-const objects, since the guts of the object must be changed.
  • By convention, ensure move constructors are as fast or faster than copy constructors. Avoid move constructors that are slower than copy constructors.

Enjoy moving!

Posted in C++ | 3 Comments

Move Construction, part III


Last time, we discussed rvalue references. Rvalue references uniquely identify objects that can be safely moved from. In the move constructor below, rhs is an rvalue reference. It refers to an object, such as a temporary object, that will only exist for another moment before it disappears forever.

Texture( Texture&& rhs ) : // move ctor
   mpBits( std::move( rhs.mpBits ) ),
   mSize ( std::move( rhs.mSize  ) )
{
   rhs.mpBits = nullptr;
}

Now it’s time to discuss std::move() and why std::move() is important.

Recall that rhs is an rvalue reference. However, there’s a problem. It has a name. You can take the address of rhs. Hence, the variable rhs, in the context of the Texture() move constructor, is an lvalue! Let that sink in for a moment.

Despite the fact that the only way the Texture() move constructor could be invoked is if rhs was an rvalue at the point of the call, the compiler must treat rhs as an lvalue in the context of the actual move constructor, because it has a name. In order to inform the compiler to treat rhs as an rvalue, we must use std::move().

std::move() does one thing: tell the compiler to treat the incoming value as an rvalue reference. That’s it. std::move() has zero performance overhead. Think of it as the equivalent of a static cast, with the type deducted automatically:

mpBits( std::move( rhs.mpBits ) );         // equivalent to:
mpBits( static_cast<t&&>( rhs.mpBits ) );  // where T is deducted from mpBits type

std::move() is provided by all C++11 implementations. It’s an inline function, so you can inspect the implementation for yourself should you care to witness reference collapsing and parameter deduction in action.

Takeaways:

  • Use std::move() whenever you need to treat a named variable as an rvalue reference, such as within a move constructor or move assignment operator.
  • std::move() is the equivalent of a cast. It has no performance penalty.
  • std::move() is self-documenting. It indicates to your reader that you intend to move from the object in question.

Now we know about move constructors, rvalue references and std::move(). Next time we’ll put it altogether, compare move constructor to copy constructors, and extract some best practices.

Posted in C++ | Leave a comment

Move Construction, part II


Last time, I provided an introduction to move construction, a new method of constructing objects in C++11. The move constructor looked like this:

Texture( Texture&& rhs ) : // move ctor
   mpBits( std::move( rhs.mpBits ) ),
   mSize ( std::move( rhs.mSize  ) )
{
   rhs.mpBits = nullptr;
}

The && notation is a little strange: two ampersands in a row. This is not a logical AND. This notation is called an rvalue reference. Rvalue references are a new feature of C++11, and they are at the core of enabling move semantics.

Before we can talk about rvalue references, we first need to talk about rvalues. In C++11, every expression is either an lvalue or an rvalue. I like to think of lvalues as Located in Memory, hence: L-values. Rvalues are not located in memory. They don’t have names, and you can’t take their address. Rvalues are ephemeral. They exist for a brief period of time, typically as temporary objects. Here are some examples:

int x;

x is an lvalue. It has a name. It lives in memory. You can take its address.

int x = 1+2;

1+2 is an rvalue. It doesn’t have a name. It doesn’t live in memory. You can’t take its address.

foo( x );

x is an lvalue. It lives in memory and you can take its address.

foo( bar() );

bar() is a default constructor that returns a bar object. That object is an rvalue. It does not have a name and does not reside in memory. You cannot take its address. In fact, bar() is a classic example of a moveable object. It is a temporary object that does not live beyond the lifetime of foo(). The result of bar() could be “moved” into foo() rather than being copied, if there was some way for the compiler to know that bar() was a moveable object.

Rvalue references to the rescue. Before C++11, a T& represented both lvalue and rvalue references. We simply called a T& a reference. In C++11, there are now two types of references. In C++11, T& is an lvalue reference, and T&& is an rvalue reference.

What does this mean? With C++11, we now have a way of uniquely identifying objects which can be safely moved from. Rvalue references uniquely identify those objects, because rvalue references bind to rvalue expressions and lvalue references bind to lvalue expressions.

Texture( Texture&& rhs ) : // move ctor
   mpBits( std::move( rhs.mpBits ) ),
   mSize ( std::move( rhs.mSize  ) )
{
   rhs.mpBits = nullptr;
}

In the move constructor, we are guaranteed that rhs represents an object that can be safely moved from. Very sweet. The next challenge is understanding exactly what it means to move from an object rather than copy from an object. We’ll cover that next time.

Posted in C++ | 1 Comment

Move Construction, part I


At GDC this year, my presentation covered move construction, a new fast method of constructing objects in C++11. Here’s how it works. Up until C++11, whenever you created a new object from an existing object, you copied the object by using a copy constructor. The copy constructor looks something like this:

Texture( const Texture& rhs ) {
   mSize = rhs.mSize;
   mpBits = new unsigned long [mSize];
   memcpy( mpBits, rhs.mpBits, mSize );
}

The problem that move constructors solve is situations like this:

Texture x( Texture(...) ); // copy from a temporary

In the scenario above, we create a temporary texture object, then we create another texture object x, copy the temporary to x, then tear down the temporary object. That’s a lot of work when it’s very clear to us as programmers that it would be more efficient to simply swap out the guts of the temporary object directly into x. That’s exactly what move constructors allow. Here’s a move constructor in C++11:

Texture( Texture&& rhs ) : // move ctor
   mpBits( std::move( rhs.mpBits ) ),
   mSize ( std::move( rhs.mSize  ) )
{
   rhs.mpBits = nullptr;
}

The move constructor allows us to do exactly what we want: eviscerate the guts from rhs. We leave rhs in a known good state. It is still a C++ object, after all — but one that will immediately be destroyed because it’s a temporary.

As a result, we can gain massive speed improvements. In this scenario, we avoid an extra allocation, a memcpy, and a deallocation. We also avoid having to hold two textures in memory at the same time.

You might have noticed something a little strange, however. The notation for a move constructor uses an unfamiliar && notation, and it passes rhs by non-const. We’ll cover this new C++11 notation next time.

Posted in C++ | 1 Comment