Несколько месяцев назад в новостях всплыла потрясающая статья [переводы на Хабре: один и второй] о 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 или вообще ОС со своего образа, а ещё очень удобная панель управления серверами собственной разработки. Обязательно попробуйте!
Автор: Mikhail
