[m-rev.] for review: string switches using tries

[Zoltan Somogyi]

On Mon, 2 Mar 2015 16:51:32 +1100, Peter Wang <novalazy at gmail.com> wrote:
> Here are the results for a real workload, Prince built in hlc.gc with
> options -O5 --intermodule-optimisation --optimize-constructor-last-call
> --string-trie-switch-size=N converting a document thesis.html.
> Times are in user seconds, averaged over ten runs each.
> 
> 3.3836s	--string-trie-switch-size=1 (no hash tables used)
> 3.5661s	--string-trie-switch-size=16
> 3.4245s	--string-trie-switch-size=64
> 3.4054s	--string-trie-switch-size=128
> 3.3586s	--string-trie-switch-size=256 (no tries used)

Thanks for that.

That is one curious set of results. It seems that all-tries
and all-hashtables are equally good (since the difference
between 3.35 and 3.38 is noise), but a mixture is worse
(since the difference between 3.38 and 3.56 is not noise).

My guess is that there are some switches with somewhere
between 16 and 63 arms that are worse with tries, possibly
because they are frequently switching on values that
require lots of comparisons and their associated conditional
branches to select the applicable arm (e.g. selecting between
aaaaaaaa, aaaaaab and aaaaaac), while some other switches
that have less than 16 arms are frequently switching on values
where the first one or two code units decide which arm is
applicable. This would explain the above pattern:
with the 16 setting, you get the slowdown from switching
from hash tables to tries, but not the compensating speedup.

Any idea whether my guess is in the right ballpark?

Zoltan.