Русский
Русский
English
Статистика
Реклама

Sscanf

Перевод Ошибку Rockstar может совершить каждый (и я тоже)

12.06.2021 16:15:59 | Автор: admin

Несколько месяцев назад в новостях всплыла потрясающая статья [переводы на Хабре: один и второй] о Grand Theft Auto Online.

Советую прочитать статью целиком, но если вкратце, GTA Online имела внезапно квадратичную производительность при парсинге большого JSON-блоба (из-за многократных вызовов strlen); после устранения этой ошибки время загрузки уменьшилось почти на 70%.

Это вызвало оживлённые дискуссии: в этом виноват C? Или, возможно, "web shit"? Или капитализм и его стимулы?

Однако все были солидарны в одном: они бы ни за что не написали подобной глупости.

(Вы уже чувствуете, что надвигается?)


Одним из моих побочных проектов является высокопроизводительная программа для просмотра 3D-моделей под названием Erizo.


Благодаря продуманному коду она открывает 97-мегабайтный двоичный файл STL на Macbook Pro 2013 года всего за 165 миллисекунд. Это потрясающая скорость.

Из соображений совместимости я написал небольшой парсер и для ASCII STL.

ASCII STL это формат обычного текста с плохой спецификацией, который выглядит вот так:

solid cube_corner          facet normal 0.0 -1.0 0.0            outer loop              vertex 0.0 0.0 0.0              vertex 1.0 0.0 0.0              vertex 0.0 0.0 1.0            endloop          endfacet          facet normal 0.0 0.0 -1.0            outer loop              vertex 0.0 0.0 0.0              vertex 0.0 1.0 0.0              vertex 1.0 0.0 0.0            endloop          endfacet          ...endsolid

Я написал чрезвычайно надёжный парсер, добавив в комментарий такое описание:

/*  Самый либеральный парсер ASCII STL: игнорирует всё, кроме *  слова 'vertex', а затем одно за другим считывает три значения float. */

Загрузка ASCII STL всегда казалась немного медленной, но я предполагал, что причина этого в неэффективном текстовом формате.

(Тучи сгущаются.)



За несколько дней произошло несколько событий:


Вот логи загрузки 1,5-мегабайтного ASCII STL метками времени (в секундах):

[erizo] (0.000000) main.c:10      | Startup![erizo] (0.162895) window.c:91    | Created window[erizo] (0.162900) window.c:95    | Made context current[erizo] (0.168715) window.c:103   | Initialized GLEW[erizo] (0.178329) window.c:91    | Created window[erizo] (0.178333) window.c:95    | Made context current[erizo] (1.818734) loader.c:109   | Parsed ASCII STL[erizo] (1.819471) loader.c:227   | Workers have deduplicated vertices[erizo] (1.819480) loader.c:237   | Got 5146 vertices (7982 triangles)[erizo] (1.819530) loader.c:240   | Waiting for buffer...[erizo] (1.819624) loader.c:326   | Allocated buffer[erizo] (1.819691) loader.c:253   | Sent buffers to worker threads[erizo] (1.819883) loader.c:258   | Joined worker threads[erizo] (1.819887) loader.c:279   | Loader thread done[erizo] (1.821291) instance.c:32  | Showed window

С момента запуска до отображения окна прошло больше 1,8 секунды!

Посмотрев на парсер ASCII свежим взглядом, я увидел, что причина очевидна:

    /*  The most liberal ASCII STL parser:  Ignore everything except     *  the word 'vertex', then read three floats after each one. */    const char VERTEX_STR[] = "vertex ";    while (1) {        data = strstr(data, VERTEX_STR);        if (!data) {            break;        }        /* Skip to the first character after 'vertex' */        data += strlen(VERTEX_STR);        for (unsigned i=0; i < 3; ++i) {            SKIP_WHILE(isspace);            float f;            const int r = sscanf(data, "%f", &f);            ABORT_IF(r == 0 || r == EOF, "Failed to parse float");            if (buf_size == buf_count) {                buf_size *= 2;                buffer = (float*)realloc(buffer, buf_size * sizeof(float));            }            buffer[buf_count++] = f;            SKIP_WHILE(!isspace);        }    }

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

Да, я совершил ту же ошибку, что и программисты, работавшие над GTA Online: написал внезапно квадратичный парсер!

Замена вызова sscanf на вызов strtof снизила время загрузки почти в 10 раз: с 1,8 секунды до 199 миллисекунд.

[erizo] (0.000000) main.c:10      | Startup![erizo] (0.178082) window.c:91    | Created window[erizo] (0.178086) window.c:95    | Made context current[erizo] (0.184226) window.c:103   | Initialized GLEW[erizo] (0.194469) window.c:91    | Created window[erizo] (0.194472) window.c:95    | Made context current[erizo] (0.196126) loader.c:109   | Parsed ASCII STL[erizo] (0.196866) loader.c:227   | Workers have deduplicated vertices[erizo] (0.196871) loader.c:237   | Got 5146 vertices (7982 triangles)[erizo] (0.196921) loader.c:240   | Waiting for buffer...[erizo] (0.197013) loader.c:326   | Allocated buffer[erizo] (0.197082) loader.c:253   | Sent buffers to worker threads[erizo] (0.197303) loader.c:258   | Joined worker threads[erizo] (0.197306) loader.c:279   | Loader thread done[erizo] (0.199328) instance.c:32  | Showed window



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

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

(Очевидно, мораль истории такова: не используйте sscanf для многократного парсинга одиночных токенов из начала строки; уверен, у вас всё будет нормально, если вы просто избежите этого.)



На правах рекламы


VDSina предлагает мощные и недорогие VPS с посуточной оплатой. Интернет-канал для каждого сервера 500 Мегабит, защита от DDoS-атак включена в тариф, возможность установить Windows, Linux или вообще ОС со своего образа, а ещё очень удобная панель управления серверами собственной разработки. Обязательно попробуйте!

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru