LINUX.ORG.RU
Форум — Development  

битовые операции, оптимизация работы со строками


0

0

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

void func1(char *c_str, int len)
{
char *c_str_end;
c_str_end = c_str + len;
while(c_str < c_str_end){
*c_str++ |= 0x20;
}
}

но я так понимаю, каждый раз процессору я подсовываю 8 бит (char) для обработки, хотя процессор способен за такт сделать операцию над 32 битами. не буду вдаваться в технические дебри и выяснять, как процессор использует свободные биты и чем их заполняет. очевидно, что в данной задаче возможности процессора используются не полностью. Было бы лучше процессору подсовывать на обработку 32 бита (int). Для этого строку нужно преобразовать к int, и пробежать по елементам массива, накладывая соответствующую маску 0x20202020. Есть загвоздка, хорошо, если длина строки кратна 4 или sizeof(int). Но, если длина строки не кратна 4, то, накладывая маску, можно повредить данные за пределами вверенной мне области памяти. Поэтому, как не крути, оставшиеся байты придется перебрать в цикле как char и наложить соответствующую маску 0х20. вот реализация:

void func2(char *c_str, int len)
{
int *i_str, *i_str_end;
char *c_str_end;

i_str = (int*)c_str;
i_str_end = i_str + (int)(len/sizeof(int));
while(i_str<i_str_end){
*i_str++ |= 0x20202020;
}
c_str = (char*)i_str_end;
c_str_end = c_str + len%sizeof(int);
while(c_str<c_str_end){
*c_str++ |= 0x20;
}
}

Внимание вопрос: верны ли мои размышления, будет ли вторая функция работать быстрее, чем первая? при какой длине строки вторая функция будет работать быстрее ?

anonymous
← Простейшая прога на c++
ORBIX2000 → 

Это что - игра "Что, Где, Когда"?
Тогда какой приз?

fuxx ★
()

ну ты можешь вспомнить про SIMD - размер SSE регистра - 128 бит.

grustnoe ★★
()

> Внимание вопрос: верны ли мои размышления, будет ли вторая функция

>работать быстрее, чем первая?

Теоретически - да. Проверьте экспериментально.

>при какой длине строки вторая функция будет работать быстрее ?

Аналогично: проверьте экспериментально.

Небольшое замечание -- c_str_end можно вычислить _до_ начала преобразования: c_str_end = c_str + len; IMHO, это проще.

Второе замечание -- могу ошибаться, но, по-моему, такой алгоритм действует не для всех кодировок. Или, предполагается ASCII 7-bit?

DKorolkov ★
()
Ответ на: комментарий от DKorolkov

да, строки предполагаются только аски. прогу погонял, вот только появилась загвоздка, некоторые символы (не буквы) обрабатваются не корректно, например '\'. придется отказаться от такой оптимизации кода, надо будет воспользоваться библиотечные функциями. жаль, задумка себя не оправдала.
всем спасибо

anonymous
()
Ответ на: комментарий от DKorolkov 

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 75.36     12.45    12.45      100   124.50   124.50  func1
 24.64     16.52     4.07      100    40.70    40.70  func2
  0.00     16.52     0.00        2     0.00     0.00  prepare_buf



void prepare_buf(char *buf, int len)
{
        char c = 'A';
        int i;
        for (i = 0; i++; i < len) {
                buf[i] = ++c;
                if (c > 'Z') c = 'A';
        }
}

#define LEN 3000000
#define RUN 100

int main(void)
{
        char *buf;
        int ook;

        buf = malloc(LEN);
        prepare_buf(buf, LEN);

        for (ook = 0; ook < RUN; ook++)
        func1(buf, LEN);

        prepare_buf(buf, LEN);
        for (ook = 0; ook < RUN; ook++)
        func2(buf, LEN);

        return 0;
}

$ gcc -pg test.c -o test

gcc version 2.95.3

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Простейшая прога на c++
Development
ORBIX2000 →