在95%的情况下,当值为0或1时,是否对非常大的阵列上的随机访问进行了优化?

想到的一个简单的可能性是,对于常见情况,每个值保留一个2位的压缩数组,每个值保留一个单独的4字节(原始元素索引为24位,实际值为8位,因此 (idx << 8) | value) )对其他数组进行排序。

查找值时,首先在2bpp数组中进行查找(O(1));如果您找到0、1或2,这就是您想要的值;如果找到3,则意味着必须在辅助数组中查找它。在这里,您将执行二进制搜索以查找 指数 将感兴趣的值左移8(O(log(n)加上一个小的n,因为这应该是1%),然后从4字节的内容中提取值。

std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;

uint8_t lookup(unsigned idx) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
    // usual (likely) case: value between 0 and 2
    if(v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
    // some coherency checks
    if(ptr == sec_arr.end()) std::abort();
    if((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}

void populate(uint8_t *source, size_t size) {
    main_arr.clear(); sec_arr.clear();
    // size the main storage (round up)
    main_arr.resize((size+3)/4);
    for(size_t idx = 0; idx < size; ++idx) {
        uint8_t in = source[idx];
        uint8_t &target = main_arr[idx>>2];
        // if the input doesn't fit, cap to 3 and put in secondary storage
        if(in >= 3) {
            // top 24 bits: index; low 8 bit: value
            sec_arr.push_back((idx << 8) | in);
            in = 3;
        }
        // store in the target according to the position
        target |= in << ((idx & 3)*2);
    }
}

对于您提议的数组,第一个数组需要10000000/4=2500000字节,第二个数组需要10000000*1%*4 B=400000字节;因此,2900000字节,即不到原始数组的三分之一,而使用最多的部分都保存在内存中,这应该有利于缓存(甚至可能适合L3)。

如果您需要超过24位的寻址,则必须调整“辅助存储”;扩展它的一个简单方法是使用256个元素的指针数组来切换索引的前8位,并转发到如上所述的24位索引排序数组。

快速基准测试

#include <algorithm>
#include <vector>
#include <stdint.h>
#include <chrono>
#include <stdio.h>
#include <math.h>

using namespace std::chrono;

/// XorShift32 generator; extremely fast, 2^32-1 period, way better quality
/// than LCG but fail some test suites
struct XorShift32 {
    /// This stuff allows to use this class wherever a library function
    /// requires a UniformRandomBitGenerator (e.g. std::shuffle)
    typedef uint32_t result_type;
    static uint32_t min() { return 1; }
    static uint32_t max() { return uint32_t(-1); }

    /// PRNG state
    uint32_t y;

    /// Initializes with seed
    XorShift32(uint32_t seed = 0) : y(seed) {
        if(y == 0) y = 2463534242UL;
    }

    /// Returns a value in the range [1, 1<<32)
    uint32_t operator()() {
        y ^= (y<<13);
        y ^= (y>>17);
        y ^= (y<<15);
        return y;
    }

    /// Returns a value in the range [0, limit); this conforms to the RandomFunc
    /// requirements for std::random_shuffle
    uint32_t operator()(uint32_t limit) {
        return (*this)()%limit;
    }
};

struct mean_variance {
    double rmean = 0.;
    double rvariance = 0.;
    int count = 0;

    void operator()(double x) {
        ++count;
        double ormean = rmean;
        rmean     += (x-rmean)/count;
        rvariance += (x-ormean)*(x-rmean);
    }

    double mean()     const { return rmean; }
    double variance() const { return rvariance/(count-1); }
    double stddev()   const { return std::sqrt(variance()); }
};

std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;

uint8_t lookup(unsigned idx) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
    // usual (likely) case: value between 0 and 2
    if(v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
    // some coherency checks
    if(ptr == sec_arr.end()) std::abort();
    if((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}

void populate(uint8_t *source, size_t size) {
    main_arr.clear(); sec_arr.clear();
    // size the main storage (round up)
    main_arr.resize((size+3)/4);
    for(size_t idx = 0; idx < size; ++idx) {
        uint8_t in = source[idx];
        uint8_t &target = main_arr[idx>>2];
        // if the input doesn't fit, cap to 3 and put in secondary storage
        if(in >= 3) {
            // top 24 bits: index; low 8 bit: value
            sec_arr.push_back((idx << 8) | in);
            in = 3;
        }
        // store in the target according to the position
        target |= in << ((idx & 3)*2);
    }
}

volatile unsigned out;

int main() {
    XorShift32 xs;
    std::vector<uint8_t> vec;
    int size = 10000000;
    for(int i = 0; i<size; ++i) {
        uint32_t v = xs();
        if(v < 1825361101)      v = 0; // 42.5%
        else if(v < 4080218931) v = 1; // 95.0%
        else if(v < 4252017623) v = 2; // 99.0%
        else {
            while((v & 0xff) < 3) v = xs();
        }
        vec.push_back(v);
    }
    populate(vec.data(), vec.size());
    mean_variance lk_t, arr_t;
    for(int i = 0; i<50; ++i) {
        {
            unsigned o = 0;
            auto beg = high_resolution_clock::now();
            for(int i = 0; i < size; ++i) {
                o += lookup(xs() % size);
            }
            out += o;
            int dur = (high_resolution_clock::now()-beg)/microseconds(1);
            fprintf(stderr, "lookup: %10d µs\n", dur);
            lk_t(dur);
        }
        {
            unsigned o = 0;
            auto beg = high_resolution_clock::now();
            for(int i = 0; i < size; ++i) {
                o += vec[xs() % size];
            }
            out += o;
            int dur = (high_resolution_clock::now()-beg)/microseconds(1);
            fprintf(stderr, "array:  %10d µs\n", dur);
            arr_t(dur);
        }
    }

    fprintf(stderr, " lookup |   ±  |  array  |   ±  | speedup\n");
    printf("%7.0f | %4.0f | %7.0f | %4.0f | %0.2f\n",
            lk_t.mean(), lk_t.stddev(),
            arr_t.mean(), arr_t.stddev(),
            arr_t.mean()/lk_t.mean());
    return 0;
}

(code and data always updated in my Bitbucket)

上面的代码使用随机数据填充一个10M元素数组,这些数据按照帖子中指定的OP分布,初始化我的数据结构,然后:

• 使用我的数据结构执行10M个元素的随机查找
• 对原始数组执行相同的操作。

(请注意,在顺序查找的情况下,数组总是以巨大的优势获胜,因为它是您可以执行的最有利于缓存的查找)

最后两个块重复50次并计时;最后,计算并打印每种查找类型的平均值和标准偏差,以及加速比(lookup\u mean/array\u mean)。

我用g++5.4.0编译了上面的代码( -O3 -static ,加上一些警告),并在一些机器上运行;他们中的大多数都在运行Ubuntu 16.04,一些是旧的Linux,一些是新的Linux。我认为操作系统在这种情况下根本不应该相关。

            CPU           |  cache   |  lookup (µs)   |     array (µs)  | speedup (x)
Xeon E5-1650 v3 @ 3.50GHz | 15360 KB |  60011 ±  3667 |   29313 ±  2137 | 0.49
Xeon E5-2697 v3 @ 2.60GHz | 35840 KB |  66571 ±  7477 |   33197 ±  3619 | 0.50
Celeron G1610T  @ 2.30GHz |  2048 KB | 172090 ±   629 |  162328 ±   326 | 0.94
Core i3-3220T   @ 2.80GHz |  3072 KB | 111025 ±  5507 |  114415 ±  2528 | 1.03
Core i5-7200U   @ 2.50GHz |  3072 KB |  92447 ±  1494 |   95249 ±  1134 | 1.03
Xeon X3430      @ 2.40GHz |  8192 KB | 111303 ±   936 |  127647 ±  1503 | 1.15
Core i7 920     @ 2.67GHz |  8192 KB | 123161 ± 35113 |  156068 ± 45355 | 1.27
Xeon X5650      @ 2.67GHz | 12288 KB | 106015 ±  5364 |  140335 ±  6739 | 1.32
Core i7 870     @ 2.93GHz |  8192 KB |  77986 ±   429 |  106040 ±  1043 | 1.36
Core i7-6700    @ 3.40GHz |  8192 KB |  47854 ±   573 |   66893 ±  1367 | 1.40
Core i3-4150    @ 3.50GHz |  3072 KB |  76162 ±   983 |  113265 ±   239 | 1.49
Xeon X5650      @ 2.67GHz | 12288 KB | 101384 ±   796 |  152720 ±  2440 | 1.51
Core i7-3770T   @ 2.50GHz |  8192 KB |  69551 ±  1961 |  128929 ±  2631 | 1.85

结果是。。。混血儿!

1. 总的来说,在这些机器中的大多数都有某种加速,或者至少它们是平起平坐的。
2. 阵列真正胜过“智能结构”查找的两种情况是在具有大量缓存且不是特别繁忙的机器上:上面的至强E5-1650(15 MB缓存)是夜间构建的机器,目前相当空闲;Xeon E5-2697(35 MB缓存)也是一款在空闲时间进行高性能计算的机器。这是有道理的,原始阵列完全适合其巨大的缓存,因此紧凑的数据结构只会增加复杂性。
3. 在“性能谱”的另一端,阵列的速度稍微快一点,我的NAS使用的是简陋的赛扬;它的缓存如此之少,以至于阵列和“智能结构”都不适合它。缓存足够小的其他机器执行类似的操作。
4. Xeon X5650必须谨慎使用-它们是非常繁忙的双插槽虚拟机服务器上的虚拟机;很可能,虽然名义上它有相当数量的缓存,但在测试期间,它会被完全无关的虚拟机多次抢占。

另一种选择可能是

• 检查结果是0、1还是2
• 如果没有,则执行常规查找

换句话说,类似于:

unsigned char lookup(int index) {
    int code = (bmap[index>>2]>>(2*(index&3)))&3;
    if (code != 3) return code;
    return full_array[index];
}

哪里 bmap 每个元素使用2位,值3表示“其他”。

这个结构更新起来很简单,占用了25%以上的内存,但大部分只在5%的情况下查找。当然,像往常一样,这是否是一个好主意取决于许多其他条件,因此唯一的答案是尝试实际使用。

这与其说是一个具体的答案,不如说是一个“冗长的评论”

除非你的数据是众所周知的,否则我怀疑任何人都不能直接回答你的问题(我不知道有什么与你的描述相匹配,但我也不知道所有用例的所有数据模式)。稀疏数据是高性能计算中的常见问题,但它通常是“我们有一个非常大的数组,但只有一些值是非零的”。

对于像我认为你的模式这样不为人所知的模式,没有人会直接知道哪个更好,这取决于细节:随机访问的随机性如何-系统是访问数据项的集群,还是完全随机的,就像从统一的随机数生成器来的一样。表格数据是完全随机的,还是有0的序列,然后是1的序列,还有其他值的分散?如果您有相当长的0和1序列,则运行长度编码可以很好地工作,但如果您有“0/1棋盘”,则运行长度编码将不起作用。此外,您还必须保留一个“起点”表,以便您能够以合理的速度到达相关地点。

我很久以前就知道,一些大型数据库只是RAM中的一个大表(本例中是电话交换机用户数据),其中的一个问题是处理器中的缓存和页表优化非常无用。调用方很少与最近调用某人的调用方相同,因此没有任何类型的预加载数据,它只是纯粹的随机数据。对于这种访问类型,大页面表是最好的优化。

在很多情况下,在“速度和小尺寸”之间进行折衷是软件工程中必须选择的事情之一[在其他工程中,这不一定是一种折衷]。因此,“为更简单的代码浪费内存”通常是首选。从这个意义上说,“简单”的解决方案很可能在速度上更好,但如果您对RAM有“更好”的使用,那么优化表的大小将为您提供足够的性能和大小上的良好改进。有很多不同的方法可以实现这一点-正如在注释中所建议的那样,一个2位字段存储两个或三个最常见的值,然后是其他值的一些替代数据格式-哈希表是我的第一种方法,但列表或二叉树也可能起作用-同样,这取决于“不是0、1或2”的模式。同样,这取决于值在表中是如何“分散”的-它们是在集群中还是更均匀地分布?

但问题是,您仍然在从RAM读取数据。然后,您将花费更多的代码来处理数据,包括一些代码来处理“这不是一个常见值”。

最常见的压缩算法的问题是,它们基于解包序列,因此不能随机访问它们。而且,将大数据分割成块(例如,一次256个条目),然后将256个条目解压缩到uint8\t数组中,获取所需数据,然后丢弃未压缩的数据,这样的开销不太可能给您带来好的性能—当然,假设这很重要。

最后,您可能需要实现注释/答案中的一个或几个想法来测试,看看它是否有助于解决您的问题,或者内存总线是否仍然是主要的限制因素。

我过去所做的是在 正面 位集的。

与Matteo的答案相比,这将占用一半的空间,但如果“异常”查找速度较慢(即存在许多异常),则可能会更慢。

然而,通常情况下,“缓存为王”。

除非你的数据有规律,否则就不可能有任何合理的速度或大小优化,而且——假设你的目标是一台普通计算机——10 MB也没什么大不了的。

你的问题有两个假设:

1. 数据存储不好,因为您没有使用所有的位
2. 更好地存储会使事情更快。

我认为这两个假设都是错误的。在大多数情况下,存储数据的适当方式是存储最自然的表示。在您的情况下,这就是您想要的:一个字节表示0到255之间的数字。任何其他表示都将更加复杂,因此,在所有其他条件相同的情况下,速度较慢,更容易出错。要想偏离这一一般原则,您需要一个比95%的数据上可能存在的六个“浪费”位更有说服力的理由。

对于第二个假设,如果且仅当更改数组大小导致缓存未命中大幅减少时,才是正确的。这是否会发生只能通过分析工作代码来确定,但我认为这不太可能产生实质性的影响。因为在这两种情况下,您都将随机访问阵列,因此处理器将很难知道在这两种情况下要缓存和保留哪些数据位。

如果数据和访问是均匀随机分布的,那么性能可能取决于访问中避免外部级别缓存丢失的部分。优化这一点需要知道缓存中可以可靠容纳的阵列大小。如果缓存足够大,每五个单元可以容纳一个字节,最简单的方法可能是让一个字节保存0-2范围内的五个基三编码值(有243个5个值的组合,因此可以放入一个字节),以及一个10000000字节数组,只要基三值指示“2”,就会查询该数组。

如果缓存没有那么大,但每8个单元可以容纳一个字节,那么就不可能使用一个字节的值从所有6561个可能的八个基3值组合中进行选择,但由于将0或1更改为2的唯一效果是导致不必要的查找,因此正确性不需要支持所有6561。相反,我们可以关注256个最“有用”的值。

特别是如果0比1更常见,或者反之亦然,一个好的方法可能是使用217个值对包含5个或更少1的0和1的组合进行编码,16个值对xxxx0000到xxxx1111进行编码,16个值对0000xxxx到1111xxxx进行编码,一个值对xxxxxxxx进行编码。四个值将保留下来,以供人们可能发现的任何其他用途。如果数据按所述随机分布,则所有查询中的绝大多数都会命中仅包含0和1的字节(在所有8个组中的约2/3中,所有位都是0和1,其中约7/8的字节具有6个或更少的1位);绝大多数没有这样做的人会在一个包含四个x的字节中着陆,并且有50%的几率会在0或1上着陆。因此,大约四分之一的查询需要进行大型数组查找。

如果数据是随机分布的,但缓存的大小不足以每八个元素处理一个字节,那么可以尝试使用这种方法,每个字节处理八个以上的项,但除非对0或1有强烈的偏向,否则可以在不必在大数组中查找的情况下处理的值的分数将随着每个字节处理的数量的增加而减少。

我将添加到 @o11c 的回答,因为他的措辞可能有点混乱。 如果需要压缩最后一位和CPU周期,我会执行以下操作。

我们将从构建 平衡的 二元搜索树,包含5%的“其他”案例。对于每个查找,您都可以快速遍历树:您有10000000个元素:其中5%在树中:因此树数据结构包含500000个元素。在O(log(n))时间内遍历此过程,将得到19次迭代。我不是这方面的专家,但我想还有一些内存高效的实现。让我们猜测一下:

• 平衡树,因此可以计算子树位置(索引不需要存储在树的节点中)。与堆(数据结构)存储在线性内存中的方式相同。
• 1字节值(2到255)
• 索引为3字节(10000000需要23位,适合3字节)

总计4个字节:500000*4=1953 kB。适合缓存!

对于所有其他情况(0或1),可以使用位向量。请注意,对于随机访问,您不能忽略5%的其他情况:1.19 MB。

这两者的结合使用了大约3099 MB。使用此技术,您将节省3.08倍的内存。

然而,这并没有击败 @意大利马特奥 (使用2.76 MB),很遗憾。我们还有什么可以做的吗?最消耗内存的部分是树中索引的3个字节。如果我们能将这个值降到2,我们将节省488kB,总内存使用量将是:2.622MB,这是更小的!

我们如何做到这一点?我们必须将索引减少到2个字节。同样,10000000需要23位。我们需要能够删除7位。我们可以简单地将10000000个元素的范围划分为78125个元素的2^7(=128)个区域。现在,我们可以为每个区域构建一个平衡树,平均包含3906个元素。只需将目标索引除以2^7(或一个位移位),即可选择正确的树 >> 7 )。现在需要存储的索引可以用剩余的16位表示。请注意,需要存储的树的长度有一些开销,但这可以忽略不计。还要注意,这种分割机制减少了遍历树所需的迭代次数,现在减少到7次迭代,因为我们减少了7位:只剩下12次迭代。

请注意,从理论上讲,您可以重复此过程以切断接下来的8位,但这需要您创建2^15个平衡树,平均约305个元素。这将导致2.143MB的内存,只需4次迭代即可遍历树,与我们开始的19次迭代相比,这是一个相当大的加速。

最后得出的结论是:这比2位向量策略的内存使用量要小,但要实现起来却很困难。但是,如果它能够区分是否适合缓存,那么可能值得一试。

如果只执行读取操作,最好不要将值赋给单个索引,而是赋给索引的间隔。

例如:

[0, 15000] = 0
[15001, 15002] = 153
[15003, 26876] = 2
[25677, 31578] = 0
...

这可以通过结构来完成。如果您喜欢OO方法,还可能需要定义类似于此的类。

class Interval{
  private:
    uint32_t start; // First element of interval
    uint32_t end; // Last element of interval
    uint8_t value; // Assigned value

  public:
    Interval(uint32_t start, uint32_t end, uint8_t value);
    bool isInInterval(uint32_t item); // Checks if item lies within interval
    uint8_t getValue(); // Returns the assigned value
}

现在,您只需通过一个间隔列表进行迭代,并检查您的索引是否位于其中一个间隔内,平均而言,该间隔占用的内存更少,但占用的CPU资源更多。

Interval intervals[INTERVAL_COUNT];
intervals[0] = Interval(0, 15000, 0);
intervals[1] = Interval(15001, 15002, 153);
intervals[2] = Interval(15003, 26876, 2);
intervals[3] = Interval(25677, 31578, 0);
...

uint8_t checkIntervals(uint32_t item)

    for(int i=0; i<INTERVAL_COUNT-1; i++)
    {
        if(intervals[i].isInInterval(item) == true)
        {
            return intervals[i].getValue();
        }
    }
    return DEFAULT_VALUE;
}

如果按大小降序排列时间间隔,则会增加提前找到要查找的项目的可能性,从而进一步降低平均内存和CPU资源使用率。

您还可以删除大小为1的所有间隔。将相应的值放入映射中,仅当在间隔中找不到要查找的项目时才进行检查。这也应该会稍微提高平均性能。

很久很久以前,我只记得。。。

在大学里,我们的任务是加速光线跟踪器程序,该程序必须通过算法从缓冲区阵列中反复读取。一位朋友告诉我要始终使用4字节倍数的RAM读取。因此,我将阵列的模式从[x1,y1,z1,x2,y2,z2,…,xn,yn,zn]更改为[x1,y1,z1,0,x2,y2,z2,0,…,xn,yn,zn,0]。意味着在每个三维坐标后添加一个空字段。经过一些性能测试:速度更快。 长话短说:从RAM中读取数组中4个字节的倍数,也可以从正确的起始位置读取,因此您可以在其中读取一个小簇,其中包含搜索到的索引,并从cpu中的这个小簇中读取搜索到的索引。(在您的情况下,不需要插入填充字段,但概念应该明确)

也许其他倍数也可能是新系统的关键。

我不知道这是否适用于你的情况,所以如果不适用:对不起。如果成功的话,我很高兴听到一些测试结果。

PS:哦,如果有任何访问模式或附近的访问索引,您可以重用缓存的集群。

PPS:可能是,倍数更像是16字节之类的,那是很久以前的事了,我能准确地记住。

考虑到这一点,您可以拆分数据,例如:

• 一个位集,它被索引并表示值0(std::vector在这里很有用)
• 获取索引并表示值1的位集
• 值2的std::向量,包含引用此值的索引
• 其他值的映射(或std::vector>)

在这种情况下,所有值都会一直显示到给定的索引,因此您甚至可以删除其中一个位集,并将该值表示为在其他位集中丢失的值。

这将为这种情况节省一些内存,但会使最坏的情况变得更糟。 您还需要更多的CPU能力来进行查找。

确保测量!

就像Mats在评论回答中提到的那样,如果不知道什么才是最好的解决方案,很难说出来 明确地 您拥有什么样的数据(例如,是否有长时间运行的0等),以及您的访问模式是什么样的(“随机”是指“到处都是”还是“不完全以线性方式”或“每个值都只随机一次”或…)。

这就是说,我们想到了两种机制:

• 位阵列;i、 例如,如果只有两个值,则可以将数组压缩8倍;如果您有4个值(或“3个值+所有其他值”),则可以压缩2倍。这可能不值得麻烦,需要基准测试,尤其是如果你有 真正地 随机访问模式,从缓存中逃逸,因此根本不会更改访问时间。
• (index,value) 或 (value,index) 表格。一、 例如,对于1%的情况有一个非常小的表,对于5%的情况可能有一个表(因为所有索引都有相同的值,所以只需要存储索引),对于最后两种情况有一个大的压缩位数组。“表格”是指可以相对快速地查找的东西;i、 例如,可能是哈希、二叉树等等,这取决于您的可用内容和实际需要。如果这些子表适合您的一级/二级缓存,您可能会很幸运。

我对C不是很熟悉,但在 C类++ 您可以使用 无符号字符 表示0-255范围内的整数。

与正常值相比 内景 (再一次,我来自 JAVA 和 C类++ 世界)其中 4字节 (32位)是必需的 无符号字符 需要 1字节 (8位)。 因此,它可能会将阵列的总大小减少75%。

您已经简洁地描述了数组的所有分布特征; 投掷阵列 。

您可以轻松地使用随机方法替换数组,该方法生成与数组相同的概率输出。

如果一致性很重要(为相同的随机索引生成相同的值),请考虑使用 bloom filter 和/或 hash map 跟踪重复点击。但是,如果您的阵列访问确实是随机的,那么这完全没有必要。