lkml.org 
[lkml]   [2017]   [Jun]   [6]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
SubjectRe: [RFC PATCH 00/10] x86: undwarf unwinder
On (06/01/17 15:25), Peter Zijlstra wrote:
[..]
> On Thu, Jun 01, 2017 at 07:47:05AM -0500, Josh Poimboeuf wrote:
>
> > > It doesn't appear to be possible to get anywhere near a frame-pointer
> > > unwinder due to having to do this log(n) lookup for every single
> > > frame.
> >
> > Hm, is there something faster, yet not substantially bigger? Hash?
> > Trie?
>
> Not sure how to make a Hash work with nearest neighbour searches. And a
> trie will only give you a constant speedup over the binary search but
> not an improvement in complexity IIRC.

by the way, as far as I know, there is *a bit* faster bsearch(). basically
there is a way to calculate pivot (middle element) using less instructions.

something like below, perhaps... may be can give some extra performance.
(not really tested. but I believe this is close to what gcc does in
libstdc++).


======

./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

---
lib/bsearch.c | 22 ++++++++++++----------
1 file changed, 12 insertions(+), 10 deletions(-)

diff --git a/lib/bsearch.c b/lib/bsearch.c
index e33c179089db..18b445b010c3 100644
--- a/lib/bsearch.c
+++ b/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;
--
2.13.1
\
 
 \ /
  Last update: 2017-06-12 00:47    [W:0.285 / U:0.224 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site