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

Question

Я читаю «Напиши отличный код, том 2», и в нем показано следующее выполнение:

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

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

Answer 1

От Оптимизация strlen () , блог Colm MacCarthaigh:

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

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

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

Answer 2

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

Итог:

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

Answer 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);
}

Answer 4

Виктор, взгляни на это:
http://en.wikipedia.org/wiki/Strlen#Implementation

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

Answer 5

Следующее должно быть быстрее, чем простой алгоритм и работать для 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);
}

Answer 6

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

Answer 7

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