Re: [patch] Fix of the CPU bottleneck in pack_vector

[Akim Demaille]

Le 14 janv. 2012 à 01:31, Yuri a écrit :

> Hi bison maintainers,

Hi Yuri,

> The attached patch fixes the CPU problem that these lines in pack_vector 
> function caused in certain testcases:
>      for (k = 0; ok && k < vector; k++)
>        if (pos[k] == j)
>          ok = false;
> 
> In the version 2.5, pos array essentially represents the integer set with 
> unique integers placed into it in the random order.
> In the above code section, pos is linearly scrolled through every time some j 
> is tested for the set membership, and this was 98.5% CPU in certain testcases.

Wow!  You just aroused my curiosity!  Could you give us some
indication on the kind of use you make of Bison?  Running
the backend is sooooo expensive, that I would have bet that
such optimization would be completely impossible to feel.

> What this patch does:
> it replaces pos integer array with pos_set boolean array. pos_set represents 
> the same integer set as pos did, but in a way of membership bit indexed by 
> the integer.
> Such that set insertion and membership testing operations are done in one 
> quick step at the expense of a little more memory allocated. Before insertion 
> was quick, but membership testing was slow and caused the CPU bottleneck.
> 
> I believe this patch will speed any sizable test case up.

Yes, I would say so too.

> Please let me know if you find any problem with the patch.

Now the problem would be how to apply it.  It is quite short, but
I doubt it falls under the "trivial change" clause.  So either
one of us would have to rewrite it, or you would have to file some
legal paperwork for the FSF.