A Real-World Example: C s basic_string

I l @ ve RuBoard

A Real-World Example: C++'s basic_string

You may be wondering whether these false optimizations really affect you. The chances are pretty good they do. As a common example, if you use an OO language with a string class, you might well be affected.

Historically, COW has long been a popular optimization in many libraries for all sorts of data structures, including strings. Because of this history, the standard C++ basic_string template was deliberately specified in such a way that vendors would have the option of producing a conforming implementation that used COW. Perhaps unsurprisingly, all early implementations that I'm familiar with did so, even though COW incurs some of its own overhead, [6] is harder to code, and is a frequent source of subtle bugs and interactions. [7]

[6] Such as flags for ownership and reference counts.

[7] Getting the COW code right is more complex than you might think. The most experienced library writers I know have told me repeatedly that they've found their COW code to be a fre-quent source of bugs. These are people with decades of experience crafting quality libraries, not first-timers.

A few years ago, our team brought in a certain vendor's implementation of the standard C++ library and tested it in a single-threaded environment. We then rebuilt the library with the multithreaded switch set, only to discover that many of our programs ran several times more slowly than before. "What could be the problem?" we wondered, scratching our heads. "It looked okay in the test harness. We just made some changes in our own code too; could it be that? Are we blocking on some high-level mutexes more than we thought? Did we introduce an inefficiency somewhere?"

A little investigative work with a profiler isolated the problem, but only deepened the mystery. Our program was spending most of its execution time just acquiring and releasing locks, far more so than could be reasonably expected from the locking performed by our own code. So where was all the locking coming from?

Curious, we investigated further and finally unearthed the problem. A few minutes of digging through the library's source showed that this vendor, like many others, had used the COW optimization in its implementation of basic_string . Naturally, we were using standard C++ strings widely instead of C-style char* 's, and nearly every string operation was causing a lock to be acquired and released.

We took a few minutes to whip up a ten-line sample program that did some reasonable string manipulation in a timed loop. It ran 34 times slower under the multithreaded build of that library than it did under the single-threaded build. We reported the problem, but as far as I know, that library still uses COW today ”and an unnecessarily inefficient implementation of COW at that. The vendor's name doesn't matter, because until recently all the most popular implementations of basic_string on Windows and other platforms used COW. Not all COW-based implementations are this inefficient, but some are.

The good news is that, as I write this in 2001, I can finally report that our industry as a whole seems to be shifting away from COW implementations of basic_string . Increasingly, newer versions of compilers are shipping C++ standard libraries that include only non- copy-on-write string s. This is good news, and it's mainly because we as programmers are increasingly writing multithreaded applications and noticing the problems, and writing articles about those problems, and the vendors have noticed. It is in the vendors' interests to give us fast tools, where "fast" means "fast in the way we are using them," and today that has come to mean "fast in multithreaded environments."

The bad news is that, alas, not all vendors have yet moved to non-COW string s. Your natural next question should therefore be:

I l @ ve RuBoard


More Exceptional C++
More Exceptional C++: 40 New Engineering Puzzles, Programming Problems, and Solutions
ISBN: 020170434X
EAN: 2147483647
Year: 2001
Pages: 118
Authors: Herb Sutter

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net