Самый странный коммит в истории ядра Linux

Принято считать, что у git merge должно быть два родительских коммита. Например, вот свежий коммит ядра Linux версии 4.10-rc6 с идентификатором 2c5d955, образованный слиянием двух родителей:

			2c5d955 Merge branch 'parisc-4.10-3' of ...
|
*- 2ad5d52 parisc: Don't use BITS_PER_LONG in use ...
*- 53cd1ad Merge branch 'i2c/for-current' of ...
		

Git также поддерживает слияния типа «осьминог», у которых есть больше двух родителей. Это непривычно для тех, кто работает над маленькими проектами: ну неужели вас не смутит слияние трёх или четырёх родителей? Однако такое случается. Иногда люди, сопровождающие ядро, объединяют десятки отдельных историй. 30 отдельных слияний проводить куда неудобнее, чем одно с 30 родителями, особенно если оно пройдёт без конфликтов.

И как часто используют этих осьминогов?

«Осьминоги» на самом деле встречаются куда чаще, чем вы могли бы подумать. Всего в истории ядра (на момент написания статьи) есть 649 306 коммитов. 46 930 (7,2%) из них — слияния. 1 549 слияний (3,3%) — осьминоги.

			$ git log --oneline | wc -l
   649306
$ git log --oneline --merges | wc -l
   46930
$ git log --oneline --min-parents=3 | wc -l
    1549
		

Приведём наглядный пример для сравнения: 20% коммитов Rails — слияния (12 401 из 63 111), и среди них нет осьминогов. Rails больше похож на среднестатистический проект: скорее всего, большинство пользователей git даже не подозревали о возможности множественного слияния.

Теперь возникает закономерный вопрос: насколько большими могут быть эти осьминоги? Символы > здесь обозначают продолжения строк — вся команда занимает 4 строки. Да, она не особо читаема, но нам больше интересен результат:

			$ (git log --min-parents=2 --pretty='format:%h %P' |
>  ruby -ne '/^(\w+) (.*)$/ =~ $_; puts "#{$2.split.count} #{$1}"' |
>  sort -n |
>  tail -1)
66 2cde51f
		

66 родителей! Да уж, немало. А что произошло?

			$ git log -1 2cde51f
commit 2cde51fbd0f310c8a2c5f977e665c0ac3945b46d
Merge: 7471c5c c097d5f 74c375c 04c3a85 5095f55 4f53477
2f54d2a 56d37d8 192043c f467a0f bbe5803 3990c51 d754fa9
516ea4b 69ae848 25c1a63 f52c919 111bd7b aafa85e dd407a3
71467e4 0f7f3d1 8778ac6 0406a40 308a0f3 2650bc4 8cb7a36
323702b ef74940 3cec159 72aa62b 328089a 11db0da e1771bc
f60e547 a010ff6 5e81543 58381da 626bcac 38136bd 06b2bd2
8c5178f 8e6ad35 008ef94 f58c4fc4 2309d67 5c15371 b65ab73
26090a8 9ea6fbc 2c48643 1769267 f3f9a60 f25cf34 3f30026
fbbf7fe c3e8494 e40e0b5 50c9697 6358711 0112b62 a0a0591
b888edb d44008b 9a199b8 784cbf8
Author: Mark Brown <[email redacted for privacy]>
Date:   Thu Jan 2 13:01:55 2014 +0000

    Merge remote-tracking branches [65 remote branch names]
		

Этот коммит сломал не один инструмент для отображения истории, и даже привлёк внимание самого Линуса Торвальдса:

Я только что извлёк звуковые обновления Takashi и получил мёрж-коммит 2cde51fbd0f3. У него 66 родителей.Что ж, он извлёкся, он работает, но, бесспорно, нужно чувствовать разницу между «слияния-осьминоги — это здорово» и «Боже, это не осьминог, это Ктулху какой-то».

Изучив код, можно понять, что этот странный коммит был слиянием различных изменений кода ASoC (ALSA System on Chip). ALSA — это звуковая подсистема; SoC — это термин, означающий вычислительное устройство на одном чипе. Т.е. ASoC — это софт для поддержки звука на встроенных системах.

И как часто возникают такие слияния?

Никогда! На втором месте по количеству родителей находится слияние fa623d1, у которого есть «всего лишь» 30 родителей. Однако разрыв между 30 и 66 родителями не будет столь удивительным, если провести небольшое исследование.

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

Если вкратце, тяжёлое одностороннее распределение случайной величины означает, что она принимает большие значения с гораздо меньшей вероятностью, чем маленькие, при этом максимальное значение не ограничено. Ядро содержит 45 381 слияние с двумя родителями и одно — с 66 родителями. Можно предположить, что когда-то мы увидим слияние с ещё большим количеством родителей.

Количество строк кода в функции или модуле также имеет тяжёлое одностороннее распределение (большинство из них маленькие, но некоторые будут огромными — подумайте о классе User в веб-приложении). То же справедливо и в отношении частоты изменения модулей (почти все будут изменяться очень редко, но некоторые — постоянно; User снова подойдёт в качестве примера). При разработке такие распределения возникают всюду и выглядят как прямые на графиках с логарифмической шкалой наподобие того, что изображён выше.

Для тех, кого заинтересовал этот случай, в ядре Linux есть и другие занимательные коммиты.