From mboxrd@z Thu Jan 1 00:00:00 1970 From: mathieu.desnoyers@efficios.com (Mathieu Desnoyers) Date: Wed, 16 Jan 2013 12:58:44 -0500 Subject: [lttng-dev] [RFC PATCH lttng-ust] Introduce hash table for lttng_create_event_if_missing() In-Reply-To: References: <20130116151446.GA11082@Krystal> Message-ID: <20130116175844.GA13272@Krystal> * Christian Babeux (christian.babeux at efficios.com) wrote: > I was able to reproduce this overhead issue on my machine. > This patch fixed it. OK! Patch pushed into lttng-ust master and stable-2.1 branches. Thanks, Mathieu > > Acked-by: Christian Babeux > > On Wed, Jan 16, 2013 at 10:14 AM, Mathieu Desnoyers > wrote: > > lttng_create_event_if_missing() takes a lot of CPU time with stress-test > > applications containing 1000 different TRACEPOINT_EVENT() and 1000 > > individual tracepoint() call-site. > > > > With tracing disabled: > > > > time ./AppWith1000_lines_TP 0 > > > > real 0m2.487s > > user 0m2.424s > > sys 0m0.000s > > > > > > Introducing this hash table cuts the overhead very significantly when > > tracing is enabled: > > > > Before patch: > > > > 72.16% AppWith1000_lin liblttng-ust.so.0.0.0 [.] lttng_create_event_if_missing > > 25.64% AppWith1000_lin AppWith1000_lines_TP [.] a(int) > > > > time ./AppWith1000_lines_TP 0 > > > > real 0m7.946s > > user 0m7.864s > > sys 0m0.000s > > > > > > After patch: > > > > 89.13% AppWith1000_lin AppWith1000_lines_TP [.] a(int) > > 3.30% AppWith1000_lin liblttng-ust.so.0.0.0 [.] lttng_create_event_if_missing > > > > time ./AppWith1000_lines_TP 0 > > > > real 0m2.762s > > user 0m2.692s > > sys 0m0.004s > > > > Signed-off-by: Mathieu Desnoyers > > --- > > diff --git a/include/lttng/ust-events.h b/include/lttng/ust-events.h > > index 095fb1e..1db8e58 100644 > > --- a/include/lttng/ust-events.h > > +++ b/include/lttng/ust-events.h > > @@ -362,6 +362,7 @@ struct lttng_event { > > int has_enablers_without_bytecode; > > /* Backward references: list of lttng_enabler_ref (ref to enablers) */ > > struct cds_list_head enablers_ref_head; > > + struct cds_hlist_node hlist; /* session ht of events */ > > }; > > > > struct channel; > > @@ -467,6 +468,7 @@ struct lttng_session { > > /* New UST 2.1 */ > > /* List of enablers */ > > struct cds_list_head enablers_head; > > + struct lttng_ust_event_ht events_ht; /* ht of events */ > > }; > > > > struct lttng_transport { > > diff --git a/liblttng-ust/lttng-events.c b/liblttng-ust/lttng-events.c > > index 5e6c90c..f70c65f 100644 > > --- a/liblttng-ust/lttng-events.c > > +++ b/liblttng-ust/lttng-events.c > > @@ -127,7 +127,7 @@ void synchronize_trace(void) > > struct lttng_session *lttng_session_create(void) > > { > > struct lttng_session *session; > > - int ret; > > + int ret, i; > > > > session = zmalloc(sizeof(struct lttng_session)); > > if (!session) > > @@ -135,6 +135,8 @@ struct lttng_session *lttng_session_create(void) > > CDS_INIT_LIST_HEAD(&session->chan_head); > > CDS_INIT_LIST_HEAD(&session->events_head); > > CDS_INIT_LIST_HEAD(&session->enablers_head); > > + for (i = 0; i < LTTNG_UST_EVENT_HT_SIZE; i++) > > + CDS_INIT_HLIST_HEAD(&session->events_ht.table[i]); > > ret = lttng_ust_uuid_generate(session->uuid); > > if (ret != 0) { > > session->uuid[0] = '\0'; > > @@ -329,17 +331,19 @@ int lttng_event_create(const struct lttng_event_desc *desc, > > { > > const char *event_name = desc->name; > > struct lttng_event *event; > > + struct cds_hlist_head *head; > > + struct cds_hlist_node *node; > > int ret = 0; > > + size_t name_len = strlen(event_name); > > + uint32_t hash; > > > > if (chan->used_event_id == -1U) { > > ret = -ENOMEM; > > goto full; > > } > > - /* > > - * This is O(n^2) (for each event, the loop is called at event > > - * creation). Might require a hash if we have lots of events. > > - */ > > - cds_list_for_each_entry(event, &chan->session->events_head, node) { > > + hash = jhash(event_name, name_len, 0); > > + head = &chan->session->events_ht.table[hash & (LTTNG_UST_EVENT_HT_SIZE - 1)]; > > + cds_hlist_for_each_entry(event, node, head, hlist) { > > assert(event->desc); > > if (!strncmp(event->desc->name, > > desc->name, > > @@ -380,6 +384,7 @@ int lttng_event_create(const struct lttng_event_desc *desc, > > if (ret) > > goto statedump_error; > > cds_list_add(&event->node, &chan->session->events_head); > > + cds_hlist_add_head(&event->hlist, head); > > return 0; > > > > statedump_error: > > @@ -499,17 +504,24 @@ void lttng_create_event_if_missing(struct lttng_enabler *enabler) > > cds_list_for_each_entry(probe_desc, probe_list, head) { > > for (i = 0; i < probe_desc->nr_events; i++) { > > int found = 0, ret; > > + struct cds_hlist_head *head; > > + struct cds_hlist_node *node; > > + const char *event_name; > > + size_t name_len; > > + uint32_t hash; > > > > desc = probe_desc->event_desc[i]; > > if (!lttng_desc_match_enabler(desc, enabler)) > > continue; > > + event_name = desc->name; > > + name_len = strlen(event_name); > > > > /* > > - * For each event in session event list, > > - * check if already created. > > + * Check if already created. > > */ > > - cds_list_for_each_entry(event, > > - &session->events_head, node) { > > + hash = jhash(event_name, name_len, 0); > > + head = &session->events_ht.table[hash & (LTTNG_UST_EVENT_HT_SIZE - 1)]; > > + cds_hlist_for_each_entry(event, node, head, hlist) { > > if (event->desc == desc) > > found = 1; > > } > > > > -- > > Mathieu Desnoyers > > EfficiOS Inc. > > http://www.efficios.com > > > > _______________________________________________ > > lttng-dev mailing list > > lttng-dev at lists.lttng.org > > http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com