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

S>L0054 убивает всю производительность.

А там разве не рекурсия?
(руки не дошли взять полный код, пока справшиваю словами)

Если рекурсия, то вполне нормально по-максимому заинлайнить тело рекурсивного метода.

Или тебе хотелось автоматического преобразования рекурсии в цикл?
В крайнем случае это можно сделать ручками, но при малой фактической вложенности (единицы десятков, те самые 20-30 максимум) смысла обычно нет.

И да, я когда-то более 15 лет назад сравнивал бинарные деревья с N-арными, ну вот 2-4 элемента в узле давали максимум производительности, т.е. увеличение кол-ва элементов в узле ничего не давало. Гораздо больше дал кастомный аллокатор узлов, но вряд ли это поможет в случае дотнета.

Еще на малой арности эффективно работает балансировка дерева.
(Кстате, не увидел у тебя балансировки, но может не весь код смотрел)

Еще, если заменить в твоей реализации _dataX на inplace-массив, то через одну константу арности можно легко менять кол-во элементов в узле, т.е. задешево сравнить сетку реализаций с отличающейся арностью.

Еще из этой области — когда-то сравнивал различные принципы построения хеш-таблиц:
— хеш-таблица в хеш-таблице (т.е. любой конфликт оборачивается в хеш-таблицу следующего подуровня и т.д. рекурсивно, т.е. тоже получается дерево, просто большой арности узлов, и размер подтаблицы не может быть равен размеру родительской таблицы, т.е. это должно быть другое простое число);
— дефолтные реализации (занятие соседних пустых ячеек);
— в хеш-таблице по данному хеш-коду содержится первый элемент и опционально указатель на сортированный список остальных конфликтных элементов.

Последний вариант показал себя самым эффективным для большинства случаев.

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

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

===================
Но в хеш-таблицах есть еще любопытный способ их построения — через подбор коэфициентов хеш-функции.
На пальцах — существует несколько классов хеш-функций, в которых через параметры можно управлять "законом" разброса.

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