Stringing legacy APIs

The lowest layer of your application typically deals with the OS APIs. The lowest layer is also the least frequently visited layer. The lowest layer is also the least priority.

Take a break. Think. This layer is supposed to feed your upper layers with data. They are going to be called frequently. They can’t be inefficient? Surely, now you want to dig back in to those headers and see monstrosity you have to deal with?

The worst offender is when it comes to dealing with strings. The OS typically deals with C style null-terminated byte strings while your ultra-modern application surely uses the jazzy std::string and the twain is unlikely ever in near future to meet. In fact such is the dependence that these APIs typically require two calls — once to determine how much memory to allocate and again to actually do the copy. Ever pondered how efficient we are when we translate back and forth?

For the rest of this post assume that we will consider the ubiquitous strcpy from the C standard library as a representative of the OS APIs we are up against. The reason we choose strcpy is twofold — a) this is available on all platforms and I don’t really have to invent a fictitious API to allow me to test across platforms and b) on a more philosophical level this is the basic operation that we are dealing with (and trying to get better at).

But before we rack our brains, what does the experts say? Scott Meyers’ Effective STL saves the day (thankfully there are people like Sutter and Meyers and Alexandrescu and Vandevoorde to get us out of any ditch) once again. It is not for nought he has an entire article (Item #16) devoted to just this topic. So we read and crank up the following piece of code:

std::string TestWithMeyersSolution(const char *s) {
    size_t len = strlen(s);
    std::vector<char> v(len + 1);
    strcpy(&v[ 0 ], s);
    return std::string(v.begin(), v.end());
}

Why does this work? Because the standard says so: Yes, it’s just fine to view a vector as an array when you need to. But first, initialize properly. This is because when we treat vectors as arrays, we get arrays, and arrays neither have members called length or size that get updated on writes nor member functions that give us back their length at our beck and call. The trick is fool the compiler to create a vector large enough to hold the string — and of course, the null terminator.

But wait a second, what was wrong with the buffer based allocation and subsequent copy to std::string that you have in your existing code?

std::string TestWithPlainBuf(const char *s) {
    size_t len = strlen(s);
    char *b = new char[ len + 1 ];
    strcpy(b, s);
    std::string d(b);
    delete [] b;
    return d;
}

Is it really that bad? Like a good programmer, you quickly hack up some tests to measure the performance and hey, what’s this? The raw buffer based solution is faster 1.3 times!  No one ever told you Good Design hurts. Time to go back to blackboard. How do we combine efficiency with design? We think a bit more and realize that one way is to get rid of the vector. It really serves no purpose here. And further, we note that most (if not all) implementations of std::string store the data contiguously. Further, the coming standard (C++0X) will probably makes this into a requirement. So, we can simply use a string instead of a vector. Again, the thing we need to watch out for is keeping the size of the string consistent. The string doesn’t have a ctor exactly like the vector but instead it will politely ask you for a initial value for each of the containers char members. And yes to be faithfully copied out as any other raw character strings we allocate one extra. So, how does the code look now?

std::string TestWithStringResize(const char *s) {
    size_t len = strlen(s);
    std::string d(len + 1, 0);
    strcpy(&d[ 0 ], s);
    d.resize(len);
    return d;
}

Et voilà! (For the observant the resize call is the masterstroke to get rid of the null-terminator. Remember, strings are not the same as C style null-terminated byte strings — they don’t need no nulls.)

So how do the three versions compare against each other? TestWithPlainBuf is about 1.3 times faster than TestWithMeyersSolution and TestWithStringResize is about 1.3 times faster than (or about 2.7 times faster than TestWithMeyersSolution) on my Windows PC. Fcators of improvement were about the same when run on a MacIntel.



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


About

This is an yet another blog on programming in general and C++ in particular. My day job involves reading and writing code. As such, sometimes I end up with interesting snippets and on those rare lucky days, with some valuable insights. Sometimes, some of those end up here. Sometimes I hang around on Stackoverflow with a weird handle.


%d bloggers like this: