快速直方图算法以及怎样更好的写C++

直方图算法(histogram)是平时工作中经常遇到的一个算法，无论1D还是2D都有非常广泛的应用。

例如，如何统计数组中出现最多次数的元素，就是直方图算法的一个典型应用。以及，我们常说的投票法，往往也可以认为是直方图算法的变种。直方图算法原理相当之简单，以至于其完全不像是一个”算法”。在最近工作的某个场景下，发现直方图成为了性能瓶颈，因此仔细研究了一下实现原理及其周边，特此记录。同时，因为整个代码是c++，快速直方图的实现对怎样高效写c++也很有指导和启发意义。

首先，我们来看下应用直方图算法的基本问题和朴素实现。

问题描述：
A. 对于给定数组a[N]，数组中所有数字均为正整数，每个数字大小不超过 k，找到出现次数最多的元素，输出它的次数和值。
B. 对于给定数组a[N]，数组中所有数字均为正整数，找到出现次数最多的元素，输出它的次数和值。

问题 A 是我们平时遇到最最基本的情况，使用1D直方图算法求解，时间复杂度 O[N]，空间复杂度 O[k]，实现如下:

int hist[k];
memset(hist, 0, sizeof(hist));

for(int i = 0; i < N; i++){  
  hist[a[i]] += 1;  // vote
}

int max_val{0}, max_pos{0};
for(int i = 0; i < k; i++){
   if(hist[i] > max_val){
      max_val = hist[i];
      max_pos = i;
    }
}

如果变量 a 本身不再使用，hist 也可以直接开在 a 上，这样也不需要额外的空间了（O[1]空间复杂度）。在实际代码中，为了兼顾可读性，我们一般不采用这种做法。所有 leetcode 之类的题解到此为止，理论上并不会有更快的解法了。

在某个场景下，如果 N = 1e12，k = 1e8，整个算法的效率大幅度降低。量变引起质变，关键在于，当 k 比较小时，hist 数组所占内存很小，可以整个放到内存中，甚至可以直接加载到 L1/L2 cache 中，其中核心的 vote 操作只需要几个指令周期即可完成。但是 k 值较大时，hist 数组无法加载进缓存，会导致读取 hist 操作变得格外耗时。同时，k 值增大使得数的范围上限提高以至于不得不使用 size_t/u_int32_t 来代替 u_int16_t/int，进一步加剧了这种情况的发生。

在大数据场景下，怎样快速生成一个直方图? 这个问题可能并没有想象的那么简单，直到19年还有相关论文来研究相关的算法。一个很好的 Benchmark: fast histgram benchmark in python。但看了里面几个核心的算法，例如 numpy / fast-histgram (in C)，发现 vote 过程基本还是暴力计算。性能上也并不太令人满意。（这里测试的数据 N 只有 1e7）

当然，性能敏感的代码，c++永远是首选，在 git 上翻过一遍后发现 boost 实现还是里面最靠谱。摘录几个核心的技巧：

选择合适的 storage，也就是上文提到的 hist，最好是连续存储，boost 默认使用的是 vector(当然也可以自定义)。我自己也测试了 vector 和裸数组，几乎无差别。
不要使用超过数据上限的数据结构。例如，如果 u_int_16 够用，就不要用 size_t。boost 使用了动态扩展的数据类型，即先用小的数据类型，如果超过上限了就更新成大的。
二维数组/多维数组转成一维数组，注意数据的空间局部性和内存的连续分配(我自己一开始使用 vector<vector>来处理2D情况，确实比1D更慢)
并行插入。boost 把投票分成两步，第一步生成对应的index，第二步进行 vote（对于1D的情况，第一步操作可省略），算法采用了三种并行的方式，A- 全并行，但这样做要么会产生 false-sharing，要么会线程不安全。文档中专门提到，当数据量小的时候，false-sharing 可能会损害性能。 B- 并行生成 index，然后串行进行投票。C- 并行生成 index 后，对index进行排序，（或者其他类似操作），这样再串行投票的时候，保证不同线程位于不同 disjoint，线程安全和 false-sharing 的问题都可以解决。按照我的经验，在我自己遇到的问题上，第一步的时间消耗远小于第二步（如果第一步时间消耗大，就不把它归类到直方图问题了）。因此，全串行/B-两个方法差别不大。对于 n 较大的情况下，排序之类的操作显然不可行，任何大于 O[N] 的算法都是不可接受的。但可能基于遇到问题的特殊性，有类似的技巧可以使用。
其他一些操作的优化，例如 sum

除此之外，boost 作为通用库，还有几个比较不错的特性：

实现了上文提到grow-axis方案，即一开始给了个小范围，动态扩展。
如果不采用grow-axis，对数据超过上下限情况的处理。
支持 chunk val 输入，会比单个点输入性能更高
使用 std::atomic 来保证插入时的线程安全，即上文提到的 5-a 这一点。并非所有库都可以保证并行插入的线程安全。以及除了插入，其他某些操作可能是非线程安全的，使用时要小心。

几个文档:

对照着boost源码，把我自己的代码完善了一轮，效果还不错。下面记录一些实验的细节.

Baseline，一个对实际问题的抽象

// std::vector<std::pair<size_t, size_t>> target_fp_vec
// std::vector<std::vector<std::pair<size_t, size_t>>> anchor_matched

std::vector<std::vector<unsigned short>> vec_vote_pool_;  
for (unsigned i = 0; i < num_target_fp; i++) {
  size_t now_frame = target_fp_vec[i].second;
  for (auto& xx : anchor_matched[i]) {
    int16_t vote_frame = xx.second - now_frame;    
    size_t name_idx = xx.first;
    vec_vote_pool_[name_idx][vote_frame] += 1; // 核心性能瓶颈
  }
}

...

profile = 2770ms

target_fp_vec 和 anchor_matched 都是基于 vector 的数据结构。实际场景下，需要先从 vector 中拿到 pair 的两个数据，进行运算后获得 indice ，然后进行投票。但进行了性能分析后，投票步骤依然是最关键的性能瓶颈。

事实上，一个好的问题抽象至关重要。问题抽象不正确会导致抽象问题的性能提升不能等价到原问题的性能提升。这里的关键就在于 N/k 两个值的大小，太小了问题的表现完全不一样。

v1a, 使用了 1D 的 hists

std::vector<unsigned short> vec_vote_pool_;  
for (unsigned i = 0; i < num_target_fp; i++) {  
  size_t now_frame = target_fp_vec[i].second;
  for (auto& xx : anchor_matched[i]) {
    int16_t vote_frame = xx.second - now_frame;
    size_t name_idx = xx.first;
    vec_vote_pool_[name_idx * col_size +vote_frame] ++; // 核心性能瓶颈
  }
}

...
// find max

profile = 1582m，只是更改了数据存储在内存的格式，速度大概提升了一倍。

v1b, 使用了并行的vote（4线程）

bool thread_for_res(
    const std::vector<std::pair<size_t, size_t>>& target_fp_vec,
    const std::vector<std::vector<std::pair<size_t, size_t>>>& anchor_matched,
    int thread_i, int thread_n, std::vector<unsigned short>* vec_vote_pool) {  
  for (unsigned i = thread_i; i < num_target_fp; i += thread_n) {
    size_t now_frame = target_fp_vec[i].second;
    for (auto& xx : (anchor_matched)[i]) {
      int16_t vote_frame = xx.second - now_frame;            
      size_t name_idx = xx.first;
      ++(*vec_vote_pool)[name_idx * col_size + vote_frame];
    }
  }
  return true;
}

std::vector<std::thread> vec_thread;
for (int i = 0; i < num_thread; i++) {
  vec_thread.push_back(std::thread(&thread_for_res, std::ref(target_fp_vec), 
                                   std::ref(anchor_matched), i, num_thread,
                                   &vec_vote_pool));
}
for (auto& x : vec_thread) x.join();

...

profile=440ms，并行后性能进一步提升。

注意并行函数调用时传参数需要使用 std::ref。这里并没有保证线程安全，但是当k和n都很大时，姑且默认十几/几十个线程访问到同一位置的概率很小，实验上也可以保证结果的一致性。

后来做了一些修改，根据问题的特点考虑了线程安全后的并行，profile=640ms，稍有增加，但依然会比串行快得多。

v1c, 换了一种局部性更好的写法

bool thread_for_res(
    const std::vector<std::pair<size_t, size_t>>& target_fp_vec,
    const std::vector<std::vector<std::pair<size_t, size_t>>>& anchor_matched,
    int thread_i, int thread_n, std::vector<unsigned short>* vec_vote_pool) {
  int thread_start = thread_i * num_target_fp / thread_n;
  int thread_end = (1 + thread_i) * num_target_fp / thread_n;
  for (unsigned i = thread_start; i < thread_end; ++i) {    
    size_t now_frame = (target_fp_vec)[i].second;
    for (auto& xx : (anchor_matched)[i]) {
      int16_t vote_frame = xx.second - now_frame;     
      size_t name_idx = xx.first;
      ++(*vec_vote_pool)[name_idx * col_size + vote_frame];
    }
  }
}

profile=373ms, 和v1c相比，又提高了一点。

几个不太有帮助的方案

v2b，使用位运算代替 pair 数据结构

// std::vector<uint32_t> target_fp_vec
// std::vector<std::vector<uint32_t>> anchor_matched

for (unsigned i = 0; i < num_target_fp; i++) {    
   size_t now_frame = target_fp_vec[i] & 4095;
   ...
}
    
...

使用 u_int32_t 来代替 pair 数据结构，出发点是 pair 的两个值范围不同，分别需要18位和14位表示，pair 数据结构就需要更大的存储空间。也可以用一个32位来存储，通过位运算来分别拿到两个值，相当于用时间换空间。以及降低 pair存储空间不连续造成性能的下降（实际上并不会）。

实际测试下来，发现两种情况下，性能差不多。

v3c 使用向量化

采用 SSE/AVX 指令完成运算，每次同时存取 4 个值，即降低之前说的计算indice的步骤，事实证明这步并不是瓶颈。同时因为每个数值在数轴上是随机分布的，因此 SSE 并不会提升 vote 的速度。

总结下来，整个优化过程中的几个要点：

问题简化和抽象，搭一个能反应问题本质却又尽量简单的 demo。
性能瓶颈的测试。千万不要想当然。
尽量不要用写 python 的方式来写 C++，C++ 代码的核心之一就是了解底层的情况。考虑每一个变量的范围，选择合适的数据类型，以及考虑数据在内存中的排布与存储。数据交互/函数调用的时候，注意避免移动/复制拷贝的开销。特别重要
算法性能的瓶颈不能只用算法复杂度来分析。常数项往往不可忽略。数据的计算外，内存读取的开销有时不可忽略。这个时候了解一些计算机体系结构的相关知识会很有帮助（不够就回去看 cs231 吧）。
相信算法库，stl 之类的并不会比手写的裸数据结构慢太多，但可读性和易用性好很多。
并行时候要更仔细的考虑。

Liufeng's Blogs

快速直方图算法以及怎样更好的写C++

Search

Table of Contents