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

Question

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

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

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

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

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

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

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

Answer 1

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

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