Оптимизация хранения и сравнения коротких (ASCII, 7-битных на символ) строк в переполнении стека
В своем проекте я использую огромный набор коротких строк в 7-битном ASCII и должен обрабатывать (хранить, сравнивать, искать и т. Д.) Эти строки с максимальной производительностью.
По сути, я строю некоторый массив Index типа uint64_t, и каждый элемент хранит 9 символов слова и использует этот индекс в качестве числового элемента для любой операции сравнения строк.
Текущая реализация работает быстро, но, возможно, ее можно немного улучшить, если вы будете ..
Эта функция преобразует до 9 начальных символов в значение uint64_t — любое сравнение этого числа эквивалентно стандартной функции «strcmp».
#include <cstdint>
#include <iostream>
uint64_t cnv(const char* str, size_t len)
{
uint64_t res = 0;
switch (len)
{
default:
case 9: res = str[8];
case 8: res |= uint64_t(str[7]) << 7;
case 7: res |= uint64_t(str[6]) << 14;
case 6: res |= uint64_t(str[5]) << 21;
case 5: res |= uint64_t(str[4]) << 28;
case 4: res |= uint64_t(str[3]) << 35;
case 3: res |= uint64_t(str[2]) << 42;
case 2: res |= uint64_t(str[1]) << 49;
case 1: res |= uint64_t(str[0]) << 56;
case 0: break;
}
return res;
}
int main()
{
uint64_t v0 = cnv("000", 3);
uint64_t v1 = cnv("0000000", 7);
std::cout << (v1 < v0);
}
Решение
Вы можете загрузить 8 байтов исходной строки за один раз, а затем сжать их в результирующем целом числе (и перевернуть их, если ваша машина имеет представление с порядковым номером в младшем порядке).
#include <iostream>
uint64_t ascii2ulong (const char *s, int len)
{
uint64_t i = (*(uint64_t*)s);
if (len < 8) i &= ((1UL << (len<<3))-1);
#ifndef BIG_ENDIAN
i = (i&0x007f007f007f007fUL) | ((i & 0x7f007f007f007f00) >> 1);
i = (i&0x00003fff00003fffUL) | ((i & 0x3fff00003fff0000) >> 2);
i = ((i&0x000000000fffffffUL) << 7) | ((i & 0x0fffffff00000000) << (7-4));
// Note: Previous line: an additional left shift of 7 is applied
// to make room for s[8] character
#else
i = ((i&0x007f007f007f007fUL) << 7) | ((i & 0x7f007f007f007f00) >> 8);
i = ((i&0x00003fff00003fffUL) << 14) | ((i & 0x3fff00003fff0000) >> 16);
i = ((i&0x000000000fffffffUL) << (28+7)) | ((i & 0x0fffffff00000000) >> (32-7));
#endif
if (len > 8) i |= ((uint64_t)s[8]);
return i;
}//Test
std::string ulong2str(uint64_t compressed) {
std::string s;
for (int i = 56; i >= 0; i-=7)
if (char nxt=(compressed>>i)&0x7f) s+= nxt;
return s;
}
int main() {
std::cout << ulong2str(ascii2ulong("ABCDEFGHI", 9))<<std::endl;
std::cout << ulong2str(ascii2ulong("ABCDE", 5))<<std::endl;
std::cout << (ascii2ulong("AB", 2) < ascii2ulong("B", 1))<<std::endl;
std::cout << (ascii2ulong("AB", 2) < ascii2ulong("A", 1))<<std::endl;
return 0;
}
Но обратите внимание: делая таким образом, вы формально нарушаете выделенные диапазоны адресов (если ваша исходная строка имеет < Выделено 8 байт). Если вы запустите программу с проверкой работоспособности памяти, она может вызвать ошибку во время выполнения. Чтобы избежать этого, вы можете, конечно, использовать memcpy скопировать столько байтов, сколько вам нужно вместо uint64_t i = (*(uint64_t*)s);:
uint64_t i;
memcpy(&i,s,std::min(len,8));
Если какое-то аппаратное ускорение используется для memcpy на вашей машине (что вполне вероятно) это может быть неплохо с точки зрения эффективности.
Другие решения
Других решений пока нет …