Здравствуйте, McSeem2, Вы писали:
MS>Здравствуйте, remark, Вы писали:
R>>Возьмём вот такую простенькую функцию перемножения матриц: R>>[. . .]
MS>Большие матрицы, например, текстуры в видеопамяти, хранятся кусочками типа 16x16. Называется глупым словом Texture Swizzling. За счет этого, в среднем в 255 из 256 случаев получаем быстрый доступ, в 1 из 256 — медленный.
Это связано с тем, что алгоритмы обработки текстур обычно требуют не отдельные строки матрицы, а прямоугольники изображения. Правильно?
Если да, то это и есть Cache-Conscious оптимизация.
Я не думаю, что это утверждение истинно в общем случае без части "например"
Большие матрицы, например, текстуры в видеопамяти, хранятся кусочками типа 16x16.
Ты наверное имел в виду просто:
Текстуры в видеопамяти хранятся кусочками типа 16x16.
?
MS>Все это конечно правильно, но в реальной жизни набор алгоритмов, легко поддающихся подобной оптиимзации крайне ограничен (как типичный пример — текстурирование в видеокартах). А те алгоритмы, которые плохо поддаются оптимизации, но хочется — превращаются в кошмар.
Я больше имел в виду просто понимание/осведомленность. Определенно это не тот вид оптимизации, который стоит применять повсеместно. Но возможностей для применения больше, чем может показаться на первый взгляд.
Например есть очень часто вызываемая функция (допустим в ран-тайме серверного приложения). Этой функции требуются некоторые данные. При "неаккуратном" размещении данных (в т.ч. динамическом выделении) может получиться, что данные распределены по нескольким кэш-линиям. Плотная упаковка всех данных в одну кэш-линию может стоить усилий и при этом быть очень легко реализуема. Фактически это будет и не оптимизация, а просто "правильный" способ делать вещи.
R>Принудительная выгрузка из всех кэшей, всех процессоров заданной строки. Практическое применение этой команды для меня пока остаётся загадкой, поэтому ничего говорить не буду.
Как загадкой? А динамическая генерация кода (в частности -- Just in time compilation) и самомодифицирующийся код как частный случай, с которого всё началось когда ещё кэшей не было?
А статья такая была. Цикл статей от Криса Касперски в журнале (ныне покойном) "Программист". И даже книгу Крис издавал.
--
// Black Lion AKA Lev Serebryakov
Re[6]: RAM - не RAM, или Cache-Conscious Data Structures
Здравствуйте, remark, Вы писали:
R>Не, тут немного другой порядок получается, не такой регулярный. Тут один порядок внутри кэш-линии, и другой порядок между кэш-линиями. Как бы binary heap из binary heap'ов. Как следствие и вначале, и в середине, и в конце дерева есть участки с очень короткими переходами. В binary heap переходы с каждом разом всё длиннее и длиннее.
Это не бинарное дерево и не куча.
Это больше похоже на Б-дерево (которое как раз было придумано для внешней памяти с блочным доступом).
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[7]: RAM - не RAM, или Cache-Conscious Data Structures
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, remark, Вы писали:
R>>Не, тут немного другой порядок получается, не такой регулярный. Тут один порядок внутри кэш-линии, и другой порядок между кэш-линиями. Как бы binary heap из binary heap'ов. Как следствие и вначале, и в середине, и в конце дерева есть участки с очень короткими переходами. В binary heap переходы с каждом разом всё длиннее и длиннее.
К>Это не бинарное дерево и не куча. К>Это больше похоже на Б-дерево (которое как раз было придумано для внешней памяти с блочным доступом).
Бинарное дерево — это частный случай Б-дерева, правильно?
То, что я описал, вроде не похоже на 2-Б-дерево... Б-дерево регулярно по всей высоте, а это — нет...
Здравствуйте, blacklion, Вы писали:
B>Здравствуйте, remark, Вы писали:
R>>clflush R>>
R>>void _mm_clflush(void const*p)
R>>
R>>Принудительная выгрузка из всех кэшей, всех процессоров заданной строки. Практическое применение этой команды для меня пока остаётся загадкой, поэтому ничего говорить не буду.
B>Как загадкой? А динамическая генерация кода (в частности -- Just in time compilation) и самомодифицирующийся код как частный случай, с которого всё началось когда ещё кэшей не было?
B>А статья такая была. Цикл статей от Криса Касперски в журнале (ныне покойном) "Программист". И даже книгу Крис издавал.
А в каком контексте clflush применяется при JIT компиляции?
Вроде ж как при модификации кода модификация будет распространяться по протоколу когерентности на общих основаниях
Насколько я помню из документации, если модифицируется выровненный блок не более 16 байт, то вообще никаких специальных мер предпринимать не надо.
В документации AMD я вижу упоминание clflush только в контексте устройств, которые не поддерживают протокол когерентности кэшей.
А в документации Intel — в контексте виртуализации...
Здравствуйте, remark, Вы писали:
R>А в каком контексте clflush применяется при JIT компиляции? R>Вроде ж как при модификации кода модификация будет распространяться по протоколу когерентности на общих основаниях :xz: R>Насколько я помню из документации, если модифицируется выровненный блок не более 16 байт, то вообще никаких специальных мер предпринимать не надо. R>В документации AMD я вижу упоминание clflush только в контексте устройств, которые не поддерживают протокол когерентности кэшей. R>А в документации Intel — в контексте виртуализации...
Очистка кэша кода. У Intel он точно сам не флашится при записи в ту область, которая закэширована (причём ведь у интела в код-кэше ещё и микрооперации или как их там нынче велено называть хранятся). У AMD -- не помню, но вроде как тоже...
Оно надо не при любой динамической генерации, но иногда приходится.
--
// Black Lion AKA Lev Serebryakov
Re[8]: RAM - не RAM, или Cache-Conscious Data Structures
Здравствуйте, remark, Вы писали:
R>Бинарное дерево — это частный случай Б-дерева, правильно?
Это очень частный случай. Когда в каждом блоке по одному ключу.
R>То, что я описал, вроде не похоже на 2-Б-дерево... Б-дерево регулярно по всей высоте, а это — нет...
Если я правильно понял твою идею — то, как раз получается регулярная структура.
Обычные Б-деревья, размазанные по памяти (динамически конструируемые) в каждом блоке, помимо ключей, содержат указатели на нижележащие блоки.
Если же адреса нижележащих блоков можно вычислять алгоритмически — то никаких проблем!
Разница с кучей — в порядке (в куче дочерние узлы "больше" родительского, в Б-дереве — "меньше-больше").
массив a b c d e f g h i j k l m n o
ДДП _______h_______
. ___d___ ___l___
. _b_ _f_ _j_ _n_
. a c e g i k m o
в ряд: h d l b f j n a c e g i k m o
БД-3 d_______h_______l
. a_b_c e_f_g i_j_k m_n_o
в ряд: d_h_l a_b_c e_f_g i_j_k m_n_o
Когда дерево заполнено не до конца, — возможны варианты его построения. В данном случае мы старались оставить незаполненным самый правый нижний блок (чтоб не было дыр в линейном размещении), поэтому верхний блок получился перекошенным.
А вот пример заполненного БД-4
Здравствуйте, Кодт, Вы писали: К>Когда дерево заполнено не до конца, — возможны варианты его построения. В данном случае мы старались оставить незаполненным самый правый нижний блок (чтоб не было дыр в линейном размещении), поэтому верхний блок получился перекошенным. К>А вот пример заполненного БД-4 К>
Для B-tree применяется очень простой алгоритм балансировки: как только страница переполняется, ее делят на две.
Добавим в дерево a h k m l f c o e i n b j d g:
Здравствуйте, Sinclair, Вы писали:
S>Для B-tree применяется очень простой алгоритм балансировки: как только страница переполняется, ее делят на две.
Вопрос: мы поштучно строим дерево из неупорядоченной последовательности, или преобразуем упорядоченную?
Понятно, что окончательный вид может варьироваться.
В первом случае каждая страница содержит служебную информацию:
— количество элементов
— указатели на дочерние страницы
Во втором случае — если потом будем только читать, но не изменять эту коллекцию — мы можем обеспечить максимальную компактность, ценой строго определённого вида.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re: RAM - не RAM, или Cache-Conscious Data Structures
Здравствуйте, remark, Вы писали:
R>Здравствуйте, McSeem2, Вы писали:
MS>>Здравствуйте, remark, Вы писали:
R>>>Возьмём вот такую простенькую функцию перемножения матриц: R>>>[. . .]
MS>>Большие матрицы, например, текстуры в видеопамяти, хранятся кусочками типа 16x16. Называется глупым словом Texture Swizzling. За счет этого, в среднем в 255 из 256 случаев получаем быстрый доступ, в 1 из 256 — медленный.
R>Это связано с тем, что алгоритмы обработки текстур обычно требуют не отдельные строки матрицы, а прямоугольники изображения. Правильно? R>Если да, то это и есть Cache-Conscious оптимизация.
Если быть точнее, то опять сказывается вдияние порядка обхода. При текстурировании происходит сканирование текстуры не по строчке, а вдоль некторого отрезка.
Поэтому группируют данные внутри прямоугольных блоков. Надеюсь, ничего не напутал, я в этом деле не спец.
... << RSDN@Home 1.1.4 stable rev. 510>>
Re[11]: RAM - не RAM, или Cache-Conscious Data Structures
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Sinclair, Вы писали:
S>>Для B-tree применяется очень простой алгоритм балансировки: как только страница переполняется, ее делят на две.
К>Вопрос: мы поштучно строим дерево из неупорядоченной последовательности, или преобразуем упорядоченную?
Я бы даже так его переформулировал: коллекция статическая или динамическая? К>Понятно, что окончательный вид может варьироваться.
К>В первом случае каждая страница содержит служебную информацию: К>- количество элементов К>- указатели на дочерние страницы
Ага.
К>Во втором случае — если потом будем только читать, но не изменять эту коллекцию — мы можем обеспечить максимальную компактность, ценой строго определённого вида.
И полной статики.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[3]: RAM - не RAM, или Cache-Conscious Data Structures
Здравствуйте, remark, Вы писали:
R>Можно использовать B-tree. Реализация может быть разная. Но суть остаётся. Нельзя просто взять B-tree и получить требуемое поведение.
Есть довольно четко определенный B+ tree где как раз учитываются особенности оговоренные в "заметке" (кстати, статью бы из нее сделать). В частности дерево состоит сегментов (bucket-ов) содержащих только ключи и ссылки на другие сегменты. Сегменты содержат близкие ключи, так что попадают в кэш. Ну, и сами сегменты обрабатываются как непрерывные части памяти, что опять же положительно влияет на попадание в кэш.
Так вот все это здорово, но есть одно "но". Если речь идет именно о поиске по ключу, а не о представлении данных в отсортированном (упорядоченном) виде, то все эти финтифлюшки резко проигрывают банальной хэш-таблице. Так что по любому применение бинарного поиска оправданно только в том случае если после поиска требуется перебор значений в упорядоченном виде. Откровенно говоря такие задача для больших объемов данных я встречал только в СУБД. Или скажем так, что логично было бы для их решения СУБД и использовать.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: RAM - не RAM, или Cache-Conscious Data Structures
Здравствуйте, VladD2, Вы писали: VD>Так вот все это здорово, но есть одно "но". Если речь идет именно о поиске по ключу, а не о представлении данных в отсортированном (упорядоченном) виде, то все эти финтифлюшки резко проигрывают банальной хэш-таблице.
Не очень понятно, почему. "Банальная" хэш таблица вроде как достаточно плохо себя ведет по отношению к кэшу. Именно поэтому в СУБД применяются небанальные хэш-таблицы.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[4]: RAM - не RAM, или Cache-Conscious Data Structures
Здравствуйте, WolfHound, Вы писали:
WH>А как можно програмно узнать размер кеш линии? WH>А то у меня есть пара алгоритмов которым от этого знания может полегчать.
Здравствуйте, longlivedeath, Вы писали:
L>Здравствуйте, WolfHound, Вы писали:
WH>>А как можно програмно узнать размер кеш линии? WH>>А то у меня есть пара алгоритмов которым от этого знания может полегчать.
L>Существует библиотека cacheprobe для этого дела — дипломная работа одного товарища из нашего института: L>http://www.cs.umu.se/~dva99ggn/thesis.html
Там же используется метод "зондирования". Мне кажется это не совсем то, чего хотелось бы. Там в выводах так и написано, что работает не на всех платформах. Хотелось бы именно платформенно-зависимого решения, но что б было портировано на большинство платформ. Хотя как ресёрч это, конечно, занятно...
Здравствуйте, Black Lion, Вы писали:
R>>А в каком контексте clflush применяется при JIT компиляции? R>>Вроде ж как при модификации кода модификация будет распространяться по протоколу когерентности на общих основаниях R>>Насколько я помню из документации, если модифицируется выровненный блок не более 16 байт, то вообще никаких специальных мер предпринимать не надо. R>>В документации AMD я вижу упоминание clflush только в контексте устройств, которые не поддерживают протокол когерентности кэшей. R>>А в документации Intel — в контексте виртуализации...
BL> Очистка кэша кода. У Intel он точно сам не флашится при записи в ту область, которая закэширована (причём ведь у интела в код-кэше ещё и микрооперации или как их там нынче велено называть хранятся). У AMD -- не помню, но вроде как тоже... BL> Оно надо не при любой динамической генерации, но иногда приходится.
Вот всё, что я вижу в "Intel® 64 and IA-32 Architectures Software Developer’s Manual. Volume 3A: System Programming Guide, Part 1" по поводу Self- и Cross-Modifying кода. Тут нет никаких упоминаний ни clflush, ни необходимости ручного сброса кэша. Тут вроде написано как раз обратное, что записи в область кода сбрасываются в память сразу, L1I кэш даже не поддерживает состояния M и E (смотри раздел 10.4).
7.1.3 Handling Self- and Cross-Modifying Code
The act of a processor writing data into a currently executing code segment with
the intent of executing that data as code is called self-modifying code. IA-32
processors exhibit model-specific behavior when executing self-modified code,
depending upon how far ahead of the current execution pointer the code has been
modified.
As processor microarchitectures become more complex and start to speculatively
execute code ahead of the retirement point (as in P6 and more recent processor
families), the rules regarding which code should execute, pre- or post-modification,
become blurred. To write self-modifying code and ensure that it is compliant with
current and future versions of the IA-32 architectures, use one of the following
coding options:
(* OPTION 1 *)
Store modified code (as data) into code segment;
Jump to new code or an intermediate location;
Execute new code;
(* OPTION 2 *)
Store modified code (as data) into code segment;
Execute a serializing instruction; (* For example, CPUID instruction *)
Execute new code;
The use of one of these options is not required for programs intended to run on the
Pentium or Intel486 processors, but are recommended to insure compatibility with
the P6 and more recent processor families.
Self-modifying code will execute at a lower level of performance than non-self-modifying
or normal code. The degree of the performance deterioration will depend upon
the frequency of modification and specific characteristics of the code.
The act of one processor writing data into the currently executing code segment of a
second processor with the intent of having the second processor execute that data as
code is called cross-modifying code. As with self-modifying code, IA-32 processors
exhibit model-specific behavior when executing cross-modifying code, depending
upon how far ahead of the executing processors current execution pointer the code
has been modified.
To write cross-modifying code and insure that it is compliant with current and future
versions of the IA-32 architecture, the following processor synchronization algorithm
must be implemented:
(* Action of Modifying Processor *)
Memory_Flag ← 0; (* Set Memory_Flag to value other than 1 *)
Store modified code (as data) into code segment;
Memory_Flag ← 1;
(* Action of Executing Processor *)
WHILE (Memory_Flag ≠ 1)
Wait for code to update;
ELIHW;
Execute serializing instruction; (* For example, CPUID instruction *)
Begin executing modified code;
(The use of this option is not required for programs intended to run on the Intel486
processor, but is recommended to insure compatibility with the Pentium 4, Intel
Xeon, P6 family, and Pentium processors.)
Like self-modifying code, cross-modifying code will execute at a lower level of performance
than non-cross-modifying (normal) code, depending upon the frequency of
modification and specific characteristics of the code.
The restrictions on self-modifying code and cross-modifying code also apply to the
Intel 64 architecture.
10.6 SELF-MODIFYING CODE
A write to a memory location in a code segment that is currently cached in the
processor causes the associated cache line (or lines) to be invalidated. This check is
based on the physical address of the instruction. In addition, the P6 family and
Pentium processors check whether a write to a code segment may modify an instruction
that has been prefetched for execution. If the write affects a prefetched instruction,
the prefetch queue is invalidated. This latter check is based on the linear
address of the instruction. For the Pentium 4 and Intel Xeon processors, a write or a
snoop of an instruction in a code segment, where the target instruction is already
decoded and resident in the trace cache, invalidates the entire trace cache. The latter
behavior means that programs that self-modify code can cause severe degradation
of performance when run on the Pentium 4 and Intel Xeon processors.
In practice, the check on linear addresses should not create compatibility problems
among IA-32 processors. Applications that include self-modifying code use the same
linear address for modifying and fetching the instruction. Systems software, such as
a debugger, that might possibly modify an instruction using a different linear address
than that used to fetch the instruction, will execute a serializing operation, such as a
CPUID instruction, before the modified instruction is executed, which will automatically
resynchronize the instruction cache and prefetch queue. (See Section 7.1.3,
“Handling Self- and Cross-Modifying Code,” for more information about the use of
self-modifying code.)
For Intel486 processors, a write to an instruction in the cache will modify it in both
the cache and memory, but if the instruction was prefetched before the write, the old
version of the instruction could be the one executed. To prevent the old instruction
from being executed, flush the instruction prefetch unit by coding a jump instruction
immediately after any write that modifies an instruction.
10.4 CACHE CONTROL PROTOCOL
The L1 instruction cache in P6 family processors implements only the “SI” part of the
MESI protocol, because the instruction cache is not writable. The instruction cache
monitors changes in the data cache to maintain consistency between the caches
when instructions are modified. See Section 10.6, “Self-Modifying Code,” for more
information on the implications of caching instructions.
17.28.1 Self-Modifying Code with Cache Enabled
On the Intel486 processor, a write to an instruction in the cache will modify it in both
the cache and memory. If the instruction was prefetched before the write, however,
the old version of the instruction could be the one executed. To prevent this problem,
it is necessary to flush the instruction prefetch unit of the Intel486 processor by
coding a jump instruction immediately after any write that modifies an instruction.
The P6 family and Pentium processors, however, check whether a write may modify
an instruction that has been prefetched for execution. This check is based on the
linear address of the instruction. If the linear address of an instruction is found to be
present in the prefetch queue, the P6 family and Pentium processors flush the
prefetch queue, eliminating the need to code a jump instruction after any writes that
modify an instruction.
Я в замешательстве, и по прежнему не вижу применений для clflush.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, remark, Вы писали:
R>>Бинарное дерево — это частный случай Б-дерева, правильно?
К>Это очень частный случай. Когда в каждом блоке по одному ключу.
R>>То, что я описал, вроде не похоже на 2-Б-дерево... Б-дерево регулярно по всей высоте, а это — нет...
К>Если я правильно понял твою идею — то, как раз получается регулярная структура.
Всё. Понял.
Если взять БД-N (N — кол-во элементов в кэш-линии, в общем случае определяется в ран-тайм), то да — будет регулярная структура. Достаточно просто выбрать какой-то вычисляемый порядок между блоками.
Если же взять произвольное N, например БД-1, БД-2, то порядок уже не будет регулярным. Т.к. нам необходимо иметь "по всей высоте дерева" переходы небольшой длины (что бы следующий блок был в той же кэш-линии, что и текущий). Очевидно, что иметь только переходы небольшой длины не получится. Следовательно надо иметь то переходы небольшой длины, то большой.
К>Обычные Б-деревья, размазанные по памяти (динамически конструируемые) в каждом блоке, помимо ключей, содержат указатели на нижележащие блоки. К>Если же адреса нижележащих блоков можно вычислять алгоритмически — то никаких проблем!
Кстати, иметь по-возможности небольшие переходы между блоками (если блок размером с кэш-линию), тоже не помешает из-за аппаратного предвыборщика данных. Он может спекулятивно загружать "следующую" кэш-линию. Если переходы только растут при спуске по дереву, то предвыборщик будет всегда промахиваться.
Здравствуйте, VladD2, Вы писали:
VD>Так вот все это здорово, но есть одно "но". Если речь идет именно о поиске по ключу, а не о представлении данных в отсортированном (упорядоченном) виде, то все эти финтифлюшки резко проигрывают банальной хэш-таблице. Так что по любому применение бинарного поиска оправданно только в том случае если после поиска требуется перебор значений в упорядоченном виде. Откровенно говоря такие задача для больших объемов данных я встречал только в СУБД. Или скажем так, что логично было бы для их решения СУБД и использовать.
Я сам задаюсь этим вопросом
По-моему, деревьям уделяют чрезмерно много внимания, во-многих случаях действительно лучше было бы использовать хэш-таблицу.
Тем не менее различным видам деревьев в различного рода исследованиях уделяют очень много внимания. Это касается как и новых "типов" деревьев, так и оптимизаций типа Cache-Conscious. Большинство ресёрча, на котором я основывался, исходит от компаний типа Sun или Microsoft, и касается это всё по всей видимости оптимизаций как ран-таймов их виртуальных машин, так и оптимизации выполнения пользовательского кода на этих виртуальных машинах (я имею в виду Java и .NET соотв.).