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

Groups > linux.kernel > #1641173 > unrolled thread

Re: [PATCH] sched: remove sched_find_first_bit()

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH] sched: remove sched_find_first_bit() Ingo Molnar <mingo@kernel.org> - 2017-05-14 20:10 +0200
    Re: [PATCH] sched: remove sched_find_first_bit() Arnd Bergmann <arnd@arndb.de> - 2017-05-15 18:10 +0200
      Re: [PATCH] sched: remove sched_find_first_bit() Arnd Bergmann <arnd@arndb.de> - 2017-05-15 22:40 +0200
        Re: [PATCH] sched: remove sched_find_first_bit() Arnd Bergmann <arnd@arndb.de> - 2017-05-15 23:10 +0200
    Re: [PATCH] sched: remove sched_find_first_bit() Ingo Molnar <mingo@kernel.org> - 2017-05-16 10:40 +0200
      Re: [PATCH] sched: remove sched_find_first_bit() Ingo Molnar <mingo@kernel.org> - 2017-05-18 09:20 +0200

#1641173 — Re: [PATCH] sched: remove sched_find_first_bit()

* Yury Norov <ynorov@caviumnetworks.com> wrote:

> sched_find_first_bit() is in fact the unrolled version of
> find_first_bit(), which is theoretically faster in some cases.
> But in the kernel it is called only in couple places in 
> kernel/sched/rt.c, and both of them are not looking like hot
> paths [...]

They are in terms of scheduling: pick_next_rt_entity() is in the RT scheduling 
fastpath.

Which makes me just suspicious of how careful this patch really is:

> that will doubtly achieve measurable benefit from using unrolled version of 
> find_first_bit() - there's no hard loops, and the execution path is not really 
> short.

... that's really just handwaving. Numbers please.

Thanks,

	Ingo

[toc] | [next] | [standalone]

#1641860

On Mon, May 15, 2017 at 5:47 PM, Yury Norov <ynorov@caviumnetworks.com> wrote:
> On Sun, May 14, 2017 at 08:09:17PM +0200, Ingo Molnar wrote:
>>
>> * Yury Norov <ynorov@caviumnetworks.com> wrote:
>>
>> > sched_find_first_bit() is in fact the unrolled version of
>> > find_first_bit(), which is theoretically faster in some cases.
>> > But in the kernel it is called only in couple places in
>> > kernel/sched/rt.c, and both of them are not looking like hot
>> > paths [...]
>>
>> They are in terms of scheduling: pick_next_rt_entity() is in the RT scheduling
>> fastpath.
>
> Sorry that. I'll be more specific. I was only saying that pick_next_rt_entity()
> is big enough to feel any difference, and it's still true for me. Please
> forget about hot paths.
>
>> Which makes me just suspicious of how careful this patch really is:
>>
>> > that will doubtly achieve measurable benefit from using unrolled version of
>> > find_first_bit() - there's no hard loops, and the execution path is not really
>> > short.
>>
>> ... that's really just handwaving. Numbers please.
>
> I use qemu running arm64 as my testing environment. It's not the best
> for performance measurements, but allows estimate something... So,
>
> This patch shows the time (in cycles) that kernel spends running the
> pick_next_rt_entity() code:
>
> diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
> index f04346329204..7c6194e30230 100644
> --- a/kernel/sched/rt.c
> +++ b/kernel/sched/rt.c
> @@ -1529,6 +1529,8 @@ pick_next_task_rt(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
>         struct task_struct *p;
>         struct rt_rq *rt_rq = &rq->rt;
>
> +       u64 cycles = get_cycles();
> +
>         if (need_pull_rt_task(rq, prev)) {
>                 /*
>                  * This is OK, because current is on_cpu, which avoids it being
> @@ -1568,6 +1570,8 @@ pick_next_task_rt(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
>
>         queue_push_tasks(rq);
>
> +       pr_err("cycles: %lld\n", get_cycles() - cycles);
> +
>         return p;
>  }
>
> I collected about 700 results in dmesg, and took 600 fastest.
> For the vanilla kernel, the average value is 368, and for patched
> kernel it is 388. It's 5% slower. But the standard deviation is
> really big for both series' - 131 and 106 cycles respectively, which
> is ~ 30%. And so, my conclusion is: there's no benefit in using
> sched_find_first_bit() comparing to find_first_bit().
>
> I also think that sched_find_first_bit() may be faster that find_first_bit()
> because it's inlined in the caller. We can do so for find_first_bit() if
> it takes small sizes at compile time, and so all parts of kernel will
> use fast find_first_bit, not only sched.

I suspect the first step would be to 'select GENERIC_FIND_FIRST_BIT'
on ARM64, which should already improve the performance for those
files that never call the 'next' variants.

Adding an inline version of find_first_{,zero_}bit could also help, but
is harder to quantify.

        Arnd

[toc] | [prev] | [next] | [standalone]

#1642033

On Mon, May 15, 2017 at 6:17 PM, Yury Norov <ynorov@caviumnetworks.com> wrote:
> On Mon, May 15, 2017 at 06:06:18PM +0200, Arnd Bergmann wrote:
>> On Mon, May 15, 2017 at 5:47 PM, Yury Norov <ynorov@caviumnetworks.com> wrote:
>> > On Sun, May 14, 2017 at 08:09:17PM +0200, Ingo Molnar wrote:
>> >
>> > I also think that sched_find_first_bit() may be faster that find_first_bit()
>> > because it's inlined in the caller. We can do so for find_first_bit() if
>> > it takes small sizes at compile time, and so all parts of kernel will
>> > use fast find_first_bit, not only sched.
>>
>> I suspect the first step would be to 'select GENERIC_FIND_FIRST_BIT'
>> on ARM64, which should already improve the performance for those
>> files that never call the 'next' variants.
>>
>> Adding an inline version of find_first_{,zero_}bit could also help, but
>> is harder to quantify.
>>
>
> I checked again, and in fact I measured on top of this patch:
> https://lkml.org/lkml/2017/5/13/137
> So find_first_bit is already enabled.

Ok. I've played around with this for a bit more and came to a generic
version that is almost as good as the current sched_find_first_bit()
on x86 (one extra comparison):

+#define sched_find_first_bit(b) find_first_bit(b, 128)
-extern unsigned long find_first_bit(const unsigned long *addr,
+extern unsigned long __find_first_bit(const unsigned long *addr,
                                    unsigned long size);

+static inline unsigned long find_first_bit(const unsigned long *addr,
+                                   unsigned long size)
+{
+       unsigned long idx;
+
+       if (!__builtin_constant_p(size))
+               return __find_first_bit(addr, size);
+
+       idx = 0;
+       switch (size) {
+       case BITS_PER_LONG * 4:
+               if (addr[0])
+                       return __ffs(addr[0]) + idx;
+               addr++;
+               idx += BITS_PER_LONG;
+       case BITS_PER_LONG * 3:
+               if (addr[0])
+                       return __ffs(addr[0]) + idx;
+               addr++;
+               idx += BITS_PER_LONG;
+       case BITS_PER_LONG * 2:
+               if (addr[0])
+                       return __ffs(addr[0]) + idx;
+               addr++;
+               idx += BITS_PER_LONG;
+       case BITS_PER_LONG * 1:
+               if (addr[0])
+                       return __ffs(addr[0]) + idx;
+               addr++;
+               idx += BITS_PER_LONG;
+               return idx;
+       }
+
+       return __find_first_bit(addr, size);
+}

However, on architectures that rely on
include/asm-generic/bitops/__ffs.h or something
similarly verbose, this would just add needless bloat
to the size rather than actually making a difference
in performance.

        Arnd

[toc] | [prev] | [next] | [standalone]

#1642059

On Mon, May 15, 2017 at 10:58 PM, Yury Norov <ynorov@caviumnetworks.com> wrote:
> On Mon, May 15, 2017 at 10:31:17PM +0200, Arnd Bergmann wrote:
>> On Mon, May 15, 2017 at 6:17 PM, Yury Norov <ynorov@caviumnetworks.com> wrote:
>>
> Yes, something like this. But size is not the multiple of BITS_PER_LONG in
> general. This should work better:
>
>        switch (round_up(size), BITS_PER_LONG) {
>        case BITS_PER_LONG * 4:
>                if (addr[0])
>                        goto ret;
>                addr++;
>                idx += BITS_PER_LONG;
>        case BITS_PER_LONG * 3:
>                if (addr[0])
>                        goto ret;
>                addr++;
>                idx += BITS_PER_LONG;
>        case BITS_PER_LONG * 2:
>                if (addr[0])
>                        goto ret;
>                addr++;
>                idx += BITS_PER_LONG;
>        case BITS_PER_LONG * 1:
>                if (addr[0])
>                        goto ret;
>                addr++;
>                idx += BITS_PER_LONG;
>                return idx;
>        }
>
>        return __find_first_bit(addr, size);
>
> ret:
>        return idx + min(__ffs(addr[0]), size % BITS_PER_LONG;
>        }
>
> (I didn't test it yet though)
>
>> However, on architectures that rely on
>> include/asm-generic/bitops/__ffs.h or something
>> similarly verbose, this would just add needless bloat
>> to the size rather than actually making a difference
>> in performance.

I tried something along these lines earlier and couldn't
get it to produce the comparable object code in the
common case.

For sched_find_first_bit() I was able to cheat and
pass 128 as the length (along with a comment), and
most others are either multiples of BITS_PER_LONG,
or they are not constant.

       Arnd

[toc] | [prev] | [next] | [standalone]

#1642305

* Yury Norov <ynorov@caviumnetworks.com> wrote:

> I collected about 700 results in dmesg, and took 600 fastest.
> For the vanilla kernel, the average value is 368, and for patched
> kernel it is 388. It's 5% slower. But the standard deviation is 
> really big for both series' - 131 and 106 cycles respectively, which
> is ~ 30%. And so, my conclusion is: there's no benefit in using
> sched_find_first_bit() comparing to find_first_bit().

Erm, so you in essence claim:

	"according to measurements the new code is 5% slower, with a high, 30% 
	 stddev, hence the new code is better!"

Basic logic fail...

Thanks,

	Ingo

[toc] | [prev] | [next] | [standalone]

#1643896

* Yury Norov <ynorov@caviumnetworks.com> wrote:

> On Tue, May 16, 2017 at 10:30:42AM +0200, Ingo Molnar wrote:
> > 
> > * Yury Norov <ynorov@caviumnetworks.com> wrote:
> > 
> > > I collected about 700 results in dmesg, and took 600 fastest.
> > > For the vanilla kernel, the average value is 368, and for patched
> > > kernel it is 388. It's 5% slower. But the standard deviation is 
> > > really big for both series' - 131 and 106 cycles respectively, which
> > > is ~ 30%. And so, my conclusion is: there's no benefit in using
> > > sched_find_first_bit() comparing to find_first_bit().
> > 
> > Erm, so you in essence claim:
> > 
> > 	"according to measurements the new code is 5% slower, with a high, 30% 
> > 	 stddev, hence the new code is better!"
> > 
> > Basic logic fail...
> > 
> > Thanks,
> > 
> > 	Ingo
> 
> No, in essence I claim that scatter is so big (in both cases, and in
> case of vanilla kernel even bigger) that 5% is not a meaningful
> difference. To be specific - new measured value is inside the
> confidence interval of previous one.

Firstly, the high spread is due to the poor measurement method: by increasing the 
number of measurements the standard deviation can be reduced.

Secondly, and most importantly, the claim you made based on the numbers is simply 
false:

> > > And so, my conclusion is: there's no benefit in using
> > > sched_find_first_bit() comparing to find_first_bit().

you _measured no benefit_, and in fact the result you got is leaning towards it 
being a benefit.

When doing a proper measurement it might strengthen, vanish or turn around - we 
simply don't know.

Thanks,

	Ingo

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web