Re: local_add_return

Mathieu Desnoyers
2008-12-17T00:01:55Z

* Rusty Russell (rusty@rustcorp.com.au) wrote:
> On Tuesday 16 December 2008 17:43:14 David Miller wrote:
> > Here ya go:
>
> Very interesting. There's a little noise there (that first local_inc of 243
> is wrong), but the picture is clear: trivalue is the best implementation for
> sparc64.
>
> Note: trivalue uses 3 values, so instead of hitting random values across 8MB
> it's across 24MB, and despite the resulting cache damage it's 15% faster. The
> cpu_local_inc test is a single value, so no cache effects: it shows trivalue
> to be 3 to 3.5 times faster in the cache-hot case.
>
> This sucks, because it really does mean that there's no one-size-fits-all
> implementation of local_t. There's also no platform yet where atomic_long_t
> is the right choice; and that's the default!
>

This problem could be fixed by introducing a local_count_t, which maps
to either local_t or to a trivalue, along with read accessors which sums
the trivalues.

I think we have two different use-cases here :

- local_t is useful as-is for things such as a tracer, which need to
modify an element of data atomically wrt local interrupts. The
atomic_long_t, in this case, is the correct fallback.
- local_count_t could be used for fast counters. It could be a
requirement to only use it from thread/softirq/irq context (never NMI
or exception) so we are sure the trivalue approach will not lead to
corruption. local_count_t could use either local_t or trivalue
depending on which is the fastest on a given architecture.

Mathieu

> Any chance of an IA64 or s390 run? You can normalize if you like, since
> it's only to compare the different approaches.
>
> Cheers,
> Rusty.
>
> Benchmarks for local_t variants
>
> (This patch also fixes the x86 cpu_local_* macros, which are obviously
> unused).
>
> I chose a large array (1M longs) for the inc/add/add_return tests so
> the trivalue case would show some cache pressure.
>
> The cpu_local_inc case is always cache-hot, so it's not comparable to
> the others.
>
> Time in ns per iteration (brackets is with CONFIG_PREEMPT=y):
>
> inc add add_return cpu_local_inc read
> x86-32: 2.13 Ghz Core Duo 2
> atomic_long 118 118 115 17 17
> irqsave/rest 77 78 77 23 16
> trivalue 45 45 127 3(6) 21
> local_t 36 36 36 1(5) 17
>
> x86-64: 2.6 GHz Dual-Core AMD Opteron 2218
> atomic_long 55 60 - 6 19
> irqsave/rest 54 54 - 11 19
> trivalue 47 47 - 5 28
> local_t 47 46 - 1 19
>
> PPC64: 2.7 GHz PPC970MP [normalized]
> atomic_long 18 18 20 3(4) 8
> irqsave/rest 10(4) 5(4) 4 8(9) 10(9)
> trivalue 9 9 2 1(3) 10
> local_t 18 18 18 3(4) 8
>
> Sparc64: UltraSPARC-IIIi
> atomic_long 243 222 - 37 169
> irqsave/rest 205 205 - 25 169
> trivalue 193 193 - 11 221
> local_t 221 221 - 37 169
>
> Sparc64: Niagara-2
> atomic_long 207 206 - 72 160
> irqsave/rest 228 228 - 78 160
> trivalue: 172 172 - 20 222
> local_t 206 207 - 73 160
>
> Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
> ---
> arch/x86/include/asm/local.h | 20 +--
> init/main.c | 223 +++++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 233 insertions(+), 10 deletions(-)
>
> diff --git a/arch/x86/include/asm/local.h b/arch/x86/include/asm/local.h
> --- a/arch/x86/include/asm/local.h
> +++ b/arch/x86/include/asm/local.h
> @@ -220,16 +220,16 @@ static inline long local_sub_return(long
> preempt_enable(); \
> }) \
>
> -#define cpu_local_read(l) cpu_local_wrap_v(local_read(&__get_cpu_var((l))))
> -#define cpu_local_set(l, i) cpu_local_wrap(local_set(&__get_cpu_var((l)), (i)))
> -#define cpu_local_inc(l) cpu_local_wrap(local_inc(&__get_cpu_var((l))))
> -#define cpu_local_dec(l) cpu_local_wrap(local_dec(&__get_cpu_var((l))))
> -#define cpu_local_add(i, l) cpu_local_wrap(local_add((i), &__get_cpu_var((l))))
> -#define cpu_local_sub(i, l) cpu_local_wrap(local_sub((i), &__get_cpu_var((l))))
> +#define cpu_local_read(l) cpu_local_wrap_v(local_read(&__get_cpu_var(l)))
> +#define cpu_local_set(l, i) cpu_local_wrap(local_set(&__get_cpu_var(l), (i)))
> +#define cpu_local_inc(l) cpu_local_wrap(local_inc(&__get_cpu_var(l)))
> +#define cpu_local_dec(l) cpu_local_wrap(local_dec(&__get_cpu_var(l)))
> +#define cpu_local_add(i, l) cpu_local_wrap(local_add((i), &__get_cpu_var(l)))
> +#define cpu_local_sub(i, l) cpu_local_wrap(local_sub((i), &__get_cpu_var(l)))
>
> -#define __cpu_local_inc(l) cpu_local_inc((l))
> -#define __cpu_local_dec(l) cpu_local_dec((l))
> -#define __cpu_local_add(i, l) cpu_local_add((i), (l))
> -#define __cpu_local_sub(i, l) cpu_local_sub((i), (l))
> +#define __cpu_local_inc(l) cpu_local_inc(l)
> +#define __cpu_local_dec(l) cpu_local_dec(l)
> +#define __cpu_local_add(i, l) cpu_local_add((i), l)
> +#define __cpu_local_sub(i, l) cpu_local_sub((i), l)
>
> #endif /* _ASM_X86_LOCAL_H */
> diff --git a/init/main.c b/init/main.c
> --- a/init/main.c
> +++ b/init/main.c
> @@ -534,6 +534,225 @@ void __init __weak thread_info_cache_ini
> {
> }
>
> +/* There are three obvious ways to implement local_t on an arch which
> + * can't do single-instruction inc/dec etc.
> + * 1) atomic_long
> + * 2) irq_save/irq_restore
> + * 3) multiple counters.
> + *
> + * This does a very rough benchmark on each one.
> + */
> +struct local1 {
> + atomic_long_t v;
> +};
> +struct local2 {
> + unsigned long v;
> +};
> +struct local3 {
> + unsigned long v[3];
> +};
> +
> +/* Enough to put some pressure on the caches. */
> +#define NUM_LOCAL_TEST (1024*1024)
> +#define NUM_LOCAL_RUNS (NUM_LOCAL_TEST*32)
> +/* This will make it jump around looking random */
> +#define STRIDE 514001
> +
> +static void *test_local_variants_mem;
> +
> +static void init_test_local_variants(void)
> +{
> + unsigned long size;
> + size = max(sizeof(struct local1),
> + max(sizeof(struct local2),
> + max(sizeof(struct local3), sizeof(local_t))))
> + * NUM_LOCAL_TEST;
> + /* Assume this works in early boot. */
> + test_local_variants_mem = alloc_bootmem_nopanic(size);
> +
> + if (!test_local_variants_mem) {
> + printk("test_local_variants: failed to allocate %lu bytes\n",
> + size);
> + return;
> + }
> +}
> +
> +static void print_result(const char *str,
> + struct timespec start, struct timespec end)
> +{
> + s64 diff;
> +
> + diff = ktime_to_ns(ktime_sub(timespec_to_ktime(end), timespec_to_ktime(start)));
> + printk("%s=%lli/%lli ",
> + str, diff, diff/NUM_LOCAL_RUNS);
> +}
> +
> +static unsigned int warm_local_test_cache(const void *mem, size_t len)
> +{
> + unsigned int i, total = 0;
> + for (i = 0; i < len; i++)
> + total += ((char *)mem)[i];
> + return total;
> +}
> +
> +#define TEST_LOOP(expr) \
> + n = 0; \
> + getnstimeofday(&start); \
> + for (i = 0; i < NUM_LOCAL_RUNS; i++) { \
> + expr; \
> + n += STRIDE; \
> + n %= NUM_LOCAL_TEST; \
> + } \
> + getnstimeofday(&end);
> +
> +/* This doesn't test cache effects at all */
> +#define NUM_PERCPU_VARS 16
> +DEFINE_PER_CPU(struct local1[NUM_PERCPU_VARS], local1_test);
> +DEFINE_PER_CPU(struct local2[NUM_PERCPU_VARS], local2_test);
> +DEFINE_PER_CPU(struct local3[NUM_PERCPU_VARS], local3_test);
> +DEFINE_PER_CPU(local_t[NUM_PERCPU_VARS], local4_test);
> +
> +static void test_local_variants(void)
> +{
> + struct timespec start, end;
> + unsigned int i, n;
> + unsigned long total, warm_total = 0;
> + struct local1 *l1;
> + struct local2 *l2;
> + struct local3 *l3;
> + local_t *l4;
> +
> + if (!test_local_variants_mem)
> + return;
> +
> + printk("Running local_t variant benchmarks\n");
> + l1 = test_local_variants_mem;
> + l2 = test_local_variants_mem;
> + l3 = test_local_variants_mem;
> + l4 = test_local_variants_mem;
> +
> + printk("atomic_long: ");
> + memset(l1, 0, sizeof(*l1)*NUM_LOCAL_TEST);
> + TEST_LOOP(atomic_long_inc(&l1[n].v));
> + print_result("local_inc", start, end);
> +
> + warm_total += warm_local_test_cache(l1, sizeof(*l1)*NUM_LOCAL_TEST);
> + TEST_LOOP(atomic_long_add(1234, &l1[n].v));
> + print_result("local_add", start, end);
> +
> + warm_total += warm_local_test_cache(l1, sizeof(*l1)*NUM_LOCAL_TEST);
> + TEST_LOOP(atomic_long_inc(&__get_cpu_var(local1_test)[n%NUM_PERCPU_VARS].v));
> + print_result("cpu_local_inc", start, end);
> +
> + warm_total += warm_local_test_cache(l1, sizeof(*l1)*NUM_LOCAL_TEST);
> + total = 0;
> + TEST_LOOP(total += atomic_long_read(&l1[n].v));
> + print_result("local_read", start, end);
> +
> + warm_total += warm_local_test_cache(l1, sizeof(*l1)*NUM_LOCAL_TEST);
> + TEST_LOOP(total += atomic_long_add_return(7, &l1[n].v));
> + print_result("local_add_return", start, end);
> +
> + printk("(total was %lu)\n", total);
> +
> + printk("irqsave/restore: ");
> + memset(l2, 0, sizeof(*l2)*NUM_LOCAL_TEST);
> + TEST_LOOP(unsigned long flags;
> + local_irq_save(flags);
> + l2[n].v++;
> + local_irq_restore(flags));
> + print_result("local_inc", start, end);
> +
> + warm_total += warm_local_test_cache(l2, sizeof(*l2)*NUM_LOCAL_TEST);
> + TEST_LOOP(unsigned long flags;
> + local_irq_save(flags);
> + l2[n].v += 1234;
> + local_irq_restore(flags));
> + print_result("local_add", start, end);
> +
> + warm_total += warm_local_test_cache(l2, sizeof(*l2)*NUM_LOCAL_TEST);
> + TEST_LOOP(unsigned long flags;
> + local_irq_save(flags);
> + __get_cpu_var(local2_test)[n%NUM_PERCPU_VARS].v++;
> + local_irq_restore(flags));
> + print_result("cpu_local_inc", start, end);
> +
> + warm_total += warm_local_test_cache(l2, sizeof(*l2)*NUM_LOCAL_TEST);
> + total = 0;
> + TEST_LOOP(total += l2[n].v);
> + print_result("local_read", start, end);
> +
> + warm_total += warm_local_test_cache(l1, sizeof(*l1)*NUM_LOCAL_TEST);
> + TEST_LOOP(unsigned long flags;
> + local_irq_save(flags);
> + l2[n].v += 7;
> + total += l2[n].v;
> + local_irq_restore(flags));
> + print_result("local_add_return", start, end);
> + printk("(total was %lu)\n", total);
> +
> + printk("trivalue: ");
> + memset(l3, 0, sizeof(*l3)*NUM_LOCAL_TEST);
> + TEST_LOOP(unsigned int idx
> + = !(preempt_count() & (HARDIRQ_MASK | SOFTIRQ_MASK)) +
> + !(preempt_count() & HARDIRQ_MASK);
> + l3[n].v[idx]++);
> + print_result("local_inc", start, end);
> +
> + warm_total += warm_local_test_cache(l3, sizeof(*l3)*NUM_LOCAL_TEST);
> + TEST_LOOP(unsigned int idx
> + = !(preempt_count() & (HARDIRQ_MASK | SOFTIRQ_MASK)) +
> + !(preempt_count() & HARDIRQ_MASK);
> + l3[n].v[idx] += 1234);
> + print_result("local_add", start, end);
> +
> + warm_total += warm_local_test_cache(l3, sizeof(*l3)*NUM_LOCAL_TEST);
> + TEST_LOOP(unsigned int idx
> + = !(preempt_count() & (HARDIRQ_MASK | SOFTIRQ_MASK)) +
> + !(preempt_count() & HARDIRQ_MASK);
> + get_cpu_var(local3_test)[n%NUM_PERCPU_VARS].v[idx]++;
> + put_cpu_var());
> + print_result("cpu_local_inc", start, end);
> +
> + warm_total += warm_local_test_cache(l3, sizeof(*l3)*NUM_LOCAL_TEST);
> + total = 0;
> + TEST_LOOP(total += l3[n].v[0] + l3[n].v[1] + l3[n].v[2]);
> + print_result("local_read", start, end);
> +
> + warm_total += warm_local_test_cache(l1, sizeof(*l1)*NUM_LOCAL_TEST);
> + TEST_LOOP(unsigned long flags;
> + local_irq_save(flags);
> + l3[n].v[0] += 7;
> + total += l3[n].v[0] + l3[n].v[1] + l3[n].v[2];
> + local_irq_restore(flags));
> + print_result("local_add_return", start, end);
> +
> + printk("(total was %lu)\n", total);
> +
> + printk("local_t: ");
> + memset(l4, 0, sizeof(*l4)*NUM_LOCAL_TEST);
> + TEST_LOOP(local_inc(&l4[n]));
> + print_result("local_inc", start, end);
> +
> + warm_total += warm_local_test_cache(l4, sizeof(*l4)*NUM_LOCAL_TEST);
> + TEST_LOOP(local_add(1234, &l4[n]));
> + print_result("local_add", start, end);
> +
> + warm_total += warm_local_test_cache(l4, sizeof(*l4)*NUM_LOCAL_TEST);
> + TEST_LOOP(cpu_local_inc(local4_test[n%NUM_PERCPU_VARS]));
> + print_result("cpu_local_inc", start, end);
> +
> + warm_total += warm_local_test_cache(l4, sizeof(*l4)*NUM_LOCAL_TEST);
> + total = 0;
> + TEST_LOOP(total += local_read(&l4[n]));
> + print_result("local_read", start, end);
> +
> + warm_total += warm_local_test_cache(l1, sizeof(*l1)*NUM_LOCAL_TEST);
> + TEST_LOOP(total += local_add_return(7, &l1[n].v));
> + print_result("local_add_return", start, end);
> + printk("(total was %lu, warm_total %lu)\n", total, warm_total);
> +}
> +
> asmlinkage void __init start_kernel(void)
> {
> char * command_line;
> @@ -630,6 +849,8 @@ asmlinkage void __init start_kernel(void
> */
> locking_selftest();
>
> + init_test_local_variants();
> +
> #ifdef CONFIG_BLK_DEV_INITRD
> if (initrd_start && !initrd_below_start_ok &&
> page_to_pfn(virt_to_page((void *)initrd_start)) < min_low_pfn) {
> @@ -687,6 +908,8 @@ asmlinkage void __init start_kernel(void
> acpi_early_init(); /* before LAPIC and SMP init */
>
> ftrace_init();
> +
> + test_local_variants();
>
> /* Do the rest non-__init'ed, we're now alive */
> rest_init();

--
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68