Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1655159

Re: [RFC PATCH 00/10] x86: undwarf unwinder

Show all headers | View raw

On Thu, Jun 1, 2017 at 5:47 AM, Josh Poimboeuf <jpoimboe@redhat.com> wrote:
> On Thu, Jun 01, 2017 at 02:17:21PM +0200, Peter Zijlstra wrote:
>> On Thu, Jun 01, 2017 at 06:58:20AM -0500, Josh Poimboeuf wrote:
>> > > Being able to generate more optimal code in the hottest code paths of the kernel
>> > > is the _real_, primary upstream kernel benefit of a different debuginfo method -
>> > > which has to be weighed against the pain of introducing a new unwinder. But this
>> > > submission does not talk about that aspect at all, which should be fixed I think.
>> >
>> > Actually I devoted an entire one-sentence paragraph to performance in
>> > the documentation:
>> >
>> >   The simpler debuginfo format also enables the unwinder to be relatively
>> >   fast, which is important for perf and lockdep.
>> >
>> > But I'll try to highlight that a little more.
>>
>> That's relative to a DWARF unwinder.
>
> Yes.
>
>> 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?

You have, roughly, a set of (key_start, value) pairs where, for any
given key, you want to find the (key_start, value) with the largest
key_start that doesn't exceed key.  Binary search gives you log_2(n)
queries, but its locality of reference sucks.  Here are two
suggestions for improving it:

1. Change the data layout.  Instead of having an array of undwarf
entries, have two parallel arrays, one with the ip addresses and one
with everything else.  This has no effect on the amount of space used,
but it makes the part used during search more compact.

2. Your key space is fairly small and your table entries should be
reasonably uniformly distributed.  Let the first IP you have unwind
data for be IP0.  Make an array mapping (IP - IP0) / B to the index of
the unwind entry for that IP for some suitable block size B.  Then, to
look up an IP, you'd find the indices of the unwind entries for (IP -
IP0) / B and (IP - IP0) / B + 1 and binary search between them.  With
constant B, this gives you O(1) performance instead of O(log(n)).
With B = 1, it's very fast, but the table is huge.  With B = 64k or
so, maybe you'd get a nice tradeoff of speedup vs size.  (With
modules, you'd presumably first search an rbtree to find which
instance of this data structure you're using and then do the lookup.)

3. Use a B-tree.  B-trees are simple if you don't need to deal with
insertion and deletion.  Presumably you'd choose your internal node
size so each internal node is exactly 64 or 128 bytes for good cache
performance.  This is still O(log(n)) and it uses more comparisons
than binary search, but you touch many fewer cache lines.

I expect that, if you do #1 and #2, you'd get excellent performance at
very little cost to the complexity of the code.

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[RFC PATCH 00/10] x86: undwarf unwinder Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 07:50 +0200
  [RFC PATCH 06/10] x86/entry: add CFI hint undwarf annotations Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 07:50 +0200
    Re: [RFC PATCH 06/10] x86/entry: add CFI hint undwarf annotations Andy Lutomirski <luto@kernel.org> - 2017-06-01 16:10 +0200
      Re: [RFC PATCH 06/10] x86/entry: add CFI hint undwarf annotations Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 16:30 +0200
        Re: [RFC PATCH 06/10] x86/entry: add CFI hint undwarf annotations Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 16:30 +0200
          Re: [RFC PATCH 06/10] x86/entry: add CFI hint undwarf annotations Andy Lutomirski <luto@kernel.org> - 2017-06-01 16:50 +0200
            Re: [RFC PATCH 06/10] x86/entry: add CFI hint undwarf annotations Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 17:10 +0200
  [RFC PATCH 09/10] extable: add undwarf table sorting ability to sorttable script Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 07:50 +0200
  [RFC PATCH 08/10] extable: rename 'sortextable' script to 'sorttable' Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 07:50 +0200
  [RFC PATCH 05/10] objtool, x86: add facility for asm code to provide CFI hints Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 07:50 +0200
    Re: [RFC PATCH 05/10] objtool, x86: add facility for asm code to  provide CFI hints Andy Lutomirski <luto@kernel.org> - 2017-06-01 16:00 +0200
      Re: [RFC PATCH 05/10] objtool, x86: add facility for asm code to  provide CFI hints Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 16:20 +0200
        Re: [RFC PATCH 05/10] objtool, x86: add facility for asm code to  provide CFI hints Andy Lutomirski <luto@kernel.org> - 2017-06-01 16:50 +0200
          Re: [RFC PATCH 05/10] objtool, x86: add facility for asm code to  provide CFI hints Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 17:10 +0200
  [RFC PATCH 01/10] objtool: move checking code to check.c Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 07:50 +0200
  [RFC PATCH 07/10] x86/asm: add CFI hint annotations to sync_core() Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 07:50 +0200
  [RFC PATCH 04/10] objtool: add undwarf debuginfo generation Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 07:50 +0200
  [RFC PATCH 10/10] x86/unwind: add undwarf unwinder Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 07:50 +0200
    Re: [RFC PATCH 10/10] x86/unwind: add undwarf unwinder Peter Zijlstra <peterz@infradead.org> - 2017-06-01 13:10 +0200
      Re: [RFC PATCH 10/10] x86/unwind: add undwarf unwinder Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 14:30 +0200
        Re: [RFC PATCH 10/10] x86/unwind: add undwarf unwinder Jiri Slaby <jslaby@suse.cz> - 2017-06-01 14:50 +0200
          Re: [RFC PATCH 10/10] x86/unwind: add undwarf unwinder Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 15:10 +0200
          Re: [RFC PATCH 10/10] x86/unwind: add undwarf unwinder Peter Zijlstra <peterz@infradead.org> - 2017-06-01 15:50 +0200
        Re: [RFC PATCH 10/10] x86/unwind: add undwarf unwinder Peter Zijlstra <peterz@infradead.org> - 2017-06-01 15:20 +0200
    Re: [RFC PATCH 10/10] x86/unwind: add undwarf unwinder Peter Zijlstra <peterz@infradead.org> - 2017-06-01 14:20 +0200
      Re: [RFC PATCH 10/10] x86/unwind: add undwarf unwinder Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 14:40 +0200
        Re: [RFC PATCH 10/10] x86/unwind: add undwarf unwinder Peter Zijlstra <peterz@infradead.org> - 2017-06-01 15:20 +0200
          Re: [RFC PATCH 10/10] x86/unwind: add undwarf unwinder Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 17:10 +0200
  [RFC PATCH 02/10] objtool, x86: add several functions and files to the objtool whitelist Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 07:50 +0200
  Re: [RFC PATCH 00/10] x86: undwarf unwinder Ingo Molnar <mingo@kernel.org> - 2017-06-01 08:10 +0200
    Re: [RFC PATCH 00/10] x86: undwarf unwinder Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 14:00 +0200
      Re: [RFC PATCH 00/10] x86: undwarf unwinder Peter Zijlstra <peterz@infradead.org> - 2017-06-01 14:20 +0200
        Re: [RFC PATCH 00/10] x86: undwarf unwinder Jiri Slaby <jslaby@suse.cz> - 2017-06-01 14:40 +0200
          Re: [RFC PATCH 00/10] x86: undwarf unwinder Jiri Slaby <jslaby@suse.cz> - 2017-06-01 15:00 +0200
          Re: [RFC PATCH 00/10] x86: undwarf unwinder Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 15:00 +0200
        Re: [RFC PATCH 00/10] x86: undwarf unwinder Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 14:50 +0200
          Re: [RFC PATCH 00/10] x86: undwarf unwinder Peter Zijlstra <peterz@infradead.org> - 2017-06-01 15:30 +0200
            Re: [RFC PATCH 00/10] x86: undwarf unwinder Sergey Senozhatsky <sergey.senozhatsky.work@gmail.com> - 2017-06-06 16:20 +0200
          Re: [RFC PATCH 00/10] x86: undwarf unwinder Andy Lutomirski <luto@kernel.org> - 2017-06-01 16:00 +0200
      Re: [RFC PATCH 00/10] x86: undwarf unwinder Ingo Molnar <mingo@kernel.org> - 2017-06-01 16:00 +0200
        Re: [RFC PATCH 00/10] x86: undwarf unwinder Jiri Slaby <jslaby@suse.cz> - 2017-06-01 16:00 +0200
          Re: [RFC PATCH 00/10] x86: undwarf unwinder Jiri Slaby <jslaby@suse.cz> - 2017-06-02 10:40 +0200
        Re: [RFC PATCH 00/10] x86: undwarf unwinder Josh Poimboeuf <jpoimboe@redhat.com> - 2017-06-01 16:10 +0200
        Re: [RFC PATCH 00/10] x86: undwarf unwinder Jiri Slaby <jslaby@suse.cz> - 2017-06-01 16:10 +0200
          Re: [RFC PATCH 00/10] x86: undwarf unwinder Mel Gorman <mgorman@suse.de> - 2017-06-02 12:50 +0200

csiph-web