[Gnash-dev] Re: string_table::noCase

[Benjamin Wolsey]

> The call to noCase seek for a match in a table of caseful-to-caseless
> string_table::key values (longs) in order to tell if the input is already
> lower-case or not (can Ben confirm this?).

The string table design means that unique strings are represented by
arbitrary keys. This obviously means that, given two keys, there's no
way to tell if they are equal case-insensitively.

That was the problem that the second lookup table solved. It means that
the 'case-insensitive' version of each string has its own key, and that
all strings that match the case-insensitive version can be matched to
that key.

Previously the string_table as a whole was set to case-insensitive mode
for SWF6. That was faster gain, but made running mixed-case SWFs
impossible, and caused known bugs in SWF6.

> The process to find a property currently has these steps:
>       1. Find the 'key' corresponding to a name (long from string)
>       2. Find the lower-case 'key' corresponding to a 'key' (long from long)
>       3. Find the Property corresponding to the lower-case 'key' (Property*
>          from long)

Objects have a container of properties with three indices:

a) Sequenced (creation order). This is the only necessary order for
compatible behaviour.
b) Case-sensitive. This improves lookup speed for large containers like
arrays.
c) Case-insensitive. This improves lookup speed for SWF6 and below.

The complexity of this is as follows:

b) allows logarithmic lookup with the additional (once-only) conversion
of string->key (O(log n)).

c) is the same as b) except with an additional lookup of
key->case-insensitive key (O(log n)).

The final lookup and the key->case-insensitive key lookup use size_t, so
are potentially faster than searching for a string.

Using strings everywhere would avoid the need to convert to a key, and
converting to lower case is O(n), removing the need for c)'s third
lookup. But all binary searches would be string searches, which adds a
bit of overhead in some cases.

However: the current implementation uses keys at least from as_object
onwards. Switching to strings either needs changes to all that code, or
to look up key->string in the string_table.

Also note that the third, case-insensitive property index is
indispensable if we are doing string lookup, as converting all
properties to lower case on demand for matching would be considerably
worse performance than we have now.

> How can we improve it ?

With the current string_table implementation, I think the options are
quite limited. 

> Was this tested to be faster than looking for the string directly
> using a case-insensitive index ?

I'm not sure where exactly you would do this if it's not covered by one
of the options above.

bwy

--
Use Gnash, the GNU Flash Player!
http://www.gnu.org/software/gnash/

Benjamin Wolsey, Software Developer - http://benjaminwolsey.de
C++ and Open-Source Flash blog - http://www.benjaminwolsey.de/bwysblog

xmpp:address@hidden
http://identi.ca/bwy

signature.asc
Description: Dies ist ein digital signierter Nachrichtenteil