我最近与一些朋友讨论了"现代"语言与C++相比的优点,当时出现以下内容(我认为受Java启发):
是否有任何C++编译器优化了循环中的动态调度？如果没有,是否存在任何允许作者强制(或强烈鼓励)这种优化的结构？
这是一个例子.假设我有一个多态层次结构:
struct A { virtual int f() { return 0; } };
struct B : A { virtual int f() { return /* something complicated */; } /*...*/ };
现在我有一个累积的循环f():
int acc(const A * p, unsigned int N)
{
int result = 0;
for (unsigned int i = 0; i != N; ++i)
result += p->f(); // #1
return result;
}
在此函数中,动态调度p->f()似乎发生在循环的每一轮中.然而,公然发送(？)的最终目标不能改变.
问题:编译器是否优化了此动态调度？如果没有,有没有办法重写代码来强制进行优化,或者至少让编译器识别出来？有没有好的测试代码可以告诉我这是否已经优化了？
我对语言和实现答案感兴趣,例如"根据标准这是不可能的",或者"是的,MSVC使用选项/xyzzy".
一些比较性评论:显然,Java会在适当的情况下优化甚至内联内部循环中的调用.Objective-C++显然允许您查询动态函数指针并存储它.
澄清:我感兴趣的主要用例是基类和带循环的函数(如累加器)是单独的翻译单元或库的一部分,并且没有对派生类的控制或知识.
我编译了上面的代码:
我做的唯一改变是使方法const作为acc()的参数'p'也是const.
当我使用g ++ 4.2.1和-O3编译它(在macbook上)时,我得到以下代码(这看起来像acc()中的循环).
看起来它不是通过查找表链接.
这是一个简单的通过已经设置vtable的寄存器获取.
57 L9:
58 movq (%r12), %rax // Get the location of f() method address via the r12 register
59 movq %r12, %rdi // Set up rdi register as `this` (for after call)
60 call *(%rax) // Call the F() method. address is in memory pointed at by rax
61 addl %eax, %r14d
62 incl %ebx
63 cmpl %r13d, %ebx
64 jne L9
如果我从行中删除虚拟描述符,则相同的代码是:
76 L16:
77 movq %r14, %rdi // Set up rdi register as `this` (for after call)
78 call __ZNK1A1fEv // Call the F() method.
79 addl %eax, %r13d
80 incl %ebx
81 cmpl %r12d, %ebx
82 jne L16
所以上面代码的不同之处在于:
movq (%r12), %rax This is a register to register copy.
The cost of this is practically nothing and you could never
detect it. No matter how many times you called the function.
call *(%rax) Here we have to look up the address to call by getting it
from memory. Now this could be expensive.
But in reality is not. The first time this is called the
memory will be placed in an in-chip memory cache (if it is
not there you will get a processor stall while it is loaded
from memory (or the next cache up)) but after that it will
be really fast.
But it is not quite as fast as just calling the address (for
the non virtual version). But the difference is insignificant
and other factors in the code will drown out any gains or
just in pure noise of the measurements.
所以回答这个问题.没有缓存函数的地址以供重用.每次通过循环查找它.
编译的来源:
#include <iostream>
struct A { virtual int f() const { return 0; } };
struct B : A { virtual int f() const { return 1; }};
int acc(const A * p, unsigned int N)
{
int result = 0;
for (unsigned int i = 0; i != N; ++i)
result += p->f(); // #1
return result;
}
int main()
{
A a;
B b;
std::cout << acc(&a, 20) << "\n";
std::cout << acc(&b, 22) << "\n";
}
完全组装:
1 .mod_init_func
2 .align 3
3 .quad __GLOBAL__I__Z3accPK1Aj
4 .section __TEXT,__textcoal_nt,coalesced,pure_instructions
5 .align 1
6 .align 4
7 .globl __ZNK1A1fEv
8 .weak_definition __ZNK1A1fEv
9 __ZNK1A1fEv:
10 LFB1477:
11 pushq %rbp
12 LCFI0:
13 movq %rsp, %rbp
14 LCFI1:
15 xorl %eax, %eax
16 leave
17 ret
18 LFE1477:
19 .align 1
20 .align 4
21 .globl __ZNK1B1fEv
22 .weak_definition __ZNK1B1fEv
23 __ZNK1B1fEv:
24 LFB1478:
25 pushq %rbp
26 LCFI2:
27 movq %rsp, %rbp
28 LCFI3:
29 movl $1, %eax
30 leave
31 ret
32 LFE1478:
33 .text
34 .align 4,0x90
35 .globl __Z3accPK1Aj
36 __Z3accPK1Aj:
37 LFB1479:
38 pushq %rbp
39 LCFI4:
40 movq %rsp, %rbp
41 LCFI5:
42 pushq %r14
43 LCFI6:
44 pushq %r13
45 LCFI7:
46 pushq %r12
47 LCFI8:
48 pushq %rbx
49 LCFI9:
50 movq %rdi, %r12
51 movl %esi, %r13d
52 xorl %r14d, %r14d
53 testl %esi, %esi
54 je L8
55 xorl %ebx, %ebx
56 .align 4,0x90
57 L9:
58 movq (%r12), %rax
59 movq %r12, %rdi
60 call *(%rax)
61 addl %eax, %r14d
62 incl %ebx
63 cmpl %r13d, %ebx
64 jne L9
65 L8:
66 movl %r14d, %eax
67 popq %rbx
68 popq %r12
69 popq %r13
70 popq %r14
71 leave
72 ret
73 LFE1479:
74 .section __TEXT,__StaticInit,regular,pure_instructions
75 .align 4
76 __Z41__static_initialization_and_destruction_0ii:
77 LFB1649:
78 pushq %rbp
79 LCFI10:
80 movq %rsp, %rbp
81 LCFI11:
82 decl %edi
83 je L18
84 L17:
85 leave
86 ret
87 .align 4
88 L18:
89 cmpl $65535, %esi
90 jne L17
91 leaq __ZStL8__ioinit(%rip), %rdi
92 call __ZNSt8ios_base4InitC1Ev
93 movq ___dso_handle@GOTPCREL(%rip), %rdx
94 xorl %esi, %esi
95 leaq ___tcf_0(%rip), %rdi
96 leave
97 jmp ___cxa_atexit
98 LFE1649:
99 .align 4
100 __GLOBAL__I__Z3accPK1Aj:
101 LFB1651:
102 pushq %rbp
103 LCFI12:
104 movq %rsp, %rbp
105 LCFI13:
106 movl $65535, %esi
107 movl $1, %edi
108 leave
109 jmp __Z41__static_initialization_and_destruction_0ii
110 LFE1651:
111 .text
112 .align 4,0x90
113 ___tcf_0:
114 LFB1650:
115 pushq %rbp
116 LCFI14:
117 movq %rsp, %rbp
118 LCFI15:
119 leaq __ZStL8__ioinit(%rip), %rdi
120 leave
121 jmp __ZNSt8ios_base4InitD1Ev
122 LFE1650:
123 .cstring
124 LC0:
125 .ascii "\12\0"
126 .text
127 .align 4,0x90
128 .globl _main
129 _main:
130 LFB1480:
131 pushq %rbp
132 LCFI16:
133 movq %rsp, %rbp
134 LCFI17:
135 pushq %r14
136 LCFI18:
137 pushq %r13
138 LCFI19:
139 pushq %r12
140 LCFI20:
141 pushq %rbx
142 LCFI21:
143 subq $32, %rsp
144 LCFI22:
145 movq __ZTV1A@GOTPCREL(%rip), %rax
146 addq $16, %rax
147 movq %rax, -48(%rbp)
148 movq __ZTV1B@GOTPCREL(%rip), %rax
149 addq $16, %rax
150 movq %rax, -64(%rbp)
151 leaq -48(%rbp), %r13
152 movq %r13, %rdi
153 call __ZNK1A1fEv
154 movl %eax, %ebx
155 movl $1, %r12d
156 .align 4,0x90
157 L24:
158 movq %r13, %rdi
159 call __ZNK1A1fEv
160 addl %eax, %ebx
161 incl %r12d
162 cmpl $20, %r12d
163 jne L24
164 movl %ebx, %esi
165 movq __ZSt4cout@GOTPCREL(%rip), %r14
166 movq %r14, %rdi
167 call __ZNSolsEi
168 movq %rax, %rdi
169 movl $1, %edx
170 leaq LC0(%rip), %rsi
171 call __ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
172 leaq -64(%rbp), %r13
173 movq %r13, %rdi
174 movq -64(%rbp), %rax
175 call *(%rax)
176 movl %eax, %ebx
177 movb $1, %r12b
178 .align 4,0x90
179 L26:
180 movq %r13, %rdi
181 movq -64(%rbp), %rax
182 call *(%rax)
183 addl %eax, %ebx
184 incl %r12d
185 cmpl $22, %r12d
186 jne L26
187 movl %ebx, %esi
188 movq %r14, %rdi
189 call __ZNSolsEi
190 movq %rax, %rdi
191 movl $1, %edx
192 leaq LC0(%rip), %rsi
193 call __ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
194 xorl %eax, %eax
195 addq $32, %rsp
196 popq %rbx
197 popq %r12
198 popq %r13
199 popq %r14
200 leave
201 ret
202 LFE1480:
203 .lcomm __ZStL8__ioinit,1,0
204 .globl __ZTV1A
205 .weak_definition __ZTV1A
206 .section __DATA,__const_coal,coalesced
207 .align 4
208 __ZTV1A:
209 .quad 0
210 .quad __ZTI1A
211 .quad __ZNK1A1fEv
212 .globl __ZTI1A
213 .weak_definition __ZTI1A
214 .align 4
215 __ZTI1A:
216 .quad __ZTVN10__cxxabiv117__class_type_infoE+16
217 .quad __ZTS1A
218 .globl __ZTS1A
219 .weak_definition __ZTS1A
220 .section __TEXT,__const_coal,coalesced
221 __ZTS1A:
222 .ascii "1A\0"
223 .globl __ZTV1B
224 .weak_definition __ZTV1B
225 .section __DATA,__const_coal,coalesced
226 .align 4
227 __ZTV1B:
228 .quad 0
229 .quad __ZTI1B
230 .quad __ZNK1B1fEv
231 .globl __ZTI1B
232 .weak_definition __ZTI1B
233 .align 4
234 __ZTI1B:
235 .quad __ZTVN10__cxxabiv120__si_class_type_infoE+16
236 .quad __ZTS1B
237 .quad __ZTI1A
238 .globl __ZTS1B
239 .weak_definition __ZTS1B
240 .section __TEXT,__const_coal,coalesced
241 __ZTS1B:
242 .ascii "1B\0"
243 .section __TEXT,__eh_frame,coalesced,no_toc+strip_static_syms+live_support
244 EH_frame1:
245 .set L$set$0,LECIE1-LSCIE1
246 .long L$set$0
247 LSCIE1:
248 .long 0x0
249 .byte 0x1
250 .ascii "zPR\0"
251 .byte 0x1
252 .byte 0x78
253 .byte 0x10
254 .byte 0x6
255 .byte 0x9b
256 .long ___gxx_personality_v0+4@GOTPCREL
257 .byte 0x10
258 .byte 0xc
259 .byte 0x7
260 .byte 0x8
261 .byte 0x90
262 .byte 0x1
263 .align 3
264 LECIE1:
265 .globl __ZNK1A1fEv.eh
266 .weak_definition __ZNK1A1fEv.eh
267 __ZNK1A1fEv.eh:
268 LSFDE1:
269 .set L$set$1,LEFDE1-LASFDE1
270 .long L$set$1
271 LASFDE1:
272 .long LASFDE1-EH_frame1
273 .quad LFB1477-.
274 .set L$set$2,LFE1477-LFB1477
275 .quad L$set$2
276 .byte 0x0
277 .byte 0x4
278 .set L$set$3,LCFI0-LFB1477
279 .long L$set$3
280 .byte 0xe
281 .byte 0x10
282 .byte 0x86
283 .byte 0x2
284 .byte 0x4
285 .set L$set$4,LCFI1-LCFI0
286 .long L$set$4
287 .byte 0xd
288 .byte 0x6
289 .align 3
290 LEFDE1:
291 .globl __ZNK1B1fEv.eh
292 .weak_definition __ZNK1B1fEv.eh
293 __ZNK1B1fEv.eh:
294 LSFDE3:
295 .set L$set$5,LEFDE3-LASFDE3
296 .long L$set$5
297 LASFDE3:
298 .long LASFDE3-EH_frame1
299 .quad LFB1478-.
300 .set L$set$6,LFE1478-LFB1478
301 .quad L$set$6
302 .byte 0x0
303 .byte 0x4
304 .set L$set$7,LCFI2-LFB1478
305 .long L$set$7
306 .byte 0xe
307 .byte 0x10
308 .byte 0x86
309 .byte 0x2
310 .byte 0x4
311 .set L$set$8,LCFI3-LCFI2
312 .long L$set$8
313 .byte 0xd
314 .byte 0x6
315 .align 3
316 LEFDE3:
317 .globl __Z3accPK1Aj.eh
318 __Z3accPK1Aj.eh:
319 LSFDE5:
320 .set L$set$9,LEFDE5-LASFDE5
321 .long L$set$9
322 LASFDE5:
323 .long LASFDE5-EH_frame1
324 .quad LFB1479-.
325 .set L$set$10,LFE1479-LFB1479
326 .quad L$set$10
327 .byte 0x0
328 .byte 0x4
329 .set L$set$11,LCFI4-LFB1479
330 .long L$set$11
331 .byte 0xe
332 .byte 0x10
333 .byte 0x86
334 .byte 0x2
335 .byte 0x4
336 .set L$set$12,LCFI5-LCFI4
337 .long L$set$12
338 .byte 0xd
339 .byte 0x6
340 .byte 0x4
341 .set L$set$13,LCFI9-LCFI5
342 .long L$set$13
343 .byte 0x83
344 .byte 0x6
345 .byte 0x8c
346 .byte 0x5
347 .byte 0x8d
348 .byte 0x4
349 .byte 0x8e
350 .byte 0x3
351 .align 3
352 LEFDE5:
353 __Z41__static_initialization_and_destruction_0ii.eh:
354 LSFDE7:
355 .set L$set$14,LEFDE7-LASFDE7
356 .long L$set$14
357 LASFDE7:
358 .long LASFDE7-EH_frame1
359 .quad LFB1649-.
360 .set L$set$15,LFE1649-LFB1649
361 .quad L$set$15
362 .byte 0x0
363 .byte 0x4
364 .set L$set$16,LCFI10-LFB1649
365 .long L$set$16
366 .byte 0xe
367 .byte 0x10
368 .byte 0x86
369 .byte 0x2
370 .byte 0x4
371 .set L$set$17,LCFI11-LCFI10
372 .long L$set$17
373 .byte 0xd
374 .byte 0x6
375 .align 3
376 LEFDE7:
377 __GLOBAL__I__Z3accPK1Aj.eh:
378 LSFDE9:
379 .set L$set$18,LEFDE9-LASFDE9
380 .long L$set$18
381 LASFDE9:
382 .long LASFDE9-EH_frame1
383 .quad LFB1651-.
384 .set L$set$19,LFE1651-LFB1651
385 .quad L$set$19
386 .byte 0x0
387 .byte 0x4
388 .set L$set$20,LCFI12-LFB1651
389 .long L$set$20
390 .byte 0xe
391 .byte 0x10
392 .byte 0x86
393 .byte 0x2
394 .byte 0x4
395 .set L$set$21,LCFI13-LCFI12
396 .long L$set$21
397 .byte 0xd
398 .byte 0x6
399 .align 3
400 LEFDE9:
401 ___tcf_0.eh:
402 LSFDE11:
403 .set L$set$22,LEFDE11-LASFDE11
404 .long L$set$22
405 LASFDE11:
406 .long LASFDE11-EH_frame1
407 .quad LFB1650-.
408 .set L$set$23,LFE1650-LFB1650
409 .quad L$set$23
410 .byte 0x0
411 .byte 0x4
412 .set L$set$24,LCFI14-LFB1650
413 .long L$set$24
414 .byte 0xe
415 .byte 0x10
416 .byte 0x86
417 .byte 0x2
418 .byte 0x4
419 .set L$set$25,LCFI15-LCFI14
420 .long L$set$25
421 .byte 0xd
422 .byte 0x6
423 .align 3
424 LEFDE11:
425 .globl _main.eh
426 _main.eh:
427 LSFDE13:
428 .set L$set$26,LEFDE13-LASFDE13
429 .long L$set$26
430 LASFDE13:
431 .long LASFDE13-EH_frame1
432 .quad LFB1480-.
433 .set L$set$27,LFE1480-LFB1480
434 .quad L$set$27
435 .byte 0x0
436 .byte 0x4
437 .set L$set$28,LCFI16-LFB1480
438 .long L$set$28
439 .byte 0xe
440 .byte 0x10
441 .byte 0x86
442 .byte 0x2
443 .byte 0x4
444 .set L$set$29,LCFI17-LCFI16
445 .long L$set$29
446 .byte 0xd
447 .byte 0x6
448 .byte 0x4
449 .set L$set$30,LCFI22-LCFI17
450 .long L$set$30
451 .byte 0x83
452 .byte 0x6
453 .byte 0x8c
454 .byte 0x5
455 .byte 0x8d
456 .byte 0x4
457 .byte 0x8e
458 .byte 0x3
459 .align 3
460 LEFDE13:
461 .constructor
462 .destructor
463 .align 1
464 .subsections_via_symbols
如果您对此类事物感兴趣,请查看Agner Fog优秀的软件优化手册.这个问题在五个中的第一个中得到了解决,优化C++(pdf)(其他都是关于汇编 - 他是一种老派).
如果f()是const函数,或者在调用时返回值p保证不变,则可以将其拉出循环并仅计算一次(参见"循环不变代码运动",第70页).大多数编译器都会这样做(参见"不同编译器的比较",第74页).
如果无法做到,那么仍然可以进行虚拟化.但是这不能在可调用函数中完成,因为为了正确起见,必须使用虚拟查找.但是如果函数是内联的,并且p调用范围中已知类型,则可以完成.调用代码必须看起来像这样:
A* aptr = new A(42); // <- The compiler knows exactly what type aptr points to
acc(a, 100); // <- This would have to be inlined!
但根据该表(第74页),只有GCC编译器进行此优化.
最后,最接近的优化(我认为)就是你所要求的.编译器可以执行一次虚拟查找,存储函数指针,然后使用该函数指针来避免循环内的虚拟查找吗？我不明白为什么不.但我不知道是否有任何编译器这样做 - 这是一个不起眼的优化,甚至在Agner Fog的强制性详细的C++手册中都没有提到.
对于它的价值,这里是他对函数指针的看法(第38页):
如果可以预测目标地址,则通过函数指针调用函数通常比直接调用函数花费几个时钟周期.如果函数指针的值与上次执行语句的值相同,则预测目标地址.如果函数指针的值已经改变,则目标地址可能被错误预测,这导致长延迟.有关分支预测,请参见第44页.如果函数指针的变化遵循简单的规则模式,Pentium M处理器可能能够预测目标,而Pentium 4和AMD处理器肯定会在每次函数指针改变时进行误预测.
有关虚拟成员函数的摘录(第54页):
如果函数调用语句总是调用相同版本的虚函数,则调用虚拟成员函数所花费的时间比调用非虚函数成员函数所花费的时间长几个时钟周期.如果版本发生变化,那么您可能会得到10到20个时钟周期的错误预测惩罚.虚函数调用的预测和误预测规则与switch语句相同,如第45页所述.
当在已知类型的对象上调用虚函数时,可以绕过调度机制,但是即使很明显这样做,也不能总是依赖编译器绕过调度机制.见第73页.
您知道函数指针在您的示例中不会更改,因此您不会得到错误预测惩罚,但他从不直接将函数指针性能与虚函数性能进行比较.两者都只比常规函数调用多"几个"时钟周期.也许它是相同的机制 - 如果是这样,"优化"只会添加额外的查找.
所以真的很难说.获得答案的最佳方法可能就是让你最喜欢的编译器吐出一些优化的程序集并深入研究它(令人不快,但最终结论!).
希望这可以帮助!
| 归档时间： |
|
| 查看次数： |
711 次 |
| 最近记录： |