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

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

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

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

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

---

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

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

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

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

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

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

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

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

---

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

• Впервые за несколько лет я вернулся к старому коду Erizo, чтобы устранить ошибку фокусировки на macOS ^[11]
• Опубликовали статью про GTA Online
• Из последовавшей дискуссии я узнал, что парсинг может быть квадратичным из-за многократных вызовов sscanf ^[12]
• Я заметил, что загрузка 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 ^[13] не указана её временная сложность, поэтому это особо хитрый пистолет для выстрела себе в ногу, и мне кажется, что не один я блуждал во тьме невежества.

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

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

---

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

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

^[14]

Автор: Mikhail

Источник ^[16]