parallel suffix tree sort optimize diff speed

[sisong]

当前的-m diff约一半以上时间消耗在后缀数组排序上；可以考虑并行实现。
一种是增加一个接口，支持外部用多线程环境并行调用；另外就是内置并行代码（当前的想法是同时支持单线程、openMP、pthread、C++11thread可选）；

[JayXon]

sais本来就不算很快吧
试过libdivsufsort么？
另外msufsort4号称更快而且支持多线程，但是比较新可能有bug

[sisong]

最近会试试libdivsufsort；

补充： 已经完成libdivsufsort的支持，而且默认支持开启宏_OPENMP时支援openMP并行；

[sisong]

试了msufsort4，在xcode中单线程ok（速度和libdivsufsort相当），多线程运行时异常；
另外测试了占用的时间，libdivsufsort中能用openmp并行执行的代码(sssort)一般占程序总时间的15%左右；这部分就算减到0，也没有太大的意义；

[JayXon]

他的算法肯定是专门为并行设计的，作者自己的benchmark说是比divsufsort的multithread快好几倍
https://encode.ru/threads/2606-msufsort-4-update?p=50474&viewfull=1#post50474

Enwik8
MSufSort 4 single threaded 6.10
DivSufSort 2.0.2 single threaded 7.37
MSufSort 4 multi-threaded 1.86
DivSufSort 2.0.2 multi-threaded 5.37

Enwik9
MSufSort 4 single threaded 80.70
DivSufSort 2.0.2 single threaded 90.63
MSufSort 4 multi-threaded 24.91
DivSufSort 2.0.2 multi-threaded 82.05

[sisong]

看数据msufsort4多线程确实很快，但我在xcode下多线程版本内存访问异常:( ,单线程没有问题， 不知道是不是我为了能够编译过而做的小改动造成的；
ps：msufsort4用了非常多的C++高级特性，不知道是不是有必要这么用，还是为了用而用:(

[sisong]

msufsort4当前新版本的测试情况是单线程正常，多线程并行一部分用例正常（偏小数据量）部分崩溃（函数堆栈溢出？），已经把用例反馈给作者。

[sisong]

msufsort4 is very slow in some case(like GCC12.2SourceCode.tar) , build by vc2019; so continure used libdivsufsort(openmp changed to std::thread).

[rongekuta]

@sisong 看了hdiff的block 模式的算法， block算出来的指纹值 进行后缀排序，
采用了最基本的sort排序 复杂度应该是N^2 logN， 是否可以进行优化？ 比如采用 倍增法
（看样子因为int32 的值域远大于 ascii ， 其他的后缀排序算法未必能直接扩展支持int32）

[sisong]

谢谢 @rongekuta 提供的信息
当前确实是按blockSize对数据分块计算指纹（64bit），然后对其序号(32bit或64bit)构成的后缀数组进行了排序。
采取了一些方式来排序的，当前的算法最差情况下复杂度是：(N/blockSize)*(16*1024/blockSize)*log(N/blockSize) (常数项比较大)

可以尝试倍增法来优化速度，因为无法使用基数排序（单字符为uint64），估计算法复杂度一般为： (N/blockSize)*log(N/blockSize)*log(N/blockSize) （中间的log(N/blockSize)可以优化为14--20）

[JayXon]

have you tried https://github.com/IlyaGrebnov/libsais

[sisong]

@JayXon
I know it & but no tested it; Because it's Apache-2.0 license(best MIT) & used openmp(I want muti-thread);

[sisong]

@rongekuta 我实现了一个后缀数组倍增算法的版本，输出的补丁数据一致； 速度比我现在已有的版本(单线程时)还慢很多。
我猜测是内存访问时大量的缓存不命中造成。
算法复杂度 (N/blockSize)*log(16*1024/blockSize)*log(N/blockSize)
-- N是文件大小，hash数量n=(N+blockSize-1)/blockSize; sa[i]=i;
算法代码如下：

template<class TIndex>
struct cmp_sa_t{
    inline cmp_sa_t(const TIndex* _rank,size_t _n,size_t _k):rank(_rank),n(_n),k(_k){}
    inline bool operator ()(TIndex i,TIndex j){
        if (rank[i]!=rank[j]) return rank[i]<rank[j];
        if ((i+k<n)&(j+k<n)) return rank[i+k]<rank[j+k];
        return i>j;
    }
    const TIndex* const rank;
    const size_t n;
    size_t k;
};

template<class TIndex>
struct cmp_S_t{
    inline explicit cmp_S_t(const adler_hash_t* _S):S(_S){}
    inline bool operator ()(TIndex i,TIndex j){
        return S[i]<S[j];
    }
    const adler_hash_t* const S;
};

template<class TIndex>
static void sort_indexs(const adler_hash_t* S,TIndex* sa,size_t n,size_t blockSize){
    if (n<=1) return;
    std::vector<TIndex> rank(n);
    std::vector<TIndex> tmp(n);
    tmp[0]=0;
    for(size_t k=0;k<std::max(1,16*1024/blockSize);k=((k==0)?1:(k*2))){
        if (k==0){
            cmp_S_t<TIndex> cmp_s(S);
            std::sort(sa,sa+n,cmp_s);
            for(size_t i=1;i<n;i++) tmp[i]=tmp[i-1]+cmp_s(sa[i-1],sa[i]);
        }else{
            cmp_sa_t<TIndex> cmp_sa(rank.data(),n,k);
            std::sort(sa,sa+n,cmp_sa);
            for(size_t i=1;i<n;i++) tmp[i]=tmp[i-1]+cmp_sa(sa[i-1],sa[i]);
        }
        if (((tmp[n-1]+1)==n)) break;
        for(size_t i=0;i<n;i++) rank[sa[i]]=tmp[i];
    }
}

[sisong]

@JayXon

I test two case

• large txt(gcc source):

libsais thread    1:  9.255 s
libsais thread    8:  6.482 s
divsufsort thread 1: 11.636 s
divsufsort thread 8:  8.878 s

• large bin(qq apk):

libsais thread 1   :  7.953 s
libsais thread 8   :  6.793 s
divsufsort thread 1:  5.846 s
divsufsort thread 8:  3.863 s

Considering libsais's license and thread mode, so keep divsufsort now.

close #322

[rongekuta]

@sisong

good job！
看来拓展的倍增法性能并没有期望的好，
我研究研究下基于block的优化，我曾经设想过利用重复数据删除技术中的基于内容的切分方式来优化，但是看起来内存也很大，也很复杂。

最近的测试给了我一些想法（也许利用Rabin–Karp 算法 比后缀数组更快）：

有位同事提到了 zstd 也支持patch模式
https://github.com/facebook/zstd/wiki/Zstandard-as-a-patching-engine
我对比了HDiff 和 zstd的压缩效果和性能（在我的centos 虚拟机上）

表1 算法patch时间与效果
文件 Hdiff patch时间 Zstd patch时间 Hdiff patch文件大小 Zstd patch文件大小
test1.obb（32MB） 5.7 秒 0.2 秒 5.175MB 5.178MB
豌豆荚apk（24MB） 2.1 秒 0.17 秒 16KB 19KB
王者荣耀（1.8GB） 62 秒 23 秒 568MB 537MB

表2 算法的apply 时间对比
文件 Hdiff apply时间 Zstd apply时间
test1.obb（32MB） 0.085 秒 0.115 秒
豌豆荚apk（24MB） 0.07 秒 0.122 秒
王者荣耀（1.8GB） 11秒 7 秒

zstd 的算法是lz77 算法， 不用后缀数组（后缀数组看起来性能开销还是挺大）
不过可惜的是zstd的apply 的内存限制没有用， 不适合小内存场景（手机等）

我觉得很有意思， 有可能不走 后缀数组排序 这种大杀器， 只是利用 Rabin–Karp 算法（lz77用到的字符串匹配）
也可以达到很高的速度

[sisong]

@rongekuta

• hdiffz 的时候加了 -m-1 -cache -p-1 -d -c-zstd 参数吗? 这样对比更有可比性一些
• hdiffz 除了默认的-m匹配模式，还支持-s匹配模式， -m-1 -cache 换成 -s-16 参数再测试看看

[rongekuta]

@rongekuta

• hdiffz 的时候加了 -m-1 -p-1 -cache -d -c-zstd 参数吗? 这样对比更有可比性一些
• hdiffz 除了默认的-m匹配模式，还支持-s匹配模式， -m-1 换成 -s-16 参数再测试看看

• hdiffz 的时候加了 -m-1 -p-1 -cache -d -c-zstd 参数吗? 这样对比更有可比性一些
  确实没有加， 用的 hdiffz old new patch
  我后续加下测试下

• hdiffz 除了默认的-m匹配模式，还支持-s匹配模式， -m-1 换成 -s-16 参数再测试看看
  后续试一试

PS： 对比1.8GB文件采用的是 hdiff 64字节分块模式

[rongekuta]

@sisong
冒昧谈谈我的想法：

因为hdiff的内存限制机制 还有可扩展框架 适合 移动设备使用
在hdiff上尝试 rabin-karp 看看性能是否更好？

想法是遍历old文件采用固定长度（8字节）计算hash值，存到hash表，
此时我们并不需要把所有的hash值都存到里边，可以采用一定采样机制，稀疏化，降低hash的冲突
并让hash表可以适当缩小。

new文件也进行滑块hash，并在hash表中查找，并且匹配
这样计算量是O（n）的

思路除了后缀排序有点类似 hdiff 的block模式， 应该在博客中你也谈到了这个思路，但是考虑到hash表内存占用，没有利用这个思路。
我猜测采用稀疏采样， 未必效果有大的下降，同时性能应该不差后缀排序

[sisong]

@rongekuta 你说的这个思路，在压缩算法中很通用，但和我的设计目标有冲突：
压缩算法假设字典数据(这里就是oldFile)都在内存中，然后利用hash值的匹配来寻找多个可能匹配的位置，并返回最佳的一个匹配(匹配长度甚至可以短到3)。 可以知道，如果字典不在内存，每次匹配尝试都将是磁盘访问(远远低于内存随机访问)时,速度将无法接受。 同理，解压(即应用补丁)的时候也必然要求 字典数据 要在内存中。
hdiffz -s的设计目标是支持oldFile可以上百GB，oldFile将始终在磁盘上，那匹配的时候就需要尽量少的尝试匹配位置(当前只会尝试1--2个可能位置)，然后一次匹配尽量长的相等长度(匹配长度最短16)，从而降低磁盘随机访问次数； 所以，hpatchz应用补丁的时候，oldFile在磁盘上时,速度也能勉强接受。

[rongekuta]

@sisong
你说的随机访问问题确实存在，大规模文件，采用细粒度的hash是会面临随机访问磁盘的问题，需要在上层加上一层分块机制；在重复数据删除也是这样两层设计；
当前我们文件大小限制是2GB（还没有达到上百GB）； 内存应该能用到 512MB
zstd这方面为了性能采用全量加载内存；

PS：
我在zstd提issue 看看 zstd是否存在改成 类似Hdiff文件缓存机制（ 不将 old文件（他们成为dict）全量加载内存）的可能性以及风险；