LINUXTALKS.CO
Форум — Tech / Games / Dev  

Замена алгоритма сортировки в sysinit позволила ускорить загрузку FreeBSD

 ,

L


0

1

Стырил с опеннета.

Во FreeBSD принято изменение, меняющее в коде инициализации ядра (sysinit) алгоритм сортировки массивов. Вместо ранее применявшегося алгоритма пузырьковой сортировки в sysinit задействован более эффективный алгоритм сортировки слиянием, что позволило на 2 мс сократить время загрузки ядра в виртуальных машинах Firecracker.
★★★★★★

на 2 мс

Ну это победа, ящитаю!
А вообще, интересно, что там сортировалось в этой бзде, что переписывание сортировки дало какой-то эффект?

Кстати, на небольших размерах, эти всякие йоба-сортировки могут быть менее эффективными, чем тупой алгоритм, работающий за O(n^2).
Например, в библиотечной сортировке в java, когда длина массива (или оставшегося кусочка) меньше некоторого порога, используется сортировка вставками (это, как и пузырёк, алгоритм за n^2)

TheAnonymous    
★★★★★★★★★★★
Linux / Firefox
Tech / Games / Dev