Experimental chill

Продолжаем наши пути неисповедимые в сортировке в 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, это будет одна из мелких частей.

gcc.godbolt.org

Compiler Explorer - C++

template <typename _Compare, typename _RandomAccessIterator>
inline void
__magic_swap(_RandomAccessIterator __x, _RandomAccessIterator __y,
_RandomAccessIterator __z, _Compare __c) {
typedef
typename std::iterator_traits<_RandomAcces…

www.group-telegram.com/ru/experimentalchill.com/160

12.8K viewsedited  Apr 2, 2022 at 09:45

Продолжаем наши пути неисповедимые в сортировке в 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, это будет одна из мелких частей.

BY Experimental chill