Пробовал. trie.reserve даёт пару десятков миллисекунд. В коде его не оставил, чтобы поменьше магических констант было. Индексы по сравнению с итераторами или указателями для std::vector также не дают никакого выигрыша. Вся реализация std::vector-а у компилятора "перед глазами", так что для меня очевидно, что разницы быть не должно. RIP-relative addressing тоже не даёт какого-то замедления по сравнению с абсолютными адресами в случае глобального static массива в 32-bit режиме.
Любой open addressing требует сравнение элементов: решение автоматически с 0.9 до 1.7 секунды замедляется, т.к. ещё в две "случайные" локации бегаем - в words и в output (можно сократить до одной доп. локации, если в корзине хранить индексы: можно даже всё в 64 байта уместить при желании struct { uint16_t hashesHigh[8]; uint24 counters[8]; uint24 words[8]; }). Если кажется, что не требует, то тогда зачем probing? Допущение хэш-коллизий автоматически влечёт за собой требование искать и сравнивать элементы вообще всегда. В исходнике есть настройка kEnableOpenAddressing - можно посмотреть, что она включает. Кроме избыточных походов по случайным адресам ещё добавляется цикл.
Больше cash miss, т.к. по 1.63 элемента на корзину (=кэш-линию) уже не получим. b + битовая длина хранимого суффикса хэша должны быть равны 32 (хотя может быть можно и для 31 или 30 бит seed для perfect hash найти), чтобы сравнение суффикса хэша избавляло нас от необходимости сравнивать содержимое элементов. Действительно perfect hash требует b >= 17. Если префикс хэша будет меньше 17, то придётся хранить уже суффиксы хэша в uint32_t, что на Ivy Bridge повлечёт необходимость усложнить код в части сравнения hashesHigh. Это опять же замедление. Параметры найденного решения действительно ограничены сверху и снизу.
Я пробовал это в каком-то виде. Называется path compression. Добавил массив, который "добивал" размер узла до целого количества кэш-линий. Ускорения не было. Для средней длины слова 4.25 это даже интуитивно кажется мне логичным.
На самом деле, id видимых тайлов считаются два раза. Аналитически на ЦПУ и честно — во фрагментном шейдере. Казалось бы, почему их не забрать с фрагментного шейдера? Но все не так просто. Об этом будет вторая статья.
Да. Это невозможно. В статье приведены антинаучные заявления маркетологов. Поверхность, если не получает дополнительную энергию излучением (от Солнца), будет находиться в тепловом равновесии (плюс-минус) с окружающей средой (воздухом), с которой обменивается энергией посредством теплопередачи.
попахивает амнезией )
На самом деле std::list::sort при обмене элементов местами не имеет дело с самими значениями, а изменяет указатели во внутренних структурах. Заставить std::stable_sort делать то же самое вряд ли возможно.
Жаль, что политика управления выделением доп. памяти в алгоритмах не предоставляется. Например, мне не хотелось бы, чтобы память выделялась и освобождалась в цикле, в котором вызвается std::inplace_merge. Также не хватает возможности указать аллокатор.
Можно ли придумать какой-то частичный индекс?
Добавление второй волны как улучшает оценку сложности в среднем случае?
Главное - это плотность. У Вселенной ещё больше масса.
Пробовал.
trie.reserve
даёт пару десятков миллисекунд. В коде его не оставил, чтобы поменьше магических констант было. Индексы по сравнению с итераторами или указателями дляstd::vector
также не дают никакого выигрыша. Вся реализацияstd::vector
-а у компилятора "перед глазами", так что для меня очевидно, что разницы быть не должно. RIP-relative addressing тоже не даёт какого-то замедления по сравнению с абсолютными адресами в случае глобальногоstatic
массива в 32-bit режиме.Любой open addressing требует сравнение элементов: решение автоматически с 0.9 до 1.7 секунды замедляется, т.к. ещё в две "случайные" локации бегаем - в
words
и вoutput
(можно сократить до одной доп. локации, если в корзине хранить индексы: можно даже всё в 64 байта уместить при желанииstruct { uint16_t hashesHigh[8]; uint24 counters[8]; uint24 words[8]; }
). Если кажется, что не требует, то тогда зачем probing? Допущение хэш-коллизий автоматически влечёт за собой требование искать и сравнивать элементы вообще всегда. В исходнике есть настройка kEnableOpenAddressing - можно посмотреть, что она включает. Кроме избыточных походов по случайным адресам ещё добавляется цикл.Больше cash miss, т.к. по 1.63 элемента на корзину (=кэш-линию) уже не получим. b + битовая длина хранимого суффикса хэша должны быть равны 32 (хотя может быть можно и для 31 или 30 бит seed для perfect hash найти), чтобы сравнение суффикса хэша избавляло нас от необходимости сравнивать содержимое элементов. Действительно perfect hash требует b >= 17. Если префикс хэша будет меньше 17, то придётся хранить уже суффиксы хэша в
uint32_t
, что на Ivy Bridge повлечёт необходимость усложнить код в части сравненияhashesHigh
. Это опять же замедление. Параметры найденного решения действительно ограничены сверху и снизу.Код с path compression.
Тоже под руками нет. Насколько я помню на ввод 0.1 на сортировку порядка 0.01 и на вывод такого же порядка цифры
Я пробовал это в каком-то виде. Называется path compression. Добавил массив, который "добивал" размер узла до целого количества кэш-линий. Ускорения не было. Для средней длины слова 4.25 это даже интуитивно кажется мне логичным.
Насколько я помню, в обсуждениях предложения в стандарт упоминались какие-то проблемы на этот счёт. Могу ошибаться.
Как интересно обязательный copy elision "дружит" с variadic functions и
__stdcall
?Будет ли вторая статья?
Thx. Действительно, нет ничего холоднее в космосе четырёх по Кельвину. Только в лабораториях у человеков бывает вещество с температурой ниже.
Да. Это невозможно. В статье приведены антинаучные заявления маркетологов. Поверхность, если не получает дополнительную энергию излучением (от Солнца), будет находиться в тепловом равновесии (плюс-минус) с окружающей средой (воздухом), с которой обменивается энергией посредством теплопередачи.
Из текста неясно как вообще скорость вращения ЧД внешне наблюдается. Какие эффекты у вращения чёрной дыры?
Крионика — это убийство. Разве нет?
Потенциально он переупорядочивает все элементы последовательности. Для n-ного элемента последовательность становится
std::is_partitioned
.Может быть имеется ввиду использование
libstdc++
совместно сicc
?https://wandbox.org/permlink/J3BGcM60Ux83ezxF вектор или дек не работают с такими типами.
Жаль, что политика управления выделением доп. памяти в алгоритмах не предоставляется. Например, мне не хотелось бы, чтобы память выделялась и освобождалась в цикле, в котором вызвается
std::inplace_merge
. Также не хватает возможности указать аллокатор.