如何优化MATLAB位运算

Question

我在MATLAB中编写了自己的SHA1实现，它能够正确生成哈希值。但是它非常慢（一个1000个字符的字符串需要9.9秒在我的Core i7-2760QM上运行），我认为这种缓慢是由于MATLAB如何实现位逻辑操作（bitand、bitor、bitxor、bitcmp）和位移操作（bitshift、bitrol、bitror）的整数。特别是我想知道为什么需要使用fi命令构建bitrol和bitror的定点数对象，因为在Intel x86汇编中，对于所有大小的寄存器和内存地址都有rol和ror。然而，bitshift非常快（不需要任何定点数构造，普通的uint64变量就可以工作），这使得情况更加奇怪：为什么在MATLAB中，bitrol和bitror需要使用fi构造定点数对象，而bitshift则不需要，在汇编级别上，所有这些操作都归结为shl、shr、rol和ror？因此，在将此函数编写为C/C++的.mex文件之前，我想知道是否有任何方法可以提高此函数的性能。我知道有一些特定于SHA1的优化，但这不是问题所在，如果基本的位旋转实现如此缓慢。

通过使用tic和toc进行少量测试，很明显使其变慢的是bitrol和fi中的循环。这里有两个这样的循环：

%# Define some variables.
FFFFFFFF = uint64(hex2dec('FFFFFFFF'));

%# constants: K(1), K(2), K(3), K(4).
K(1) = uint64(hex2dec('5A827999'));
K(2) = uint64(hex2dec('6ED9EBA1'));
K(3) = uint64(hex2dec('8F1BBCDC'));
K(4) = uint64(hex2dec('CA62C1D6'));

W = uint64(zeros(1, 80));

... some other code here ...

%# First slow loop begins here.

for index = 17:80
    W(index) = uint64(bitrol(fi(bitxor(bitxor(bitxor(W(index-3), W(index-8)), W(index-14)), W(index-16)), 0, 32, 0), 1));
end

%# First slow loop ends here.

H = sha1_handle_block_struct.H;

A = H(1);
B = H(2);
C = H(3);
D = H(4);
E = H(5);

%# Second slow loop begins here.

for index = 1:80
    rotatedA = uint64(bitrol(fi(A, 0, 32, 0), 5));

    if (index <= 20)
        % alternative #1.
        xorPart = bitxor(D, (bitand(B, (bitxor(C, D)))));
        xorPart = bitand(xorPart, FFFFFFFF);
        temp = rotatedA + xorPart + E + W(index) + K(1);
    elseif ((index >= 21) && (index <= 40))
        % FIPS.
        xorPart = bitxor(bitxor(B, C), D);
        xorPart = bitand(xorPart, FFFFFFFF);
        temp = rotatedA + xorPart + E + W(index) + K(2);
    elseif ((index >= 41) && (index <= 60))
        % alternative #2.
        xorPart = bitor(bitand(B, C), bitand(D, bitxor(B, C)));
        xorPart = bitand(xorPart, FFFFFFFF);
        temp = rotatedA + xorPart + E + W(index) + K(3);
    elseif ((index >= 61) && (index <= 80))
        % FIPS.
        xorPart = bitxor(bitxor(B, C), D);
        xorPart = bitand(xorPart, FFFFFFFF);
        temp = rotatedA + xorPart + E + W(index) + K(4);
    else
        error('error in the code of sha1_handle_block.m!');
    end

temp = bitand(temp, FFFFFFFF);
E = D;
D = C;
C = uint64(bitrol(fi(B, 0, 32, 0), 30));
B = A;
A = temp;
end

%# Second slow loop ends here.

使用 tic 和 toc 进行测量，我的笔记本电脑计算消息 abc 的 SHA1 哈希需要大约 0.63 秒，其中第一个慢循环花费了约 0.23 秒，第二个慢循环花费了约 0.38 秒。那么，在编写 .mex 文件之前，是否有一些方法可以优化 MATLAB 中的这些循环呢？

- nrz

Answer 1

有一个来自MATLAB文件交换平台的DataHash，可以快速计算SHA-1哈希值。
我运行了以下代码：

x = 'The quick brown fox jumped over the lazy dog';  %# Just a short sentence
y = repmat('a', [1, 1e6]);                           %# A million a's
opt = struct('Method', 'SHA-1', 'Format', 'HEX', 'Input', 'bin');
tic, x_hashed = DataHash(uint8(x), opt), toc
tic, y_hashed = DataHash(uint8(y), opt), toc

并得到以下结果：

x_hashed = F6513640F3045E9768B239785625CAA6A2588842
经过的时间为0.029250秒。

y_hashed = 34AA973CD4C4DAA4F61EEB2BDBAD27316534016F
经过的时间为0.020595秒。

我用一个在线SHA-1工具验证了结果，计算确实是正确的。而且，这10⁶个a的哈希值比第一句话快了约1.5倍。

那么，DataHash是如何做到这么快的呢？居然还使用了java.security.MessageDigest库！
如果你想要一个快速的MATLAB友好的SHA-1函数，那就选择这个吧。

但是，如果这只是一个实现快速位级操作的练习，那么MATLAB并不能有效地处理它们，在大多数情况下，你将不得不求助于MEX。

- Eitan T

---

在我看来，加速SHA1的选项是使用java.security.MessageDigest库或编写MEX函数。由于我计划使我的MATLAB代码与GNU Octave兼容（并希望将GNU Octave用作开发环境），而且似乎MATLAB和Octave在处理Java方面存在一些差异，因此使用Java库不是理想的解决方案。但是，DataHash非常快，因此在我实现MEX解决方案或找到其他有效实现SHA1的方法之前，它可以胜任工作，而无需使用Java。 - nrz

将我的自己的fMRI分析工具箱移植到Octave是我长期的项目，我不想基于此限制答案。无论如何，我目前需要的是一种有效的方法来计算较大文件的SHA1（在MATLAB中），以便能够继续开发，而DataHash是一个可行的解决方案。 - nrz

@nrz：Octave具有兼容的MEX API，可用于编写C扩展。他们还拥有自己的API，用于编写OCT文件（相当于MATLAB中的MEX文件）。 - Amro

@nrz：忘记那个吧，Octave-Forge已经有一个SHA1函数了（SVN仓库）。 - Amro

@Amro 非常好！因此，解决方案将是检查环境，并在MATLAB中使用DataHash，在Octave中使用SHA1。但是，在我的计算机上，SHA1（/usr/lib/x86_64-linux-gnu/octave/packages/general-1.3.1/x86_64-pc-linux-gnu-api-v48+/SHA1.oct）会导致Octave 3.6.2崩溃，但这个错误可能很快就会被修复。 - nrz

Answer 2

作为大多数MATLAB函数，bitand、bitor和bitxor都是向量化的。因此，如果您提供这些函数的向量输入而不是在每个元素上循环调用它们，您将获得更快的速度。

例如：

%# create two sets of 10k random numbers
num = 10000;
hex = '0123456789ABCDEF';
A = uint64(hex2dec( hex(randi(16, [num 16])) ));
B = uint64(hex2dec( hex(randi(16, [num 16])) ));

%# compare loop vs. vectorized call
tic
C1 = zeros(size(A), class(A));
for i=1:numel(A)
    C1(i) = bitxor(A(i),B(i));
end
toc

tic
C2 = bitxor(A,B);
toc

assert(isequal(C1,C2))

时间是：

Elapsed time is 0.139034 seconds.
Elapsed time is 0.000960 seconds.

这快了一个数量级！

问题在于，据我所知，SHA-1计算无法很好地进行向量化。因此，您可能无法利用这种向量化。

作为一个实验，我实现了一个纯基于MATLAB的函数来计算这样的位操作：

function num = my_bitops(op,A,B)
    %# operation to perform: not, and, or, xor
    if ischar(op)
        op = str2func(op);
    end

    %# integer class: uint8, uint16, uint32, uint64
    clss = class(A);
    depth = str2double(clss(5:end));

    %# bit exponents
    e = 2.^(depth-1:-1:0);

    %# convert to binary
    b1 = logical(dec2bin(A,depth)-'0');
    if nargin == 3
        b2 = logical(dec2bin(B,depth)-'0');
    end

    %# perform binary operation
    if nargin < 3
        num = op(b1);
    else
        num = op(b1,b2);
    end

    %# convert back to integer
    num = sum(bsxfun(@times, cast(num,clss), cast(e,clss)), 2, 'native');
end

不幸的是，在性能方面，这甚至更糟:

tic, C1 = bitxor(A,B); toc
tic, C2 = my_bitops('xor',A,B); toc
assert(isequal(C1,C2))

时间是：

Elapsed time is 0.000984 seconds.
Elapsed time is 0.485692 seconds.

结论：编写一个MEX函数或搜索文件交换来看看是否有人已经完成 :)

- Amro

---

据我所知，SHA1 无法有效地进行向量化。你的 my_bitops 函数似乎是尝试在 MATLAB 中加速计算位运算的有趣方式，但不幸的是它并没有解决性能问题。我认为在编写 MEX 函数或使用他人编写的 MEX 之前，EitanT 提到的 DataHash 将是解决问题的方法。 - nrz

Answer 3

在MATLAB中，为什么bitrol和bitror需要使用由fi构建的定点数值对象，而bitshift则不需要？

bitrol和bitror不是适用于uints的按位逻辑函数集合的一部分。它们是定点工具箱的一部分，该工具箱还包含适用于定点输入的bitand、bitshift等变体。

如果您想尝试仅使用uint函数，则可以将bitrol表示为两个bitshift、一个bitand和一个bitor。但这可能会更慢。

- Michael

---

通过用自己的左旋函数替换所有的 bitrol(fi( ... 代码，SHA1 计算 1000 个 a 的时间从 9.9 秒降至约 0.42 秒，因此现在比以前快了约 23.5 倍。然而，计算更长消息的 SHA1 散列（例如 FIPS 文档中一百万（10^6）个 a 的示例消息）仍需要大约 422 秒（我的原始代码需要 9430 秒来计算），而在 bash 中运行 time printf 'a%.0s' {1..1000000} | sha1sum 只需要 0.953 秒。因此，比我的原始代码快了 23.5 倍，但仍比 sha1sum 慢约 440 倍。 - nrz