优化阵列压缩

Question

假设我有一个数组 k = [1 2 0 0 5 4 0]

我可以按如下方式计算掩码 m = k > 0 = [1 1 0 0 1 1 0]

仅使用掩码m和以下操作

1. 向左/向右移动
2. 和/或
3. 加/减/乘

我可以将k压缩成以下内容 [1 2 5 4]

这是我目前的做法(MATLAB伪代码):

function out = compact( in )
    d = in
    for i = 1:size(in, 2) %do (# of items in in) passes
        m = d > 0
        %shift left, pad w/ 0 on right
        ml = [m(2:end) 0] % shift
        dl = [d(2:end) 0] % shift

        %if the data originally has a gap, fill it in w/ the 
        %left shifted one
        use = (m == 0) & (ml == 1) %2 comparison  

        d = use .* dl + ~use .* d

        %zero out elements that have been moved to the left
        use_r = [0 use(1:end-1)]
        d = d .* ~use_r
    end

    out = d(1 : size(find(in > 0), 2)) %truncate the end
end

直觉

每次迭代,我们将掩模向左移动并比较掩模.如果我们发现在此移位之后,原来为void(mask [i] = 0)的索引现在有效(mask [i] = 1),我们设置索引以获得左移数据.

题

上述算法具有O(N*(3 shift + 2比较+ AND + add + 3 multiplies)).有没有办法提高效率？

Answer 1

在原始的伪代码中没有太多优化.我在这看到几个小的改进:

• 循环可以执行少一次迭代(即size-1),
• 如果'use'为零,你可以提前打破循环,
• use = (m == 0) & (ml == 1)可能可能简化为use = ~m & ml,
• 如果~计为单独的操作,这将是最好使用反相形式:use = m | ~ml,d = ~use .* dl + use .* d,use_r = [1 use(1:end-1)],d = d .*use_r

但是有可能发明更好的算法.算法的选择取决于使用的CPU资源:

• 加载存储单元,即将算法直接应用于存储器字.在芯片制造商向其指令集添加高度并行的SCATTER指令之前,这里无法做任何事情.
• SSE寄存器,即在整个16字节寄存器上工作的算法.像拟议的伪代码这样的算法在这里无济于事,因为我们已经有各种随机/置换指令,这使得工作更好.使用PMOVMSKB的各种比较指令,将结果分组为4位并在switch/case下应用各种shuffle指令(如LastCoder所述)是我们能做的最好的.
• 具有最新指令集的SSE/AVX寄存器允许更好的方法.我们可以直接使用PMOVMSKB的结果,将其转换为PSHUFB之类的控制寄存器.
• 整数寄存器,即GPR寄存器或同时在SSE/AVX寄存器的几个DWORD/QWORD部分上工作(允许执行多个独立的压缩).所提出的应用于整数寄存器的伪代码允许压缩任何长度的二进制子集(从2到20位).这是我的算法,它可能会表现得更好.

C++,64位,子集宽度= 8:

typedef unsigned long long ull;
const ull h = 0x8080808080808080;
const ull l = 0x0101010101010101;
const ull end = 0xffffffffffffffff;

// uncompacted bytes
ull x = 0x0100802300887700;

// set hi bit for zero bytes (see D.Knuth, volume 4)
ull m = h & ~(x | ((x|h) - l));

// bitmask for nonzero bytes
m = ~(m | (m - (m>>7)));

// tail zero bytes need no special treatment
m |= (m - 1);

while (m != end)
{
  ull tailm = m ^ (m + 1); // bytes to be processed
  ull tailx = x & tailm; // get the bytes
  tailm |= (tailm << 8); // shift 1 byte at a time
  m |= tailm; // all processed bytes are masked
  x = (x ^ tailx) | (tailx << 8); // actual byte shift
}

Answer 2

所以你需要弄清楚额外的并行性,转移/混洗开销是否值得这么简单的任务.

for(int inIdx = 0, outIdx = 0; inIdx < inLength; inIdx++) {
 if(mask[inIdx] == 1) {
  out[outIdx] = in[inIdx];
  outIdx++;
 }
}

如果你想进行并行SIMD路由,你最好的选择是一个SWITCH CASE,其中包含掩码的下4位的所有可能的排列.为什么不是8？因为PSHUFD指令只能在XMMX m128而不是YMMX m256上进行随机播放.

所以你做了16个案例:

• [1 1 1 1],[1 1 1 0],[1 1 0 0],[1 0 0 0],[0 0 0 0]不需要任何特殊的移位/随机播放只需将输入复制到输出MOVDQU并将输出指针分别增加4,3,2,1,0.
• [0 1 1 1],[0 0 1 1],[0 1 1 0],[0 0 0 1],[0 1 0 0],[0 0 1 0]您只需要使用PSRLx(右移)逻辑)并将输出指针分别增加3,2,2,1,1,1
• [1 0 0 1],[1 0 1 0],[0 1 0 1],[1 0 1 1],[1 1 0 1]使用PSHUFD打包输入然后将输出指针递增2,分别为2,2,3,3.

因此,每种情况都是最少量的处理(1到2个SIMD指令和1个输出指针添加).case语句的周围循环将处理常量输入指针加法(加4)和MOVDQA加载输入.