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

S>Здравствуйте, VladD2, Вы писали:
VD>>Так вот все это здорово, но есть одно "но". Если речь идет именно о поиске по ключу, а не о представлении данных в отсортированном (упорядоченном) виде, то все эти финтифлюшки резко проигрывают банальной хэш-таблице.

S>Не очень понятно, почему. "Банальная" хэш таблица вроде как достаточно плохо себя ведет по отношению к кэшу. Именно поэтому в СУБД применяются небанальные хэш-таблицы.


Имхо как раз хорошо. Мы сразу "тыкаем" в нужный элемент (или очень рядом). Этот элемент случайный, это да. Но с деревом то мы тоже доберёмся до этого же случайного элемента, только перед этим "пройдёмся" по ряду других "случайных" и не интересующих нас элементов.

Здравствуйте, remark, Вы писали:
R>Имхо как раз хорошо. Мы сразу "тыкаем" в нужный элемент (или очень рядом). Этот элемент случайный, это да. Но с деревом то мы тоже доберёмся до этого же случайного элемента, только перед этим "пройдёмся" по ряду других "случайных" и не интересующих нас элементов.
Для read-only операций да. Но для них можно сделать вообще perfect hash, и добиться попаданий с первого раза при оптимальном использовании кэша.
А вот для пополняемых таблиц — дупа. Рехешинг, которым обычно решают проблему переполнения, приведет к полному сбросу кэша, и если таблица больше кэша процессора, то поведение будет крайне неприятным. B-trees, как и модификации хештаблиц для СУБД учитывают это, и стараются ограничить количество страниц, которые затрагиваются при всех операциях.

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

S>А вот для пополняемых таблиц — дупа. Рехешинг, которым обычно решают проблему переполнения, приведет к полному сбросу кэша, и если таблица больше кэша процессора, то поведение будет крайне неприятным.

Закрытое хэширование?
Несколько поколений таблицы + рехешенг в фоне?

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

R>По-моему, деревьям уделяют чрезмерно много внимания, во-многих случаях действительно лучше было бы использовать хэш-таблицу.
Да, причём в хэш-таблицах тоже не всё так уж просто и прямо, если честно.

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

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

S>Здравствуйте, remark, Вы писали:
R>>Имхо как раз хорошо. Мы сразу "тыкаем" в нужный элемент (или очень рядом). Этот элемент случайный, это да. Но с деревом то мы тоже доберёмся до этого же случайного элемента, только перед этим "пройдёмся" по ряду других "случайных" и не интересующих нас элементов.

S>Для read-only операций да. Но для них можно сделать вообще perfect hash, и добиться попаданий с первого раза при оптимальном использовании кэша.
S>А вот для пополняемых таблиц — дупа. Рехешинг, которым обычно решают проблему переполнения, приведет к полному сбросу кэша, и если таблица больше кэша процессора, то поведение будет крайне неприятным. B-trees, как и модификации хештаблиц для СУБД учитывают это, и стараются ограничить количество страниц, которые затрагиваются при всех операциях.

Ну это уже что-то. По-крайней мере становится понятна мотивация разработчиков БД. Тем не менее, мне кажется, что в большей части остального ПО, это не существенно. Основная "тяжелая" операция для хэш-таблицы — это увеличение основной таблицы. Остальные могут быть выполнены достаточно локально. Имхо, обычно размер таблицы приходит в какое-то устоявшееся состояние. Например, храним в хэш-таблице пользовательские соединения/сессии. Начальный размер задаем, допустим, 4096. За несколько увеличений (удвоений) размер таблицы выйдет в "устоявшийся режим".

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

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

R>>По-моему, деревьям уделяют чрезмерно много внимания, во-многих случаях действительно лучше было бы использовать хэш-таблицу.
E>Да, причём в хэш-таблицах тоже не всё так уж просто и прямо, если честно.

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

E>Ну стандартные ассоциативные контейнеры все "деревянные"

Ты имеешь в виду С++? Будем надеяться, что в С++ это всё же исправят в будущем. В тех языках, о которых речь, — Java и .NET — афаик в стандартной библиотеке изначально присутствуют *не* только "деревянные" контейнеры.

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

R>Ты имеешь в виду С++? Будем надеяться, что в С++ это всё же исправят в будущем.
Да их в науке о структурах данных за что-то любят. Наверное за универсальность.

R>В тех языках, о которых речь, — Java и .NET — афаик в стандартной библиотеке изначально присутствуют *не* только "деревянные" контейнеры.
А кто там ассоциативный и не "деревянный"?

R>

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

R>>В тех языках, о которых речь, — Java и .NET — афаик в стандартной библиотеке изначально присутствуют *не* только "деревянные" контейнеры.
E>А кто там ассоциативный и не "деревянный"?
Эээ... java.util.HashMap, ConcurrentSkipListMap, ConcurrentNavigableMap, ...?

Здравствуйте, Erop, Вы писали:
E>Закрытое хэширование?
Что имеется в виду?
E>Несколько поколений таблицы + рехешенг в фоне?
В каком еще "фоне"?
На всякий случай напомню, что мы говорим о поведении кэша процессора. Любой "фоновый" процесс, который занимается рандомным обращением к памяти, будет вышибать данные "нефонового" процесса из кэша.

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

S>На всякий случай напомню, что мы говорим о поведении кэша процессора. Любой "фоновый" процесс, который занимается рандомным обращением к памяти, будет вышибать данные "нефонового" процесса из кэша.
Это, кстати, вопрос. У разных процессоров могут быть разные кэши.

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

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

S>>А вот для пополняемых таблиц — дупа. Рехешинг, которым обычно решают проблему переполнения, приведет к полному сбросу кэша, и если таблица больше кэша процессора, то поведение будет крайне неприятным.

E>Закрытое хэширование?
E>Несколько поколений таблицы + рехешенг в фоне?


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

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

R>Допустим таблица стала слишком заполненной — решили её увеличить. Запустили фоновый процесс. Он неспеша всё пересчитал, пришёл с новой версией структуры и обнаружил, что таблица уже сильно поменялась — добавилось много новых значений, удалилось много старых значений. Просто заменить текущую версию своей он не сможет...
Понятно, что для всех случаев это работать не будет. А вот для read-mostly — так вполне может быть и выигрыш.

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

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

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

C>Понятно, что для всех случаев это работать не будет. А вот для read-mostly — так вполне может быть и выигрыш.

Для read-mostly — это замечательное решение. Но для read-mostly и не стоит проблемы очень дорогих операций изменений, и частого роста хэш-таблицы.

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

S>Здравствуйте, Erop, Вы писали:
E>>Закрытое хэширование?
S>Что имеется в виду?
А гугол меня знает?..

E>>Несколько поколений таблицы + рехешенг в фоне?
S>В каком еще "фоне"?
S>На всякий случай напомню, что мы говорим о поведении кэша процессора. Любой "фоновый" процесс, который занимается рандомным обращением к памяти, будет вышибать данные "нефонового" процесса из кэша.
1) Прцессоров может быть и много и кэшей тоже
2) Даже если проц. один, то нагрузка на него может быть не ровной.

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

E>>Несколько поколений таблицы + рехешенг в фоне?

R>Какие-либо действия в фоне реализовать достаточно сложно в данном случае.
R>Допустим таблица стала слишком заполненной — решили её увеличить. Запустили фоновый процесс. Он неспеша всё пересчитал, пришёл с новой версией структуры и обнаружил, что таблица уже сильно поменялась — добавилось много новых значений, удалилось много старых значений. Просто заменить текущую версию своей он не сможет...

Можно какое-то время иметь две таблицы и всегда искать сначала в "новой" (большой), а потом, если не нашли, в "старой" (маленькой).

При этом, на время рехэширования, новую таблицу запираем на предмет того, что объекты не удаляем из неё, а только помечаем, как удалённые.

Ну и работаем поверх такого пирога + постепенно переносим всё из "старой" таблицы в "новую"...

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

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

E>>>Несколько поколений таблицы + рехешенг в фоне?

R>>Какие-либо действия в фоне реализовать достаточно сложно в данном случае.
R>>Допустим таблица стала слишком заполненной — решили её увеличить. Запустили фоновый процесс. Он неспеша всё пересчитал, пришёл с новой версией структуры и обнаружил, что таблица уже сильно поменялась — добавилось много новых значений, удалилось много старых значений. Просто заменить текущую версию своей он не сможет...

E>Можно какое-то время иметь две таблицы и всегда искать сначала в "новой" (большой), а потом, если не нашли, в "старой" (маленькой).

E>При этом, на время рехэширования, новую таблицу запираем на предмет того, что объекты не удаляем из неё, а только помечаем, как удалённые.

E>Ну и работаем поверх такого пирога + постепенно переносим всё из "старой" таблицы в "новую"...


Ну да, на словах всё очень просто и замечательно.

Всегда надо проверять обе таблицы, либо в новой структуре хранить "удаления" элементов, а потом как-то их все разом удалять, когда формирование новой таблицы закончено. Какой вариант ты выбираешь?

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


R>Всегда надо проверять обе таблицы, либо в новой структуре хранить "удаления" элементов, а потом как-то их все разом удалять, когда формирование новой таблицы закончено. Какой вариант ты выбираешь?

Третий
После рехеширования не удалять "удалённые" ключи, пока не потребуется занимаесое ими место...

Я ещё раз напоминаю, про закрытое хэширование...

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

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


R>>Всегда надо проверять обе таблицы, либо в новой структуре хранить "удаления" элементов, а потом как-то их все разом удалять, когда формирование новой таблицы закончено. Какой вариант ты выбираешь?

E>Третий
E>После рехеширования не удалять "удалённые" ключи, пока не потребуется занимаесое ими место...

E>Я ещё раз напоминаю, про закрытое хэширование...


Так тут придётся не удалять "удалённые" элементы не пока не понадобится занимаемое ими место. А вообще. Просто не удалять.

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

R>

RAM — не RAM

Занятно — ровно через месяц после моего поста Герб Саттер написал практически то же самое в DDJ:
Maximize Locality, Minimize Contention

Cache-Conscious Design

Locality is a first-order issue that trumps much of our existing understanding of performance optimization. Most traditional optimization techniques come after "locality" on parallel hardware (although a few are still equally or more important than locality, such as big-Oh algorithmic complexity for example).

Arrange your data carefully by following these three guidelines, starting with the most important:

First: Keep data that are not used together apart in memory. If variables A and B are not protected by the same mutex and are liable to be used by two different threads, keep them on separate cache lines. (Add padding, if necessary; it's a great way to "waste" memory to make your code run faster.) This avoids the invisible convoying of false sharing (ping-pong) where in the worst case only one contending thread can make progress at all, and so typically trumps other important cache considerations.

Second: Keep data that is frequently used together close together in memory. If a thread that uses variable A frequently also needs variable B, try to put A and B in the same cache line if possible. For example, A and B might be two fields in the same object that are frequently used together. This is a traditional technique to improve memory performance in both sequential and concurrent code, which now comes second to keeping separate data apart.

Third: Keep "hot" (frequently accessed) and "cold" (infrequently accessed) data apart. This is true even if the data is conceptually in the same logical object. This helps both to fit "hot" data into the fewest possible cache lines and memory pages and to avoid needlessly loading the "colder" parts. Together these effects reduce (a) the cache footprint and cache misses, and (b) the memory footprint and virtual memory paging.

А теперь ещё нашёл, что за 2 дня до моего поста появилась аналогичная статья на RapidMind:
Why the Future isn’t Flat

The constant-access-time “flat” memory illusion is as important as the serial illusion. In a flat memory, every location in memory can be accessed with exactly the same cost, independent of the order of access. For decades, this simple cost model has been used as an implicit assumption in the design of computer programs. Even theoretical computer science, which analyzes the best-case asymptotic complexity of algorithms for solving various abstract problems, is primarily based on this illusion. Unfortunately, it is just an illusion, although computer architects have been able to develop many clever mechanisms to maintain it. However, the latency of accessing a random word in external main memory (DRAM) is quite slow compared to processor speed, by two orders of magnitude or more. A computer using a memory system consisting only of DRAM would be intolerably slow, so modern machines instead have a memory hierarchy, where copies of certain parts of the memory space are kept in faster, smaller cache memories. If the most frequently accessed data can be kept in the fastest cache memories, then on average a low access cost can be achieved. The memory hierarchy exploits the fact that typical programs exhibit spatial and temporal locality. This mechanism has been reasonably successful at maintaining the flat memory illusion in serial computers. However, even in serial computers significant performance gains are possible by designing programs using a more realistic memory model. For example, it is worthwhile to use data structures and algorithms that are designed to have high levels of spatial and temporal locality.

Кто у кого списывает?... не понятно
В любом случае пользователи RSDN получают актуальнейший контент в русском изложении


R>

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

R>Кто у кого списывает?... не понятно
R>В любом случае пользователи RSDN получают актуальнейший контент в русском изложении
Блин. Кто опять машиной времени балуется!!