This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [Patch] Optimize _BFSExecutor in regex

On Mon, Oct 7, 2013 at 7:12 AM, Jonathan Wakely <> wrote:
> On 6 October 2013 23:43, Tim Shen wrote:
>> Here's a simple piece of code
>> the reveals _BFSExecutor's
>> inefficiency. Some optimizations are here to reduce the unecessary
>> time complexity from O(n^2) to O(n).
>> I'll do a bootstrap and full testing before committing.
> In the ChangeLog, please fix the spelling of "unnecessary".
> The constructor of _TodoList could be "explicit"
> Does _TodoList really need to derive from std::vector<_StateIdT> or
> could it just have a second member? I think there's no benefit to
> using inheritance here.
> _TodoList::__exists should be named _M_exists to follow the library
> coding standards.
> Shouldn't _TodoList::_M_empty() also set __exists[n] = false for all n?
> I think it's guaranteed that __exists[__u] is always in range, right?

Anyway, here's the patch. I intended to write something like a
Quine[1] as the testcase but gave up ;)

Thank you!


Tim Shen

Attachment: a.patch
Description: Binary data

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]