С++ таблица поиска isalpha

Помните первое правило оптимизации: не делайте этого.

Тогда запомните второе правило оптимизации, которое нужно применять очень редко: пока не делайте этого.

Затем, если вы действительно столкнулись с узким местом и определили isalpha как причину, что-то вроде этого может быть быстрее, в зависимости от того, как ваша библиотека реализует функцию. Вам нужно будет измерить производительность в вашей среде и использовать ее только в том случае, если действительно есть измеримое улучшение. Это предполагает, что вам не нужно тестировать значения за пределами диапазона unsigned char (обычно 0...255); вам понадобится немного дополнительной работы для этого.

#include <cctype>
#include <climits>

class IsAlpha
{
public:
    IsAlpha()
    {
        for (int i = 0; i <= UCHAR_MAX; ++i)
            table[i] = std::isalpha(i);
    }

    bool operator()(unsigned char i) const {return table[i];}

private:
    bool table[UCHAR_MAX+1];
};

Использование:

IsAlpha isalpha;

for (int i = 0; i <= UCHAR_MAX; ++i)
    assert(isalpha(i) == bool(std::isalpha(i)));

Я всегда использовал этот единственный метод сравнения (я предполагаю, что он работает лучше), так как это быстрее, чем выполнение до четырех сравнений.

unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A' 

Я протестировал несколько различных способов и учел промахи кеша TLB для метода таблицы поиска. Я провел тесты на окнах. Вот время, если кодировка была «0»... «z»:

lookup tbl no tlb miss:                        4.8265 ms
lookup table with tlb miss:                    7.0217 ms
unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A':  10.5075 ms
(ch>='A' && ch<='Z') || (ch>='a' && ch<='z'): 17.2290 ms
isalpha:                                      28.0504 ms

Вы можете ясно видеть, что код локали имеет свою стоимость.

Вот время, если кодировка была 0..255:

tbl no tlb miss:                               12.6833 ms
unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A':   29.2403 ms
(ch>='A' && ch<='Z') || (ch>='a' && ch<='z'):  34.8818 ms
isalpha:                                       78.0317 ms
tbl with tlb miss:                            143.7135 ms

Время больше, потому что было протестировано больше символов. Количество сегментов, которые я использовал для «сброса» tlb, было больше во втором тесте. Возможно, метод поиска в таблице больше страдает от промаха tlb, чем показывает первый запуск. Вы также можете видеть, что одиночный метод cmp работает лучше, когда символ является альфа-каналом.

Метод таблицы поиска лучше всего подходит для сравнения множества символов подряд, но он не намного лучше, чем метод с одним cmp. Если вы сравниваете символы здесь и там, то отсутствие кэша tlb может сделать метод tbl хуже, чем метод одиночного cmp. Одиночный метод cmp работает лучше всего, когда символы, скорее всего, будут альфа-каналами.

Вот код:

__forceinline bool isalpha2(BYTE ch) {
    return (ch>='A' && ch<='Z') || (ch>='a' && ch<='z');
}

__forceinline bool isalpha1(BYTE ch) {
    return unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A';
}
bool* aTbl[256];

int main(int argc, char* argv[]) 
{
    __int64 n = 0, cTries = 100000;
    int b=63;
    int ch0=' ', ch1 ='z'+1;
    ch0=0, ch1 = 256;
    // having 255 tables instead of one lets us "flush" the tlb.
    // Intel tlb should have about ~32 entries (depending on model!) in it, 
    // so using more than 32 tables should have a noticable effect.
    for (int i1=0 ; i1<256 ; ++i1) {
        aTbl[i1] = (bool*)malloc(16384);
        for (int i=0 ; i<256 ; ++i)
            aTbl[i1][i] = isalpha(i);
    }

    { CBench Bench("tbl with tlb miss");
        for (int i=1 ; i<cTries ; ++i) {
            for (int ch = ch0 ; ch < ch1 ; ++ ch) 
                n += aTbl[ch][ch];  // tlb buster
        }
    }
    { CBench Bench("tbl no tlb miss");
        for (int i=1 ; i<cTries ; ++i) {
            for (int ch = ch0 ; ch < ch1 ; ++ ch) 
                n += aTbl[0][ch];
        }
    }
    { CBench Bench("isalpha");
        for (int i=1 ; i<cTries ; ++i) {
            for (int ch = ch0 ; ch < ch1 ; ++ ch)
                n += isalpha(ch);
        }
    }
    { CBench Bench("unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A'");
        for (int i=1 ; i<cTries ; ++i) {
            for (int ch = ch0 ; ch < ch1 ; ++ ch)
                n += isalpha1(ch);
        }
    }
    { CBench Bench("(ch>='A' && ch<='Z') || (ch>='a' && ch<='z')");
        for (int i=1 ; i<cTries ; ++i) {
            for (int ch = ch0 ; ch < ch1 ; ++ ch) 
                n += isalpha2(ch);
        }
    }
    return n;
}


class  CBench {
public:
    __declspec(noinline) CBench(CBench* p) : m_fAccumulate(false), m_nTicks(0),
     m_cCalls(0), m_pBench(p), m_desc(NULL), m_nStart(GetBenchMark()) { }
    __declspec(noinline) CBench(const char *desc_in, bool fAccumulate=false) : 
     m_fAccumulate(fAccumulate), m_nTicks(0), m_cCalls(0), m_pBench(NULL), 
     m_desc(desc_in), m_nStart(GetBenchMark()) {    }
    __declspec(noinline) ~CBench() {
        __int64 n = (m_fAccumulate) ? m_nTicks : GetBenchMark() - m_nStart;
        if (m_pBench) {
            m_pBench->m_nTicks += n;
            m_pBench->m_cCalls++;
            return;
        } else if (!m_fAccumulate) {
            m_cCalls++;
        }
        __int64 nFreq;
        QueryPerformanceFrequency((LARGE_INTEGER*)&nFreq);
        double ms = ((double)n * 1000)/nFreq;
        printf("%s took: %.4f ms, calls: %d, avg:%f\n", m_desc, ms, m_cCalls,
             ms/m_cCalls);
    }
    __declspec(noinline) __int64 GetBenchMark(void) {
        __int64 nBenchMark;
        QueryPerformanceCounter((LARGE_INTEGER*)&nBenchMark);
        return nBenchMark;
    }
    LPCSTR     m_desc;
    __int64    m_nStart, m_nTicks;
    DWORD      m_cCalls;
    bool       m_fAccumulate;
    CBench*    m_pBench;
};

На самом деле, согласно Plauger в «Стандартной библиотеке C» [91], isalpha часто реализуется с использованием таблицы поиска. Эта книга действительно устарела, но, возможно, она актуальна и сегодня. Вот его предложенное определение isalpha

Функция

int isalpha(int c)
{
    return (_Ctype[c] & (_LO|_UP|_XA));
}

Макрос

#define isalpha(c) (_Ctype[(int)(c)] & (_LO|_UP|_XA))

Реализация вашей библиотеки компилятора, вероятно, будет достаточно эффективной и, вероятно, уже использует таблицу поиска в большинстве случаев, но также обрабатывает некоторые ситуации, которые могут быть немного сложными для правильного понимания, если вы собираетесь делать свои собственные isalpha():

• правильная работа с подписанными символами (используя отрицательную индексацию в таблице поиска)
• работа с локалями, отличными от ASCII

Возможно, вам не нужно обрабатывать локали, отличные от ASCII, и в этом случае вы можете (возможно) немного улучшить библиотеку.

На самом деле, я не удивлюсь, если макрос или функция просто вернет результат:

((('a' <= (c)) && ((c) <= 'z')) || (('A' <= (c)) && ((c) <= 'Z')))

может быть быстрее, чем поиск по таблице, поскольку ему не нужно будет попадать в память. Но я сомневаюсь, что это было бы быстрее в каком-либо значимом смысле, и было бы трудно измерить разницу, за исключением, возможно, теста, который не делал ничего, кроме вызовов isalpha() (что также могло бы улучшить результаты поиска в таблице, поскольку таблица, вероятно, будет находиться в кеше для многие тесты).

И действительно ли isalpha() является узким местом? Для всех?

Просто используйте тот, который находится в библиотеке вашего компилятора.

Если вы ищете буквенные символы, az, это намного меньше символов, чем ваш массив из 255. Вы можете вычесть «A» из рассматриваемого символа ASCII (самый низкий буквенный символ), который будет индексом в вашем массиве. например «B» - «A» равно 1. Если тест отрицательный, это не альфа. Если больше вашей максимальной альфы ('z'), то это не альфа.

Если вы вообще используете юникод, этот метод не сработает.

Я думаю, что вы можете реализовать isalpha намного проще, чем с таблицей поиска. Используя тот факт, что символы 'a'-'z' и 'A'-'Z' идут друг за другом в ASCII достаточно простого теста:

char c ;
// c gets some value
if(('A'<=c && 'Z'>=c) || ('a'<=c && 'z'>=c)) // c is alpha

Обратите внимание, что это не учитывает разные локали.