Улучшение реализации моего redblack дерева

Question

Я написал реализацию rb-дерева. Узлы выделяются с помощью malloc. Это хорошая идея выделить большую таблицу в начале и использовать это пространство для распределения узлов и удвоения размера каждый раз, когда таблица переполняется. Это сделало бы операции вставки несколько более быстрыми, предполагая, что время для выделения является значительным, о чем я не уверен.

Answer 1

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

Некоторые общие мысли/комментарии:

• отведение один большой блок (и рост его по мере необходимости), как правило, используют меньше памяти в целом. Обычный распределитель общего назначения (например, malloc/free в C) имеет накладные расходы при каждом распределении. Так, например, небольшой запрос на распределение в 100 байт может привести к использованию 128 байтов.
• В системе с ограниченной памятью с большим количеством фрагментации памяти может оказаться невозможным выделить большой блок памяти и нарезать его, тогда как несколько небольших распределений могут по-прежнему преуспеть.
• Хотя выделение большого блока уменьшает конкуренцию для синхронизации на уровне распределителя (например, в malloc), по-прежнему необходимо обеспечить собственную синхронизацию при захвате узла из вашего собственного управляемого списка/блока (при условии, что многопоточная система). Но тогда, вероятно, должна быть какая-то синхронизация, связанная со вставкой самого узла, поэтому она может обрабатываться в той же самой операции.

В конечном счете, вам нужно будет протестировать его и измерить разницу. Одна простая вещь, которую вы могли бы сделать, это просто написать простой тест «отбрасывания», который выделяет количество узлов, которые вы ожидаете обрабатывать, и просто время, которое требуется (и, возможно, время их освобождения). Это может дать вам приблизительную оценку затрат на размещение.