- Релиз nginx 1.23.0, topin89, 22:47 , 21-Июн-22 (1) +1
- Релиз nginx 1.23.0, Онаним, 23:09 , 21-Июн-22 (5) +1
Быстрая вставка, быстрое удаление элемента - единственное, что могу придумать.Больше ничего в голову не приходит. Ещё есть конечно вариант, когда суммарный размер всех указателей сопоставим с размером L1D хотя бы, а останавливаться при проходе надо максимум посерёдке - но это явно не тот случай.
- Релиз nginx 1.23.0, Аноним, 01:21 , 22-Июн-22 (21)
- Релиз nginx 1.23.0, Онаним, 22:25 , 22-Июн-22 (42)
Что за ...ня, написанная на ...не, простите?
- Релиз nginx 1.23.0, Онаним, 22:26 , 22-Июн-22 (43)
А самое главное - какое эта ^_^ня имеет отношение к nginx?
- Релиз nginx 1.23.0, Онаним, 22:52 , 22-Июн-22 (49)
Я даже тебе объясню, почему вообще мимо тазика: реализация этих примитивов на езычге, где работа с указателями реализована через libastral (или libanal), может быть совершенно неоптимальной.
- Релиз nginx 1.23.0, Онаним, 23:10 , 21-Июн-22 (6) +1
С другой стороны бинарный поиск в отсортированном списке - так себе затея, т.е. это tradeoff. Вот в жизни не поверю, что у них число вставок-удалений превышает число поисков.
- Релиз nginx 1.23.0, topin89, 10:41 , 22-Июн-22 (35)
- Релиз nginx 1.23.0, Онаним, 22:27 , 22-Июн-22 (44)
Вставка в связанный список - это 2 указателя заменить, если по-минимуму. O(1) Вставка в массив указателей - это, простите, сдвинуть N указателей. O(N)
- Релиз nginx 1.23.0, Онаним, 22:29 , 22-Июн-22 (45)
(кроме вырожденного случая вставки в конец массива)
- Релиз nginx 1.23.0, 1, 09:36 , 23-Июн-22 (53)
- Релиз nginx 1.23.0, Онаним, 13:39 , 23-Июн-22 (54)
Вставка в конец массива (или, если быть совсем точным - всегда в одинаково отдалённую от конца массива позицию) - это O(1), не зависит от числа элементов в массиве, поэтому и вырожденный случай.
- Релиз nginx 1.23.0, native76, 23:34 , 21-Июн-22 (12) +1
- Релиз nginx 1.23.0, topin89, 14:52 , 22-Июн-22 (40)
- Релиз nginx 1.23.0, Онаним, 22:34 , 22-Июн-22 (46)
Блоки одинакового размера для содержимого хедеров? Не, конечно это nginx, там всякое может быть. Но не верю.
- Релиз nginx 1.23.0, Аноним, 01:11 , 22-Июн-22 (20) +1
- Релиз nginx 1.23.0, Lucky, 05:23 , 22-Июн-22 (28) +2
- Релиз nginx 1.23.0, 1, 09:11 , 22-Июн-22 (32) +3
- Релиз nginx 1.23.0, Онаним, 22:38 , 22-Июн-22 (47)
Пришёл на ум ещё один вариант, когда связный список эффективнее - это когда его надо часто на запись блокировать между потоками (вставка-удаление). В случае массива указателей придётся блокировать таковой целиком (или извращаться с частичной блокировкой). В случае связного списка блокировать придётся только непосредственно участвующие записи (одну или две, в зависимости односвязный или двусвязный это список).Но это опять не про nginx.
- Релиз nginx 1.23.0, Онаним, 22:42 , 22-Июн-22 (48)
Ну и на вставку в связный список аналогично хорошо RCU ложится, если возможность в соседнем потоке пролистать список в stale state без нового элемента не напрягает. На удаление - на любителя, прочитать удалённую запись обычно не есть гуд.
- Релиз nginx 1.23.0, Гость, 23:17 , 21-Июн-22 (7) +6 [^]
- Релиз nginx 1.23.0, Мохнатый пись, 00:15 , 22-Июн-22 (14) –2
- Релиз nginx 1.23.0, Вы забыли заполнить поле Name, 03:41 , 23-Июн-22 (50)
- Релиз nginx 1.23.0, Онаним, 09:05 , 23-Июн-22 (51)
Тем, кто ещё на этом сидит, ещё не начал phaseout, и не готов платить за поддержку - я бы уже советовал задуматься.
- Релиз nginx 1.23.0, Аноним, 09:13 , 23-Июн-22 (52)
- Релиз nginx 1.23.0, Какаянахренразница, 13:55 , 23-Июн-22 (55)
|