【原】MATLAB标准性能优化技术 — 数据缓存

缓存是将预期被多次重用的数据存储在临时存储(内存变量、磁盘文件等)中的过程，目的是提高数据访问速度。数据在第一次使用时存储在存储库中;随后的用法从存储库而不是从原始位置读取数据。

从缓存中多次提取数据比重新加载或重新计算数据要快得多。每当我们有需要多次重新计算或重新加载的信息时，合理使用缓存可以大大增加效率。

缓存可以说是最简单，但也可能是最有效的性能优化技术之一，在MATLAB中，缓存的好处通常超过任何其他性能调优技术。

但缓存通常会增加代码的复杂性，并使代码的可维护性稍微降低，还有一个缺点是，随着程序运行和持续缓存数据，内存使用量会增加，但这可以通过跟踪缓存的数据大小并在达到某个限制或在预定义的时间过了之后清除旧的缓存元素来缓解这一问题。

我们还应该意识到所谓的“缓存谬误”:

在测试中，我们通常重用相同的数据集，所以缓存带来了巨大的速度提升，然而在部署的系统中，可能没有任何缓存的数据元素被重用，在这种情况下，由于额外的处理和内存开销，缓存实际上可能会降低性能。

在决定是否使用缓存时，以及在性能调优周期中，我们应该尝试在系统中尽可能接近地模拟目标运行时环境。

01

只读缓存

在下面的例子中，loadData（）函数用于从文件中读取数据，可以看到其被反复调用：

for iter = 1 : 100
     newData = loadData();
    result(iter) = max(max(newData)) + rand(1);
end

相反，loadData()可以只在缓存变量中调用一次(我们称其为newData)，然后在所有循环迭代中重用该变量。

newData = loadData();
newData = max(max(newData));
for iter = 1 : 100
    result(iter) = newData + rand(1);
end

这个方法的核心思想是:当有一个被反复重新计算的数组时，不要在每次迭代中重新计算整个数组;相反，只更新新的数据元素。从这个意义上说，数组变成了它自己的缓存版本。例如，如果我们显示一张地图，然后向东平移，我们只需计算东部的新地图块并将它们添加到现有地图中，而不是重新计算整个地图。

作为另一种变体，考虑迭代处理数组唯一值的常见用例。这种想法的一个常见表达是下面的循环:

uniqueVals = unique(data);
for idx = 1 : length(uniqueVals)
% Search for the current value within data
    dataIdx = (data == uniqueVals(idx)); % logical array
% now do something useful with dataIdx
    b = someFunctionOf(dataIdx);
end

我们可以使用unique函数的第二个输出参数来缓存unique值的索引位置，以便稍后在循环中重用，从而节省大量处理时间:

[sortedData, sortedDataIdx] = sort(data);
[uniqueVals, sortedStartIdx] = unique(data);
sortedEndIdx = [sortedStartIdx(2:end)'-1, length(data)];
for idx = 1 : length(uniqueVals)
% Direct access to cached data indexes - no need to search
    dataIdx = sortedDataIdx(sortedStartIdx:sortedEndIdx);
    % now do something useful with dataIdx
    b = someFunctionOf(dataIdx);
end

只读缓存的另一个例子是预计算常数。这些值在整个程序中保持不变，尽管它们可能在程序的不同调用中有所不同。简单的例子是：

time = 5/(24*60); % =0.0034722 (meaning 5 minutes in datenum units)
folder = ['abc\', computer('arch'), '\def']; % ='abc\win64\def

02

消除公共子表达式

消除公共子表达式(Common subexpression elimination，简称CSE)是一种优化技术，它将相同的(公共)子表达式结果缓存到变量中。这是只读缓存机制的一种变体。如果表达式只需要很短的时间来重新求值，这通常不会对性能产生太大影响。但是，有时通用表达式的性能消耗很大，例如，从文件中重新加载数据，或者重新计算复杂的最小化问题。在这种情况下，将公共表达式结果缓存到一个临时变量中以便以后重用是有意义的。

例如，在下面的代码中，完全不需要多次调用complexatedalgo:

% Non-optimized version
data1 = a*sin(b)/complicatedAlgo(c) + 2.3;
data2 = a*sin(b)/complicatedAlgo(c) + 5.8/c;
data3 = a*sin(b)/complicatedAlgo(c) - 8.1*b^2;% Optimized version
temp = a*sin(b)/complicatedAlgo(c);
data1 = temp + 2.3;
data2 = temp + 5.8/c;
data3 = temp - 8.1*b^2;

我们通过直接调用其核心算法，绕过内部检查并消除内部调用开销，可以显著提高循环性能：

CSE发挥作用的另一种情况是GUI回调(特别是快速触发的鼠标移动回调)，其中通常需要引用常见表达式，如get (gca， 'XLimit')。在这种情况下，我们只需将属性值存储在一个变量中(例如xlim)，然后在需要访问回调函数中未修改的属性值时使用该变量。

03

可写缓存

在许多实际使用的缓存中，我们需要实时更新缓存，而不能依赖于前面小节中描述的只读缓存。可写缓存自然比只读缓存更难设置。我们需要检查请求的键是否存在于缓存中，如果存在则检索缓存的值(缓存命中)，如果不存在则使用未缓存的值更新缓存(缓存未命中)。

在某些情况下，我们可能希望用最近的值更新现有的缓存值(缓存更新)。正确地实现这种逻辑可能很棘手，特别是在可以异步访问缓存和/或从多个不同的程序位置访问缓存的情况下。

在可写缓存中，当缓存变得太大而无法存入内存时，可能需要从缓存中删除一些数据项。有许多算法可以帮助决定丢弃哪些数据项:最旧的、最新的、最不经常使用的、最近最少使用的、最近使用的、随机的，等等。

初始化可写缓存时，我们有两个主要选项:

• 从一个空缓存开始，让缓存在正常使用期间被填充。这导致了所谓的缓存预热效应，即需要一些时间让缓存被填满，以至于对性能产生影响。

• 用一些初始值预填充缓存，以加快缓存的有效性，但代价是设置时间较长。

下面是一个计算斐波那契数列值的简单记忆示例，这里选择只预填充前两个序列值，并在运行时更新其余的序列值:

function value = fibonacci(n)
  persistent cachedData
  if isempty(cachedData)
    cachedData(1) = 1;
    cachedData(2) = 1;
  end
  try
    value = cachedData(n);
  catch
    %value = fibonacci(n-2) + fibonacci(n-1);
    if length(cachedData) < n-1
    % populate the cache for n-1,n-2; discard result
    fibonacci(n-1);
    end
    value = cachedData(n-2) + cachedData(n-1);
    cachedData(n) = value; % update the cache
  end
end % fibonacci

传统的基于递归的斐波那契实现通常在每次递归迭代中调用两个函数。

标准的递归将导致对许多序列元素的重新计算，而有效的memoization（memoization：计算机科学的概念，来源于memo，这个方法主要是记录一个值，以便以后可以搜索它）对任何元素的计算都不会超过一次

作为在持久变量中存储memoized数据的替代方法，我们可以使用嵌套函数。只要我们将嵌套函数的句柄保存在工作空间作用域中，它的内部变量就会像缓存一样保存，按照这样的思想可以将上述代码修改为：

function fh = fibonacci_outer
    fib = [1, 1, 2]; % first few elements
    fh = @fibonacci_nested; % handle for nested function
    function value = fibonacci_nested(n)
        try
            value = fib(n);
        catch
            if length(fib) < n-1
  % populate the cache for n-1,n-2; discard result
                fibonacci_nested(n-1);
            end
            value = fib(n-2) + fib(n-1);
            fib(n) = value; % update the cache
        end
    end % fibonacci_nested
end % fibonacci_outer

—— end ——