Как написать лучшую функцию strlen?

Я читаю "Write Great Code Volume 2", и он показывает следующую иммерсионность:

int myStrlen( char *s )
{
    char *start;
    start = s;
    while( *s != 0 )
    {
        ++s;
    }
    return s - start;
}

В книге говорится, что эта реализация типична для неопытного программиста C. Я кодируюсь на C в течение последних 11 лет, и я не вижу, как написать функцию лучше, чем это в C (я могу думать о том, чтобы лучше писать в сборке). Как можно писать код лучше, чем в C? Я посмотрел стандартную библиотечную реализацию функции strlen в glibc, и я не мог понять ее большую часть. Где я могу найти лучшую информацию о том, как писать высоко оптимизированный код?

Ответы

Ответ 1

Из Оптимизация strlen(), blogpost от Colm MacCarthaigh:

К сожалению, в C были обречены на реализацию O (n), в лучшем случае, но все еще не были выполнены... мы можем сделать что-то о самом размере n.

Это хороший пример того, в каком направлении вы можете работать, чтобы ускорить его. И еще одна цитата из него

Иногда происходит действительно очень быстро, просто делает вас действительно безумным.

Ответ 2

Виктор, посмотри на это:
http://en.wikipedia.org/wiki/Strlen#Implementation

P.S. Причина, по которой вы не понимаете версию glibc, вероятно, потому, что она использует смещение бита, чтобы найти\0.

Ответ 3

Для начала это бесполезно для кодировок, таких как UTF-8... то есть вычисление количества символов в строке UTF-8 более сложно, тогда как количество байтов, конечно, так же просто вычислить, как, например, строку ASCII.

В целом, вы можете оптимизировать некоторые платформы, читая их в более крупные регистры. Поскольку другие ссылки, опубликованные до сих пор, не имеют примера этого, здесь немного псевдо-псевдокода для нижнего конца:

int size = 0;
int x;
int *caststring = (int *) yourstring;
while (int x = *caststring++) {
  if (!(x & 0xff)) /* first byte in this int-sized package is 0 */ return size;
  else if (!(x & 0xff00)) /* second byte etc. */ return size+1;
  /* rinse and repeat depending on target architecture, i.e. twice more for 32 bit */
  size += sizeof (int);
}

Ответ 4

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

Нижняя строка:

Отличный код подчеркивает читаемость по скорости во всех случаях, кроме самых критически важных. Напишите свой код так четко, как только сможете, и только оптимизируйте детали, которые оказались узкими местами.

Ответ 5

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

Ответ 6

Отвечая на вопрос OP о том, где искать предложения, как писать код для производительности, здесь ссылка в MIT OpenCourse при написании оптимизированного кода C (смотрите Ссылка "Материалы" слева от страницы).

Ответ 7

Следующее должно быть быстрее, чем наивный алгоритм и работать для 32/64 бит.

union intptr {
    char* c;
    long* l;
#define LSIZE sizeof(long)
};

#define aligned_(x, a) \
    ((unsigned long) (x) % (a) == 0)

#define punpktt_(x, from, to) \
    ((to) (-1)/(from) (-1)*(from) (x))
#define punpkbl_(x) \
    punpktt_(x, unsigned char, unsigned long)

#define plessbl_(x, y) \
    (((x) - punpkbl_(y)) & ~(x) & punpkbl_(0x80))
#define pzerobl_(x) \
    plessbl_(x, 1)

static inline unsigned long maskffs_(unsigned long x)
{
    unsigned long acc = 0x00010203UL;
    if (LSIZE == 8)
       acc = ((acc << 16) << 16) | 0x04050607UL;
    return ((x & -x) >> 7) * acc >> (LSIZE*8-8);
}

size_t strlen(const char* base)
{
    union intptr p = { (char*) base };
    unsigned long mask;

    for ( ; !aligned_(p.c, LSIZE); p.c++ )
        if (*p.c == 0)
            return p.c - base;

    while ( !(mask = pzerobl_(*p.l)) )
        p.l++;
    return p.c - base + maskffs_(mask);
}