Now Throw in an Optimization : Copy-On-Write (COW)

I l @ ve RuBoard

Now Throw in an "Optimization": Copy-On-Write (COW)

COW, a form of lazy copy that uses reference-counted string representations, is probably the most well-known string optimization. Items 14 to 16 introduce and describe this optimization.

COW doesn't apply only to strings, but the motivation is straightforward. Copying or assigning a plain old string usually involves a general-purpose dynamic memory allocation, which is typically an expensive operation (compared to, say, a function call), so copying a string must become an expensive operation. At the same time, calling code often might make copies of string objects, but then never actually modify the copies. For example, calling code can make a copy of a string object, perform some read-only operations such as printing it out or calculating its length, and then destroy the copy. When that happens, it seems wasteful to have done the work to create a distinct copy only to find out later that it wasn't really needed after all.

So what's different about a COW string, such as the Optimized::String described in Items 14 to 16, is that its copy constructor initially performs only a shallow copy and defers the deep copy for as long as possible. Read-only operations on either (source or target) string won't care, after all. Only when a possibly mutating operation is attempted on one of the strings will the string finally be forced to make a deep copy. ^[2]

^[2] COW can also be extended to share substrings, not just entire strings. (See [Niec00].)

Is COW worth it? In a single-threaded program, sometimes. Whether it's really an optimization depends heavily on how string objects are used. See Rob Murray's discussion and empirical measurements in [Murray93] for more information about COW in the real (but single-threaded) world.

The real fun starts when you move to a (possibly) multithreaded environment. As it turns out, using COW can exact an unexpected performance penalty if thread safety is important, and a severe one in some popular (but unnecessarily inefficient) commercial implementations .

I l @ ve RuBoard