[Patch] Optimize _BFSExecutor in regex
Tim Shen
timshen91@gmail.com
Mon Oct 7 16:48:00 GMT 2013
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
More information about the Gcc-patches
mailing list