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

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

Таким лёгким манёвром мы сделали так, чтобы можно было определять неконфликтующие роуты /user/:id и /user/me. Правда, не совсем понимаю, почему кто-то умудряется это в фичи приписывать - штука так-то дефолтная.

Ещё я потом между делом добавил greedy wildcards, в стандартном mux подглядел, и заменил ими костыльные path catcher'ы - аж от души отлегло.

Но вот незадача: тут-то уж точно хэшмапы не вкорячишь. Ну, то есть, можно было бы, но это было бы крайне неудобно из-за того, что при инсерте я довольно часто "ломаю" строки напополам и подменяю ноды. Приходится держать наследников всё так же в массиве. А это проблема - вполне себе может быть кейс, когда сервис насчитывает в себе 500-700 роутов. А с деревом штука такая, что чем меньше ключи похожи, тем ширше его пидорасит. Очень неприятно линейно перебирать пару сотен строк, знаете ли. Даже учитывая, что строки сами по себе не сильно-то на сравнение приятные:)

Поленившись ещё месяца 2, наконец допёр до нормальных бенчмарков (не в слепую же проблему решать?). Ситуацию спасает всеми излюбленный бинарный поиск. Удивительно просто оказалось сделать вставку упорядоченной - один цикл while key < predecessor.value и slices.Insert (кстати, невероятно полезный пакет). Немного сильнее попотеть пришлось над поиском - slices.BinarySearchFunc сгладил worst-case, но на более лайтовых кейсах всё-таки оверхеда прибавил. Нагло спиздил Вырезал с мясом Заинлайнил себе slices.BinarySearch, и получил очень приятные числа практически по всем бенчам. В сумме, где-то в 2-4 раза шустрее стало - особенно прирост был, очевидно, с "широкими" деревьями - где у одного узла очень много наследников (и, соответственно, каждого перебрать надо). Со 128 штуками, вместо 128 линейных сравнений, мы теперь делаем только 7 - чистая вин-вин ситуация. На удивление, "глубокие" деревья со 128 узлами вглубь тоже прирост показали.

Кстати, в slices.BinarySearch переполнения избежали более прикольным способом, чем в джабе - int(uint(a+b) >> 1). Что значит, если переполнение и случится - старший бит один хуй падёт пред побитовым сдвигом вправо:)