From mboxrd@z Thu Jan  1 00:00:00 1970
From: anik.mishra@ericsson.com (Anik Mishra)
Date: Wed, 16 Jan 2013 21:37:32 +0000
Subject: [lttng-dev] [RFC PATCH lttng-ust] Introduce hash table for
 lttng_create_event_if_missing()
Message-ID: <0AF7BA51953555439020FD85D854801F039A5D@eusaamb105.ericsson.se>

-----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