I'm Not Too Bright

Spot the insanity:


struct WordTreeNode
{
bool IsWord;
StringBuilder Word;
DynamicArray Nodes;
DynamicArray UsedNodes;
int UsedNodeCount;

WordTreeNode();
~WordTreeNode();
};

...

WordTreeNode::WordTreeNode() : IsWord(false), Nodes(26), UsedNodes(26)
{
...
}

void WordList::AddWordToTree(const StringBuilder& word, const StringBuilder& fullWord, WordTreeNode* node, int letterIdx)
{
WordTreeNode* currentNode = node;
for (uint32 i = 0; i < word.Length(); ++i)
{
char letter = word;

int idx = letter - 'A';
if (currentNode->Nodes[idx] == NULL)
{
currentNode->Nodes[idx] = new WordTreeNode();
currentNode->UsedNodes[currentNode->UsedNodeCount++] = idx;
}

currentNode = currentNode->Nodes[idx];
}

currentNode->IsWord = true;
currentNode->Word = fullWord;
}



Answer:
If you said, "you're using your own containers instead of STL!," sorry, but that's not it. This code was written before the Android NDK had full STL support. Writing my own containers was (at the time) a necessity.

The answer is that I'm using *way* too much memory.

Here are some raw numbers:
About 160,000 of these WordTreeNodes get created and stored in memory for my word tree.

Which means that, assuming 4-byte integers, for UsedNodeCount we're using 160,000 * 4 = 640,000 bytes (~640 K).
Worse yet is UsedNodes, which is 160,000 * 26 * 4 = 16,640,000 (~16MB !!)

Solving this is painfully simple.

We can cut out UsedNodeCount entirely and just use the Size() method for UsedNodes, which drops that bit of memory.
Further, we can change UsedNodes to use uint8 instead of int, cutting out essentially 3 bytes per element, or 12.5 MB.

We can also take this a step further and only make UsedNodes as big as it needs to be instead of having a constant size of 26. I'm not doing this right now for speed reasons (trying to keep loading time fast), but... writing a quick test app here, I would be saving about:

4 MB.

The same operation can be applied to Nodes, reclaiming about another 4 MB.

Thus, after fixing some incredibly stupid mistakes of mine, I can reclaim over 20 MB of memory. This is a *big deal* for an iPhone app.