Банановые шкурки

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

Сижу я, смотрю на код “сетевого движка”. Там обертка над сокетами, которая есть суть std::vector<byte>. С одной стороны мы асинхронно добавляем сообщения ( которые тоже суть std::vector<byte> ), к другой стороне этого вектора присосался сокет, который не менее асинхронно выбирает сообщения и посылает по 256 байт на удаленный сервер. Пошел ругаться с серверными программистами.

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

Моя эскапада была прервана в том духе, что-де “у тебя самого в рендере push_back в std::vector без предварительного резервирования”. Я был вынужден свои излияния по поводу отстойности stl прекратить, ибо таки-да. Есть такое у меня в рендере. Пробормотал я что-то по поводу “драфтовости” кода и удалился.

Стал пристально вглядываться в свой замечательный код рендера. Там действительно используются std::vector’а. В двух местах. В первом месте я собираю запросы на occlusion cull. Собираю окклюдеры и ресиверы в очередь, сортирую, потом собственно считаю видимость.

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

Промежуточным контейнером  рендер-примитивов выступает std::vector. Добавление производится с помощью push_back. А сортировка в обоих случаях производится по целому числу, вполне хватает шестнадцати бит.

Реализация STL у нас своя, местами забавная. Смотрю в код, вижу что sort делает внутри new и выполняет сортировку слиянием.

Убиваю эту дурацкую сортировку с аллокацией, делаю такую же, как и в партиклах. Корзиночную, два прохода по 256 корзинок. Убиваю std::vector, вставляю фиксированный массив на 16 тысяч рендер-примитивов.

Перекомпилирую… Удивленно вижу, что fps поднялся ровно в полтора раза в debug версии. Ценой сотни что ли строк кода. В release не так значительно, но все одно – сильно быстрее. В самой обычной игре скорость в полтора раза поднялась, не в синтетических тестах.

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

  • http://blog.fxposter.org/ FX Poster

    Теперь опять пойдешь к серверным программистам? :)

  • http://www.vogster.com raskolnikov

    неудивительно, что у нас геймдев в таком зажопии…
    кстати, узнается, Нивал-стайл – жестяк :)

  • dDIMA

    Обертка над сокетами на std::vector. Возможно, оно даже и живет. Вопрос в том, насколько оно хорошо написано. Ну то есть я верю в то, что тут можно пройтись и не поскользнуться. Но если оно не дай бог, в несколько потоков аксессицца…..

  • ViT

    афтар прав, на низком уровне с сокетами так работать низя! В том что описано дан довольно простой пример того как сокеты работают.У меня в проекте требуется пересылать и получать в несколько потоков обернутые мылом xmlзапросы и получать в ответ оные же. Первые реализации “по учебнику” работы с носками показали, что даже используя штатные средства и то возникают проблемы. Позже я переписал работу с носками таким бразом чтобы организовать выборку из стека по 1 байту, что и дало приемлемый результат.

  • belaz

    Есть аналогичное указанному в посте. Тоже сообщения. Только не сеть, а RS232 (AKA COM). Использует std::deque.
    Правда ситуация другая – всё гораздо медленнее, но успешно и надёжно работает, под разными ОС, разными компиляторами, продолжительное время. Правда – код однопоточный, стабильный и проверенный на разных конфигурациях.

    Однако :-), после переноса всего на vs 2005 в отладке stl показал ошибки работы с итераторами….. Хорошо – на практике не проявлялось никак… (А может, что и плохо – как посмотреть…)

    Я к тому, что нельзя кого-попало пускать к такому коду, что накладывает вполне определённые требования к персоналу. И в реальной жизни и конкретной исторической ситуации может приводить к интересным организационным “загогулинам”…

  • $ergi0

    а как лучше выкручиваться, когда 16 тысяч может и не хватить, а памяти слишком много бы жрать не хотелось?
    писать подобие деки с выделением блоками кила по 4?

  • shodan

    $ergi0,
    зачем деку? Тупо вектор, с большим начальным размером (см. 16K) и разумеется сортировку без временных аллокаций.

    Но кстати в игре заранее известно, что 16K примитивов хватит: это очень много, в разы больше разумных пределов.

  • $ergi0

    ну, случай когда заведомо известно сколько хватит – он не интересен :)

  • $ergi0

    пока самое адское, что я видел из использования стл – считывание сортированной последовательности из файла в map. наверно можно что-то похуже придумать.

  • dDIMA

    2 $ergi0
    > пока самое адское, что я видел из использования стл…
    Я видел в рабочем коде следующее (причем разработчики искренне удивлялись моему полуобморочному состоянию):
    void func(int n)
    {
    std::vector names;
    names.push_back(“Hero”);
    names.push_back(“Enemy”);
    names.push_back(“Boss”);
    callSubFunc(names[n].c_str());
    }

  • Vitaly

    Дело в том, что “банановая шкурка” не сразу такой становится.
    Если пишется клиентская часть сетевого движка с маленькой нагрузкой, то нечего усложнять код с целью достижения совершенства. К примеру, сетевые peer-2-peer движки Демиургов 1, 2 и Блицкрига 1 внутрях были N^2 по кол-ву peer-ов.

    А вот сортировка слиянием в базовой библиотеке, использующейся по всему проекту – ахтунг в “промышленных масштабах”.

  • Neko-Lich

    Тема банановых шкурок не раскрыта

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

    > Реализация STL у нас своя, местами забавная
    Прекрасный пример банановой шкурки “нестандартная стандартная библиотека” :D

  • http://www.sdl.ru TSS

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

    2dDIMA: жестоко они тебя подставили…

  • http://__vortex__.livejournal.com vortex

    > Я видел в рабочем коде следующее
    Пойду выпью валеряночки :) Кстати нечто подобное, с завидным постоянством, творится во многих проектах. Я как-то рейд по нашему коду делал (небыло у нас code review, к сожалению) исправлял похожие случаи (передача строк по значению, вектор как локальная переменная, и др.). Жуткое было время. :)

  • dDIMA

    Кстати, только что заметил, что в примере кода чуть повыше движок форума вырезал темплейтный параметр у std::vector. Для полноты счастья уточню, что это был std::string.

  • $ergi0

    2 dDIMA
    Тут как мне кажется всё таки от общей неграмотности, чем от незнания именно СТЛ :) Но всё равно мощно.

  • http://-winnie.livejournal.com _winnie

    А нет такого, что уже отлаженые .cpp/либы – компилируются с минимальной оптимизацией даже в Debug-режиме всей игры? Со включенными ассертами, stack-frame, и прочее, но не с тормознутым /Od.

  • http://kss.livejournal.com/ Joes

    > Жуткое было время. :)
    Да ладно тебе! Романтика! ;-)

  • avs313

    >пока самое адское, что я видел из использования стл – считывание сортированной последовательности из файла в map.
    а как правильно делать? последовательность перемешивать или как?

  • $ergi0

    Да не надо мапом пользоваться вообще здесь, пусть она хоть трижды несортированная.

  • http://kss.livejournal.com/ Joes

    Вы не поверите, но если сравнивать два варианта:
    1. std::vector, потом std::sort, потом проход по полученному вектору
    2. std::set и сразу в него кормить, потом проход по полученному множеству
    на одинаковом наборе строк (в количестве 1000000 штук) дает следующие результаты:

    Vector: 2688.000000, Set: 2250.000000
    (это получено с помощью GetTickCount())

  • lenik

    [quote]
    > Стал говорить, что stl в низком уровне омерзительна, как размокший окурок в писсуаре.
    [...]
    > Реализация STL у нас своя, местами забавная.
    [/quote]
    Единственная полезная информация, почерпнутся из данного поста заключается в том, что “своя, местами забавная реализация СТЛ… омерзительна, как окурок в писсуаре”.

    СТЛ — это инструмент. Тупой и простой, как молоток. Пригодный для забивания гвоздей. С его помощью также можно принимать роды, обжимать RJ45 или полоть грядки. Но для этой цели он пригоден гораздо меньше. И вдвойне непригоден для этого “самодельный молоток”, типа, резиновая киянка или там кувалда с выскакивающей ручкой.

    И все проблемы от того, что народ либо не разобравшись начинает весь мир воспринимать, как незабитый гвоздь, а когда “вдруг” возникают проблемы (от того, что мир, собака, на самом деле далеко не гвоздь), пытается ещё и изобрести свой молоток, чтобы забить всё навсегда и окончательно.

    И правильными выводами должны быть:
    1. не пытайтесь, ради всего святого, писать на коленке свою версию СТЛ, свято веря, что она будет хоть в чём-то лучше уже существующих
    2. знайте, какие ограничения накладывает использование стандартной библиотеки и не пытайтесь применять её там, где это нецелесообразно

  • Sergei_am

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

    >>и не пытайтесь применять её там, где это нецелесообразно
    Ну, а ето настолько абстрактно, что аж непрактично как правило, имхо.
    Я бъ сказал, что объчно есть антипаттернъ, которъе можно распознавать даже на етапе их создания и думать второй раз, типа тех же per-frame векторов, per-frame map/set в виде локальнъх переменнъй, создание идентификаторов в string, опять же per-frame и подобное.

    Вот только, КПД создание такого кода настолько въсоко, что может искусить каждого… :)

  • Dmitry Tyurev

    lenik
    >>что она будет хоть в чём-то лучше уже существующих

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

  • Sergei_am

    Joes
    >>Вы не поверите, но если сравнивать два варианта:
    Чему тут не поверить, я могу придумать пример, где вектор+сортировка может слить в сколько раз хочеш set-у… :)

  • http://kss.livejournal.com/ Joes

    Sergei_am: я привел пример относительно примера с сортировкой последовательности из файла. Так что лучше сразу в set, чем сортировать потом в памяти. С map’ой (хоть и не тот контейнер, да), результаты очень похожие.

  • Sergei_am

    Joes:
    Я опять повторюсь, ето очень зависит от самой последовательности. И тут и там n.logn операций, но размер множества во время работъ программъ разное, т.е. у set-a оно меньше заведомо, т.е. так сказать константа перед n.logn меньше. Ничего странного, имхо.

  • http://kss.livejournal.com/ Joes

    Sergei_am: я вообще это все к “Да не надо мапом пользоваться вообще здесь, пусть она хоть трижды несортированная.” писал. Разве что map на set поменял, ибо второе значение не надо.

  • $ergi0

    Joes: без кода мягко говоря неубедительно.

  • lenik

    Sergei_am> Сходу она лучше тем, что явно будет более узкоспециализированна, со всеми последствиями.

    Как только я слышу слово “узкоспециализирована”, я сразу хватаюсь за пистолет. Потому, что обычно это означает “работает только в присутствии автора, а если чуть изменить условия/параметры — падает вдребезги”.

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

    Это не абстрактно, это написано в любой приличной книжке по СТЛ, где 80% места уделяется не рассказу о классах/методах, а именно рассказу о требованиях по памяти, сравнению их производительности и подробностям применения (или неприменения). В-общем, “читайте книжки — они рулез” (с) Перцев

  • Sergei_am

    lenik:
    >>Как только я слышу слово “узкоспециализирована”, я сразу хватаюсь за пистолет.
    Слово, как слово. Посмотри в словаре его смъсловое значение. Узкая специализация создала подлодки скажем, которъе намного лучше плавают под водой чем корабли…

    >>Это не абстрактно, это написано в любой приличной книжке по СТЛ, где 80%
    Ето правило не приносит ни одного конструктивного бита знания, т.к. еще надо понять где нецелесообразно, как нецелесообразно, почему и т.д. А ето и есть суть етого знания. Т.е. самому правилу грош цена, ето явнъй труизм и мне лично такое читать вообще неинтересно.

  • IronPeter

    lenik,

    У нас какой-то старый STLPort. Рипнутый ( выброшены reverse iterators & allocators ), чтобы компилировалось быстрее. Никто на коленке ее не писал. Так что пункт первый он конечно правильный, есть много промышленных реализаций STL, можно выбирать. Есть много форков с разными забавными свойствами. Мысль разработчиков сильно гуляла по древу со времен Степанова. 14 лет прошло уже с первой версии.

    К сожалению, иногда приходится хакать и рипать стандартную библиотеку. Скажем, для inplace загрузки. Фиксированная версия STL в билде игры – это не такое уж и плохое решение.

    Кроме STL часто нужны более другие контейнеры. Нужен inplace – это раз. Нужны аналоги boost::array – это два. Нужно что-то более другое, чем STL аллокаторы. Отсюда и плясать.

    Концепция STL от EA – она правильная в чем-то.

  • lenik

    IronPeter,

    Концепция СТЛ в моём понимании (возможно, неверном =) — это коллекция кода, который надоело писать самому из раза в раз, изобретая велосипед. Их есть много разных, можно выбирать, расширять и углублять. Но говорить, что СТЛ — это банановая шкурка, и отказываться от неё совсем — это back to square one, опять к изобретению велосипеда — несерьезно.

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

  • IronPeter

    Каждая возможность написать код – это банановая шкурка. Каждая строчка код – гвоздик в гроб проекта.

    Команды, что “начинающих”, что “продолжающих”, что “кончающих” девелоперов – они одинаковы. Массу кода пишут джуниоры. Сениоры заняты. Они не пишут код. Они составляют планы. По этим планам джуниоры пишут мажор-фичи со сверхсветовой скоростью. Сверхсветовые скорости запрещены теорией Эйнштейна. Те сениоры, которые не составляют планы – впали в маразм и хачат PS3 по ночам. На работе делают фичи примерно за 3 джуниоров. Плодят мусер. Роняют молотки на ноги.

    Есть корпоративное легаси. Тот же малостандартный STL со своими граблями. Умные указатели. Кодогены. Конвенции, стандарты. Неписаные на wiki правила.

    В этой обстановке в выборе между джуниором со знанием boost и джуниором без знания boost я выберу второго.

  • Dmitry Tyurev

    > опять к изобретению велосипеда — несерьезно.

    Конечно, несерьёзно! Более того – глупо. :) Кстати, например, в EA сидят глупые и несерьёзные люди. А также в Valve. И авторы Ogr’a туда же. Они все непроходимые бездари, не знают, что СТЛ это круто и всё лезут своими кривыми ручёнками, ковыряют что-то! :) Ну, ничего, хотя весь мир во мгле, зато есть lenik, который не изобретает велосипед, а точно знает, как надо. ;-)

  • cppg

    Значит, нефиг юзать STL даже в драфтовом коде. А то такой код обычно доживает спокойно до релиза %)