• entries
25
39
• views
47079

# I'm Not Too Bright

952 views

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;}

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.

Nice job!

Two thoughts:
1) Are you sure 8-bit is enough? You are 100% absolutely certain that a node will not be used by more than 255 times? Is that, "It almost certainly probably wont happen except in weird cases" certainty, or is it "It's literally impossible to happen" certainty? If the former (merely 'improbable' not 'impossible') consider adding a safety check in the unlikely chance you hit 250 - in case something goes wrong, it'll be much easier to debug.

2) Are you currently sharing the words/strings themselves if they are similar (I can't entirely tell from that code)? If there's a strong likelihood of some words being identical, you might consider using flyweight to conserve more space. Boost::flyweight, if you can get it to work on Android and iPhone, might save even more space (or it could waste more space, depending on the situations where you use it). Ofcourse, if you've already saved enough space, there's no point in optimizing further unnecessarily.

(1) UsedNodes is storing ASCII letters in the range 0-25 (only upper-case letters, converted to fall in that range), so there's definitely no chance I'll have an overflow. Further, UsedNodes is tracking uniquely used letters for a node, so the size of the array will also never exceed 26. You scared me for a moment and I put in some sanity checks just to be sure, but yea, I'm 100% on this. :-)

(2) The word list has already been scrubbed for uniqueness, so there are definitely no duplicates. There are instances where I return a lot of words from the list, but in those instances I return pointers to the words in the list to keep from making unnecessary copies.

But I think what you're getting at is similar words, ie: "COBRA" versus "COBRAS" in which yes, there are a lot of those. Thanks for the tip about boost::flyweight. I still need to evaluate whether I need more memory, but if I do I'll definitely consider that.

Thanks,
--Brian

## Create an account

Register a new account