From Cristian Constantin:

while caching the last element from the conversation hash chain lists speeds-up
the operation when the hash/chain lists are actually built, it 
does NOT help a lot when a certain random conversation which is in the hash
table is looked-up.

I did some profiling and tracing and I saw that a lot of cpu time is spent in
the function conversation_lookup_hashtable() when wireshark
is asked to show the "Flow Graph", "TCP Conversations", "Voip Calls".  I used
two types of captures with over 500k packets:

- tcp packets having the _same_ src ip addr, src tcp port, dst ip addr, dst tcp 
  port
- (mostly) sip packets containing sdp payloads which advertise the _same_ ip
  addr, udp port for media

these types of captures lead to _huge_ chain lists behind the same hash bucket 
(to which the conversation is actually mapped)

the solution would be to cache the last found conversation into the head of the 
chain list and to use it whenever it is possible; most of the time the look-up
will be in O(1) instead of O(n) (n - number
of elements in the list).

https://bugs.wireshark.org/bugzilla/show_bug.cgi?id=7149

svn path=/trunk/; revision=42141

2 files changed, 8 insertions, 1 deletions

diff --git a/epan/conversation.c b/epan/conversation.c
index 55e8cd8917..f1a13f771a 100644
--- a/epan/conversation.c
+++ b/epan/conversation.c
@@ -640,6 +640,7 @@ conversation_new(const guint32 setup_frame, const address *addr1, const address
 	new_key->port2 = port2;
 
 	conversation = se_alloc(sizeof(conversation_t)); 
+	memset(conversation, 0, sizeof(conversation_t));
 
 	conversation->index = new_index;
 	conversation->setup_frame = setup_frame;
@@ -729,6 +730,7 @@ conversation_lookup_hashtable(GHashTable *hashtable, const guint32 frame_num, co
 {
 	conversation_t* conversation=NULL;
 	conversation_t* match=NULL;
+	conversation_t* chain_head=NULL;
 	conversation_key key;
 	guint found=0;
 
@@ -742,7 +744,7 @@ conversation_lookup_hashtable(GHashTable *hashtable, const guint32 frame_num, co
 	key.port1 = port1;
 	key.port2 = port2;
 
-	match = g_hash_table_lookup(hashtable, &key);
+	chain_head = (match = g_hash_table_lookup(hashtable, &key));
 		
 	if (match && (match->setup_frame > frame_num))
 		match = NULL;
@@ -750,10 +752,13 @@ conversation_lookup_hashtable(GHashTable *hashtable, const guint32 frame_num, co
 	if (match) {
 		if((match->last)&&(match->last->setup_frame<=frame_num))
 			return match->last;
+		if((match->latest_found)&&(match->latest_found->setup_frame<=frame_num))
+			return match->latest_found;
 		for (conversation = match->next; conversation; conversation = conversation->next) {
 			if ((conversation->setup_frame <= frame_num)
 				&& (conversation->setup_frame > match->setup_frame)) {
 					match = conversation;
+					chain_head->latest_found = conversation;
 					found=1;
 			} else if(conversation->setup_frame>frame_num)
 				/* we are past the frame_num */
diff --git a/epan/conversation.h b/epan/conversation.h
index f7a0f38dd3..9d46525d48 100644
--- a/epan/conversation.h
+++ b/epan/conversation.h
@@ -72,6 +72,8 @@ typedef struct conversation_key {
 typedef struct conversation {
 	struct conversation *next;	/** pointer to next conversation on hash chain */
 	struct conversation *last;	/** pointer to the last conversation on hash chain */
+	struct conversation *latest_found;
+								/** pointer to the last conversation on hash chain */
 	guint32	index;				/** unique ID for conversation */
 	guint32 setup_frame;		/** frame number that setup this conversation */
 	GSList *data_list;			/** list of data associated with conversation */