[lttng-dev] [RFC PATCH lttng-ust] Introduce hash table for lttng_create_event_if_missing()

[Anik Mishra]

-----Original Message-----
From: Mathieu Desnoyers [mailto:mathieu.desnoyers at 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