Jump to content
  • Advertisement
  • entries
    25
  • comments
    39
  • views
    47079

I'm Not Too Bright

Sign in to follow this  
Nairb

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



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.
Sign in to follow this  


2 Comments


Recommended Comments

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.

Share this comment


Link to comment
(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

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!