From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751481AbdFFOOc (ORCPT ); Tue, 6 Jun 2017 10:14:32 -0400 Received: from mail-pf0-f194.google.com ([209.85.192.194]:36403 "EHLO mail-pf0-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751424AbdFFOOU (ORCPT ); Tue, 6 Jun 2017 10:14:20 -0400 Date: Tue, 6 Jun 2017 23:14:24 +0900 From: Sergey Senozhatsky To: Peter Zijlstra Cc: Josh Poimboeuf , Ingo Molnar , x86@kernel.org, linux-kernel@vger.kernel.org, live-patching@vger.kernel.org, Linus Torvalds , Andy Lutomirski , Jiri Slaby , "H. Peter Anvin" , Sergey Senozhatsky Subject: Re: [RFC PATCH 00/10] x86: undwarf unwinder Message-ID: <20170606141424.GA504@jagdpanzerIV.localdomain> References: <20170601060824.wv2go3adbvx5ptmt@gmail.com> <20170601115819.3twoowcnvtrfzjzr@treble> <20170601121721.lezoecnyah3aic6a@hirez.programming.kicks-ass.net> <20170601124705.gw5snmcsetsrhw24@treble> <20170601132523.quyvnej54y23hel4@hirez.programming.kicks-ass.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20170601132523.quyvnej54y23hel4@hirez.programming.kicks-ass.net> User-Agent: Mutt/1.8.3 (2017-05-23) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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