Archive for the ‘C++’ Category

Guarantees in sizes of C++ objects

Monday, March 29th, 2010

Well, this is really basic, but something I did not always remember. So I decided to check up on this in Stroustrup book that happened to be on my table this morning. Here is what I found:

C++ objects are expressed in terms of multiples of the size of a char, so by definition the size of a char is 1. Here is the guarantee provided by the language:

1 ≡ sizeof(char) ≤ sizeof(short) ≤ sizeof(int) ≤ sizeof(long)
1 ≤ sizeof(bool) ≤ sizeof(long)
sizeof(char) ≤ sizeof(wchar_t) ≤ sizeof(long)
sizeof(float) ≤ sizeof(double) ≤ sizeof(long double)
sizeof(N) ≡ sizeof(signed N) ≡ sizeof(unsigned N)

where N can be char, short int, int, or long int. It is also guaranteed that a char has at least 8 bits, a short and an int at least 16 bits, a long at least 32 bits. A char can hold a character of the machine’s character set.

Certainly interesting that I don’t remember half of this. Some of them are what we already know from basic computer organization class (where some of us learned C), but my memory doesn’t last that long.

P.S. This is also certainly very different from Java, where the basic “1″ is actually an int instead of a char.

Copy and move semantics

Sunday, March 29th, 2009

Recently, I have been asked some questions by an academic juniors (by a few years) about smart pointers. In the discussions, we came across terms like copy-constructible, and move semantics. While these concepts may be straightforward for more experienced C++ developers, the concepts are more absurd for programmers who are brought up in the era of garbage-collected languages.

Let’s go through the easy part first: copy semantics. When we talked about copy semantics we meant that a call like these:

vector<int> list;
<..>
vector<int> list2(list);  // Copy constructor

vector<int> list;

/* Thanks to Richie for providing a
   correct version of assignment. */
vector<int> list2;
list2 = list;  // Copy-on-assign

will results in list2 copying the content of list. The first example is an example of a copy constructor: a constructor that takes as a parameter an object of the same type as the constructor’s class (roughly-speaking), and copy the contents of the passed objects. It generally means that changing the content of list will not change the contents of list2 and vice-versa. A class with copy constructor that fulfill the copy semantic is sometime called copy-constructible.

The second example also performs copying operation. The operation is, however, implemented as assignment operator. This is sometime called copy-on-assign.

We should perhaps note that the default copy-constructor and assignment operator generally does not fulfill copy semantics. In fact, it is neither copy nor move semantics; neither here nor there. The default copy-constructor and assignment performs (more or less) a shallow copy; a mixed semantics if you like. They directly copy fields contents. If the field is of primitives type, it correctly performs copy operation. If the field is of types that correctly implemented copy semantics, the default also correctly performs copy operation; otherwise they will not adhere to proper copy semantics. Furthermore, if the field is pointer type, it will perform a copy: a copy of the address in the pointer. Hence, both the new object and the old one will contain the same address in the pointer field. Most of the time, this is not what you want.

Remember to not rely on the defaults: either implement your own copy-constructor and copy assignment, or make them private so that they will not be automatically generated. Boost has a base-class called noncopyable that you may want to use. I prefer using a macro (the macro definition is incomplete but shows the structure that we want):

#define DISABLE_COPY_AND_ASSIGNMENT(classname) \
classname(const classname& t) {} \
classname& operator=(const classname& t) { \
  return *this; \
}

// In some_class.h:
class SomeClass {
 public:
  <..>
 private:
  <..>
  DISABLE_COPY_AND_ASSIGNMENT(SomeClass);
}

Moving on, move semantics arise (more or less) because copy semantics impose performance overhead due to memory allocation and initialization. In many cases you may simply want to give the object to another piece of code without performing an expensive copy operation. In the olden days, you would simply initialize the object you wish to pass on as a pointer and simply pass the pointer to another person in the future. However, this risks 2 major issues: (1) as long as you hold a reference to the pointer, you may still be able to modify the object (a big issue when involving multi-threading); (2) you have to perform manual memory management. Hence, we arrive at modern move semantics. :)

Today, most C++ developers are well-acquainted with smart pointers (if you do not know what they meant, please Google it, they are important). One of the basic smart pointers in C++0x is called unique_ptr. A unique_ptr maintain (as its name implies) a unique pointer: when one instance of unique_ptr is holding to a pointer to an object, no other instances may have a pointer to the same object. Furthermore, people have developed techniques to ensure that you never need to hold a raw pointer at all. All seems good. Well, not really. Smart pointers usually rely on stack allocation, which means that they die (along with the object they hold) when they go out of scope. Here is where move semantics become useful:

unique_ptr<SomeClass> createSomeClass() {
  unique_ptr<SomeClass> ptr(new SomeClass(<..>));
  <..>
  return ptr;
}

// Somewhere else:
unique_ptr<SomeClass> a_ptr = createSomeClass();

Note that, technically, a copy and an assignment occurs here (however, many modern compilers may do away with the copy as optimization). First, when you return ptr, a copy-constructor for unique_ptr is called with ptr as its argument. After that, this new object is assigned to a_ptr. Note that while I said copy-constructor, a more apt term would be move-constructor. Roughly, a move-constructor will pilfer the pointer from the unique_ptr passed to it; the original unique_ptr will no longer hold the pointer. Hence, the term move semantics. Similarly, on assignment, the pointer is being moved from one unique_ptr to another.

Half the time, you would adhere closely to either copy or move semantics. However, sometime you may want to consider partial copy semantics, e.g. shallow copy. This is generally acceptable since the cost of following full copy semantics may be prohibitive. However, we usually do not mix copy semantics and move semantics together. They generally don’t play well together and will cause confusion to other developers. (There is no such thing as mixed copy/move semantics.)

Rant #2: Backward-compatibility and API-breaking changes

Wednesday, November 26th, 2008

So, recently, I’ve switched some of the codes I maintained to use this great new version of a common utility (shall not bore you with the details). The new version has tonnes of great, new stuffs. It was exciting. I managed to clean up my config files a lot just by using the new version.

Of course, the new version specifically promised that while it is breaking the API, all of its functionality that already exist in the previous version already exists in the new one and that user (i.e. me) can use an adapter classes to convert between the two versions.

All is well, until today. Today, I had to extend part of my code to work together with an older code that uses the previous API. Guess what? While the old build rules has been updated so that it can depend on the new build rule for the new version, the reverse is not true! Hold on! Why!? Yea, that surprised me a lot! So I had two options, extracting the part I need and update it to use the new API and make the two systems depend on this or update the older code to use the new version.

I chose the latter because it wasn’t a huge amount of work and the design is cleaner if I kept with the old design (breaking up that part of the code seems rather hackish to me). After half an hour of updating the old code, I got both system working together well (I wrote some script to automate some of the task, if you’re wondering why it takes only half an hour). The code links well, though since there are many other codes that depend on the other code that I just modified, I had to run the API in a compatibility mode, but that’s no big deal.

Only minutes later, when I started writing unit tests (before I even started writing my production code), I realized that, umm, once the new API works on compatibility mode, you have to use the adapter class to get the new functionality I need. There is no automatic detection, everything is manual! No convenient methods to convert one to another easily (I mean it’s C++, they could easily write operator() to convert from one to the other pretty darn easily!). Crap! I realized that I had to modify the codes in far too many places to make this worth it. So I just decided to ditch the feature I need.

There are so many lessons I learned from just today’s experience. If I were to write the new API, I would have provide automatic conversion between one to another, I would have backported some of the most important new features (mind you, these new features are very doable with the old version), I would try my best not to make any API-breaking changes. You know, having the old and new data structures extend the same base class would have been much better.

Lastly, seriously, I know there were some serious problems with the old code, but I’d rather have those codes deprecated slowly over time while the new code is being phased in. During this transition, you better don’t just introduce new features on just the new code (or worse, just the old code). You need to support both of them, or otherwise, help people who use the old version migrate. This is no open source code, it’s a privately-owned code. While the code base is arguably huge, there have been evidence of successful deprecation in the past, why can’t this one do that?

C++’s scoped_ptr and unique_ptr smart pointers

Sunday, November 23rd, 2008

I got bitten again just the other day when I was modifying old code. It crashed. Yes, I added an extra delete when one is not required resulting in a double deletion. It reinforced my belief that most pointers in C++ should be smart pointers. A new C++ programmers will be caught often for memory leaks for forgetting to delete a pointer. As you get more experienced, while forgetting to delete becomes far less of a problem, double deletion becomes more rampant (Hey! It’s hard to keep track of object ownership you know? Especially when you’re rushing to modify other people’s code before deadline…)

scoped_ptr

To the rescue is Boost scoped_ptr smart pointer. There are two main reasons, in my opinion, to use scoped pointers.

Scoped pointers ease manual memory management. It holds a pointer to the object that it manage and it performs automatic deletion of the object it holds when it is deleted. The scoped_ptr object itself is a templated auto pointer, which means that it will be deleted automatically when it goes out of scope. Here is a simple, incomplete implementation of scoped_ptr:

template <typename T>
class scoped_ptr : noncopyable {
 public:
  explicit scoped_ptr(T* p = NULL) { p_ = p; }
  ~scoped_ptr() {
    if (p_ != NULL) delete p_;
  }
  void reset(T* p = NULL) {
    if (p_) delete p_;
    p_ = p;
  }

  // Some implementation may choose
  // to crash if p_ is NULL for the
  // following 3 operators.
  T& operator*() const { return *p_; }
  T* operator->() const { return p_; }
  T* get() const { return p_; }
 private:
  T* p_;
};

Let’s analyze the class. It extends Boost’s noncopyable interface (some would prefer to use macro for this), which implies that a scoped_ptr object may not be copied or assigned to another scoped_ptr. It induces a strict ownership of the owned pointer. As you see above, the destructor of scoped_ptr simply delete the held pointer, similarly with reset(T*) method.

This brings us to a second, more important point. scoped_ptr enforces a strict ownership of an object. In another word, it forces us programmers to think and then rethink about the ownership of an object. Many times, the problem with C++ developers are not forgetting to delete. It is not knowing who exactly owns an object. For example, let’s check out the following really simple class definition:

class ConfusedClass {
 public:
  ConfusedClass() {}
  ~ConfusedClass() {}
  void DoSomething() {
     a_ = b_.PerformSomething();
  }
  AnotherClass* GetA() { return a_; }
 private:
  AnotherClass* a_;
  YetAnotherClass b_;
};

In a world without scoped_ptr, this class can be really confusing. Who owns the object held by a_? Is it b_? Is it ConfusedClass? Or is it the class who calls GetA? The last option looks unlikely here. But it’s pretty hard to differentiate between the first two cases! A subsequent reader of the class definition would probably need to dig YetAnotherClass to determines that information. (Note also that the destructor is empty, it can be that b_ holds the object held by a_, or… it can be a bug—forgetting to delete a_!)

With scoped_ptr, when we write ConfusedClass, we should be thinking about the ownership of the object held by a_. And if we think this class should owns it, we should use scoped_ptr<AnotherClass> a_ instead! That way, subsequent reader of the class definition knows for sure that the object is owned by ConfusedClass (or shall we call it SmartClass now).

As a bonus, code with multiple exit path will be easily managed with scoped_ptr (instead of hunting each exit path and making sure all the pointers that should be deleted are deleted). Imagine how troublesome it is to manage a method with a throw for example. (I remembered writing a Java code where I’ve had to always have 3 if blocks in the finally part of a try-catch-finally, to actually check for null and close a ResultSet, a PreparedStatement, and an SqlConnection. In C++, I’ll simply write a wrapper similar to scoped_ptr to perform the closing.)

unique_ptr

C++0x expands the smart pointer repertoire even more with unique_ptr (Committee Draft §20.8.12). This smart pointer has a strict ownership as with scoped pointer. However, it is MoveConstructible and MoveAssignable (as described by the CD). What those jargons mean is that a unique_ptr s can be constructed with parameter of another unique_ptr u with a corresponding ownership transfer of the held object from u to s (MoveConstructible) and a unique_ptr u can be assigned to another unique_ptr s with ownership of the owned object transferred from u to s (MoveAssignable).

This pointer adds a little extra value to scoped pointer version. That is, you can transfer ownership (there is no release method in scoped pointer, while unique_ptr has not just a move constructor and move assignment, but also an explicit release method). This is basically a better version of std::auto_ptr (I’ve heard talk of making auto pointer deprecated).

To effectively used smart pointer, use the correct smart pointer for each of your needs. If you need a strict ownership semantics without any trasnfer, use scoped_ptr. If you need ability to transfer ownership in addition to that, use unique_ptr (or std::auto_ptr). Even better, make such rules part of your software/company’s style guide. Future maintainers will thank you when he can easily see an orderly semantics in the chaos.

shared_ptr

There is another smart pointer introduced in C++0x. The name is shared_ptr (CD § 2.8.13.2). This pointer is basically a referenced-counting smart pointers that implements shared ownership of the held object. When the last shared_ptr holding the particular object is destructed, the object is deleted too. Now, I won’t delve too much into this smart pointer because I believe in strict ownership as opposed to shared one. There should be a very, very rare situation where it demands shared ownership of an object. In a good software design, only one object should owned a particular object.

Now there is one place where shared_ptr is very, very useful: the STL containers. When you insert or retrieved a member into an STL containers, a copy of the object is made. For performance reason, keeping a pointer in the containers make lots of sense (especially when copying is expensive). As with any pointer usage, it becomes very hard to keep track of these objects. Hence the usage of shared_ptr. Copying a shared pointer is cheap. Additionally, there’s no risk of forgetting to delete a pointer within an STL containers. (Keep in mind that shared_ptr is usually twice as big as a normal pointer as it needs to keep another pointer to the reference counter.)

Example usage:

vector<shared_ptr<ClassA> > vector_of_a;
hash_map<int, shared_ptr<ClassA> > map_of_int_to_a;

John Resig’s degrading script tags

Thursday, November 13th, 2008

I just re-discovered this interesting Javascript trick from John Resig’s blog (link here). Under usual circumstances, I would frown when I see eval in Javascript code, the one construct I tried to avoid like a plague. But I don’t resist interesting usage of eval. This is one of them. Basically, the trick allows you to have a script tag with an embedded Javascript, like this:

<script src="some_js_file.js">
  // Do something with the loaded file.
  callSomething(); ...
</script>

Interesting huh? To make this work, the loaded script file itself will end with the a two-liner that basically find the script element and evaluates the innerHTML of the element:

var scripts =
    document.getElementsByTagName("script");
eval(scripts[scripts.length - 1].innerHTML);

Ingenious. As an added bonus, the content of the script element will not be executed if the Javascript fails to download (since, obviously, the last two lines that we just added won’t be executed).

Also interesting is how this hack utilizes the synchronous property of Javascript loading. In most browsers except the most recent ones (most of them still in beta/nightly), whenever a script tag is encountered, the rendering stops until the script is downloaded and executed. That means by the time the script is loaded, it knows for sure that the script tag it is in is the last one on the DOM since nothing else has been rendered. Thus, you can access the element by using the above method (see scripts[scripts.length - 1] part of the code).

I’m a little bit behind with how newer browsers download its Javascript. I suspect that the method above may not work. I guess it’ll depend on the heuristics the browsers use to make Javascript download not blocking. I heard that Firefox will actually assume that the script does not do anything to the DOM and continues rendering, in which case the above technique may not work. (I’m sure I’m missing something, probably there are some heuristics that FF used that I’m not aware of.)

Well, still, it is an ingenuous way of utilizing eval.

Template concept feature (C++0x)

Friday, October 31st, 2008

So I was kind of bored and went on to read parts of C++0x committee draft that were published recently (was it just last month?). A copy is available at the C++ standards committee website. I have heard of some new interesting stuffs that’s coming with C++0x, but wasn’t really paying attention to their specifics. So when I read them in the standard paper, the specifics started to blow me out! The one thing that interest me a lot (other than all those functional programming’s lambdas) is template concept (§14.9.2).

As you may already know, C++ has long supported generic programming through template. Simple example:

template <typename T, typename U>
class pair {
 public:
  pair(T t, U u) : first(t), second(u) {}
  T first;
  U second;
};

That defines a pair container that can contain a pair of anything! Straightforward, isn’t it? It is, up to a point. Note that this is also a valid template:

template <typename Runnable>
void schedule(Runnable* task) {
  // Let's delegate to a scheduler
  // to schedule the task.
  scheduler_->run(task);
}

class scheduler {
  <..>
  template <typename Runnable>
  void run(Runnable* task) {
    // Do something and then run the task.
    <..>
    task->run();
  }
}

// somewhere in main:
schedule(some_task);

What does this template requires? Yes, it needs Runnable to actually implement run method. Now remember that while we name the typename Runnable, there is nothing stopping us from using typename T for it. Runnable is not an interface! Let’s say some_task actually does not implement run method. However, when the compiler encountered schedule(some_task); in main, it has no way to determine what some_task needs to implement (it does not know that some_task needs to have run method). Similarly when scheduler_->run(task); is called, the compiler still has no reason to reject it. It only rejects the program when it encounters task->run();. At that point the compiler will throw several cryptic line that basically says, hey task does not implements run in scheduler#run, which is instantiated in schedule function, which is instantiated in main. In reality, that is 3 lines of compiler error for 1 error. If you use standard library that relies on templates heavily, it is not uncommon to have 10+ lines of compiler errors, each lines averaging at about 200 characters, just for 1 template error. I have had my share of “debugging” compiler error message.

Template concept

This is where concept comes in. Concept allows you to provide requirements for a typename. For the above example, using concept, we can transform it into:

auto concept Runnable<typename T> {
  void T::run();
}

template <Runnable T>
  void schedule(T task) {
  <..>
}

Now Runnable becomes a kind of interface (well, the committee calls it concept). Now the compiler could easily tells, the moment schedule is called, whether task satisfies the requirement of needing run method, instead of analyzing further until it encounters the requirement implicitly in scheduler#run. It can then inform the developer the moment he tries to use template with conceptually incompatible type. Neat huh?

It’s very powerful too. It allows several different type of requirement:

  • Availability of a non-member operator exists;
  • Availability static/non-static c-tor/d-tor/method (may specify different overloaded methods as well) exists;
  • Availability of a operator new and delete (these are necessarily member operator, hence the special case);
  • Axioms; etc.

There are more interesting concept-related stuffs. Concept refinement is of course possible (similar to class inheritance; heck, even the syntax is similar). You can also specify a default if the requirement is not satisfied. The draft gave one example of this:

concept EqualityComparable<typename T> {
  bool operator==(T, T);
  bool operator!=(T x, T y) { return !(x == y); }
}

That’s freakin’ awesome! While T may not have operator!= defined, you can provide a default implementation that will work as long as T have operator== defined.

Effect on compilation speed

At first I was excited to think that this will probably speed up compilation of bigger codebase, only to realize a minute later that I was wrong, so completely wrong. Concept provides a set of requirements that a typename must satisfy, but the template itself may use other methods/operators not specified by the concept! That means that the usual static type-checking must still be done, in addition to checking that the typename satisfies the concept! So compilation speed definitely goes down. That’s a definite blah, but the benefits seem to far outweigh the additional burden placed at the compiler.