Re: [PATCH 2/2] radix-tree: Fix optimisation problem

From	Linus Torvalds <torvalds@linux-foundation.org>
Newsgroups	linux.kernel
Subject	Re: [PATCH 2/2] radix-tree: Fix optimisation problem
Date	2016-09-25 22:00 +0200
Message-ID	<slnKF-2kb-5@gated-at.bofh.it> (permalink)
References	(2 earlier) <sl4I1-7rE-5@gated-at.bofh.it> <sl5kJ-7Xh-5@gated-at.bofh.it> <sllSx-1a9-5@gated-at.bofh.it> <slmYh-240-5@gated-at.bofh.it> <slmYh-240-3@gated-at.bofh.it>
Organization	linux.* mail to news gateway

Show all headers | View raw

[Multipart message — attachments visible in raw view] - view raw

On Sun, Sep 25, 2016 at 12:04 PM, Linus Torvalds
<torvalds@linux-foundation.org> wrote:
>        It gets rid of
> the ad-hoc arithmetic in radix_tree_descend(), and just makes all that
> be inside the is_sibling_entry() logic instead. Which got renamed and
> made to actually return the main sibling.

Sadly, it looks like gcc generates bad code for this approach. Looks
like it ends up testing the resulting sibling pointer twice (because
we explicitly disable -fno-delete-null-pointer-checks in the kernel,
and we have no way to say "look, I know this pointer I'm returning is
non-null").

So a smaller patch that keeps the old boolean "is_sibling_entry()" but
then actually *uses* that inside radix_tree_descend() and then tries
to make the nasty cast to "void **" more legible by making it use a
temporary variable seems to be a reasonable balance.

At least I feel like I can still read the code, but admittedly by now
that may be because I've stared at those few lines so much that I feel
like I know what's going on. So maybe the code isn't actually any more
legible after all.

.. and unlike my previous patch, it actually generates better code
than the original (while still passing the fixed test-suite, of
course). The reason seems to be exactly that temporary variable,
allowing us to just do

        entry = rcu_dereference_raw(*sibentry);

rather than doing

        entry = rcu_dereference_raw(parent->slots[offset]);

with the re-computed offset.

So I think I'll commit this unless somebody screams.

                     Linus

Thread

Re: [PATCH 2/2] radix-tree: Fix optimisation problem Cedric Blancher <cedric.blancher@gmail.com> - 2016-09-25 01:40 +0200
  Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-25 02:20 +0200
    Re: [PATCH 2/2] radix-tree: Fix optimisation problem Cedric Blancher <cedric.blancher@gmail.com> - 2016-09-25 20:00 +0200
      Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-25 21:10 +0200
        Re: [PATCH 2/2] radix-tree: Fix optimisation problem Cedric Blancher <cedric.blancher@gmail.com> - 2016-09-25 21:50 +0200
        Re: [PATCH 2/2] radix-tree: Fix optimisation problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-09-25 22:00 +0200
          RE: [PATCH 2/2] radix-tree: Fix optimisation problem Matthew Wilcox <mawilcox@microsoft.com> - 2016-09-26 23:30 +0200
            Re: [PATCH 2/2] radix-tree: Fix optimisation problem Cedric Blancher <cedric.blancher@gmail.com> - 2016-09-26 23:50 +0200

csiph-web