{"id":5908,"date":"2024-05-28T07:00:24","date_gmt":"2024-05-28T14:00:24","guid":{"rendered":"http:\/\/writeasync.net\/?p=5908"},"modified":"2024-05-27T21:59:49","modified_gmt":"2024-05-28T04:59:49","slug":"5908","status":"publish","type":"post","link":"https:\/\/writeasync.net\/?p=5908","title":{"rendered":"How fast from `wstring` to `string`?"},"content":{"rendered":"

Anyone who has dealt with both “narrow” and “wide” strings<\/a> in the same C++ module is inevitably faced with this little annoyance:<\/p>\n

\r\nstd::wstring get_wide_text()\r\n{\r\n    \/\/ . . .\r\n}\r\n\r\nvoid write_narrow_text(std::ostream& os)\r\n{\r\n    \/\/ ERROR! can't write wide string to narrow stream!\r\n    os << get_wide_text();\r\n}\r\n<\/pre>\n
In MSVC, you might see an error like C2676<\/a> (\"binary '<<': 'std::basic_ostream<char,std::char_traits<char>>' does not define this operator or a conversion to a type acceptable to the predefined operator\"<\/code>). But if you think about it, it’s totally sensible for the C++ standard library to not<\/em> define any default operators that work across different string types.<\/p>\n
For one thing, it is not possible to know for certain the encoding<\/a> of a std::string<\/code> or std::wstring<\/code> by just looking its character type. Plenty of code out there<\/a> gets away with assuming std::string<\/code> means UTF-8<\/a> and std::wstring<\/code> means UTF-16<\/a>. That is, however, just convention and not<\/strong> contractual. So, if we want our program to interoperate with these string types, we have pay for what we use. We must convert!<\/p>\n
You might try to reach for an STL solution to this surely near-universal problem. Sadly, the code that did exist to handle this scenario, the codecvt<\/code> header, is now deprecated<\/a>. That being said, it is not too hard to cook up a Win32 replacement for the very simple use case we are dealing with above, i.e., conversion from UTF-16 to UTF-8. The Windows API for this is WideCharToMultiByte<\/a>.<\/p>\n
Now, we can fairly easily write a nice C++ wrapper over this C-style API (see commit on GitHub<\/a>):<\/p>\n
\r\nstd::string to_utf8(const std::wstring& utf16_input)\r\n{\r\n    const auto input_size = gsl::narrow<int>(utf16_input.size());\r\n    const auto required_size = WideCharToMultiByte(CP_UTF8, 0, utf16_input.c_str(), input_size, nullptr, 0, nullptr, nullptr);\r\n    THROW_LAST_ERROR_IF_MSG(required_size == 0, "Failed to get required size");\r\n    auto utf8_result = std::string(required_size, '\0');\r\n    const auto actual_size = WideCharToMultiByte(CP_UTF8, 0, utf16_input.c_str(), input_size, utf8_result.data(), required_size, nullptr, nullptr);\r\n    THROW_LAST_ERROR_IF_MSG(actual_size == 0, "Failed to convert to UTF-8");\r\n    return utf8_result;\r\n}\r\n<\/pre>\n
Note that we’re using a few helper libraries here: GSL<\/a> (for a bit of safety) and WIL<\/a> (for a bit of convenience). Also note the “call twice” pattern here to first discover how long the converted string will be so that we can prepare a buffer of the right size on the final call. (This pattern is used by so many Win32 APIs, that WIL has helpers for one common resize-and-retry strategy<\/a>.)<\/p>\n
If you want simplicity, it’s hard to beat this implementation. Ah, but wait, it’s a bit too<\/em> simple. Because 0 is used an error signal in this Win32 API, we cannot tell the difference between a true zero-length string and zero-because-we-failed. This should fix it (see commit on GitHub<\/a>):<\/p>\n
\r\n    const auto input_size = gsl::narrow<int>(utf16_input.size());\r\n    if (input_size == 0)\r\n    {\r\n        return {};\r\n    }\r\n<\/pre>\n
Wait, we still need to account for totally invalid inputs (see commit on GitHub<\/a>):<\/p>\n
\r\n    const auto required_size = WideCharToMultiByte(CP_UTF8, WC_ERR_INVALID_CHARS, utf16_input.c_str(), input_size, nullptr, 0, nullptr, nullptr);\r\n\/\/ . . .\r\n    const auto actual_size = WideCharToMultiByte(CP_UTF8, WC_ERR_INVALID_CHARS, utf16_input.c_str(), input_size, utf8_result.data(), required_size, nullptr, nullptr);\r\n<\/pre>\n
Okay, so now<\/em> it’s simple and it definitely solves the problem we had above:<\/p>\n
\r\nvoid write_narrow_text(std::ostream& os)\r\n{\r\n    \/\/ Error is gone, and everything works... \r\n    \/\/ ...as long as we're prepared to deal with UTF-8 output\r\n    os << to_utf8(get_wide_text());\r\n}\r\n<\/pre>\n
But there is something not quite satisfying about this solution. In particular, what if our access pattern looked more like this?<\/p>\n
\r\nvoid write_narrow_text(std::ostream& os)\r\n{\r\n    const auto s = to_utf8(get_wide_text());\r\n    for (auto c : s)\r\n    {\r\n        \/\/ put commas before each space char\r\n        if (c == ' ')\r\n        {\r\n            os << ',';\r\n        }\r\n\r\n        os << c;\r\n    }\r\n}\r\n<\/pre>\n
The function above would produce an output like \"a, b, c\"<\/code> when given a (wide string) input of L\"a b c\"<\/code>. We have to walk through each input char individually, but we also<\/em> had to do that when converting the input. In fact, we had to do it twice<\/strong> during conversion as discussed before. Luckily, there is no rule that says we have to produce a full-fledged std::string<\/code> from the conversion process — the WideCharToMultiByte<\/code>, being a typical C-callable Win32 API<\/a>, works purely on raw buffers. Wouldn’t it make sense then to convert as we go, block by block? Let’s find out!<\/p>\n
First, we have to figure out a strategy for doing this block conversion. Using a size_t<\/code> template parameter<\/a> to define the output block size gives us some niceties around constexpr<\/code>-ness. But what should the input block size be? Astute readers of the Unicode standard<\/a> will note that UTF-16 can represent all characters in at most two code units<\/a>. In other words, we might have one or two wchar_t<\/code> elements for each “character” (or really, code point<\/a>). Further, UTF-8 may need up to four code units (which we store as char<\/code>) for the same code point. The absolute worst case then if we knew nothing more than this is the expansion of one wchar_t<\/code> of input to four char<\/code>s of output. (It turns out only surrogate pairs<\/a> should end up producing the longest sequences in UTF-8, but this 1:4 ratio is a safe upper bound for our purposes.)<\/p>\n
Next, we are keeping our char-by-char goal in mind, which means we should build a range<\/a> type. Internally, the range should use some sort of input iterator<\/a> to do the heavy lifting. How do we know when we’ve reached the end? We could use a sentinel<\/a>.<\/p>\n
Putting all this together, we end up with something like this for our “public” API:<\/p>\n
\r\ntemplate <size_t N>\r\n    requires (N > 3)\r\ndetail::Utf8Range<N> to_utf8(const std::wstring& utf16_input)\r\n{\r\n    return { std::wstring_view{utf16_input} };\r\n}\r\n<\/pre>\n
The user needs to decide on a block size N and pass an input string, and we give back the range as promised:<\/p>\n
\r\ntemplate <size_t N>\r\n    requires (N > 3)\r\nclass Utf8Range\r\n{\r\npublic:\r\n    using Input = std::wstring_view;\r\n    using Output = gsl::span<char>;\r\n    class Iterator;\r\n    struct Sentinel {};\r\n\r\n    Utf8Range(Input input) noexcept : m_input{ input }, m_block{}\r\n    {}\r\n\r\n    Iterator begin()\r\n    {\r\n        return { m_input, Output{m_block} };\r\n    }\r\n\r\n    Sentinel end()\r\n    {\r\n        return {};\r\n    }\r\n\r\n    \/\/ . . .\r\n\r\nprivate:\r\n    Input m_input;\r\n    std::array<char, N> m_block;\r\n};\r\n<\/pre>\n
This should be enough to support a range-based for loop<\/a> to do a single pass over the converted output string. Now what should the iterator look like? It has a few complexities like needing to support conversion of the next block when we exhaust the current one and the expectation of passing back the first char right away (unlike C# enumerators which are positioned before<\/em> the first element<\/a>), just to name a few. As a first cut, this might work (see commit on GitHub<\/a>):<\/p>\n
\r\n    class Iterator\r\n    {\r\n    public:\r\n        using difference_type = std::ptrdiff_t;\r\n        using value_type = char;\r\n\r\n        Iterator() noexcept : m_source{}, m_next_offset{}, m_block{}, m_index{}\r\n        {}\r\n\r\n        Iterator(Input source, Output block)\r\n            : m_source{ source }, m_next_offset{}, m_block{ block }, m_index{ m_block.size() - 1 }\r\n        {\r\n            move_next();\r\n        }\r\n\r\n        char operator*() const\r\n        {\r\n            return m_block[m_index];\r\n        }\r\n\r\n        Iterator& operator++()\r\n        {\r\n            if (!at_end())\r\n            {\r\n                move_next_char();\r\n            }\r\n\r\n            return *this;\r\n        }\r\n\r\n        Iterator operator++(int)\r\n        {\r\n            Iterator prev = *this;\r\n            ++*this;\r\n            return prev;\r\n        }\r\n\r\n        bool operator==(Sentinel) const noexcept\r\n        {\r\n            return at_end();\r\n        }\r\n\r\n    private:\r\n        bool at_block_end() const noexcept\r\n        {\r\n            return m_index == m_block.size() - 1;\r\n        }\r\n\r\n        bool at_end() const noexcept\r\n        {\r\n            return (m_next_offset >= m_source.size()) && at_block_end();\r\n        }\r\n\r\n        void move_next_char()\r\n        {\r\n            if (!at_block_end())\r\n            {\r\n                ++m_index;\r\n            }\r\n            else\r\n            {\r\n                move_next();\r\n            }\r\n        }\r\n\r\n        void move_next()\r\n        {\r\n            if (at_end())\r\n            {\r\n                return;\r\n            }\r\n\r\n            const auto hr = try_move_next();\r\n            THROW_IF_FAILED_MSG(hr, "Error near offset %llu while attempting UTF-8 conversion", m_next_offset);\r\n\r\n            m_index = 0;\r\n        }\r\n\r\n        HRESULT try_move_next()\r\n        {\r\n            const auto input_block = next_block();\r\n            const auto input_size = gsl::narrow<int>(input_block.size());\r\n            static constexpr const auto output_size = gsl::narrow<int>(N);\r\n            const auto actual_size = WideCharToMultiByte(CP_UTF8, WC_ERR_INVALID_CHARS, input_block.data(), input_size, m_block.data(), output_size, nullptr, nullptr);\r\n            if (actual_size == 0)\r\n            {\r\n                return HRESULT_FROM_WIN32(GetLastError());\r\n            }\r\n\r\n            m_block = m_block.subspan(0, actual_size);\r\n            m_next_offset += actual_size;\r\n            return S_OK;\r\n        }\r\n\r\n        auto next_block() const\r\n        {\r\n            static constexpr const auto M = (N \/ 4);\r\n            const auto max_input_size = m_source.size() - m_next_offset;\r\n            const auto input_size = (M <= max_input_size) ? M : max_input_size;\r\n            return m_source.substr(m_next_offset, input_size);\r\n        }\r\n\r\n        Input m_source;\r\n        size_t m_next_offset;\r\n        Output m_block;\r\n        size_t m_index;\r\n    };\r\n<\/pre>\n
This works for the scenarios we described above, correctly sliding the block forward to the next as we reach the end of each previous one. And then someone asks, “What about emoji?” Ah, yes — emoji characters<\/a> use the surrogate pair encoding we talked about before. Each one will use two wchar_t<\/code>s, and it would be an error to try to split one “down the middle,” so to speak. We can see this error in action by using this test:<\/p>\n
\r\nTEST(to_utf8_test, emoji_block)\r\n{\r\n    const auto raw = std::array<uint16_t, 5>{0xD83D, 0xDE0E, 0xD83D, 0xDC4D, 0x0000};\r\n    const auto input = std::wstring{ reinterpret_cast<const wchar_t*>(raw.data()) };\r\n    const auto expected = std::string{ "\\xF0\\x9F\\x98\\x8E\\xF0\\x9F\\x91\\x8D" };\r\n\r\n    test_utf8_block<4>(input, expected);\r\n    test_utf8_block<9>(input, expected);\r\n    test_utf8_block<14>(input, expected);\r\n    test_utf8_block<19>(input, expected);\r\n}\r\n<\/pre>\n
The first test function (test_utf8_block<4><\/code>) fails because the four char<\/code> output block is mapped to a one wchar_t<\/code> input block, and it is not valid to have an unpaired surrogate<\/a>. The fix is to detect this error and then widen the input block by one wchar_t<\/code> as a retry step. Worst case, we’ll fail again and report the same error. With luck, though, we’ll continue happily converting the rest of the string (see commit on GitHub<\/a>):<\/p>\n
\r\n            if (FAILED(try_move_next<false>()))\r\n            {\r\n                const auto hr = try_move_next<true>();\r\n                THROW_IF_FAILED_MSG(hr, "Error near offset %llu while attempting UTF-8 conversion", m_next_offset);\r\n            }\r\n\r\n\/\/ . . .\r\n        template <bool OneMore>\r\n        HRESULT try_move_next()\r\n        {\r\n            const auto input_block = next_block<OneMore>();\r\n            \/\/ . . .\r\n        }\r\n\r\n        template <bool OneMore>\r\n        auto next_block() const\r\n        {\r\n            static constexpr const auto M = (N \/ 4) + (OneMore ? 1 : 0);\r\n            \/\/ . . .\r\n        }\r\n<\/pre>\n
Whew! That’s a fair amount of work, but it seems to do the job. Now to finally answer the question asked in the title of this article — how fast is this? Let’s run some benchmarks<\/a> (see full commit on GitHub<\/a>):<\/p>\n
\r\nstatic void to_utf8_very_long_string(benchmark::State& state)\r\n{\r\n    const auto input = make_very_long_string();\r\n    auto ss = std::stringstream{};\r\n\r\n    for (auto _ : state)\r\n    {\r\n        ss.clear();\r\n        const auto result = str::to_utf8(input);\r\n        ss << result;\r\n    }\r\n}\r\n\r\n\/\/ . . .\r\n\r\nstatic void to_utf8_very_long_string_by_char(benchmark::State& state)\r\n{\r\n    const auto input = make_very_long_string();\r\n    auto ss = std::stringstream{};\r\n\r\n    for (auto _ : state)\r\n    {\r\n        ss.clear();\r\n        for (auto c : str::to_utf8(input))\r\n        {\r\n            ss << c;\r\n        }\r\n    }\r\n}\r\n\r\n\/\/ ...\r\n\r\ntemplate <size_t N>\r\nstatic void to_utf8_block_very_long_string(benchmark::State& state)\r\n{\r\n    const auto input = make_very_long_string();\r\n    auto ss = std::stringstream{};\r\n\r\n    for (auto _ : state)\r\n    {\r\n        ss.clear();\r\n        for (auto c : str::to_utf8<N>(input))\r\n        {\r\n            ss << c;\r\n        }\r\n    }\r\n}\r\n<\/pre>\n
These are the basic benchmarks we will consider. We have the full round-trip through a std::string<\/code> version tested in to_utf8_very_long_string<\/code> and to_utf8_very_long_string_by_char<\/code> as well as a template function to_utf8_block_very_long_string<\/code> for testing a set of block-based variations. The results on my machine look like this:<\/p>\n
\r\n-------------------------------------------------------------------------------\r\nBenchmark                                     Time             CPU   Iterations\r\n-------------------------------------------------------------------------------\r\nto_utf8_very_long_string                  56961 ns        52550 ns        13380\r\nto_utf8_very_long_string_by_char        2036363 ns      1801273 ns          373\r\nto_utf8_64_block_very_long_string        728050 ns       697545 ns         1120\r\nto_utf8_256_block_very_long_string       694001 ns       655692 ns         1120\r\nto_utf8_1024_block_very_long_string      714926 ns       655692 ns         1120\r\nto_utf8_4096_block_very_long_string      718333 ns       655692 ns         1120\r\nto_utf8_16384_block_very_long_string     997483 ns      1024933 ns          747\r\n<\/pre>\n
This tells us that if char-by-char is the need, the block-based algorithm can beat the simpler one (when using roughly ~1K block sizes). But if you just need to output the whole string as-is, it is still orders of magnitude faster to do the full round-trip conversion (maybe there is some vectorization<\/a> going on?). In any case, we have shown yet again the triumph of measurement over assumption!<\/p>\n","protected":false},"excerpt":{"rendered":"
Anyone who has dealt with both “narrow” and “wide” strings in the same C++ module is inevitably faced with this little annoyance: std::wstring get_wide_text() { \/\/ . . . } void write_narrow_text(std::ostream& os) { \/\/ ERROR! can’t write wide string… <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[101,104],"tags":[],"class_list":["post-5908","post","type-post","status-publish","format-standard","hentry","category-native","category-performance"],"_links":{"self":[{"href":"https:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5908","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5908"}],"version-history":[{"count":6,"href":"https:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5908\/revisions"}],"predecessor-version":[{"id":5914,"href":"https:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5908\/revisions\/5914"}],"wp:attachment":[{"href":"https:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5908"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5908"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5908"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}