Why COW was deemed ungood for std::string.

COW, short for copy on write, is a way to implement mutable strings so that creating strings and logically copying strings, is reduced to almost nothing; conceptually they become free operations like no-ops.

Basic idea: to share a data buffer among string instances, and only make a copy for a specific instance (the copy on write) when that instance’s data is modified. The general cost of this is only an extra indirection for accessing the value of a string, so a COW implementation is highly desirable. And so the original C++ standard, C++98, and its correction C++03, had special support for COW implementations, and e.g. the g++ compiler’s std::string implementations used COW.

So why was that support dropped in C++11?

In particular, would the same reason or reasons apply to a reference counted immutable string value class?

As we’ll see it does not, it’s just a severe mismatch between the std::string design and the ideal COW requirements. But it took a two hour car trip, driving 120 kms on winter roads, for my memory to yet again cough up the relevant scenario where Things Go Wrong™. I guess it’s like the “why can’t I assign a T** to a T const** question; it’s quite counter-intuitive.

Basic COW string theory: the COPOW principle.

A COW string has two possible states: exclusively owning the buffer, or sharing the buffer with other COW strings.

It starts out in state owning. Assignments and copying initializations can make it sharing. Before executing a “write” operation it must ensure that it’s in owning state, and a transition from sharing to owning involves copying the buffer contents to a new and for now exclusively owned buffer.

With a string type designed for COW any operation will be either non-modifying, a “read” operation, or directly modifying, a “write” operation, which makes it is easy to determine whether the string must ensure state owning before executing the operation.

With a std::string, however, references, pointers and iterators to mutable contents are handed out with abandon. Even a simple value indexing of a non-const string, s[i], hands out a reference that can be used to modify the string. And so for a non-const std::string every such hand-out-free-access operation can effectively be a “write” operation, and would have to be regarded as such for a COW implementation (if the current C++ standard had permitted a COW implementation, which it doesn’t).

I call this the principle of copy on possibility of write, or COPOW for short. It’s for strings that aren’t designed for COW. For a COW-oriented design applying COPOW reduces to pure COW.

A code example showing how COW works.

To keep the size of the following example down I don’t address the issue of constant time initialization from literal, but just show how assignment and copy initialization can be reduced to almost nothing:

#include <cppx-core/_all_.hpp>  // https://github.com/alf-p-steinbach/cppx-core

using C_str = const char*;      // Is also available in cppx.

namespace my
{
    $use_cppx( Raw_array_of_, Size );
    $use_std( begin, end, make_shared, vector, shared_ptr );

    class Cow_string
    {
        using Buffer = vector<char>;

        shared_ptr<Buffer>      m_buffer;
        Size                    m_length;

        void ensure_is_owning()
        {
            if( m_buffer.use_count() > 1 )
            {
                m_buffer = make_shared<Buffer>( *m_buffer );
            }
        }

    public:
        auto c_str() const
            -> C_str
        { return m_buffer->data(); }

        auto length() const
            -> Size
        { return m_length; }

        auto operator[]( const Size i ) const
            -> const char&
        { return (*m_buffer)[i]; }

        auto operator[]( const Size i )
            -> char&
        {
            ensure_is_owning();
            return (*m_buffer)[i];
        }

        template< Size n >
        Cow_string( Raw_array_of_<n, const char>& literal ):
            m_buffer( make_shared<Buffer>( literal, literal + n ) ),
            m_length( n - 1 )
        {}
    };
}  // namespace my

Here assignment is the default-generated assignment operator that just assigns the data members m_buffer and m_length, which are a shared_ptr and an integer, and ditto for copy initialization.

And apparently this code abides by the COPOW principle, so it should be safe…

The problem: UB by adding code that just copies.

Consider the following usage code, it’s perfectly fine:

auto main() -> int
{
    my::Cow_string s = "Du store Alpakka!";
    const C_str p = s.c_str();

    // In this block the contents of `s` are not modified.
    {
        $use_std( ignore );
        const char first_char = s[0];
        ignore = first_char;
    }

    $use_std( cout, endl );
    cout << p << endl;
}

This code is fine because the COW string is already in state owning when s[0] is executed on the non-const s. So all that the initialization of first_char does is to copy a char value. Fine.

But if a maintainer innocently just introduces a logical copy of the string value, which is what COW primarily optimizes, and which certainly doesn’t change the conceptual value, then mayhem ensues:

auto main() -> int
{
    my::Cow_string s = "Du store Alpakka!";
    const C_str p = s.c_str();

    // In this block the contents of `s` are not modified.
    {
        $use_std( ignore );
        my::Cow_string other = s;
        ignore = other;

        const char first_char = s[0];
        ignore = first_char;
    }

    $use_std( cout, endl );
    cout << p << endl;      //! Undefined behavior, p is dangling.
}

Uh oh.

Since s here is in state sharing, the COPOW principle makes the s[0] operation copy the shared buffer, to become owning. Then at the end of the block the only remaining owner of the original buffer, the other string, is destroyed, and destroys the buffer. Which leaves the p pointer dangling.

For a custom string type like Cow_string this is a user error. The type is just badly designed, so that it’s very easy to inadvertently use it incorrectly. But for a std::string it’s formally a bug in the COW implementation, a bug showing that COPOW is just not enough.

For a std::string, if the standard had permitted a COW implementation, to avoid the above calamity it would be necessary to transition to the owned state, incurring an O(n) copying of string data, every place that a reference, pointer or iterator is handed out, regardless of const-ness of the string. One could maybe call that copy on handing out any reference, COHOAR. It greatly reduces the set of cases where COW has an advantage. The C++ standardization committee deemed that cost too high, the remaining advantages of COW too low, to continue supporting COW. So,

  • the C++03 wordings that supported COW were removed;
  • wording was introduced, especially a general O(1) complexity requirement for [] indexing, that disallowed COW; and
  • functionality such as string_view was added, that relies on having pointers to string buffers, and that itself hands out references.

What about threads?

It’a common misconception that COW std::strings would be incompatible with multi-threading, or that making it compatible would make it inefficient, because with COW ordinary copying of a string doesn’t yield an actual copy that another thread can access freely.

In order to allow string instances that are used by different threads, to share a buffer, just about every access function, including simple [] indexing, would need to use a mutex.

However, a simple solution is to just not use ordinary copy initialization or assignment to create a string for another thread, but instead a guaranteed content copying operation such as std::string::substr, or initialization from iterator pair. The C++11 standard could have gone in this other direction. It could, in principle, have added to the existing C++03 support for COW strings, noting that COHOAR, not just COPOW, is required, and added a dedicated deep-copy operation or deep-copy support type plus wording about thread safety.

What about reference counted immutable strings?

An immutable string is a string type such as the built in string types in Java, C# or Python, where the available operations don’t support string data modification. Strings can still be assigned. One just can’t directly change the string data, like changing “H” to ”J“ in “Hello”.

Immutable strings can and in C++ typically will share their string data via reference counting, just as with COW strings. As with COW strings they support amortized constant time initialization from literal, ditto superfast copy assignment and copy initialization, and in addition, if strings don’t need to be zero-terminated they support constant time substring operations. They’re highly desirable.

So, is the problem shown above, a showstopper for immutable strings in C++?

Happily, no. The problem comes about because std::string hands out references, pointers and iterators that can be used to change the string data without involving std::string code, i.e. without its knowledge. That can’t happen with an immutable string.

And figuring out this, whether there was a showstopper, and whether std::string_view (that hands out references) could be used freely in code that would deal with immutable strings, was the reason that I delved into the question of COW std::string again. At one point, long ago, I knew, because I participated in some debates about it, but remembering the problematic use case wasn’t easy. It’s just not intuitive to me, that adding an operation that just copies, can create UB…

Advertisements

Unicode part 1: Windows console i/o approaches



The Windows console subsystem has a host of Unicode-related bugs. And standard Windows programs such as more (not to mention the C# 4.0 compiler csc) just crash when they’re run from a console window with UTF-8 as active codepage, perplexingly claiming that they’re out of memory. On top of that the C++ runtime libraries of various compilers differ in how they behave. Doing C++ Unicode i/o in Windows consoles is therefore problematic. In this series I show how to work around limitations of the Visual C++ _O_U8TEXT file mode, with the Visual C++ and g++ compilers. This yields an automatic translation between external UTF-8 and internal UTF-16, enabling Windows console i/o of characters in the Basic Multilingual Plane.

Introduction

In both Windows and Linux properly internationalized applications use either UTF-16 or UTF-32 for their internal string handling. For example, the popular cross platform ICU library (International Components for Unicode) is based on UTF-16 encoded strings. For this kind of application Windows seems to be the better fit, since Windows’ API is UTF-16 based while Linux’ API is effectively, on a modern installation, UTF-8 based.

Still, in a simple console program one does not typically take on the quite steep overhead of full-fledged Unicode handling.

Instead of using a full-fledged Unicode handling library like ICU, one then relies on just the standard C and C++ libraries, and the Unicode handling reduces to what can easily be expressed using just the direct C++ language and standard library support.

How the Linux “all UTF-8” approach does not work in Windows

In Linux the typical small Unicode console program has everything char-based and UTF-8 encoded. The external data, the internal strings, the string literals, and of course the C or C++ source code, are all UTF-8 encoded. The total unification allows simple programs like this:

[utf8_sans_bom.all_utf8.cpp]
#include <stdexcept>        // std::runtime_error, std::exception
#include <stdlib.h>         // EXIT_SUCCESS, EXIT_FAILURE
#include <iostream>         // std::cout, std::cerr, std::endl
#include <string>           // std::string
using namespace std;

bool throwX( string const& s ) { throw runtime_error( s ); }
bool hopefully( bool v ) { return v; }

string lineFrom( istream& stream )
{
    string result;
    getline( stream, result );
    hopefully( !stream.fail() )
        || throwX( "lineFrom: failed to read line" );
    return result;
}

int main()
{
    try
    {
        static char const       narrowText[]    = "Blåbærsyltetøy! 日本国 кошка!";
        
        cout << "Narrow text: " << narrowText << endl;
        cout << endl;
        cout << "What's your name? ";
        string const name = lineFrom( cin );
        cout << "Glad to meet you, " << name << "!" << endl;
        return EXIT_SUCCESS;
    }
    catch( exception const& x )
    {
        cerr << "!" << x.what() << endl;
    }
    return EXIT_FAILURE;
}

Testing this in Ubuntu 11.10:

[~/blog/examples]
$ g++ utf8_sans_bom.all_utf8.cpp
[~/blog/examples]
$ ./a.out
Narrow text: Blåbærsyltetøy! 日本国 кошка!

What's your name? Bjørn Bråten Sæter
Glad to meet you, Bjørn Bråten Sæter!
[~/blog/examples]
$  _

Yay, it worked OK in Linux!

Testing the very same source code file in Windows using the same Linux-origins compiler (namely g++), and intentionally not specifying any codepage for the console window:

W:\examples> g++ -pedantic -Wall utf8_sans_bom.all_utf8.cpp

W:\examples> a
Narrow text: Blåbærsyltetøy! 日本国 кошка!

What's your name? Bjørn Bråten Sæter
Glad to meet you, Bjorn Bråten Sæter!

W:\examples> _

One reason for the gobbledygook here is that the Windows console by default assumes that the program produces OEM encoded text. That means, it assumes that the text is encoded using the original IBM PC character set, or a variation of that old character set. This encoding assumption is called the console window’s active codepage, and it can be inspected and changed via the chcp command, e.g. from codepage 437 (original IBM PC character set) to 65001 (UTF-8):

W:\examples> chcp
Active code page: 437

W:\examples> chcp 65001
Active code page: 65001

W:\examples> a
Narrow text: Blåbærsyltetøy! 日本国 кошка!huh?

W:\examples> _

Positive: the initial UTF-8 text output appeared to work. The Chinese characters 日本国 displayed as just empty rectangles, but they copied OK. Both the Norwegian and Russian copied OK and also displayed OK.

Negative: input did apparently not work, and it apparently caused some of the program’s output (including the prompt before the input operation) to disappear!

Exactly what went wrong above is difficult to say for sure. It might be the input operation, or it might be something else. However, the exact cause is irrelevant because input fails outright, not just producing weird side effects, if the user types in some non-ASCII characters such as Norwegian æ, ø and å:

W:\examples> a
Narrow text: Blåbærsyltetøy! 日本国 кошка!Bjørn Bråten Sæter
!lineFrom: failed to read line

W:\examples> _

About direct console i/o

Given that total failure for the “all UTF-8” approach has been established, it may perhaps appear to be overkill to also show the unintelligible output effect with the Windows platform’s major compiler, Visual C++ (here version 10.0), but as you’ll see it’s relevant:

W:\examples> cl utf8_sans_bom.all_utf8.cpp /Fe"b"
utf8_sans_bom.all_utf8.cpp

W:\examples> chcp
Active code page: 65001

W:\examples> b
Narrow text: Bl��b��rsyltet��y! ��������� ����������!

What's your name? Bjørn Bråten Sæter
!lineFrom: failed to read line

W:\examples> _

Here the Visual C++ runtime detects that the standard output is connected to a console window. And instead of sending the text via the ordinary standard output stream, it then attempts to place the correct Unicode UCS2-encoded characters directly in the console window’s text buffer. However, since the C++ source code was encoded as UTF-8 without BOM (as is usual in Linux), the Visual C++ compiler erroneously assumed that the source code was encoded as Windows ANSI, and so, since Visual C++ has Windows ANSI sort of hardwired as its C++ narrow character execution character set, it blindly copied the string literal’s bytes to the executable’s string values, whence the runtime, for its direct console i/o, is given UTF-8 bytes instead of the Windows ANSI bytes that it expects – so that its helpful translation to UCS2 fails…

At the Windows API level the runtime implements direct console output by calling the WriteConsole function instead of the WriteFile function. And similarly, if the console input had worked, then it would probably have been via a call to the ReadConsole function instead of the ReadFile function. The WriteConsole function accesses the console window’s text buffer directly and takes an UTF-16 wchar_t based argument, and ditto for ReadConsole.

Portable source code should be UTF-8 with BOM

One can avoid the direct console i/o by redirecting the output.

Such redirection then establishes that the output text byte level data is good, that all would have been well for this particular program’s output, except for the interference from the probably well-intentioned direct console i/o help attempt:

W:\examples> echo Bjørn Bråten Sæter | b >result

W:\examples> type result
Narrow text: Blåbærsyltetøy! 日本国 кошка!

What's your name? Glad to meet you, Bjørn Bråten Sæter !

W:\examples> _

And because the data is correct, one can be sure that the Visual C++ compiler was tricked into assuming that the source code was ANSI Western. And this then means that any wide string literal, which a Windows compiler has to translate to UTF-16, will be incorrectly translated if it contains any non-ASCII characters. Hence, for portable source code it is not a good idea to encode the source code as UTF-8 without BOM – for that is effectively to lie to the compiler.

Now that also g++ accepts a BOM at the start of the source code, portable source code should therefore be encoded as UTF-8 with BOM.

With the BOM in place Visual C++ correctly determines that the source code is UTF-8 encoded, although as of late 2011 this appears to still be undocumented. And with a correct assumption about the source code’s encoding, narrow string literals are correctly translated to Windows ANSI encoded string values in the executable. For Unicode literals in Windows one should therefore use wide string literals, e.g. L"Blåbærsyltetøy! 日本国 кошка!", which in Windows ends up as an UTF-16 encoded string value in the executable.

The Visual C++ UTF-8 stream mode

Use source code encoded as UTF-8 with BOM, and use wide string literals, OK (or rather, one just has to accept that complication!), but how does one then output one of these literals?

E.g., std::wcout in Windows has a rather strong tendency to translate down to Windows ANSI, not to UTF-8?

Well, in his 2008 blog posting Conventional wisdom is retarded, aka What the @#%&* is _O_U16TEXT? Michael Kaplan explained that

“the [Visual C++] CRT? Starting in 2005/8.0, it knows more about Unicode than any of us having been giving it credit for…”

The Visual C++ runtime library can convert automatically between internal UTF-16 and external UTF-8, if you just ask it to do so by calling the _setmode function with the appropriate file descriptor number and mode flag. E.g., mode _O_U8TEXT causes conversion to/from UTF-8.

One reason that many people have not known about the Unicode support that he discusses there, a Visual C++ Unicode stream mode, is that it’s mostly undocumented. Kaplan gives a link to documentation of the deprecated _wsopen function, as one place where the mode flags have been (inadvertently?) documented. However, the main usage is through the _setmode function, where, on the contrary, the official documentation goes on about how _setmode will invoke the “invalid parameter handler” unless the mode argument is either _O_TEXT or _O_BINARY. So, by using this functionality one is not just in ordinary Microsoft undocumented land. One is wholly over in explicitly-documented-as-not-working land.

On the other hand, considering that the official documentation is plain wrong about many things (e.g., for Visual C++ 10 it maintains that the source code encoding is limited to ASCII), and that the _setmode documentation is incorrect about the argument checking, and that the g++ compiler provides C level support for the _O_U8TEXT mode feature, considering all that one may choose to ignore the will-not-work statements of the documentation and just treat it as a documentation defect, for what good is a feature that can’t be used?

Since there is not really any alternative in order to get UTF-8 translation also down at the C library level, this is the approach that I’m going to discuss more detailed in part 2.

It might seem from Kaplan’s blog posting that you don’t have to do more than just set the mode, and go! But as you can expect from something in explicitly-documented-as-not-working land, it’s not fully implemented even in Visual C++. And even less fully implemented in g++…

Summary so far

Above I introduced two approaches to Unicode handling in small Windows console programs:

  • The all UTF-8 approach where everything is encoded as UTF-8, and where there are no BOM encoding markers.
     
  • The wide string approach where all external text (including the C++ source code) is encoded as UTF-8, and all internal text is encoded as UTF-16.

The all UTF-8 approach is the approach used in a typical Linux installation. With this approach a novice can remain unaware that he is writing code that handles Unicode: it Just Works™ – in Linux. However, we saw that it mass-failed in Windows:

  • Input with active codepage 65001 (UTF-8) failed due to various bugs.
     
  • Console output with Visual C++ produced gibberish due to the runtime library’s attempt to help by using direct console output.
     
  • I mentioned how wide string literals with non-ASCII characters are incorrectly translated to UTF-16 by Visual C++ due to the necessary lying to Visual C++ about the source code encoding (which is accomplished by not having a BOM at the start of the source code file).

The wide string approach, on the other hand, was shown to have special support in Visual C++, via the _O_U8TEXT file mode, which I called an UTF-8 stream mode. But I mentioned that as of Visual C++ 10 this special file mode is not fully implemented and/or it has some bugs: it cannot be used directly but needs some scaffolding and fixing. That’s what part 2 is about.


Cheers!

Cheers, & enjoy!

[cppx] B true, or B thrown! (Using the >> throwing pattern)

How often have you declared a variable and invented an ungrokkable three-letter name for that variable, just to temporarily hold the result of some API function so that you can check it immediately after the call? Let me guess, you’ve done that thousands of times. And if so then here are happy tidings: you can completely avoid introducing all those helper variables! 🙂

[… More] Read all of this posting →

[cppx] Is C4099 really a sillywarning? (MSVC sillywarnings)

Evidently some people get to my blog by googling up C4099, the MSVC warning that you’ve used struct in one place and class in another place, for the same class. This is one of the alleged sillywarnings in my sillywarnings suppression header. But given e.g. the discussion at StackOverflow, is it really a sillywarning, or perhaps something to take seriously?

[… More] Read all of this posting →

[cppx] Exception translation, part II

In part I I showed how to use the cppx library’s exception translation support, which decouples the specification of how non-standard exceptions should be translated, from each routine’s invocation of such translation. The translation can be customized by dynamically installing and uninstalling exception translator routines. And essentially each routine that wants exception translation must use a catch (this will most often be a generic catch(...)) where it invokes cppx::rethrowAsStdX, which in turn invokes the installed exception translator routines and performs a default translation if none of them apply.

In this second part I discuss how that translation machinery works.

In part III I’ll discuss the support for installation and uninstallation of exception translator routines. And perhaps I’ll need a part IV to discuss the cppx exception types! Anyway, now, diving down into the code…

[… More] Read all of this posting →

[cppx] Exception translation, part I

MFC throws pointers, Xerces throws various types not derived from std::exception, and as I recall the Lotus Notes API throws integers. An interesting diversity. But as the Chinese curse goes: may you live in interesting times! Such non-standard exceptions generally require you to have multiple catches every place such an exception could otherwise escape to higher levels, or where you want to handle any exception with a given general meaning. It’s not that the designers have tried to be clever or that they’re out to get you: it’s just that these libraries stem from before C++ was standardized, i.e., before 1998.

One partial remedy is exception translation. Somehow arrange for any non-standard exception to be caught and result in some corresponding exception derived from std::exception. It does not solve all the problems – but it sure beats doing it by copy-n’-paste coding of exception handlers!

With C++98 exception translation cannot be completely centralized in a portable, reusable way. As far as I know that’s not possible even with the upcoming C++0x standard. But it’s possible to provide portable and application-independent support that does most of the job, and that provides a general convention that largely eliminates the chance of any non-standard exception slipping through, and that’s what I discuss here. [… More] Read all of this posting →

[cppx] Unique identifier values via std::type_info

Like my posting about cloning this posting about unique identifier values is in preparation for discussing the cppx library’s exception translation support. In short the aspect discussed here is how to let the calling code choose an id for a set of installed translators, so that it can remove them all in one operation (specifying that id). And the simplest id you have in C++ is a type with external linkage. You can obtain a unique-wrt.-comparisions id for a class from the typeid operator. The only problem is that that id, of type std::type_info, is not copyable and not generally comparable, so it can’t be used directly as a key in a std::map, say, and the standard fails to guarantee that you will always obtain the same std::type_info instance for the same type, so it’s a bit risky to use a pointer to that instance…

[… More] Read all of this posting →

[cppx] 3 ways to mix in a generic cloning implementation

To clone an object is to create a dynamically allocated copy of the object, of the same dynamic type, generally without knowing the exact dynamic type. The common way to do that is a virtual method, e.g. called clone, that simply invokes the type’s copy constructor. And the main problem with cloning in C++ is: how to reduce the extreme redundancy of zillions of essentially identical clone methods everywhere?

[… More] Read all of this posting →

[cppx] ZStr, an ownerhip transferring string type

The ZStr ownerhip transferring string class that I introduced in my first Xerces posting may have seemed like total overkill for the job. In C++98 it’s difficult to do correctly, and it requires some less-than-commonly available support machinery. And so if Xerces string handling was the only reason to do it, I wouldn’t have done it.

But once a string class like ZStr is available you (or at least I) find that it’s a natural first choice for many tasks. The beauty of it is that it allows you to defer the decision of trading efficiency for functionality, because the ownership can be transferred to an immutable sharing string type at any point. Or the string can be copied to a copying mutable string type like std::string, whatever.

With a type like ZStr, if you’re implementing library-like functionality, the decision of which “rich” string type does not have to be imposed on the client code. Instead of already trading away the efficiency you’re giving the client code the choice, including the choice of just using ZStr.

[… More] Read all of this posting →

[cppx] Xerces strings simplified by ownership, part II.

In part I of this series I discussed Xerces’ UTF16-based string representation, a common deallocation pitfall for such strings, and how to convert to and from such strings correctly by using C++ RAII techniques. For the RAII techniques I presented one solution using boost::shared_ptr, and one more efficient solution using a home-brewed ownership transfer class, cppx::Ownership. And I promised to next (i.e. in this installment) discuss how to do it even more efficiently by using wchar_t strings as the program’s native strings, and detecting the minimal amount of work needed for each conversion.

[… More] Read all of this posting →