Re: [Patch] Optimize _BFSExecutor in regex

[Jonathan Wakely <jwakely dot gcc at gmail dot com>]

On 7 October 2013 22:14, Tim Shen wrote:
> On Mon, Oct 7, 2013 at 1:28 PM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
>> std::memset() on about 125 bytes is not a big deal, I doubt it's
>> significantly more expensive than the calculations to find the right
>> bits and do the necessary masking for three elements.
>> std::vector<bool> is a strange beast, remember.
>
> Probably there could be bitwise operation?

Yes, most operations on vector<bool> involve bitwise operations.

> I've test the 3 trues out of 1000 elements here :
> https://gist.github.com/innocentim/6874889
> In my machine, choosing "v.assign(v.size(), false);" cost 1.768s and
> choosing the other cost 1.088s. When we push 7 elements, they cost
> almost same time. When push more than that, v.assign() shall win.

You're right, popping one at a time is measurably faster than filling
the whole vector<bool> with zeros, even when _M_exists.size() is
small.  I'm quite surprised. I expected updating the vector size on
every pop_back() to make it slower.

The version in your gist (which is *not* what your first patch did!)
is faster for any size of _M_exists and any ratio of _M_states.size()
/ _M_exists.size():


> I do this because I need to use _M_clear() in this patch :)
>
> Anyway let's use v.assign().

Sorry for wasting your time regarding using assign(), it does seem to
be slower (and produces larger code) so please go for something like
in your gist (not in the original patch, which left true values in the
_M_exists vector!) i.e. something like

for (auto __i : _M_states)
    _M_base[__i] = false;
  _M_base.clear();

But please rename _M_base, that name doesn't make sense, it used to be
the base class, but it isn't now, and that vector has nothing to do
with base classes now! How about  _M_states?

Please also make _M_empty() const.

Thanks!