在while循环中优化分支,为什么更少的指令花费更多的运行时间？
Inc*_*Lee 5 c optimization data-structures
我有一个由C实现的数据结构项目,它为其他程序导出各种API.最近我想对grofile描述的Hot函数做一些优化.这是供您参考的项目.
https://github.com/Incarnation-p-lee/libds 有一个热门函数binary_search_tree_node_insert,如下所示:
/*
* RETURN the pointer of inserted node of the binary search tree
* If root is NULL or node is NULL, RETURN NULL.
*/
struct binary_search_tree *
binary_search_tree_node_insert(struct binary_search_tree *root,
struct binary_search_tree *node)
{
register struct binary_search_tree **iter;
if (!node || !root) {
pr_log_warn("Attempt to access NULL pointer.\n");
} else {
iter = &root;
while (*iter) {
if (node->chain.nice == (*iter)->chain.nice) {
if (*iter == node) {
pr_log_info("Insert node exist, nothing will be done.\n");
} else {
doubly_linked_list_merge((*iter)->chain.link, node->chain.link);
}
return *iter;
#ifndef OPT_HOT
} else if (node->chain.nice > (*iter)->chain.nice) {
iter = &(*iter)->right;
} else if (node->chain.nice < (*iter)->chain.nice) {
iter = &(*iter)->left;
#else
} else {
binary_search_tree_insert_path_go_through(node, iter);
#endif
}
}
return *iter = node;
}
return NULL;
}
我想优化两个else-if部分,因为它是半个半分支,这可能会对管道造成很大影响.所以我写了一个宏binary_search_tree_insert_path_go_through替换这两个分支.实施如下:
/*
* 1. node->nice => rbx, *iter => rcx.
* 2. compare rbx, and 0x8(rcx).
* 3. update iter.
*/
#define binary_search_tree_insert_path_go_through(node, iter) \
asm volatile ( \
"mov $0x18, %%rax\n\t" \
"mov $0x20, %%rdx\n\t" \
"mov 0x8(%1), %%rbx\n\t" \
"mov (%0), %%rcx\n\t" \
"cmp 0x8(%%rcx), %%rbx\n\t" \
"cmovg %%rdx, %%rax\n\t" \
"lea (%%rcx, %%rax), %0\n\t" \
:"+r"(iter) \
:"r"(node) \
:"rax", "rbx", "rcx", "rdx")
但是这个功能的单元测试已经下降了大约6-8%.从objdump代码(右手优化的代码),它有更少的指令,我很难理解为什么它在优化之前花费更多的时间.
并且有一些细节供您参考:
struct collision_chain {
struct doubly_linked_list *link;
sint64 nice;
};
/*
* binary search tree
*/
struct binary_search_tree {
struct collision_chain chain;
sint32 height; /* reserved for avl */
/* root node has height 0, NULL node has height -1 */
union {
struct binary_search_tree *left;
struct avl_tree *avl_left; /* reserved for avl */
struct splay_tree *splay_left; /* reserved for splay */
};
union {
struct binary_search_tree *right;
struct avl_tree *avl_right; /* reserved for avl */
struct splay_tree *splay_right; /* reserved for splay */
};
};
struct doubly_linked_list {
uint32 sid;
void *val;
struct doubly_linked_list *next;
struct doubly_linked_list *previous;
};
它运行在具有2核i5-3xxM的虚拟机上,cpuinfo如下:
processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 58
model name : Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
stepping : 9
microcode : 0x19
cpu MHz : 2568.658
cache size : 6144 KB
physical id : 0
siblings : 2
core id : 0
cpu cores : 2
apicid : 0
initial apicid : 0
fpu : yes
fpu_exception : yes
cpuid level : 5
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx rdtscp lm constant_tsc rep_good nopl pni ssse3 lahf_lm
bogomips : 5137.31
clflush size : 64
cache_alignment : 64
address sizes : 36 bits physical, 48 bits virtual
power management:
processor : 1
vendor_id : GenuineIntel
cpu family : 6
model : 58
model name : Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
stepping : 9
microcode : 0x19
cpu MHz : 2568.658
cache size : 6144 KB
physical id : 0
siblings : 2
core id : 1
cpu cores : 2
apicid : 1
initial apicid : 1
fpu : yes
fpu_exception : yes
cpuid level : 5
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx rdtscp lm constant_tsc rep_good nopl pni ssse3 lahf_lm
bogomips : 5137.31
clflush size : 64
cache_alignment : 64
address sizes : 36 bits physical, 48 bits virtual
power management:
我不知道现代处理器是否也一样，但Linus 确实不喜欢 07 年的 CMOV 指令。
由于您正在进行微观优化，因此将相等检查移至最后一个位置。它几乎总是错误的，但你在每次迭代中都做到了。
此外，我会尝试不使用指针到指针模式。由于指针别名问题，间接往往会使优化器陷入困境。相反，使用带有两个指针的英寸蠕虫模式：
void insert(NODE *x, NODE **root) {
NODE *trail = NULL;
NODE *lead = *root;
while (lead) {
trail = lead;
if (x->key < lead->key)
lead = lead->left;
else if (x->key > lead->key)
lead = lead->right;
else return; // do nothing;
}
// lead has found null, so insert
if (trail)
// redo the last key comparison
if (x->key < trail->key)
trail->left = x;
else
trail->right = x;
else
*root = x;
}
在我的 MacBook 上，这会编译为以下 64 位代码，其中循环仅包含 10 条指令。从您帖子中的小列表中很难看出，但看起来它相当长：
pushq %rbp
movq %rsp, %rbp
movq (%rsi), %rdx
testq %rdx, %rdx
je LBB0_11
movl 16(%rdi), %ecx
LBB0_2:
movq %rdx, %rax # dx=lead, ax=trail
cmpl 16(%rax), %ecx # comparison with key
jge LBB0_4 # first branch
movq %rax, %rdx # go left (redundant because offset(left)==0!)
jmp LBB0_6
LBB0_4:
jle LBB0_12 # second branch
leaq 8(%rax), %rdx # go right
LBB0_6:
movq (%rdx), %rdx # move lead down the tree
testq %rdx, %rdx # test for null
jne LBB0_2 # loop if not
testq %rax, %rax # insertion logic
je LBB0_11
movl 16(%rdi), %ecx
cmpl 16(%rax), %ecx
jge LBB0_10
movq %rdi, (%rax)
popq %rbp
retq
LBB0_11:
movq %rdi, (%rsi)
LBB0_12: # return for equal keys
popq %rbp
retq
LBB0_10:
movq %rdi, 8(%rax)
popq %rbp
retq
如果比较成本很高（您没有显示什么是“好”），您还可以尝试存储跟踪比较的二进制结果，以便最终检查使用它而不是重新进行比较。