Re: [PATCH] dfa: save memory for states

[Bruno Haible]

Hi Norihiro,

I'm not maintainer of the 'dfa' module, but nevertheless I'd like to know
what is going on more precisely (because clearing a cache more often
deteriorates running times than improve running times). 3 questions:

1)
> This patch checks number of states in beginning of dfa execution, and if
> there are a lot of states, release them.

Have you measured what are the execution times without/before and with/after
your patch, for example in the "seq -f '%g bottles of beer on the wall' 2400"
example that you showed? Can you show us the benchmark results?

2) Your patch cuts down on three different caches:
  - d->states,
  - d->trans, d->fails,
  - d->mb_trans.
Can you prepare a separate patch for each of the three changes, and
present the benchmark results of each? It would be interesting to know
which of the three has the most effect on the timings.

3) If you are right that reducing the size of a cache improves the timings,
then it means the lookup in the cache is not O(1)? In other words, can the
lookup in the cache be optimized (through more adapted data structures -
I'm thinking of binary trees or hash tables), so that a larger cache size
will NOT lead to a longer execution time?

Bruno