gpt4 book ai didi

c - while循环中的分支优化,为什么更少的指令花费更多的运行时间?

转载 作者:太空狗 更新时间:2023-10-29 15:07:04 30 4
gpt4 key购买 nike

我有一个用 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代码(右手优化代码)来看,指令少,我很难理解为什么优化前要花更多时间。

enter image description here

还有一些细节供大家引用:

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;
};

它运行在 virtual-box 上,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 really didn't like the CMOV instruction back in '07 .

由于您正在进行微观优化,因此请将相等性检查移至最后一个位置。它几乎总是错误的,但您在每次迭代中都做到了。

此外,我会尝试使用指针到指针模式。由于指针别名问题,间接往往会使优化器阻塞。相反,使用带有两个指针的英寸蠕虫模式:

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

如果比较代价高昂(你没有显示“好”是什么),你也可以尝试存储跟踪比较的二进制结果,以便最终检查使用它而不是重做比较。

关于c - while循环中的分支优化,为什么更少的指令花费更多的运行时间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31084363/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com