Привет! Хотел бы рассказать о процессе решения одной задачи. Она имеет очень простую формулировку и некоторые дополнительные условия, которые существенно меняют подход к решению.
В первые месяцы ковидной эры так случилось, что на моей текущей на тот момент работе всем уполовинили зарплату и я, недолго думая, пошёл на рынок труда. На собесе в одну известную российскую IT-компанию я получил эту задачу. Задачку нужно было просто решить: решить корректно, не "убив" при этом скорость "так, чтобы совсем ужас был".
Уже за рамками "вступительного испытания" ради спортивного интереса можно было посоревноваться с авторским решением в скорости. Спустя примерно год после упомянутых событий у меня появилось свободное время, пришли новые идеи и я попытался найти предельно быстрое решение, о чём и пойдёт речь в статье.
Условие задачи
Исходное условие задачи:
Напишите считалку частотного словаря.
Словом считается набор латинских букв,[a-zA-Z]+
. Все символы, кроме[a-zA-Z]
, считаются пробелами. Слова должны быть приведены к нижнему регистру. Выводить нужно частоту, затем само слово, причём результат должен быть отсортирован по частоте по убыванию, а слова, имеющие одинаковую частоту, должны быть отсортированы по алфавиту. Пример:
$ cat in.txt
I agree with you
I say what you do about the world
It's poison
And it's sick
And you want to get out of it
$ freq in.txt out.txt
$ cat out.txt
3 it
3 you
2 and
2 i
2 s
1 about
1 agree
1 do
1 get
1 of
1 out
1 poison
1 say
1 sick
1 the
1 to
1 want
1 what
1 with
1 world
Решить нужно в один поток.
Как потом оказалось (и это существенный момент), считалку требовалось написать для конкретного файла: pg.txt (по ссылке — архив, содержащий файл). Файл содержит корпус из сконкатенированных текстов на английском, немецком и, возможно, некоторых других языках.
$ md5sum *.txt
850944413ba9fd1dbf2b9694abaa930d *lf.txt
d1362c6c9de664c34c3066ec1d01078f *crlf.txt
соотв две эталонных md5
Также известно, что лучшее существующее решение отрабатывает за секунду на "среднем" современном процессоре архитектуры x86-64. Требуется дать как можно более быстрое решение.
Где всё найти
Код проекта находится в ветке master репозитория.
Окружение
Далее в тексте результаты замеров времени выполнения приведены для Intel(R) Xeon(R) CPU E5-2667 v2 @ 3.30GHz. Это Ivy Bridge. Память - DDR3 1866MHz ECC REG, 4 channels.
Мой выбор языка — C++. Компиляторы — GCC/clang актуальных версий и компилятор из Visual Studio 2019 и MinGW-w64 (в случае Windows).
На Windows я в итоге забил, так как результаты замеров времени на нём систематически оставляли желать лучшего, несмотря на настройку энергопотребления Performance.
На GCC тоже не переключался в последнее время, так что могло что-то разойтись. В ходе поиска решения даже обнаружил баг компилятора.
Характеристики текста
Количество символов: 336 183 276.
$ du -b pg.txt
336183276 pg.txt
$ LC_ALL="C" wc -m pg.txt
336183276 pg.txt
Количество символов совпадает с размером фала, т.к. файл в соответствии с условием интерпретируется как содержащий текст в однобайтовой кодировке.
Количество слов: 58 801 281.
$ LC_ALL="C" awk -F '[^A-Za-z]+' '
{
for (i = 1; i <= NF; ++i)
if ($i)
++j
}
END {
print j
}
' pg.txt
58801281
Число различных слов: 213 637.
$ LC_ALL="C" awk -F '[^A-Za-z]+' '
{
for (i = 1; i <= NF; ++i)
if ($i)
++w[tolower($i)]
}
END {
print length(w)
}
' pg.txt
213637
Как будет показано в дальнейшем, количество уникальных слов тоже является важным условием для возможности получения оптимального решения задачи. Для корпуса большего размера предложенный в конце статьи алгоритм может быть нереализуем.
Время подсчёта частот слов будет намного больше, чем время сортировки результата подсчёта, так как 58801281 >> 213637
. Основной упор при оптимизации решения придётся делать именно на посчёт частот слов.
Распределение длин слов.
$ LC_ALL="C" awk -F '[^A-Za-z]+' '
{
for (i = 1; i <= NF; ++i)
if ($i)
++l[length($i)]
}
END {
for (j in l)
print j, l[j]
}
' pg.txt | sort -k1g | column -t
1 3018380
2 10389242
3 13784482
4 10605768
5 6407052
6 4713535
7 3845034
8 2404953
9 1742863
10 1020733
11 455583
12 249480
13 108981
14 38231
15 12161
16 3546
17 881
18 219
19 73
20 20
21 15
22 8
23 2
24 7
25 1
27 2
28 2
29 5
32 3
34 1
35 1
37 3
42 1
44 2
48 1
51 1
53 1
58 1
61 2
64 1
66 2
68 1
70 1
Максимальная длина слова - 70, средняя - 4.25, медианная - 4
$ LC_ALL=C awk -F '[^A-Za-z]+' '
{
for (i = 1; i <= NF; ++i)
if ($i)
print length($i)
}
' pg.txt | sort -n | jq -s '
{
count: length,
mininum: min,
average: (add / length),
maximum: max,
median: .[length / 2 floor],
p90: .[length * 0.90 | floor],
p95: .[length * 0.95 | floor],
p99: .[length * 0.99 | floor],
p999: .[length * 0.999 | floor]
}
'
{
"count": 58801281,
"mininum": 1,
"average": 4.25427611007318,
"maximum": 70,
"median": 4,
"p90": 8,
"p95": 9,
"p99": 11,
"p999": 13
}
99.9979% слов имеют длину, не превышающую 16 символов (байт).
$ LC_ALL=C awk -F '[^A-Za-z]+' '
{
for (i = 1; i <= NF; ++i)
if ($i)
print length($i)
}
' pg.txt | sort -n | awk '
/17/ { if (!i) i = NR }
END { print i / NR }
'
0.999979
Знание этого факта мне не удалось применить с пользой. Наверное, это тоже можно использовать для оптимизации, но я не придумал хорошего способа.
Референсное решение
Несмотря на то, что есть md5 hash результата, для отладки разрабатываемого алгоритма потребуется реализация пусть медленная, но корректная и ответ которой можно будет посмотреть глазами и сравнить с ответом более продвинутой, но ещё пока неверной, реализации.
Самое простое (для меня) решение — это написать считалку "на bash" (что подразумевает использование sed
, awk
, sort
, uniq
и т.п.). Выглядит она так:
LC_ALL="C" awk -F '[^A-Za-z]+' '
{
for (i = 1; i <= NF; ++i)
if ($i)
++w[tolower($i)]
}
END {
for (i in w)
print w[i], i
}
' | sort -k1gr,2
Помещаю этот код в файл freq.sh и запускаю, передавая на вход pg.txt
, а (эталонный) вывод сохраняя в ref.txt
.
$ time bash freq.sh <pg.txt | tee ref.txt | md5sum -
real 0m24.834s
user 0m24.759s
sys 0m0.090s
850944413ba9fd1dbf2b9694abaa930d -
Криптографический хэш результата верный, а следовательно верным является и содержимое (коллизии md5 практически невероятны). Время сильно зависит от версии awk
. Год назад у меня это решение отрабатывало за 120 секунд в том же окружении.
Характеристики результата
Топ слов по частоте.
$ head -16 ref.txt | column -t
3343241 the
1852717 and
1715705 of
1560152 to
1324244 a
956926 in
933954 i
781286 he
713514 that
690876 was
665710 it
608451 you
580460 his
498427 with
442288 for
433687 had
"The" встречается 3343241 раз. Для счётчиков придётся использовать uint32_t
(или uint24
, о чём ниже).
Распределение длин слов.
$ LC_ALL="C" awk -F '[^A-Za-z]+' '
{
for (i = 1; i <= NF; ++i)
if ($i)
w[tolower($i)]
}
END {
for (i in w)
++l[length(i)]
for (j in l)
print j, l[j]
}
' pg.txt | sort -k1g | column -t
1 26
2 442
3 2958
4 10757
5 21406
6 31287
7 36105
8 33983
9 28101
10 20362
11 12875
12 7684
13 4045
14 1955
15 921
16 384
17 181
18 60
19 33
20 13
21 12
22 7
23 2
24 7
25 1
27 2
28 2
29 5
32 3
34 1
35 1
37 2
42 1
44 2
48 1
51 1
53 1
58 1
61 2
64 1
66 2
68 1
70 1
Средняя длина слова - 7.814
$ LC_ALL=C awk -F '[^A-Za-z]+' '
{
for (i = 1; i <= NF; ++i)
if ($i)
w[tolower($i)]
}
END {
for (i in w)
print length(w)
}
' pg.txt | sort -n | tee /tmp/1 | jq -s '
{
count: length,
sum: add,
mininum: min,
average: (add / length),
maximum: max,
median: .[length / 2 | floor],
p90: .[length * 0.90 | floor],
p95: .[length * 0.95 | floor],
p99: .[length * 0.99 | floor],
p999: .[length * 0.999 | floor]
}
'
{
"count": 213637,
"sum": 1669418,
"mininum": 1,
"average": 7.814273744716505,
"maximum": 70,
"median": 8,
"p90": 11,
"p95": 12,
"p99": 14,
"p999": 17
}
count
- это (опять же) количество слов, sum
- сумма их длин. Весь словарь поместится в массив длиной count + sum = 1883055
байт, если разделять слова '\0'
.
Методика измерений
Здесь стоит сразу оговорить методику измерений.
Важно создать среду, в которой воспроизводимость результатов измерений будет сохраняться как можно более стабильной.
Джиттер неизбежен, но можно свести его к минимуму. Источником джиттера могут быть прерывания потока вследствие обычной работы планировщика ОС, изменения частоты работы ядра, на котором выполняется поток, вследствие изменения режима работы процессора.
sudo find /sys/devices/system/cpu -name scaling_governor \
-exec sh -c 'echo performance >{}' ';'
sudo sh -c 'echo off >/sys/devices/system/cpu/smt/control'
sudo tuna --cpus=1-7 --isolate
Здесь в результате выполнения первой команды частота ядер почти не скачет и залочена на максимальную (на максимальную "для всех", но меньшие подмножества ядер могут работать на более высокой частоте обычно). Без этой настройки ядро переключится в режим максимальной производительности только спустя какое-то время после получения нагрузки.
У меня частоты ядер выглядят примерно так
$ grep MHz /proc/cpuinfo
cpu MHz : 3043.824
cpu MHz : 3722.037
cpu MHz : 3721.075
cpu MHz : 3674.557
cpu MHz : 3592.679
cpu MHz : 3550.398
cpu MHz : 3513.916
cpu MHz : 3612.262
cpu MHz : 3468.005
cpu MHz : 3764.145
cpu MHz : 3586.930
cpu MHz : 3576.853
cpu MHz : 3564.029
cpu MHz : 3587.192
cpu MHz : 3244.385
cpu MHz : 2761.846
Вторая команда отключает HyperThreading (это интелловское название SMT). В результате половина ядер "исчезает" (например, из вывода htop
) — остаются ядра с номерами 0-7. В некоторых случаях это даёт 30% ускорение для однопоточных задач.
Третья команда настраивает планировщик Linux не назначать потоки (что почти всегда соблюдается ОС) на ядра 1-7. Таким образом, все процессы в системе вытесняются на ядро 0. Также желательно закрыть браузер, выключить Wi-Fi и/или Ethernet и прочие источники прерываний.
Следующей командой можно посчитать количества переключений контекста на всех ядрах за 10 секунд и убедиться, что подавляющее большинство из них происходят на ядре 0:
sudo perf stat -e 'sched:sched_switch' -a -A --timeout 10000
Делаем множество запусков программы на ядрах 1-7. В качестве результата берём минимальное значение среди всех полученных (здесь нет ошибки: именно минимальное).
for i in {1..20}
do
time taskset --cpu-list 1-7 ./freq pg.txt out.txt
done
После проведения замеров времени выполнения требуется вернуть систему в исходное состояние:
sudo sh -c 'echo on >/sys/devices/system/cpu/smt/control'
sudo tuna --cpus=0-15 --include
sudo find /sys/devices/system/cpu -name scaling_governor \
-exec sh -c 'echo powersave >{}' ';'
Полное руководство по настройке системы вы можете прочитать здесь: Low latency guide. Другие статьи там также крайне интересны.
Наивное решение
Код
#include <algorithm>
#include <fstream>
#include <functional>
#include <streambuf>
#include <string_view>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <vector>
#include <cstdlib>
#include <cctype>
int main(int argc, char * argv[])
{
if (argc < 3) {
return EXIT_FAILURE;
}
std::ifstream i(argv[1]);
if (!i.is_open()) {
return EXIT_FAILURE;
}
i.seekg(0, std::ios::end);
auto size = size_t(i.tellg());
i.seekg(0, std::ios::beg);
std::string input;
input.resize(size);
i.read(input.data(), size);
auto toLower = [](char c) {
return std::tolower(std::make_unsigned_t<char>(c));
};
std::transform(std::cbegin(input), std::cend(input),
std::begin(input), toLower);
std::unordered_map<std::string_view, size_t> wordCounts;
auto isAlpha = [](char c) {
return std::isalpha(std::make_unsigned_t<char>(c));
};
auto end = std::end(input);
auto beg = std::find_if(std::begin(input), end, isAlpha);
while (beg != end) {
auto it = std::find_if(beg, end, std::not_fn(isAlpha));
++wordCounts[{beg, it}];
beg = std::find_if(it, end, isAlpha);
}
std::vector<const decltype(wordCounts)::value_type *> output;
output.reserve(wordCounts.size());
for (const auto & wordCount : wordCounts) {
output.push_back(&wordCount);
}
auto isLess = [](auto lhs, auto rhs) -> bool
{
return std::tie(rhs->second, lhs->first) <
std::tie(lhs->second, rhs->first);
};
std::sort(std::begin(output), std::end(output), isLess);
std::ofstream o(argv[2]);
if (!o.is_open()) {
return EXIT_FAILURE;
}
for (auto wordCount : output) {
o << wordCount->second << ' ' << wordCount->first << '\n';
}
return EXIT_SUCCESS;
}
Оператор сравнения "меньше" в isLess
осуществляет сравнение кортежей лексикографически и с требуемым смыслом. Преобразования, связанные со знаковостью типа в isAlpha
требуются, т.к. знаковый ли тип char
- не определено в общем случае (секция Notes здесь). Если их не сделать, то код получится некросплаформенным.
Компилирую, запускаю и убеждаюсь, что результат верный:
clang++ -std=c++20 -march=native -Ofast naive.cpp -o naive &&
time LC_ALL="C" ./naive pg.txt out.txt &&
md5sum out.txt ref.txt
real 0m5.399s
user 0m5.248s
sys 0m0.151s
850944413ba9fd1dbf2b9694abaa930d out.txt
850944413ba9fd1dbf2b9694abaa930d ref.txt
Программа отрабатывает существенно быстрее, чем freq.sh
: 5.4 секунды.
Что здесь можно оптимизировать? Можно попробовать другие реализации хэш-таблиц. Та же std::unordered_map
из libc++
(выше были приведены результаты для libstdc++
) отрабатывает уже за 3.9 секунды.
folly::F14ValueMap
- за 4.1 (folly.cpp)google::sparse_hash_map
- за 3.6 секунды (sparse_hash_map.cpp)absl::flat_hash_map
- за 2.6 (absl.cpp)google::dense_hash_map
- за 2.4 (dense_hash_map.cpp)
Также можно ускорить ввод, его предварительную обработку (приведение к нижнему регистру) и вывод: с ~0.5
секунды до ~0.1
секунды.
Общий код для всех библиотечных контейнеров: common.hpp.
Лучшее время - 2.4 секунды.
Второй подход: решение через trie
Результатам "наивного решения" до одной секунды далеко. Нужно искать и пробовать альтернативные способы решения.
Следующей идеей было использовать префиксное дерево. Модификация префиксного дерева, которая подходит для подсчёта слов, хранит в каждом узле количество раз, которое слово, соответствующее пути, оканчивающемуся в данном узле, встретилось в тексте. После того, как дерево построено, все листья содержат ненулевое значение счётчика. Также ненулевое значение счётчик может иметь и во внутренних узлах, так как одно слово может быть префиксом другого слова.
Далее следует фрагмент решения. Класс Timer
(для замера времени) и классы InputStream
и OutputStream
(кастомный ввод/вывод большими блоками) не приведены для краткости.
Код решения:
#include "helpers.hpp"
#include "io.hpp"
#include "timer.hpp"
#include <fmt/color.h>
#include <fmt/format.h>
#include <algorithm>
#include <chrono>
#include <iterator>
#include <memory>
#include <string_view>
#include <utility>
#include <vector>
#include <cassert>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
namespace
{
constexpr std::size_t kAlphabetSize = 'z' - 'a' + 1;
alignas(__m128i) char input[1 << 29];
auto inputEnd = input;
struct TrieNode
{
uint32_t count = 0;
uint32_t children[kAlphabetSize] = {};
};
} // namespace
int main(int argc, char * argv[])
{
Timer timer{fmt::format(fg(fmt::color::dark_green), "total")};
if (argc != 3) {
fmt::print(stderr, "usage: {} in.txt out.txt\n", argv[0]);
return EXIT_FAILURE;
}
using namespace std::string_view_literals;
auto inputFile =
(argv[1] == "-"sv) ? wrapFile(stdin) : openFile(argv[1], "rb");
if (!inputFile) {
fmt::print(stderr, "failed to open '{}' file to read\n", argv[1]);
return EXIT_FAILURE;
}
auto outputFile =
(argv[2] == "-"sv) ? wrapFile(stdout) : openFile(argv[2], "wb");
if (!outputFile) {
fmt::print(stderr, "failed to open '{}' file to write\n", argv[2]);
return EXIT_FAILURE;
}
timer.report("open files");
std::size_t readSize =
readInput(std::begin(input), std::size(input), inputFile);
if (readSize == 0) {
return EXIT_SUCCESS;
}
inputEnd += readSize;
timer.report("read input");
toLower(input, inputEnd);
timer.report("make input lowercase");
std::vector<TrieNode> trie(1);
{
uint32_t index = 0;
for (auto i = input; i != inputEnd; ++i) {
if (*i != '\0') {
uint32_t & child = trie[index].children[*i - 'a'];
if (child == 0) {
child = uint32_t(trie.size());
index = child;
trie.emplace_back();
} else {
index = child;
}
} else if (index != 0) {
++trie[index].count;
index = 0;
}
}
}
fmt::print(stderr, "trie size = {}\n", trie.size());
timer.report(fmt::format(fg(fmt::color::dark_blue), "count words"));
std::vector<std::pair<uint32_t, uint32_t>> rank;
std::vector<char> words;
std::vector<char> word;
auto traverseTrie = [&](const auto & traverseTrie,
const auto & children) -> void {
size_t c = 0;
for (uint32_t child : children) {
if (child != 0) {
const TrieNode & node = trie[child];
word.push_back('a' + c);
if (node.count != 0) {
rank.emplace_back(node.count, uint32_t(words.size()));
words.insert(std::cend(words), std::cbegin(word),
std::cend(word));
words.push_back('\0');
}
traverseTrie(traverseTrie, node.children);
word.pop_back();
}
++c;
}
};
traverseTrie(traverseTrie, trie.front().children);
assert(word.empty());
fmt::print(stderr, "word count = {}, length = {}\n", rank.size(),
words.size());
timer.report("recover words from trie");
std::stable_sort(std::begin(rank), std::end(rank),
[](auto && l, auto && r) { return r.first < l.first; });
timer.report(fmt::format(fg(fmt::color::dark_orange), "sort words"));
OutputStream<> outputStream{outputFile};
for (const auto & [count, word] : rank) {
if (!outputStream.print(count)) {
fmt::print(stderr, "output failure");
return EXIT_FAILURE;
}
if (!outputStream.putChar(' ')) {
fmt::print(stderr, "output failure");
return EXIT_FAILURE;
}
if (!outputStream.print(std::next(words.data(), word))) {
fmt::print(stderr, "output failure");
return EXIT_FAILURE;
}
if (!outputStream.putChar('\n')) {
fmt::print(stderr, "output failure");
return EXIT_FAILURE;
}
}
timer.report("write output");
return EXIT_SUCCESS;
}
В коде для обхода дерева использована идиома рекурсивного вызова лямбда-функции traverseTrie, взятая с SO.
Бонусом использования положения в массиве индексов дочерних элементов для кодирования символов является то, что при прямом обходе в глубину мы естественным образом получаем слова, уже отсортированные лексикографически. Далее, перед выводом результата, пары (слово, частота) остаётся только "досортировать" по частоте, не нарушая относительный порядок слов, имеющих одинаковую частоту, для чего используется стабильная сортировка.
1.48 секунды. Уже существенно ближе к секунде, чем любой из вариантов с хэш-таблицами из библиотек. К сожалению, решение через trie не удастся ощутимо ускорить. Это связано с тем как на низком уровне функционирует работа с памятью в системе.
Масштабы времени
Многим знакомы разные варианты таблицы, где приведены характерные времена для процессов, происходящих с нашим кодом во время выполнения.
Важны характерные времена выполнения инструкций разного рода и доступа к памяти: RAM и диску. Можно ожидать, что "скалярные" инструкции выполняются дольше, чем соответствующие SSE/AVX инструкции для тех же количеств данных. Инструкции контроля порядка выполнения в случае статистически частого неверного предсказания перехода сильно уступают по скорости эквивалентному коду без ветвлений, если такой можно написать, так как в случае неверного предсказания требуется сбросить конвейер и заполнить его микрооперациями для кода из другой ветки. Последовательный доступ к данным в общем или произвольный доступ к данным, которые находятся в кэше L1d, быстрее, чем если постоянно случаются кэш-промахи в результате которых происходит чтение из кэшей более высоких уровней или даже RAM. Доступ к данным на диске будет осуществляться быстрее, если его читать крупными блоками.
Таким образом, данные из памяти лучше читать последовательно - это запустит автоматическую предвыборку (prefetch) в кэши данных. При произвольном (случайном) доступе к памяти желательно трогать как можно меньшее количество кэш-линий. Например, при подсчёте слов, на каждое встретившееся слово для инкремента соответствующего ему счётчика желательно прочитать и записать только память, целиком принадлежащую единственной кэш-линии.
Для счётного префиксного дерева можно посчитать количество доступов к памяти и оценить количество кэш-миссов. Размер кэша данных L1 и размер его линии в моей системе:
$ getconf -a | grep -P '[123]_D?CACHE_'
LEVEL1_DCACHE_SIZE 32768
LEVEL1_DCACHE_ASSOC 8
LEVEL1_DCACHE_LINESIZE 64
LEVEL2_CACHE_SIZE 262144
LEVEL2_CACHE_ASSOC 8
LEVEL2_CACHE_LINESIZE 64
LEVEL3_CACHE_SIZE 26214400
LEVEL3_CACHE_ASSOC 20
LEVEL3_CACHE_LINESIZE 64
Размер TrieNode
- 108. В конце подсчёта размер массива, содержащего узлы trie, 501266. Целиком он не помещается даже в L3 кэш. В L1d помещается 303 элемента. Пока идёт подсчёт, скорей всего из L1d не вытесняются только самые "горячие" пути (например, "the"). В L2 подолгу лежит уже больше горячих путей. "Населённость" уровней результирующего дерева выглядит так: 26, 559, 5320, 27945, 65471 и т.д. Можно предположить, что двух-трёхбуквенный префикс почти всегда находится в L1d+L2, а для горячих путей и более длинный префикс не вытесняется. Таким образом для средней длины слова 4.25 будет прочитано один-три TrieNode
не из L1d. TrieNode
располагается в двух кэш-линиях. Какая из "половин" будет прочитана при чтении элемента TrieNode::children
будет определяться тем, на примерно какую половину алфавита приходится текущая буква. Последний TrieNode
придётся прочитать только чтобы инкрементировать счётчик в нём, что даёт потенциально лишний кэш-мисс. Если же расположить массив со счётчиками рядом с children
в структуре, то размер TrieNode
вырастет почти в два раза, отчего деградирует кэш-локальность. В таком случае время выполнения вырастает до 1.54 секунды.
Больше всего кэш-миссов даёт строка if (child == 0)
. Так говорит perf
. Это ожидаемо. Больше половины времени выполнения уходит на данную строку; ещё 20% на ++trie[index].count;
.
libstdc++'s policy based data structures
Среди расширений libstdc++
есть trie-based containers. Они кастомизируются и умеют делать то, что требуется: быть счётным префиксным деревом.
Так выглядит нужный контейнер:
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/trie_policy.hpp>
template<typename Key, typename Value>
using Trie =
__gnu_pbds::trie<Key, Value,
__gnu_pbds::trie_string_access_traits<Key, 'a', 'z'>,
__gnu_pbds::pat_trie_tag,
__gnu_pbds::null_node_update>;
Работает он медленнее, чем ручная реализация, представленная выше: 6.57 секунды.
Дальнейшие рассуждения
Что можно существенно улучшить в решении с префиксным деревом? Я затрудняюсь ответить: я пробовал path compression, пробовал близкие к корню пары букв хранить в массиве, пробовал ещё что-то, - ничего не давало выигрыша. До секунды ещё далеко, а значит нужно двигаться другим путём.
Как могло бы выглядеть решение, которое приводило бы к меньшему количеству случайных доступов к памяти, имело бы меньшее количество непредсказуемых условных ветвлений? В таком решении входная строка читается последовательно и для каждого очередного слова делается ровно один поход в память за значением соответствующего ему счётчика, которое затем инкрементируется и записывается обратно. Этот поход - единственное место, где случайного доступа не избежать.
Знание того, что слову соответствует некоторый конкретный счётчик, расположенный по некоторому определённому адресу в памяти - это так называемое взаимно однозначное отображение. Нам подойдёт односторонне отображение из строки в целое число - некоторая функция. Каким бы могло быть это отображение? К примеру, можно построить minimal perfect hash function. Для этого существует утилита gperf. Она строит minimal perfect hash function для некоторого набора строк. Однако, вычисление значения функции, которую генерирует gperf, является дорогим. Да и, как оказалось, построить её для 213637 значений практически нереально. Если ослабить требования и не требовать минимальности, т.е. отображения в диапазон целых чисел без пропусков, то найти perfect hash function для словаря из pg.txt
вполне реально.
Генерация хэш-функций
Процессоры x86 и ARM имеют инструкции для расчёта CRC32C. Значение CRC32, посчитанное для строки, можно использовать как хэш строки. Такая хэш-функция имеет свои недостатки (см. секцию EDIT здесь), но при решении данной задачи они не важны. Плюсом использования хардварного расчёта значения хэш-функции на основе CRC32-инструкций является то, что выполняется оно очень быстро: reciprocal throughput - от 1 до 3 тактов для однобайтового варианта инструкции. Мощность множества принимаемых значений также обладает оптимальными свойствами: минимальный нативный тип на x86, позволяющий индексировать массив из 213637 элементов, - это как раз double word или uint32_t
.
Как же сгенерировать целое семейство хэш-функций, имея только одну инструкцию? Инструкции, рассчитывающие CRC32, аккумулируют значение CRC32. То есть для расчёта значения CRC32 строки необходимо "скармливать" инструкции два операнда: текущее значение CRC32 и очередную порцию данных из строки, и делать следует это последовательно. Полученное в результате выполнения инструкции значение будет являться новым "текущим значением". Завершается процесс расчёта CRC32, когда строка пройдена полностью. На первом шаге "текущее значение" инициализируется некоторой константой. Варьируя значение этой константы можно получать разные хэш-функции.
Семейства хэш-функций надобятся, к примеру, в реализации фильтра Блума.
Количество коллизий
Посчитаем ожидаемое количество коллизий. Есть k = 213637
мячей и m = 2^32
корзин. Раскидываем мячи так, чтобы вероятность попасть в любую корзину была одинаковой и равной 1/m
. Вероятность, что i
-ый мяч попадёт в уже занятую корзину (i - 1)/m
. Ожидаемое количество корзин с более, чем одним мячом таково:
Что составляет примерно 5.31 в нашем случае.
Вероятность найти хэш-функцию такую, что случится 0 коллизий для хэша длиной 32 бита (m = 2^32
значений) среди k = 213637
строк :
from decimal import Decimal
from functools import reduce
from operator import mul
def prob(k, m):
return reduce(mul, map(lambda i: 1 - Decimal(i) / m, range(k)))
print(prob(213637, 2 ** 32)) # 0.004925409327321181763062307628
Эти расчёты говорят, что в среднем каждая двухсотая (~1/203
) хэш-функция, генерируемая гипотетическим "генератором хэш-функций", не будет давать коллизий, т.е. будет совершенной.
Код для поиска значений seed
, соответствующих совершенным хэш-функциям:
std::unordered_set<uint32_t> hashes;
for (uint32_t seed = 0;
seed < std::numeric_limits<uint32_t>::max(); // Ctrl+C
++seed) {
bool bad = false;
for (const auto & word : words) {
auto hash = seed;
for (char c : word) {
hash = _mm_crc32_u8(hash, uint8_t(c));
}
if (!hashes.insert(hash).second) {
bad = true;
break;
}
}
hashes.clear();
if (!bad) {
fmt::print("{}\n", seed);
}
}
На практике для pg.txt
совершенные хэш-функции на базе CRC32C встречаются раз в 5 чаще. Объяснения этому я не имею (кстати, был бы рад увидеть в коментариях обсуждение причин такого расхождения теории с практикой).
Реализация: sparsest hash map
Простейший вариант хэш-таблицы:
uint32_t counts[std::size_t(std::numeric_limits<uint32_t>::max()) + 1];
Для такой хэш-таблицы алгоритм подсчёта слов выглядит следующим образом. Бежим по строке и считаем хэш каждого очередного слова. Инкрементируем элемент массива counts
с индексом, равным значению хэша. Если предыдущее значение счётчика было 0, то сохраняем указатель на слово в соответствующем элементе массива words
. words
имеет тот же размер, что и counts
. После окончания подсчёта бежим по counts
и для всех ненулевых элементов собираем слова из words
. Сортируем полученные пары и выводим.
Проблемой такого подхода является то, что значения разбросаны по памяти и в одну страницу виртуальной памяти (4096 байт на x86) попадает в среднем примерно 1.026 элементов хэш-таблицы (либо 0). То есть буквально один элемент на одну страницу. Страницы физической памяти выделяются лениво, стоимость выделения ненулевая и происходит, если мы "трогаем" память - пишем в неё или читаем. В случае столь разреженной хэш-таблицы, как данная, получается, что почти на каждый элемент ОС выделяет отдельную страницу физической памяти.
Вторая проблема: для сбора результатов необходимо прочитать все 16 ГБ counts
и найти все счётчики, не содержащие нули. При этом все незатронутые при подсчёте страницы опять же будут задеты (прочитаны) и для них будет выделена физическая память, что даст дополнительное замедление (и рост потребления памяти). Всего при подсчёте задето примерно 4.9% всех страниц, в которых располагается counts
, но ОС придётся аллоцировать страницы физической памяти для всех 100% виртуальных.
В операционных системах есть функции, позволяющие узнать состояние страниц виртуальной памяти. В Linux для этих целей есть файл /proc/PID/pagemap
для каждого процесса в системе. Для текущего процесса к нему можно обратиться как к /proc/self/pagemap
. Файл состоит из 64-битных блоков, соответствующих страницам памяти процесса, старший бит которых установлен для тех страниц, для которых выделена физическая память. Для некоторой страницы, имеющей адрес первого байта p
, вычислить смещение offset
соответствующего блока в /proc/self/pagemap
можно так: offset = std::uintptr_t(p) / getpagesize()
- это смещение в файле в 8-байтных блоках. Используя знание о том, какие блоки виртуальной памяти не были затронуты, можно пропускать их целиком: в них наверняка нули.
Для того, чтобы код, содержащий массив из 2^32
элементов, скомпилировался, необходимо указать флаг -mcmodel=medium
. Также для выставления смещения в адресном пространстве 64 - log2(4096) + log2(8) = 55
бит в файле /proc/self/pagemap
потребуется включить поддержку 64-битных смещений в <stdio.h>
. Делается это указанием -D_FILE_OFFSET_BITS=64
компилятору, в результате чего становится доступна нестандартная функция fseeko64
.
При запуске данного варианта решения у меня возникла следующая проблема. В системе есть всего 32GB RAM (swap отключен) и аллоцировать виртуальной памяти больше, чем есть физической, ОС не даёт. systemd-run --scope -p MemoryMax=33G --user ./sparsest
также не решает проблему. В итоге как минимум один из двух массивов counts
и words
пришлось урезать: вместо uint32_t
для words
(напомню, тип значения его элемента должен вмещать 1883056) я использовал 3-байтовый тип uint24
:
#pragma pack(push, 1)
struct uint24 {
unsigned value : 24;
};
#pragma pack(pop)
Результаты:
6.07 секунды, если читать все 16ГБ массива
counts
.2.07 секунды, если использовать
/proc/self/pagemap
для отсева заведомо пустых страниц.
Такой подход не лучше, чем подход с trie. Двигаемся дальше.
Хэш-таблица поплотнее
Для размещения элементов будем использовать массив, размер которого меньше, чем размер области принимаемых значений хэш-функции.
Будем выбирать в качестве размера массива степени двойки. Почему? Потому что операцией взятия остатка от деления на степень двойки является операция побитового И с константой вида 0b111...111
. Операция эта на полтора порядка (десятичных на этот раз) быстрее, чем целочисленное деление (частью которого и является на самом деле получение остатка, то есть код правых частей операторов x = a / b; y = a % b;
оптимизируется в одну инструкцию, если они стоят рядом: idiv
на x86). Замечу, что использование размеров из ряда степеней двойки - это существенная оптимизация не только для случая столь узкоспециализированной хэш-таблицы, которая потребуется в решении данной задачи, но и при разработке хэш-таблиц общего назначения. Операция взятия остатка нужна, чтобы адресоваться в массиве длиной n
, используя значение хэш-функции, лежащее в диапазоне {0, 1, ..., m - 1}
, когда m > n
. Остаток от деления всегда будет в диапазоне {0, 1, ..., n - 1}
.
Так как операция взятия остатка нарушает свойство взаимной однозначности отображения, то в одну ячейку массива теперь может попадать более одного элемента. Есть два подхода для того, чтобы иметь с этим дело. Один подход - это chaining, когда в каждой ячейке массива находится некоторый контейнер, в который складываются новые элементы, имеющие одинаковое значение хэш-функции по модулю размера масива. То есть такие, для которых произошла так называемая хэш-коллизия. Другой подход - open addressing. Он состоит в том, чтобы при хэш-коллизии искать по какому-либо фиксированному алгоритму следующую незанятую ячейку.
Open addressing предполагает какое-то сканирование памяти в надежде найти пустую ячейку. Это лишние чтения из памяти, которые даже в случае стратегии линейного поиска (англ. linear probing, при хэш-коллизии пробуем следующий-по-модулю-размера-массива элемент) будут негативно сказываться на производительности. Можно ли как-то красиво использовать chaining? Ведь chaining - это не обязательно односвязные списки, как обычно даётся в определении.
Можно в каждой ячейке хранить массив фиксированной длины (корзину), состоящий из элементов, и надеяться, что он не переполнится. Получается гибрид chaining и open addressing: в двумерном массиве при коллизиях по первому измерению постепенно заполняются элементы по второму.
Переполнение корзин
Ожидаемое количество элементов, попадающих в одну корзину, - 213637 / 2^b
, где 2^b
- количество корзин.
Вероятность того, что в одной из корзин находится не более a
элементов:
Соответственно для 2^b
корзин вероятность, что ни в одной из них нет более a
элементов:
Какова же вероятность того, что нам посчастливится сгенерировать хэш-функцию, которая для 2^b
корзин не даст переполнения ни в одной из них при размере корзины a
? Будем рассматривать в качестве значений a
некоторые степени двойки, которые могут быть количествами элементов хэш-таблицы, помещающимися в одну кэш-линию: 4, 8, 16, 32.
a\b |
13 |
14 |
15 |
16 |
17 |
18 |
---|---|---|---|---|---|---|
4 |
- |
- |
- |
3.36E-7444 |
1.83E-1463 |
5.44E-175 |
8 |
- |
- |
3.54E-3369 |
9.52E-184 |
0.00107 |
0.946 |
16 |
- |
7.25E-1304 |
4.66E-7 |
0.995 |
1.00 |
1 |
32 |
8.23E-404 |
0.959 |
1.00 |
1 |
1 |
1 |
Код, дающий таблицу, приведённую выше
from decimal import Decimal, getcontext
from scipy.special import gammaincc
def prob(k, b, s):
return Decimal(gammaincc(s + 1, k / b)) ** b
K = 213637
A = [4, 8, 16, 32]
B = range(13, 19)
print('|a\\b', end='|')
for b in B:
print(b, end='|')
print()
print('|:---:', end='|')
for b in B:
print(':---:', end='|')
print()
getcontext().prec = 3
for a in A:
print(f'|{a}', end='|')
for b in B:
if a * 2 ** b >= K:
print(prob(K, 2 ** b, a), end='|')
else:
print('-', end='|')
print()
Выбор параметров хэш-таблицы
Допустим мы сгенерировали хэш-функцию не дающую коллизий на наших данных. Это значит, что для элементов попадающих в одну корзину, то есть имеющих совпадающий префикс хэша hashLow
, суффикс хэша hashHigh
не будет давать коллизий в рамках данной корзины. Если суффикс хэша хранить в корзине наряду с элементом, то, только лишь сравнивая одно значение сохранённого суффикса хэша, можно однозначно идентифицировать нужный элемент. При этом сами элементы не потребуется сравнивать на равенство.
Элементы, т.е. подстроки-слова, которые, напомню, могут иметь длину 70 байт, хранить в корзине контрпродуктивно. Хранение их в корзине раздуло бы её размер далеко за пределы одной кэш-линии (64 байта). При этом, данные эти в ходе подсчёта слов не читаются, а только единожды записываются, когда слово встречается впервые.
Таким образом в корзине будут храниться 3 значения: суффикс хэша, счётчик, указатель или индекс, указывающий на слово. При этом "горячими" из них будут являться только суффикс и счётчик. Указатель или индекс можно хранить в соседнем массиве words[hashLow][popcnt(hashHigh != 0)]
, имеющем те же размерности, что и массив с корзинами.
Далее стоит вопрос выбора AoS vs SoA ("array of structures versus structure of arrays"). Хранить ли суффиксы хэша вперемешку со счётчиками? Если хранить суффиксы хэша в отдельном массиве hashesHigh
, то массив можно загружать как вектор в SSE/AVX регистр и сравнивать с новым суффиксом хэша за одну векторную операцию без необходимости бежать циклом по массиву, перебирая все сравниваемые значения по одному. Несмотря на то, что цикл этот имел бы фиксированное максимальное количество итераций, даже будучи развёрнутым полностью он скорей всего сгенерировал бы множество инструкций условного перехода, что наверняка дало бы код более медленный, чем пара векторных инструкций, оперирующих с массивом, как целым.
Определив, какой суффикс хэша совпадает с текущим, инкрементируем соответствующий элемент массива счётчиков. Если же совпадающего значения не найдено, то значение кладём в первый незанятый элемент массива, инкрементируем соответственный элемент в массиве со счётчиками, копируем новое слово в массив со словами и сохраняем его индекс в массиве words
.
Оценим возможное количество элементов в корзине. Счётчик - это uint32_t
(если размер кэш-линии прижмёт, то можно опять же использовать uint24
), суффикс хэша - это либо uint32_t
, либо, если его размер не более 16 бит, uint16_t
(или даже uint8_t
, но здесь не пригодился). Решим неравенство в натуральных числах: (sizeof(hashHigh) + sizeof(counter)) * x = (4 + 4) * x <= 64
. Откуда x <= 8
. Для hashHigh
типа uint16_t
решение - x <= 10
. SSE/AVX регистры имеют размерами степени двойки. Отсюда - корзина будет содержать 8 элементов.
Для b = 17
вполне реально найти совершенную хэш-функцию, не дающую переполнений даже для корзины, содержащей всего 8 элементов. При таких параметрах хэш-таблицы (a = 8
, b = 17
) доля занятых элементов (англ. occupancy) равна ~0.203
. В одной корзине будет находится в среднем ~1.63
элемента.
На самом деле есть ещё один факт, который делает b = 17
оптимальным выбором. Для пометки незанятых элементов необходим так называемый "tombstone" - такое особое значение элемента массива hashesHigh
, которое не может получиться в результате вычисления hashHigh
. Если hashHigh
имеет 15 значащих бит, то при типе элемента массива hashesHigh
uint16_t
старший бит всех незанятых элементов должен содержать единицу, чтобы любое возможное значение hashHigh
, полученное как hash >> 17
, отличалось от него. Существуют SSE/AVX инструкции (movemask), которые позволяют выделять значения старших битов элементов векторных регистров и помещать их в регистр общего назначения. Другие инструкции (bsf, lzcnt) далее позволяют вычислить индекс младшего установленного бита в регистре общего назначения, который и является индексом первого незанятого элемента hashesHigh
. Всё это без каких-либо циклов и условных переходов.
Итоговый результат для данного подхода - это 0.892 секунды. Насколько мне известно, это лучший результат на данный момент. Когда я автору сообщил, что достиг субсекундной скорости, он ответил "ну, тогда возможно перегнал и с меня будет бутылка".
Выводы
Как видно, если понимать условие задачи буквально, то можно найти решение, которое будет эксплуатировать какие-то упущения формулировки.
Мне определённо больше по душе подход с trie. Решение же с фиксированным seed-ом, заточенное под конкретные входные данные, будет работать только для них (ну почти). Хотя и для подхода, который описан в статье, можно найти применение, например, если универсум фиксированный и известен заранее. Универсум при этом должен иметь не очень большое количество элементов, так как уже для 436492 элементов вероятность найти совершенную хэш-функцию на базе CRC32 меньше 2^-32
.
m = Decimal(2 ** 32)
k = 1
value = Decimal(1)
while value * m >= 1:
value *= 1 - Decimal(k) / m
k += 1
print(k) # 436492
Возможны области применения, где множество слов (или элементов иной природы), на котором нашли seed
, незначительно отличается от множества слов в текстах, с которыми алгоритм работает дальше. Если ошибки, вызванные коллизиями или переполнением корзин, несущественны, то подход также может оказаться полезен. При этом переполнение следует специальным образом обработать, например, игнорировать.
On genre
На самом деле, конечно же, в статье приведено описание того, "как можно было бы научным методом прийти к решению". Само решение я нашёл случайно, хоть и перепробовал перед этим почти всё, что описано в статье. Повезло, что нужный seed (10675 при практической вероятности ~10^-5
) нашёлся довольно быстро. Все вероятности были посчитаны постфактум, специально для статьи, чтобы дать предлагаемым подходам теоретическое обоснование.
Идея того, как могут быть устроены корзины, была мною найдена в статье Open-sourcing F14 for faster, more memory-efficient hash tables. Идея применить в решении совершенную хэш-функцию - собственная, как и способ работы с входной строкой.
Обращение к читателю
Обо всех неточностях, помарках и стилистических ошибках прошу сообщать в личку.
В коментариях рад был бы увидеть предложения альтернативных способов решения задачи. Таких, которые могли бы составить конкуренцию приведённым в статье. Также интересно было бы узнать ваше мнение о том, какие модификации или оптимизации предложенных решений стоило бы попробовать.
Спасибо Коле К. за корректуру и редактуру. Спасибо автору задачи за задачу.
Комментарии (17)
avdx
03.06.2022 16:11+2А что насчет префиксного дерева с узлом не из одного символа а из нескольких? Количество случайных доступов к памяти должно уменьшиться пропорционально, процент cache miss'ов наверное вырастет, но думаю не на столько, насколько уменьшиться количество самих обращений, т.ч. в общем должен быть выигрыш.
Orient Автор
03.06.2022 16:24Я пробовал это в каком-то виде. Называется path compression. Добавил массив, который "добивал" размер узла до целого количества кэш-линий. Ускорения не было. Для средней длины слова 4.25 это даже интуитивно кажется мне логичным.
Orient Автор
03.06.2022 19:43Код с path compression.
avdx
04.06.2022 20:32Реализация у вас неверная. По факту никакого path compression в ней не выполняется. Даже по выводу можно видеть, что число узлов получается такое же, как и без path compression, а должно быть меньше.
Если исправить, то число узлов будет почти в два раза меньше, но выигрыша по времени относительно реализации без path compression все равное не получается — усложняется логика ветвления и видимо это все съедает.
Ogoun
03.06.2022 23:32+1Ради интереса попробовал на языке с GC (C#).
Код
using System.Collections.Concurrent; using System.Diagnostics; using System.Text; var file = @"E:\Desktop\Media\pg.txt"; var sw = new Stopwatch(); sw.Start(); var word = new StringBuilder(); var freqDict = new ConcurrentDictionary<string, int>(1, 1500000); char[] block = new char[1024 * 1024 * 1024]; int count; char sym; using (var stream = new FileStream(file, FileMode.Open, FileAccess.Read, FileShare.None, 1024 * 1024 * 64)) { using (TextReader reader = new StreamReader(stream)) { while ((count = reader.ReadBlock(block, 0, block.Length)) > 0) { for (int i = 0; i < count; i++) { sym = char.ToLowerInvariant(block[i]); if (sym >= 'a' && sym <= 'z') { word.Append((char)sym); } else if (word.Length > 0) { freqDict.AddOrUpdate(word.ToString(), 1, (_, o) => o + 1); word.Clear(); } } } } } sw.Stop(); Console.WriteLine($"{freqDict.Count} words. {sw.ElapsedMilliseconds} ms"); var max = freqDict.OrderByDescending(x => x.Value).Take(25); Console.WriteLine($"Max\r\n{string.Join("\r\n", max.Select(m => $"{m.Key} = {m.Value}"))}");
Результат работы
Результат
213637 words. 5510 ms Max the = 3343241 and = 1852717 of = 1715705 to = 1560152 a = 1324244 in = 956926 i = 933954 he = 781286 that = 713514 was = 690876 it = 665710 you = 608451 his = 580460 with = 498427 for = 442288 had = 433687 as = 426356 her = 415101 she = 371545 is = 370831 at = 362783 s = 358148 not = 346718 but = 338402 on = 338295
Ogoun
03.06.2022 23:40То есть наивное решение на .net 6 и C++ по скорости практически идентичны.
v__17
04.06.2022 11:19+2Мне кажется, это не совсем корректное сравнение, проблема кроется в .Take(25)
Из документации MSDN про OrderByDescending: "This method is implemented by using deferred execution. The immediate return value is an object that stores all the information that is required to perform the action. The query represented by this method is not executed until the object is enumerated either by calling its GetEnumerator method directly or by using foreach in Visual C# or For Each in Visual Basic."
В случае применения .Take(25) достаточно будет найти 25 максимальных элементов, что совершенно неэквивалентно полной сортировке в оригинальном решении на с++
Mingun
04.06.2022 13:06Так ведь в этом решении замеряется лишь время построения словаря с частотами слов, а его сортировка и взятие 25 максимальных элементов уже за пределами кода измерения времени.
Hixon10
04.06.2022 03:27+4Зачем в этом решении используется ConcurrentDictionary?
Ogoun
06.06.2022 09:51Исключительно для сокращения кода, AddOrUpdate позволяет написать в одну строку, вместо
var s = word.ToString(); if (freqDict.ContainsKey(s) == false) { freqDict[s] = 1; } else { freqDict[s]++; }
С обычным словарем скорость работы станет на секунду меньше. 4417 ms
masyaman
04.06.2022 23:59+1Пара вопросов.
Мне не очень понятно почему бакет фиксированной длинны лучше, чем Open Addressing на массиве большего размера? Условно, если у нас 2^b корзин по 8 элементов в каждом, то почему бы не выделить 8 * 2 ^ b корзин по одному элементу, а при коллизии использовать, например, quadratic probing (он вроде как дружелюбен к кешам при маленьком заполнении)? Это из-за возможности использования векторных инструкций?
Если сделать не одну хеш-таблицу, а 26 и определять в какую из них идти по первой букве, то мы вроде бы сильно уменьшим проблему коллизиями. Эдакий одноуровневый trie. Есть подозрение, что по скорости не выиграем т.к. памяти скорее всего больше понадобится и, соответственно, больше cache miss. А если настроить размер хеш таблиц для каждой буквы отдельно? Или так не получится из-за жесткой привязки b = 17?
Orient Автор
05.06.2022 10:33+1Любой open addressing требует сравнение элементов: решение автоматически с 0.9 до 1.7 секунды замедляется, т.к. ещё в две "случайные" локации бегаем - в
words
и вoutput
(можно сократить до одной доп. локации, если в корзине хранить индексы: можно даже всё в 64 байта уместить при желанииstruct { uint16_t hashesHigh[8]; uint24 counters[8]; uint24 words[8]; }
). Если кажется, что не требует, то тогда зачем probing? Допущение хэш-коллизий автоматически влечёт за собой требование искать и сравнивать элементы вообще всегда. В исходнике есть настройка kEnableOpenAddressing - можно посмотреть, что она включает. Кроме избыточных походов по случайным адресам ещё добавляется цикл.Больше cash miss, т.к. по 1.63 элемента на корзину (=кэш-линию) уже не получим. b + битовая длина хранимого суффикса хэша должны быть равны 32 (хотя может быть можно и для 31 или 30 бит seed для perfect hash найти), чтобы сравнение суффикса хэша избавляло нас от необходимости сравнивать содержимое элементов. Действительно perfect hash требует b >= 17. Если префикс хэша будет меньше 17, то придётся хранить уже суффиксы хэша в
uint32_t
, что на Ivy Bridge повлечёт необходимость усложнить код в части сравненияhashesHigh
. Это опять же замедление. Параметры найденного решения действительно ограничены сверху и снизу.
wataru
Не могли бы вы привести пример вывода кода с trie? Интересно посмотреть как там время распределено между вводом, построением tire, рекурсивным обходом и сортировкой, а компилятора под рукой сейчас нет.
Orient Автор
Тоже под руками нет. Насколько я помню на ввод 0.1 на сортировку порядка 0.01 и на вывод такого же порядка цифры
Orient Автор