LINUX.ORG.RU

Контейнеры в C


2

3

Будучи сиплюсплюсником, меня давно интересует как те же задачи выполняются в C. Знаю, на ЛОРе есть множество приверженцев C, надеюсь они ответят на пару простых вопросов.

Я являюсь активным сторонником идеи «Алгоритм должен работать настолько быстро, насколько позволяет железо». С этой точки зрения C++ даёт потрясающие возможности из-за своей системы кодогенерации. Да, я имею в виду шаблоны.

Не будем зарываться в дебри boost'а, возьмём простую задачу - контейнеры.

Для примера я взял односвязные списки в GTK GSList и Qt QList. QList позволяет хранить как простые, так и сложные типы с конструкторами, деструкторами, типы с общими данными. При этом накладных расходов на выделение в куче не происходит, а при реаллокации выбирается нужный алгоритм в зависимости от QTypeInfo<T>, к примеру для int будет вызван memcpy(), а для QString оператор копирования. Кроме того блок данных заранее резервируется и для сложных типов вызывается placement constructor. Для удаления данных по указателям используется алгоритм qDeleteAll(from,to), который сам дёрнет нужные конструкторы. Беглый просмотр GSList показал, что в нём можно хранить только указатели, со всеми вытекающими накладными расходами на аллокацию/уничтожение памяти, ручное кастирование, слежение за утечками, фрагментацию памяти.

Аналогичная ситуация со связными списками GList и QLinkedList.

Это даже не затрагивая вопрос о типизации, в C++ компилятор сразу даст по рукам при попытке записать в контейнер неверный тип или с помощью неявного преобразования с explicit-конструктором.

Далее, счётчики ссылок и деструкторы.

К примеру, в C++ список строк будет выглядеть как QList<QString>, при этом можно забыть про внутреннюю структуру строки - конструктор, деструктор и операторы копирования сами занимаются подсчётом ссылок, разделением и уничтожением данных. Вернуть строку из функции проще простого:

QString foo()
{
    return listOfStrings.at( 5 );
}

Этот код абсолютно безопасен и оптимален с точки зрения использования памяти и процессора, поскольку время тратится только на увеличение счётчика и копирование указателя.

В GTK я сходу нашёл GString:

struct GString 
{
  gchar *str;
  gint len;
};

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

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

Или может GTK неудачный пример, тогда дайте ссылку на правильную C-библиотеку с контейнерами.

★★★★★
Ответ на: комментарий от ahonimous

>>пациент, да у вас тяжелая форма амнезии

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

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

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

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

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

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

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

http://gramota.ru/slovari/dic/?bts=x&word=%EF%E0%F0%E0

седьмой пункт

unC0Rr ★★★★★
()
Ответ на: комментарий от MuZHiK-2

Вначале попробовал отвечать на вопросы товарища MuZHiK-2, но понял, что дело это неблагодарное.

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

1. Данная тема не преследует сравнение C и C++ вообще, а только частный случай.
2. Сопутствующая библиотека не играет роли, важен сам принцип, можно ли технически достичь желаемого результата в компилируемом обьектнике с помощью средств языка. Если технически достичь можно, то хотелось бы увидеть код.
3. Счётчики ссылок, автоматизация удаления - не рассматриваются в этой теме.

Используемая библиотека на C не играет роли, но поскольку главный защитник этого языка, MuZHiK-2, несколько раз упомянул GList, то предлагаю его и сравнивать. Для сравнения со стороны C++ возьмём такой же связный список - QLinkedList.

Звено GList:

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

Звено QLinkedList:

template <typename T>
struct QLinkedListNode
{
    inline QLinkedListNode(const T &arg): t(arg) { }
    QLinkedListNode *n, *p;
    T t;
};

Как видим в C++ с помощью шаблона ликвидируется накладные расходы на аллокацию лишних данных в куче, в C же всё хранится по указателю.

Идём дальше, сравним сортировку в массивах GArray и QVector:

GList:

void g_array_sort_with_data(GArray *array, GCompareDataFunc compare_func, gpointer user_data);

QVector:

qSort();

Собственно, вопрос не в сложности алгоритма, а в том, что в g_array_sort_with_data() подставляется указатель на функцию, в то время как в C++ алгоритм будет оптимизирован на этапе генерации кода используя инлайновые операторы сравнения типов.

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

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

вообще внизу всего ассемблерный код

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

точнее опиши - в чем ты видиш неэффективность Си решения ?

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

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

struct Person {
    char *nick;
    char name[0];
};

struct Person* make_person(const char *nick, const char *name)
{
    unsigned int nick_l = strlen(nick), name_l = strlen(name);
    struct Person *p = (struct Person*)malloc(sizeof(struct Person*) + nick_l + name_l + 2);
    p->nick = (char*)p + sizeof(*p) + nick_l + 1;
    memcpy(p->nick, nick, nick_l + 1);
    memcpy(p->name, name, name_l + 1);
    return p;
}

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

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

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

>Ну это уже низкоуровневый код.

Превед! А C — это кроссплатформенный ассемблер!

А если кто нить удалит nick выше - то все ляжет раком?

В приципе, const char *nick, const char name[0] тебе в помощь. Мне было лениво касты к char* писать, поэтому без const обошелся.

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

на такие const тоже спокойно вызывается и delete и free

ну так это можно достаточно легко сделать и на C++

[code]

class String;

class StringRef { StringRef(const String&); };

[/code]

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

Только это не спасает от того, что если кто-то сохранил этот Ref, а снизу его удалили.

В любом случае без GC требуется некоторый уровень доверия

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

>на такие const тоже спокойно вызывается и delete и free

Ты давно последний раз компилятор в руки брал? -Wall -Werror спасут тебя от подобных глупостей.

В любом случае без GC требуется некоторый уровень доверия

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

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

ИМХО быдлокод

struct Person { 
    char *nick; 
    char name[0]; 
}; 
 
struct Person* make_person(const char *nick, const char *name) 
{ 
    unsigned int nick_l = strlen(nick), name_l = strlen(name); 
    struct Person *p = (struct Person*)malloc(sizeof(struct Person*) + nick_l + name_l + 2); 
    p->nick = (char*)p + sizeof(*p) + nick_l + 1; //<-- тут ошибка, вместо nick_l надо name_l
    memcpy(p->nick, nick, nick_l + 1); 
    memcpy(p->name, name, name_l + 1); 
    return p; 
}
А что мне помешает подобное написать на С++? Религия?

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

>//<-- тут ошибка, вместо nick_l надо name_l

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

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

>А что мне помешает подобное написать на С++? Религия?

То, что это будет не C++. Это будет в лучше млучае «C с классами».

linuxfan
()
Ответ на: комментарий от linuxfan
struct Person { 
    char *nick; 
    char name[0]; 
}

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

http://www.xakep.ru/magazine/xa/106/126/1.asp

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

>> А что мне помешает подобное написать на С++? Религия?

То, что это будет не C++. Это будет в лучше млучае «C с классами».

Сформулируешь кратенько отличие Ъ-Си++ от «Си с классами»?

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

Если я напишу map < string, string > , то это будет C++, а если напишу map < char *, char * >, то он вдруг станет «C с классами» ?

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

>> То, что это будет не C++. Это будет в лучше млучае «C с классами».

Сформулируешь кратенько отличие Ъ-Си++ от «Си с классами»?

Я над этим его заявлением так уржался, что под стол чуть не свалился ))) Судя по всему у него какой-то особый, неведомый нам С++ есть. И это чудило еще советует мне «покинуть профессию программиста» )))

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

>Сформулируешь кратенько отличие Ъ-Си++ от «Си с классами»?

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

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

>> Сформулируешь кратенько отличие Ъ-Си++ от «Си с классами»?

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

Видимо, не сформулируешь.

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

Как видим в C++ с помощью шаблона ликвидируется накладные расходы на аллокацию лишних данных в куче, в C же всё хранится по указателю.

Твой идиотизм и, главное, полное непонимание вопроса меня уже достало, поэтому пришло время макнуть тебя глубже. Я даже не поленился и написал небольшой тест для списков (можешь написать аналогичный для массивов, только смотри, не выпрыгни из окна от неожиданных результатов). Итак, Qt4 и твой указанный выше QLinkedList, который, как ты заявляешь, супер-пупер оптимальный:

struct person
{
    QString nick;
    int id;
};

int main(int argc, char *argv[])
{
    QLinkedList <person> list;

    for (int i = 0; i < 100000; ++i) {
        person per = {"Dendy", i};
        list.append (per);
    }
}

Как видишь, простенький тест на добавление 100 К элементов. Никакой магии. Аналогичный тестик на С с использованием GLib и GList:

#include <glib.h>

	typedef struct {
		gchar* nick;
		gint id;
	} person;

int main(int argc, char** argv)
{
	GList *list = NULL;
	guint i;

	for (i = 0; i < 100000; ++i) {
		person *Prs = g_slice_new (person);
		Prs->nick = g_strdup ("Dendy");
		Prs->id = i;
		list = g_list_prepend (list, Prs);
	}

	list = g_list_reverse (list);

	return 0;
}

Как видишь, я выделяю память в куче (на что ты и сетовал так активно) и работаю тут с указателями (и даже пришлось скопировать строчку, на что ты тоже там нес пургу). Теперь результаты тестов (через команду time). Для теста Qt4 в среднем (+- 0.002s)

real	0m0.062s
user	0m0.056s
sys	0m0.004s

Для теста GLib (+- 0.002s):

real	0m0.040s
user	0m0.032s
sys	0m0.008s

О, ужас! Qt4 сливает порядка 30% по скорости на такой простенькой задачке! А что будет дальше? Ясно дело, хуже. Так я не расслышал, что ты там за чушь нес про оптимальность и запупенность, скорость и форсаж своих любимых крестов?

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

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

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

Еще веселее будет без кэширования отсортировать такой список на пару миллионов элементов или найти в нем что-нибудь :)

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

>>Еще веселее будет без кэширования отсортировать такой список на пару миллионов элементов или найти в нем что-нибудь :)

Ну я уж не стал так жестко макать слоника и Ко, все крестовые навороты дадут просадку процентов в 50, наверно :)

MuZHiK-2 ★★★★
()
Ответ на: комментарий от namezys

>>И какие опции компилятора?

Опции компилятора я вообще не трогал - то, что по дефолту у креатора для Qt, и то, что выдает pkg-config для glib-теста.

MuZHiK-2 ★★★★
()
Ответ на: комментарий от namezys

>>Попробуй QList для начала.

Проверил только что - абсолютно такой же результат.

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

Как мне скомпилить прогу вторую?

Да, и вы забыли о том, что вообще-то строки в Qt юникодные, и вы за одно их конвертите

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

>>Как мне скомпилить прогу вторую?

gcc -o <prog_name> `pkg-config --cflags --libs glib-2.0` <main.c>

Да, и вы забыли о том, что вообще-то строки в Qt юникодные, и вы за одно их конвертите

Передал обоим тестам пустые строчки - у обоих время сократилось, но Qt все равно проигрывает процентов 30.

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

Можно еще проверить реализацию связанных списков без всяких «глистов»: на чистом С. Что-то вроде

struct person{
   char* nick;
   int id;
   struct person *prev;
   struct person *next;
}

struct person *newperson(){
   struct person *ptr = (struct person*)malloc(sizeof(struct person));
   return ptr;
}

struct person *addperson(struct person *last){
   struct person ptr = newperson();
   if(!last){
      ptr->prev = NULL;
      ptr->next = NULL;
   }
   else{
      if(!last->next){
        last->next = ptr;
        ptr->prev = last;
        ptr->next = NULL;
      }
      else{
        ptr->next = last->next;
        last->next->prev = ptr;
        last->next = ptr;
        ptr->prev = last;
      }
   return ptr;
}
и т.д.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от namezys

Ну мужик, я сам разобрался.

Qt:

#include <QString>
#include <QList>

const QString dendy = "Dendy";
 
struct person 
{ 
    person(const QString& a_nick, int a_id) :
        nick(a_nick), id(a_id) {}

    QString nick; 
    int id; 
}; 
 
int main(int argc, char *argv[]) 
{
    Q_UNUSED(argc);
    Q_UNUSED(argv); 
    QList<person> list; 
 
    for (int i = 0; i < 1000000; ++i) { 
        list.append( person(dendy, i) ); 
    } 
} 
g++ -c -pipe -O2 -Wall -W -D_REENTRANT -DQT_NO_DEBUG -DQT_GUI_LIB -DQT_CORE_LIB -DQT_SHARED -I/usr/share/qt4/mkspecs/linux-g++ -I. -I/usr/include/qt4/QtCore -I/usr/include/qt4/QtGui -I/usr/include/qt4 -I. -I. -o a.o a.cpp
g++ -Wl,-O1 -o qt a.o    -L/usr/lib -lQtGui -lQtCore -lpthread

glib:

#include <glib.h> 

const char* dendy = "Dendy";
 
typedef struct { 
   gchar* nick; 
   gint id; 
} person; 
 
int main(int argc, char** argv) 
{ 
   GList *list = NULL; 
   guint i; 
 
   for (i = 0; i < 1000000; ++i) { 
      person *Prs = g_slice_new (person); 
      Prs->nick = g_strdup (dendy); 
      Prs->id = i; 
      list = g_list_prepend (list, Prs); 
   } 
 
   list = g_list_reverse (list); 
 
   return 0; 
}
~/test_qt/c$ gcc -O2 `pkg-config --cflags --libs glib-2.0` a.c
~/test_qt/c$ pkg-config --cflags --libs glib-2.0
-I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include  -lglib-2.0

Тестирование (1 000 000) элементов:

namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m0.176s
user    0m0.110s
sys     0m0.050s
namezys@namezys-desktop:~/test_qt$ time c/a.out 

real    0m0.244s
user    0m0.060s
sys     0m0.040s
namezys ★★★★
()
Ответ на: комментарий от MuZHiK-2

Не забыл что C++ еще выделенную память в конце чистит? Удали все элементы из GList, увидешь что время выполнения сравняется.

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

> list.append( person(dendy, i) );

все правильно - ушло лишнее копирование и стало быстрее, и да - в варианте MuZHiK-2 надо еще 1000000 раз g_free вызвать + g_slice_free

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

Добавил удаление в glib, увеличил кол-во элементов до 10 000 000

glib: 2.4s в среднем за 10 запусков (в сторону уменьшения) qt: 1.6s

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

Там не только линейное копирование - там еще вообще-то еще и приведение к unicode

хотя компилятор мог это и оптимизировать

namezys ★★★★
()
Ответ на: комментарий от MuZHiK-2
namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m1.622s
user    0m1.320s
sys     0m0.300s
namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m1.802s
user    0m1.560s
sys     0m0.240s
namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m1.714s
user    0m1.370s
sys     0m0.320s
namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m1.688s
user    0m1.310s
sys     0m0.370s
namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m1.536s
user    0m1.300s
sys     0m0.190s
namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m1.637s
user    0m1.330s
sys     0m0.280s
namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m1.597s
user    0m1.210s
sys     0m0.330s
namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m1.738s
user    0m1.410s
sys     0m0.300s
namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m1.418s
user    0m1.120s
sys     0m0.290s
namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m1.354s
user    0m1.060s
sys     0m0.280s
namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m1.361s
user    0m1.050s
sys     0m0.300s
namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m1.813s
user    0m1.470s
sys     0m0.340s
namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m1.672s
user    0m1.160s
sys     0m0.210s
namezys@namezys-desktop:~/test_qt$ time qt/qt 

real    0m1.722s
user    0m1.040s
sys     0m0.200s
namezys@namezys-desktop:~/test_qt$ time c/a.out 

real    0m2.493s
user    0m1.620s
sys     0m0.580s
namezys@namezys-desktop:~/test_qt$ time c/a.out 

real    0m2.332s
user    0m1.350s
sys     0m0.510s
namezys@namezys-desktop:~/test_qt$ time c/a.out 

real    0m2.591s
user    0m1.500s
sys     0m0.640s
namezys@namezys-desktop:~/test_qt$ time c/a.out 

real    0m2.182s
user    0m1.580s
sys     0m0.440s
namezys@namezys-desktop:~/test_qt$ time c/a.out 

real    0m2.511s
user    0m1.540s
sys     0m0.600s
namezys@namezys-desktop:~/test_qt$ time c/a.out 

real    0m2.382s
user    0m1.750s
sys     0m0.590s
namezys@namezys-desktop:~/test_qt$ time c/a.out 

real    0m2.498s
user    0m1.710s
sys     0m0.670s
namezys@namezys-desktop:~/test_qt$ time c/a.out 

real    0m2.344s
user    0m1.230s
sys     0m0.590s
namezys@namezys-desktop:~/test_qt$ time c/a.out 

real    0m2.426s
user    0m1.750s
sys     0m0.650s
namezys@namezys-desktop:~/test_qt$ time c/a.out 

real    0m2.435s
user    0m1.880s
sys     0m0.510s
namezys@namezys-desktop:~/test_qt$ time c/a.out 

real    0m2.289s
user    0m1.620s
sys     0m0.620s
namezys@namezys-desktop:~/test_qt$ time c/a.out 

real    0m2.471s
user    0m1.690s
sys     0m0.610s
namezys@namezys-desktop:~/test_qt$ time c/a.out 

real    0m2.406s
user    0m1.750s
sys     0m0.640s
namezys ★★★★
()
Ответ на: комментарий от ahonimous
#include <string>
#include <list>

struct person 
{ 
    std::string nick; 
    int id; 
}; 
 
int main(int argc, char *argv[]) 
{ 
    std::list<person> list; 
    list.resize( 100000 );
    
    std::list<person>::iterator it = list.begin();
    for( int i = 0 ; i < 100000 ; ++i, ++it )
    {
    	(*it).nick = "Dendy";
    	(*it).id   = i;
    }
} 

у меня этот вариант в 8 раз быстрее варианта мужика, без очистки памяти

ahonimous
()
Ответ на: комментарий от ahonimous
#include <string>
#include <list>

struct person 
{ 
    std::string nick; 
    int id; 
}; 
 
const std::string str = "Dendy"; 
 
int main(int argc, char *argv[]) 
{ 
    std::list<person> list; 
    list.resize( 100000 );
    
    std::list<person>::iterator it = list.begin();
    for( int i = 0 ; i < 100000 ; ++i, ++it )
    {
    	(*it).nick = str;
    	(*it).id   = i;
    }
} 

если сделать как у namezys с const QString - то станет еще в 2 раза быстрее

ahonimous
()
Ответ на: комментарий от MuZHiK-2

Этот вариант на С + glib:

(-O3 -pipe -fomit-frame-pointer)
real	0m0.077s
user	0m0.039s
sys	0m0.003s

Вариант на CL:

(defstruct person (nick "") (id 0))

(defun foo (persons)
  (dotimes (i 100000)
    (push (make-person :nick "oh-no!" :id i) persons)))

(time (foo nil))
Evaluation took:
  0.013 seconds of real time
  0.007000 seconds of total run time (0.003000 user, 0.004000 system)
  53.85% CPU
  32,868,423 processor cycles
  2,402,008 bytes consed

Но чтобы быть честным я ещё объявлю типы и буду использовать append:

(defstruct person
  (nick "" :type string)
  (id   0  :type fixnum))

(defun foo (persons)
  (declaim (type list persons))
  (dotimes (i 100000)
    (setf persons (list* persons (make-person :nick "oh-no!" :id i)))))

(time (foo nil))
Evaluation took:
  0.012 seconds of real time
  0.005999 seconds of total run time (0.004999 user, 0.001000 system)
  42.86% CPU
  36,249,397 processor cycles
  2,397,912 bytes consed
quasimoto ★★★★
()
Ответ на: комментарий от anonymous

>>Не забыл что C++ еще выделенную память в конце чистит? Удали все элементы из GList, увидешь что время выполнения сравняется.

QList тоже в деструкторе каждый элемент чистит или только собственную память? Иначе будет нечестно.

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

> QList тоже в деструкторе каждый элемент чистит или только собственную память? Иначе будет нечестно.

Он ее чистит честно - дергает деструктор. Можно сделать пометку для этого типа, чтоб удалял просто память. Еще быстрее будет

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

>>Он ее чистит честно - дергает деструктор. Можно сделать пометку для этого типа, чтоб удалял просто память. Еще быстрее будет

Он дергает СВОЙ деструктор, но не деструктор каждого элемента. Не?

MuZHiK-2 ★★★★
()
Ответ на: комментарий от quasimoto

> Но чтобы быть честным я ещё объявлю типы и буду использовать append:

ради интереса - прогоните на время плз мой вариант на С++ для общей картины

ahonimous
()
Ответ на: комментарий от MuZHiK-2

> Он дергает СВОЙ деструктор, но не деструктор каждого элемента. Не?

каждого элемента

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

>> Сформулируешь кратенько отличие Ъ-Си++ от «Си с классами»?

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

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

shelA
()
Ответ на: комментарий от MuZHiK-2

> Он дергает СВОЙ деструктор, но не деструктор каждого элемента. Не?

Он дергает и деструктор каждого элемента, если не указано, что это QtTrivialType

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

> Я сейчас сделаю их такими, чтоб не появлялось констант времени компиляции и прогоню

кстати, если добавить "-static" то время выполнения моего примера можно сократить с .007 до 0.006 сек, а если добавить abort() - чтоб не очищать память( как у остальных примеров ), то 0.004 сек

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

Значит, если взять 1000.000 повторений, то вот так:

1) Вариант C + GLIB (мужика который)

real	0m0.444s
user	0m0.349s
sys	0m0.055s

2) C++ std:: *** (ахонимуса)

real	0m0.276s
user	0m0.193s
sys	0m0.016s

3) На CL

Evaluation took:
  0.212 seconds of real time
  0.185972 seconds of total run time (0.161975 user, 0.023997 system)
  [ Run times consist of 0.127 seconds GC time, and 0.059 seconds non-GC time. ]
  87.74% CPU
  538,488,519 processor cycles
  24,007,904 bytes consed

Ещё я заметил, что на C или CL можно неограниченно увеличивать размер списка, а вот на C++ после 10.000.000 начались вылеты.

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

а если учесть что она ваще ничего нужного неделает - то ее время выполнения равно 0лю - потому как ее запускать ваше ненадо
так ? :)

нагородили кучу примеров и нипонятно чего непонятно с чем сравниваете

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

но это ведь не чистое время - тут нет очистки списка, да?

Тут всё, включая расход на вызов и возвращение из функции (и подготовка списка, но списки там не такие просты - нельзя сказать, что они очищаются)

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

> но списки там не такие просты - нельзя сказать, что они очищаются

т.е. не очищаются, как я понял, получается что сравниваются разные задачи - С++ уже отдал всю память, а CL нет

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

С++ уже отдал всю память, а CL нет

Это тонкий вопрос :) т.к. память отдаёт GC. Но я замечу такую штуку - если говорить о реализации _одинаковых_ алгоритмов (одинаково хорошо), то среднестатистически можно разогнать CL до (иногда лучше) уровня Си, хотя в большинстве случаев это конечно не так - CL будет отставать. Собственно, бенчмарки на шутауте это и показывают (там есть парочка тестов где CL сравним с Си). Оффтопик, однако ;)

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

> но я замечу такую штуку - если говорить о реализации _одинаковых_ алгоритмов (одинаково хорошо), то среднестатистически можно разогнать CL до (иногда лучше) уровня Си

и ваш пример это тоже показал - реализация на CL оказалась быстрее реализации на glib

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

Чистый CPP:

#include <string> 
#include <list> 
#include <stdlib.h>
 
struct person  
{  
    std::string nick;  
    int id;  
};  
  
  
int main(int argc, char *argv[])  
{  
    std::list<person> list;
    int count = atoi(argv[2]);    
    list.resize(count); 
     
    const std::string str = argv[1];  

    std::list<person>::iterator it = list.begin(); 
    for( int i = 0 ; i < count ; ++i, ++it ) { 
       it->nick = str; 
       it->id   = i; 
    } 
}

namezys@namezys-desktop:~/test_qt/cpp$ time ./a.out dendy 10000000

real    0m1.319s
user    0m0.850s
sys     0m0.380s
namezys@namezys-desktop:~/test_qt/cpp$ time ./a.out dendy 10000000

real    0m1.358s
user    0m0.980s
sys     0m0.300s
namezys@namezys-desktop:~/test_qt/cpp$ time ./a.out dendy 10000000

real    0m1.353s
user    0m0.850s
sys     0m0.380s
namezys@namezys-desktop:~/test_qt/cpp$ time ./a.out dendy 10000000

real    0m1.368s
user    0m0.940s
sys     0m0.270s
namezys@namezys-desktop:~/test_qt/cpp$ time ./a.out dendy 10000000

real    0m1.320s
user    0m0.880s
sys     0m0.430s

но этот код с «шоткатом»

CPP + Qt:

#include <QString>
#include <QLinkedList>
#include <stdlib.h>

struct person 
{ 
    person(const QString& a_nick, int a_id) :
        nick(a_nick), id(a_id) {}

    QString nick; 
    int id; 
}; 
 
int main(int argc, char *argv[]) 
{
    Q_UNUSED(argc);
    Q_UNUSED(argv); 
    QLinkedList<person> list; 

    const QString dendy = argv[1];
    int count = atoi(argv[2]); 
 
    for (int i = 0; i < count; ++i) { 
        list.append( person(dendy, i) ); 
    } 
}

namezys@namezys-desktop:~/test_qt/qt$ time ./qt dendy 10000000

real    0m1.586s
user    0m1.280s
sys     0m0.270s
namezys@namezys-desktop:~/test_qt/qt$ time ./qt dendy 10000000

real    0m1.584s
user    0m1.220s
sys     0m0.240s
namezys@namezys-desktop:~/test_qt/qt$ time ./qt dendy 10000000

real    0m1.616s
user    0m1.220s
sys     0m0.350s
namezys@namezys-desktop:~/test_qt/qt$ time ./qt dendy 10000000
^[[A
real    0m1.728s
user    0m1.350s
sys     0m0.330s
namezys@namezys-desktop:~/test_qt/qt$ time ./qt dendy 10000000

real    0m1.571s
user    0m1.180s
sys     0m0.320s

Влияние QList и QLinkedList на глаз не заметил

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

#include <glib.h> 

typedef struct { 
   gchar* nick; 
   gint id; 
} person; 
 
int main(int argc, char** argv) 
{ 
   GList *list = NULL; 
   guint i; 
   gchar* dendy = g_strdup(argv[1]);
   int count = atoi(argv[2]);
 
   for (i = 0; i < count; ++i) { 
      person *Prs = g_slice_new (person); 
      Prs->nick = dendy; 
      Prs->id = i; 
      list = g_list_prepend (list, Prs); 
   } 
 
   //list = g_list_reverse (list); 
   g_list_free(list);
 
   return 0; 
}
namezys@namezys-desktop:~/test_qt/c$ time ./a.out dendy 10000000

real    0m1.548s
user    0m1.190s
sys     0m0.330s
namezys@namezys-desktop:~/test_qt/c$ time ./a.out dendy 10000000

real    0m1.472s
user    0m1.080s
sys     0m0.380s
namezys@namezys-desktop:~/test_qt/c$ time ./a.out dendy 10000000

real    0m1.496s
user    0m1.200s
sys     0m0.270s
namezys@namezys-desktop:~/test_qt/c$ time ./a.out dendy 10000000

real    0m1.472s
user    0m0.940s
sys     0m0.460s
namezys@namezys-desktop:~/test_qt/c$ time ./a.out dendy 10000000

real    0m1.407s
user    0m0.930s
sys     0m0.320s

А теперь варинт с получением независимых строк

namezys@namezys-desktop:~/test_qt/c$ time ./a.out dendy 10000000

real    0m2.390s
user    0m1.710s
sys     0m0.440s
namezys@namezys-desktop:~/test_qt/c$ time ./a.out dendy 10000000

real    0m2.358s
user    0m1.770s
sys     0m0.550s
namezys@namezys-desktop:~/test_qt/c$ time ./a.out dendy 10000000

real    0m2.294s
user    0m1.680s
sys     0m0.560s
namezys@namezys-desktop:~/test_qt/c$ time ./a.out dendy 10000000

real    0m2.385s
user    0m1.810s
sys     0m0.500s
namezys@namezys-desktop:~/test_qt/c$ time ./a.out dendy 10000000

real    0m2.400s
user    0m1.730s
sys     0m0.510s

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

В связи в оптимизаций без создания раздельных объектов привожу аналог кода на qt

#include <QString>
#include <QLinkedList>
#include <stdlib.h>

struct person 
{ 
    person(const QString& a_nick, int a_id) :
        nick(&a_nick, 0, a_nick.length()), id(a_id) {}

    QStringRef nick; 
    int id; 
}; 
 
int main(int argc, char *argv[]) 
{
    Q_UNUSED(argc);
    Q_UNUSED(argv); 
    QLinkedList<person> list; 

    const QString dendy = argv[1];
    int count = atoi(argv[2]); 
 
    for (int i = 0; i < count; ++i) { 
        list.append( person(dendy, i) ); 
    } 
}
namezys@namezys-desktop:~/test_qt/qt$ time ./qt dendy 10000000

real    0m1.029s
user    0m0.560s
sys     0m0.310s
namezys@namezys-desktop:~/test_qt/qt$ time ./qt dendy 10000000

real    0m1.103s
user    0m0.720s
sys     0m0.320s
namezys@namezys-desktop:~/test_qt/qt$ time ./qt dendy 10000000

real    0m1.104s
user    0m0.760s
sys     0m0.200s
namezys@namezys-desktop:~/test_qt/qt$ time ./qt dendy 10000000

real    0m1.055s
user    0m0.720s
sys     0m0.300s
namezys@namezys-desktop:~/test_qt/qt$ time ./qt dendy 10000000

real    0m1.050s
user    0m0.690s
sys     0m0.290s
namezys ★★★★
()
Ответ на: комментарий от MuZHiK-2

Списки сравнивать не очень интересно. Давай лучше сравним GTree и std::map. Вот где веселье то будет, потому что GTree будет на порядок медленее :)

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

>>Списки сравнивать не очень интересно. Давай лучше сравним GTree и std::map. Вот где веселье то будет, потому что GTree будет на порядок медленее :)

Теперь твоя очередь писать тесты :)

MuZHiK-2 ★★★★
()
Ответ на: комментарий от quasimoto

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

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