[Top][All Lists]

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

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

From: Yuri
Subject: Fwd: [patch] Fix of the CPU bottleneck in pack_vector
Date: Thu, 20 Dec 2012 17:32:57 -0800
User-agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:17.0) Gecko/17.0 Thunderbird/17.0


I reported this issue with the testcase and patch in Jan 2012.
Now I see that you didn't apply it as of 2.7 (Dec 2012).

Why didn't you apply it? It fixes the algorithmic bottleneck in bison that I am sure someone else will hit it sooner or later.

Also why there is no bug tracking page for bison? How can people meaningfully track issues without the bug tracker?


-------- Original Message --------
Subject:        [patch] Fix of the CPU bottleneck in pack_vector
Date:   Fri, 13 Jan 2012 16:31:34 -0800
From:   Yuri <address@hidden>
To:     address@hidden

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

I believe this patch will speed any sizable test case up.

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


Attachment: patch.txt
Description: Text document

reply via email to

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