Списко- или вектороподобная структура данных в ядре

список

Естественно.

выделением памяти через kmem_cache

От горшка два вершка, а уже хочет kmem_cache

kmem_cache

Ну а как ещё? Не kmalloc()'ать же на каждое учетверённое слово.

Я понимаю, что тяжеловесно (особенно если учесть, что это список диапазонов секторов к discard'у), поэтому сюда и пришёл.

Не kmalloc()'ать же на каждое учетверённое слово.

(участливо) Нет? А почему нет?

Оверхед там, все дела. Я не знаю, какой именно оверхед у kmalloc, но предполагаю, что он есть.

Оверхед там, все дела

Забота об оверхеде - это прекрасно. Правда, без подсчета количества узлов списка хотя бы на манжетах выглядит злокачественным случаем premature optimization,

Я не знаю, какой именно оверхед у kmalloc

kmalloc - это buddy allocator; kmem_cache нужен для улучшения использования кэша, а не для избежания накладных расходов kmalloc.

Естественно.

В ведре линукса наверняка есть списки. Я так понимаю, ТС'у лучше подсказать готовое.

Да, конечно.

куча.

Списки-то есть, ясное дело. Я умею грепать.

От десяти до десяти тысяч.

А то, что kmem_cache — это slab-аллокатор, совсем не играет? Я всегда считал, что они применяются как раз при выделении хреналиона одинаковых объектов.

И да, паттерн использования таков: постепенно добавлять элементы, потом единовременно всё обработать и очистить список.

до десяти тысяч.

Тогда kmem_cache может быть оправдан. Правда, одновременно возникают сомнения насчет списка - может, тебе лучше будет дерево?

Лол, в masseffect переиграл?

Каковы преимущества дерева перед списком? Мне поиск не нужен, только один раз отсортировать и проитерировать.

Каковы преимущества дерева перед списком?

Время вставки в отсортированный список - O(n), в RB-дерево O(log(n)).

Мне поиск не нужен

Совсем?

Совсем. И мне не нужен отсортированный список — его достаточно отсортировать (т. е. O(n*log(n))) перед итерированием.

Мне поиск не нужен

Совсем?

Совсем

Какая-то нетипичная для ядра задача...

достаточно отсортировать (т. е. O(n*log(n))) перед итерированием.

Тогда ответ очевиден - дерево тебе не нужно.

при чем тут ME?

«Элкоры»

Какая-то нетипичная для ядра задача...

Поддержка discard для reiser4. Надо хранить в течение транзакции список блоков, освобождённых за её время.

Тогда ответ очевиден.

Связный список с выделением памяти через kmalloc или kmem_cache?

От горшка два вершка, а уже хочет kmem_cache

Что там может пойти не так?

Связный список с выделением памяти через kmalloc или kmem_cache?

Подойдет и то, и то. Если элементов в списке ожидается в среднем хотя бы сотня, можно и kmem_cache сделать.

Что там может пойти не так?

YAGNI же.

(удивленно) как это я сразу не догадался

оО, нулёвый и ты тут. Твои познания и советы такие нулёвые, что яб на твоём месте даже не пытался кому-то кукарекать слово «ественно», либо уточнять, что естественно это мирка нулёвого бомжа, а не мира.

нужно добавлять элементы

Список сливает в говно.

нужно сравнительно быстро объединять две таких структуры

Если объединение всключает в себя сортировку, то тоже в говно сливает список. Да и ничего не мешает сделать объекдинение через список массивов.

нужно уметь сортировать элементы — можно при добавлении, можно отдельно после добавления всех элементов

Сортировка списка - тормазной даунизм.

От горшка два вершка, а уже хочет kmem_cache

От горшка два вершка, а уже такой самоувернный и крайне балаболистый.

оО, нулёвый и ты тут. Твои познания и советы такие нулёвые, что яб на твоём месте даже не пытался кому-то кукарекать слово «ественно», либо уточнять, что естественно это мирка нулёвого бомжа, а не мира.

ААА ЦАРЬ МЕНЯ ПОМНИТ, Я ПРИШЕЛ К УСПЕХУ!!11

Речь идёт о коде в ядре. Мне нужна структура данных для хранения массива пар целых чисел (8 или 16 байт на элемент).

А ты не можешь описать чего тебе надо хранить, сколько, для чего, что будет записываться, зачем тебе нужна сортировка, объекденение, что такое «добавлять» и прочее?

Мне приходит в голову разве что связный список с выделением памяти через kmem_cache.

Плохо, ты даже 5% начальных условий не описал, из которых уже что-то «приходит» - а так это не прешло - ты просто выкрикнул слово форфан.

Диапазоны секторов. В треде уже описал.

Ну как можно забыть такого дебилушку? - тут на лоре таких мильён - один краше другого.

Ты хоть поспоришь со мною?

Ты хоть поспоришь со мною?

Спорить? С тобой? Царь, да ты совсем рехнулся. Я скорее с генератором случайных чисел поспорю.

Это без разницы, мне это ниочем не говорит.

Ты опиши как это должно работать. Внятного описания за 2минуты гуглёжки я не нашел.

Откуда берутся твои диапазоны секторов, что ты потом с ними делаешь? Т.е. внятно: вот у меня происходит то-то - это мне гинерит диапазоны - я их собираю. Собираю я эти диапазоны для того-то.

Ну тыж пытался? Только вот обоссался, а теперь чё не хочешь - тыж так яро срался? Ищешь отговорки? С гпсч ты споришь постоянно(пивет толксы, всякие емулеки, дауны-студенты и прочий сброд из которого состоит аудитория лора на ~100%), в чем проблема?

Давай, давай - вякнул - отвечай.

Ну тыж пытался?

Да. И сделал соответствующий вывод.

отвечай

А то что - уважать не будешь? Ой бида пичаль.

обоссался
срался
вякнул

Рот помой с мылом.

Да. И сделал соответствующий вывод.

И какой-же? Как может делать вывод какой-то бомж, который везде обосрался? Где ты там последний раз обосрался? на руст-бенчарках? Или это был не ты, хотя вроде ты.

Меня это так веселит, когда нулёвое ничтожество пытается из себя что-то корчить.

А то что - уважать не будешь? Ой бида пичаль.

Нет, суть в том, бесполезны вы для меня, а не наоборот. Яж всё надеюсь, что вы выростите из детсадовского балабольства и начнёте хоть минималистично пытаться аргументировать свой выхлоп, для начала.

Вся твоя пародия на сознание состоит из ничтожных говношаблонов. Сказали обезъянке: «связный список» - дак теперь он везде повторяет, а когда его вгоняют в говно - он «я не я и шкура не моя - я с тобою не буду спорить, ко-ко-ко - мне это не интересно» и прочее.

Тыж не зря не стал спорить со мною, ибо всем ясно, что и тебя и твои списки я с говном смешаю, но суть в том, что ты как и с «пи-бенчем» скажешь - да мне интересно, ко-ко-ко; я не виновен.

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

Рот помой с мылом.

С чего? Какбэ констация факта твоего обсирательства не перемещает кучу под тобою ко мне. Но делай вид, что это нетак.

бесполезны вы для меня

Да ладно? Кому бы ты писал эти свои стены текста, если бы нас не было. Вот ты нам бесполезен, это да.

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

Вменяемое описании задачи в треде. Вменяемое решение задачи в треде.

А ничтожество типа тебя кукарекает про списки, обход которых стоит в десятки-сотни-тысячи раз дороже обхода массива, но нулёвый питух кроме O(n) ничего же не знает. Коненчо своими кривыми ручёнками ты отсилы выжмешь десяток раз, но какбэ это вина не массива, а твоих кривых ручёнок.

Ну дак я тебе же пишу, чтобы ты перестал быть питухом, а так мне написание стены текста ничего не даёт. Ну разве скилл обоссывания питухов.

Моя польза возможно будет лишь в будущем, когда я буду обитать не среди безмозглых приматов, а взаимополезных людей. Именно мыслящих и думающих людей, а не макак, которые скандируют мифы и легенды из обосанных недокнижёнок.

Не kmalloc()'ать же на каждое учетверённое слово.

Можно выделять память не на каждое слово, а на каждую тысячу. Чуть-чуть большего расхода памяти никто не заметит (всё равно она будет потом освобождаться), зато скорость заметно возрастёт.

Вот смотри - вместо того, чтобы взять и коллективно решить проблему

«Проблема» была решена до твоего появления в топике.

Моя польза возможно будет лишь в будущем

...когда ты станешь удобрением.

«Проблема» была решена до твоего появления в топике.

А ну да, спасибо поржал. Гениальное решение - заюзать говно и сказать, что решено.

...когда ты станешь удобрением.

Ну дак кто обоссался ты или я? Кто слился, кто анскильнео ничтожество, кто ссытся даже поспорить со мною? Всяко не ты.

Да и вообще нахрен вы такие? Я пытаюсь с вами говорить, чего-то объяснить. Все им не нравится, хотя жить в окияне говна и кукарекатЬ ,что всё решено - это же так руто.

tailgunner и царь нашли друг друга. Очень трогательно

По теме:

Почему не держать это в простом массиве?

нужно добавлять элементы
нужно сравнительно быстро объединять две таких структуры

krealloc() + memcpy()

нужно уметь сортировать элементы — можно при добавлении, можно отдельно после добавления всех элементов

sort()

Что интересно, текущий мейнтейнер reiser4 (который Эдуард Шишкин) сказал, что стоит предпочесть rb-дерево, т. к. асимптотика у него даже лучше, чем у связного списка + сортировки за O(n*log(n)). Я опять в раздумьях.

krealloc() + memcpy()

Хм. Ты царь, который наконец принял таблетки, или его брат по разуму?

rb-дерево, т. к. асимптотика у него даже лучше, чем у связного списка + сортировки за O(n*log(n))

Этого я не понимаю.

Я опять в раздумьях.

Абстрагируй операции над списком блоков так, чтобы нижележащую структуру данных можно было менять, и делай пока более простой вариант. Почему-то мне кажется, что вопрос «список или дерево» на этом этапе неважен %)

Этого я не понимаю.

Я уже и сам не понимаю. Сейчас пересчитал — получается, что списки быстрее при количестве элементов, большем ~150.

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

• Для списков:
  • Заполнение: 2N
  • Слияние: 1
  • Сортировка: 2N*log(2N)
  Итого 2N+2N*log(2N)
• Для RB-деревьев:
  • Заполнение: 2*(log(1)+log(2)+...+log(N-1)) = 2*log((N-1)!)
  • Слияние: log(N)+log(N+1)+...+log(2N-1) = log((2N-1)!/(N-1)!)
  • Сортировка: 1
  Итого 2log((N-1)!) + log((2N-1)!/(N-1)!) = log((2N-1)!(N-1)!)

Абстрагируй операции над списком блоков

Естественно, я уже. Мне не хочется дважды реализовывать эти интерфейсы, потому что времени на всю эту содомию у меня ровно майские праздники (а потом ЕГЭ).

Слияние: log(N)+log(N+1)+...+log(2N-1) = log((2N-1)!/(N-1)!)

Ты выполняешь слияние последовательной вставкой элементов одного дерева в другое? Думаю, есть специальный алгоритм слияния двух деревьев. Гугл говорит http://stackoverflow.com/questions/3176863/concatenating-red-black-trees/3224...

Мне не хочется дважды реализовывать эти интерфейсы

Думаю, тебе и не придется %) Делай на списках.

Уже читал. Запилить fingers в ядре? Спасибо, как-нибудь потом :)

Делай на списках.

Ок. Выбрано как рабочая гипотеза...

Запилить fingers в ядре?

Спросить Шишкина, не это ли он имел в виду.