1

我对 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 的索引未对齐，并且不可能对齐）？

提前谢谢了！

4

3 回答 3

3

你还没有真正展示你是如何访问你的数据库的，所以这都是非常推测的：

  • 是indlistforx数据库中 20 个索引的列表，所以您正在执行 20 次随机访问？

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

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

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

  • 您能否在更高级别重新排序访问以获得更好的缓存行为：更顺序、更好的空间或时间参考局部性？

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

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

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

  • 让您的getfromdatabank回报成为未来/承诺/无论如何，而不是同步完成（或 20 个期货的向量，如果这不是太细粒度的话）
  • 尝试并行调度大量这些异步请求，或者在单独的线程中（访问期货将是一个阻塞操作），或者使用事件循环来处理诸如显式协同程序之类的完成
  • 有一个专用线程聚合来自多个请求的所有数据库访问，并对它们重新排序以获得更好的缓存性能

仅当额外的同步开销主要由改进的读取性能支配，并且您可以有效地并行运行许多查询时，这才有效。

于 2012-10-15T23:23:21.257 回答
2

由于需要初始化浮点数，因此您确实应该使用 std::vector<>，它并不慢，像这样构造和填充：

std::vector< float > databank( 100000000, 0.0f );

有几个加速选项：

1）如果有相当大的键（索引）重用，那么您可以使用某种缓存或记忆策略。看有关示例，http://www.boost.org/doc/libs/1_51_0/libs/flyweight/doc/index.html 。

2) 您可以使用 std::async() 将处理拆分为多个线程。

3）确保您的编译器已打开并正在使用 simd 指令（x86 上的 sse）。如果不通过使用编译器内在函数强制使用 simd。这将允许近 4 倍的改进。

于 2012-10-15T23:00:20.200 回答
1

问题不在于你如何代表你的databank. 问题是你如何使用它。在短时间内随机访问您的分散广泛的部分databank会扼杀您的表现。你getdatafromdatabank(x, indlistforx, databank)几乎indlistforx可以保证性能不佳。由此启用的随机访问indlistforx会带来显着的性能损失。如果随机访问是绝对必要的，因为使用你的算法如何databank工作，那只是你必须付出的代价。

如果您可以修改您的算法，以便它们访问您的databank. 更改getdatafromdatabank以便您仅指定第一个索引（要加载到的元素的索引x[0]），而不是 20 个索引的数组。

x大小为 20是否有原因？如果您勉强保留输出数组和1 级缓存x的相关块，您将获得最佳性能。如果大小超过此最佳大小databank，性能将开始下降，并且可能会显着下降。x

于 2012-10-15T23:54:13.953 回答