Re: [Patch] Optimize _BFSExecutor in regex

[Tim Shen <timshen91 at gmail dot com>]

Sorry I forgot to reply the mailing list. Here's the discussion:

----------------------------------------------- Tim
--------------------------------

On Oct 7, 2013 7:12 AM, "Jonathan Wakely" <jwakely.gcc@gmail.com> wrote:
> 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.

I use private inheritance here to convey "it's just a wrapper class of
vector". I don't see great difference between it and using a second
member?

> _TodoList::__exists should be named _M_exists to follow the library
> coding standards.

Sorry for that >.<

> Shouldn't _TodoList::_M_empty() also set __exists[n] = false for all n?

We can add an assertion here, but _M_empty shouldn't set anything.
This function has no side effect.

> I think it's guaranteed that __exists[__u] is always in range, right?

Of course. Otherwise vector's range checker will help, right?

----------------------------------------------- Jonathan
--------------------------------

On 7 October 2013 14:31, Tim Shen wrote:
> On Oct 7, 2013 7:12 AM, "Jonathan Wakely" <jwakely.gcc@gmail.com> wrote:
>> 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.
>
> I use private inheritance here to convey "it's just a wrapper class of
> vector". I don't see great difference between it and using a second member?

Aggregation is simpler,

If I see subtyping I wonder if some users of the type need to rely on
conversion to the base class, i.e. whether it is important that
_TodoList IS-A vector, but as it's private and has no friends, that
can't be true.

In general, prefer composition to inheritance:
http://www.artima.com/cppsource/codestandards3.html

>> Shouldn't _TodoList::_M_empty() also set __exists[n] = false for all n?
>
> We can add an assertion here, but _M_empty shouldn't set anything. This
> function has no side effect.

Sorry, I meant _M_clear() not _M_empty().

Currently you loop over the vector popping one element at a time until
it's empty, why not just use _BaseT::clear()?  Does anything even use
that member?  If it is needed, why is it correct to not reset the
flags in __exists to false?

>> I think it's guaranteed that __exists[__u] is always in range, right?
>
> Of course. Otherwise vector's range checker will help, right?

Only in Debug Mode, there is no range checking in operator[] in the
normal case.  But as long as the vector has the right size (from
_M_nfa.size()) and can only be accessed with valid indices it's fine.

----------------------------------------------- Tim
--------------------------------

On Mon, Oct 7, 2013 at 10:56 AM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
> Aggregation is simpler,

OK I'll change it to use a private member, since indeed I don't need
to use protected part of vector.

> Currently you loop over the vector popping one element at a time until
> it's empty, why not just use _BaseT::clear()?  Does anything even use
> that member?  If it is needed, why is it correct to not reset the
> flags in __exists to false?

I use a loop to clear rather than a _BaseT::clear() then reset the
__exists(_M_exists), simply because it's too
expensive(O(__exists.size())). With my implementation, I can make it
O(this->size()), which is usually far smaller than size of __exists. A
better way to do that is to traverse *this and only reset all trues,
then _BaseT::clear().

Ah we can remove this member function, because it's used only in early
versions of this patch.

----------------------------------------------- Jonathan
--------------------------------

On 7 October 2013 16:34, Tim Shen wrote:
> On Mon, Oct 7, 2013 at 10:56 AM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
>> Aggregation is simpler,
>
> OK I'll change it to use a private member, since indeed I don't need
> to use protected part of vector.
>
>> Currently you loop over the vector popping one element at a time until
>> it's empty, why not just use _BaseT::clear()?  Does anything even use
>> that member?  If it is needed, why is it correct to not reset the
>> flags in __exists to false?
>
> I use a loop to clear rather than a _BaseT::clear() then reset the
> __exists(_M_exists),

Where do you reset __exists? That was my point, I don't see that being
reset, but it should have been.

> simply because it's too
> expensive(O(__exists.size())). With my implementation, I can make it
> O(this->size()), which is usually far smaller than size of __exists. A
> better way to do that is to traverse *this and only reset all trues,
> then _BaseT::clear().

Traversing a vector<bool> is not efficient because of the proxy
iterators it uses. I expect it would be much quicker to have done:

  __exists.assign(__exists.size(
), false);

because that turns into the equivalent of a std::memset() on integers.

> Ah we can remove this member function, because it's used only in early
> versions of this patch.

OK, great. So the changes to _M_clear() don't matter then :-)


-- 
Tim Shen