Всем привет.
Возник несложный вопрос, но что-то я туплю с недосыпу.
Вот, допустим, у нас есть два байтовых массива, a и b.
И мы хотим вычислить, скажем, их сумму, c[i] = a[i] + b[i].
Допустим для простоты, что длина массива кратна 4 (или 8).
Это значит, что я могу его интерпретировать как массив int (или long).
И вот, собственно, вопрос — могу ли я ускорить сложение путём каких-то манипуляций с "длинными" числами? Что-то типа SIMD без SIMD инструкций.
Ну, то есть понятно, что если переполнения нет, то можно просто сложить два инта; байты int_c[i] == int_a[i] + int_b[i] как раз совпадут с нужными нам байтами.
Но если где-то будет переполнение, то оно "полезет" в соседние байты, а каждый из байтов должен переполняться самостоятельно.

Здравствуйте, Sinclair, Вы писали:

S>Всем привет.
S>Возник несложный вопрос, но что-то я туплю с недосыпу.
S>Вот, допустим, у нас есть два байтовых массива, a и b.
S>И мы хотим вычислить, скажем, их сумму, c[i] = a[i] + b[i].
S>Допустим для простоты, что длина массива кратна 4 (или 8).
S>Это значит, что я могу его интерпретировать как массив int (или long).
S>И вот, собственно, вопрос — могу ли я ускорить сложение путём каких-то манипуляций с "длинными" числами? Что-то типа SIMD без SIMD инструкций.
S>Ну, то есть понятно, что если переполнения нет, то можно просто сложить два инта; байты int_c[i] == int_a[i] + int_b[i] как раз совпадут с нужными нам байтами.
S>Но если где-то будет переполнение, то оно "полезет" в соседние байты, а каждый из байтов должен переполняться самостоятельно.

А почему без SIMD ? Надо, чтобы на 8088 работало ?

Именно это делает довольно древняя команда PADDB (еще из MMX)

The PADDB and VPADDB instructions add packed byte integers from the first source operand and second source operand and store the packed integer results in the destination operand. When an individual result is too large to be represented in 8 bits (overflow), the result is wrapped around and the low 8 bits are written to the destination operand (that is, the carry is ignored).

https://www.felixcloutier.com/x86/paddb:paddw:paddd:paddq

Кстати, есть intrinsic _m_paddb

https://learn.microsoft.com/en-us/cpp/intrinsics/x86-intrinsics-list?view=msvc-170

Здравствуйте, Sinclair, Вы писали:

S>Всем привет.
S>Возник несложный вопрос, но что-то я туплю с недосыпу.
S>Вот, допустим, у нас есть два байтовых массива, a и b.
S>И мы хотим вычислить, скажем, их сумму, c[i] = a[i] + b[i].
S>Допустим для простоты, что длина массива кратна 4 (или 8).
S>Это значит, что я могу его интерпретировать как массив int (или long).
S>И вот, собственно, вопрос — могу ли я ускорить сложение путём каких-то манипуляций с "длинными" числами? Что-то типа SIMD без SIMD инструкций.
S>Ну, то есть понятно, что если переполнения нет, то можно просто сложить два инта; байты int_c[i] == int_a[i] + int_b[i] как раз совпадут с нужными нам байтами.
S>Но если где-то будет переполнение, то оно "полезет" в соседние байты, а каждый из байтов должен переполняться самостоятельно.

Можно сложение заменить на более сложную конструкцию типа такого для исходных a, b:

(a + b) & 0xff | ((((a & 0xff00) + (b & 0xff00)) & 0xff00))

либо более прямолинейно

(a + b) & 0xff | ((((a >> 8) + (b >> 8)) & 0xff) << 8)

Т.е. комбинируем сумму как побитовое или сумм каждого байта сдвинутого с учетом позиции. Но с mmx действительно должно быть все проще.

Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А почему без SIMD ? Надо, чтобы на 8088 работало ?
Да, типа того. Ну, и плюс некоторые экзотические сценарии с векторизацией операций со смешением разрядностей. Типа (byte) x + (byte) y + (int)z. В зависимости от того, с какой ассоциативностью мы выполняем операцию, мы можем попробовать сделать конверсию либо до сложения, либо после. Если до, то всё просто — это, скажем, VPMOVZXBD, после которого выполняем VPADDD. А вот если после, то сначала мы хотим получить 8 частичных сумм для байтов, а уже потом делать VPMOVZXBD и второе сложение.
PD>Именно это делает довольно древняя команда PADDB (еще из MMX)
PD>The PADDB and VPADDB instructions add packed byte integers from the first source operand and second source operand and store the packed integer results in the destination operand. When an individual result is too large to be represented in 8 bits (overflow), the result is wrapped around and the low 8 bits are written to the destination operand (that is, the carry is ignored).
PD>https://www.felixcloutier.com/x86/paddb:paddw:paddd:paddq
Да, точно, про этот вариант я забыл
PD>Кстати, есть intrinsic _m_paddb
PD>https://learn.microsoft.com/en-us/cpp/intrinsics/x86-intrinsics-list?view=msvc-170
К сожалению, в дотнете нету MMX-интринсиков.
Ладно, попробуем зайти с другого конца.

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>А почему без SIMD ? Надо, чтобы на 8088 работало ?
S>Да, типа того. Ну, и плюс некоторые экзотические сценарии с векторизацией операций со смешением разрядностей. Типа (byte) x + (byte) y + (int)z. В зависимости от того, с какой ассоциативностью мы выполняем операцию, мы можем попробовать сделать конверсию либо до сложения, либо после. Если до, то всё просто — это, скажем, VPMOVZXBD, после которого выполняем VPADDD. А вот если после, то сначала мы хотим получить 8 частичных сумм для байтов, а уже потом делать VPMOVZXBD и второе сложение.

Ну такое просто командами процессора едва ли возможно. Тут впору сценарий писать — в каком порядке в зависимости от чего.

S>К сожалению, в дотнете нету MMX-интринсиков.

MMX я и впрямь не нашел, но intrinsic есть. SSE2 как минимум содержит ту же PADDB, правда, на xmm

https://learn.microsoft.com/ru-ru/dotnet/api/system.runtime.intrinsics.x86?view=net-6.0

S>Ладно, попробуем зайти с другого конца.

Нормальные герои всегда идут в обход

https://www.youtube.com/watch?v=okG8qrzv53k

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ну такое просто командами процессора едва ли возможно. Тут впору сценарий писать — в каком порядке в зависимости от чего.
Как раз ммх-командами-то оно вроде как и заработает, как надо.
Берём 8 байт, потом прибавляем к ним другие 8 байт, потом расширяем до 8 интов, и прибавляем к ним 8 интов.

S>>К сожалению, в дотнете нету MMX-интринсиков.
PD>MMX я и впрямь не нашел, но intrinsic есть.
Про те я в курсе.
SSE2 как минимум содержит ту же PADDB, правда, на xmm
на xmm она ест по 16 байт, а не по 8. Не получится совместить с интами AVX2 без дополнительных приседаний.

Здравствуйте, Sinclair, Вы писали:

S>на xmm она ест по 16 байт, а не по 8. Не получится совместить с интами AVX2 без дополнительных приседаний.

Насколько я понял из начального сообщения, речь идет о сложении байтовых массивов. Какая разница, какими кусками их представлять ? Почему 4 или 8 годится, а 16 нет ?

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Насколько я понял из начального сообщения, речь идет о сложении байтовых массивов. Какая разница, какими кусками их представлять ? Почему 4 или 8 годится, а 16 нет ?
Если просто два байтовых массива — то, естественно, берём самые длинные регистры из доступных.
А вот когда складываем байты с интами, то всё получается интереснее. Я выше расписал подробно пример.

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>Насколько я понял из начального сообщения, речь идет о сложении байтовых массивов. Какая разница, какими кусками их представлять ? Почему 4 или 8 годится, а 16 нет ?
S>Если просто два байтовых массива — то, естественно, берём самые длинные регистры из доступных.
S>А вот когда складываем байты с интами, то всё получается интереснее. Я выше расписал подробно пример.

Честно говоря, я тот пример не совсем понял.
Складывали байтовые массивы, и вдруг откуда-то появился int. Откуда он взялся ? Из этих байтовых массивов не мог, весь процесс нарушится. Со стороны ? Но тогда это после сложения массивов ?
И если уж нужно выйти за 255, то не проще ли сделать исходные массивы из short или даже int и PADDW/PADDD ? Все carry сохранятся, а потом их можно брать или не брать.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Честно говоря, я тот пример не совсем понял.
PD>Складывали байтовые массивы, и вдруг откуда-то появился int. Откуда он взялся ?
Очевидно, из массива целых.
PD>Из этих байтовых массивов не мог, весь процесс нарушится. Со стороны ? Но тогда это после сложения массивов ?
Вот у нас исходный код:

void AddAdd(byte[] a, byte[] b, int[] c, int[] d, int len)
{
  for(int i=0; i<len; i++)
    d[i] = (a[i] + b[i]) + c[i];
}

Его нужно векторизовать. Если бы все исходные массивы были одинаковой разрядности, то можно было бы просто сделать комбинацию из VMOVDQU/VPADDx.
PD>И если уж нужно выйти за 255, то не проще ли сделать исходные массивы из short или даже int и PADDW/PADDD ? Все carry сохранятся, а потом их можно брать или не брать.
Для того, чтобы исходные массивы стали short или int, их нужно сначала сконвертировать — а это лишний проход и потеря производительности.

Здравствуйте, Sinclair, Вы писали:

S>Для того, чтобы исходные массивы стали short или int, их нужно сначала сконвертировать — а это лишний проход и потеря производительности.

Согласен, но тогда вопрос — а нельзя ли их там, где они создаются, сделать сразу int[] ?

Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Согласен, но тогда вопрос — а нельзя ли их там, где они создаются, сделать сразу int[] ?
Ну, если можно, то вопрос снят.
А вот, например, grayscale-изображения идут в виде byte[].

Здравствуйте, Sinclair, Вы писали:

S>Всем привет.
S>Возник несложный вопрос, но что-то я туплю с недосыпу.
S>Вот, допустим, у нас есть два байтовых массива, a и b.
S>И мы хотим вычислить, скажем, их сумму, c[i] = a[i] + b[i].
S>Допустим для простоты, что длина массива кратна 4 (или 8).
S>Это значит, что я могу его интерпретировать как массив int (или long).
S>И вот, собственно, вопрос — могу ли я ускорить сложение путём каких-то манипуляций с "длинными" числами? Что-то типа SIMD без SIMD инструкций.
S>Ну, то есть понятно, что если переполнения нет, то можно просто сложить два инта; байты int_c[i] == int_a[i] + int_b[i] как раз совпадут с нужными нам байтами.
S>Но если где-то будет переполнение, то оно "полезет" в соседние байты, а каждый из байтов должен переполняться самостоятельно.

Четные и нечетные байтики можно обрабатывать отдельно. (Будет два сложения вместо одного.)

uint64_t a, b;
uint64_t mask1 = 0x00ff00ff00ff00ff;
uint64_t mask2 = ~mask1;
return   ( ( a & mask1 + b & mask1 ) & mask1  )
       | ( ( a & mask2 + b & mask2 ) & mask2  );

Точное решение не скажу, надо думать. Но идея такая: берём исходные 7 байтов. Далее между ними вставляем 6 битов нулевых и один перед первым таким образом они расползаются до 63 битов. Ну или 8 байтов по сути. Далее такие 8-байтовые куски можно сложить. Лишний бит уедет в те биты, которые были добавлены. Ну а потом надо всё назад скукожить.

Подозреваю, правда, что 7 отдельных сложений будет быстрей, чем вся эта битовая возня. Но может быть и не будет.