LINUX.ORG.RU

[C] Связные списки: реализация glib VS реализация linux kernel


0

2

Интересуют преимущества и недостатки этих двух подходов к реализации связных списков.

glib:

struct GList {
  gpointer data;
  GList *next;
  GList *prev;
};

next и prev указывают на такой же GList

linux:

struct list_head{
	struct list_head *next;
	struct list_head *prev;
};

struct my_cool_list{
	struct list_head list; /* kernel's list structure */
	int my_cool_data;
	void* my_cool_void;
};

То, что вижу я:

1. Реализация в linux требует на sizeof(void *)*N байт меньше, чем реализация в glib, где N - количество элементов в списке.

Why so?

glib = N * { sizeof(next_ptr) + sizeof(prev_ptr) + sizeof(data_ptr) + sizeof(data_struct) }

linux = N * { sizeof(data_struct) + sizeof(next_ptr) + sizeof(prev_ptr) }

То есть, нет N штук data_ptr.

2. Мне кажется, модель списков в glib более интуитивно понятная.

Плюс, в linux list_head структура сама определяет, в каких списках она может хранится. Если я захочу добавить возможность вносить структуру в список, у меня есть 2 варианта:

а) изменить код структуры и добавить туда еще один list_head;

б) написать структуру-обертку и использовать уже ее.

То есть, код получается зависимым от того, что сделал разработчик. В linux такое можно легко использовать, поскольку сорцы открыты, либо закрыты полностью (есть только unmodifiable headers).

Опять же, неудобно каждый раз писать структуру обертку

struct my_struct {
  int a;
  struct list_head list1;
};

struct my_struct_add {
  struct my_struct datal
  struct list_head list2;
};

для добавления возможности вставлять структуру в списки.

Гораздо проще в данном плане использовать модель GLib, где _любой_ объект может быть добавлен в список.

3. Реализация list_head оперирует сдвигом для определения указателя на структуру по указателю на list_head.

void *mystruct_ptr = mylist_ptr - &(((struct mystruct *)0)->mylist_head);

Насколько это портабельно между различными компиляторами?

Тема интересная, посему - lets discuss begin!

★★

> Насколько это портабельно между различными компиляторами?

Настолько же, насколько портабельно выравнивание структур.

Deleted ()

>Тема интересная

Да, мне интересно нафига мутить то что давно есть в C++?

_________

//wfrr

anonymous ()

Че та какие то очень тонкие тонкости. В приведенных случаях хранятся разные наборы данных (какой то gpointer vs int и void*). Что лучше зависит от задачи. Разный порядок следования служебных указателей и пользовательских данных - если не делать каких от откровенных глупостей с кастомизацией то это вообще пофик во всех смыслах. И чего?

AIv ★★★★★ ()

очевидно что в linux_kernel списках можно обойтись вообще без обращений к куче например цепочка сех фреймов в винде в стеке каждой функции выделяеися структурка хранящая контекст и эти структурки связываются в интузивный список очень быстро коспическая скорость потом можно взать указатель на head и пробежатся по всем сех фреймам распооложенным в стека в каждой функции свой а теперь представьтн GLIB смписок динамическое выделение узла при входе в каждую функцию это просто ужас как медленно

anonymous ()
Ответ на: комментарий от tailgunner

Почему оно абсолютно портабельно?

Представь, что я запишу в файл

write(myfd, mystruct_ptr, sizeof(struct mystruct));

на, например, x86, а прочту записанное где-нибудь на powerpc

read(myfd, &mystruct, sizeof(struct mystruct));

Скорее всего, я прочту неправильно (зависит, понятно, от архитектур). Следовательно, выравнивание структур не портабельно.

Так почему же ты утверждаешь, что оно абсолютно портабельно?

bk_ ★★ ()
Ответ на: комментарий от tailgunner

И как по-русски нормально перевести intrusive/nonintrusive, а то по смыслу понятно, но «вмешивающийся/невмешивающийся» не звучит.

bk_ ★★ ()
Ответ на: комментарий от elverion

Там все красиво описано, но касается только С++. Беседа же идет про С.

bk_ ★★ ()
Ответ на: комментарий от bk_

> Представь, что я запишу в файл

Структуру с указателями в файл? Прикольно.

Так почему же ты утверждаешь, что оно абсолютно портабельно?

Напомню, речь о портабельности языковой конструкции (ты сам сказал «портабельность между компиляторами»), а не файлов данных (которые, если писать их в твоем стиле, непортабельны по определению, и не только из-за выравнивания).

tailgunner ★★★★★ ()
Ответ на: комментарий от tailgunner

Все верно, ты прав - мне просто было интересно, что ты скажешь на это :)

То есть, _любой компилятор языка С_ гарантирует, что вышеописанная конструкция «определения сдвига адреса члена структуры» будет всегда работать?

Если можно, дай линк, пожалуйста на пункт в стандарте, а то я пока не могу найти это.

bk_ ★★ ()

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

anonymous ()
Ответ на: комментарий от bk_

Фигня. Я также могу сделать GList на объектах в стеке.

То, что ты описал - не критерий для сравнения.

это как это нука покажи в итоге ты родиш интузивный список

anonymous ()

bk_, разница в том что, в одном случае(glib) в элементе списка хранятся сами данные, а в другом(linux) - указатель на данные, я правильно понял?

Если так, то в glib дважды вызывается malloc - один раз для элемента списка, другой - для самих данных соответственно, что на дефрагментации кучи может сказываться как положительно, так и отрицательно. Но вызов malloc сам по себе потребует времени.

Но, вот если размер данных большой и использовать случай «linux» получится же, что через стек такие элементы передавать нельзя.

backbone ★★★★★ ()
Ответ на: комментарий от anonymous

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

Будет больше на одну операцию суммирования указателя. Это много для современного компьютера даже при условии большого количества листов?

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

А разве в GList я такого сделать не могу?

bk_ ★★ ()
Ответ на: комментарий от bk_

> То есть, _любой компилятор языка С_ гарантирует, что вышеописанная конструкция «определения сдвига адреса члена структуры» будет всегда работать?

Глупо говорить о «любом» - вдруг где-то баг именно на такую конструкцию. Все Си-компиляторы, которыми я пользовался, это гарантировали (а если ты снова меня проверяешь, распиши-ка все типы).

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

Будет больше на одну операцию суммирования указателя.

Сказано же - на одну операцию доступа к памяти.

tailgunner ★★★★★ ()
Ответ на: комментарий от backbone

в одном случае(glib) в элементе списка хранятся сами данные, а в другом(linux) - указатель на данные, я правильно понял?

Если я тебя понял, то нет - ты понял неправильно :)

Но на счет того, что в GList для добавления элемента нужно 2 malloc (сам GList + моя структура), а для linux list_head только 1 malloc (только моя структура) - это верно.

использовать случай «linux» получится же, что через стек такие элементы передавать нельзя.

Если видимость объектов в списке ограничена иерархией стека с фрейма, в котором они создались, то, по-моему, ты не прав:

// Стек в GList

GList *list = NULL;

struct mystruct s1, s2, s3;
g_list_append(list, &s1);
g_list_append(list, &s2);
g_list_append(list, &s3);

// Передача списка с элементами в стеке.
some_func(list);

g_list_free(list);


//======

// Стек в list_head

struct mystruct {
int data1;
char data2;

struct list_head list;
};

struct mystruct s1, s2, s3;
INIT_LIST(&s1.list);
push_list(&s1.list, &s2.list);

// Аналогично передаю список по стеку вниз.
fn(&s1);

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

bk_ ★★ ()
Ответ на: комментарий от bk_

>> В случае с указателем тебе нужно дав доступа к памяти, чтобы добраться до своей структуры, в случае встраивания узла листа в свою структуру - только один.

Будет больше на одну операцию суммирования указателя. Это много для современного компьютера даже при условии большого количества листов?

Блин, ну ведь у тебя наверно в компе два ядра как минимум, а ты все еще вопросы задаешь, как погромизд под ДОС. Задай себе пару вопросов:

1) какой размер строки кэша в твоем процессоре

2) какова разница во времени доступа к данным в кэше и в оперативной памяти?

3) как времена из пункта 2 соотносятся с временем добавления константы к содержимому регистра процессора

Если вопросы не отпадут, то тебе лучше сменить область делятельности прямо сейчас

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

А разве в GList я такого сделать не могу?

Можешь, но: а) см. выше; б) зачем вырезать гланды через задний проход?

anonymous ()
Ответ на: комментарий от tailgunner

Все Си-компиляторы, которыми я пользовался

Вопрос без выпендривания с моей стороны, чисто для интереса - какими компиляторами ты пользовался?

Сказано же - на одну операцию доступа к памяти.

Ты имеешь в виду, что в GList я должен:

1. Прочесть данные по указателю в glist и найти значение поля 'data'.

2. Прочесть данные по указателю data и получить мою структуру.

А в list_head (если я имею 'struct mystruct s1;') только

1. Прочесть данные по указателю next/prev и получить структуру.

Я верно понял?

Если да, то тогда при наличии указателя на структуру stryct mystruct *s1, а не значения, я должен все равно сделать 2 чтения:

1. Прочесть данные сруктуры.

2. Прочесть данные по указателю next.

bk_ ★★ ()
Ответ на: комментарий от bk_

вот смотри сех фрейм добавляется в интрузивный список (такой код вевчале каждой функции обрабатывающей исклчения)

push        offset _except_handler3 (401B0Ah) пихаем процедуру хендлер
mov         eax,dword ptr fs:[00000000h] читаем указатель на головной фрейм
push        eax  пихаем указатель на следующий фрейм (только что бывший головным)
mov         dword ptr fs:[0],esp записываем в голову списка новый фрейм
вот вся мощь интузивного списка изобрази это на GList а мы посмотрим

anonymous ()
Ответ на: комментарий от anonymous

См. мой коммент.

Еще раз вопрос: я выиграю в количестве обращений к памяти только при использовании «значения» структуры, а не указателя на нее (пример в комменте выше)?

максимально эффективно пользоваться кэшированием в разнообразных уровнях кэшей.

Хотелось бы более конкретных примеров по удобству list_head для кэширования в разнообразных уровнях кэшей.

bk_ ★★ ()
Ответ на: комментарий от bk_

> Ты ничего не понял. Прочти еще раз 1ый пост - я там внятно описал методику хранения в обоих случаях.

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

Давай посмотрим linux реализацию для хранения gpointer. Разница ТОЛЬКО в порядке следования информации относящийся непосредственно к списку/пользовательской информации.

linux подход требует сдвигов для доступа к польз данным. Первый подход ограничивает размер данных хранящихся непосредственно в ячейке списка размером gpointer, если данных больше приходится хранить данные отдельно (если напр в куче оно понятно медленней и геморней).

Какой подход лучше - зависит от задачи. И чего?

AIv ★★★★★ ()

тема какаято странная

это не две реализации - это просто две разные веши

у глибов - обычьная рунтаймовая
а вторая - компилиться на ПРЕПРОЦЕССОРОМ

ты могеш очень легко из 2ой сделать 1вую
а вот наоборот - никак

и во второй - ты могеш одну структуру сделать содержащию вхождения во многие списки
в первой тоже можно - но во 2ой это делаеться еще пропроцессором - когда как вторая только рунтайм - тоесть во время выполнения

ae1234 ★★ ()
Ответ на: комментарий от bk_

Спасибо за подробный пример!
По поводу стека я неверно выразился. Если нужно передать информацию только об одном элементе, то в случае glib можно передать сам элемент, т.к. он всего 12-32 байта, а в случае linux нужно передать указатель на элемент, после чего потребуется доступ по указателю для доступа к prev, next.

backbone ★★★★★ ()
Ответ на: комментарий от bk_

Еще раз вопрос: я выиграю в количестве обращений к памяти только при использовании «значения» структуры, а не указателя на нее (пример в комменте выше)?

Ты глисты-то свои без указателя собираешься находить что ли?

Хотелось бы более конкретных примеров по удобству list_head для кэширования в разнообразных уровнях кэшей.

Читай книжки, они рулез, вместо того, чтобы на лоре штаны просиживать

anonymous ()
Ответ на: комментарий от anonymous

Ты глисты-то свои без указателя собираешься находить что ли?

А поцчему ви отвечаете вопросом на вопрос?

В glist то я всегда в два присеста прочту - нет выбора, а в list_head в 1 при использовании самой структуры и в 2 при использовании указателя на нее.

_Еще раз_ мой вопрос (немного видоизменю): в каких случаях целесообразно применять list_head в отличие от nonintrusive-списков?

bk_ ★★ ()
Ответ на: комментарий от bk_

> какими компиляторами ты пользовался?

Какие-то безымянные на ЕС ЭВМ, Borland начиная с Turbo, Watcom, Ultra, GCC.

Я верно понял?

Да.

при наличии указателя на структуру stryct mystruct *s1, а не значения, я должен все равно сделать 2 чтения:

1. Прочесть данные сруктуры.

2. Прочесть данные по указателю next.

Для перехода к следующему элементу - да. Но речь шла об обращении к данным структуры, в которую встроен узел списка.

tailgunner ★★★★★ ()
Ответ на: комментарий от bk_

>>> Ты глисты-то свои без указателя собираешься находить что ли?

А поцчему ви отвечаете вопросом на вопрос?

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

У тебя есть два указателя на элемент списка - один на глист, второй на linux kernel list. Для того чтобы добраться до данных в первом случае тебе нужно дереференсить указатели два раза, во втором случае - один. При этом в первом случае ты в общем случае не имеешь контроля над тем, как будут располагаться в памяти глист и собственно данные, во втором случае они будут рядом, и, возможно, уже будут в кэше, так как размер строки кэша больше размера двух указателей.

Теперь задай себе три вопроса, приведенные выше, определись, что делать с областью деятельности

anonymous ()
Ответ на: комментарий от bk_

не щито - а речь о том что одно делаеться при компиляции - второе делаеться уже работой программы

и из линуксового можно сделать глиб вариант - а наоборот нет
и используют так - как нужно в конкретный момент времени

ae1234 ★★ ()
Ответ на: комментарий от anonymous

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

О, анон, на _этом_ я прозрел! Ты сделал мой день.

bk_ ★★ ()
Ответ на: комментарий от bk_

> О, анон, на _этом_ я прозрел! Ты сделал мой день.

Чаще включай голову и читай книжки, и область деятельности менять не придется :)

anonymous ()
Ответ на: комментарий от rg-400

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

//Тем ни о чем.

+1 но местами забавно ;-)

AIv ★★★★★ ()
Ответ на: комментарий от bk_

как ? определяеш через линуксовые - такуюже структуру как в глибах и юзаеш

man queue
sys/queue.h
там много препроцесорных вставок

ae1234 ★★ ()
Ответ на: комментарий от AIv

> Напр в возможности хранить в одном списке структуры разных типов и размеров.

Ничто не мешает этого делать и без глистов

anonymous ()

И кстати «связный список» звучит примерно как «сладкий сахар». Списки бывают ОДНОсвязные и ДВУХсвязные, НЕсвязных списков не бывает;-)

AIv ★★★★★ ()

Всех, оказавшим содействие, благодарю! То, что хотел, узнал.

bk_ ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.