Metric related performance improvements
Ian Rogers
reviewerv2 cover Metric related performance improvements
The "PMU JSON event tests" have been running slowly, these changes target improving them with an improvement of the test running 8 to 10 times faster.
The first patch changes from searching through all aliases by name in a list to using a hashmap. Doing a fast hashmap__find means testing for having an event needn't load from disk if an event is already present.
The second patch switch the fncache to use a hashmap rather than its own hashmap with a limited number of buckets. When there are many filename queries, such as with a test, there are many collisions with the previous fncache approach leading to linear searching of the entries.
The final patch adds a find function for metrics. Normally metrics can match by name and group, however, only name matching happens when one metric refers to another. As we test every "id" in a metric to see if it is a metric, the find function can dominate performance as it linearly searches all metrics. Add a find function for the metrics table so that a metric can be found by name with a binary search.
Before these changes:
``` $ time perf test -v 10 10: PMU JSON event tests : 10.1: PMU event table sanity : Ok 10.2: PMU event map aliases : Ok 10.3: Parsing of PMU event table metrics : Ok 10.4: Parsing of PMU event table metrics with fake PMUs : Ok 10.5: Parsing of metric thresholds with fake PMUs : Ok real 0m18.499s user 0m18.150s sys 0m3.273s ```
After these changes:
``` $ time perf test -v 10 10: PMU JSON event tests : 10.1: PMU event table sanity : Ok 10.2: PMU event map aliases : Ok 10.3: Parsing of PMU event table metrics : Ok 10.4: Parsing of PMU event table metrics with fake PMUs : Ok 10.5: Parsing of metric thresholds with fake PMUs : Ok real 0m2.338s user 0m1.797s sys 0m2.186s ```
v2: Rebase on tmp.perf-tools-next.
Ian Rogers (3):
perf fncache: Switch to using hashmap
perf pmu: Change aliases from list to hashmap
perf metricgroup: Binary search when resolving referred to metrics
tools/perf/builtin-stat.c | 6 +- tools/perf/pmu-events/empty-pmu-events.c | 66 ++++++++- tools/perf/pmu-events/jevents.py | 66 ++++++++- tools/perf/pmu-events/pmu-events.h | 23 +++- tools/perf/tests/pmu-events.c | 129 +++++++++-------- tools/perf/util/fncache.c | 69 +++++----- tools/perf/util/fncache.h | 1 - tools/perf/util/hwmon_pmu.c | 43 +++--- tools/perf/util/metricgroup.c | 102 ++++++-------- tools/perf/util/metricgroup.h | 2 +- tools/perf/util/pmu.c | 167 +++++++++++++++-------- tools/perf/util/pmu.h | 4 +- tools/perf/util/srccode.c | 4 +- tools/perf/util/tool_pmu.c | 17 +-- 14 files changed, 430 insertions(+), 269 deletions(-)
Signature · 1 line
2.49.0.1045.g170613ef41-goog
Ian Rogers
reviewerPATCH v2 1/3 perf fncache: Switch to using hashmap
The existing fncache can get large in testing situations. As the bucket array is a fixed size this leads to it degrading to O(n) performance. Use a regular hashmap that can dynamically reallocate its array.
Before:
``` $ time perf test "Parsing of PMU event table metrics" 10.3: Parsing of PMU event table metrics : Ok 10.4: Parsing of PMU event table metrics with fake PMUs : Ok real 0m14.132s user 0m17.806s sys 0m0.557s ```
After:
``` $ time perf test "Parsing of PMU event table metrics" 10.3: Parsing of PMU event table metrics : Ok 10.4: Parsing of PMU event table metrics with fake PMUs : Ok real 0m13.287s user 0m13.026s sys 0m0.532s ```
--- tools/perf/util/fncache.c | 69 +++++++++++++++++++++------------------ tools/perf/util/fncache.h | 1 - tools/perf/util/srccode.c | 4 +-- 3 files changed, 39 insertions(+), 35 deletions(-)
tools/perf/util/fncache.c +37 -32
@@ -1,53 +1,58 @@// SPDX-License-Identifier: GPL-2.0-only /* Manage a cache of file names' existence */ +#include <pthread.h> #include <stdlib.h> -#include <unistd.h> #include <string.h> -#include <linux/list.h> +#include <unistd.h> +#include <linux/compiler.h> #include "fncache.h" +#include "hashmap.h" -struct fncache { -struct hlist_node nd; -bool res; -char name[]; -}; +static struct hashmap *fncache; -#define FNHSIZE 61 +static size_t fncache__hash (long key,void *ctx__maybe_unused ) +{ +return str_hash ((const char *)key); +} -static struct hlist_head fncache_hash[FNHSIZE ]; +static bool fncache__equal (long key1,long key2,void *ctx__maybe_unused ) +{ +return strcmp ((const char *)key1, (const char *)key2) ==0 ; +} -unsigned shash (const unsigned char *s) +static void fncache__init (void ) { -unsigned h =0 ; -while (*s) - h =65599 * h + *s++; -return h ^ (h >>16 ); + fncache =hashmap__new (fncache__hash, fncache__equal,/*ctx=*/ NULL ); +} + +static struct hashmap *fncache__get (void ) +{ +static pthread_once_t fncache_once =PTHREAD_ONCE_INIT ; + +pthread_once (&fncache_once, fncache__init); + +return fncache; }static bool lookup_fncache (const char *name,bool *res) { -int h =shash ((const unsigned char *)name) %FNHSIZE ; -struct fncache *n; - -hlist_for_each_entry (n, &fncache_hash[h], nd) { -if (!strcmp (n->name, name)) { - *res = n->res; -return true; - } - } -return false; +long val; + +if (!hashmap__find (fncache__get (), name, &val)) +return false; + + *res = (val !=0 ); +return true; }static void update_fncache (const char *name,bool res) { -struct fncache *n =malloc (sizeof (struct fncache ) +strlen (name) +1 ); -int h =shash ((const unsigned char *)name) %FNHSIZE ; - -if (!n) -return ; -strcpy (n->name, name); - n->res = res; -hlist_add_head (&n->nd, &fncache_hash[h]); +char *old_key =NULL , *key =strdup (name); + +if (key) { +hashmap__set (fncache__get (), key, res, &old_key,/*old_value*/ NULL ); +free (old_key); + } }/* No LRU, only use when bounded in some other way. */
tools/perf/util/fncache.h +0 -1
@@ -1,7 +1,6 @@#ifndef _FCACHE_H#define _FCACHE_H 1 -unsigned shash (const unsigned char *s);bool file_available (const char *name);#endif
tools/perf/util/srccode.c +2 -2
@@ -16,7 +16,7 @@#include "srccode.h" #include "debug.h" #include <internal/lib.h> // page_size -#include "fncache.h" +#include "hashmap.h" #define MAXSRCCACHE (32*1024*1024)#define MAXSRCFILES 64
@@ -92,7 +92,7 @@ static struct srcfile *find_srcfile(char *fn)struct srcfile *h;int fd;unsigned long sz; -unsigned hval =shash ((unsigned char *)fn) %SRC_HTAB_SZ ; +size_t hval =str_hash (fn) %SRC_HTAB_SZ ; hlist_for_each_entry (h, &srcfile_htab[hval], hash_nd) {if (!strcmp (fn, h->fn)) {
Signature · 1 line
2.49.0.1045.g170613ef41-goog
Ian Rogers
reviewerPATCH v2 2/3 perf pmu: Change aliases from list to hashmap
In reply to Ian RogersFinding an alias for things like perf_pmu__have_event would need to search the aliases list, whilst this happens relatively infrequently it can be a significant overhead in testing. Switch to using a hashmap. Move common initialization code to perf_pmu__init. Refactor the test strct perf_pmu_test_pmu to not have perf pmu within it to better support the perf_pmu__init function.
Before:
``` $ time perf test "Parsing of PMU event table metrics" 10.3: Parsing of PMU event table metrics : Ok 10.4: Parsing of PMU event table metrics with fake PMUs : Ok real 0m13.287s user 0m13.026s sys 0m0.532s ```
After:
``` $ time perf test "Parsing of PMU event table metrics" 10.3: Parsing of PMU event table metrics : Ok 10.4: Parsing of PMU event table metrics with fake PMUs : Ok real 0m13.011s user 0m12.885s sys 0m0.485s ```
--- tools/perf/tests/pmu-events.c | 129 +++++++++++++------------- tools/perf/util/hwmon_pmu.c | 43 ++++----- tools/perf/util/pmu.c | 167 ++++++++++++++++++++++------------ tools/perf/util/pmu.h | 4 +- tools/perf/util/tool_pmu.c | 17 +--- 5 files changed, 199 insertions(+), 161 deletions(-)
tools/perf/tests/pmu-events.c +62 -67
@@ -38,7 +38,9 @@ struct perf_pmu_test_event { };struct perf_pmu_test_pmu { -struct perf_pmu pmu; +const char *pmu_name; +bool pmu_is_uncore; +const char *pmu_id;struct perf_pmu_test_event const *aliases[10 ]; };
@@ -553,11 +555,10 @@ static int __test_core_pmu_event_aliases(const char *pmu_name, int *count)if (!pmu)return -1 ; -INIT_LIST_HEAD (&pmu->format); -INIT_LIST_HEAD (&pmu->aliases); -INIT_LIST_HEAD (&pmu->caps); -INIT_LIST_HEAD (&pmu->list); - pmu->name =strdup (pmu_name); +if (perf_pmu__init (pmu,PERF_PMU_TYPE_FAKE , pmu_name) !=0 ) { +perf_pmu__delete (pmu); +return -1 ; + } pmu->is_core = true; pmu->events_table = table;
@@ -594,14 +595,30 @@ static int __test_uncore_pmu_event_aliases(struct perf_pmu_test_pmu *test_pmu) {int alias_count =0 , to_match_count =0 , matched_count =0 ;struct perf_pmu_test_event const **table; -struct perf_pmu *pmu = &test_pmu->pmu; -const char *pmu_name = pmu->name; +struct perf_pmu *pmu;const struct pmu_events_table *events_table;int res =0 ; events_table =find_core_events_table ("testarch" ,"testcpu" );if (!events_table)return -1 ; + + pmu =zalloc (sizeof (*pmu)); +if (!pmu) +return -1 ; + +if (perf_pmu__init (pmu,PERF_PMU_TYPE_FAKE , test_pmu->pmu_name) !=0 ) { +perf_pmu__delete (pmu); +return -1 ; + } + pmu->is_uncore = test_pmu->pmu_is_uncore; +if (test_pmu->pmu_id) { + pmu->id =strdup (test_pmu->pmu_id); +if (!pmu->id) { +perf_pmu__delete (pmu); +return -1 ; + } + } pmu->events_table = events_table;pmu_add_cpu_aliases_table (pmu, events_table); pmu->cpu_aliases_added = true;
@@ -617,7 +634,8 @@ static int __test_uncore_pmu_event_aliases(struct perf_pmu_test_pmu *test_pmu)if (alias_count != to_match_count) {pr_debug ("testing aliases uncore PMU %s: mismatch expected aliases (%d) vs found (%d)\n" , - pmu_name, to_match_count, alias_count); + pmu->name, to_match_count, alias_count); +perf_pmu__delete (pmu);return -1 ; }
@@ -630,9 +648,10 @@ static int __test_uncore_pmu_event_aliases(struct perf_pmu_test_pmu *test_pmu) .count = &matched_count, }; -if (strcmp (pmu_name, test_event.matching_pmu)) { +if (strcmp (pmu->name, test_event.matching_pmu)) {pr_debug ("testing aliases uncore PMU %s: mismatched matching_pmu, %s vs %s\n" , - pmu_name, test_event.matching_pmu, pmu_name); + pmu->name, test_event.matching_pmu, pmu->name); +perf_pmu__delete (pmu);return -1 ; }
@@ -641,34 +660,32 @@ static int __test_uncore_pmu_event_aliases(struct perf_pmu_test_pmu *test_pmu)if (err) { res = err;pr_debug ("testing aliases uncore PMU %s: could not match alias %s\n" , - pmu_name, event->name); + pmu->name, event->name); +perf_pmu__delete (pmu);return -1 ; } }if (alias_count != matched_count) {pr_debug ("testing aliases uncore PMU %s: mismatch found aliases (%d) vs matched (%d)\n" , - pmu_name, matched_count, alias_count); + pmu->name, matched_count, alias_count); res =-1 ; } +perf_pmu__delete (pmu);return res; }static struct perf_pmu_test_pmu test_pmus[] = { { - .pmu = { - .name ="hisi_sccl1_ddrc2" , - .is_uncore =1 , - }, + .pmu_name ="hisi_sccl1_ddrc2" , + .pmu_is_uncore =1 , .aliases = { &uncore_hisi_ddrc_flux_wcmd, }, }, { - .pmu = { - .name ="uncore_cbox_0" , - .is_uncore =1 , - }, + .pmu_name ="uncore_cbox_0" , + .pmu_is_uncore =1 , .aliases = { &unc_cbo_xsnp_response_miss_eviction, &uncore_hyphen,
@@ -676,88 +693,70 @@ static struct perf_pmu_test_pmu test_pmus[] = { }, }, { - .pmu = { - .name = "hisi_sccl3_l3c7", - .is_uncore = 1, - }, + .pmu_name = "hisi_sccl3_l3c7", + .pmu_is_uncore = 1, .aliases = { &uncore_hisi_l3c_rd_hit_cpipe, }, }, { - .pmu = { - .name = "uncore_imc_free_running_0", - .is_uncore = 1, - }, + .pmu_name = "uncore_imc_free_running_0", + .pmu_is_uncore = 1, .aliases = { &uncore_imc_free_running_cache_miss, }, }, { - .pmu = { - .name = "uncore_imc_0", - .is_uncore = 1, - }, + .pmu_name = "uncore_imc_0", + .pmu_is_uncore = 1, .aliases = { &uncore_imc_cache_hits, }, }, { - .pmu = { - .name = "uncore_sys_ddr_pmu0", - .is_uncore = 1, - .id = "v8", - }, + .pmu_name = "uncore_sys_ddr_pmu0", + .pmu_is_uncore = 1, + .pmu_id = "v8", .aliases = { &sys_ddr_pmu_write_cycles, }, }, { - .pmu = { - .name = "uncore_sys_ccn_pmu4", - .is_uncore = 1, - .id = "0x01", - }, + .pmu_name = "uncore_sys_ccn_pmu4", + .pmu_is_uncore = 1, + .pmu_id = "0x01", .aliases = { &sys_ccn_pmu_read_cycles, }, }, { - .pmu = { - .name = (char *)"uncore_sys_cmn_pmu0", - .is_uncore = 1, - .id = (char *)"43401", - }, + .pmu_name = "uncore_sys_cmn_pmu0", + .pmu_is_uncore = 1, + .pmu_id = "43401", .aliases = { &sys_cmn_pmu_hnf_cache_miss, }, }, { - .pmu = { - .name = (char *)"uncore_sys_cmn_pmu0", - .is_uncore = 1, - .id = (char *)"43602", - }, + .pmu_name = "uncore_sys_cmn_pmu0", + .pmu_is_uncore = 1, + .pmu_id = "43602", .aliases = { &sys_cmn_pmu_hnf_cache_miss, }, }, { - .pmu = { - .name = (char *)"uncore_sys_cmn_pmu0", - .is_uncore = 1, - .id = (char *)"43c03", - }, + .pmu_name = "uncore_sys_cmn_pmu0", + .pmu_is_uncore = 1, + .pmu_id = "43c03", .aliases = { &sys_cmn_pmu_hnf_cache_miss, }, }, { - .pmu = { - .name = (char *)"uncore_sys_cmn_pmu0", - .is_uncore = 1, - .id = (char *)"43a01", - }, + .pmu_name = "uncore_sys_cmn_pmu0", + .pmu_is_uncore = 1, + .pmu_id = "43a01", .aliases = { &sys_cmn_pmu_hnf_cache_miss, },
@@ -796,10 +795,6 @@ static int test__aliases(struct test_suite *test __maybe_unused,for (i =0 ; i <ARRAY_SIZE (test_pmus); i++) {int res; -INIT_LIST_HEAD (&test_pmus[i].pmu.format); -INIT_LIST_HEAD (&test_pmus[i].pmu.aliases); -INIT_LIST_HEAD (&test_pmus[i].pmu.caps); - res =__test_uncore_pmu_event_aliases (&test_pmus[i]);if (res)return res;
tools/perf/util/hwmon_pmu.c +22 -21
64 lines not on this page · raw message
tools/perf/util/pmu.c +107 -60
295 lines not on this page · raw message
tools/perf/util/pmu.h +3 -1
@@ -14,6 +14,7 @@#include "mem-events.h" struct evsel_config_term ; +struct hashmap ;struct perf_cpu_map ;struct print_callbacks ;
@@ -125,7 +126,7 @@ struct perf_pmu {* event read from <sysfs>/bus/event_source/devices/<name>/events/ or * from json events in pmu-events.c. */ -struct list_head aliases; +struct hashmap *aliases;/** * @events_table: The events table for json events in pmu-events.c. */
@@ -294,6 +295,7 @@ int perf_pmu__pathname_scnprintf(char *buf, size_t size,int perf_pmu__event_source_devices_fd (void );int perf_pmu__pathname_fd (int dirfd,const char *pmu_name,const char *filename,int flags); +int perf_pmu__init (struct perf_pmu *pmu,__u32 type,const char *name);struct perf_pmu *perf_pmu__lookup (struct list_head *pmus,int dirfd,const char *lookup_name,bool eager_load);struct perf_pmu *perf_pmu__create_placeholder_core_pmu (struct list_head *core_pmus);
tools/perf/util/tool_pmu.c +5 -12
@@ -502,19 +502,12 @@ struct perf_pmu *tool_pmu__new(void)struct perf_pmu *tool =zalloc (sizeof (struct perf_pmu ));if (!tool) - goto out; - tool->name =strdup ("tool" ); -if (!tool->name) { -zfree (&tool); - goto out; - } +return NULL ; - tool->type =PERF_PMU_TYPE_TOOL ; -INIT_LIST_HEAD (&tool->aliases); -INIT_LIST_HEAD (&tool->caps); -INIT_LIST_HEAD (&tool->format); +if (perf_pmu__init (tool,PERF_PMU_TYPE_TOOL ,"tool" ) !=0 ) { +perf_pmu__delete (tool); +return NULL ; + } tool->events_table =find_core_events_table ("common" ,"common" ); - -out:return tool; }
Signature · 1 line
2.49.0.1045.g170613ef41-goog
Ian Rogers
reviewerPATCH v2 3/3 perf metricgroup: Binary search when resolving referred to metrics
In reply to Ian RogersUnlike with events, metrics can be matched by name or a list of metric groups. However, when a metric refers to another metric it isn't referring to a group but the singular metric in question. Prior to this change every "id" in a metric expression is checked to see if it is a metric by scanning all the metrics in the metrics table. As the table is sorted my metric name we can speed the search in the resolution case by binary searching for the metric.
Rename some of the metricgroup functions to make it clearer whether they match a metric by name or by both name and group.
Before:
``` $ time perf test -v 10 10: PMU JSON event tests : 10.1: PMU event table sanity : Ok 10.2: PMU event map aliases : Ok 10.3: Parsing of PMU event table metrics : Ok 10.4: Parsing of PMU event table metrics with fake PMUs : Ok 10.5: Parsing of metric thresholds with fake PMUs : Ok real 0m15.972s user 0m13.176s sys 0m3.001s ```
After:
``` $ time perf test -v 10 10: PMU JSON event tests : 10.1: PMU event table sanity : Ok 10.2: PMU event map aliases : Ok 10.3: Parsing of PMU event table metrics : Ok 10.4: Parsing of PMU event table metrics with fake PMUs : Ok 10.5: Parsing of metric thresholds with fake PMUs : Ok real 0m5.343s user 0m1.871s sys 0m2.128s ```
--- tools/perf/builtin-stat.c | 6 +- tools/perf/pmu-events/empty-pmu-events.c | 66 ++++++++++++++- tools/perf/pmu-events/jevents.py | 66 ++++++++++++++- tools/perf/pmu-events/pmu-events.h | 23 +++-- tools/perf/util/metricgroup.c | 102 +++++++++-------------- tools/perf/util/metricgroup.h | 2 +- 6 files changed, 192 insertions(+), 73 deletions(-)
tools/perf/builtin-stat.c +3 -3
@@ -1854,7 +1854,7 @@ static int add_default_events(void)* will use this approach. To determine transaction support * on an architecture test for such a metric name. */ -if (!metricgroup__has_metric (pmu,"transaction" )) { +if (!metricgroup__has_metric_or_groups (pmu,"transaction" )) {pr_err ("Missing transaction metrics\n" ); ret =-1 ; goto out;
@@ -1888,7 +1888,7 @@ static int add_default_events(void) smi_reset = true; } -if (!metricgroup__has_metric (pmu,"smi" )) { +if (!metricgroup__has_metric_or_groups (pmu,"smi" )) {pr_err ("Missing smi metrics\n" ); ret =-1 ; goto out;
@@ -1978,7 +1978,7 @@ static int add_default_events(void)* Add TopdownL1 metrics if they exist. To minimize * multiplexing, don't request threshold computation. */ -if (metricgroup__has_metric (pmu,"Default" )) { +if (metricgroup__has_metric_or_groups (pmu,"Default" )) {struct evlist *metric_evlist =evlist__new ();if (!metric_evlist) {
tools/perf/pmu-events/empty-pmu-events.c +65 -1
84 lines not on this page · raw message
tools/perf/pmu-events/jevents.py +65 -1
84 lines not on this page · raw message
tools/perf/pmu-events/pmu-events.h +18 -5
@@ -74,6 +74,7 @@ struct pmu_events_table;struct pmu_metrics_table ;#define PMU_EVENTS__NOT_FOUND -1000 +#define PMU_METRICS__NOT_FOUND -1000 typedef int (*pmu_event_iter_fn)(const struct pmu_event *pe, const struct pmu_events_table *table,
@@ -88,11 +89,11 @@ int pmu_events_table__for_each_event(const struct pmu_events_table *table,pmu_event_iter_fn fn, void *data);/* -* Search for table and entry matching with pmu__name_match. Each matching event -* has fn called on it. 0 implies to success/continue the search while non-zero -* means to terminate. The special value PMU_EVENTS__NOT_FOUND is used to -* indicate no event was found in one of the tables which doesn't terminate the -* search of all tables. +* Search for a table and entry matching with pmu__name_wildcard_match or any +* tables if pmu is NULL. Each matching event has fn called on it. 0 implies to +* success/continue the search while non-zero means to terminate. The special +* value PMU_EVENTS__NOT_FOUND is used to indicate no event was found in one of +* the tables which doesn't terminate the search of all tables. */ int pmu_events_table__find_event(const struct pmu_events_table *table, struct perf_pmu *pmu,
@@ -104,6 +105,18 @@ size_t pmu_events_table__num_events(const struct pmu_events_table *table,int pmu_metrics_table__for_each_metric (const struct pmu_metrics_table *table,pmu_metric_iter_fn fn,void *data); +/* +* Search for a table and entry matching with pmu__name_wildcard_match or any +* tables if pmu is NULL. Each matching metric has fn called on it. 0 implies to +* success/continue the search while non-zero means to terminate. The special +* value PMU_METRICS__NOT_FOUND is used to indicate no metric was found in one +* of the tables which doesn't terminate the search of all tables. +*/ +int pmu_metrics_table__find_metric (const struct pmu_metrics_table *table, +struct perf_pmu *pmu, +const char *metric, +pmu_metric_iter_fn fn, +void *data);const struct pmu_events_table *perf_pmu__find_events_table (struct perf_pmu *pmu);const struct pmu_metrics_table *pmu_metrics_table__find (void );
tools/perf/util/metricgroup.c +40 -62
192 lines not on this page · raw message
tools/perf/util/metricgroup.h +1 -1
@@ -85,7 +85,7 @@ int metricgroup__parse_groups_test(struct evlist *evlist, struct rblist *metric_events);void metricgroup__print (const struct print_callbacks *print_cb,void *print_state); -bool metricgroup__has_metric (const char *pmu,const char *metric); +bool metricgroup__has_metric_or_groups (const char *pmu,const char *metric_or_groups);unsigned int metricgroups__topdown_max_level (void );int arch_get_runtimeparam (const struct pmu_metric *pm);void metricgroup__rblist_exit (struct rblist *metric_events);
Signature · 1 line
2.49.0.1045.g170613ef41-goog