标签: cpu-cache

我有一个应用程序,通过250 MB的数据流,应用一个简单快速的神经网络阈值函数到数据块(每个只有2个32位字).基于(非常简单的)计算的结果,块被不可预测地推入64个箱中的一个.所以这是一个大流和64个较短(可变长度)的流.

使用不同的检测功能重复多次.

计算是内存带宽有限.我可以说这是因为即使我使用的计算密集程度更高的判别函数也没有速度变化.

构造新流的写入以优化内存带宽的最佳方法是什么？我特别认为理解缓存使用和缓存行大小可能在这方面发挥重要作用.想象一下最糟糕的情况,我有64个输出流,运气不好,许多映射到同一个缓存行.然后,当我将下一个64位数据写入流时,CPU必须将过时的高速缓存行清除到主存储器,然后加载到正确的高速缓存行中.每个都使用64 BYTES的带宽...所以我的带宽有限的应用可能会浪费95%的内存带宽(尽管在这个假设的最坏情况下).

甚至很难尝试测量效果,因此围绕它设计方法更加模糊.或者我甚至追逐一个幽灵瓶颈,以某种方式硬件优化得比我更好？

我正在使用Core II x86处理器,如果这有任何区别的话.

编辑:这是一些示例代码.它通过一个数组流,并将其元素复制到伪随机选择的各种输出数组.使用不同数量的目标bin运行相同的程序会产生不同的运行时,即使完成了相同数量的计算和内存读写操作:

2个输出流:13秒
8个输出流:13秒
32个输出流:19秒
128个输出流:29秒
512个输出流:47秒

使用512与2输出流之间的差异是由缓存行驱逐开销引起的4倍(可能是??).

#include <stdio.h>
#include <stdlib.h>
#include <ctime>

int main()
{
  const int size=1<<19;
  int streambits=3;
  int streamcount=1UL<<streambits; // # of output bins
  int *instore=(int *)malloc(size*sizeof(int));
  int **outstore=(int **)malloc(streamcount*sizeof(int *));
  int **out=(int **)malloc(streamcount*sizeof(int));
  unsigned int seed=0;

  for (int j=0; j<size; j++) instore[j]=j;

  for (int i=0; i< streamcount; ++i) 
    outstore[i]=(int *)malloc(size*sizeof(int));

  int startTime=time(NULL);
  for (int k=0; k<10000; k++) {
    for (int i=0; i<streamcount; i++) out[i]=outstore[i]; …

我已经看到了一些工具,让你可以天寒C和C++的缓存,但该工具(Valgrind的)的目的是为Linux和他们的状态在他们的网站实在是太多了工作,制定适用于Windows).

C#开发人员可以使用任何工具来分析缓存吗？

我有ANTS Performance Profiler但它不执行缓存分析.

我有Intel Core IvyBridge处理器，Intel®Core™i7-3770 CPU @ 3.40GHz（L1-32KB，L2-256KB，L3-8MB）。我知道L3具有包容性，并且在多个内核之间共享。我想了解有关我的系统的以下内容

第1部分 ：

1. L1是包含性还是排他性？
2. L2是包含性还是排他性？

第2部分 ：

如果L1和L2都包括在内，则为了找到L2的访问时间，我们首先声明一个大小大于L2高速缓存（256KB）的数组（1MB），然后开始访问整个数组以加载到L2高速缓存中。之后，由于缓存行大小为64B，所以我们以64B的步长从开始索引到结束索引访问数组元素。为了获得更好的准确结果，我们重复此过程（访问索引处index，开始到末尾的数组元素）多次，比如说进行一百万次并取平均值。

我的理解为什么这种方法会给出正确的结果，如下所示：当我们访问大小大于L2缓存大小的数组时，整个数组将从主内存加载到L3，然后从L3加载到L2，再从L2加载到L1。整个数组的最后32KB位于L1中，因为最近已对其进行了访问。由于具有包容性和高速缓存一致性，整个阵列也存在于L2和L3高速缓存中。现在，当我从起始索引再次开始访问数组时，起始索引不在 L1高速缓存中，而是在L2高速缓存中，因此将出现高速缓存未命中，并且将从L2高速缓存中加载它。这样，整个数组的所有元素将需要更长的访问时间，总的来说，我将获得整个数组的总访问时间。要获得单次访问权限，我将获得总访问次数的平均值。

我的问题是- 我正确吗？

提前致谢 。

我正在寻找.Net中的数据结构,它保持异构结构在内存中连续,以便对cpu-cache友好.

这个类型的数据结构在这个博客中解释:T-machine.org在Iteration 4.

在.Net中,值类型(结构)数组使数据在内存中保持连续,但这仅适用于非泛型数组.我试图创建一个ValueType[],但结构框是盒装的.因此,引用在内存中是连续的,而不是真实的数据.

经过多次尝试,我认为在.Net中本身不可能.我看到的唯一可能的解决方案是手动管理字节数组中结构的分类和反序列化,但我不认为它会是高性能的.

你找到了原生解决方案吗？我的更好的解决方案？

编辑1:我正在尝试实现T-Machine.org博客中描述的实体组件系统.

我正在尝试用C++实现股票匹配引擎/订单簿,并且正在寻找更加缓存友好的架构.目前,我的数据结构如下:

• 极限价格的侵入式rb-tree.
• 用于以限价价格持有订单的侵入性双重链表.

我已经考虑过替换rb-tree的方法,例如本身链接的稀疏数组的稀疏数组,但我相信rb-tree是一个更好的用例,因为我正在处理一本稀疏的书.现在,对于双向链表,我考虑过使用数组.除了填充后调整大小,附加和遍历将是最佳的,但删除将需要移动或跳过删除的条目.我还考虑了一个展开的链表,但是从我的研究和测试来看,当条目是几个字节而不是更大的Order结构时,它似乎工作得更好.

是否还有其他人可以指出的数据结构,尤其是优化缓存友好性？

另一方面,如果我使用LIFO堆栈作为内存池并提供带有来自此堆栈的对象的双向链接引用列表以重用最近删除的引号,则它将保留缓存时间局部性,但不一定保留空间局部性.我的直觉在这方面是否正确？

另外,我试图在linux中使用perf stat进行相当多的测试和分析缓存,但这并不容易.如果有人有关于如何进行缓存分析的更多提示,那么他们将非常受欢迎.

最后,请不要对过早优化发表评论.我这样做主要是为了锻炼和学习更多.这个项目不用于生产,我没有完成时间表.谢谢!

编辑更清晰,这与我当前的实现类似,最初来自https://web.archive.org/web/20110219163448/http://howtohft.wordpress.com/2011/02/15/how-to -build-a-fast-limit-order-book /:

限制订单簿(LOB)必须实现三个主要操作:添加,取消和执行.目标是在O(1)时间内实施这些操作,同时使交易模型能够有效地提出诸如"什么是最佳报价和报价？","价格A和B之间有多少交易量？"之类的问题.或者"订单X在书中的当前位置是什么？"

一本书中的绝大多数活动通常由增加和取消操作组成,因为做市商争夺头寸,执行距离遥远(实际上我会争辩说许多股票的大部分有用信息,特别是在早上,是添加和取消的模式,而不是执行,但这是另一个帖子的主题).添加操作在要以特定限价执行的订单列表的末尾下订单,取消操作从书中的任何地方删除订单,并且执行从书的内部删除订单(内部该书定义为最高购买价格的最早买单和最低卖价的最早卖单.这些操作中的每一个都是一个id号(下面的伪代码中的Order.idNumber),

Order
  int idNumber;
  bool buyOrSell;
  int shares;
  int limit;
  int entryTime;
  int eventTime;
  Order *nextOrder;
  Order *prevOrder;
  Limit *parentLimit;

Limit  // representing a single limit price
  int limitPrice;
  int size;
  int totalVolume;
  Limit *parent;
  Limit *leftChild;
  Limit *rightChild;
  Order *headOrder;
  Order *tailOrder;

Book
  Limit *buyTree;
  Limit *sellTree;
  Limit *lowestSell;
  Limit *highestBuy;

我们的想法是使用limitPrice排序的Limit对象的二叉树,每个对象本身都是Order对象的双向链接列表.本书的每一面,即购买限额和卖出限额,应该在不同的树中,以便书的内部分别对应于买入限价树的结束和开始,并且卖出限价树.每个订单也是一个键入idNumber的地图中的条目,每个限制也是一个键入limitPrice的地图中的条目.

使用此结构,您可以轻松实现这些关键操作并获得良好的性能:

• 添加 - O(log M)为限制的第一个订单,所有其他的O(1)
• 取消 - O(1)
• 执行 - O(1) …

我有一个C++程序,我想通过检查CPU缓存的命中数和未命中数来量化它的性能.

最好的方法是什么？

我尝试使用英特尔的性能计数器监视器,但它使用了在Yosemite上禁用的未签名内核扩展.我显然可以禁用检查以不加载未签名的kexts,但我不想沿着那条路走下去.

还有其他可能的方式我不知道吗？

根据包括Wikipedia在内的一些资料，实现二叉树的两种最常用的方法是：

1. 每个节点明确拥有其子节点的节点和指针（或引用）。
2. 子节点的位置由其父节点的索引隐式给出的数组。