哈西表查询中的指令预测问题
哈西表，大家都非常熟悉了，对于哈西查询算法，如果从ｃｐｕ的角度看问题，会有些不同的感觉。 <br />如下代码是找出我们匹配的一项 <br /><br />struct connection * lookup(struct bucket * head,unsigned int saddr, unsigned int daddr, unsigned short sport, unsigned short dport) <br />{ <br /> struct connection *conn = head->conn; <br /> <br /> for(; NULL != conn; conn = conn->next){ <br /> if(...) <br /> break; <br /> } <br /> <br /> return conn; <br /><br />} <br />假设我们不希望有太多的内存被占用，或者哈西值总是无法满足我们的分布要求（如果效果很好，就没有必要看下去了:-)），所以让我们来考虑上面代码的效率。如果不考虑ｃａｃｈｅ ｍｉｓｓ 的情况，那么就来考虑指令流水的问题。 <br />现在我们所使用的指令预测大致为经典的 ｔｗｏ－ｌｅｖｅｌ ｐｒｅｄｉｃａｔｉｏｎ， ｇｓｈａｒｅ的 ｈｙｂｒｉｄ ｐｒｅｄｉｃａｔｉｏｎ， ａｇｒｅｅ ｐｒｅｄｉｃａｔｉｏｎ．．．他们都是以跳转指令的地址，作为基础。所以近乎每一次的查询几乎都会产生ｍｉｓｓｐｒｅｄｉｃａｔｉｏｎ，产生延迟的时钟是ｐｉｐｅｌｉｎｅ的级数，为了解决这个问题，我使用了很笨的方法，就是为每一个桶产生一个相同的查询函数，简单的测试结果告诉我提高了２７％。 代码如下： <br /><br /> conn = bucket ->lookup( saddr, daddr, sport, dport); <br />（说实话上面实验仅仅来验证自己的观点，实际应用中同样会产生指令预测失败。因为我们不能奢望总是会找上次一样的地方（ｃｏｒｅ２的指令预测，在上面的代码将使用ｌｏｏｐ ｃｏｕｎｔｅｒ ）） <br /><br />所以我将ｈａｓｈ设计如下 <br />struct list{ <br /> <br /> struct list *next; <br /> struct list *prev; <br /><br />}; <br />struct connection { <br /> struct list link; <br /> unsigned long saddr; <br /> unsigned long daddr; <br /> unsigned short sport; <br /> unsigned short dport; <br /> int state; <br /><br />}; <br />struct bucket { <br /> struct list ｈｅａｄ; <br /> struct connection *cache; <br />}; <br />初始化之后ｂｕｃｋｅｔ 与 ｃｏｎｎ 构成了一个双向闭环，ｌｉｎｕｘ这样的结构比比皆是。 <br /> <br />上面代码希望使用公共的查询函数完成指令预测的效果减少指令预测失败带来的负面影响，ｂｕｃｋｅｔ 中的 ｃａｃｈｅ 存储着上次访问的连接，ｃｏｎｎｅｃｔｉｏｎ 中的ｓｔａｔｅ 有四个状态 ００， ０１， １０， １１， 初始值为０，当我们发现 ｃａｃｈｅ 并不是我们的目标，那么就检查ｃａｃｈｅ所指向的ｃｏｎｎｅｃｔｉｏｎ 中的状态值，如果＜２向左查，否则向右查，如果左侧查不到，就查右侧，反之也一样。根据最后的结果＋１（右侧找到）或者 －１（左侧找到），最大不超过３最小不超过０。以上的代码我测试过，某些情况下效果很好 提高 ４００％，有些时候提高 ５０％，最差情况没有提高，也没有衰退。 <br />实际上我认为学习汇编的目的是为了了解ｃｐｕ， <br />
页:
[1]