Optimizing Memory Usage
Date: 7/4/2005
It occured to me the other day that Scribe has definately lost some of that "lightweight" character that it used to have. In fact it was down right scary when I looked at the memory usage the other day after Scribe had been running for a few hours and it was 110mb. What the? Huh?

After I calmed down I decided to get to the bottom of it. For starters I did a leak test, and fixed every damn leak. But still the memory usage would rocket up to around 100mb. But it'd do that after the first receive. Alright what gets loaded during a mail receive? The bayesian spam word tables... bugger. Well they are only a few MB on disk, why are they adding 60mb to my memory image?

Good question.

So firstly I looked at the hash table sizes, and lo and behold they were much larger than needed because some of the word counts were way out which put off the preallocation of hash table space. Fixed that. But still quite a lot of memory was unaccounted for.

One thing that bothered me about the hash table implementation I'm using is that it does an allocation for each value stored to hold the key name (a string). On a small table it's no big deal but on a hash table of half a million entries it really hurts, both in allocation / free time overhead, and the extra memory being used to track all those blocks. As a side effect of the extra time spent freeing 500k blocks of memory you risk slowing the program to a halt for minutes on end if that memory has been swapped out to disk. I'm assumed the memory manager wants to "touch" each peice of memory it free's, which means swapping all those 500k bits of memory into physical ram just to free it. Nasty nasty nasty.

So I've given the hash table the option of using a string pool. Which works by doing one big allocation and putting lots of strings end to end inside it. This has 2 very important features, firstly it's very fast to allocate and free, secondly it doesn't require swapping vast amounts of memory into physical ram to free.

The downside of course is that if you delete a key in the hash table it leaves a hole in the string pool's memory, which is wasted space. But for a large static hash table it's perfect.

Now, in doing all this work I decide to keep track of the numbers involved to find the optimal values for hash table size, and the effect it has on the overall memory usage. Check it out:

Table Size Allocs (MB) Load Time (s) VM Size (KB)
x2 16.08 35 79672
x2.5 18.60 10 82252
x3 21.13 13 84844
x4 26.19 4 90024
After adding string pooling:
x2 16.08 20 38124
x2.5 18.60 5 40720
x3 21.13 7 43304
x4 26.19 1.3 48484

The hash table is preallocated to a multiple of the number of words it has to store, thats the first column. After the string pooling optimization the memory image is drastically smaller due to the overhead of maintain 500k blocks being gone.

I've settled on a multiplier of 2.5 because it seems to have the best memory/speed trade off. For reference Scribe is using about 20000kb without the word lists loaded, in debug mode. So it's getting close to just the data for the strings and hash table's, with little or no overhead.

I think there are better solutions yet, but they take a lot of coding and testing. So I'll leave them for another day. I like the idea of using a tree structure for the word lists to avoid duplicate storage of letters... e.g. if there are 1000 words starting with 'a' then it should be possible to store all of them in a container marked 'a' and store just the rest of the string minus the 'a'. Saving more memory. But thats an idea for later.
07/04/2005 11:17pm
Interesting. I wish it wasn't just a little over my head, but interesting nonetheless. There's nothing like an engaging problem to suck away your time, is there?
09/04/2005 9:01am
My head is a little too low too for all this, but then again, one learns every day. It's interesting though to read how Scribe is developing.
12/04/2005 11:37am
Nice work, Matt. I love this part of the development cycle where you can make something run faster with a little bit of time and effort. The desire to optimise and refactor is the difference between mass-produced software and well-produced software.
(Great write up too)

Email (optional): (Will be HTML encoded to evade harvesting)
Remember username and/or email in a cookie.
Notify me of new posts in this thread via email.