* [lttng-dev] [RFC PATCH lttng-ust] Introduce hash table for lttng_create_event_if_missing()
@ 2013-01-16 21:37 Anik Mishra
2013-01-21 19:06 ` Mathieu Desnoyers
0 siblings, 1 reply; 6+ messages in thread
From: Anik Mishra @ 2013-01-16 21:37 UTC (permalink / raw)
-----Original Message-----
From: Mathieu Desnoyers [mailto:mathieu.desnoyers@efficios.com]
Sent: January-16-13 10:15 AM
To: lttng-dev at lists.lttng.org
Subject: [lttng-dev] [RFC PATCH lttng-ust] Introduce hash table for lttng_create_event_if_missing()
[...]
@@ -329,17 +331,19 @@ int lttng_event_create(const struct lttng_event_desc *desc, {
[...]
- /*
- * 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) {
[...]
From other code:
#define LTTNG_UST_EVENT_HT_BITS 6
#define LTTNG_UST_EVENT_HT_SIZE (1U << LTTNG_UST_EVENT_HT_BITS)
The way I read this, if there's a substantial number of events, you're just dividing the time required by a constant 64. The complexity remains the same. Are you sure this is really a long term solution?
Anik
^ permalink raw reply [flat|nested] 6+ messages in thread
* [lttng-dev] [RFC PATCH lttng-ust] Introduce hash table for lttng_create_event_if_missing()
2013-01-16 21:37 [lttng-dev] [RFC PATCH lttng-ust] Introduce hash table for lttng_create_event_if_missing() Anik Mishra
@ 2013-01-21 19:06 ` Mathieu Desnoyers
0 siblings, 0 replies; 6+ messages in thread
From: Mathieu Desnoyers @ 2013-01-21 19:06 UTC (permalink / raw)
* Anik Mishra (anik.mishra at ericsson.com) wrote:
> -----Original Message-----
> From: Mathieu Desnoyers [mailto:mathieu.desnoyers@efficios.com]
> Sent: January-16-13 10:15 AM
> To: lttng-dev at lists.lttng.org
> Subject: [lttng-dev] [RFC PATCH lttng-ust] Introduce hash table for lttng_create_event_if_missing()
>
> [...]
> @@ -329,17 +331,19 @@ int lttng_event_create(const struct lttng_event_desc *desc, {
> [...]
> - /*
> - * 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) {
> [...]
>
> From other code:
> #define LTTNG_UST_EVENT_HT_BITS 6
> #define LTTNG_UST_EVENT_HT_SIZE (1U << LTTNG_UST_EVENT_HT_BITS)
>
> The way I read this, if there's a substantial number of events,
> you're just dividing the time required by a constant 64. The
> complexity remains the same. Are you sure this is really a long term
> solution?
If we have much more than 10k _different_ TRACEPOINT_EVENT in the code,
we'll probably have other issues to fix.
Thanks,
Mathieu
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 6+ messages in thread
* [lttng-dev] [RFC PATCH lttng-ust] Introduce hash table for lttng_create_event_if_missing()
2013-01-16 16:19 ` Christian Babeux
@ 2013-01-16 17:58 ` Mathieu Desnoyers
0 siblings, 0 replies; 6+ messages in thread
From: Mathieu Desnoyers @ 2013-01-16 17:58 UTC (permalink / raw)
* 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 <christian.babeux at efficios.com>
>
> On Wed, Jan 16, 2013 at 10:14 AM, Mathieu Desnoyers
> <mathieu.desnoyers at efficios.com> 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 <mathieu.desnoyers at efficios.com>
> > ---
> > 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
^ permalink raw reply [flat|nested] 6+ messages in thread
* [lttng-dev] [RFC PATCH lttng-ust] Introduce hash table for lttng_create_event_if_missing()
2013-01-16 15:14 Mathieu Desnoyers
2013-01-16 15:53 ` David Goulet
@ 2013-01-16 16:19 ` Christian Babeux
2013-01-16 17:58 ` Mathieu Desnoyers
1 sibling, 1 reply; 6+ messages in thread
From: Christian Babeux @ 2013-01-16 16:19 UTC (permalink / raw)
I was able to reproduce this overhead issue on my machine.
This patch fixed it.
Acked-by: Christian Babeux <christian.babeux at efficios.com>
On Wed, Jan 16, 2013 at 10:14 AM, Mathieu Desnoyers
<mathieu.desnoyers at efficios.com> 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 <mathieu.desnoyers at efficios.com>
> ---
> 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
^ permalink raw reply [flat|nested] 6+ messages in thread
* [lttng-dev] [RFC PATCH lttng-ust] Introduce hash table for lttng_create_event_if_missing()
2013-01-16 15:14 Mathieu Desnoyers
@ 2013-01-16 15:53 ` David Goulet
2013-01-16 16:19 ` Christian Babeux
1 sibling, 0 replies; 6+ messages in thread
From: David Goulet @ 2013-01-16 15:53 UTC (permalink / raw)
Acked-by: David Goulet <dgoulet at efficios.com>
Mathieu Desnoyers:
> 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 <mathieu.desnoyers at efficios.com>
> ---
> 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;
> }
>
^ permalink raw reply [flat|nested] 6+ messages in thread
* [lttng-dev] [RFC PATCH lttng-ust] Introduce hash table for lttng_create_event_if_missing()
@ 2013-01-16 15:14 Mathieu Desnoyers
2013-01-16 15:53 ` David Goulet
2013-01-16 16:19 ` Christian Babeux
0 siblings, 2 replies; 6+ messages in thread
From: Mathieu Desnoyers @ 2013-01-16 15:14 UTC (permalink / raw)
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 <mathieu.desnoyers at efficios.com>
---
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
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2013-01-21 19:06 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-01-16 21:37 [lttng-dev] [RFC PATCH lttng-ust] Introduce hash table for lttng_create_event_if_missing() Anik Mishra
2013-01-21 19:06 ` Mathieu Desnoyers
-- strict thread matches above, loose matches on Subject: below --
2013-01-16 15:14 Mathieu Desnoyers
2013-01-16 15:53 ` David Goulet
2013-01-16 16:19 ` Christian Babeux
2013-01-16 17:58 ` Mathieu Desnoyers
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox