* [patch 096/115] lib/bsearch.c: micro-optimize pivot position calculation
@ 2017-07-10 22:52 akpm
0 siblings, 0 replies; only message in thread
From: akpm @ 2017-07-10 22:52 UTC (permalink / raw)
To: akpm, mm-commits, peterz, sergey.senozhatsky, torvalds
From: Sergey Senozhatsky <sergey.senozhatsky@gmail.com>
Subject: lib/bsearch.c: micro-optimize pivot position calculation
There is a slightly faster way (in terms of the number of instructions
being used) to calculate the position of a middle element, preserving
integer overflow safeness.
./scripts/bloat-o-meter lib/bsearch.o.old lib/bsearch.o.new
add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-24 (-24)
function old new delta
bsearch 122 98 -24
TEST
INT array of size 100001, elements [0..100000]. gcc 7.1, Os, x86_64.
a) bsearch() of existing key "100001 - 2":
BASE
====
$ perf stat ./a.out
Performance counter stats for './a.out':
619.445196 task-clock:u (msec) # 0.999 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
133 page-faults:u # 0.215 K/sec
1,949,517,279 cycles:u # 3.147 GHz (83.06%)
181,017,938 stalled-cycles-frontend:u # 9.29% frontend cycles idle (83.05%)
82,959,265 stalled-cycles-backend:u # 4.26% backend cycles idle (67.02%)
4,355,706,383 instructions:u # 2.23 insn per cycle
# 0.04 stalled cycles per insn (83.54%)
1,051,539,242 branches:u # 1697.550 M/sec (83.54%)
15,263,381 branch-misses:u # 1.45% of all branches (83.43%)
0.620082548 seconds time elapsed
PATCHED
=======
$ perf stat ./a.out
Performance counter stats for './a.out':
475.097316 task-clock:u (msec) # 0.999 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
135 page-faults:u # 0.284 K/sec
1,487,467,717 cycles:u # 3.131 GHz (82.95%)
186,537,162 stalled-cycles-frontend:u # 12.54% frontend cycles idle (82.93%)
28,797,869 stalled-cycles-backend:u # 1.94% backend cycles idle (67.10%)
3,807,564,203 instructions:u # 2.56 insn per cycle
# 0.05 stalled cycles per insn (83.57%)
1,049,344,291 branches:u # 2208.693 M/sec (83.60%)
5,485 branch-misses:u # 0.00% of all branches (83.58%)
0.475760235 seconds time elapsed
b) bsearch() of un-existing key "100001 + 2":
BASE
====
$ perf stat ./a.out
Performance counter stats for './a.out':
499.244480 task-clock:u (msec) # 0.999 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
132 page-faults:u # 0.264 K/sec
1,571,194,855 cycles:u # 3.147 GHz (83.18%)
13,450,980 stalled-cycles-frontend:u # 0.86% frontend cycles idle (83.18%)
21,256,072 stalled-cycles-backend:u # 1.35% backend cycles idle (66.78%)
4,171,197,909 instructions:u # 2.65 insn per cycle
# 0.01 stalled cycles per insn (83.68%)
1,009,175,281 branches:u # 2021.405 M/sec (83.79%)
3,122 branch-misses:u # 0.00% of all branches (83.37%)
0.499871144 seconds time elapsed
PATCHED
=======
$ perf stat ./a.out
Performance counter stats for './a.out':
399.023499 task-clock:u (msec) # 0.998 CPUs utilized
0 context-switches:u # 0.000 K/sec
0 cpu-migrations:u # 0.000 K/sec
134 page-faults:u # 0.336 K/sec
1,245,793,991 cycles:u # 3.122 GHz (83.39%)
11,529,273 stalled-cycles-frontend:u # 0.93% frontend cycles idle (83.46%)
12,116,311 stalled-cycles-backend:u # 0.97% backend cycles idle (66.92%)
3,679,710,005 instructions:u # 2.95 insn per cycle
# 0.00 stalled cycles per insn (83.47%)
1,009,792,625 branches:u # 2530.660 M/sec (83.46%)
2,590 branch-misses:u # 0.00% of all branches (83.12%)
0.399733539 seconds time elapsed
Link: http://lkml.kernel.org/r/20170607150457.5905-1-sergey.senozhatsky@gmail.com
Signed-off-by: Sergey Senozhatsky <sergey.senozhatsky@gmail.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---
lib/bsearch.c | 22 ++++++++++++----------
1 file changed, 12 insertions(+), 10 deletions(-)
diff -puN lib/bsearch.c~bsearch-micro-optimize-pivot-position-calculation lib/bsearch.c
--- a/lib/bsearch.c~bsearch-micro-optimize-pivot-position-calculation
+++ a/lib/bsearch.c
@@ -33,19 +33,21 @@
void *bsearch(const void *key, const void *base, size_t num, size_t size,
int (*cmp)(const void *key, const void *elt))
{
- size_t start = 0, end = num;
+ const char *pivot;
int result;
- while (start < end) {
- size_t mid = start + (end - start) / 2;
+ while (num > 0) {
+ pivot = base + (num >> 1) * size;
+ result = cmp(key, pivot);
- result = cmp(key, base + mid * size);
- if (result < 0)
- end = mid;
- else if (result > 0)
- start = mid + 1;
- else
- return (void *)base + mid * size;
+ if (result == 0)
+ return (void *)pivot;
+
+ if (result > 0) {
+ base = pivot + size;
+ num--;
+ }
+ num >>= 1;
}
return NULL;
_
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2017-07-10 22:52 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-07-10 22:52 [patch 096/115] lib/bsearch.c: micro-optimize pivot position calculation akpm
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.