bison-patches
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[patch] Fix of the CPU bottleneck in pack_vector


From: Yuri
Subject: [patch] Fix of the CPU bottleneck in pack_vector
Date: Fri, 13 Jan 2012 16:31:34 -0800
User-agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:9.0) Gecko/20111226 Thunderbird/9.0

Hi bison maintainers,

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.

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.

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

Thanks,
Yuri

Attachment: patch.txt
Description: Text document


reply via email to

[Prev in Thread] Current Thread [Next in Thread]