/pidgin/main: e198bddf2ef9: Trie: lower memory usage for smaller...

[Tomasz Wasilczyk]

Changeset: e198bddf2ef981f731384fd67b3112c7176a981a
Author:	 Tomasz Wasilczyk <twasilczyk at pidgin.im>
Date:	 2014-03-27 18:14 +0100
Branch:	 default
URL: https://hg.pidgin.im/pidgin/main/rev/e198bddf2ef9

Description:

Trie: lower memory usage for smaller collections

diffstat:

 libpurple/trie.c |  24 ++++++++++++++++++++++--
 1 files changed, 22 insertions(+), 2 deletions(-)

diffs (62 lines):

diff --git a/libpurple/trie.c b/libpurple/trie.c
--- a/libpurple/trie.c
+++ b/libpurple/trie.c
@@ -30,7 +30,17 @@
 #define PURPLE_TRIE_GET_PRIVATE(obj) \
 	(G_TYPE_INSTANCE_GET_PRIVATE((obj), PURPLE_TYPE_TRIE, PurpleTriePrivate))
 
-#define PURPLE_TRIE_STATES_POOL_BLOCK_SIZE 102400
+/* A single internal (that don't have any children) consists
+ * of 256 + 4 pointers. That's 1040 bytes on 32-bit machine or 2080 bytes
+ * on 64-bit.
+ *
+ * Thus, in 10500-byte pool block we can hold about 5-10 internal states.
+ * Threshold of 100 states means, we'd need 10-20 "small" blocks before
+ * switching to ~1-2 large blocks.
+ */
+#define PURPLE_TRIE_LARGE_THRESHOLD 100
+#define PURPLE_TRIE_STATES_SMALL_POOL_BLOCK_SIZE 10880
+#define PURPLE_TRIE_STATES_LARGE_POOL_BLOCK_SIZE 102400
 
 typedef struct _PurpleTrieRecord PurpleTrieRecord;
 typedef struct _PurpleTrieState PurpleTrieState;
@@ -43,6 +53,7 @@ typedef struct
 	PurpleMemoryPool *records_str_mempool;
 	PurpleMemoryPool *records_obj_mempool;
 	PurpleTrieRecordList *records;
+	gsize records_total_size;
 
 	PurpleMemoryPool *states_mempool;
 	PurpleTrieState *root_state;
@@ -271,6 +282,14 @@ purple_trie_states_build(PurpleTrie *tri
 	if (priv->root_state != NULL)
 		return TRUE;
 
+	if (priv->records_total_size < PURPLE_TRIE_LARGE_THRESHOLD) {
+		purple_memory_pool_set_block_size(priv->states_mempool,
+			PURPLE_TRIE_STATES_SMALL_POOL_BLOCK_SIZE);
+	} else {
+		purple_memory_pool_set_block_size(priv->states_mempool,
+			PURPLE_TRIE_STATES_LARGE_POOL_BLOCK_SIZE);
+	}
+
 	priv->root_state = root = purple_trie_state_new(trie, NULL, '\0');
 	g_return_val_if_fail(root != NULL, FALSE);
 	g_assert(root->longest_suffix == NULL);
@@ -554,6 +573,7 @@ purple_trie_add(PurpleTrie *trie, const 
 	g_assert(rec->word_len > 0);
 	rec->data = data;
 
+	priv->records_total_size += rec->word_len;
 	priv->records = purple_record_list_prepend(priv->records_obj_mempool,
 		priv->records, rec);
 }
@@ -613,7 +633,7 @@ purple_trie_init(GTypeInstance *instance
 	priv->records_str_mempool = purple_memory_pool_new();
 	priv->states_mempool = purple_memory_pool_new();
 	purple_memory_pool_set_block_size(priv->states_mempool,
-		PURPLE_TRIE_STATES_POOL_BLOCK_SIZE);
+		PURPLE_TRIE_STATES_SMALL_POOL_BLOCK_SIZE);
 }
 
 static void