Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Мега-СУБД: указатели, плотная упаковка и строки кеша

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

Массив с бинарным поиском - чуть меньший идиотизм, потому что всё равно отравляет кэш. Допустим, у вас 4-байтовые ключи и строка кэша 64 байта. Первое обращение к массиву вытянет 16 ключей (строку кеша, содержащую "серединный" ключ), из которых 15 будут бесполезны и занимать драгоценное место.

Проблема хорошо известна в алгоритмах внешнего поиска (B-tree и т п), и решения для дисков можно переносить на случай иерархии памяти. Там разные варианты есть. Например, в лоб сделать B-tree с 64-байтовыми страницами, и упаковать его в массив.

Далее, 8 байт на указатель - это непомерное расточительство памяти. Можно побить память на сегменты по 64к, и использовать короткие внутрисегментные указатели. И отказаться от указателей, и использовать вместо них индексы в массивах (или, эквивалентно, большое выравнивание). Первый подход позволяет не хранить "старшие" биты в указателях, а второй - младшие.

Условно, если есть 100 связных структур по 600 узлов одинакового размера - то можно узлы для всех них аллоцировать в одном массиве из 60к элементов, а вместо указателей использовать двухбайтовые индексы в этом массиве. Можно даже gc организовать локальный.

Мне кажется, что такая софтварная сегментация вполне может выстрелить в системах типа редиса. Потому что

а) длинных указателей мало
б) алиасинг под контролем - на большинство живых узлов ровно один указатель
в) системное ПО - можно один раз потрахаться, а потом 100500 раз хипсторам продать
Tags: fp, programming
Subscribe

  • Верифицированный лигаси-фри стек в пару рыл за 20 лет

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

  • Contracts first

    Тут из альтернативной вселенной сообщают, что завтипы говно и не нужны. Вместо этого берете язык с простыми типами и контрактами в стиле Eiffel…

  • Implementing Algebraic Effects in C “Monads for Free in C”

    Тут проскочила ссылка на пейпер. Не радуйтесь, там это лапша из setjmp/long jump, а не rust-style zero cost.

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 8 comments