Написать 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;
}

Объяснение кода листинга программы

  1. Включаем необходимые заголовочные файлы:
    • stdio.h для работы с функциями ввода-вывода
    • stdlib.h для работы с функцией malloc и free
    • string.h для работы со строками
    • time.h для работы со временем
  2. Определяем константы:
    • N - размер массива в байтах (1000000000 байт)
    • K - количество итераций в каждом из циклов
  3. Функция strlen():
    • Инициализируем переменную len равной 0
    • В цикле считываем каждый символ строки и увеличиваем значение len на 1
    • Возвращаем значение len
  4. Функция 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 для освобождения памяти, выделенной под массив символов
  5. Возвращаем 0:
    • Если все шаги выполнены корректно, возвращаем 0, иначе возвращаем 1

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 3.733 из 5
Похожие ответы