From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751145AbdFANZa (ORCPT ); Thu, 1 Jun 2017 09:25:30 -0400 Received: from merlin.infradead.org ([205.233.59.134]:54086 "EHLO merlin.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750952AbdFANZ3 (ORCPT ); Thu, 1 Jun 2017 09:25:29 -0400 Date: Thu, 1 Jun 2017 15:25:23 +0200 From: Peter Zijlstra To: Josh Poimboeuf Cc: Ingo Molnar , x86@kernel.org, linux-kernel@vger.kernel.org, live-patching@vger.kernel.org, Linus Torvalds , Andy Lutomirski , Jiri Slaby , "H. Peter Anvin" Subject: Re: [RFC PATCH 00/10] x86: undwarf unwinder Message-ID: <20170601132523.quyvnej54y23hel4@hirez.programming.kicks-ass.net> References: <20170601060824.wv2go3adbvx5ptmt@gmail.com> <20170601115819.3twoowcnvtrfzjzr@treble> <20170601121721.lezoecnyah3aic6a@hirez.programming.kicks-ass.net> <20170601124705.gw5snmcsetsrhw24@treble> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20170601124705.gw5snmcsetsrhw24@treble> User-Agent: NeoMutt/20170113 (1.7.2) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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.