[C++?] Серьезный вопрос.

> ну вот, школьники обиделись :)))

да - мы, школьники, выражаем бурный протест против провокаций в наш адрес

> Тормоз он...

Ничем не обоснованное утверждение. Как мы увидели tailq работает чуть быстрее чем list. rb_tree работает чуть медленнее чем map.

Да, тесты с -O0 никакого практического интереса не представляют.

> это, очевидно, даст ему ответ на его вопрос "и что же вы пишите?"

очевидно, что если б ты скопипастил сюда немного текста, то сэкономил бы и свое и чужое время

> это, очевидно, даст ему ответ на его вопрос "и что же вы пишите?"

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

> очевидно, что если б ты скопипастил сюда немного текста, то сэкономил бы и свое и чужое время

я просто не хочу этой информацией светить тут

> rb_tree работает чуть медленнее чем map.

ничего, что map - это и есть rb-tree?

> я просто не хочу этой информацией светить тут

В интернетах, значит, светишь, а на ЛОРе (который тоже часть интернета) не хочешь? Где логика?

>Ты в курсе, что в современной операционной системе до первого обращения к неинициализированной странице память выделена не будет? Поэтому [MAX_VARS] не так страшно на самом деле, как кажется.

Да вот хз, половина компиляторов Си с радостью засунут статический массив в .data а не в .bss

Уверен что гыцаца этим не грешит, но на консолях наверно свои компиляторы.

А как связана балансировка с поиском? И массив ты на каждой вставке сортировать собрался? Может всё таки использовать структуру данных под задачу?

Кстати хеши в stl уже почти есть. В современных компиляторах (gcc 4 и студия 2008 sp1) это tr1/unordered_map и unordered_set.

я имею ввиду RB_TREE из sys/tree.h

> В интернетах, значит, светишь, а на ЛОРе (который тоже часть интернета) не хочешь? Где логика?

без логики. просто не хочу. отчитываться тоже не хочу :)

>И массив ты на каждой вставке сортировать собрался?

Обычно ассоциативные массивы создаются один раз и навсегда. В играх - точно.

PS: Зачем сортировать на каждой вставке если можно найти бинарным поиском посадочное место и вставить туда?

Ой, ты опять проголодался?

> Ничем не обоснованное утверждение. Как мы увидели tailq работает чуть быстрее чем list.

При том, что для tailq мы радостно в цикле для каждого элемента выделяли память... Так что если придётся хранить в списке что-то сложнее int -- ууупс.

> rb_tree работает чуть медленнее чем map.

Чуть быстрее, чем std::set, при том, что является аналогом std::map, ты хотел сказать? При той же фигне с int vs struct?

> Да, тесты с -O0 никакого практического интереса не представляют.

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

Ты хоть одну фразу без 4.2 способен выдать? 8))

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

Единственная часть буста, которая употреблялась "в тему" на моей памяти -- это boost::thread. Остальные абстракции настолько абстрактны или так подтекают, что ими лучше не пользоваться.

> без логики. просто не хочу. отчитываться тоже не хочу :)

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

> PS: Зачем сортировать на каждой вставке если можно найти бинарным поиском посадочное место и вставить туда?

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

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

я знал, что к этому придет. это же лор :)

> Единственная часть буста, которая употреблялась "в тему" на моей памяти -- это boost::thread. Остальные абстракции настолько абстрактны или так подтекают, что ими лучше не пользоваться.

Смартпойнтеры, shared_from_this - не? bind, function - не? Asio - не? Регэкспы (раз всё равно буст уже заюзан) - не? format - не?

Без таких мелочей (которые всё равно изобретать придётся) лучше сразу убить менеджера и на Лиспе начинать писать.

> я знал, что к этому придет. это же лор :)

Это опыт, товарищ ;)

> Обычно ассоциативные массивы создаются один раз и навсегда. В играх - точно.

Не всегда.

> PS: Зачем сортировать на каждой вставке если можно найти бинарным поиском посадочное место и вставить туда?

И данные двигать? Ты уверен, что это будет быстрее балансировки?

>> PS: Зачем сортировать на каждой вставке если можно найти бинарным поиском посадочное место и вставить туда?

>вы серьезно считаете, что в большинстве случаев, когда у нас не больше 1000-2000 элементов, есть смысл пользоваться такими велосипедами( которые не факт что в результате будут быстрее ), чем использовать стандартный контейнер?

По крайней мере память будет выделена единым блоком а не кусочками с указателем на парента, двумя указателями на детей и маркером цвета узла, кроме собственно пары ключ-значение. Если учитывать выравнивание, rb-дерево несет накладной расход в ~16 байт (на x86_64 - в ~32 байта) + MCB на каждый узел.

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

Чуть быстрее, чем std::set, при том, что является аналогом std::map, ты хотел сказать? При той же фигне с int vs struct?

4.2

$ time -p ./set 50000000
real 41.64
user 40.42
sys 1.20
$ time -p ./tree 50000000
real 42.82
user 41.78
sys 1.02
$ time -p ./set 10000000
real 6.79
user 6.61
sys 0.18
$ time -p ./tree 10000000
real 7.40
user 7.22
sys 0.19

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

при отладке можно и подождать немного

>> PS: Зачем сортировать на каждой вставке если можно найти бинарным поиском посадочное место и вставить туда?

>И данные двигать? Ты уверен, что это будет быстрее балансировки?

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

>При том, что для tailq мы радостно в цикле для каждого элемента выделяли память... Так что если придётся хранить в списке что-то сложнее int -- ууупс.

Уупс, а каждый элемент RBtree, оказывается, располагается статически в секции .astral? Или если ты не пишешь явно malloc/new, то значит и выделения динамической памяти не происходит?

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

у вас есть готовая реализация?

> 4.2

Иди читай тред сначала, трололо. У меня tree чуть (процента на 3 в среднем по сотне запусков) быстрее на -O2 и не волнует. C2D T9400.

По остальным пунктам вопросов нет? Отличненько, так и запишем:

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

2) Reset -- автомат для генерации 4.2 в любом заданном кол-ве

> при отладке можно и подождать немного

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

> rb-дерево несет накладной расход в ~16 байт (на x86_64 - в ~32 байта) + MCB на каждый узел.

можно так реализовать, что не будет накладного расхода. просто сделать с std::map гораздо сложнее (если вообще возможно). это даже если не начинать говорить о паталогиях map<string,string>

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

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

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

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

в играх для pc, в связи с большим объемом оперативы и наличием своп-файла, многие плюют на эти проблемы, и пользуются stl :)

>Или если ты не пишешь явно malloc/new, то значит и выделения динамической памяти не происходит?

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

ак что если придётся хранить в списке что-то сложнее int — ууупс.

4.2

$ time -p ./tree2 20000000
real 14.95
user 14.18
sys 0.78
$ time -p ./set2 20000000
real 14.47
user 13.64
sys 0.76

#include <stdint.h>
struct ComplexType
{
        uint32_t t;
        uint16_t v;
        double k;
        float h;
        char c;
};

#include "tree.h"
#include <err.h>
#include <stdio.h>
#include <stdlib.h>

#include "complex_type.h"
struct node
{
        RB_ENTRY (node) entry;
        int i;
        struct ComplexType v;
};
int
intcmp (struct node *e1, struct node *e2)
{
        return (e1->i < e2->i ? -1 : e1->i > e2->i);
}
RB_HEAD (inttree, node) head = RB_INITIALIZER (&head);
RB_GENERATE (inttree, node, entry, intcmp)


int
main (int argc, char ** argv)
{
        int i;
        int N = atoi (argv[1]);
        struct node *n;
        for (i = 0; i < N; i++)
        {
                if ( (n = malloc (sizeof (struct node) ) ) == NULL)
                        err (1, NULL);
                n->i = i;
                RB_INSERT (inttree, &head, n);
        }

        for (i = 0; i < N; i++)
        {
                n->i = i;
                struct node *w = RB_FIND (inttree, &head, n);
        }


        struct node *nxt;
        struct node *var;
        for (var = RB_MIN (inttree, &head); var != NULL; var = nxt)
        {
                nxt = RB_NEXT (inttree, &head, var);
                RB_REMOVE (inttree, &head, var);
                free (var);
        }
        return (0);
}

#include <map>
#include <stdlib.h>
#include "complex_type.h"

using namespace std;

int main(int argc, char ** argv)
{
        int n = atoi(argv[1]);
        map < int, ComplexType > lst;

        for (int i = 0; i < n; ++i) {
                ComplexType c;
                lst.insert(make_pair(i, c));
        }

        for (int i = 0; i < n; ++i) {
                map < int, ComplexType >::iterator it = lst.find(i);
        }
        return 0;
}

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

>у вас есть готовая реализация?

http://loki-lib.sourceforge.net/html/a00645.html

> Уупс, а каждый элемент RBtree, оказывается, располагается статически в секции .astral? Или если ты не пишешь явно malloc/new, то значит и выделения динамической памяти не происходит?

Уроки уже выучил? Тогда получи дополнительное задание:

1) найди в std::list RBtree

2) поправь тестик для использования как элемента списка struct { int i; double j; } и посмотри внимательно на результаты

>Смартпойнтеры, shared_from_this - не? bind, function - не? Asio - не? Регэкспы (раз всё равно буст уже заюзан) - не? format - не?

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

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

Бустовые пулы и регэкспы я вообще никогда и ни за что пользовать не собираюсь, потому как на моих глазах эти вещи приводили к падению многопоточных приложений под нагрузкой в версии 1.33. Я понимаю, что же 1.40 на дворе, но неприятный осадок остался, так что я за regex.h или за ppcre, если можно.

>Без таких мелочей (которые всё равно изобретать придётся)

Это без bind, function чтоли? Без них замечательно проживем, чай не лисп какой. asio? Я больше доверяю рукописным приблудам на libevent/libev.

>> Ведь коллекции/контейнеры почти в любой программе нужны.

> не нужны

Не верю. (C)

> 4.2

Это заголовок, я понял.

Во-первых, я про список говорил, альтернативно-русскочитающий ты наш... 8))

> У меня tree чуть (процента на 3 в среднем по сотне запусков) быстрее на -O2 и не волнует. C2D T9400.

Это меня мало волнует, у меня на C2Q 9550 map быстрее. Вот когда у меня на машине RB_TREE будет быстрее, тогда и поговорим.

> На боевом сервере. Чтобы кору получить. Которая раз в месяц возникает при невыясненных обстоятельствах (т.е. по искурёженной оптимизатором коре непонятно, смоделировать ситуацию не выходит). Спасибо, доктор.

Если не можете организовать процесс тестирования, то это ваши проблемы. Нормальные люди для этого тестовые сервера держат.

>> А чем так плох STL?

> Тормоз он...

Отчасти соглашусь. Но универсальных решений не бывает. Так что, общей библиотеке простительно.

У меня лично одна большая претензия. Сложно создавать свои контейнеры и использовать их вместе и вместо стандартных. Шаблоны, конечно, хороши. Но иногда хочется заменяемости контейнеров через наследование. Хотя, быть может, в последние годы меня слишком избаловали коллекции из Java и .NET :)

> Консольщики и память-то динамически выделять штатными средствами не любят. Свои специфические решения под задачу, очевидно.

Тогда почему нельзя использовать свой аллокатор? И не поверю, что контейнеры бывают настолько специфическими для задачи. Все равно, в них что-то есть общее, что можно было бы вынести в отдельную библиотеку. Пусть не STL. Но какая-то библиотека должна быть. Или они постоянно переизобретают колесо?

> struct something somevar[MAX_VARS] -- коллекция/контейнер? Если да -- то нужны, но на stl свет клином не сошёлся.

В STL-вском понимании - да, если задать ее как интервал [начало, конец). Но я не люблю такие "фиксированные" решения. Теряется масштабируемость.

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

Верной дорогой идете, товарищи!

Здравый смысл подсказывает, что фрагментация кучи происходит из-за создания и уничтожения большого числа временных объектов вперемешку с долгоживущими. И опять-таки здравый смысл нашептывает предложение держать пулы для короткоживущих объектов и не злоупотреблять динамической памятью, что позволит избежать фрагментации памяти. Но извращенцы, конечно, могут притащить какой-нибудь bohem-gc и радоваться жизни.

> http://loki-lib.sourceforge.net/html/a00645.html

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

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

>Уроки уже выучил? Тогда получи дополнительное задание

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

> Это меня мало волнует

Да я заметил. Как ляпнуть 4.2 -- так всегда впереди планеты всей...

> Если не можете организовать процесс тестирования, то это ваши проблемы. Нормальные люди для этого тестовые сервера держат.

Попробуй ещё раз прочитать то, что ты же процитировал. По аналогии с тестами std::map vs sys/tree.h -- 20 000 000 раз, вдруг дойдёт.

> Да вот хз - Саттер пишет что на практике связанный список обгоняет массив на рандомных вставках начиная где-то с ~1000 элементов. Кроме того, рандомные вставки в играх не особо-то не нужны: весь уровень обычно представляет собой статическую структуру которую надо отрендерить. Ну, для обработки событий геймплея возможно нужны LIFO и FIFO структуры которых можно построить на базе массивов фиксированного размера.

Если много статики, то тогда может быть и так.

> Но универсальных решений не бывает. Так что, общей библиотеке простительно.

Библиотеке простительно. Непростительно использовать эту библиотеку там, где она не подходит.

> Пусть не STL. Но какая-то библиотека должна быть. Или они постоянно переизобретают колесо?

Своя/не своя библиотека, хорошо подходящая под данный класс задач, не вопрос. Или вообще не нужны такие контейнеры.

> В STL-вском понимании - да, если задать ее как интервал [начало, конец).

Нету у нас stl, забудь. Это чистый C. Так считается это контейнером/коллекцией?

> Теряется масштабируемость.

Одно теряется, другое выигрывается... Как всегда и везде.

если на твоей конкретной машине что-то работает всего лишь на 3% быстрее, а у меня это работает на 3% медленнее, то это не доказательство абсудрдного утверждения о "тормозности" stl.

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

О, да. Вот тебе ещё одно задание.

3) Что именно мне продемонстрировали и как это связано с std::list vs tailq?

> Ты мне укажи связь между твоими двумя пунктами "задания"

Только после того, как ты продемонстрируешь наличие RBtree в std::list.

> А я, кажется, начинаю понимать, почему большинство современных игр либо текут памятью, либо частенько завершаются с access violation.

это те которые используют stl, кучу шаблонов, смарт-пойнтеров, и т.п.

Агы-агы, на простых типах. Ты со списками уже прогнал вариант со структурой посложнее? У меня там результаты получились довольно-таки печальные для stl.

При этом кто тебе сказал, что я предлагаю заменять stl чем-нибудь уровня sys/queue.h или sys/tree.h? Там другие радости жизни используются.

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

именно так мы и делаем.

Слушай, ты ныл, что std::map/std::set медленный. Тебе чуть выше показали, что все не так.

Ты принялся ныть о том, что у тебя ж еще память динамически выделяется. Тебе указали, что в STL тоже происходит выделение динамической памяти (и в RBtree, и в list -- grep _List_node).

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

>именно так мы и делаем.

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