From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <linux-kernel-owner@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
        id S1751552AbdKUSEA (ORCPT <rfc822;w@1wt.eu>);
        Tue, 21 Nov 2017 13:04:00 -0500
Received: from mga01.intel.com ([192.55.52.88]:8170 "EHLO mga01.intel.com"
        rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP
        id S1751324AbdKUSD7 (ORCPT <rfc822;Linux-kernel@vger.kernel.org>);
        Tue, 21 Nov 2017 13:03:59 -0500
X-ExtLoop1: 1
X-IronPort-AV: E=Sophos;i="5.44,432,1505804400"; 
   d="scan'208";a="176241018"
Date: Tue, 21 Nov 2017 10:03:50 -0800
From: Andi Kleen <ak@linux.intel.com>
To: Jiri Olsa <jolsa@redhat.com>
Cc: Jin Yao <yao.jin@linux.intel.com>, acme@kernel.org, jolsa@kernel.org,
        peterz@infradead.org, mingo@redhat.com,
        alexander.shishkin@linux.intel.com, Linux-kernel@vger.kernel.org,
        kan.liang@intel.com, yao.jin@intel.com
Subject: Re: [PATCH v1 5/9] perf util: Remove a set of shadow stats static
 variables
Message-ID: <20171121180350.GJ28112@tassilo.jf.intel.com>
References: <1511189024-19908-1-git-send-email-yao.jin@linux.intel.com>
 <1511189024-19908-6-git-send-email-yao.jin@linux.intel.com>
 <20171121151740.GG20440@krava>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20171121151740.GG20440@krava>
User-Agent: Mutt/1.9.1 (2017-09-22)
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

> all this is about switching from array to rb_list for the --per-thread case,
> which can be considered as a special use case.. how much do we suffer in
> performance with new code? how about the "perf stat -I 100", would it scale
> ok for extreme cases (many events in -e or -dddd..)

rbtrees scale by log N, with N being the entries in the tree.

Even in extreme cases, let's say 10000 events and 1000 cpus it would
need only 8 memory accesses and comparisons for each look up.
Even if we assume cache misses for all of the memory lookups,
at ~200ns per cache miss it's still only 1us per event, which 
is negligible.

In practice not all memory accesses will be misses because
the upper levels of the tree are almost certainly cached
from earlier accesses.


-Andi