Откуда такая скорость у mold?
#опытным

На графиках с предыдущего поста видно, что mold работает чуть ли не на порядок быстрее, чем ld или gold. За счет чего они так сильно ускорили линковщик?

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

⚡️Самая мякотка - работа в параллель. C единицами трансляции мы интуитивно понимаем как параллелить: каждому вычислительному юниту даем обрабатывать свою TU. С линковкой конечно сложнее, но тоже решаемо. Линкерам на вход подается большое число однотипных данных, которые нужно обработать, и между которыми не так уж и много связей. Поэтому эту гору данных можно разбить на поток задачек, которые независимо можно выполнять на большом количестве потоков.

Однако рано или поздно наступит этап reduce, когда нужно собирать данные воедино. Для этого они используют потокобезопасную мапу, которая хранит отображение названия символа на сам объект символа. В качестве такой мапы mold использует Intel TBB's tbb::concurrent_hash_map. Крутая либа на самом деле, одно из лучших решений для высокопроизводительных потокобезопасных вычислений.

⚡️В качестве аллокатора используют mimaloc. Cтандартный malloc из glibc плохо масштабируется на большом количестве ядер, поэтому они решили попробовать сторонние решения. Среди jemalloc, tbbmalloc, tcmalloc и mimalloc - mimalloc от Microsoft
показал наилучшую производительность.

⚡️Маппинг файлов в адресное пространство процесса. Операции ввода-вывода всегда долгие. Но в mold'е сделали ход конем: Они просто отображают содержимое файла в память программы и могут его читать быстрее.

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

Молодцы, ребята. Комплексно подошли к проблеме, работали по всем фронтам и применили интересные технические решения.

Be faster. Stay cool.

#tools