Вопрос к программистам на C , Исходники ядра Linux

Цитата Flex Ferrum @ 19.04.06, 15:07

Вот смотри. (рассматривая с позиции С++). У меня (как у разработчика клиентского кода) есть три последовательности - массив int'ов, массив double'ов и массив std::string'ов. (заметь - полностью детерминированная система. Так?) Мне эти три последовательности надо отсортировать. Имею право на такое желание? Имею. Но вот незадача - скорость сортировки меня не совсем устраивает. Узкое место - в процедуре обмена значений. Следуя твоей логике, я должен написать три варианта функции сортировки для каждого из типа последовательностей. Так? Продолжая работать над кодом у меня появилось еще две последовательности - массив char'ов и массив структур MySuperPuperStructure. Может быть такое? Легко. Для каждого из вновь появившехся типов последовательностей заново писать алгоритм сортировки? А через месяц появится еще три типа последовательностей. Что мне делать, следуя предложенной тобою линии? Всякий раз переписывать функции сортировки? Али как?

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

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

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

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

так что тут еще вопрос, что лучше, а что хуже.

Цитата bugger @ 20.04.06, 07:19

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

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

С какой-то стороны да. С другой стороны, есть такая вещь, как оптимизатор компилятора. Я когда игрался с boost::lambda решил посмотреть - а какой же код он генерирует. Был в легком шоке. Взял простой исходный текст:

int main(int, char**)
{
 using namespace boost;
 std::vector<int> vec(10, 10);
 
 std::transform(vec.begin(), vec.begin() + 3, vec.begin(), lambda::_1 + 3);
 
 return 0;
}

В объектном коде std::transform выглядел так:

 std::transform(vec.begin(), vec.begin() + 3, vec.begin(), lambda::_1 + 3);
004010E8  lea         ecx,[esi+0Ch]
004010EB  cmp         esi,ecx
004010ED  mov         dword ptr [esp+34h],1
004010F5  mov         eax,esi
004010F7  je          main+9Ah (40110Ah)
004010F9  lea         esp,[esp]
00401100  add         dword ptr [eax],3
00401103  add         eax,4
00401106  cmp         eax,ecx
00401108  jne         main+90h (401100h)

Это к слову о "заточке" под определенный тип данных...

Добавлено 20.04.06, 07:39

Цитата linuxfan @ 20.04.06, 05:55

Вообще говоря, обобщенные алгоритмы это не та область, в которой хороши процедурные языки. Конечно, в силу необходимости их приходится использовать и в таких случаях нельзя не сказать спасибо дядьке Страуструпу и комитету ISO за существование шаблонов в языке C++. Но если посмотреть, например, на Lisp то быстро становится понятно, каким костылем являются темплейты, хотя, конечно, они сильно облегчают решение многих задач. Но ИМХО все элементы ФП в плюсах -- редкостно уродливый костыль, от которого весь мир в восторге, потому что ничего другого не видел.

Вполне возможно. Поскольку с лиспом никогда дела не имел - судить сложно. Может быть костыль. Но мне жизнь очень и очень облегчает.

Кто-нибудь скажет что с этим делать?

[root@106-109-8-11 hel2]# ./a.out
bash: ./a.out: Permission denied

Я собрал a.out командой as hello.S, а он не запускается. В чем дело?
И можно сделать, чтобы as назвал выходной файл как-нибудь по другому?

Цитата Flex Ferrum @ 20.04.06, 07:33

Это к слову о "заточке" под определенный тип данных...

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

Цитата bugger @ 20.04.06, 07:58

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

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

Добавлено 20.04.06, 08:04
(Определить, естественно, на этапе компиляции)

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

Цитата bugger @ 20.04.06, 08:06

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

Все не так сложно:

template<typename T> void DoSwap(T& t1, T& t2)
{
    Swapper<
        (boost::is_integral<T>::value) ? InPlace :
        (HasSwap<T>::value ? ViaMemberFun : StandardSwap)
    >::DoSwap(t1, t2);
}

Вот и все проверки. Выполняются они, заметь, на этапе компиляции.

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

Цитата bugger @ 20.04.06, 08:23

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

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

Уважаемые коллеги, продолжим завтра. Сегодня занят под завязку. Есть пара интересных моментов.

2 plan699.
Постой пока в стороне (в смысле -- почитай). Здесь -- затопчут. Заодно в разделе UNIX поройся, пока, во всяком случае...

Цитата plan699 @ 20.04.06, 07:48

Я собрал a.out командой as hello.S, а он не запускается. В чем дело?
И можно сделать, чтобы as назвал выходной файл как-нибудь по другому?

as делает объектник, а не исполняемый модуль (как obj в DOS/Windows). Его надо слинковать, например командой ld. Только засада в том, что лично я у себя не могу найти crt*.o, с которым бы получился требуемый результат.
Ну а задать имя проще простого: as -o hello.o hello.s

Цитата

Но если посмотреть, например, на Lisp то быстро становится понятно,

После AutoLISP у меня от него изжога... :D:D:D

Цитата

Только засада в том, что лично я у себя не могу найти crt*.o, с которым бы получился требуемый результат.

Угу... Угу... :D:D:D
Да не всё так просто -- на "раз-два-три". Блин, либо мы действительно знаем систему, либо мы пытаемся делать вид, что мы умные.

Цитата

Ну, с другой стороны, твое право. А я предпочитаю себя не ограничивать в средствах.

Да! Конечно! Вот только уволь меня от печальной необходимости колупаться в 14 кб текста на, вообщем-то банальной задачке. А иногда приходится. :D:D:D
С другой стороны. Этот вопрос я покамест отставлю в сторону, т.к. с ним мы будем разбираться в соотв. холиваре.

Цитата

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

А кто мешает просто и явно указать, что file_int.c -- реализации функций для int, file_int.h -- описания функций. А вот для char будет file_char.c|file_char_h.h. Но реализации будут адекватными и портируемыми (см. про то, что POSIX говорит о портируемости и "переносимости на уровне исходных кодов" в частности).

Оно, конечно, понятно, что для контактенации строк можно воспользоваться "+" (при желании), но вот деление на strcat/strncat не зря придумано. И во-все не по "историческим" соображениям.

По lcc. Вышеприводимый мой код для qsort был залит в свежеустановленный lcc-win32, под wine.
asm:

.file   "c:\lcc\include\stddef.h"
_$M0:
    .file   "c:\lcc\projects\fl\fl.c"
    .text
    .file   "c:\lcc\include\stdlib.h"
_$M1:
    .file   "c:\lcc\projects\fl\fl.c"
_$M2:
    .text
;    1 #include <stdlib.h>
;    2 #define MAX_ARR 1024
;    3
;    4 int arr[MAX_ARR];
;    5 int n;
;    6
;    7 static int comp_func( int *a, int *b )
    .type   _comp_func,function
_comp_func:
;    8 {
    .line   8
;    9     if( *a < *b )
    .line   9
    movl    4(%esp),%eax
    movl    8(%esp),%edx
    movl    (,%edx),%edx
    cmpl    %edx,(,%eax)
    jge _$5
;   10     {
;   11     return( -1 );
    .line   11
    orl $-1,%eax
    jmp _$4
_$5:
;   12     }
;   13     else if( *b < *a )
    .line   13
    movl    8(%esp),%eax
    movl    4(%esp),%edx
    movl    (,%edx),%edx
    cmpl    %edx,(,%eax)
    jge _$7
;   14     {
;   15     return( 1 );
    .line   15
    xor %eax,%eax
    inc %eax
    jmp _$4
_$7:
;   16     }
;   17     return( 0 );
    .line   17
    xor %eax,%eax
_$4:
;   18 }
    .line   18
    ret
_$9:
    .size   _comp_func,_$9-_comp_func
;   19
;   20 int main( int argc, char *argv[] )
    .type   _main,function
_main:
    pushl   %ebp
    movl    %esp,%ebp
;   21 {
    .line   21
;   22     qsort( arr, n, sizeof( int ), comp_func );
    .line   22
    pushl   $_comp_func
    pushl   $4
    pushl   _n
    pushl   $_arr
    call    _qsort
    addl    $16,%esp
;   23     return 0;
    .line   23
    xor %eax,%eax
;   24 }
    .line   24
    popl    %ebp
    ret
_$11:
    .size   _main,_$11-_main
    .globl  _main
    .bss
    .globl  _n
    .align  2
    .type   _n,object
    .comm   _n,4
    .globl  _arr
    .align  2
    .type   _arr,object
    .comm   _arr,4096
    .extern _qsort

Здесь, если не ошибаюсь, использован nasm, по этой причине конструкции, мягко говоря, странноваты.
Далее. Была включена просто оптимизация, без доп. ухищрений. Если кто-то не понял -- просто кликнул на галочке "Optimize" и всё.
По дефолту получил 3104 байта. Не сомневаюсь, что по-игравшись с Alignmet'ом и т.д. и т.п., получу результат ещё меньше.
Почему так не может M$, несмотря на то, что авторы компилятора имеют e-mail@microsoft.com?

Далее. Могу привести код, его размер (и скриншот) для пустого приложения Win32. Там всё ещё веселее.
И, кстати, замечу, что решение для Control-Panel Applet не будет столь очевидным (по своей простоте создания в среде lcc). Замечу так же, что .cpl в Visual создаётся и пишется по-проще (в разы). Это к теме того, что в M$ можно запросто использовать компилятор, отличный от Visual.

Собственно, в "пристёжке" смотрите. Там есть .EXE'шник, размером в 6688 байт. Конечно же, с установками "по дефолту" (-O) :D:D:D
Рекомендую создать в Visual столь же "функциональный" примерчиксссс...
Прикреплённый файлtestwin.zip (8.58 Кбайт, скачиваний: 78)

Цитата the_Shadow @ 20.04.06, 11:35

Да! Конечно! Вот только уволь меня от печальной необходимости колупаться в 14 кб текста на, вообщем-то банальной задачке. А иногда приходится. :D:D

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

Цитата the_Shadow @ 20.04.06, 11:35

А кто мешает просто и явно указать, что file_int.c -- реализации функций для int, file_int.h -- описания функций. А вот для char будет file_char.c|file_char_h.h. Но реализации будут адекватными и портируемыми (см. про то, что POSIX говорит о портируемости и "переносимости на уровне исходных кодов" в частности).

А одновременно я их использовать смогу?

Цитата the_Shadow @ 20.04.06, 11:35

По дефолту получил 3104 байта. Не сомневаюсь, что по-игравшись с Alignmet'ом и т.д. и т.п., получу результат ещё меньше.
Почему так не может M$, несмотря на то, что авторы компилятора имеют e-mail@microsoft.com?

Объясню. Потому что в M$ тоже знают про правило 80/20, и "по умолчанию" делают такие настройки, которые подходят подавляющему большинсту разработчиков. А оставшаяся часть достигнет необходимого им результата внимательно прочитав необходимые разделы документации. И этот подход имеет право на существование. В чем собственно предмет спора? В том, что настройки проекта "по умолчанию" не подходят конкретно тебе? Ну так измени их. У тебя есть для этого все средства. А добиться от компилятора VC экзешников маленького размера можно - я это успешно продемонстрировал.

Цитата

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

Слушай, у меня есть проблема... :D:D:D
Приведённый тобой код не линкуется (точнее, всё-таки, не линковался :D:D:D ) без дополнительных (и специфичных для С++) библиотек? Пришлось доустанавливать. И... Это довольно значительный объём, знаешь ли... Я -- то же что-то не то делаю? :D:D:D

Ну, тогда расскажи мне -- почему без доп. либ... Оно ни как... :D:D:D

Цитата

А одновременно я их использовать смогу?

Flex! Блин, отец, ну ты меня удивляешь... :(((
А что, "раздельную компиляцию" и "разделение областей видимости" были придуманы Бъярном-Мёртвым-Страусом??? 8-/ И до него, в С, мы жили без них? Уверяю тебя -- он свой С++ писал под OS IRIX (а это, как ты понимаешь, во-все не Win... :D:D:D).
Но позволь -- я могу одно и то же имя переменной (к примеру) использовать в разных областях видимости -- на уровне отдельного файла, отдельного проекта... Другое дело, что имена функции должны быть более информативными, к примеру, my_q_sort_int( тут мы чётко говорим что сортируем) И my_qsort_char( и тут то же, кстати) всё-таки лучше, чем просто my_qsort и гадай там -- для какого именно это случая... Но это же, позволь, вообще прописная истина!

Цитата

А добиться от компилятора VC экзешников маленького размера можно - я это успешно продемонстрировал.

Извини, но не до конца. Я дополнил своё сообщение.

Добавлено 20.04.06, 12:05
Кстати, скрин всего этого безобразия...

Прикреплённая картинка

Цитата the_Shadow @ 20.04.06, 11:35

Собственно, в "пристёжке" смотрите. Там есть .EXE'шник, размером в 6688 байт. Конечно же, с установками "по дефолту" (-O) :D:D

С моими опциями компиляции exe-шник занял 4704 байта.

Цитата the_Shadow @ 20.04.06, 11:53

Приведённый тобой код не линкуется (точнее, всё-таки, не линковался) без дополнительных (и специфичных для С++) библиотек?
Я -- то же что-то не то делаю? :D:D

Какой именно код?

Цитата the_Shadow @ 20.04.06, 11:53

А что, "раздельную компиляцию" и "разделение областей видимости" были придуманы Бъярном-Мёртвым-Страусом??? 8-/

Расскажи - как я могу это сделать, если сортировка разным массивов мне нужна в пределах одной функции?

Добавлено 20.04.06, 12:13

Цитата the_Shadow @ 20.04.06, 11:53

Но позволь -- я могу одно и то же имя переменной (к примеру) использовать в разных областях видимости -- на уровне отдельного файла, отдельного проекта... Другое дело, что имена функции должны быть более информативными, к примеру, my_q_sort_int( тут мы чётко говорим что сортируем) И my_qsort_char( и тут то же, кстати) всё-таки лучше, чем просто my_qsort и гадай там -- для какого именно это случая... Но это же, позволь, вообще прописная истина!

Еще один шаг - и мы таким образом дойдем до использования венгерки. А ты не задумывался над тем, что компилятор, вообще говоря, и так знает тип сортируемой последовательности? Зачем ему дополнительным образом его указывать?

Добавлено 20.04.06, 12:19

Цитата the_Shadow @ 20.04.06, 11:35

Далее. Могу привести код, его размер (и скриншот) для пустого приложения Win32. Там всё ещё веселее.
И, кстати, замечу, что решение для Control-Panel Applet не будет столь очевидным (по своей простоте создания в среде lcc). Замечу так же, что .cpl в Visual создаётся и пишется по-проще (в разы). Это к теме того, что в M$ можно запросто использовать компилятор, отличный от Visual.

И тем не менее не пойму - чего ты хочешь доказать? Что lcc по умолчанию генерирует более "легкий" exe-шник, чем VC? А смысл, если все дело в настройках? Да, настройки "по умолчанию" проектов под VC продуцируют не такой маленький размер исполняемых файлов. Но это не значит, что эти настройки нельзя поменять, и нельзя добиться аналогичных размеров экзешников от VC.