是否有用于元素部分移动的 simd instruction/intrinsic/builtin？
Is there a simd instruction/intrinsic/builtin for partial shift of elements?
一个最小的例子会更有益：
假设我有一个已排序的 8 整数 = {10, 20, 30, 40, 50, 60, 70, 80}（我的用例是针对已排序的整数，但考虑到向量指令作用于整个数据集，我不确定该信息是否有价值）
需要的操作很少：
- 插入并移位。
-> 在其排序位置插入 25。
-> 变为在索引 2 处插入 25 并移位休息。
10, 20, 30, 40, 50, 60, 70, 80 变为：10, 20, 25, 30, 40, 50, 60, 70
- 移除并移动并在后面插入。
-> 从数组中删除 20，如果找到并删除了 20，则在后面插入 90。
10, 20, 30, 40, 50, 60, 70, 80 变为 10, 30, 40, 50, 60, 70, 80, 90
或者一组指令就能让它工作吗？
我正在为降序排序的数组尝试使用多个步骤插入和移位部分。 https://godbolt.org/z/_WCxkW
做你想做的事情的一个通用方法是（[u]int_{8,16,32,64} 甚至 float/double 的一般想法是相同的）：
将x插入input:
// Shift your input array (e.g. "abcefghi") to the right:
out = ShiftRight(input); // out = 0abcefgh
// broadcast the to-be-inserted element (e.g., 'd')
insert = broadcast(x); // insert = dddddddd
// compute
out = min(max(out,insert),input)
// == min(max(0abcefgh,dddddddd),abcefghi)
// == min(ddddefgh,abcefghi) == abcdefgh
从input中移除第一个不小于x的元素:
// shift input (e.g., "abcdefgh") to the left (insert something at the end)
out = ShiftLeft(input); // out = bcdefghX
// determine elements smaller than `x` (e.g., "f") by broadcast and compare
mask = broadcast(x) < input; // mask = 11111000
// take masked elements from `input` and other values from `out` (using a blend instruction)
out = blend(mask, input, out); // == abcdeghX
如果要删除的元素数量不能保证为 1（即，它可能不存在或多次存在），这就比较困难，因为每个输出值都可能取决于每个输入值。一种想法可能是比较相等性并计算元素的数量（使用 maskmove 和 popcount）。
要移动你可以使用
- SSE2且只有一个128位寄存器：
pslldq, psrldq
- SSSE3 和一系列 128 位寄存器：
palignr
- AVX2 和一个 256 位寄存器：
vpermd 具有预先确定的索引向量（没有 AVX2 等效于在整个 256 位寄存器上工作的先前指令）
- 如果您的输入存储在内存中，请使用一个元素偏移再次加载它（这需要 "safe" 元素超出数组的每一端 - 如果您这样做可能会引入显着的读写延迟多次执行这些操作）
对于广播，我建议只使用 _mm[256]_set1_epi32 内部函数，让编译器找出最有效的方法（如果没有 AVX2，这可能需要随机播放）
Min/max 运算符适用于各种 sizes/types（取决于 SSE/AVX 版本）——只需搜索以 pmin/pmax 开头的说明。
据我所知，AVX512之前没有无符号比较，当然你可以使用有符号比较，如果没有值大于最大有符号值。或者您可以通过在比较之前翻转高位来解决（我假设在 Whosebug 上有一个相关的问题）。
最后，如果您有 SSE4.1，混合由 pblendvb 完成。否则你需要做一些bitwise-and/andnot/or操作。
一个最小的例子会更有益：
假设我有一个已排序的 8 整数 = {10, 20, 30, 40, 50, 60, 70, 80}（我的用例是针对已排序的整数，但考虑到向量指令作用于整个数据集，我不确定该信息是否有价值）
需要的操作很少：
- 插入并移位。
-> 在其排序位置插入 25。 -> 变为在索引 2 处插入 25 并移位休息。
10, 20, 30, 40, 50, 60, 70, 80 变为：10, 20, 25, 30, 40, 50, 60, 70
- 移除并移动并在后面插入。
-> 从数组中删除 20，如果找到并删除了 20，则在后面插入 90。
10, 20, 30, 40, 50, 60, 70, 80 变为 10, 30, 40, 50, 60, 70, 80, 90
或者一组指令就能让它工作吗？
我正在为降序排序的数组尝试使用多个步骤插入和移位部分。 https://godbolt.org/z/_WCxkW
做你想做的事情的一个通用方法是（[u]int_{8,16,32,64} 甚至 float/double 的一般想法是相同的）：
将x插入input:
// Shift your input array (e.g. "abcefghi") to the right:
out = ShiftRight(input); // out = 0abcefgh
// broadcast the to-be-inserted element (e.g., 'd')
insert = broadcast(x); // insert = dddddddd
// compute
out = min(max(out,insert),input)
// == min(max(0abcefgh,dddddddd),abcefghi)
// == min(ddddefgh,abcefghi) == abcdefgh
从input中移除第一个不小于x的元素:
// shift input (e.g., "abcdefgh") to the left (insert something at the end)
out = ShiftLeft(input); // out = bcdefghX
// determine elements smaller than `x` (e.g., "f") by broadcast and compare
mask = broadcast(x) < input; // mask = 11111000
// take masked elements from `input` and other values from `out` (using a blend instruction)
out = blend(mask, input, out); // == abcdeghX
如果要删除的元素数量不能保证为 1（即，它可能不存在或多次存在），这就比较困难，因为每个输出值都可能取决于每个输入值。一种想法可能是比较相等性并计算元素的数量（使用 maskmove 和 popcount）。
要移动你可以使用
- SSE2且只有一个128位寄存器：
pslldq,psrldq - SSSE3 和一系列 128 位寄存器：
palignr - AVX2 和一个 256 位寄存器：
vpermd具有预先确定的索引向量（没有 AVX2 等效于在整个 256 位寄存器上工作的先前指令） - 如果您的输入存储在内存中，请使用一个元素偏移再次加载它（这需要 "safe" 元素超出数组的每一端 - 如果您这样做可能会引入显着的读写延迟多次执行这些操作）
对于广播，我建议只使用 _mm[256]_set1_epi32 内部函数，让编译器找出最有效的方法（如果没有 AVX2，这可能需要随机播放）
Min/max 运算符适用于各种 sizes/types（取决于 SSE/AVX 版本）——只需搜索以 pmin/pmax 开头的说明。
据我所知，AVX512之前没有无符号比较，当然你可以使用有符号比较，如果没有值大于最大有符号值。或者您可以通过在比较之前翻转高位来解决（我假设在 Whosebug 上有一个相关的问题）。
最后，如果您有 SSE4.1，混合由 pblendvb 完成。否则你需要做一些bitwise-and/andnot/or操作。