О тонкостях повышения performance на С++, или как делать не надо

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

    Вкратце, задача была такой — есть некий робот на С++, обдирающий HTML страницы, и собранное складывающий в БД (MySQL). С массой функционала и вебом на LAMP — но это к повествованию отношения не имеет.

    Предыдущая команда умудрилась на 4-ядерном Xeon в облаке получить фантастическую скорость сбора аж в 2 страницы в секунду, при 100% утилизации CPU как сборщика, так и БД на отдельном таком же сервере.



    К слову, поняв что они не справляются — «команда крепких профессионалов» из г. Бангалор сдалась и разбежалась, так что кроме горки исходников — «ничего! помимо бус» (С).

    О тонкостях наведения порядка в PHP и в схеме БД поговорим как-нибудь в другой раз, приведу только один пример приехавшего к нам мастерства.

    Приступаем к вскрытию


    image
    Столь серьезная загрузка БД меня заинтересовала в первую очередь. Включаю детальное логирование — и начинаю вырывать на себе волосы во всех местах вот оно.

    Задачи из интерфейса разумеется складывались в БД, а робот 50 раз в секунду опрашивал — а не появилась ли новая задача? Причем данные естественно разложены так, как удобно интерфейсу, а не роботу. Итог — три inner join в запросе.

    Тут же увеличиваю интервал на «раз в секунду». Убираю безумный запрос, то есть — добавляю новую табличку из трех полей и пишу триггера на таблицы из веба, чтобы заполнялось автоматом, и меняю на простой
    select * from new_table where status = Pending
    

    Новая картинка — сборщик по-прежнему занят на 100%, БД на 2%, теперь четыре страницы в секунду.

    Берем в руки профилировщик


    image
    И внезапно выясняется, что 80% времени выполнения занимают чудные методы EnterCriticalSection и LeaveCriticalSection. А вызываются они (предсказуемо) из стандартного аллокатора одной известной компании.

    Вечер перестает быть томным, а я понимаю что работы — много и переписывать придется от души.

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

    Самое время ознакомиться — а что было улучшено до меня?

    Об опасности premature optimizations мысленным лучом


    image
    Видя, что БД загружена на 100%, ребята были твердо уверены, что тормозит вставка в список новых URL для обработки.

    Я даже затрудняюсь понять — чем они руководствовались, оптимизируя именно этот кусок кода. Но сам подход! У нас по идее тормозит вот тут, давайте мы затормозим еще.

    Для этого, они придумали такие трюки:

    1. Очередь асинхронных запросов на insert
    2. Огромная HashMap в памяти, самописная, с giant lock, которая запоминала все пройденные URL в памяти. А так как это был сервер — то его после таких оптимизаций приходилось регулярно перезапускать. Очистку своего кэша они не доделали.
    3. Масса магических констант, например — для обработки следующей партии URL из БД беретсмя не более 400 записей. Почему 400? А подобрали.
    4. Количество «писателей» в БД было велико, и каждый пытался свою часть впихнуть в цикле, вдруг повезет.

    И конечно же много других перлов было в наличии.

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

    void GodClass::PlaceToDB(const Foo* bar, ...) {
    /* тут код с вариантом номер 1, закомментарен */
    /* тут код с вариантом номер 2 - копипаст первого и немного изменений, закомментарен  */
    /* тут код с вариантом номер 3 - еще изменили, не забыв скопировать вариант номер два, закомментарен  */
    ....
    /* тут вариант номер N-1, уже ничего общего не имеет с первым вариантом, закомментарен  */
    // а тут наконец-то вариант рабочий
    }
    


    Что делал я


    image
    Разумеется, все трюки были немедленно выброшены, я вернул синхронную вставку, а в БД был повешен constraint, чтобы отсекал дубли (вместо плясок с giant lock и самописным hashmap).

    Автоинкрементные поля также убрал, вместо них вставил UUID (для подсчета нового значения может приползать неявный lock table). Заодно серьезно уменьшил таблицу, а то по 20К на строчку — неудивительно что БД проседает.

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

    Результат — 15 страниц в секунду.

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

    Регулярные выражения для разбора мегабайтных структурированных файлов — это плохо


    image
    Продолжаю изучать то, что сделано до меня, наслаждаюсь подходом неизвестных мне авторов.

    Ме-то-ди-ка!

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

    • Вырезали все комментарии в HTML
    • Вырезали комментарии в JavaScript
    • Вырезали теги script
    • Вырезали теги style
    • Вынули две цифры из head
    • Вырезали все кроме body
    • Теперь собрали все «a href» и вырезали их
    • В body вырезали все ненужные div и table, а также картинки
    • После чего убрали табличную разметку
    • В оставшемся убирали теги p, strong, em, i, b, г и т. д.
    • И наконец в оставшемся plain text достали еще три цифры

    Удивительно с таким подходом, что оно хотя бы 2 страницы в секунду пережевывало.

    Понятно, сами выражения после их тюнинга я не привожу — это огромная простыня нечитаемых закорючек.

    Это еще не все — разумеется, была использована правильная библиотека boost, а все операции проводились над std::string (правильно — а куда еще HTML складывать? char* не концептуально! Только хардкор!). Вот отсюда и безумное количество реаллокаций памяти.

    Беру char* и простенький парсер HTML в SAX-style, нужные цифры запоминаю, параллельно вытаскиваю URL. Два дня работы, и вот.

    Результат — 200 страниц в секунду.

    Уже приемлемо, но — мало. Всего в 100 раз.

    Еще один подход к снаряду


    image
    Перехожу к результатам нового профилирования. Стало лучше, но аллокаций все еще много, и на первое место вылез почему-то бустовский to_lower().

    Первое, что бросается в глаза — это могучий класс URL, цельнотянутый из Java. Ну правильно — ведь это С++, он по любому быстрее будет, подумаешь что аллокаторы разные. Так что пачка копий и substring() — наше индусское все. И конечно же to_lower прямо к URL::host применять ни-ни — надо на каждом сравнении и упоминании и непременно boost-ом.

    Убираю чрезмерное употребление to_lower(), переписываю URL на char* без переаллокаций вместо std::string. Заодно оптимизирую пару циклов.

    Результат — 300 страниц в секунду.

    На этом закончил, ускорение было достигнуто в 150 раз, хотя еще были резервы для ускорения. И так убил больше 2х недель.

    Выводы


    image
    Выводы как всегда — классика жанра. Используйте инструменты при оценке производительности, не выдумывайте из головы. Ширше (или ширее) пользуйтесь готовыми библиотеками, вместо закатывания солнца вручную.

    И да пребудет с вами святой Коннектий высокий перформанс!
    Поделиться публикацией

    Комментарии 65

      +5
      Нужно везде искать плюсы. Например, нагрузка на сервер была в 150 раз меньше.
        +8
        Полезная нагрузка.
        • НЛО прилетело и опубликовало эту надпись здесь
            +7
            Напомнило

            — Да в вашем Це два креста вообще плюсов нет!
            — Вообще-то есть. Например, я нашел целых два прямо в названии.

            ;-)
              0
              А еще энтропия во Вселенной медленнее увеличивалась.
              • НЛО прилетело и опубликовало эту надпись здесь
                  +1
                  Ну, «мера беспорядка системы», степень неопределённости.
                0
                Есть такое хорошее слово «Энергоэффективность»…
                  0
                  Нужно везде искать плюсы.
                  C++.
                  0
                  Молодец. Но и сам не с того конца подошел, не так ли. Профилирование наше все :)
                    +3
                    Профилирование вещь такая — своеобразная. С ним надо внимательно.

                    Я как на результаты с локом в msvcrt посмотрел — была первая мысль «а не стащить ли с линукса lock-free memory allocator». Хорошо что удержался от этой (в данном случае) глупости и стал дальше смотреть, а то можно было бы сурово засесть за полировку ногтей вместо решения проблемы.

                    По факту я тогда за БД и взялся, чтобы мозги прочистились и результаты профилирования сложились бы в какую-то разумную картинку. Помогло — наутро сообразил, что лечить надо не симптомы.

                    А то статья бы начиналась «и после трех месяцев тупизны и полировки ненужного я догадался посмотреть в профайлере не только первых пять позиций» ;-)
                      +1
                      «а не стащить ли с линукса lock-free memory allocator»

                      Всем все лишь бы стащить.
                      HeapCreate (флаг HEAP_NO_SERIALIZE)
                        +1
                        (пугается)

                        Setting HEAP_NO_SERIALIZE eliminates mutual exclusion on the heap. Without serialization, two or more threads that use the same heap handle might attempt to allocate or free memory simultaneously, which may cause corruption in the heap.

                        Я же имел в виду нечто вот такое, которое вполне себе lock-free thread-safe.

                        Впрочем, таких реализаций несколько, эта мне сейчас первая в гугле попалась.
                          0
                          Ок, виноват, забыл, что под lock-free обычно имеют ввиду thread-safe.
                          Глянул одним глазом код аллокаторов. Используются те же спин-блокировки, что и в EnterCriticalSection, так что один фиг.
                          Но тем не менее, не вижу необходимости в многопоточнй куче для данной задачи, если обработку каждой страницы делать в отдельном потоке, тогда алгоритм парсинга страницы будет отднопоточным и синхронизация внутри алгоритма не потребуется.
                    +1
                    А вы не рассматривали использование string::reserve() для уменьшения реаллокаций? Все таки использование char * может быть чревато ошибками.
                      0
                      Там подавляющее большинство const char*, так что — вряд ли.

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

                      Вот для иллюстрации,

                      class URL
                      {
                      public:
                      	URL(const URL* context, const char* spec);
                      	URL(const char* spec);
                      ...
                      
                      private:
                      	bool parseURL(const char* spec, int start, int limit);
                      	...
                      
                      	std::string protocol;
                      	std::string host;
                      	std::string domainSuffix;
                      	int port;
                      	std::string file;
                      	std::string query;
                      	std::string authority;
                      	std::string path;
                      	std::string userInfo;
                      	std::string ref;
                      };
                      

                      Хотя по факту достаточно хранить саму строчку и пачку указателей на ее части.
                        0
                        Может стоит в тексте сразу написать, что вместо копирования подстроки в отдельную переменную используются указатели на начало и конец подстроки.
                          +4
                          В нормальных реализациях std::string есть copy-on-write, так что при условии что строки не модифицируются, ни какого глубокого копирования не происходит. Единственное известное мне исключение — VC++
                            +2
                            Это как раз был именно он — VC++ ;-)
                              0
                              Можно тогда длинную строку сделать и накодить быстренько класс stringref, который бы как раз работал с подстроками.
                                +1
                                Ну например в STLport строки были тоже не COW. А также в новой Clang'овой libc++ тоже было принято решение делать строки не COW, а с short sring optimization.

                                И COW может привести к плохой производительности в многопоточных программах, потому что счётчик ссылок всё равно надо защищать.

                                Обсуждение и пара ссылок в этом вопросе на StackOverflow
                              0
                              А с юникодными урлами оно как работает?
                                0
                                Емнип URL encoding стандартный никто никуда не разворачивал, так и был %20%2E-бла-бла.
                            +5
                            Мне по тексту показалось «пользуйтесь готовыми библиотеками, вместо закатывания солнца вручную» что ребята тоже придерживались такой логики, только не там где это стоило делать.
                              +4
                              Ширше (или ширее) пользуйтесь готовыми библиотеками, вместо закатывания солнца вручную.
                              Они и пользовались во весь рост.
                              Результат оптимизации хороший, но так много статей «ОНИ vs Я» и так мало «посмотрите какой хороший код, мне бы так»
                                0
                                (разводит руками) ядро линукса что-ли в пример привести, какую-нибудь ветку 2.2, она попроще?

                                А на С++ я с ходу и не подскажу, куда так смотреть можно. WebCore разве что, или Qt на ночь перечитывать.
                                  0
                                  Скорее это просто мысли в слух нежеди претензия.
                                  Очень много в нашей индустрии ругают своих коллег. На эту ситуацию можно посмотреть с другой стороны — заказчики возможно хотели 10 страниц в секунду за дешево, получили только 2, неудовлетворившись пошли уже к более квалифицированному инженеру из Германии (?), месячный оклад которого плюс соц. отчисления, налоги и прочее может прокормить маленькую деревушку в Индии в течении года.
                                  Вопрос часто не стоит в качестве кода, а в том что требуется заказчику и насколько хороший результат он готов оплатить.
                                    +1
                                    Так если б я как та бангалорская деревушка — полгодика бы по-повышал производительность с 1 страницы аж до двух — мне бы тоже платили плошку риса в день, не?

                                    Я ведь не только рис ем, да и местный direktsaft тоже недешев. Вот и приходится отжиматься на совесть, а не с 9 до 6 с перерывом на бассейн и трехчасовой ланч.

                                    Мне кстати некоторые заказчики так и говорят — ну ты Виктор и знаешь толк во вкусной и (не)полезной пище — то лапшу тебе японскую, то сок с кокосовым молоком тайский, а если стейк так рибаи! А я им — да полноте, швайнебратен — вот наш выбор!!!, а рибаи да лапша — это я так, эстетствую ;-)
                                      0
                                      Так если б я как та бангалорская деревушка — полгодика бы по-повышал производительность с 1 страницы аж до двух — мне бы тоже платили плошку риса в день, не?
                                      Просто бы уволили, но платить ниже минимума не смогут по закону.
                                +1
                                Читал вслух! Отличная пятничная статья!
                                  +2
                                  Если вы сидели в комнате один — у меня для вас плохие новости…
                                    +2
                                    Мне повезло со второй половинкой)
                                  0
                                  > SAX — это так сложно
                                  А вы не боитесь что простой HTML не совсем XML или это всетаки был XHTML? А то вдруг найдется вумный дизайнер который забудет закрыть p или li где-то в середине страницы?
                                    0
                                    Судя по тому, что эти теги просто выкидывали регулярками, то в данном случае это не страшно.
                                      +6
                                      Я брал libxml2. У нее есть (были?) именно HTML Chunks.

                                      /*
                                       * Summary: interface for an HTML 4.0 non-verifying parser
                                       * Description: this module implements an HTML 4.0 non-verifying parser
                                       *              with API compatible with the XML parser ones. It should
                                       *              be able to parse "real world" HTML, even if severely
                                       *              broken from a specification point of view.
                                       *
                                       * Copy: See Copyright for the status of this software.
                                       *
                                       * Author: Daniel Veillard
                                       */
                                      

                                      0
                                      хорошо и с юмором — отлично! :)
                                        +1
                                        >>Беру char*
                                        Специально для вас был придуман string::reserve
                                          +1
                                          ->Регулярные выражения для разбора мегабайтных структурированных файлов — это плохо
                                          На собеседовании надо мной слегка хихикали, когда я свои уже имеющиеся решения рассказывал, типа почему не использовал регулярные выражения. То что разница в скорости в более чем в 40 раз, что производительность упирается в парсер на тормозном доступе в нет, это мелочь, башь — вот где сила.
                                          ->Понятно, сами выражения после их тюнинга я не привожу — это огромная простыня нечитаемых закорючек.
                                          Даже если б оно приемлемо работало, регексы слить стоило только за это. Даже строчка, ищущая IP адрес выглядит практически нечитаемо и очень медленно работает, что говорить про более сложные конструкции.
                                            0
                                            Глупый вопрос: а зачем решать подобную задачу на C++? Есть же более подходящие для этого языки. И накосячить в них сложнее.
                                              +1
                                              Вот уж чего не знаю того не знаю — приехало это именно в таком виде. Может напели заказчику о том как они ускорят по сравнению с (например) питоном, и не смогли?
                                              0
                                              >Даже строчка, ищущая IP адрес выглядит практически нечитаемо
                                              а приведите её для примера плз.
                                                –4
                                                Ничего если я?

                                                IPv4 only
                                                (\d(\d(\d)?)?\.\d(\d(\d)?)?\.\d(\d(\d)?)?\.\d(\d(\d)?)?)|(\h(\h)?\.\h(\h)?\.\h(\h)?\.\h(\h)?)
                                                
                                                ;-)
                                                  +2
                                                  такой вариант, но он найдет и 999.999.999.999, зато просто
                                                  \d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}

                                                  или еще короче
                                                  (\d{1,3}\.){3}\d{1,3}
                                                  0
                                                  Что-то вроде вот такого должно быть:
                                                  qr/^((?:(?:1?\d\d?|2(?:[0-4]\d+|5[0-5]))\.){3}(?:1?\d\d?|2(?:[0-4]\d+|5[0-5])))$/
                                                  
                                                  +1
                                                  150 раз разницы в производительности — это они всерьез или может так и задумали эти ребята чтобы потом еще тянуть из заказчика деньги?
                                                    0
                                                    Если всё было так и задумано, то чего же они тогда разбежались?
                                                      +2
                                                      Совесть загрызла ))
                                                    +3
                                                    Сначала я подумал — к чему тут картинки? А оказалось — просто свежие с openclipart понадёргано.
                                                      +1
                                                      Да, я лентяй, я уже признавался ;-)

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

                                                      Вот поясню ход моих мыслей, почему взял именно эти.

                                                      1. Ага — ускоряем производительность, то есть устраняем узкие места, или решаем задачу «в одну трубу втекает, в другую вытекает»). Оно.

                                                      2. Приступаем к вскрытию — то есть проникаем — проникает кто? спецназ — кто там самый был? аватар.

                                                      3. Берем в руки профилировщик — давно шашку в руки не брал — рыцарь — гладиатор.

                                                      4. Опасность — бомба (банально) — бережемся от — о! берегите спички от детей!

                                                      5. Что делал я — я кто? инженер — вот тебе кульман, расписался тут понимаешь!

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

                                                      7. Снаряд — пушка (банально), подход — штанга, брутально. О, мультик вспомнил про Спортландию, странно что там лука не было. Точно — лук со снарядами перекликается, беру!

                                                      8. Святой Коннектий — святой — фольклор — фея. Опа! в стиле техно, отлично!

                                                      Ежик — означает храбрость (С) КВН
                                                      0
                                                      Аплодирую стоя! А какой профилировщик брали?
                                                        +1
                                                        Смеяться на индусами уже как-то стыдно даже. Куда ни глянь: «Need deceloper NOT FROM INDIA/PAKISTAN!»
                                                          0
                                                          > Новая картинка — сборщик по-прежнему занят на 100%, БД на 2%, теперь четыре страницы в секунду.

                                                          Да вы же повысили производительность исходного кода В ДВА РАЗА! Можно было взять отпуск, а по возвращению сдавать первую версию и тут же предлагать начать разработку второй.
                                                            0
                                                            Видимо индусы так и делали, а тут раз! И надо повысить не в два, а в сто, какой уж тут отпуск ;-)
                                                            0
                                                            Оффтоп: картинки с супергероями делали сами с помощью HeroMachine? Я прям заностальгировал, игрался в них в детстве.
                                                            +4
                                                            Что касается парсинга HTML регулярными выражениями, всё уже было сказано здесь, ни отнять, ни прибавить.
                                                              +1
                                                              2 недели на исправления парсинга нескольких цифр из хтмля?
                                                                +1
                                                                Все остальное было скучно и неинтересно, даже и писать-то не о чем. Исправили баги номер… переделали синхронизацию… исправили то то и это… добавили из фичреквеста пункты…

                                                                Обычные будни. Кому интересно читать про «как поправили CSS чтобы могучая закладка в 2 строчки текста не разваливала пол-страницы, баг нумер такой-то»?

                                                                А вот про особенности оптимизации — по крайней мере есть о чем рассказать.
                                                                0
                                                                басня «Индусы и д'Артаньян» :)
                                                                Интересно, какой процент изначального кода остался жив после оптимизации? Не проще ли было выбросить это чудовище и написать с нуля?
                                                                  0
                                                                  Я не так уж и много поменял — задача была не довести до идеала, а чтобы работало. Немного БД, немного обход, убрал странное, вот и все.

                                                                  На самом-то деле, как и в любом проекте с длинной историей, там много чего было понаверчено, описанный кусочек — хорошо если 0.1% кода.
                                                                  0
                                                                  > Автоинкрементные поля также убрал, вместо них вставил UUID (для подсчета нового значения может приползать неявный lock table)

                                                                  Это в какой субд так? В mysql — не так
                                                                    0
                                                                    Вот тут написано следующее:

                                                                    When accessing the auto-increment counter, InnoDB uses a special table-level AUTO-INC lock that it keeps to the end of the current SQL statement, not to the end of the transaction. The special lock release strategy was introduced to improve concurrency for inserts into a table containing an AUTO_INCREMENT column. Nevertheless, two transactions cannot have the AUTO-INC lock on the same table simultaneously, which can have a performance impact if the AUTO-INC lock is held for a long time. That might be the case for a statement such as INSERT INTO t1… SELECT… FROM t2 that inserts all rows from one table into another.

                                                                    Фактически, это означает что все bulk inserts бодренько выстраиваются в очередь на table lock — per statement, и не особенно то и спасает, что лок в журнал не попадает. Емнип fast mutex прикрутили только в 5.1.

                                                                    А теперь представьте себе картинку, что это счастье идет в конкурентных транзакциях в параллель, что в транзакции таких инсертов не один, и получим весьма существенный penalty.
                                                                      0
                                                                      Cool story! =)

                                                                      Оптимизировали, оптимизировали, и наконец выоптимизировали!

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

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

                                                                        Самое читаемое