Продолжаем наши пути неисповедимые в сортировке в C++.
Ох, наконец-то мне можно говорить об этом.
Тут наши друзья из DeepMind решили запушить свои находки в сортировках 3, 4 и 5 элементов примитивных типов. https://reviews.llvm.org/D118029
Такой кейс очень интересный, потому что компилируются в машинный код без веток (только с помощью cmov).
Количество инструкций скомпилированного sortN без веток равно 2N + 4M (M -- оптимальное количество сравнений N элементов):
1. N копирований инструкций из памяти
2. N копирований инструкции из регистров
3. 4 инструкции на компаратор
3.1. Переместить во временный регистр
3.2. Сравнить
3.3. 2 условных хода с помощью cmov
Если посчитать количество инструкций, то вы можете увидеть
Sort3 2*3 + 4*3 = 18 (3 элемента за 3 сравнения)
Sort4 2*4 + 4*5 = 28 (4 элемента за 5 сравнений)
Sort5 2*5 + 4*9 = 46 (5 элементов за 9 сравнений)
И компилятор это генерирует на картинке снизу и по ссылке https://gcc.godbolt.org/z/Mdn8WxaMK
Ребята из DeepMind решили применить MuZero (та самая AlphaZero, дада) на то, чтобы она поискала какие-то улучшения в branchless sorting
И она нашла как сделать sort3 за 17 инструкций, sort5 за 43.
Условно когда мы сортируем 3 элемента A, B, C мы делаем
cond_swap(B, C)
cond_swap(A, C)
cond_swap(A, B)
Каждая по 4 инструкции
MuZero нашёл это сделать так:
cond_swap(B, C) // B < C
magic_swap(A, B, C)
magic_swap похож на двойной cond_swap, но с одним отличием:
1. Move C into tmp.
2. Compare A and C.
3. Conditionally move A into C.
4. Conditionally move A into tmp.
// By now C’ = max(A, C), tmp = min(A, C)
Move tmp into A. !!!, эта была в двойном cond_swap, а теперь ушло
5. Compare tmp and B.
6. Conditionally move B into A.
7. Conditionally move tmp into B.
Это настолько круто, насколько это возможно. Теперь мы с помощью reinforcement learning находим оптимизации в сортировках.
Быстрее ли оно, чем 18 инструкций? На самом деле вряд ли, mov из регистров в регистр это переименовывание регистров, и работа будет идти только на декодинге инструкции и retirement (выходе из пайплайна) части. Мелочи, в реальности особо не заметно, но приятно в любом случае.
Я пилю просто огромный пост по поводу того, что мы в итоге сделали с сортировками в Google, это будет одна из мелких частей.
Ох, наконец-то мне можно говорить об этом.
Тут наши друзья из DeepMind решили запушить свои находки в сортировках 3, 4 и 5 элементов примитивных типов. https://reviews.llvm.org/D118029
Такой кейс очень интересный, потому что компилируются в машинный код без веток (только с помощью cmov).
Количество инструкций скомпилированного sortN без веток равно 2N + 4M (M -- оптимальное количество сравнений N элементов):
1. N копирований инструкций из памяти
2. N копирований инструкции из регистров
3. 4 инструкции на компаратор
3.1. Переместить во временный регистр
3.2. Сравнить
3.3. 2 условных хода с помощью cmov
Если посчитать количество инструкций, то вы можете увидеть
Sort3 2*3 + 4*3 = 18 (3 элемента за 3 сравнения)
Sort4 2*4 + 4*5 = 28 (4 элемента за 5 сравнений)
Sort5 2*5 + 4*9 = 46 (5 элементов за 9 сравнений)
И компилятор это генерирует на картинке снизу и по ссылке https://gcc.godbolt.org/z/Mdn8WxaMK
Ребята из DeepMind решили применить MuZero (та самая AlphaZero, дада) на то, чтобы она поискала какие-то улучшения в branchless sorting
И она нашла как сделать sort3 за 17 инструкций, sort5 за 43.
Условно когда мы сортируем 3 элемента A, B, C мы делаем
cond_swap(B, C)
cond_swap(A, C)
cond_swap(A, B)
Каждая по 4 инструкции
MuZero нашёл это сделать так:
cond_swap(B, C) // B < C
magic_swap(A, B, C)
magic_swap похож на двойной cond_swap, но с одним отличием:
1. Move C into tmp.
2. Compare A and C.
3. Conditionally move A into C.
4. Conditionally move A into tmp.
// By now C’ = max(A, C), tmp = min(A, C)
5. Compare tmp and B.
6. Conditionally move B into A.
7. Conditionally move tmp into B.
Это настолько круто, насколько это возможно. Теперь мы с помощью reinforcement learning находим оптимизации в сортировках.
Быстрее ли оно, чем 18 инструкций? На самом деле вряд ли, mov из регистров в регистр это переименовывание регистров, и работа будет идти только на декодинге инструкции и retirement (выходе из пайплайна) части. Мелочи, в реальности особо не заметно, но приятно в любом случае.
Я пилю просто огромный пост по поводу того, что мы в итоге сделали с сортировками в Google, это будет одна из мелких частей.