3

我有 0-1 值向量，我需要对其进行一些矩阵运算。它们不是很稀疏（只有一半的值是 0），但是将它们保存为逻辑变量而不是 double 可以节省 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 OS X 10.8.3 上的 MATLAB R2012b，Intel Core i7 3.4 GHz

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

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

4

3 回答 3

3

我将首先发布一个更好的基准。我正在使用 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 和稀疏度=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依赖于为您的平台优化的 BLAS 实现来执行全矩阵乘法（想想DGEMM）。在一般情况下，这包括单/双类型的例程，但不包括布尔值，因此会发生转换，这可以解释为什么它对于logical.

在英特尔处理器上，BLAS/LAPACK 例程由英特尔 MKL 库提供。不确定 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包进行许多稀疏操作，但我不确定）。

于 2013-05-23T21:10:35.713 回答
2

当您处理完全适合缓存且不太稀疏的数据时（如在您的基准测试中），做额外的工作（如在逻辑类型和双精度之间转换，或使用稀疏存储方案）以尝试减少内存占用只会减慢您的代码速度（如您所见）。

当每个加载的数据元素完成足够数量的计算工作时（如您的示例中的情况），来自 L1 缓存的数据访问速度足够快，可以“有效地免费”。发生这种情况时，执行速度受到计算的限制，而不是加载/存储流量；通过使用逻辑变量，您正在做更多的计算，这会减慢您的基准。

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

于 2013-05-19T14:31:33.010 回答
2

我认为结果与不同的表示合理相关。

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

逻辑数组更节省空间，每个元素仅使用一个字节而不是 8 个字节，但是当您只有 8 个元素时，这不会获得任何好处。另一方面，在使用它进行双精度运算之前，它确实必须转换为双精度，并添加一个步骤。

稀疏数组使用更复杂的表示，旨在在大多数数组为零时节省空间。它需要更多的操作来确定给定索引处的元素为零，或者获得其非零值。将它用于即使是最小的缓存也很容易适应的 50% 非零数组是一种误用。它最适合降低几乎为零的大型阵列的内存和数据传输成本。参见稀疏与正常数组 Matlab

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

于 2013-05-19T13:12:37.580 回答