This is the original GotW problem and solution substantially as posted to Usenet. See the book More Exceptional C++ (Addison-Wesley, 2002) for the most current solution to this GotW issue. The solutions in the book have been revised and expanded since their initial appearance in GotW. The book versions also incorporate corrections, new material, and conformance to the final ANSI/ISO C++ standard. |
Reference Counting - Part I
Difficulty: 4 / 10Reference counting is a common optimization (also called "lazy copy" and "copy on write"). Do you know how to implement it? 
ProblemJG Question1. Consider the following simplified String class: namespace Original {
class String {
public:
String(); // start off empty
~String(); // free the buffer
String( const String& ); // take a full copy
void Append( char ); // append one character
private:
char* buf_; // allocated buffer
size_t len_; // length of buffer
size_t used_; // # chars actually used
};
}This is a simple String that does not contain any fancy optimizations. When you copy an Original::String, the new object immediately allocates its own buffer and you immediately have two completely distinct objects. Your assignment: Implement Original::String. Guru Question2. Unfortunately, sometimes copies of string objects are taken, used without modification, and then discarded. "It seems a shame," the implementer of Original::String might frown to herself, "that I always do all the work of allocating a new buffer (which can be expensive) when it may turn out that I never needed to, if all the user does is read from the new string and then destroy it. I could have just let the two string objects share a buffer under the covers, avoiding the copy for a while, and only really take a copy when I know I need to because one of the objects is going to try to modify the string. That way, if the user never modifies the copy, I never need to do the extra work!" With a smile on her face and determination in her eyes, the implementer designs an Optimized::String that uses a reference-counted implementation (also called "lazy copy" or "copy on write"): namespace Optimized {
struct StringBuf {
StringBuf(); // start off empty
~StringBuf(); // delete the buffer
void Reserve( size_t n );// ensure len >= n
char* buf; // allocated buffer
size_t len; // length of buffer
size_t used; // # chars actually used
unsigned refs; // reference count
};
class String {
public:
String(); // start off empty
~String(); // decrement reference count
// (delete buffer if refs==0)
String( const String& ); // point at same buffer and
// increment reference count
void Append( char ); // append one character
private:
StringBuf* data_;
};
}Your assignment: Implement Optimized::StringBuf and Optimized::String. You may want to add a private String::AboutToModify() helper function to simplify the logic. Author's Notes1. I don't show operator= because it's essentially the same as copy construction. 2. This issue of GotW incidentally illustrates another use for namespaces, namely clearer exposition. Writing the above was much nicer than writing about differently-named "OriginalString" and "OptimizedString" classes (which would have made reading and writing the example code a little harder). Also, the namespace syntax is very natural here in the expository paragraphs. Using namespaces judiciously can likewise improve readability in your production code and "talkability" during design meetings and code reviews.
SolutionThis is a simple String that does not contain any fancy optimizations. When you copy an Original::String, the new object immediately allocates its own buffer and you immediately have two completely distinct objects. Your assignment: Implement Original::String. Here is a straightforward implementation. namespace Original {
String::String() : buf_(0), len_(0), used_(0) { }
String::~String() { delete[] buf_; }
String::String( const String& other )
: buf_(new char[other.len_]),
len_(other.len_),
used_(other.used_)
{
copy( other.buf_, other.buf_ + used_, buf_ );
}I've chosen to implement an additional Reserve helper function for code clarity, since it will be needed by other mutators besides Append. Reserve ensures that our internal buffer is at least n bytes long, and allocates additional space using an exponential-growth strategy: void String::Reserve( size_t n ) {
if( len_ < n ) {
size_t newlen = max( len_ * 1.5, n );
char* newbuf = new char[ newlen ];
copy( buf_, buf_+used_, newbuf );
delete[] buf_; // now all the real work is
buf_ = newbuf; // done, so take ownership
len_ = newlen;
}
}
void String::Append( char c ) {
Reserve( used_+1 );
buf_[used_++] = c;
}
}Aside: What's the Best Buffer Growth Strategy?When a String object runs out of room in its currently- allocated buffer, it needs to allocate a larger one. The key question is: "How big should the new buffer be?" [Note: The analysis that follows holds for other structures and containers that use allocated buffers, such as a standard vector<>.] There are several popular strategies. I'll note each strategy's complexity in terms of the number of allocations required, and the average number of times a given character must be copied, for a string of eventual length N. a) Exact growth. In this strategy, the new buffer is made exactly as large as required by the current operation. For example, appending one character and then appending another will force two allocations; first a new buffer is allocated with space for the existing string and the first new character; next, another new buffer is allocated with space for that and the second new character. - Advantage: No wasted space. - Disadvantage: Poor performance. This strategy requires O(N) allocations and an average of O(N) copy operations per char, but with a high constant factor in the worst case (same as (b) with an increment size of 1). Control of the constant factor is in the hands of the user code, not controlled by the String implementer.
b) Fixed-increment growth. The new buffer should be a fixed amount larger than the current buffer. For example, a 64-byte increment size would mean that all string buffers would be an integer multiple of 64 bytes long. - Advantage: Little wasted space. The amount of unused space in the buffer is bounded by the increment size, and does not vary with the length of the string. - Disadvantage: Moderate performance. This strategy requires both O(N) allocations and an average of O(N) copy operations per char. That is, both the number of allocations and the average number of times a given char is copied vary linearly with the length of the string. However, control of the constant factor is in the hands of the String implementer.
c) Exponential growth. The new buffer is a factor of F larger than the current buffer. For example, with F=.5, appending one character to full string which is already 100 bytes long will allocate a new buffer of length 150 bytes. - Advantage: Good performance. This strategy requires O(logN) allocations and an average of O(k) copy operations per char. That is, the number of allocations varies linearly with the length of the string, but the average number of times a given char is copied is constant(!) which means that the amount of copying work to create a string using this strategy is at most a constant factor greater than the amount of work that would have been required had the size of the string been known in advance. - Disadvantage: Some wasted space. The amount of unused space in the buffer will always be strictly less than N*F bytes, but that's still O(N) average space wastage.
The following chart summarizes the tradeoffs: Growth Strategy Allocations Char Copies Wasted Space
--------------- ----------- ----------- ------------
Exact O(N) with O(N) with none
high const. high const.
Fixed-increment O(N) O(N) O(k)
Exponential O(logN) O(k) O(N)In general, the best-performing strategy is exponential growth. Consider a string that starts empty and grows to 1200 characters long. Fixed-increment growth requires O(N) allocations and on average requires copying each character O(N) times (in this case, using 32-byte increments, that's 38 allocations and on average 19 copies of each character). Exponential growth requires O(logN) allocations and on average requires making only O(k) -- one or two -- copies of each character (yes, really; see the reference below); in this case, using a factor of 1.5, that's 10 allocations and on average 2 copies of each character. 1,200-char string 12,000-char string
====================== =======================
Fixed-incr Exponential Fixed-incr Exponential
growth growth growth growth
(32 bytes) (1.5x) (32 bytes) (1.5x)
---------- ----------- ---------- -----------
# of memory 38 10 380 16
allocations
avg # of 19 2 190 2
copies made
of each charThis result can be surprising. For more information, see Andrew Koenig's column in the September 1998 issue of JOOP (Journal of Object-Oriented Programming). Koenig also shows why, again in general, the best growth factor is not 2 but probably about 1.5. He also shows why the average number of times a given char is copied is constant -- i.e., doesn't depend on the length of the string. Your assignment: Implement Optimized::StringBuf and Optimized::String. You may want to add a private String::AboutToModify() helper function to simplify the logic. First, consider StringBuf. Note that the default memberwise copying and assignment don't make sense for StringBufs, so both operations should also be suppressed (declared as private and not defined). namespace Optimized {
StringBuf::StringBuf() : buf(0), len(0), used(0), refs(1) { }
StringBuf::~StringBuf() { delete[] buf; }
void StringBuf::Reserve( size_t n ) {
if( len < n ) {
size_t newlen = max( len * 1.5, n );
char* newbuf = new char[ newlen ];
copy( buf, buf+used, newbuf );
delete[] buf; // now all the real work is
buf = newbuf; // done, so take ownership
len = newlen;
}
}Next, consider String itself. The default constructor and the destructor are easy to implement. String::String() : data_(new StringBuf) { }
String::~String() {
if( --data_->refs < 1 ) {
delete data_;
}
}Next, we write the copy constructor to implement the "lazy copy" semantics by simply updating a reference count. We will only actually split off the shared representation if we discover that we need to modify one of the strings that share this buffer. String::String( const String& other )
: data_(other.data_)
{
++data_->refs;
}I've chosen to implement an additional AboutToModify helper function for code clarity, since it will be needed by other mutators besides Append. AboutToModify ensures that we have an unshared copy of the internal buffer; that is, it performs the "lazy copy" if it has not already been performed. For convenience, AboutToModify takes a minimum buffer size, so that we won't needlessly take our own copy of a full string only to turn around and immediately perform a second allocation to get more space. void String::AboutToModify( size_t n ) {
if( data_->refs > 1 ) {
auto_ptr<StringBuf> newdata( new StringBuf );
newdata.get()->Reserve( max( data_->len, n ) );
copy( data_->buf, data_->buf+data_->used, newdata.get()->buf );
newdata.get()->used = data_->used;
--data_->refs; // now all the real work is
data_ = newdata.release(); // done, so take ownership
}
else {
data_->Reserve( n );
}
}
void String::Append( char c ) {
AboutToModify( data_->used+1 );
data_->buf[data_->used++] = c;
}
} | 
