Профилирование vtype_dict #33

New Issue

2022-08-17T00:34:55+03:00

lirent commented

2022-08-17 00:34:55 +03:00

(Migrated from dev.lirent.ru)

В данный момент ноды хэш таблиц vtype_dict основаны на красно-черных деревьях, что ведет к увеличению скорости доступа к элементам, при высоком уровне коллизий. Однако, это ведет и к снижению скорости вставки/удаления элементов при высоком уровне коллизий (в случаях, когда не более 2-3 значений приходится на одну ячейку хэша, скорость вставки/удаления падает не столь значительно).

Основное преимущество данного подхода: более эффективные методы поиска наибольших/наименьших значений (что используется, например, при высчитывании хэша vtype_dict).

Это практически не влияет на скорость перехэширования таблиц (в худшую сторону), однако, все же, требует большее количество памяти для одной ноды.

В рамках условно-идеального состояния таблиц (без коллизий), данный тип нод никаким образом не проявляет себя и его использование носит спорный характер.

Требуется рассмотреть возможность

Профилировния vtype_dict, с предоставлением возможности выбора (при помощи флагов компиляции), использовать красно-черные деревья, в качестве базовых нод, или использовать односвязный список типа stack
Отказ от красно-черных деревьев в пользу односвязного списка типа stack

В данный момент ноды хэш таблиц vtype_dict основаны на красно-черных деревьях, что ведет к увеличению скорости доступа к элементам, при высоком уровне коллизий. Однако, это ведет и к снижению скорости вставки/удаления элементов при высоком уровне коллизий (в случаях, когда не более 2-3 значений приходится на одну ячейку хэша, скорость вставки/удаления падает не столь значительно). Основное преимущество данного подхода: более эффективные методы поиска наибольших/наименьших значений (что используется, например, при высчитывании хэша vtype_dict). Это практически не влияет на скорость перехэширования таблиц (в худшую сторону), однако, все же, требует большее количество памяти для одной ноды. В рамках условно-идеального состояния таблиц (без коллизий), данный тип нод никаким образом не проявляет себя и его использование носит спорный характер. Требуется рассмотреть возможность - Профилировния vtype_dict, с предоставлением возможности выбора (при помощи флагов компиляции), использовать красно-черные деревья, в качестве базовых нод, или использовать односвязный список типа stack - Отказ от красно-черных деревьев в пользу односвязного списка типа stack

lirent commented

2022-08-17 22:14:12 +03:00

(Migrated from dev.lirent.ru)

Задача: переделать ноды vtype_dict, основанные на rbtree, на односвязный список, так как это покрывает большее количество опитимизационных кейсов.

lirent commented

2022-08-18 02:29:33 +03:00

(Migrated from dev.lirent.ru)

Выполнено

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: c/libcdsb#33