Home 通过滑动窗口来优化 vector
Post
Cancel

通过滑动窗口来优化 vector

Posted 2020/11/08
By Caturra
16 min read

最近在写一个库，有一个场景是 std::vector 存储一些对象，每次都是往后面添加，但是内部的元素可能会随机地失效（且不可恢复），这种场合下需要针对性地优化 vector：

  1. 尽可能回收这些占坑的无效元素，避免容器支离破碎的碎片
  2. 降低添加过程的响应时间，避免扩充时造成的 \(O(n)\) 卡顿（就是要求严格 \(O(1)\)，非均摊 \(O(1)\)）

其中要求一是这个特殊容器的特定条件，要求二是这个容器需要达成的目的，不希望加入两个元素之间有过大的性能差异（这会对其它操作有影响），而扩容是 vector 的通病

一个场景的模拟

 ---------------------------
|x| | | | |x| | |x|x| | |x| |
 ---------------------------

这是一个容器的内部，其中 x 就是已经失效但是占坑的元素，甚至扩容也会把这些碎片 copy 过去，洁癖必须处理

常规做法

不考虑碎片问题的话，就是上来就为 vector 保留一个较大的 capacity（好像是 effective 系列提到的做法）

但这么做又有问题了，

  1. 我不想有碎片，但为什么上来就造一个可能很大又用不着的 capacity，这浪费可能比碎片还大
  2. 这个容器最终的大小无法估计，预留只能简单缓解前 N 次的扩容
  3. 如果 capacity 过大可以 shrink_to_fit，但 shrink_to_fit 也是一个相当”卡顿”的操作，而且时机不好把控

常规做法 2

用链表取代 vector 容器，总不会不合理的扩容了

但是碎片处理依然无法下手（见下面 GC）

而且我需要连续的一块空间（暂不谈 cache 友好这种玄学）

GC 的思路

不妨以消灭碎片为前提来考虑，假如每次扩容前都 check 一下有哪些 index 是已经失效的，搬过去的时候不 copy 这些失效元素，是否更加合理

这种做法是有一定依据，完全回收了过去失效的碎片，也让下一次扩容的时机延迟了（个数少了，就更少机会触发扩容）

但这又有问题

  1. check 碎片怎么 check，遍历吗？不也“卡顿”？
  2. 那我记一个表？失效的时候先写个 index 到里面去？那么要为这个 GC 思路买单是不是不太划算，首先额外空间是 \(O(n)\) 的，其次对设计是侵入式的，接口很别扭，元素自己失效必须要调用这个容器的某个接口，万一元素本身就有一个失效又不会记下映射表的可能？比如 unique_ptr.reset()？

可行但不够优雅

是不是应该从简单的例子发现点什么优雅的做法

设想

先从简单的场景设想一下，万一碎片是这样子的，是不是很好处理

 ---------------------------
| | | |x|x|x|x|x| | | | | | |
 ---------------------------

就是说碎片总是连续一大块的，即只有一块，也是连续的块

那就简单了，记下一对碎片下标的区间 [begin,end]，每次分配都先复用它们，维护 begin 和 end 就好了，低时延，少碎片

进一步为了方便维护，更加理想的碎片分布应该是这样

 ---------------------------
| | | | | | | | | |x|x|x|x|x|
 -----------------·---------
                  begin

这个时候我只维护一个 begin 就足够了，end 永远等于 capacity

swap

设想美好，那就尽可能凑成这种样子

假如此时有一个元素随机失效了，像这样

 ---------------------------
| | | |x| | | | | |x|x|x|x|x|
 -----------------·---------
                  begin

那我们可以通过 swap 的技巧来实现，把 begin-1 换过去，只要右值成本足够廉价

 ---------------------------
| | | |-| | | | |x|x|x|x|x|x|
 ---------------·-----------
                begin

BUT

这只是理想，根据前面的要求，我没有维护一个表，失效是元素自身的操作，我不知道哪里会有 x 出现

这个时候需要一定的算法，比如定时 check 一小部分连续空间，来做到严格\(O(1)\)的查找，

比如第一次查下标[0,3]，第二次查[4,7]，就是算法傻了点

因为有可能存在这种情况：查[4,7]时发现 6 是失效的，那把 begin-1 下标 swap 过去吧！

万一 begin-1 也是随机无效的？那 begin-2 吧！……

在 swap 这一步就可能陷于一个 while，虽然通过各种方法可以凑成一个高效可行的方法（比如顺便把 begin 更新了、比如也限制固定的操作数、或者牺牲一点无视这种情况），但不够优雅，别问为什么，问就是我试过了

那基于这个做法有什么优雅点的改进

维护窗口

尽可能利用有效信息，在前面的每次查找一小部分连续空间算法中，我们能得到的有效信息是：这一块我检测过了

为了维护信息方便用于下一次的查找，维护一个窗口，内部是一个近似维护检测过的信息，在这里我选择维护已经无效的元素

就是说在窗口 \([l,r]\) 中表示从 \(l\) 到 \(r\) 这一块的区间总是无效的，只维护一块区间窗口

问题就来了，怎么确保碎片总是聚在一块，和前面的固定次数的遍历又有什么联系

用 swap 和滑动这两个技巧就知道了

  1. 零大小窗口：如果遍历总是找不到一个失效元素，保持 \(r = l-1\)，\(l,r\)保持向右滑动，仍为未开启状态（\(r < l\)）
  2. 启动窗口：当找到第一个失效元素时 \((vec[l] == \phi)\)，令 \(r = l\)，表示启动一个大小为 1 的窗口
  3. 交换：当启动窗口后发现一个有效元素时（\(vec[r+1]<>\phi\)），\(swap(vec[l],vec[r+1])\)，并整体右移窗口，继续维护 \([l,r]\) 的性质
  4. 结束：当窗口和 \(begin\) 可以拼在一块时，直接令 \(begin = l\)，窗口关闭，复位为 \([0,-1]\)，并重新开始下一边轮询

（就是一个会交换的滑动窗口，很直观吧，关键操作就是第三点）

Code

这里试给出一个不严格的实现

    void updateReusableIndex() {
        auto resetWindow = [this] {
            _window.left = 0;
            _window.right = -1;
        };
        if(_reusableIndex != 0) { // need GC
            for(int _ = 0; _ < step; ++_) {
                if(_window.left > _window.right) { // 未启动
                    if(_container[_window.left] == nullptr) { // 可以启动
                        ++_window.right;
                    } else { // 零大小窗口整体右滑，仍未启动
                        ++_window.left;
                        ++_window.right;
                        if(_window.left == _reusableIndex) { // TODO 没有准确算过
                            resetWindow();
                        }
                    }
                    continue;
                }
                // 直到_right >= _left 说明 container[left] 是一个 nullptr

                // left/right < reuseIndex
                if(_window.right + 1 == _reusableIndex) { // merge, [left,right] + [reuse,size()) 全是 nullptr，可回收
                    _reusableIndex = _window.left;
                    resetWindow(); // close window
                } else if(_container[_window.right + 1] == nullptr) {
                    ++_window.right;
                } else { // 没有触发到 reuse，但是找到一个可用连接
                    std::swap(_container[++_window.right],
                         _container[_window.left++]); // R+1 和 L 交换，且窗口右滑
                }
                    
            }
        }
    }

// 一些成员
    int _reusableIndex; // 第一个可用的 index
    struct { int left, right; } _window; // 用于维护回收连接的窗口
    constexpr static int step = 2;

这种做法可以满足：

  1. 尽量回收碎片（非严格，但是窗口永远是合法的）
  2. 尽量延迟了扩容，碎片越多越容易更新 begin
  3. 算法严格\(O(1)\)非均摊，额外空间成本也是\(O(1)\)
  4. 不需要修改元素的接口，只需要在容器中定义好什么算失效即可

在 -O3 且添加 N=10^8 次的添加操作，随机失效的测试中，数据为

滑动窗口
30.7963s // 表示处理N=1e8需要的整体时间
0.087155s // 表示添加元素之间最大的时间差

耿直的vector
32.3052s
0.217208s

可以看出这个优化是相当管用的，卡顿是成倍的差距很好理解，因为最卡顿的时候就是扩容，每次都是倍增

这个简单的策略以后会汇总于我的轮子说明文档中

THE END

C++
This post is licensed under CC BY 4.0 by the author.
Contents