把逻辑变量和双精度变量混合起来比较慢？

Question

我有0-1值的向量，我需要对其进行一些矩阵运算。它们不是非常稀疏的(只有一半的值是0)，但将它们保存为逻辑变量而不是双精度，可以节省8倍的内存:1字节用于逻辑，8字节用于双浮点。

逻辑向量和双倍矩阵的矩阵乘法会比同时用作双倍矩阵慢吗？我的初步结果如下：

>> x = [0 1 0 1 0 1 0 1]; A = rand(numel(x)); xl = logical(x);
>> tic; for k = 1:10000; x * A * x'; end; toc %'
Elapsed time is 0.017682 seconds.
>> tic; for k = 1:10000; xl * A * xl'; end; toc %'
Elapsed time is 0.026810 seconds.
>> xs = sparse(x);
>> tic; for k = 1:10000; xs * A * xs'; end; toc %'
Elapsed time is 0.039566 seconds.

似乎使用逻辑表示要慢得多(稀疏甚至更慢)。有人能解释一下原因吗？是类型转换时间吗？这是CPU/FPU指令集的限制吗？

编辑:我的系统是Mac 10.8.3、英特尔酷睿i7 3.4 GHz上的MATLAB R2012b

EDIT2:一些评论表明这只是Mac的一个问题。如果可能的话，我想从不同的架构和操作系统中编译结果。

EDIT3:我的实际问题需要计算长度为m的所有可能的二进制向量的很大一部分，其中m可能太大，8 * m * 2^m无法放入内存。

Answer 1

首先，我将发布一个稍微更好的基准测试。我使用Steve Eddins的TIMEIT函数来获得更精确的时间：

function [t,err] = test_mat_mult()
    %# data
    N = 4000; sparsity = 0.7;    %# adjust size and sparsity of data
    x = double(rand(1,N) > sparsity);
    xl = logical(x);
    xs = sparse(x);
    A = randn(N);

    %# functions
    f = cell(3,1);
    f{1} = @() mult_func(x,A);
    f{2} = @() mult_func(xl,A);
    f{3} = @() mult_func(xs,A);

    %# timeit
    t = cellfun(@timeit, f);

    %# check results
    v = cellfun(@feval, f, 'UniformOutput',true);
    err = max(abs(v-mean(v)));  %# maximum error
end

function v = mult_func(x,A)
    v = x * A * x';
end

以下是在我的机器(WinXP 32位，R2013a)上运行N=4000和sparsity=0.7的结果：

>> [t,err] = test_mat_mult
t =
     0.031212    %# double
     0.031970    %# logical
     0.071998    %# sparse
err =
   7.9581e-13

您可以看到，平均而言，double只比logical稍好一些，而sparse则像预期的那样比两者都慢(因为它关注的是有效的内存使用，而不是速度)。

现在请注意，MATLAB relies on BLAS实现针对您的平台进行了优化，以执行full-matrix multiplication (想想DGEMM)。在一般情况下，这包括单/双精度类型的例程，但不包括布尔值，因此将发生转换，这可以解释为什么logical速度较慢。

在英特尔处理器上，BLAS/LAPACK例程由Intel MKL Library提供。我不确定AMD，但我认为它使用了等同的ACML

>> internal.matlab.language.versionPlugins.blas
ans =
Intel(R) Math Kernel Library Version 10.3.11 Product Build 20120606 for 32-bit applications

当然，稀疏情况则是另一回事。(我知道MATLAB使用SuiteSparse包进行许多稀疏操作，但我不确定)。

Answer 2

我认为这些结果与不同的表现形式有合理的联系。

对于表示很容易放入缓存中的小数据体来说，非稀疏双数组是简单而有效的。

逻辑数组的空间效率更高，每个元素只使用一个字节，而不是8个字节，但当您只有8个元素时，这不会带来任何好处。另一方面，在使用它进行双重算术之前，必须将其转换为double，添加一个步骤。

稀疏数组使用更复杂的表示形式，以便在大多数数组为零时节省空间。它需要更多的操作来确定给定索引处的元素为零，或者获取其非零值。将它用于50%的非零数组，即使是最小的缓存也很容易容纳，这是一种误用。它最适合于减少几乎为零的大型阵列的内存和数据传输成本。请参阅Sparse vs Normal Array Matlab

如果你真的在处理8个元素数组，你应该坚持使用双精度的非稀疏数组。如果您的实际工作涉及更大的数组，则需要使用类似的大小进行基准测试。您还需要确保测试数据的稀疏性与真实数据相匹配。

Answer 3

当您正在处理完全适合缓存并且不太稀疏的数据时(如在您的基准测试中)，执行额外的工作(例如在逻辑类型和双精度之间转换，或者使用稀疏存储方案)来尝试减少内存占用只会降低代码的速度(正如您已经注意到的)。

从L1缓存访问数据的速度足够快，当每个加载的数据元素都有足够的计算工作量时(如您的示例所示)，可以“有效地释放”数据。当这种情况发生时，执行速度受到计算的限制，而不是加载/存储流量；通过使用逻辑变量，您正在进行更多的计算，这会降低您的基准测试速度。

你真正想要解决的问题中的工作集有多大？如果它不比处理器上的L2缓存大，那么您应该只使用普通的双矩阵。使用逻辑变量变得有利的确切阈值可能要大得多，但需要一些实验来确定。(这还取决于MATLAB如何处理转换；您希望将转换作为乘法的平铺的一部分--如果MATLAB不这样做，它可能永远不会比使用double更快，无论数据集有多大)。