avl_string_cache branch

[chromatic]

On Wednesday 31 March 2010 at 15:47, Vasily Chekalkin wrote:

> Just few notes:
> 
> 1. We have much more constant strings in this tree than before. Due PBC 
changed to use it.

That should be okay with a memory savings overall, as we can reuse string 
headers more often.

> 2. Overall tree height is about 12. So we are doing more strings traversal 
than before.

I think that's the source of the slower performance; almost every comparison 
of strings ends up checking the contents of the string with a memcmp.  I think 
we need a custom tree traversal function which exploits natural indexing 
characteristics of our strings.

At the topmost level, check by string length.  Then check by encoding type.  
Then check by each character in the string, rather than comparing the whole 
string at a time (an inlined comparison of the correct character in the string 
is cheaper than even the memcmp call).

In other words, every level we descend into the tree we need to check only one 
piece of information -- the length of the string, the encoding type, or one 
specific character in the string.

Does that make sense?

-- c