c++ - 有没有快速内存访问的技巧？

Question

我是 C++ 编程世界的新手，很抱歉提出我的业余问题:

我在主内存(一维数组)中存储了一大块数据，我需要经常访问那里的一些数据，我的做法是:

float *x=new float[20];//array to store x;
int *indlistforx=new int[20];//array to store the index of x;
float *databank=new float[100000000];//a huge array to store data

/... fill data to databank.../


for (int i=0;i<N;i++)//where N is a very large number;
 {
  /... write index to indlistforx.../
  getdatafromdatabank(x, indlistforx, databank);
  //Based on the index provided by indlistforx, read data from databank then pass them to x

  /...do something with x.../
  };

是否有任何高效/快速的方法来访问这些数据(x 的索引未对齐，并且不可能对齐)？

非常感谢!

Answer 1

你还没有真正展示你是如何访问你的数据库的，所以这一切都是推测性的:

• indlistforx 是数据库中包含 20 个索引的列表，所以您要进行 20 次随机访问？

  • 这些指数的步幅是多少:它们是连续的、靠在一起的还是随机的？
  • 如果它们是连续的或靠得很近，对它们进行排序可能会有所帮助(因此您按升序读取以改进预取，并将来自同一缓存行的读取分组在一起)

• 20 个指数的不同组跳动了多少？它们可以重叠吗？

  • 如果它们不能重叠，那么您的数据库被有效地划分为一些 block 大小，然后在不同的处理器上处理每个分区可能会增加您可以使用的有效缓存量(如果您有多个处理器)
  • 如果请求可以重叠，如果数据库是只读的，同时运行它们仍然可以工作。如果有任何内容写入数据库，这将成为缓存抖动的秘诀

• 您能否在更高级别对访问进行重新排序以获得更好的缓存行为:更连续、更好的空间或时间引用局部性？

  • 这与我的第一个建议基本相同，但高于单个 indlistforx 请求的级别
  • 类似地，考虑重新排序以有效地划分数据库并尝试多处理器的想法

---

如果没有看到所有代码(或代表性示例，我知道即使这样可能太大)也很难深入了解更多细节。

但是，有一种通用技术可能会奏效……它也可能非常重量级，以至于实现成本超过节省的成本。

• 让您的 getfromdatabank 返回一个 future / promise /任何东西，而不是同步完成(或者一个包含 20 个 future 的 vector ，如果粒度不是太细的话)
• 尝试并行分派(dispatch)大量这些异步请求，要么在单独的线程中(访问 future 将是阻塞操作)，要么使用事件循环来处理诸如显式协程之类的完成
• 有一个专用线程聚合来自多个请求的所有数据库访问，并对它们重新排序以获得更好的缓存性能

只有在额外的同步开销主要由提高的读取性能决定，并且您可以有效地并行运行许多查询时，这才有用。