Написать strlen() путем считывания групп из 8ми байтов строки - C (СИ)
Формулировка задачи:
Всем здравствуйте.
Хочу написать strlen () путем считывания групп из 8ми байтов (long long) строки. Архитектура процессора 64 бит (intel; старшие биты слева), значит, если читать строку таким методом, скорость strlen будет довольно высокой (long long ведь запихнется в регистр; чтение с оперативки медленнее, чем с регистра).
//! Прошу не писать исходники. Хочу только получить идеи реализации и ответы на вопросы.
Думаю, это должно быть примерно так:
1) Делаем преобразование указателя на чар в указатель на лонг лонг (назовем новую переменную index).
2) Пишем цикл в цикле. Во внутреннем будет будут манипуляции с битами (условие: счетчик внутреннего цикла < 8). Во внешнем count++;
Манипуляции с битами:
В этом случае ведь в битовом представлении (слева - направо)
if ( !(index [i]) << 56 >> 56)) // Найден '\0' (являются ли последние 8бит нулями) index [i] >>= 8; //Сдвиг числа (чтобы сделать предшествующее действие для всех битов)
Вопросы следующие:
1) Как качественно перевести char* в long long*? Например:char arr [] = {"AAAAAAAB"}; //ASCII 'A' = 065; В двоичном 01000001
long long *x = (long long*) arr;x != 01000001 (7 раз) и 01000010 (1раз)
(что как раз мне и требуется)?? Как максимально быстро достичь этого результата? 2) Почему в этом случае выводится не ноль: long long x; printf ("%d", (unsigned) x >> 64); /* sizeof (long long) = 8; Хоть я и считываю только первые 4ре байта, но тем не менее, они ведь все равно должны были обнулиться*/ 3) По возможности, киньте ссылку исходник strlen () (стандартной). PS Постарался написать попонятней, но, боюсь не вышло. В общем, если непонятно, что я написал, то сформулирую весь пост покороче: Меня интересует написание оптимизированной под архитектуру 64бит процессора ф-ии strlen (по-моему, стандартная strlen () оптимизирована под 32бит).Решение задачи: «Написать strlen() путем считывания групп из 8ми байтов строки»
textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define N 1000000000UL
#define K 50
size_t slen(const char * s)
{
size_t len = 0;
while (*(s++))
++len;
return len;
}
int main(void)
{
char *arr;
size_t len1, len2, len3;
size_t i;
int k;
clock_t t0, t1, t2, t3;
arr = (char*)malloc(N);
if (NULL == arr)
{
printf("Can't allocate memory");
return 1;
}
srand(time(NULL));
for (i = 0; i < N; ++i)
arr[i] = 1 + rand() % 255;
arr[N-1] = '\0';
printf("start\n");
t0 = clock();
for (k = 0; k < K; ++k)
len1 = strlen(arr), arr[N-k-2] = 1;
t1 = clock() - t0;
t0 = clock();
for (k = 0; k < K; ++k)
len2 = slen(arr), arr[N-k-2] = 1;
t2 = clock() - t0;
t0 = clock();
for (k = 0; k < K; ++k)
len3 = fast_strlen(arr), arr[N-k-2] = 1;
t3 = clock() - t0;
free(arr);
printf("len1: %ld, time: %f\n", len1, (double)(t1)/CLOCKS_PER_SEC/K);
printf("len2: %ld, time: %f\n", len2, (double)(t2)/CLOCKS_PER_SEC/K);
printf("len3: %ld, time: %f\n", len3, (double)(t3)/CLOCKS_PER_SEC/K);
return 0;
}
Объяснение кода листинга программы
- Включаем необходимые заголовочные файлы:
stdio.hдля работы с функциями ввода-выводаstdlib.hдля работы с функциейmallocиfreestring.hдля работы со строкамиtime.hдля работы со временем
- Определяем константы:
N- размер массива в байтах (1000000000 байт)K- количество итераций в каждом из циклов
- Функция strlen():
- Инициализируем переменную
lenравной 0 - В цикле считываем каждый символ строки и увеличиваем значение
lenна 1 - Возвращаем значение
len
- Инициализируем переменную
- Функция main():
- Инициализируем переменные:
arr- указатель на выделенный массив символовlen1,len2,len3- для хранения результатов работы функцийi- для итерации по массивуk- для итерации по цикламt0,t1,t2,t3- для измерения времени выполнения каждой функции
- Создаем массив символов:
- Используем функцию
mallocдля выделения памяти под массив символов - Если память не может быть выделена, выводим сообщение об ошибке и завершаем программу
- Используем функцию
- Инициализируем массив символов:
- Используем генератор случайных чисел для заполнения массива символами от 1 до 255
- Устанавливаем последний символ массива в
\0
- Измеряем время выполнения:
- Запускаем таймер
t0перед началом выполнения функции - В цикле выполняем функцию
strlenи сохраняем результат вlen1 - Восстанавливаем время выполнения и вычисляем время выполнения функции
strlen - Аналогично для функций
slenиfast_strlen
- Запускаем таймер
- Выводим результаты:
- Выводим значения
len1,len2,len3и время выполнения каждой функции
- Выводим значения
- Свобождаем память:
- Используем функцию
freeдля освобождения памяти, выделенной под массив символов
- Используем функцию
- Инициализируем переменные:
- Возвращаем 0:
- Если все шаги выполнены корректно, возвращаем 0, иначе возвращаем 1