2
\$\begingroup\$

C++ Standard Library functions like std::tolower, std::isalpha, etc. could be quite slow when it comes to large texts and handling locales.

So, I decided to have fast tolower function, caching the values. They are blazingly fast.

Assumption: nobody will intentionally try to hack the code, trying all possible and impossible ways to call tolower_fast before cache is filled. I assume that tolower_fast will be called much later in common program flow from function main.

Performace measurement

On godbolt.org test it gives:

Duration of std::tolower = 0.17513s
Duration of tolower_fast = 0.000366216s
Duration of tolower_fast2 = 1.38e-06s

On my PC with VS 2022 release:

Duration std::tolower = 1.46942s
Duration tolower_fast = 0.0001968s
Duration tolower_fast2 = 5.35e-05s

(Actually, tolower_fast and tolower_fast2 don't differ so much between each other, this is measurement error).

So, real performance difference is about 1000 times in Release on local PC. Real large texts processing improved from minutes to seconds.

The code

I see many ways to implement caching, for example the following two (demo):

#include <locale>

const std::locale locale(""); // Any reasonable locale

static struct tolower_cache_t {
    char cache[UCHAR_MAX + 1];

    tolower_cache_t() {
        for (size_t c = 0; c <= UCHAR_MAX; ++c)
            cache[c] = std::tolower((char)c, locale);
    }
} tolower_cache;

inline char tolower_fast(char ch) {
    return tolower_cache.cache[ch];
}

class ToLower
{
public:
    ToLower() {
        for (size_t c = 0; c <= UCHAR_MAX; ++c)
            cache[c] = std::tolower((char)c, locale);
    }

    bool operator()(char c) const { return cache[c]; }
private:
    bool cache[UCHAR_MAX + 1];
};

static ToLower tolower_fast2;

int main()
{
    char c = 'A';
    char lc1 = tolower_fast(c);
    char lc2 = tolower_fast2(c);
}

The first one uses object and a function, the second one uses functional object. I guess that from compilation perspective (when it comes to call tolower itself) they should give the similar code. The questions are:

  1. Which of two implementations is better? I mean here potential problems and maintainability.
  2. Are there any issues with the approach and code?
  3. Is there a better way to do this which will still guarantee cache filling before tolower_fast?
\$\endgroup\$
12
  • 1
    \$\begingroup\$ How fast is it really? Did you benchmark your cached versions against simply calling std::tolower() uncached? Without any real numbers to back it up, a statement like "blazingly fast" is meaningless, and potentially even completely false. \$\endgroup\$
    – G. Sliepen
    Jan 26 at 22:14
  • \$\begingroup\$ @G.Sliepen, of course, I measured. The question has been updated. I was sure the difference would be obvious so I decided not to overcomplicate the question, since std::tolower call goes to operation system level (for each character!) to see the locale and translate properly. It is really slow. \$\endgroup\$ Jan 26 at 22:30
  • 2
    \$\begingroup\$ Always enable compiler optimization when doing benchmarks. The numbers change significantly if you add -O2. Also, there is a huge difference between calling std::tolower() with one or two arguments. If you call it without a locale, it will be faster than your cached version (see godbolt.org). \$\endgroup\$
    – G. Sliepen
    Jan 26 at 22:41
  • 1
    \$\begingroup\$ If you know what locale you are going to use you can most of the time just do bit mask operations to implement to_lower. It might end up being faster than using a cache. \$\endgroup\$ Jan 27 at 4:47
  • 1
    \$\begingroup\$ @G.Sliepen, on the "Also, there is a huge difference between calling std::tolower() with one or two arguments. If you call it without a locale, it will be faster than your cached version". I tried on local PC with VS 2024 with std::locale::global(std::locale("Russian")); and std::tolower() with one argument, no changes in performance at all. I tried to reproduce this on godbolt, but clang doesn't accept any Russian-related local I've tried and x64 msvc doesn't produce output on godbolt, so I have no chance to try there. So, still slow on VS 2024 even with 1 argument. \$\endgroup\$ Jan 29 at 12:58

3 Answers 3

4
\$\begingroup\$
  1. Which of two implementations is better? I mean here potential problems and maintainability.

There is a third way. You don't need structs to build the cache, instead you can just use free functions:

static auto make_tolower_cache() {
    std::array<char, UCHAR_MAX + 1> cache;
    for (std::size_t c = 0; c < cache.size(); ++c)
        cache[c] = std::tolower(static_cast<char>(c), locale);
    return cache;
}

static auto tolower_cache = make_tolower_cache();

inline char tolower_fast(char ch) {
    return tolower_cache[ch];
}
  1. Are there any issues with the approach and code?

It only works for simple 8-bit locales. For Unicode, especially if it is encoded using UTF-8, you will need a different approach.

  1. Is there a better way to do this which will still guarantee cache filling before tolower_fast?

You can declare a static array inside a function. When that function is then called for the first time, it will be initialized. Subsequent times it doesn't have to do the full initialization anymore, but there is some overhead because it still needs to check somehow whether it is the first time the function is called:

inline char tolower_fast(char ch) {
    static auto tolower_cache = make_tolower_cache();
    return tolower_cache[ch];
}

So if performance is the most important thing, then that is not the way to go. There are various other ways to address this: call a function early in main() to initialize the cache, never call tolower_fast() before main() starts, ensure the link order is such that a global static cache is initialized early enough, and so on.

Note that if you need even more perfomance, then search for or create a function that lowers multiple characters at a time using SIMD instructions.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for the clue with SIMD instructions. Currently my code processes 3Gb file in 0.177 seconds on my local PC, which is good enough for the moment, but as soon as I see another case to speed up, I will try SIMD. One issue for my and your versions, as I understand that in case we need it in header file to inline the function call, we will have static array duplicated across all cpp files which include this header file. I guess the solution from Toby Speight should help in this case to make this instantiation a bit more manageable. \$\endgroup\$ Jan 31 at 18:03
5
\$\begingroup\$

Don’t Reinvent the Wheel

Your standard library almost certainly already uses a pre-filled lookup table that’s faster than this.

But if You Do

Use a constexpr Array

The lookup table contains only 256 constant values, which are known at compile time. They should be declared as compile-time constants that the compiler can perform constant-folding optimization on. There should not be a cache at all, which you call tolower on every element and fill. Initialize the table with constant expressions.

Make it for a Single Locale

If you really need to change the locale dynamically and have the same function work, use the standard library tolower, or if you don’t, keep a struct of lookup tables for each locale you support, and give your library an initialization function that selects the locale data you currently want to use.

Putting it all Together

The implementation is very simple:

static constexpr unsigned char tolower_table_cp866[256] = {
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F,
    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1A, 0x1B, 0x1C, 0x1D, 0x1E, 0x1F,
    0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2A, 0x2B, 0x2C, 0x2D, 0x2E, 0x2F,
    0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
    0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6A, 0x6B, 0x6C, 0x6D, 0x6E, 0x6F,
    0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7A, 0x5B, 0x5C, 0x5D, 0x5E, 0x5F,
    0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6A, 0x6B, 0x6C, 0x6D, 0x6E, 0x6F,
    0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, 0x7A, 0x5B, 0x5C, 0x7D, 0x7E, 0x7F,
    0xA0, 0xA1, 0xA2, 0xA3, 0xA4, 0xA5, 0xA6, 0xA7, 0xA8, 0xA9, 0xAA, 0xAB, 0xAC, 0xAD, 0xAE, 0xAF,
    0xE0, 0xE1, 0xE2, 0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9, 0xEA, 0xEB, 0xEC, 0xED, 0xEE, 0xEF,
    0xA0, 0xA1, 0xA2, 0xA3, 0xA4, 0xA5, 0xA6, 0xA7, 0xA8, 0xA9, 0xAA, 0xAB, 0xAC, 0xAD, 0xAE, 0xAF,
    0xB0, 0xB1, 0xB2, 0xB3, 0xB4, 0xB5, 0xB6, 0xB7, 0xB8, 0xB9, 0xBA, 0xBB, 0xBC, 0xBD, 0xBE, 0xBF,
    0xC0, 0xC1, 0xC2, 0xC3, 0xC4, 0xC5, 0xC6, 0xC7, 0xC8, 0xC9, 0xCA, 0xCB, 0xCC, 0xCD, 0xCE, 0xCF,
    0xD0, 0xD1, 0xD2, 0xD3, 0xD4, 0xD5, 0xD6, 0xD7, 0xD8, 0xD9, 0xDA, 0xDB, 0xDC, 0xDD, 0xDE, 0xDF,
    0xE0, 0xE1, 0xE2, 0xE3, 0xE4, 0xE5, 0xE6, 0xE7, 0xE8, 0xE9, 0xEA, 0xEB, 0xEC, 0xED, 0xEE, 0xEF,
    0xF1, 0xF1, 0xF3, 0xF3, 0xF5, 0xF5, 0xF7, 0xF7, 0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
};

constexpr unsigned char tolower_cp866(const unsigned char c) noexcept {
    return tolower_table_cp866[c];
}

With this implementation, the very basic test driver:

#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <string_view>

using std::exit, std::uint8_t;
using namespace std::literals::string_view_literals;

constexpr auto upper_sv = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    "\x80\x81\x82\x83\x84\x85\x86\x87\x88\x89\x8A\x8B\x8C\x8D\x8E\x8F"
    "\x90\x91\x92\x93\x94\x95\x96\x97\x98\x99\x9A\x9B\x9C\x9D\x9E\x9F"
    "\xF0\xF2\xF4\xF6"sv;

constexpr auto lower_sv = "abcdefghijklmnopqrstuvwxyz"
    "\xA0\xA1\xA2\xA3\xA4\xA5\xA6\xA7\xA8\xA9\xAA\xAB\xAC\xAD\xAE\xAF"
    "\xE0\xE1\xE2\xE3\xE4\xE5\xE6\xE7\xE8\xE9\xEA\xEB\xEC\xED\xEE\xEF"
    "\xF1\xF3\xF5\xF7"sv;


int main() {
    for (size_t i = 0; i < upper_sv.size(); ++i) {
        if (tolower_cp866((unsigned char)upper_sv[i]) != (unsigned char)lower_sv[i]) {
            std::cerr << i << ": " << (unsigned)(uint8_t)tolower_cp866((unsigned char)upper_sv[i]) << " != " << (unsigned)(uint8_t)lower_sv[i] << '\n';
            exit(EXIT_FAILURE);
        }
    }

    for (size_t i = 0; i < upper_sv.size(); ++i) {
        if (tolower_cp866((unsigned char)lower_sv[i]) != (unsigned char)lower_sv[i]) {
            exit(EXIT_FAILURE);
        }
    }

    std::cout << tolower_cp866('A') << '\n';

    return EXIT_SUCCESS;
}

On this example, the string comparisons can inline the calls to tolower_cp866, and most compliers can completely optimize the call tolower_cp866('A') to the constant 'a'.

Try it on Godbolt.

\$\endgroup\$
13
  • \$\begingroup\$ Thank you for the input. Before I provide my opinion on it, let me double check that you got me correctly. Here are my conditions: (1) there are many functions like that, to_lower, to_upper, isapha (see much more here: cctype and this is not the end of the day); (2) Version which uses locale is slow by measurement; (3) Benchmark-oriented tests like tolower_cp866('A') is not my case since I need to process large texts. (And I could change code page, keeping only one per build). Are you still sure this solution is any better? \$\endgroup\$ Jan 29 at 23:48
  • \$\begingroup\$ @DamirTenishev Yes, I think it is. Let’s go through them. 1: Each function like that takes only a 256-byte table and a single line of code, which is trivial. \$\endgroup\$
    – Davislor
    Jan 30 at 10:07
  • \$\begingroup\$ @DamirTenishev 2: This version ought to be much faster, especially on constant strings. If you need multiple 8-bit locales, you could represent each character set with an enum, and use that as an index into an array of struct holding all the tables and other data your reimplementation needs. This could also be constexpr. \$\endgroup\$
    – Davislor
    Jan 30 at 10:09
  • \$\begingroup\$ @DamirTenishev 3: This function is a drop-in replacement that can be used on a string, including a loop, an algorithm, or a range adaptor. Here, I also demonstrate how to use it to do a case-insensitive string comparison. \$\endgroup\$
    – Davislor
    Jan 30 at 10:11
  • \$\begingroup\$ Basically, making the lookup table and the function constexpr rather than initializing it at runtime enables some more optimizations. \$\endgroup\$
    – Davislor
    Jan 30 at 10:16
2
\$\begingroup\$

The two implementations do different things - ToLower invoking std::isalpha() is very misleading.

Otherwise, the second version is much better, as it doesn't depend on the global variable tolower_cache. That said, there's no good reason that the lookup table can't be a static variable within the function.

The second version still depends on a global variable (locale). I'd pass that as a constructor argument, so that we can easily create translators for different locales:

#include <algorithm>
#include <array>
#include <cctype>
#include <limits>
#include <locale>
#include <ranges>

class ToLower
{
    std::array<char, std::numeric_limits<char>::max() + 1> table = {};

public:
    explicit ToLower(const std::locale& locale = {})
    {
        set_locale(locale);
    }

    void set_locale(const std::locale& locale)
    {
        auto const func = [&locale](char c){return std::tolower(c, locale); };
        std::ranges::copy(std::views::iota(0u, table.size())
                          | std::views::transform(func),
                          table.begin());
    }

    char operator()(char c) const { return table[c]; }
};

We can demonstrate the different locales using Turkish (which doesn't downcase I due to the lack of a single-byte ı).

#include <iostream>
#include <string>
int main()
{
    std::string sample = "CODE REVIEW";
    std::string output = sample;
    std::ranges::transform(sample, output.begin(), ToLower{std::locale::classic()});
    std::cout << output << '\n';
    std::ranges::transform(sample, output.begin(), ToLower{std::locale{"tr_TR.UTF-8"}});
    std::cout << output << '\n';
}

Output:

code review
code revIew

Unfortunately, the table-based approach only really works for single-byte character sets. Populating and using a 16GB table of all wchar_t loses all the gains we made - which is why std::tolower() doesn't work that way.

\$\endgroup\$
5
  • \$\begingroup\$ "the second version is much better, as it doesn't depend on the global variable tolower_cache" No, but the second version does depend on the global variable tolower_fast2, so I don't see how this is any better. It has most of the same issues as the first one, but you are right that if you pass it a locale as a parameter, you can have multiple instances of it, which the first version doesn't support. \$\endgroup\$
    – G. Sliepen
    Jan 30 at 12:40
  • \$\begingroup\$ Well, tolower_fast2 could be made const as it stands, but tolower_cache can't without more work. \$\endgroup\$ Jan 30 at 14:04
  • 1
    \$\begingroup\$ You can just add const right in front of tolower_cache in OP's code. \$\endgroup\$
    – G. Sliepen
    Jan 30 at 14:30
  • \$\begingroup\$ "The two implementations do different things - ToLower invoking std::isalpha() is very misleading". Thank you for catching this, this is typo, since initially this was implemented in two different ways and putting these two fragments together I missed to change the name. Of course, it meant to be std::tolower. Despite the rules, I changed the code since this is, indeed too much confusing. Feel free to update your answer, removing this part and thank you again. Let me address the answer itself in a separate comment. \$\endgroup\$ Jan 30 at 20:25
  • \$\begingroup\$ Special thanks to you for the example with the parametrization and ranges. It really helps. Not sure this version will illuminate the need for a kind of global variable for the table, because in your case table initialization is needed on each instantiation; although it is indeed not too much CPU work, but having it initialized once could be better. On the other hand if all this work is localized in couple of functions which are rarely called and if we have many locales, it is definitely the best approach. Thank you again. \$\endgroup\$ Jan 31 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.