Несколько месяцев назад в новостях всплыла потрясающая статья [переводы на Хабре: один и второй] о 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 всегда казалась немного медленной, но я предполагал, что причина этого в неэффективном текстовом формате.
(Тучи сгущаются.)
За несколько дней произошло несколько событий:
- Впервые за несколько лет я вернулся к старому коду Erizo, чтобы устранить ошибку фокусировки на macOS
- Опубликовали статью про GTA Online
- Из последовавшей дискуссии я узнал, что
парсинг может быть квадратичным из-за многократных вызовов sscanf - Я заметил, что загрузка 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 или вообще ОС со своего образа, а ещё очень удобная панель управления серверами собственной разработки. Обязательно попробуйте!
