elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Искусство программирования без лишней синхронизации
elizarov

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

Например, если вы ставите перед собой задачу сделать множество с операциями добавления и проверки наличия объекта, которое хранит произвольные сравнимые между собой объекты, то, при отсутствии какой-либо дополнительной информации об элементах этого множества, реализация такого множества в лучшем случае будет иметь амортизированное время работы своих операций O(log n). И не надо винить разработчиков STL в том, что std::set работает медленно. Просто изначальная постановка задачи по хранению множества сравнимых объектов поставлена в слишком общем виде. Замечательно, что std::set позволяет быстро найти минимальный (первый) и максимальный (последний) элемент, но на практике это не часто нужно. Вместо этого часто нужно, чтобы добавления и обновления в множестве происходили быстро, чего можно достичь ценой написания хэш-функции для хранимых в множестве объектов, чтобы их можно было положить в std::hash_set.

Аналогично, если вы ставите перед собой задачу сделать LRU-кэш для многопоточного использования, а именно такое множество элементов, которое при превышении некоторого порога размера удаляет наиболее давно использовавший объект, то его реализация просто обязана иметь синхронизацию различных потоков чтения между собой, чтобы решить какой из этих потоков читал элемент раньше другого, то есть чтобы определить какое чтение произошло до другого. И тут совершенно не важно, насколько изобретательны вы будете в реализации этого алгоритма. Вместо обновления списков порядка доступа к объектам в момент чтения, вы можете складывать эти задачи в очередь, как это делают авторы ConcurrentLinkedHashMap, да и вообще придумать массу других ухищрений, но синхронизация между потоками останется, и она будет ограничивать вертикальную масштабируемость вашего кода. Прежде чем тратить время на написание или поиск готового кода, который удовлетворяет этим требованиям, задайте себе вопрос: а оно вам нужно? Действительно ли вам необходимо жестко специфицированное поведение LRU-кэша или всё будет хорошо, если он будет выкидывать почти наиболее давно использовавшие объекты, но не обязательно самые-самые давно использовавшиеся? Действительно ли важно чтобы его размер был жестко ограничен неким n или он может колебаться, скажем, в пределах от n до 2n? Да и вообще, важно ли чтобы он был именно LRU? А может быть подойдет, или даже будет лучше, LFU или другой алгоритм? Чаще всего правильный ответ на эти вопросы "да в общем-то все равно, главное чтобы кэшировало хорошо и быстро работало".

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

Возвращаясь к LRU-кэшу. Осознание фактической гибкости требований на практике предъявляемых к программному алгоритму кэша, открывает огромный простор для выбора высокопроизводительной стратегии его реализации. Например, при каждом доступе к элементу можно лениво (без барьеров и синхронизации) запоминать время последнего обращения к этому элементу (которое совершенно не обязательно должно быть очень точным) и при превышении размера некоего предела подчищать половину наиболее давно не используемых элементов. А более умный алгоритм удаления может быть реализован если подсчитывать число обращений к каждому объекту или другую статистику, создавая синхронизацию только при обращении из разных потоком к одному и тому же объекту в кэше, без необходимости поддержания каких-либо глобальных структур данных типа двусвязных списков для очереди LRU-кэша . Ведь FIFO очередь это тоже жестко специфицированный объект, который часто используется там, где он на самом деле гарантированный first-in first-out порядок не нужен. Но об этом в другой раз.

UPDATE: О некоторых особенностях производительности многопоточного кода можно почитать в заметке "Память, пропускная способность и многопоточность".


  • 1
Во, всячески поддерживаю!

То есть я ровно то же самое думаю, но формулировками не затруднялся, а тут - все сформулировано.

Да. Это презентация которая очень подробно раскрывает тему затронутую мной в заметке Память это новый диск или LinkedList vs ArrayList.

спасибо большое за всю серию!

  • 1
?

Log in

No account? Create an account