Написать 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
иfree
string.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
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д