From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754633AbcEPTE7 (ORCPT ); Mon, 16 May 2016 15:04:59 -0400 Received: from mail-io0-f194.google.com ([209.85.223.194]:35279 "EHLO mail-io0-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754318AbcEPTE4 (ORCPT ); Mon, 16 May 2016 15:04:56 -0400 MIME-Version: 1.0 In-Reply-To: <1463417556-23087-4-git-send-email-pantelis.antoniou@konsulko.com> References: <1463417556-23087-1-git-send-email-pantelis.antoniou@konsulko.com> <1463417556-23087-4-git-send-email-pantelis.antoniou@konsulko.com> Date: Mon, 16 May 2016 21:04:55 +0200 X-Google-Sender-Auth: 7wrvee9v-Z9qAQat6cvStRk_PvE Message-ID: Subject: Re: [PATCH v2 3/5] of: unittest: hashed phandles unitest From: Geert Uytterhoeven To: Pantelis Antoniou Cc: Rob Herring , Frank Rowand , Matt Porter , Grant Likely , Koen Kooi , Guenter Roeck , Marek Vasut , "devicetree@vger.kernel.org" , "linux-kernel@vger.kernel.org" , Pantelis Antoniou Content-Type: text/plain; charset=UTF-8 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, May 16, 2016 at 6:52 PM, Pantelis Antoniou wrote: > Add a benchmarking hashed phandles unittest which report what kind > of speed up we get switching to hashed phandle lookups. > > ### dt-test ### the hash method is 8.2 times faster than the original > > On the beaglebone we perform about 1877 phandle lookups until that > point in the unittest. Each non-hashed lookup takes about 23us when > the cash is hot, while the hash lookup takes about 3us. cache > For those 1877 lookup we get a speedup in the boot sequence of > 1877 * (23 - 3) = 37.5ms, which is not spectacular but there's no > point in wasting cycles and energy. > > Signed-off-by: Pantelis Antoniou > --- > drivers/of/unittest.c | 68 +++++++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 68 insertions(+) > > diff --git a/drivers/of/unittest.c b/drivers/of/unittest.c > index 7ea3689..59cad84 100644 > --- a/drivers/of/unittest.c > +++ b/drivers/of/unittest.c > @@ -25,6 +25,9 @@ > > #include > > +#include > +#include > + > #include "of_private.h" > > static struct unittest_results { > @@ -2266,6 +2269,70 @@ out: > static inline void __init of_unittest_overlay(void) { } > #endif > > +#define PHANDLE_LOOKUPS 1000 > + > +static void __init of_unittest_phandle_hash(void) > +{ > + struct device_node *node; > + phandle max_phandle; > + u32 ph; > + unsigned long flags; > + int i, j, total; unsigned int > + ktime_t start, end; > + s64 dur[2]; No idea why ktime_to_us() returns s64 i.s.o. u64... > + int dec, frac; unsigned int? > + /* test only available when hashing is available */ > + if (!of_phandle_ht_available()) { > + pr_warn("phandle hash test requires hash to be initialized\n"); > + return; > + } > + > + /* find the maximum phandle of the tree */ > + raw_spin_lock_irqsave(&devtree_lock, flags); > + max_phandle = 0; > + total = 0; > + for_each_of_allnodes(node) { > + if (node->phandle != (phandle)-1U && Drop the "U" suffix? > + node->phandle > max_phandle) > + max_phandle = node->phandle; > + total++; > + } > + raw_spin_unlock_irqrestore(&devtree_lock, flags); > + max_phandle++; > + > + pr_debug("phandle: max-phandle #%u, #%d total nodes\n", > + (u32)max_phandle, total); phandle is already u32, so no need for the cast. > + > + /* perform random lookups using the hash */ > + for (j = 0; j < 2; j++) { > + > + /* disabled for pass #0, enabled for pass #1 */ > + of_phandle_ht_is_disabled = j == 0; > + > + start = ktime_get_raw(); > + for (i = 0; i < PHANDLE_LOOKUPS; i++) { > + ph = prandom_u32() % max_phandle; > + node = of_find_node_by_phandle(ph); > + of_node_put(node); > + } > + end = ktime_get_raw(); > + > + dur[j] = ktime_to_us(end) - ktime_to_us(start); > + pr_debug("#%d lookups in %lld us (%s)\n", $u > + PHANDLE_LOOKUPS, dur[j], > + j == 0 ? "original" : "hashed"); > + } > + > + unittest(dur[0] > dur[1], "Non hashing phandles are faster!?"); > + > + dec = (int)div64_s64(dur[0] * 10 + 5, dur[1]); I'd expect div64_u64(), if not for ktime_to_us() returning s64... > + frac = dec % 10; > + dec /= 10; > + pr_info("the hash method is %d.%d times faster than the original\n", %u.%u once dec and frac are unsigned. > + dec, frac); > +} Gr{oetje,eeting}s, Geert -- Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org In personal conversations with technical people, I call myself a hacker. But when I'm talking to journalists I just say "programmer" or something like that. -- Linus Torvalds