[PATCH] stdlib-bsearch: middle element calculation may overflow
Sergey Senozhatsky
sergey.senozhatsky.work@gmail.com
Thu Mar 30 05:00:00 GMT 2017
On (03/29/17 21:06), Andrew Pinski wrote:
> > 8368: e92d4ff8 push {r3, r4, r5, r6, r7, r8, r9, sl, fp, lr} 83e4: e92d4ff8 push {r3, r4, r5, r6, r7, r8, r9, sl, fp, lr}
> > 836c: e2526000 subs r6, r2, #0 83e8: e2526000 subs r6, r2, #0
> > 8370: e59da028 ldr sl, [sp, #40] ; 0x28 83ec: e59da028 ldr sl, [sp, #40] ; 0x28
> > 8374: 11a07000 movne r7, r0 83f0: 11a07000 movne r7, r0
> > 8378: 11a08001 movne r8, r1 83f4: 11a08001 movne r8, r1
> > 837c: 11a09003 movne r9, r3 83f8: 11a09003 movne r9, r3
> > 8380: 13a05000 movne r5, #0 83fc: 13a05000 movne r5, #0
> > 8384: 1a000004 bne 839c <____bsearch+0x34> 8400: 1a000004 bne 8418 <__bsearch+0x34>
> > 8388: ea00000f b 83cc <____bsearch+0x64> 8404: ea00000f b 8448 <__bsearch+0x64>
> > 838c: 0a000011 beq 83d8 <____bsearch+0x70> 8408: 0a000011 beq 8454 <__bsearch+0x70>
> > 8390: e2845001 add r5, r4, #1 840c: e2845001 add r5, r4, #1
> > 8394: e1550006 cmp r5, r6 8410: e1550006 cmp r5, r6
> > 8398: 2a00000b bcs 83cc <____bsearch+0x64> 8414: 2a00000b bcs 8448 <__bsearch+0x64>
> > 839c: e0854006 add r4, r5, r6 8418: e0464005 sub r4, r6, r5
> > 83a0: e1a040a4 lsr r4, r4, #1 841c: e08540a4 add r4, r5, r4, lsr #1
>
> This is just the magic here. ARM is special in that they have shifts
> with their adds. AARCH64 is similar but on some microarch, doing the
> shift seperate from the add is better. So this shows that it is worse
> on those targets for latency reasons :).
BTW, FreeBSD's kernel bsearch implementation is quite interesting
and unique. take a look:
https://github.com/freebsd/freebsd/blob/master/sys/libkern/bsearch.c
x86_64 gcc7 -O2
400630: 41 57 push %r15
400632: 41 56 push %r14
400634: 41 55 push %r13
400636: 41 54 push %r12
400638: 55 push %rbp
400639: 53 push %rbx
40063a: 48 83 ec 18 sub $0x18,%rsp
40063e: 48 85 d2 test %rdx,%rdx
400641: 48 89 7c 24 08 mov %rdi,0x8(%rsp)
400646: 74 53 je 40069b <_bsearch+0x6b>
400648: 49 89 f4 mov %rsi,%r12
40064b: 48 89 d3 mov %rdx,%rbx
40064e: 48 89 cd mov %rcx,%rbp
400651: 4d 89 c5 mov %r8,%r13
400654: eb 1a jmp 400670 <_bsearch+0x40>
400656: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
40065d: 00 00 00
400660: 48 83 eb 01 sub $0x1,%rbx
400664: 4d 8d 24 2e lea (%r14,%rbp,1),%r12
400668: 48 d1 eb shr %rbx
40066b: 48 85 db test %rbx,%rbx
40066e: 74 2b je 40069b <_bsearch+0x6b>
400670: 49 89 df mov %rbx,%r15
400673: 48 8b 7c 24 08 mov 0x8(%rsp),%rdi
400678: 49 d1 ef shr %r15
40067b: 4c 89 fa mov %r15,%rdx
40067e: 48 0f af d5 imul %rbp,%rdx
400682: 4d 8d 34 14 lea (%r12,%rdx,1),%r14
400686: 4c 89 f6 mov %r14,%rsi
400689: 41 ff d5 callq *%r13
40068c: 83 f8 00 cmp $0x0,%eax
40068f: 74 0d je 40069e <_bsearch+0x6e>
400691: 7f cd jg 400660 <_bsearch+0x30>
400693: 4c 89 fb mov %r15,%rbx
400696: 48 85 db test %rbx,%rbx
400699: 75 d5 jne 400670 <_bsearch+0x40>
40069b: 45 31 f6 xor %r14d,%r14d
40069e: 48 83 c4 18 add $0x18,%rsp
4006a2: 4c 89 f0 mov %r14,%rax
4006a5: 5b pop %rbx
4006a6: 5d pop %rbp
4006a7: 41 5c pop %r12
4006a9: 41 5d pop %r13
4006ab: 41 5e pop %r14
4006ad: 41 5f pop %r15
4006af: c3 retq
this should not overflow, as far as I can see.
perf stat (-O2, x86_64)
and it *seems* to be faster than the existing glibc bsearch()
//* I'm not stating this though *//
== CHAR array
Performance counter stats for './a.out':
421.053507 task-clock:u (msec) # 0.999 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
49 page-faults:u # 0.116 K/sec
1,324,686,237 cycles:u # 3.146 GHz (82.90%)
91,991,733 stalled-cycles-frontend:u # 6.94% frontend cycles idle (83.54%)
57,399,708 stalled-cycles-backend:u # 4.33% backend cycles idle (67.23%)
3,596,376,160 instructions:u # 2.71 insn per cycle
# 0.03 stalled cycles per insn (83.61%)
732,521,201 branches:u # 1739.734 M/sec (83.61%)
7,764,387 branch-misses:u # 1.06% of all branches (83.09%)
0.421633822 seconds time elapsed
Performance counter stats for './a.out':
420.720555 task-clock:u (msec) # 0.999 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
49 page-faults:u # 0.116 K/sec
1,317,505,328 cycles:u # 3.132 GHz (82.89%)
86,237,745 stalled-cycles-frontend:u # 6.55% frontend cycles idle (82.89%)
58,424,019 stalled-cycles-backend:u # 4.43% backend cycles idle (67.16%)
3,591,713,950 instructions:u # 2.73 insn per cycle
# 0.02 stalled cycles per insn (83.60%)
733,832,646 branches:u # 1744.228 M/sec (83.60%)
7,335,495 branch-misses:u # 1.00% of all branches (83.55%)
0.421209527 seconds time elapsed
Performance counter stats for './a.out':
420.446508 task-clock:u (msec) # 0.998 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
49 page-faults:u # 0.117 K/sec
1,309,007,427 cycles:u # 3.113 GHz (82.87%)
85,067,714 stalled-cycles-frontend:u # 6.50% frontend cycles idle (83.54%)
63,478,544 stalled-cycles-backend:u # 4.85% backend cycles idle (67.18%)
3,606,339,245 instructions:u # 2.76 insn per cycle
# 0.02 stalled cycles per insn (83.59%)
730,795,217 branches:u # 1738.141 M/sec (83.62%)
6,900,426 branch-misses:u # 0.94% of all branches (83.09%)
0.421232740 seconds time elapsed
Performance counter stats for './a.out':
422.715593 task-clock:u (msec) # 0.998 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
47 page-faults:u # 0.111 K/sec
1,326,499,959 cycles:u # 3.138 GHz (82.97%)
100,747,231 stalled-cycles-frontend:u # 7.59% frontend cycles idle (82.97%)
67,604,908 stalled-cycles-backend:u # 5.10% backend cycles idle (67.29%)
3,578,538,258 instructions:u # 2.70 insn per cycle
# 0.03 stalled cycles per insn (83.68%)
731,849,769 branches:u # 1731.305 M/sec (83.68%)
8,105,098 branch-misses:u # 1.11% of all branches (83.22%)
0.423636686 seconds time elapsed
== INT array
Performance counter stats for './a.out':
367.111305 task-clock:u (msec) # 0.998 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
52 page-faults:u # 0.142 K/sec
1,142,267,432 cycles:u # 3.112 GHz (82.87%)
186,370,432 stalled-cycles-frontend:u # 16.32% frontend cycles idle (83.52%)
18,145,529 stalled-cycles-backend:u # 1.59% backend cycles idle (67.30%)
3,608,624,538 instructions:u # 3.16 insn per cycle
# 0.05 stalled cycles per insn (83.65%)
729,956,547 branches:u # 1988.379 M/sec (83.67%)
6,567 branch-misses:u # 0.00% of all branches (83.31%)
0.367872314 seconds time elapsed
Performance counter stats for './a.out':
367.367983 task-clock:u (msec) # 0.998 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
53 page-faults:u # 0.144 K/sec
1,146,948,361 cycles:u # 3.122 GHz (82.85%)
189,862,982 stalled-cycles-frontend:u # 16.55% frontend cycles idle (82.85%)
16,090,029 stalled-cycles-backend:u # 1.40% backend cycles idle (67.34%)
3,610,943,628 instructions:u # 3.15 insn per cycle
# 0.05 stalled cycles per insn (83.71%)
729,705,480 branches:u # 1986.307 M/sec (83.68%)
239,259 branch-misses:u # 0.03% of all branches (83.33%)
0.368188108 seconds time elapsed
Performance counter stats for './a.out':
435.185387 task-clock:u (msec) # 0.999 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
52 page-faults:u # 0.119 K/sec
1,367,508,177 cycles:u # 3.142 GHz (82.77%)
317,962,731 stalled-cycles-frontend:u # 23.25% frontend cycles idle (83.45%)
89,442,496 stalled-cycles-backend:u # 6.54% backend cycles idle (66.91%)
3,614,939,853 instructions:u # 2.64 insn per cycle
# 0.09 stalled cycles per insn (83.46%)
731,171,118 branches:u # 1680.137 M/sec (83.46%)
11,699,371 branch-misses:u # 1.60% of all branches (83.41%)
0.435828955 seconds time elapsed
Performance counter stats for './a.out':
426.947345 task-clock:u (msec) # 0.999 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
53 page-faults:u # 0.124 K/sec
1,335,309,841 cycles:u # 3.128 GHz (83.14%)
299,538,314 stalled-cycles-frontend:u # 22.43% frontend cycles idle (83.15%)
78,271,313 stalled-cycles-backend:u # 5.86% backend cycles idle (66.28%)
3,619,103,716 instructions:u # 2.71 insn per cycle
# 0.08 stalled cycles per insn (83.14%)
734,182,321 branches:u # 1719.609 M/sec (83.81%)
10,304,408 branch-misses:u # 1.40% of all branches (83.76%)
0.427541178 seconds time elapsed
-ss
More information about the Libc-alpha
mailing list