Веревки: что «достаточно велико, чтобы извлечь выгоду из эффектов кэша»?

Question

Из Википедия :

Основные недостатки больше общее использование пространства и медленнее индексирование, оба из которых становятся более суров, как древовидная структура становится больше и глубже. Тем не менее, многие практическое применение индексации включать только итерацию по Строка, которая остается быстрой до тех пор, пока узлы листа достаточно велики, чтобы извлечь выгоду из эффектов кэша.

Я реализую своего рода компромисс между веревками и струнами. В основном это просто веревки, за исключением того, что я объединяю объекты конкатенации в строки, когда конкатенированные строки короткие. Для этого есть несколько причин:

1. Преимущества объектов конкатенации минимальны, когда конкатенированные строки короткие (не требуется слишком много времени для конкатенации двух строк в их обычной форме).
2. Это уменьшает размер / глубину дерева (сокращает нижние стороны канатов).
3. При этом увеличивается размер конечных узлов (чтобы лучше использовать кеш).

Однако, когда длина увеличивается, преимущества *1020* канатов также уменьшаются, поэтому я хотел бы найти некоторый компромисс. Логично, что «сладкое пятно» находится там, где «конечные узлы достаточно велики, чтобы извлечь выгоду из эффектов кэша». Проблема в том, что я не знаю, насколько она велика.

РЕДАКТИРОВАТЬ: Когда я писал это, мне пришло в голову, что идеальный размер будет размером страницы кеша, потому что тогда веревка вызывает пропуски кеша только тогда, когда они произойдут в любом случае в строке. Итак, мой второй вопрос: правильны ли эти рассуждения? И существует ли кроссплатформенный способ определения размера страницы кэша?

Мой целевой язык - C ++.

Answer 1

Предел для веревочеобразной нити будет построен поверх std::list<char>. Это, очевидно, не очень эффективно. При выполнении итерации у вас может быть одна ошибка кэша на «лист» / символ. По мере увеличения количества символов на листе среднее число пропусков уменьшается с разрывом, как только распределение листьев превышает одну строку кэша.

Это может быть хорошей идеей, чтобы иметь большие листья; передача памяти в иерархиях кеша может иметь разную степень детализации на разных уровнях. Кроме того, при нацеливании на смешанный набор процессоров (то есть потребительских ПК) размер листа, который является большей степенью двойки, будет целым кратным размеру строки кэша на большем количестве машин. Например. если вы обращаетесь к процессорам с 16- и 32-байтовыми строками кэша, 32 байта будет лучшим выбором, поскольку это всегда целое число строк кэша. Потерять половину строки кэша - позор.