Feeds:
Posts
Comments

Archive for October, 2009

An CPU cache trick

下面有两种用单链表解决冲突的hash表节点定义。
————————————————————————–
template<typenmae Key,typename Value>
class Node { Key _key; Value _value; Node<Key,Value>* next;};
———————————————————————————-
template<typenmae Key,typename Value>
class Node { Key _key; Node<Key,Value>* next;Value _value;};
————————————————————————-
两种节点定义仅仅在数据项放置顺序上有区别,哪种实际性能会更好能或者说更加cache友好一些呢?
注意到hash表在查找的时候需要历遍节点比较节点的_key与要查找的key,如果不同则要取得节点的next指针并移动到下一个节点。第一种定义在_value的字节数较大的情况下会导致_key和next不可能出现在同一个cache line中,于是在读取next数据项的时候就很可能会多一次cache miss,而第二种定义更有可能在读取_key的同时next已经在同一个cache line中了,所以第二种定义更加cache友好。而实践也证明定义二的性能更好。
Advertisements

Read Full Post »