На собеседованиях с программистами я часто прошу их написать простую программу, подсчитывающую частотность слов в текстовом файле. Это хорошая задача, проверяющая множество навыков, а уточняющие вопросы позволяют зайти на удивление глубоко.
Один из моих уточняющих вопросов такой: «Что является узким местом производительности вашей программы?» Многие отвечают что-то типа «считывание из входящего файла».
На самом деле, написать эту статью меня вдохновил ответ на чей-то вопрос в Gopher Slack: «Я заметил, что много дополнительной работы приходится на разделение строки и тому подобное, но обычно всё это намного быстрее ввода-вывода, поэтому нас это не волнует».
Я не стал спорить… и пока не
проанализировал производительность задачи с подсчётом слов, думал так же. Ведь всех нас этому учили, правда? «Ввод-вывод — это медленно».
Но это больше не так! Дисковый ввод-вывод мог быть медленным 10-20 лет назад, но 2022 году
последовательное считывание файла с диска выполняется очень быстро.
Насколько же быстро? Я протестировал скорость чтения и записи моего ноутбука при помощи
этой методики, но с параметром
count=4096
, то есть с чтением и записью 4 ГБ. Вот результаты, полученные на моём Dell XPS 13 Plus 2022 года с накопителем Samsung PM9A1 NVMe и Ubuntu 22.04:
Разумеется, системные вызовы относительно медленны, но при последовательном чтении или записи один syscall нужно выполнять через каждые 4 КБ или 64 КБ (или другую величину, в зависимости от размера буфера). А ввод-вывод по сети по-прежнему медленный, особенно в нелокальной сети.
Так что же
является узким местом в программе, считающей частотность слов? Это обработка или парсинг входящих данных, а также соответствующее распределение памяти: разбиение входящих данных на слова, преобразование в нижний регистр и подсчёт частотностей при помощи таблицы хэшей.
Я модифицировал свои программы подсчёта слов на Python и Go так, чтобы фиксировать время разных этапов процесса: считывания входящих данных, обработки (медленная часть), сортировки по самым частым и вывода. Потом выполнил проверку на текстовом файле размером 413 МБ, то есть на приличном объёме входящих данных (100 конкатенированных копий
текста Библии короля Якова).
Ниже показаны усреднённые результаты трёх лучших прогонов в секундах:
Сортировка и вывод занимают пренебрежимо мало времени: так как входящие данные состоят из 100 копий, количество уникальных слов относительно невелико. Примечание: это приводит к ещё одному уточняющему вопросу на собеседовании. Некоторые кандидаты говорят, что узким местом будет сортировка, потому что её сложность O(N log N), а не обработка входящих данных, сложность которой O(N). Однако здесь легко забыть, что мы имеем дело с двумя разными N: общим количеством слов в файле и количеством уникальных слов.
Внутренняя работа
версии на Python сводится к нескольким строкам кода:
content = sys.stdin.read()
counts = collections.Counter(content.lower().split())
most_common = counts.most_common()
for word, count in most_common:
print(word, count)
На Python запросто можно выполнять построчное чтение, однако это немного медленнее, поэтому здесь я просто считываю весь файл в память и обрабатываю его за раз.
В
простой версии на Go используется тот же подход, однако стандартная библиотека Go не содержит
collections.Counter
, поэтому выполнять сортировку «самых частых» нам нужно самостоятельно.
Оптимизированная версия на Go существенно быстрее, однако и гораздо сложнее. Мы избегаем большинства распределений памяти, выполняя преобразования в нижний регистр и разделяя текст на слова
с замещением. Это хорошее эмпирическое правило для оптимизации кода с интенсивными вычислениями: снижайте количество распределений памяти. Информацию о том, как это профилировать, читайте в моей
статье об оптимизации подсчёта количества слов.
Я не показал оптимизированную версию на Python, потому что сложно оптимизировать Python ещё сильнее! (Время снизилось с 8,4 до 7,5 секунды). Код уже и так быстр, потому что базовые операции выполняются в коде на C; именно поэтому часто не важно, что «Python медленный».
Как видите, дисковый ввод-вывод в простой версии на Go занимает всего 14% от времени выполнения. В оптимизированной версии мы ускорили и чтение, и обработку, и дисковый ввод-вывод занимает всего 7% от общего времени.
Какой же я делаю вывод? Если вы обрабатываете «big data», то дисковый ввод-вывод, вероятно, не будет узким местом. Даже поверхностные измерения дадут понять, что основное время тратится на парсинг и распределение памяти.
Естественно, что если 400 мегов зашарашить в оперативную память и там начать из них устраивать и реорганизовывать всякие коллекции, то производительность будет небольшой и по времени, и по памяти. А если 400 гигов, так вообще всё навернётся. Неверной дорогой идёте, товарищи.
Там в английской статье, на которую стоит ссылка, показано, что grep работает в 50 раз быстрее.
работает быстрее по сравнению с чем?
Note that
grep
andwc
don’t actually solve the word counting problem, they’re just here for comparison.Чтоб сосчитать слова, в подавляющем большинстве случаев достаточно одного прохода по тексту, что и делают grep и wc. И пары массивов – например, счётчик частот, индексируемый 16- или 24-разрядным самым тупым хешем, и ссылки на сами слова (или их позиции в файле, если не хотим читать файл целиком). Только для разрешения коллизий хеша придётся делать второй проход.
Я недавно реально подофигел, что grep работает даже быстрее индекса в mysql
Тоесть на моих данных выгоднее выгрузить спискок в файл и пройти grep, чем искать с использованием индекса в памяти.
grep реально быстро работает.
Думаю потому, что индексы оптимизированы для совпадения слева. А вы скорее всего ищете слова в центре и тогда индекс превращается в просто сокращенную версию таблицы, которую СУБД и перебирает — что, конечно, лучше перебора исходной полной таблицы, но сильно хуже поиска по двоичному дереву. Grep, подозреваю, выигрывает потому, что читает данные бОльшими порциями относительно mysql.
Неа, слева, от 3 до 8 символов, только цифры. Таблица в 30млн.
Смотря какой Индекс Вы имели в виду
Поверхностное гугление показывает, что производительность чтения из кэша процессора составляет порядка терабайта/с, производительность чтения из RAM порядка 40ГБ/с. Т.е. диск всё ещё на 3 порядка отстаёт от кэша примерно как и в старые добрые времена, и на полтора от RAM.
Сразу вопросы к эксперименту: у дисков есть свои кэши, последовательные прогоны в поисках лучшего наверняка осядут в этих кэшах и результаты будут уже не те, как по первому разу. Также наверно и в RAM после первого эксперимента прочитанное с диска частично тоже где-то закэшируется.
Диски-то тоже разные. Конечно, у большинства сейчас SSD в новейших макбуках. Но HDD тоже встречаются пока еще. А еще сетевые диски бывают. Например, в AWS облаке GP2 диски вообще хз что из себя представляют - там вполне может быть файл размазан по нескольким сетевым дискам и кроме вас еще 200 серверов с ними сейчас работают и время доступа будет непредсказуемым и нелинейным.
Позвольте уточнить - современные м.2 ssd способны читать последовательные данные со скоростью 7 Гб/секунду. ОС, файловая система и т.п. могут накладывать оверхед, но я предлагаю отталкиваться именно от теоретической верхней границы, как и для 40 Гб/сек для оперативной памяти.
Мне кажется, на старых компьютерах с жёсткими дисками соотношение скоростей было совсем не таким.
Переход от жёстких дисков к ssd m.2 выглядит действительно прорывом - раньше по sata нельзя было передавать больше 550 Мегабайт в секунду (на практике диски достигали 100-150 мегабайт в секунду при последовательном чтении), а рандомное чтение вызывало задержки, измеряемые в миллисекундах.
Сравнить 150 мегабайт/сек старого жёсткого диска и 7 гигабайт нового ссд - разница полтора порядка.
По оперативной памяти тоже есть прогресс, но не такой радикальный
Ну вы и сравнили - старую практику и современный теоретический потолок
Ну, из "ввод/вывод" в статье рассмотрен только ввод. Да и, в общем-то, мизерного объёма данных)
Что касаемо основного вопроса («Что является узким местом производительности вашей программы?), то единственный правильный ответ тут: без бенчмарков разговор бессмысленен :)
Очень спортное утверждение, все еще не подтвержденное ничем.
С точки зрения быстродействия процессора и чтение из случайного места ОП - медленное так то. И есть методики (типа ESC или векторизации), которые наглядно демонстрируют, насколько.
Поэтому то, насколько быстрее стали диски, все еще не опровергает утверждение, что I/O медленное.
Первое апреля? Правда смешно! Особенно когда увидел что это в хабах "Совершенный код" и "Клиентская оптимизация"
Хорошо бы еще помнить, что помимо throughput есть и latency. И совершенно различные паттерны доступа.
Есть очень интересная страничка с интерактиными измененниями latency по годам.
На одной работе было такое приложение. Есть хранилище с несколькими миллиардами документов, надо их проиндексировать. Надо получить порцию данных (20000 документов), декодировать JSON, взять поле, декодировать Base64, декодировать JSON еще раз, взять список полей, сгенерировать XML, вывести в STDOUT, который читает индексатор. Обработка на PHP. Сеть работала быстро, вывод в STDOUT тоже, тормозил PHP. Сделали много параллельных процессов по числу ядер на сервере со сбором данных в главном процессе и запуск с небольшой задержкой, чтобы не все сразу лезли в сеть. Тогда стало упираться в работу индексатора.
Когда много данных и работы со строками, сеть перестает быть узким местом.
413Мб - это даже близко не BigData. Начали бы хотя бы с 413Гб - да и слов уникальных бы побольше (для теста можно брать не слова из текста а парные сочетания всех слов друг с другом, ну и книжек заодно не одну взять а 1000). А так вообще-то боле менее серьёзный уровень BigData обозначился бы на 413Тб или 413Пб - но это в "домашних" условиях уже моделировать очень сложно. Но и 413Гб началась бы уже совсем другая кухня - где текст так просто в память целиком не загнать. А с большим количеством слов (или как я предложил - парных словосочетаний из 1000 книг - ну или программно сгенерированный источник с миллиардами таких вот "сочетаний") началась бы ещё и проблема с хранением статистического массива. Да BigData - это не шутки, там совсем другие законы и подходы. Но, у Вас в компании видимо совсем не уровень BigData раз это всё для Вас не важно.
И как можно говорить об оптимизации и BigData, когда нет параллельной обработки (тем более то на Go) - а там сразу ещё и задачи конкуренции возникают (что тоже на собеседовании проверять неплохо бы).
Да и если говорить о файле (даже если он один - что даже интереснее, но в BigData такое бывает редко) очень большого объёма - то даже его чтение можно было бы немного распараллелить - раз ввод-вывод занимает почти на порядок меньше времени чем обработка!
И всё надо асинхронизировать!
А уж сколько оптимизационных финтов при обработке пропущено - да хотя бы то, что слова сразу можно было бы разделить по просто определяемым группам - и делать поиск только в нужной группе (например - поделив их по длинам, но можно и по другим критериям, например просто по первой букве, или вычислять простой числовой хеш и по нему определять подгруппу) - в общем организовать картотеку - а не единый массив. С выделением памяти тоже много чего упущено!
Как говорится, +1
Более того, для сетевого ввода это тоже может быть верно.
Пример – чтение таблицы целиком из PostgreSQL (SELECT * FROM <TABLE>) в Perl при помощи fetchall_arrayref. Если просто читать данные, то память под массив с результатом выделяется один раз, и чтение занимает примерно Х времени. А если попытаться эти данные обрабатывать, передавая полученный массив аргументом в какую-нибудь функцию, то уже 5×Х
Как показывает моя практика, чаще бывает так, что программисты в принципе не понимают как работает та или иная вещь на низком уровне. Как пример тоже самое выделение памяти, когда и в какой момент память копируется или возвращается по ссылке. При этом на ревью боятся если встречают 3 вложенных цикла и говорят что это слишком дорого, не приводя аргументов)
А почему вы называете этих людей программистами?
Как-то странно выносить какие-то суждения о программистах вообще, приводя в пример людей, очевидно не являющихся квалифицированными программистами.
Не все же системные программисты, и не все даже знакомы с с Си и C++. Да и под разными средами исполнения память выделяется по-разному. "Управляемые приложения", в т.ч. скриптовые вообще создавались так, чтобы программисты меньше задумывались над этим вопросом. Хотя, вот C# - например не так уж прост вопросах выделения памяти (чем, скажем Java), особенно с версии NET CORE 3 - но там своя кухня и нюансы. И не надо говорить - что люди разрабатывающие приложения на высокоуровневых ЯП - не программисты, раз не углубляются в особенности памяти. Они да - не системные, а прикладные программисты. И современные ЯП развиваются так, чтобы разработка приложений на них шла так, чтобы больше думать о прикладной логике, чем о низкоуровневых заморочках. И даже BigData идёт путём к тому, чтобы меньше думать о нюансах той или иной низкоуровневой прослойки платформы, и больше об оптимизации логики обработки больших массивов. Мне трудно представить каким была бы разработка сайтов или прикладных приложений баз данных, если бы программистам приходилось думать о тонкостях выделения памяти