Re[2]: RAM - не RAM, или Cache-Conscious Data Structures
От: remark Россия http://www.1024cores.net/
Дата: 01.05.08 18:58
Оценка:
Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, remark, Вы писали:


R>>Возьмём вот такую простенькую функцию перемножения матриц:

R>>[. . .]

MS>Большие матрицы, например, текстуры в видеопамяти, хранятся кусочками типа 16x16. Называется глупым словом Texture Swizzling. За счет этого, в среднем в 255 из 256 случаев получаем быстрый доступ, в 1 из 256 — медленный.



Это связано с тем, что алгоритмы обработки текстур обычно требуют не отдельные строки матрицы, а прямоугольники изображения. Правильно?
Если да, то это и есть Cache-Conscious оптимизация.


Я не думаю, что это утверждение истинно в общем случае без части "например"

Большие матрицы, например, текстуры в видеопамяти, хранятся кусочками типа 16x16.


Ты наверное имел в виду просто:

Текстуры в видеопамяти хранятся кусочками типа 16x16.

?


MS>Все это конечно правильно, но в реальной жизни набор алгоритмов, легко поддающихся подобной оптиимзации крайне ограничен (как типичный пример — текстурирование в видеокартах). А те алгоритмы, которые плохо поддаются оптимизации, но хочется — превращаются в кошмар.



Я больше имел в виду просто понимание/осведомленность. Определенно это не тот вид оптимизации, который стоит применять повсеместно. Но возможностей для применения больше, чем может показаться на первый взгляд.
Например есть очень часто вызываемая функция (допустим в ран-тайме серверного приложения). Этой функции требуются некоторые данные. При "неаккуратном" размещении данных (в т.ч. динамическом выделении) может получиться, что данные распределены по нескольким кэш-линиям. Плотная упаковка всех данных в одну кэш-линию может стоить усилий и при этом быть очень легко реализуема. Фактически это будет и не оптимизация, а просто "правильный" способ делать вещи.



1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re: RAM - не RAM, или Cache-Conscious Data Structures
От: blacklion Россия  
Дата: 13.05.08 08:37
Оценка:
Здравствуйте, remark, Вы писали:

R>clflush

R>
R>void _mm_clflush(void const*p) 
R>

R>Принудительная выгрузка из всех кэшей, всех процессоров заданной строки. Практическое применение этой команды для меня пока остаётся загадкой, поэтому ничего говорить не буду.
Как загадкой? А динамическая генерация кода (в частности -- Just in time compilation) и самомодифицирующийся код как частный случай, с которого всё началось когда ещё кэшей не было?

А статья такая была. Цикл статей от Криса Касперски в журнале (ныне покойном) "Программист". И даже книгу Крис издавал.

--
// Black Lion AKA Lev Serebryakov
Re[6]: RAM - не RAM, или Cache-Conscious Data Structures
От: Кодт Россия  
Дата: 13.05.08 16:03
Оценка:
Здравствуйте, 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 Россия http://www.1024cores.net/
Дата: 13.05.08 17:56
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, remark, Вы писали:


R>>Не, тут немного другой порядок получается, не такой регулярный. Тут один порядок внутри кэш-линии, и другой порядок между кэш-линиями. Как бы binary heap из binary heap'ов. Как следствие и вначале, и в середине, и в конце дерева есть участки с очень короткими переходами. В binary heap переходы с каждом разом всё длиннее и длиннее.


К>Это не бинарное дерево и не куча.

К>Это больше похоже на Б-дерево (которое как раз было придумано для внешней памяти с блочным доступом).


Бинарное дерево — это частный случай Б-дерева, правильно?
То, что я описал, вроде не похоже на 2-Б-дерево... Б-дерево регулярно по всей высоте, а это — нет...



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: RAM - не RAM, или Cache-Conscious Data Structures
От: remark Россия http://www.1024cores.net/
Дата: 13.05.08 18:29
Оценка:
Здравствуйте, 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 — в контексте виртуализации...





1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[3]: RAM - не RAM, или Cache-Conscious Data Structures
От: Black Lion Россия  
Дата: 14.05.08 05:48
Оценка:
Здравствуйте, 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
От: Кодт Россия  
Дата: 14.05.08 10:00
Оценка: 47 (2)
Здравствуйте, 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

Б-деревья арности 2^n-1 изоморфны ДДП (кстати, КЧД — это БД-3 поверх ДДП).

Чтоб рациональнее использовать блоки памяти, нам нужны Б-деревья арности 2^n. Пожалуйста:
БД-4           _e_________j_______n_o
.       a_b_c_d   f_g_h_i   k_l_m

в ряд:  e_j_n_o a_b_c_d f_g_h_i k_l_m

БД-2               _____i___________o
.          _c_____f_         _l___n
.       a_b   d_e   g_h   j_k   m

Когда дерево заполнено не до конца, — возможны варианты его построения. В данном случае мы старались оставить незаполненным самый правый нижний блок (чтоб не было дыр в линейном размещении), поэтому верхний блок получился перекошенным.
А вот пример заполненного БД-4
.               e_________j_________o_________t
.       a_b_c_d   f_g_h_i   k_l_m_n   p_q_r_s   u_v_w_x
в ряд:  e_j_o_t a_b_c_d f_g_h_i k_l_m_n p_q_r_s u_v_w_x
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[9]: RAM - не RAM, или Cache-Conscious Data Structures
От: Sinclair Россия https://github.com/evilguest/
Дата: 14.05.08 11:29
Оценка:
Здравствуйте, Кодт, Вы писали:
К>Когда дерево заполнено не до конца, — возможны варианты его построения. В данном случае мы старались оставить незаполненным самый правый нижний блок (чтоб не было дыр в линейном размещении), поэтому верхний блок получился перекошенным.
К>А вот пример заполненного БД-4
К>
К>.               e_________j_________o_________t
К>.       a_b_c_d   f_g_h_i   k_l_m_n   p_q_r_s   u_v_w_x
К>в ряд:  e_j_o_t a_b_c_d f_g_h_i k_l_m_n p_q_r_s u_v_w_x
К>

Для B-tree применяется очень простой алгоритм балансировки: как только страница переполняется, ее делят на две.
Добавим в дерево a h k m l f c o e i n b j d g:

1-4. a, h, k, m: всё помещается в одну страницу:

a_h_k_m
[page1] [page2] [page3] [page4] [page5] [page6]

5. l:
a_h     l_m     k
[page1] [page2] [page3] [page4] [page5] [page6]

При этом дерево вот такое:
    k
a_h   l_m

6-8. f, c, o:
a_c_f_h l_m_o   k
[page1] [page2] [page3] [page4] [page5] [page6]

9. e: опять переполняется первая страница. Делим ее еще раз:
a_c     l_m_o   e_k     f_h
[page1] [page2] [page3] [page4] [page5] [page6]

При этом дерево вот такое:
    e_____k
a_c   f_h   l_m_o

10-14. i, n, b, j, d волшебным образом влезают в выделенные страницы:
a_b_c_d l_m_n_o e_k     f_h_i_j
[page1] [page2] [page3] [page4] [page5] [page6]

15. g вызовет сплит страницы 4:
a_b_c_d l_m_n_o e_h_k   f_g     i_j
[page1] [page2] [page3] [page4] [page5] [page6]

Окончательный вид дерева:
        e_____h_____k
a_b_c_d   f_g   i_j   l_m_n_o
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[10]: RAM - не RAM, или Cache-Conscious Data Structures
От: Кодт Россия  
Дата: 14.05.08 12:24
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Для B-tree применяется очень простой алгоритм балансировки: как только страница переполняется, ее делят на две.


Вопрос: мы поштучно строим дерево из неупорядоченной последовательности, или преобразуем упорядоченную?
Понятно, что окончательный вид может варьироваться.

В первом случае каждая страница содержит служебную информацию:
— количество элементов
— указатели на дочерние страницы

Во втором случае — если потом будем только читать, но не изменять эту коллекцию — мы можем обеспечить максимальную компактность, ценой строго определённого вида.
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re: RAM - не RAM, или Cache-Conscious Data Structures
От: Ka3a4oK  
Дата: 14.05.08 18:39
Оценка:
Жесть.
... << RSDN@Home 1.1.4 stable rev. 510>>
Re[3]: RAM - не RAM, или Cache-Conscious Data Structures
От: Ka3a4oK  
Дата: 14.05.08 18:39
Оценка:
Здравствуйте, 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 Россия https://github.com/evilguest/
Дата: 15.05.08 03:50
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Sinclair, Вы писали:


S>>Для B-tree применяется очень простой алгоритм балансировки: как только страница переполняется, ее делят на две.


К>Вопрос: мы поштучно строим дерево из неупорядоченной последовательности, или преобразуем упорядоченную?

Я бы даже так его переформулировал: коллекция статическая или динамическая?
К>Понятно, что окончательный вид может варьироваться.

К>В первом случае каждая страница содержит служебную информацию:

К>- количество элементов
К>- указатели на дочерние страницы
Ага.

К>Во втором случае — если потом будем только читать, но не изменять эту коллекцию — мы можем обеспечить максимальную компактность, ценой строго определённого вида.

И полной статики.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[3]: RAM - не RAM, или Cache-Conscious Data Structures
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.05.08 10:16
Оценка:
Здравствуйте, remark, Вы писали:

R>Можно использовать B-tree. Реализация может быть разная. Но суть остаётся. Нельзя просто взять B-tree и получить требуемое поведение.


Есть довольно четко определенный B+ tree где как раз учитываются особенности оговоренные в "заметке" (кстати, статью бы из нее сделать). В частности дерево состоит сегментов (bucket-ов) содержащих только ключи и ссылки на другие сегменты. Сегменты содержат близкие ключи, так что попадают в кэш. Ну, и сами сегменты обрабатываются как непрерывные части памяти, что опять же положительно влияет на попадание в кэш.

Так вот все это здорово, но есть одно "но". Если речь идет именно о поиске по ключу, а не о представлении данных в отсортированном (упорядоченном) виде, то все эти финтифлюшки резко проигрывают банальной хэш-таблице. Так что по любому применение бинарного поиска оправданно только в том случае если после поиска требуется перебор значений в упорядоченном виде. Откровенно говоря такие задача для больших объемов данных я встречал только в СУБД. Или скажем так, что логично было бы для их решения СУБД и использовать.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: RAM - не RAM, или Cache-Conscious Data Structures
От: Sinclair Россия https://github.com/evilguest/
Дата: 15.05.08 11:05
Оценка: +1
Здравствуйте, VladD2, Вы писали:
VD>Так вот все это здорово, но есть одно "но". Если речь идет именно о поиске по ключу, а не о представлении данных в отсортированном (упорядоченном) виде, то все эти финтифлюшки резко проигрывают банальной хэш-таблице.
Не очень понятно, почему. "Банальная" хэш таблица вроде как достаточно плохо себя ведет по отношению к кэшу. Именно поэтому в СУБД применяются небанальные хэш-таблицы.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[4]: RAM - не RAM, или Cache-Conscious Data Structures
От: longlivedeath  
Дата: 15.05.08 16:34
Оценка: 20 (2)
Здравствуйте, WolfHound, Вы писали:

WH>А как можно програмно узнать размер кеш линии?

WH>А то у меня есть пара алгоритмов которым от этого знания может полегчать.

Существует библиотека cacheprobe для этого дела — дипломная работа одного товарища из нашего института:
http://www.cs.umu.se/~dva99ggn/thesis.html
Re[5]: RAM - не RAM, или Cache-Conscious Data Structures
От: remark Россия http://www.1024cores.net/
Дата: 15.05.08 17:13
Оценка:
Здравствуйте, longlivedeath, Вы писали:

L>Здравствуйте, WolfHound, Вы писали:


WH>>А как можно програмно узнать размер кеш линии?

WH>>А то у меня есть пара алгоритмов которым от этого знания может полегчать.

L>Существует библиотека cacheprobe для этого дела — дипломная работа одного товарища из нашего института:

L>http://www.cs.umu.se/~dva99ggn/thesis.html


Там же используется метод "зондирования". Мне кажется это не совсем то, чего хотелось бы. Там в выводах так и написано, что работает не на всех платформах. Хотелось бы именно платформенно-зависимого решения, но что б было портировано на большинство платформ. Хотя как ресёрч это, конечно, занятно...



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[4]: RAM - не RAM, или Cache-Conscious Data Structures
От: remark Россия http://www.1024cores.net/
Дата: 15.05.08 19:28
Оценка:
Здравствуйте, 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.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[9]: RAM - не RAM, или Cache-Conscious Data Structures
От: remark Россия http://www.1024cores.net/
Дата: 23.05.08 09:32
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, remark, Вы писали:


R>>Бинарное дерево — это частный случай Б-дерева, правильно?


К>Это очень частный случай. Когда в каждом блоке по одному ключу.


R>>То, что я описал, вроде не похоже на 2-Б-дерево... Б-дерево регулярно по всей высоте, а это — нет...


К>Если я правильно понял твою идею — то, как раз получается регулярная структура.



Всё. Понял.
Если взять БД-N (N — кол-во элементов в кэш-линии, в общем случае определяется в ран-тайм), то да — будет регулярная структура. Достаточно просто выбрать какой-то вычисляемый порядок между блоками.
Если же взять произвольное N, например БД-1, БД-2, то порядок уже не будет регулярным. Т.к. нам необходимо иметь "по всей высоте дерева" переходы небольшой длины (что бы следующий блок был в той же кэш-линии, что и текущий). Очевидно, что иметь только переходы небольшой длины не получится. Следовательно надо иметь то переходы небольшой длины, то большой.


К>Обычные Б-деревья, размазанные по памяти (динамически конструируемые) в каждом блоке, помимо ключей, содержат указатели на нижележащие блоки.

К>Если же адреса нижележащих блоков можно вычислять алгоритмически — то никаких проблем!


Кстати, иметь по-возможности небольшие переходы между блоками (если блок размером с кэш-линию), тоже не помешает из-за аппаратного предвыборщика данных. Он может спекулятивно загружать "следующую" кэш-линию. Если переходы только растут при спуске по дереву, то предвыборщик будет всегда промахиваться.


З.ы. А что такое ДДП и КЧД?


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[10]: RAM - не RAM, или Cache-Conscious Data Structures
От: SergH Россия  
Дата: 23.05.08 09:40
Оценка: 1 (1)
Здравствуйте, remark, Вы писали:

R>З.ы. А что такое ДДП и КЧД?


ДДП — двоичные деревья поиска
КЧД — красно-чёрные деревья

http://www.rsdn.ru/article/alg/binstree.xml
Автор(ы): Роман Акопов
Дата: 22.05.2004
Статья рассказывает об алгоритмах работы с двоичными деревьями поиска и о красно-черных деревьях (КЧД). Производится сравнение скоростных характеристик различных операций для деревьев и массивов. В прилагаемом С++-коде приводится реализация бинарных деревьев поиска и красно-черных деревьев.
Делай что должно, и будь что будет
Re[4]: RAM - не RAM, или Cache-Conscious Data Structures
От: remark Россия http://www.1024cores.net/
Дата: 23.05.08 09:54
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Так вот все это здорово, но есть одно "но". Если речь идет именно о поиске по ключу, а не о представлении данных в отсортированном (упорядоченном) виде, то все эти финтифлюшки резко проигрывают банальной хэш-таблице. Так что по любому применение бинарного поиска оправданно только в том случае если после поиска требуется перебор значений в упорядоченном виде. Откровенно говоря такие задача для больших объемов данных я встречал только в СУБД. Или скажем так, что логично было бы для их решения СУБД и использовать.



Я сам задаюсь этим вопросом
По-моему, деревьям уделяют чрезмерно много внимания, во-многих случаях действительно лучше было бы использовать хэш-таблицу.
Тем не менее различным видам деревьев в различного рода исследованиях уделяют очень много внимания. Это касается как и новых "типов" деревьев, так и оптимизаций типа Cache-Conscious. Большинство ресёрча, на котором я основывался, исходит от компаний типа Sun или Microsoft, и касается это всё по всей видимости оптимизаций как ран-таймов их виртуальных машин, так и оптимизации выполнения пользовательского кода на этих виртуальных машинах (я имею в виду Java и .NET соотв.).



1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.