LINUX.ORG.RU

Оцените идею (unordered_map)

 ,


0

1

Создается класс, реализующий map<double,X> и unordered_map<X,X>, который состоит из фиксированной части и массива «записей». Массив может менять свой размер, фиксированная часть - нет. Этот класс реализует объект javascript если быть совсем точным. Зачем - ну допустим потом объясню.

map реализовано через skip-list, это по сути double-linked list, но со ссылками для быстрого проскока значений с шагом 2,4,8,...

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

пусть N=hash%Nbuckets, K=hash/Nbuckets. Тогда для каждой корзины можно создать свой скип-лист, где ключем будет K. это позволит иметь логарифмическую сложность даже если одна корзина перегружена.

вторая идея: а пусть «неупорядоченный список» вообще весь будет реализован отдельным скиплистом, как и упорядоченный. Но в него будет не один вход как в упорядоченный, а Nbuckets входов. Ключом в обоих списках является double, но для unordered - это будет double((2^51-1)&((hash<<51-5)^hash)) и Nbuckets=32.

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

Хороша ли идея на первый взгляд?

Заранее говорю, что задачи сделать збс как в v8 не стоит. Это очень специфический компилятор JS, задача которого быстро прототипировать код, на лету потыкать палкой что отвалилось. Если будет не очень но не совсем ужас-ужас, то вроде как и не ужас.

Звучит как боль с гиганстским оверхедом. Если все это еще и будет ворочать частомодифицируемыми короткоживущими постоянно разбалансированными скиплистами с n меньше полсотни, то удачи тебе выиграть у массива с реаллоком. =)

Зато если напишешь параллельный скиплист с фоновой балансировкой, то браузер с твоим движком сможет жрать весь 32-ядерный проц вместо одного ядра. =D

t184256 ★★★★★ ()
Последнее исправление: t184256 (всего исправлений: 2)
Ответ на: комментарий от t184256

я поприкидывал, вроде как ситуации когда скиплисты будут совсем уж разбалансированы нужно создавать руками, делая много delete и вставок. ребалансировка там очень простая, O(n) и при этом

а)90% случаев она требуется один раз для однотипных объектов на всех(потому что прототип кэшируется)

б)там где идёт постоянное перепихивание, скорее всего объект будет из нескольких полей.

в)inline cache и hidden class делаются довольно просто за всего 1 переменную в каждом объекте, и 2 переменные*8байт в окрестностях кода откуда будут обращаться.

salozar ()

Хороша ли идея на первый взгляд?

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

AKonia ★★ ()
Ответ на: комментарий от salozar

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

AKonia ★★ ()

Не в полной мере понял, что за структура данных планируется, но почему не использовать хотя бы красно-чёрные деревья вместо «скип-лист»?

Waterlaz ★★★★★ ()

Псевдокод рулит для начала, причем в котором хороший дизайн API как правило fluent.

anonymous ()

map реализовано через skip-list, это по сути double-linked list, но со ссылками для быстрого проскока значений с шагом 2,4,8,…

Сверх-костыльная реализация бинарного дерева поиска. Интересен вопрос перебалансировки при изменении

anonymous ()
Ответ на: комментарий от anonymous

Сверх-костыльная реализация бинарного дерева поиска

Я не уверен что до конца понимаю что ТС собрался делать, но похоже на одну из распространённых реализаций in-place hash table collision resolution algo. И тогда к поиску в дереве это никакого отношения не имеет.

bugfixer ★★ ()
Последнее исправление: bugfixer (всего исправлений: 1)
Ответ на: комментарий от bugfixer

Я не уверен что до конца понимаю что ТС собрался делать

И мне тоже кажется, что надо смотреть в сторону b-деревьев. Если размеры соответствующе большие. Иначе даже линейный поиск в несортированном, или бинарный в сортированном порвут, как кошка солнечный зайчик.

anonymous ()
Ответ на: комментарий от bugfixer

у объекта числовые свойства выводятся упорядоченно, они приводимы к double. дабы не писать код дважды, можно оставить от хеша 51 бит и хранить его как double.

salozar ()
Ответ на: комментарий от bugfixer

я нашел «Separate chaining with binary search tree hashing» как самое похожее на реализацию.

в каждой корзине оказывается отдельный skip-list, и при большом количестве коллизий поиск внутри отдельной корзины не деградирует до O(n) а лишь до O(log(n))

skip-list выбран, потому что его ребалансировка делается за 15 строчек ибо это всегда отсортированный список и надо лишь создать заново ссылки для пропуска элементов. после ребалансировки поиск и удаление - аналогично простые операции сложности O(log(n))

после оптимизации, а она будет проводиться для большинства объектов один раз после создания экземпляра через

function Foo() {}
new Foo(...)
а потом тупо повторяться по шаблону до создания класса. в самом экземпляре хранится признак того, что после оптимизации не изменялось положение элементов, если это так, то элементы образуют упорядоченный вектор, а не список и можно применять бинарный поиск.

salozar ()
Ответ на: комментарий от salozar

у объекта числовые свойства выводятся упорядоченно, они приводимы к double

Как с дребезгом в младших битах бороться будем?

bugfixer ★★ ()
Ответ на: комментарий от bugfixer

так упорядоченные - int32 и double, откуда там дребезг возьмётся? int32 всегда можно привести к дублю без потерь.

с неупорядоченными аналогично - только битов 51, младшие 5 закидываем в старшие биты(47...51), биты 5...51 сдвигаем вниз на 5. откуда тут дребезгу взяться.

salozar ()
Ответ на: комментарий от salozar

так упорядоченные - int32 и double, откуда там дребезг возьмётся?

Святая простота. Хотя бы на за/выгрузке в/из FPU.

int32 всегда можно привести к дублю без потерь.

Дык, и делайте int32 ключом.

bugfixer ★★ ()
Ответ на: комментарий от bugfixer

Хотя бы на за/выгрузке в/из FPU.

может у вас проц бракованный если он в зависимости от фазы луны два double по разному сравнивает.

salozar ()
Ответ на: комментарий от bugfixer

поменяйте всё таки процессор или не разгоняйте его так. у нормальных людей результат movsd+comisd для одних и тех же исходных значений не меняется.

salozar ()
Ответ на: комментарий от salozar

Вы отдаёте себе отчет что FPU 80 битный а double это 64 бита? В общем случае результаты будут разниться от уровня оптимизации (от того произошла выгрузка из регистра FPU в память или нет). Как я сказал - удачи. И хорошо если оно не в проде рванёт…

bugfixer ★★ ()
Ответ на: комментарий от bugfixer

я вас сейчас удивлю, но мантисса хранится с 3мя лишними битами. И если у вас целое уместилось в мантиссу в памяти, то ничего нового не случится в fpu. тем более если единственная операция, которая производится там это сравнение.

ах да. и не fpu а sse2 на x86-64, где даже этих битов лишних нет.

salozar ()
Ответ на: комментарий от salozar

И если у вас целое уместилось в мантиссу в памяти, то ничего нового не случится в fpu.

Хорошо хорошо, не нервничайте Вы так. Возможно оно у Вас даже и заработает. На Вашем железе, с текущим компилятором. Но я не знаю какая часть IEEE гарантирует эквивалентность результатов сравнения int32 и double(int32). Как по мне так это хорошая такая мина замедленного действия.

bugfixer ★★ ()

не нравится unordered смотри на flat_hash_map или dense_hash_map или куча других реализаций

anonymous2 ★★★★★ ()
Ответ на: комментарий от salozar

Ты совершаешь большой программистский грех предполагая, какие инструкции сгенерирует компилятор.

Даже в самом лучшем случае, если генерация FP-ключа у тебя локализована в одном месте исходника в специальной функции, никто не запрещает компилятору заинлайнить некоторые из вызовов. И, инлайня, воспользоваться знанием о параметрах и заменить static_cast<double>(...) на подстановку вычисленного им результата. Ты готов поручиться, что вычисленное компилятором совпадёт с вычисленным в рантайме? Даже на одном и том же процессоре, компилятор и результирующий бинарник могут собираться под разные архитектуры и, соответственно, преобразование может совершиться разными методами.

Я уже не вспоминаю об оптимизации UB. Условно, если автор компилятора считает, что результат (double)x == (double)x не определён, и компилятор видит, что контейнер никогда не обходится итератором, он имеет право выкинуть операцию добавления в мапу, если сгенерированный ключ нигде в другом месте не сохраняется.

khrundel ★★★ ()
Ответ на: комментарий от khrundel

автор компилятора считает, что результат (double)x == (double)x не определён

gcc так не считает, иначе бы он unordered compare использовал.

salozar ()
Ответ на: комментарий от salozar

gcc так не считает, иначе бы он unordered compare использовал.

Так совместимость со старым кодом, сишечка писалась когда IEEE-754 не было. Но в общем это неважно, сейчас оно использует ordered, а завтра возьмёт и станет использовать unordered, а может продолжит использовать ordered, но при этом оптимизатор будет считать, что (double)x == (double)x необязательно == true. В этом прелесть плюсов. Вон, известный хак из Quake 3 для вычисления pow(x, -1/2), когда адрес флоата приводился к указателю на int и дальше шла битовая магия, он на современных компиляторах не работает, потому что компилятор знает, приведение в другой тип есть UB, а так как программист должен UB избегать, а язык для случая UB не требует никаких гарантий, значит зависимость результата от битовых операций просто показалась, значит битовые операции на результат не влияют и их можно оптимизировать нафиг.

khrundel ★★★ ()
Ответ на: комментарий от khrundel

УМВР,ЧЯДНТ?

#include <math.h>
float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;
  i  = 0x5f3759df - ( i >> 1 );
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) );

  return y;
}
gcc 11.2
Q_rsqrt(float):
        movss   DWORD PTR [rsp-4], xmm0
        mulss   xmm0, DWORD PTR .LC0[rip]
        mov     rdx, QWORD PTR [rsp-4]
        mov     eax, 1597463007
        movss   xmm1, DWORD PTR .LC1[rip]
        sar     rdx
        sub     eax, edx
        movd    xmm2, eax
        mulss   xmm0, xmm2
        mulss   xmm0, xmm2
        subss   xmm1, xmm0
        mulss   xmm1, xmm2
        movaps  xmm0, xmm1
        ret
.LC0:
        .long   1056964608
.LC1:
        .long   1069547520
шланг13
.LCPI0_0:
        .long   0xbf000000                      # float -0.5
.LCPI0_1:
        .long   0x3fc00000                      # float 1.5
Q_rsqrt(float):                            # @Q_rsqrt(float)
        movd    eax, xmm0
        mulss   xmm0, dword ptr [rip + .LCPI0_0]
        shr     eax
        mov     ecx, 1597463007
        sub     ecx, eax
        movd    xmm1, ecx
        mulss   xmm0, xmm1
        mulss   xmm0, xmm1
        addss   xmm0, dword ptr [rip + .LCPI0_1]
        mulss   xmm0, xmm1
        ret

salozar ()
Ответ на: комментарий от salozar

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

salozar ()
Ответ на: комментарий от salozar

Всё делаешь не так.

Вот прямо сейчас, ты показываешь выхлоп компилятора и на основании этого делаешь вывод о корректности кода.

khrundel ★★★ ()

Оцените идею (unordered_map)

Шутка

Она БЕСЦЕННА!
anonymous ()
Ограничение на отправку комментариев: только для зарегистрированных пользователей