[patch 1/N] std::regex refactoring - _BracketMatcher

[patch 1/N] std::regex refactoring - _BracketMatcher

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 1154 bytes --]

Hi,

I've been looking through the regex code and have a few ideas for
simplifications or optimisations that I'd like to share.

This first patch is for _BracketMatcher. We only use std::bitset when
is_same<_CharT, char> so 8 * sizeof(_CharT) should be __CHAR_BIT__
instead. We also only user _UnsignedCharT when is_same<_CharT, char>
so that can just be simplified to unsigned char.

The contents of _BracketMatcher::_M_char_set are not sorted and can
contain duplicates in the current code. Making that a sorted, unique
list in _BracketMatcher::_M_ready() allows a binary search instead of
linear search. This improves worst case performance for pathological
regular expressions like std::wregex('['+std::wstring(1000, 'a')+"b]")
but I'm not sure if it helps in the common case.

Finally, in the non-char case the _CacheT member is an unused empty
object, so having that as the first member requires 7 bytes of
padding. Re-ordering the members reduces the size of a non-char
_BracketMatcher by 8 bytes (but it's still a whopping 96 bytes).

(For a char _BracketMatcher the bitset cache makes it 128 bytes,
this patch doesn't change that).

Thoughts?



[-- Attachment #2: re1.patch --]
[-- Type: text/x-diff, Size: 3178 bytes --]

diff --git a/libstdc++-v3/include/bits/regex_compiler.h b/libstdc++-v3/include/bits/regex_compiler.h
index f5a198f..a9dd8d3 100644
--- a/libstdc++-v3/include/bits/regex_compiler.h
+++ b/libstdc++-v3/include/bits/regex_compiler.h
@@ -396,6 +396,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       _M_ready()
       {
+	std::sort(_M_char_set.begin(), _M_char_set.end());
+	auto __end = std::unique(_M_char_set.begin(), _M_char_set.end());
+	_M_char_set.erase(__end, _M_char_set.end());
 	_M_make_cache(_IsChar());
 #ifdef _GLIBCXX_DEBUG
 	_M_is_ready = true;
@@ -405,10 +408,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     private:
       typedef typename is_same<_CharT, char>::type _IsChar;
       struct _Dummy { };
+      static constexpr size_t _S_cache_size() { return 1ul << __CHAR_BIT__; }
       typedef typename conditional<_IsChar::value,
-				   std::bitset<1 << (8 * sizeof(_CharT))>,
+				   std::bitset<_S_cache_size()>,
 				   _Dummy>::type _CacheT;
-      typedef typename make_unsigned<_CharT>::type _UnsignedCharT;
 
     private:
       bool
@@ -416,14 +419,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       bool
       _M_apply(_CharT __ch, true_type) const
-      { return _M_cache[static_cast<_UnsignedCharT>(__ch)]; }
+      { return _M_cache[static_cast<unsigned char>(__ch)]; }
 
       void
       _M_make_cache(true_type)
       {
-	for (int __i = 0; __i < _M_cache.size(); __i++)
-	  _M_cache[static_cast<_UnsignedCharT>(__i)] =
-	    _M_apply(__i, false_type());
+	for (unsigned __i = 0; __i < _S_cache_size(); __i++)
+	  _M_cache[__i] = _M_apply(static_cast<char>(__i), false_type());
       }
 
       void
@@ -431,13 +433,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { }
 
     private:
-      _CacheT                                   _M_cache;
       std::vector<_CharT>                       _M_char_set;
       std::vector<_StringT>                     _M_equiv_set;
       std::vector<pair<_StrTransT, _StrTransT>> _M_range_set;
       _CharClassT                               _M_class_set;
       _TransT                                   _M_translator;
       const _TraitsT&                           _M_traits;
+      _CacheT                                   _M_cache;
       bool                                      _M_is_non_matching;
 #ifdef _GLIBCXX_DEBUG
       bool                                      _M_is_ready;
diff --git a/libstdc++-v3/include/bits/regex_compiler.tcc b/libstdc++-v3/include/bits/regex_compiler.tcc
index 128dac1..36edfba 100644
--- a/libstdc++-v3/include/bits/regex_compiler.tcc
+++ b/libstdc++-v3/include/bits/regex_compiler.tcc
@@ -507,12 +507,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _BracketMatcher<_TraitsT, __icase, __collate>::
     _M_apply(_CharT __ch, false_type) const
     {
-      bool __ret = false;
-      if (std::find(_M_char_set.begin(), _M_char_set.end(),
-		    _M_translator._M_translate(__ch))
-	  != _M_char_set.end())
-	__ret = true;
-      else
+      bool __ret = std::binary_search(_M_char_set.begin(), _M_char_set.end(),
+				      _M_translator._M_translate(__ch));
+      if (!__ret)
 	{
 	  auto __s = _M_translator._M_transform(__ch);
 	  for (auto& __it : _M_range_set)

[patch 2/N] std::regex refactoring - sub _Executor for lookahead

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 58 bytes --]

Is there any reason this object is created on the heap?



[-- Attachment #2: re2.patch --]
[-- Type: text/x-patch, Size: 881 bytes --]

diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
index 7f89933..92ca590 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -145,13 +145,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _M_lookahead(_State<_TraitsT> __state)
     {
       _ResultsVec __what(_M_cur_results.size());
-      auto __sub = std::unique_ptr<_Executor>(new _Executor(_M_current,
-							    _M_end,
-							    __what,
-							    _M_re,
-							    _M_flags));
-      __sub->_M_start_state = __state._M_alt;
-      if (__sub->_M_search_from_first())
+      _Executor __sub(_M_current, _M_end, __what, _M_re, _M_flags);
+      __sub._M_start_state = __state._M_alt;
+      if (__sub._M_search_from_first())
 	{
 	  for (size_t __i = 0; __i < __what.size(); __i++)
 	    if (__what[__i].matched)

Re: [patch 2/N] std::regex refactoring - sub _Executor for lookahead

[Tim Shen]

On Mon, Apr 28, 2014 at 8:45 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
> Is there any reason this object is created on the heap?

Say, _Executor's size is so huge and a uncommon user gets a stack
overflow by keep invoking this function?


-- 
Regards,
Tim Shen

Re: [patch 2/N] std::regex refactoring - sub _Executor for lookahead

[Jonathan Wakely]

On 28/04/14 10:18 -0400, Tim Shen wrote:
>On Mon, Apr 28, 2014 at 8:45 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
>> Is there any reason this object is created on the heap?
>
>Say, _Executor's size is so huge and a uncommon user gets a stack
>overflow by keep invoking this function?

Ah yes, I didn't think of that. But the size of _Executor is fixed,
isn't it?  If it has a huge number of states or matches those will be
on the heap anyway, in vectors/arrays.

It could be huge if instantiated with a huge iterator type, as it
stores three members of the iterator type, but I don't think users
should be too surprised if they overflow the stack with freakishly
large iterators :-)

Am I still missing something?

(I don't have a preference for whether to change this, but if we keep
it on the heap we should add a comment, or I'll keep forgetting the
rationale and try to change it again!)

Re: [patch 2/N] std::regex refactoring - sub _Executor for lookahead

[Tim Shen]

On Mon, Apr 28, 2014 at 10:55 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
> Ah yes, I didn't think of that. But the size of _Executor is fixed,
> isn't it?  If it has a huge number of states or matches those will be
> on the heap anyway, in vectors/arrays.
>
> It could be huge if instantiated with a huge iterator type, as it
> stores three members of the iterator type, but I don't think users
> should be too surprised if they overflow the stack with freakishly
> large iterators :-)
>
> Am I still missing something?
>
> (I don't have a preference for whether to change this, but if we keep
> it on the heap we should add a comment, or I'll keep forgetting the
> rationale and try to change it again!)

Either way is OK, in fact. Let's just keep the code simple by applying
this patch. I can't imagine one could use nested lookahead. :)


-- 
Regards,
Tim Shen

Re: [patch 1/N] std::regex refactoring - _BracketMatcher

[Tim Shen]

On Mon, Apr 28, 2014 at 8:40 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
> I've been looking through the regex code and have a few ideas for
> simplifications or optimisations that I'd like to share.

Thanks :)

> This first patch is for _BracketMatcher. We only use std::bitset when
> is_same<_CharT, char> so 8 * sizeof(_CharT) should be __CHAR_BIT__
> instead. We also only user _UnsignedCharT when is_same<_CharT, char>
> so that can just be simplified to unsigned char.

Yes, since _UnsignedCharT is just used as indexes, we can always use a
larger unsigned integer instead. Maybe "size_t" is a better choice?

I'm not sure if we'll have a wchar_t cache (bitset<65536>) in the future ;)

> The contents of _BracketMatcher::_M_char_set are not sorted and can
> contain duplicates in the current code. Making that a sorted, unique
> list in _BracketMatcher::_M_ready() allows a binary search instead of
> linear search. This improves worst case performance for pathological
> regular expressions like std::wregex('['+std::wstring(1000, 'a')+"b]")
> but I'm not sure if it helps in the common case.

Trust me, in common case, even it's a bit slower, it won't be
observable. So it's just OK.

> Finally, in the non-char case the _CacheT member is an unused empty
> object, so having that as the first member requires 7 bytes of
> padding. Re-ordering the members reduces the size of a non-char
> _BracketMatcher by 8 bytes (but it's still a whopping 96 bytes).
>
> (For a char _BracketMatcher the bitset cache makes it 128 bytes,
> this patch doesn't change that).

This is OK too.

Rant: I can't understand why the committee doesn't keep things simple
by letting struct { } has 0 size. I used to implement my own tuple by
specializing tuple<> as an empty struct. The thing is, one tuple
shouldn't `has it` as a member, or it will get extra padding; at last
I used inheritance.


-- 
Regards,
Tim Shen

Re: [patch 1/N] std::regex refactoring - _BracketMatcher

[Jonathan Wakely]

On 28/04/14 10:15 -0400, Tim Shen wrote:
>On Mon, Apr 28, 2014 at 8:40 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
>> I've been looking through the regex code and have a few ideas for
>> simplifications or optimisations that I'd like to share.
>
>Thanks :)
>
>> This first patch is for _BracketMatcher. We only use std::bitset when
>> is_same<_CharT, char> so 8 * sizeof(_CharT) should be __CHAR_BIT__
>> instead. We also only user _UnsignedCharT when is_same<_CharT, char>
>> so that can just be simplified to unsigned char.
>
>Yes, since _UnsignedCharT is just used as indexes, we can always use a
>larger unsigned integer instead. Maybe "size_t" is a better choice?

There is a well-defined mapping from every unsigned char in the range
[0,255] to char and back, so conversions between char and unsigned
char are fine.  If we used a larger type then we would get the wrong result
when char is signed, because (size_t)(char)-1 != (unsigned char)(char)-1

>I'm not sure if we'll have a wchar_t cache (bitset<65536>) in the future ;)

sizeof(wchar_t) is 4 on unix-like systems, but a cache for char16_t
wouldn't be totally crazy.

If you prefer I will not remove the uses of _CharT and _UnsignedCharT
and won't assume the cache is only used for char. There are still some
simplifications we can make.

>> The contents of _BracketMatcher::_M_char_set are not sorted and can
>> contain duplicates in the current code. Making that a sorted, unique
>> list in _BracketMatcher::_M_ready() allows a binary search instead of
>> linear search. This improves worst case performance for pathological
>> regular expressions like std::wregex('['+std::wstring(1000, 'a')+"b]")
>> but I'm not sure if it helps in the common case.
>
>Trust me, in common case, even it's a bit slower, it won't be
>observable. So it's just OK.
>
>> Finally, in the non-char case the _CacheT member is an unused empty
>> object, so having that as the first member requires 7 bytes of
>> padding. Re-ordering the members reduces the size of a non-char
>> _BracketMatcher by 8 bytes (but it's still a whopping 96 bytes).
>>
>> (For a char _BracketMatcher the bitset cache makes it 128 bytes,
>> this patch doesn't change that).
>
>This is OK too.

Thanks, I'll clean the patch up and commit it soon.

Re: [patch 1/N] std::regex refactoring - _BracketMatcher

[Tim Shen]

On Mon, Apr 28, 2014 at 11:05 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
> There is a well-defined mapping from every unsigned char in the range
> [0,255] to char and back, so conversions between char and unsigned
> char are fine.  If we used a larger type then we would get the wrong result
> when char is signed, because (size_t)(char)-1 != (unsigned char)(char)-1

You are right. I've missed this.

> sizeof(wchar_t) is 4 on unix-like systems, but a cache for char16_t
> wouldn't be totally crazy.
>
> If you prefer I will not remove the uses of _CharT and _UnsignedCharT
> and won't assume the cache is only used for char. There are still some
> simplifications we can make.

Yes, I (now again) prefer _UnsignedCharT. But it's just kind of
personal flavor, I suppose?

> Thanks, I'll clean the patch up and commit it soon.

Thanks again :)


-- 
Regards,
Tim Shen

[patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 1461 bytes --]

This change splits _Executor::_M_main() into two overloaded
_M_main_dispatch() functions, choosing which to run based on the
__dfs_mode template parameter.

I think this gives a (very) small improvement in compilation time when
using regexes.

Splitting _M_main() allows the _M_match_queue and _M_visited members
(which are only used in BFS mode) to be replaced with an instantiation
of the new _States class template. _States<__dfs> only contains the
start state (so that it's not empty and doesn't waste space) but
_States<__bfs> contains the start state and also the match queue and
visited list.

As the visited list never changes size after construction I changed
its type from unique_ptr<vector<bool>> to unique_ptr<bool[]>, which
avoids an indirection, although now that that member is only present
when actually required it could just be vector<bool>. An array of bool
is simpler to access, but takes more heap memory. vector<bool> uses
less space but the compiler has to do all the masking to address
individual bits.

I also changed this range-based for loop in _M_main (now in
_M_main_dispatch(__bfs)) to make __task a reference, avoiding one
copy, and to move from __task.second, avoiding a second copy:

        auto __old_queue = std::move(_M_states._M_match_queue);
        for (auto& __task : __old_queue)
          {
            _M_cur_results = std::move(__task.second);
            _M_dfs<__match_mode>(__task.first);
          }

Thoughts?


[-- Attachment #2: re3.patch --]
[-- Type: text/x-patch, Size: 10833 bytes --]

diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
index c110b88..064e3df 100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -42,8 +42,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    */
 
   /**
-   * @brief Takes a regex and an input string in and
-   * do the matching.
+   * @brief Takes a regex and an input string and does the matching.
    *
    * The %_Executor class has two modes: DFS mode and BFS mode, controlled
    * by the template parameter %__dfs_mode.
@@ -52,6 +51,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   bool __dfs_mode>
     class _Executor
     {
+      using __search_mode = integral_constant<bool, __dfs_mode>;
+      using __dfs = true_type;
+      using __bfs = false_type;
+
     public:
       typedef typename iterator_traits<_BiIter>::value_type _CharT;
       typedef basic_regex<_CharT, _TraitsT>                 _RegexT;
@@ -71,16 +74,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_re(__re),
       _M_nfa(*__re._M_automaton),
       _M_results(__results),
-      _M_match_queue(__dfs_mode ? nullptr
-		     : new vector<pair<_StateIdT, _ResultsVec>>()),
       _M_rep_count(_M_nfa.size()),
-      _M_visited(__dfs_mode ? nullptr : new vector<bool>(_M_nfa.size())),
+      _M_states(_M_nfa._M_start(), _M_nfa.size()),
       _M_flags((__flags & regex_constants::match_prev_avail)
 	       ? (__flags
 		  & ~regex_constants::match_not_bol
 		  & ~regex_constants::match_not_bow)
-	       : __flags),
-      _M_start_state(_M_nfa._M_start())
+	       : __flags)
       { }
 
       // Set matched when string exactly match the pattern.
@@ -113,7 +113,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       template<bool __match_mode>
 	bool
-	_M_main();
+	_M_main()
+	{ return _M_main_dispatch<__match_mode>(__search_mode{}); }
+
+      template<bool __match_mode>
+	bool
+	_M_main_dispatch(__dfs);
+
+      template<bool __match_mode>
+	bool
+	_M_main_dispatch(__bfs);
 
       bool
       _M_is_word(_CharT __ch) const
@@ -144,6 +153,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       bool
       _M_lookahead(_State<_TraitsT> __state);
 
+       // Holds additional information used in BFS-mode.
+      template<typename _SearchMode, typename _ResultsVec>
+	struct _State_info;
+
+      template<typename _ResultsVec>
+	struct _State_info<__bfs, _ResultsVec>
+	{
+	  explicit
+	  _State_info(_StateIdT __start, size_t __n)
+	  : _M_start(__start), _M_visited_states(new bool[__n]())
+	  { }
+
+	  bool _M_visited(_StateIdT __i)
+	  {
+	    if (_M_visited_states[__i])
+	      return true;
+	    _M_visited_states[__i] = true;
+	    return false;
+	  }
+
+	  void _M_queue(_StateIdT __i, const _ResultsVec& __res)
+	  { _M_match_queue.emplace_back(__i, __res); }
+
+	  // Saves states that need to be considered for the next character.
+	  vector<pair<_StateIdT, _ResultsVec>>	_M_match_queue;
+	  // Indicates which states are already visited.
+	  unique_ptr<bool[]>			_M_visited_states;
+	  // To record current solution.
+	  _StateIdT _M_start;
+	};
+
+      template<typename _ResultsVec>
+	struct _State_info<__dfs, _ResultsVec>
+	{
+	  explicit
+	  _State_info(_StateIdT __start, size_t) : _M_start(__start)
+	  { }
+
+	  // Dummy implementations for DFS mode.
+	  bool _M_visited(_StateIdT) const { return false; }
+	  void _M_queue(_StateIdT, const _ResultsVec&) { }
+
+	  // To record current solution.
+	  _StateIdT _M_start;
+	};
+
+
     public:
       _ResultsVec                                           _M_cur_results;
       _BiIter                                               _M_current;
@@ -152,15 +208,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       const _RegexT&                                        _M_re;
       const _NFAT&                                          _M_nfa;
       _ResultsVec&                                          _M_results;
-      // Used in BFS, saving states that need to be considered for the next
-      // character.
-      unique_ptr<vector<pair<_StateIdT, _ResultsVec>>>      _M_match_queue;
-      // Used in BFS, indicating that which state is already visited.
       vector<pair<_BiIter, int>>                            _M_rep_count;
-      unique_ptr<vector<bool>>                              _M_visited;
+      _State_info<__search_mode, _ResultsVec>		    _M_states;
       _FlagT                                                _M_flags;
-      // To record current solution.
-      _StateIdT                                             _M_start_state;
       // Do we have a solution so far?
       bool                                                  _M_has_sol;
     };
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
index 7f89933..3e14bf6 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -35,7 +35,7 @@ namespace __detail
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
-    bool __dfs_mode>
+	   bool __dfs_mode>
     bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
     _M_search()
     {
@@ -53,8 +53,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return false;
     }
 
-  // This function operates in different modes, DFS mode or BFS mode, indicated
-  // by template parameter __dfs_mode. See _M_main for details.
+  // The _M_main function operates in different modes, DFS mode or BFS mode,
+  // indicated by template parameter __dfs_mode, and dispatches to one of the
+  // _M_main_dispatch overloads.
   //
   // ------------------------------------------------------------
   //
@@ -75,6 +76,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // Time complexity: \Omega(match_length), O(2^(_M_nfa.size()))
   // Space complexity: \theta(match_results.size() + match_length)
   //
+  template<typename _BiIter, typename _Alloc, typename _TraitsT,
+	   bool __dfs_mode>
+  template<bool __match_mode>
+    bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
+    _M_main_dispatch(__dfs)
+    {
+      _M_has_sol = false;
+      _M_cur_results = _M_results;
+      _M_dfs<__match_mode>(_M_states._M_start);
+      return _M_has_sol;
+    }
+
   // ------------------------------------------------------------
   //
   // BFS mode:
@@ -84,11 +97,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   //
   // It first computes epsilon closure (states that can be achieved without
   // consuming characters) for every state that's still matching,
-  // using the same DFS algorithm, but doesn't re-enter states (find a true in
-  // _M_visited), nor follows _S_opcode_match.
+  // using the same DFS algorithm, but doesn't re-enter states (using
+  // _M_states._M_visited to check), nor follow _S_opcode_match.
   //
-  // Then apply DFS using every _S_opcode_match (in _M_match_queue) as the start
-  // state.
+  // Then apply DFS using every _S_opcode_match (in _M_states._M_match_queue)
+  // as the start state.
   //
   // It significantly reduces potential duplicate states, so has a better
   // upper bound; but it requires more overhead.
@@ -98,49 +111,39 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // Space complexity: \Omega(_M_nfa.size() + match_results.size())
   //                   O(_M_nfa.size() * match_results.size())
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
-    bool __dfs_mode>
+	   bool __dfs_mode>
   template<bool __match_mode>
     bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
-    _M_main()
+    _M_main_dispatch(__bfs)
     {
-      if (__dfs_mode)
+      _M_states._M_queue(_M_states._M_start, _M_results);
+      bool __ret = false;
+      while (1)
 	{
 	  _M_has_sol = false;
-	  _M_cur_results = _M_results;
-	  _M_dfs<__match_mode>(_M_start_state);
-	  return _M_has_sol;
-	}
-      else
-	{
-	  _M_match_queue->push_back(make_pair(_M_start_state, _M_results));
-	  bool __ret = false;
-	  while (1)
+	  if (_M_states._M_match_queue.empty())
+	    break;
+	  std::fill_n(_M_states._M_visited_states.get(), _M_nfa.size(), false);
+	  auto __old_queue = std::move(_M_states._M_match_queue);
+	  for (auto& __task : __old_queue)
 	    {
-	      _M_has_sol = false;
-	      if (_M_match_queue->empty())
-		break;
-	      _M_visited->assign(_M_visited->size(), false);
-	      auto _M_old_queue = std::move(*_M_match_queue);
-	      for (auto __task : _M_old_queue)
-		{
-		  _M_cur_results = __task.second;
-		  _M_dfs<__match_mode>(__task.first);
-		}
-	      if (!__match_mode)
-		__ret |= _M_has_sol;
-	      if (_M_current == _M_end)
-		break;
-	      ++_M_current;
+	      _M_cur_results = std::move(__task.second);
+	      _M_dfs<__match_mode>(__task.first);
 	    }
-	  if (__match_mode)
-	    __ret = _M_has_sol;
-	  return __ret;
+	  if (!__match_mode)
+	    __ret |= _M_has_sol;
+	  if (_M_current == _M_end)
+	    break;
+	  ++_M_current;
 	}
+      if (__match_mode)
+	__ret = _M_has_sol;
+      return __ret;
     }
 
   // Return whether now match the given sub-NFA.
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
-    bool __dfs_mode>
+	   bool __dfs_mode>
     bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
     _M_lookahead(_State<_TraitsT> __state)
     {
@@ -150,7 +153,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 							    __what,
 							    _M_re,
 							    _M_flags));
-      __sub->_M_start_state = __state._M_alt;
+      __sub->_M_states._M_start = __state._M_alt;
       if (__sub->_M_search_from_first())
 	{
 	  for (size_t __i = 0; __i < __what.size(); __i++)
@@ -195,17 +198,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     };
 
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
-    bool __dfs_mode>
+	   bool __dfs_mode>
   template<bool __match_mode>
     void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
     _M_dfs(_StateIdT __i)
     {
-      if (!__dfs_mode)
-	{
-	  if ((*_M_visited)[__i])
-	    return;
-	  (*_M_visited)[__i] = true;
-	}
+      if (_M_states._M_visited(__i))
+	return;
 
       const auto& __state = _M_nfa[__i];
       // Every change on _M_cur_results and _M_current will be rolled back after
@@ -302,8 +301,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    }
 	  else
 	    if (__state._M_matches(*_M_current))
-	      _M_match_queue->push_back(make_pair(__state._M_next,
-						  _M_cur_results));
+	      _M_states._M_queue(__state._M_next, _M_cur_results);
 	  break;
 	// First fetch the matched result from _M_cur_results as __submatch;
 	// then compare it with
@@ -375,7 +373,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   // Return whether now is at some word boundary.
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
-    bool __dfs_mode>
+	   bool __dfs_mode>
     bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
     _M_word_boundary(_State<_TraitsT> __state) const
     {

Re: [patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Tim Shen]

On Mon, Apr 28, 2014 at 10:46 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
> This change splits _Executor::_M_main() into two overloaded
> _M_main_dispatch() functions, choosing which to run based on the
> __dfs_mode template parameter.
>
> I think this gives a (very) small improvement in compilation time when
> using regexes.
>
> Splitting _M_main() allows the _M_match_queue and _M_visited members
> (which are only used in BFS mode) to be replaced with an instantiation
> of the new _States class template. _States<__dfs> only contains the
> start state (so that it's not empty and doesn't waste space) but
> _States<__bfs> contains the start state and also the match queue and
> visited list.

This is great! I keep worrying about the ugly all-in-one _Executor
class; I've tried to specialize two versions of it, but that
introduced much duplicated code. Your abstract is nice!

> As the visited list never changes size after construction I changed
> its type from unique_ptr<vector<bool>> to unique_ptr<bool[]>, which
> avoids an indirection, although now that that member is only present
> when actually required it could just be vector<bool>. An array of bool
> is simpler to access, but takes more heap memory. vector<bool> uses
> less space but the compiler has to do all the masking to address
> individual bits.

What about bitset? Anyway we should get rid of vector<bool>.

> I also changed this range-based for loop in _M_main (now in
> _M_main_dispatch(__bfs)) to make __task a reference, avoiding one
> copy, and to move from __task.second, avoiding a second copy:
>
>        auto __old_queue = std::move(_M_states._M_match_queue);
>        for (auto& __task : __old_queue)
>          {
>            _M_cur_results = std::move(__task.second);
>            _M_dfs<__match_mode>(__task.first);
>          }

I didn't know why I've written the code that copys a lot. Thanks.


-- 
Regards,
Tim Shen

Re: [patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Jonathan Wakely]

On 28/04/14 11:40 -0400, Tim Shen wrote:
>On Mon, Apr 28, 2014 at 10:46 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
>> This change splits _Executor::_M_main() into two overloaded
>> _M_main_dispatch() functions, choosing which to run based on the
>> __dfs_mode template parameter.
>>
>> I think this gives a (very) small improvement in compilation time when
>> using regexes.
>>
>> Splitting _M_main() allows the _M_match_queue and _M_visited members
>> (which are only used in BFS mode) to be replaced with an instantiation
>> of the new _States class template. _States<__dfs> only contains the
>> start state (so that it's not empty and doesn't waste space) but
>> _States<__bfs> contains the start state and also the match queue and
>> visited list.
>
>This is great! I keep worrying about the ugly all-in-one _Executor
>class; I've tried to specialize two versions of it, but that
>introduced much duplicated code. Your abstract is nice!

Thanks. I'll clean up that patch and commit it soon too.

The next thing I plan to look at, which I haven't done yet, is to see
if passing the __match_mode template parameter as a runtime function
parameter makes any difference to the way the code is structuted. Do
you have any thoughts in that, before I waste time doing something
that won't work?

>> As the visited list never changes size after construction I changed
>> its type from unique_ptr<vector<bool>> to unique_ptr<bool[]>, which
>> avoids an indirection, although now that that member is only present
>> when actually required it could just be vector<bool>. An array of bool
>> is simpler to access, but takes more heap memory. vector<bool> uses
>> less space but the compiler has to do all the masking to address
>> individual bits.
>
>What about bitset? Anyway we should get rid of vector<bool>.

The size of a bitset is fixed at compile-time. If we could use
dynarray<bool> that might be nice, but we can't :-)

Re: [patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Tim Shen]

On Mon, Apr 28, 2014 at 12:51 PM, Jonathan Wakely <jwakely@redhat.com> wrote:
> The next thing I plan to look at, which I haven't done yet, is to see
> if passing the __match_mode template parameter as a runtime function
> parameter makes any difference to the way the code is structuted. Do
> you have any thoughts in that, before I waste time doing something
> that won't work?

The thing behind the template parameter is like this:

0) We have DFS and BFS executor;
1) To be DRY, I write one class for those two approaches. We have to
use some option variable (__match_mode) in a function (say
_Executor::_M_dfs) to distingush one approach from another.
2) Keep checking the flag at runtime hurts efficiency, so a template
flag is used.

However, it turns out that it's not clear that if __match_mode is
frequently asked (in _Executor::_M_main and the _S_opcode_accept
branch in _Executor::_M_dfs).

If we want to change it to a runtime flag, it should be a class
member. Otherwise we have to pass it as a function parameter all the
time, and it may waste an instruction and one byte per recursive call.
It surely make the code cleaner.

Am I premature optimizing?


-- 
Regards,
Tim Shen

Re: [patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Jonathan Wakely]

On 28/04/14 15:02 -0400, Tim Shen wrote:
>If we want to change it to a runtime flag, it should be a class
>member. Otherwise we have to pass it as a function parameter all the
>time, and it may waste an instruction and one byte per recursive call.
>It surely make the code cleaner.

Data members are accessed through the 'this' pointer, which can
require an indirection and be harder to optimise than a function
parameter.

>Am I premature optimizing?

I don't know yet - we need to measure.

My concern is that making it a template parameter causes twice as much
code to be instantiated, which makes executables bigger and can cause
more I-cache misses.

Re: [patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Tim Shen]

On Mon, Apr 28, 2014 at 3:10 PM, Jonathan Wakely <jwakely@redhat.com> wrote:
> Data members are accessed through the 'this' pointer, which can
> require an indirection and be harder to optimise than a function
> parameter.

It doesn't matter if this variable is not frequently checked. But
let's just use the function parameter and expecting compiler's
optimization.

> My concern is that making it a template parameter causes twice as much
> code to be instantiated, which makes executables bigger and can cause
> more I-cache misses.

Worth a try. Will you make the change or will I? It seems to be
simpler doing than talking.


-- 
Regards,
Tim Shen

Re: [patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 572 bytes --]

On 28/04/14 15:24 -0400, Tim Shen wrote:
>Worth a try. Will you make the change or will I? It seems to be
>simpler doing than talking.

Yes :-)

I'm testing the attached patch now. It compiles slightly faster
(-ftime-report shows, as expected, that less time is spent in template
instantiation).

I'd also like to change __match_mode from a bool to an enum like:

   enum _Match_mode { _S_exact_match, _S_prefix_match };

Because I find it easier to read something like:

   if (__match_mode == _S_exact_match)
     // ...

rather than

   if (__match_mode)
     // ...



[-- Attachment #2: re4.patch --]
[-- Type: text/plain, Size: 8325 bytes --]

diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
index 064e3df..617d1a4 100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -88,7 +88,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_match()
       {
 	_M_current = _M_begin;
-	return _M_main<true>();
+	return _M_main(true);
       }
 
       // Set matched when some prefix of the string matches the pattern.
@@ -96,33 +96,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_search_from_first()
       {
 	_M_current = _M_begin;
-	return _M_main<false>();
+	return _M_main(false);
       }
 
       bool
       _M_search();
 
     private:
-      template<bool __match_mode>
-	void
-	_M_rep_once_more(_StateIdT);
-
-      template<bool __match_mode>
-	void
-	_M_dfs(_StateIdT __start);
-
-      template<bool __match_mode>
-	bool
-	_M_main()
-	{ return _M_main_dispatch<__match_mode>(__search_mode{}); }
-
-      template<bool __match_mode>
-	bool
-	_M_main_dispatch(__dfs);
-
-      template<bool __match_mode>
-	bool
-	_M_main_dispatch(__bfs);
+      void
+      _M_rep_once_more(bool __match_mode, _StateIdT);
+
+      void
+      _M_dfs(bool __match_mode, _StateIdT __start);
+
+      bool
+      _M_main(bool __match_mode)
+      { return _M_main_dispatch(__match_mode, __search_mode{}); }
+
+      bool
+      _M_main_dispatch(bool __match_mode, __dfs);
+
+      bool
+      _M_main_dispatch(bool __match_mode, __bfs);
 
       bool
       _M_is_word(_CharT __ch) const
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
index a7351de..c0c75fa 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -45,7 +45,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       do
 	{
 	  _M_current = __cur;
-	  if (_M_main<false>())
+	  if (_M_main(false))
 	    return true;
 	}
       // Continue when __cur == _M_end
@@ -78,13 +78,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   //
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
 	   bool __dfs_mode>
-  template<bool __match_mode>
     bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
-    _M_main_dispatch(__dfs)
+    _M_main_dispatch(bool __match_mode, __dfs)
     {
       _M_has_sol = false;
       _M_cur_results = _M_results;
-      _M_dfs<__match_mode>(_M_states._M_start);
+      _M_dfs(__match_mode, _M_states._M_start);
       return _M_has_sol;
     }
 
@@ -112,9 +111,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   //                   O(_M_nfa.size() * match_results.size())
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
 	   bool __dfs_mode>
-  template<bool __match_mode>
     bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
-    _M_main_dispatch(__bfs)
+    _M_main_dispatch(bool __match_mode, __bfs)
     {
       _M_states._M_queue(_M_states._M_start, _M_results);
       bool __ret = false;
@@ -128,7 +126,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  for (auto& __task : __old_queue)
 	    {
 	      _M_cur_results = std::move(__task.second);
-	      _M_dfs<__match_mode>(__task.first);
+	      _M_dfs(__match_mode, __task.first);
 	    }
 	  if (!__match_mode)
 	    __ret |= _M_has_sol;
@@ -168,9 +166,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // we need to spare one more time for potential group capture.
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
     bool __dfs_mode>
-  template<bool __match_mode>
     void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
-    _M_rep_once_more(_StateIdT __i)
+    _M_rep_once_more(bool __match_mode, _StateIdT __i)
     {
       const auto& __state = _M_nfa[__i];
       auto& __rep_count = _M_rep_count[__i];
@@ -179,7 +176,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  auto __back = __rep_count;
 	  __rep_count.first = _M_current;
 	  __rep_count.second = 1;
-	  _M_dfs<__match_mode>(__state._M_alt);
+	  _M_dfs(__match_mode, __state._M_alt);
 	  __rep_count = __back;
 	}
       else
@@ -187,7 +184,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  if (__rep_count.second < 2)
 	    {
 	      __rep_count.second++;
-	      _M_dfs<__match_mode>(__state._M_alt);
+	      _M_dfs(__match_mode, __state._M_alt);
 	      __rep_count.second--;
 	    }
 	}
@@ -195,9 +192,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
 	   bool __dfs_mode>
-  template<bool __match_mode>
     void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
-    _M_dfs(_StateIdT __i)
+    _M_dfs(bool __match_mode, _StateIdT __i)
     {
       if (_M_states._M_visited(__i))
 	return;
@@ -216,19 +212,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    // Greedy.
 	    if (!__state._M_neg)
 	      {
-		_M_rep_once_more<__match_mode>(__i);
+		_M_rep_once_more(__match_mode, __i);
 		// If it's DFS executor and already accepted, we're done.
 		if (!__dfs_mode || !_M_has_sol)
-		  _M_dfs<__match_mode>(__state._M_next);
+		  _M_dfs(__match_mode, __state._M_next);
 	      }
 	    else // Non-greedy mode
 	      {
 		if (__dfs_mode)
 		  {
 		    // vice-versa.
-		    _M_dfs<__match_mode>(__state._M_next);
+		    _M_dfs(__match_mode, __state._M_next);
 		    if (!_M_has_sol)
-		      _M_rep_once_more<__match_mode>(__i);
+		      _M_rep_once_more(__match_mode, __i);
 		  }
 		else
 		  {
@@ -237,12 +233,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		    // better by attempting its next node.
 		    if (!_M_has_sol)
 		      {
-			_M_dfs<__match_mode>(__state._M_next);
+			_M_dfs(__match_mode, __state._M_next);
 			// DON'T attempt anything if it's already accepted. An
 			// accepted state *must* be better than a solution that
 			// matches a non-greedy quantifier one more time.
 			if (!_M_has_sol)
-			  _M_rep_once_more<__match_mode>(__i);
+			  _M_rep_once_more(__match_mode, __i);
 		      }
 		  }
 	      }
@@ -253,7 +249,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    auto& __res = _M_cur_results[__state._M_subexpr];
 	    auto __back = __res.first;
 	    __res.first = _M_current;
-	    _M_dfs<__match_mode>(__state._M_next);
+	    _M_dfs(__match_mode, __state._M_next);
 	    __res.first = __back;
 	  }
 	  break;
@@ -263,27 +259,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    auto __back = __res;
 	    __res.second = _M_current;
 	    __res.matched = true;
-	    _M_dfs<__match_mode>(__state._M_next);
+	    _M_dfs(__match_mode, __state._M_next);
 	    __res = __back;
 	  }
 	  break;
 	case _S_opcode_line_begin_assertion:
 	  if (_M_at_begin())
-	    _M_dfs<__match_mode>(__state._M_next);
+	    _M_dfs(__match_mode, __state._M_next);
 	  break;
 	case _S_opcode_line_end_assertion:
 	  if (_M_at_end())
-	    _M_dfs<__match_mode>(__state._M_next);
+	    _M_dfs(__match_mode, __state._M_next);
 	  break;
 	case _S_opcode_word_boundary:
 	  if (_M_word_boundary(__state) == !__state._M_neg)
-	    _M_dfs<__match_mode>(__state._M_next);
+	    _M_dfs(__match_mode, __state._M_next);
 	  break;
 	// Here __state._M_alt offers a single start node for a sub-NFA.
 	// We recursively invoke our algorithm to match the sub-NFA.
 	case _S_opcode_subexpr_lookahead:
 	  if (_M_lookahead(__state) == !__state._M_neg)
-	    _M_dfs<__match_mode>(__state._M_next);
+	    _M_dfs(__match_mode, __state._M_next);
 	  break;
 	case _S_opcode_match:
 	  if (__dfs_mode)
@@ -291,7 +287,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      if (_M_current != _M_end && __state._M_matches(*_M_current))
 		{
 		  ++_M_current;
-		  _M_dfs<__match_mode>(__state._M_next);
+		  _M_dfs(__match_mode, __state._M_next);
 		  --_M_current;
 		}
 	    }
@@ -322,11 +318,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		  {
 		    auto __backup = _M_current;
 		    _M_current = __last;
-		    _M_dfs<__match_mode>(__state._M_next);
+		    _M_dfs(__match_mode, __state._M_next);
 		    _M_current = __backup;
 		  }
 		else
-		  _M_dfs<__match_mode>(__state._M_next);
+		  _M_dfs(__match_mode, __state._M_next);
 	      }
 	  }
 	  break;
@@ -358,9 +354,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    }
 	  break;
 	case _S_opcode_alternative:
-	  _M_dfs<__match_mode>(__state._M_alt);
+	  _M_dfs(__match_mode, __state._M_alt);
 	  if (!__dfs_mode || !_M_has_sol)
-	    _M_dfs<__match_mode>(__state._M_next);
+	    _M_dfs(__match_mode, __state._M_next);
 	  break;
 	default:
 	  _GLIBCXX_DEBUG_ASSERT(false);

Re: [patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Tim Shen]

On Mon, Apr 28, 2014 at 3:29 PM, Jonathan Wakely <jwakely@redhat.com> wrote:
> I'm testing the attached patch now. It compiles slightly faster
> (-ftime-report shows, as expected, that less time is spent in template
> instantiation).
>
> I'd also like to change __match_mode from a bool to an enum like:
>
>   enum _Match_mode { _S_exact_match, _S_prefix_match };
>
> Because I find it easier to read something like:
>
>   if (__match_mode == _S_exact_match)
>     // ...
>
> rather than
>
>   if (__match_mode)
>     // ...

Oh this is nice, good to know.

Thanks!


-- 
Regards,
Tim Shen

Re: [patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Jonathan Wakely]

I thought I'd make a 5x speedup to the run-time of the regex matching,
but I was comparing the wrong version and the improvement actually
came from one of your patches yesterday - maybe this one:
http://gcc.gnu.org/ml/gcc-patches/2014-04/msg01725.html

Nice work!

My changes don't seem to make anything worse, and the first one makes
a big improvement to the worst case performance of std::wregex.

Re: [patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Tim Shen]

On Mon, Apr 28, 2014 at 4:18 PM, Jonathan Wakely <jwakely@redhat.com> wrote:
> I thought I'd make a 5x speedup to the run-time of the regex matching,
> but I was comparing the wrong version and the improvement actually
> came from one of your patches yesterday - maybe this one:
> http://gcc.gnu.org/ml/gcc-patches/2014-04/msg01725.html
>
> Nice work!

That's surprising. May I ask for the performance testcase?

> My changes don't seem to make anything worse, and the first one makes
> a big improvement to the worst case performance of std::wregex.

Glad to see that!

Thanks!


-- 
Regards,
Tim Shen

Re: [patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Jonathan Wakely]

On 28/04/14 17:14 -0400, Tim Shen wrote:
>On Mon, Apr 28, 2014 at 4:18 PM, Jonathan Wakely <jwakely@redhat.com> wrote:
>> I thought I'd make a 5x speedup to the run-time of the regex matching,
>> but I was comparing the wrong version and the improvement actually
>> came from one of your patches yesterday - maybe this one:
>> http://gcc.gnu.org/ml/gcc-patches/2014-04/msg01725.html
>>
>> Nice work!
>
>That's surprising. May I ask for the performance testcase?

See below. These are just microbenchmarks, so not very good or
reliable, but the <regex> code is large enough and complicated enough
that the results are fairly consistent and reproducible.
(I use __builtin_printf and __builtin_puts when I'm too lazy to
include a file, there's no other reason for that!)

I was using something like this to test basic_regex<char>:

#include <regex>

int main()
{
   auto re = std::regex("[abc]{3}d*x?");
   int count = 0;
   for (int i = 0; i < 100000; ++i)
     if (std::regex_match("bab", re)
         && std::regex_search("aacdddddddddddddddddddddddxaa", re))
       ++count;
   __builtin_printf("%d\n", count);
}

This runs much faster on trunk than with 4.9.0, so we might want to
backport your recent patches to the gcc-4_9-branch.

I was using examples like this for testing _BracketMatcher with
basic_regex<wchar_t>

#include <regex>

int main()
{
   auto re = std::wregex(L'[' + std::wstring(300, L'a') + L"bc"
                         + std::wstring(1000, 'a') + L"d]");
   int count = 0;
   for (int i = 0; i < 100000; ++i)
     if (std::regex_match(L"b", re) && std::regex_match(L"d", re))
       ++count;
   __builtin_printf("%d\n", count);
}

This runs faster with my patch to use std::sort and std::unique on the
_M_char_set vector, because the regex compiles to be equivalent to
std::wregex(L"[abcd]")

Re: [patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Tim Shen]

On Tue, Apr 29, 2014 at 6:17 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
> This runs much faster on trunk than with 4.9.0, so we might want to
> backport your recent patches to the gcc-4_9-branch.

It's faster but nothing to do with optimization. It's because my first
patch set the DFS approach by default, which is faster in common case
but has bad worst case performance. Try your testcase and
regex_match("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", regex("(a*){30}"))
with/without defining _GLIBCXX_REGEX_USE_THOMPSON_NFA in the trunk
version.


-- 
Regards,
Tim Shen

Re: [patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Jonathan Wakely]

On 29/04/14 12:54 -0400, Tim Shen wrote:
>On Tue, Apr 29, 2014 at 6:17 AM, Jonathan Wakely <jwakely@redhat.com> wrote:
>> This runs much faster on trunk than with 4.9.0, so we might want to
>> backport your recent patches to the gcc-4_9-branch.
>
>It's faster but nothing to do with optimization. It's because my first
>patch set the DFS approach by default, which is faster in common case
>but has bad worst case performance. Try your testcase and
>regex_match("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", regex("(a*){30}"))
>with/without defining _GLIBCXX_REGEX_USE_THOMPSON_NFA in the trunk
>version.

Ah yes, of course ... but that's still a nice improvement for people
using a regex with no back references (at least for the common cases).

Re: [patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Paolo Carlini]

.. are we going to add some of these (micro-)benchmarks to the 
performance testsuite, yes? ;)

Paolo.

Re: [patch 3/N] std::regex refactoring - _Executor DFS / BFS

[Tim Shen]

On Tue, Apr 29, 2014 at 1:25 PM, Paolo Carlini <paolo.carlini@oracle.com> wrote:
> .. are we going to add some of these (micro-)benchmarks to the performance
> testsuite, yes? ;)

I think the wregex one is great :)


-- 
Regards,
Tim Shen

Re: [patch 1/N] std::regex refactoring - _BracketMatcher

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 131 bytes --]

I'm committing the attached patch, combining the various patches we
discussed in April.

Tested x86_64-linux, committed to trunk.


[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 29952 bytes --]

commit f8e0936df9cdc31460bb79ac82f43486967983b1
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue Apr 8 16:24:56 2014 +0100

    	* include/bits/regex_compiler.h (__detail::_BracketMatcher): Reorder
    	members to avoid wasted space when not using a cache.
    	(__detail::_BracketMatcher::_M_ready()): Sort and deduplicate set.
    	* include/bits/regex_compiler.tcc
    	(__detail::_BracketMatcher::_M_apply(_CharT, false_type)): Use binary
    	search on set.
    	* include/bits/regex_executor.h (__detail::_Executor::_Match_mode):
    	New enumeration type to indicate match mode.
    	(__detail::_Executor::_State_info): New type holding members only
    	needed in BFS-mode. Replace unique_ptr<vector<bool>> with
    	unique_ptr<bool[]>.
    	(__detail::_Executor::_M_rep_once_more, __detail::_Executor::_M_dfs):
    	Replace template parameter with run-time function parameter.
    	(__detail::_Executor::_M_main): Likewise. Dispatch to ...
    	(__detail::_Executor::_M_main_dispatch): New overloaded functions to
    	implement DFS and BFS mode.
    	* include/bits/regex_executor.tcc (__detail::_Executor::_M_main):
    	Split implementation into ...
    	(__detail::_Executor::_M_main_dispatch): New overloaded functions.
    	(__detail::_Executor::_M_lookahead): Create nested executor on stack.
    	(__detail::_Executor::_M_rep_once_more): Pass match mode as function
    	argument instead of template argument.
    	(__detail::_Executor::_M_dfs): Likewise.
    	* include/bits/regex_scanner.tcc: Fix typos in comments.
    	* testsuite/performance/28_regex/range.cc: New.

diff --git a/libstdc++-v3/include/bits/regex.tcc b/libstdc++-v3/include/bits/regex.tcc
index 0d737a0..a81f517 100644
--- a/libstdc++-v3/include/bits/regex.tcc
+++ b/libstdc++-v3/include/bits/regex.tcc
@@ -32,7 +32,7 @@
 // If _GLIBCXX_REGEX_USE_THOMPSON_NFA is defined, the thompson NFA
 // algorithm will be used. This algorithm is not enabled by default,
 // and cannot be used if the regex contains back-references, but has better
-// (polynomial instead of exponential) worst case performace.
+// (polynomial instead of exponential) worst case performance.
 // See __regex_algo_impl below.
 
 namespace std _GLIBCXX_VISIBILITY(default)
diff --git a/libstdc++-v3/include/bits/regex_compiler.h b/libstdc++-v3/include/bits/regex_compiler.h
index 52f7235..ca116de 100644
--- a/libstdc++-v3/include/bits/regex_compiler.h
+++ b/libstdc++-v3/include/bits/regex_compiler.h
@@ -43,7 +43,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     struct _BracketMatcher;
 
   /**
-   * @brief Builds an NFA from an input iterator interval.
+   * @brief Builds an NFA from an input iterator range.
    *
    * The %_TraitsT type should fulfill requirements [28.3].
    */
@@ -329,7 +329,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       operator()(_CharT __ch) const
       {
 	_GLIBCXX_DEBUG_ASSERT(_M_is_ready);
-	return _M_apply(__ch, _IsChar());
+	return _M_apply(__ch, _UseCache());
       }
 
       void
@@ -400,21 +400,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       _M_ready()
       {
-	_M_make_cache(_IsChar());
+	std::sort(_M_char_set.begin(), _M_char_set.end());
+	auto __end = std::unique(_M_char_set.begin(), _M_char_set.end());
+	_M_char_set.erase(__end, _M_char_set.end());
+	_M_make_cache(_UseCache());
 #ifdef _GLIBCXX_DEBUG
 	_M_is_ready = true;
 #endif
       }
 
     private:
-      typedef typename is_same<_CharT, char>::type _IsChar;
+      // Currently we only use the cache for char
+      typedef typename std::is_same<_CharT, char>::type _UseCache;
+
+      static constexpr size_t
+      _S_cache_size() { return 1ul << (sizeof(_CharT) * __CHAR_BIT__); }
+
       struct _Dummy { };
-      typedef typename conditional<_IsChar::value,
-				   std::bitset<1 << (8 * sizeof(_CharT))>,
-				   _Dummy>::type _CacheT;
-      typedef typename make_unsigned<_CharT>::type _UnsignedCharT;
+      typedef typename std::conditional<_UseCache::value,
+					std::bitset<_S_cache_size()>,
+					_Dummy>::type _CacheT;
+      typedef typename std::make_unsigned<_CharT>::type _UnsignedCharT;
 
-    private:
       bool
       _M_apply(_CharT __ch, false_type) const;
 
@@ -425,9 +432,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       void
       _M_make_cache(true_type)
       {
-	for (size_t __i = 0; __i < _M_cache.size(); __i++)
-	  _M_cache[static_cast<_UnsignedCharT>(__i)] =
-	    _M_apply(__i, false_type());
+	for (unsigned __i = 0; __i < _M_cache.size(); __i++)
+	  _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type());
       }
 
       void
@@ -435,7 +441,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { }
 
     private:
-      _CacheT                                   _M_cache;
       std::vector<_CharT>                       _M_char_set;
       std::vector<_StringT>                     _M_equiv_set;
       std::vector<pair<_StrTransT, _StrTransT>> _M_range_set;
@@ -444,6 +449,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _TransT                                   _M_translator;
       const _TraitsT&                           _M_traits;
       bool                                      _M_is_non_matching;
+      _CacheT					_M_cache;
 #ifdef _GLIBCXX_DEBUG
       bool                                      _M_is_ready;
 #endif
diff --git a/libstdc++-v3/include/bits/regex_compiler.tcc b/libstdc++-v3/include/bits/regex_compiler.tcc
index 472cf1f..0df10cc 100644
--- a/libstdc++-v3/include/bits/regex_compiler.tcc
+++ b/libstdc++-v3/include/bits/regex_compiler.tcc
@@ -37,9 +37,9 @@
 // When compiling, states are *chained* instead of tree- or graph-constructed.
 // It's more like structured programs: there's if statement and loop statement.
 //
-// For alternative structure(say "a|b"), aka "if statement", two branchs should
-// be constructed. However, these two shall merge to an "end_tag" at the end of
-// this operator:
+// For alternative structure (say "a|b"), aka "if statement", two branches
+// should be constructed. However, these two shall merge to an "end_tag" at
+// the end of this operator:
 //
 //                branch1
 //              /        \
@@ -151,7 +151,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       else if (_M_match_token(_ScannerT::_S_token_line_end))
 	_M_stack.push(_StateSeqT(_M_nfa, _M_nfa._M_insert_line_end()));
       else if (_M_match_token(_ScannerT::_S_token_word_bound))
-	// _M_value[0] == 'n' means it's negtive, say "not word boundary".
+	// _M_value[0] == 'n' means it's negative, say "not word boundary".
 	_M_stack.push(_StateSeqT(_M_nfa, _M_nfa.
 	      _M_insert_word_bound(_M_value[0] == 'n')));
       else if (_M_match_token(_ScannerT::_S_token_subexpr_lookahead_begin))
@@ -256,7 +256,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      auto __end = _M_nfa._M_insert_dummy();
 	      // _M_alt is the "match more" branch, and _M_next is the
 	      // "match less" one. Switch _M_alt and _M_next of all created
-	      // nodes. This is a hacking but IMO works well.
+	      // nodes. This is a hack but IMO works well.
 	      std::stack<_StateIdT> __stack;
 	      for (long __i = 0; __i < __n; ++__i)
 		{
@@ -511,12 +511,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _BracketMatcher<_TraitsT, __icase, __collate>::
     _M_apply(_CharT __ch, false_type) const
     {
-      bool __ret = false;
-      if (std::find(_M_char_set.begin(), _M_char_set.end(),
-		    _M_translator._M_translate(__ch))
-	  != _M_char_set.end())
-	__ret = true;
-      else
+      bool __ret = std::binary_search(_M_char_set.begin(), _M_char_set.end(),
+				      _M_translator._M_translate(__ch));
+      if (!__ret)
 	{
 	  auto __s = _M_translator._M_transform(__ch);
 	  for (auto& __it : _M_range_set)
diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
index c110b88..1991c00 100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -42,8 +42,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    */
 
   /**
-   * @brief Takes a regex and an input string in and
-   * do the matching.
+   * @brief Takes a regex and an input string and does the matching.
    *
    * The %_Executor class has two modes: DFS mode and BFS mode, controlled
    * by the template parameter %__dfs_mode.
@@ -52,6 +51,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   bool __dfs_mode>
     class _Executor
     {
+      using __search_mode = integral_constant<bool, __dfs_mode>;
+      using __dfs = true_type;
+      using __bfs = false_type;
+
+      enum class _Match_mode : unsigned char { _Exact, _Prefix };
+
     public:
       typedef typename iterator_traits<_BiIter>::value_type _CharT;
       typedef basic_regex<_CharT, _TraitsT>                 _RegexT;
@@ -71,24 +76,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_re(__re),
       _M_nfa(*__re._M_automaton),
       _M_results(__results),
-      _M_match_queue(__dfs_mode ? nullptr
-		     : new vector<pair<_StateIdT, _ResultsVec>>()),
       _M_rep_count(_M_nfa.size()),
-      _M_visited(__dfs_mode ? nullptr : new vector<bool>(_M_nfa.size())),
+      _M_states(_M_nfa._M_start(), _M_nfa.size()),
       _M_flags((__flags & regex_constants::match_prev_avail)
 	       ? (__flags
 		  & ~regex_constants::match_not_bol
 		  & ~regex_constants::match_not_bow)
-	       : __flags),
-      _M_start_state(_M_nfa._M_start())
+	       : __flags)
       { }
 
-      // Set matched when string exactly match the pattern.
+      // Set matched when string exactly matches the pattern.
       bool
       _M_match()
       {
 	_M_current = _M_begin;
-	return _M_main<true>();
+	return _M_main(_Match_mode::_Exact);
       }
 
       // Set matched when some prefix of the string matches the pattern.
@@ -96,24 +98,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _M_search_from_first()
       {
 	_M_current = _M_begin;
-	return _M_main<false>();
+	return _M_main(_Match_mode::_Prefix);
       }
 
       bool
       _M_search();
 
     private:
-      template<bool __match_mode>
-	void
-	_M_rep_once_more(_StateIdT);
+      void
+      _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
 
-      template<bool __match_mode>
-	void
-	_M_dfs(_StateIdT __start);
+      void
+      _M_dfs(_Match_mode __match_mode, _StateIdT __start);
 
-      template<bool __match_mode>
-	bool
-	_M_main();
+      bool
+      _M_main(_Match_mode __match_mode)
+      { return _M_main_dispatch(__match_mode, __search_mode{}); }
+
+      bool
+      _M_main_dispatch(_Match_mode __match_mode, __dfs);
+
+      bool
+      _M_main_dispatch(_Match_mode __match_mode, __bfs);
 
       bool
       _M_is_word(_CharT __ch) const
@@ -144,6 +150,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       bool
       _M_lookahead(_State<_TraitsT> __state);
 
+       // Holds additional information used in BFS-mode.
+      template<typename _SearchMode, typename _ResultsVec>
+	struct _State_info;
+
+      template<typename _ResultsVec>
+	struct _State_info<__bfs, _ResultsVec>
+	{
+	  explicit
+	  _State_info(_StateIdT __start, size_t __n)
+	  : _M_start(__start), _M_visited_states(new bool[__n]())
+	  { }
+
+	  bool _M_visited(_StateIdT __i)
+	  {
+	    if (_M_visited_states[__i])
+	      return true;
+	    _M_visited_states[__i] = true;
+	    return false;
+	  }
+
+	  void _M_queue(_StateIdT __i, const _ResultsVec& __res)
+	  { _M_match_queue.emplace_back(__i, __res); }
+
+	  // Saves states that need to be considered for the next character.
+	  vector<pair<_StateIdT, _ResultsVec>>	_M_match_queue;
+	  // Indicates which states are already visited.
+	  unique_ptr<bool[]>			_M_visited_states;
+	  // To record current solution.
+	  _StateIdT _M_start;
+	};
+
+      template<typename _ResultsVec>
+	struct _State_info<__dfs, _ResultsVec>
+	{
+	  explicit
+	  _State_info(_StateIdT __start, size_t) : _M_start(__start)
+	  { }
+
+	  // Dummy implementations for DFS mode.
+	  bool _M_visited(_StateIdT) const { return false; }
+	  void _M_queue(_StateIdT, const _ResultsVec&) { }
+
+	  // To record current solution.
+	  _StateIdT _M_start;
+	};
+
+
     public:
       _ResultsVec                                           _M_cur_results;
       _BiIter                                               _M_current;
@@ -152,15 +205,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       const _RegexT&                                        _M_re;
       const _NFAT&                                          _M_nfa;
       _ResultsVec&                                          _M_results;
-      // Used in BFS, saving states that need to be considered for the next
-      // character.
-      unique_ptr<vector<pair<_StateIdT, _ResultsVec>>>      _M_match_queue;
-      // Used in BFS, indicating that which state is already visited.
       vector<pair<_BiIter, int>>                            _M_rep_count;
-      unique_ptr<vector<bool>>                              _M_visited;
+      _State_info<__search_mode, _ResultsVec>		    _M_states;
       _FlagT                                                _M_flags;
-      // To record current solution.
-      _StateIdT                                             _M_start_state;
       // Do we have a solution so far?
       bool                                                  _M_has_sol;
     };
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
index 7f89933..aefa8f4 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -35,7 +35,7 @@ namespace __detail
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
-    bool __dfs_mode>
+	   bool __dfs_mode>
     bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
     _M_search()
     {
@@ -45,7 +45,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       do
 	{
 	  _M_current = __cur;
-	  if (_M_main<false>())
+	  if (_M_main(_Match_mode::_Prefix))
 	    return true;
 	}
       // Continue when __cur == _M_end
@@ -53,8 +53,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return false;
     }
 
-  // This function operates in different modes, DFS mode or BFS mode, indicated
-  // by template parameter __dfs_mode. See _M_main for details.
+  // The _M_main function operates in different modes, DFS mode or BFS mode,
+  // indicated by template parameter __dfs_mode, and dispatches to one of the
+  // _M_main_dispatch overloads.
   //
   // ------------------------------------------------------------
   //
@@ -62,12 +63,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   //
   // It applies a Depth-First-Search (aka backtracking) on given NFA and input
   // string.
-  // At the very beginning the executor stands in the start state, then it tries
-  // every possible state transition in current state recursively. Some state
-  // transitions consume input string, say, a single-char-matcher or a
+  // At the very beginning the executor stands in the start state, then it
+  // tries every possible state transition in current state recursively. Some
+  // state transitions consume input string, say, a single-char-matcher or a
   // back-reference matcher; some don't, like assertion or other anchor nodes.
-  // When the input is exhausted and/or the current state is an accepting state,
-  // the whole executor returns true.
+  // When the input is exhausted and/or the current state is an accepting
+  // state, the whole executor returns true.
   //
   // TODO: This approach is exponentially slow for certain input.
   //       Try to compile the NFA to a DFA.
@@ -75,6 +76,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // Time complexity: \Omega(match_length), O(2^(_M_nfa.size()))
   // Space complexity: \theta(match_results.size() + match_length)
   //
+  template<typename _BiIter, typename _Alloc, typename _TraitsT,
+	   bool __dfs_mode>
+    bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
+    _M_main_dispatch(_Match_mode __match_mode, __dfs)
+    {
+      _M_has_sol = false;
+      _M_cur_results = _M_results;
+      _M_dfs(__match_mode, _M_states._M_start);
+      return _M_has_sol;
+    }
+
   // ------------------------------------------------------------
   //
   // BFS mode:
@@ -84,11 +96,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   //
   // It first computes epsilon closure (states that can be achieved without
   // consuming characters) for every state that's still matching,
-  // using the same DFS algorithm, but doesn't re-enter states (find a true in
-  // _M_visited), nor follows _S_opcode_match.
+  // using the same DFS algorithm, but doesn't re-enter states (using
+  // _M_states._M_visited to check), nor follow _S_opcode_match.
   //
-  // Then apply DFS using every _S_opcode_match (in _M_match_queue) as the start
-  // state.
+  // Then apply DFS using every _S_opcode_match (in _M_states._M_match_queue)
+  // as the start state.
   //
   // It significantly reduces potential duplicate states, so has a better
   // upper bound; but it requires more overhead.
@@ -98,60 +110,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // Space complexity: \Omega(_M_nfa.size() + match_results.size())
   //                   O(_M_nfa.size() * match_results.size())
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
-    bool __dfs_mode>
-  template<bool __match_mode>
+	   bool __dfs_mode>
     bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
-    _M_main()
+    _M_main_dispatch(_Match_mode __match_mode, __bfs)
     {
-      if (__dfs_mode)
+      _M_states._M_queue(_M_states._M_start, _M_results);
+      bool __ret = false;
+      while (1)
 	{
 	  _M_has_sol = false;
-	  _M_cur_results = _M_results;
-	  _M_dfs<__match_mode>(_M_start_state);
-	  return _M_has_sol;
-	}
-      else
-	{
-	  _M_match_queue->push_back(make_pair(_M_start_state, _M_results));
-	  bool __ret = false;
-	  while (1)
+	  if (_M_states._M_match_queue.empty())
+	    break;
+	  std::fill_n(_M_states._M_visited_states.get(), _M_nfa.size(), false);
+	  auto __old_queue = std::move(_M_states._M_match_queue);
+	  for (auto& __task : __old_queue)
 	    {
-	      _M_has_sol = false;
-	      if (_M_match_queue->empty())
-		break;
-	      _M_visited->assign(_M_visited->size(), false);
-	      auto _M_old_queue = std::move(*_M_match_queue);
-	      for (auto __task : _M_old_queue)
-		{
-		  _M_cur_results = __task.second;
-		  _M_dfs<__match_mode>(__task.first);
-		}
-	      if (!__match_mode)
-		__ret |= _M_has_sol;
-	      if (_M_current == _M_end)
-		break;
-	      ++_M_current;
+	      _M_cur_results = std::move(__task.second);
+	      _M_dfs(__match_mode, __task.first);
 	    }
-	  if (__match_mode)
-	    __ret = _M_has_sol;
-	  return __ret;
+	  if (__match_mode == _Match_mode::_Prefix)
+	    __ret |= _M_has_sol;
+	  if (_M_current == _M_end)
+	    break;
+	  ++_M_current;
 	}
+      if (__match_mode == _Match_mode::_Exact)
+	__ret = _M_has_sol;
+      return __ret;
     }
 
   // Return whether now match the given sub-NFA.
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
-    bool __dfs_mode>
+	   bool __dfs_mode>
     bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
     _M_lookahead(_State<_TraitsT> __state)
     {
       _ResultsVec __what(_M_cur_results.size());
-      auto __sub = std::unique_ptr<_Executor>(new _Executor(_M_current,
-							    _M_end,
-							    __what,
-							    _M_re,
-							    _M_flags));
-      __sub->_M_start_state = __state._M_alt;
-      if (__sub->_M_search_from_first())
+      _Executor __sub(_M_current, _M_end, __what, _M_re, _M_flags);
+      __sub._M_states._M_start = __state._M_alt;
+      if (__sub._M_search_from_first())
 	{
 	  for (size_t __i = 0; __i < __what.size(); __i++)
 	    if (__what[__i].matched)
@@ -169,9 +166,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   // we need to spare one more time for potential group capture.
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
     bool __dfs_mode>
-  template<bool __match_mode>
     void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
-    _M_rep_once_more(_StateIdT __i)
+    _M_rep_once_more(_Match_mode __match_mode, _StateIdT __i)
     {
       const auto& __state = _M_nfa[__i];
       auto& __rep_count = _M_rep_count[__i];
@@ -180,7 +176,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  auto __back = __rep_count;
 	  __rep_count.first = _M_current;
 	  __rep_count.second = 1;
-	  _M_dfs<__match_mode>(__state._M_alt);
+	  _M_dfs(__match_mode, __state._M_alt);
 	  __rep_count = __back;
 	}
       else
@@ -188,24 +184,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  if (__rep_count.second < 2)
 	    {
 	      __rep_count.second++;
-	      _M_dfs<__match_mode>(__state._M_alt);
+	      _M_dfs(__match_mode, __state._M_alt);
 	      __rep_count.second--;
 	    }
 	}
     };
 
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
-    bool __dfs_mode>
-  template<bool __match_mode>
+	   bool __dfs_mode>
     void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
-    _M_dfs(_StateIdT __i)
+    _M_dfs(_Match_mode __match_mode, _StateIdT __i)
     {
-      if (!__dfs_mode)
-	{
-	  if ((*_M_visited)[__i])
-	    return;
-	  (*_M_visited)[__i] = true;
-	}
+      if (_M_states._M_visited(__i))
+	return;
 
       const auto& __state = _M_nfa[__i];
       // Every change on _M_cur_results and _M_current will be rolled back after
@@ -221,33 +212,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    // Greedy.
 	    if (!__state._M_neg)
 	      {
-		_M_rep_once_more<__match_mode>(__i);
+		_M_rep_once_more(__match_mode, __i);
 		// If it's DFS executor and already accepted, we're done.
 		if (!__dfs_mode || !_M_has_sol)
-		  _M_dfs<__match_mode>(__state._M_next);
+		  _M_dfs(__match_mode, __state._M_next);
 	      }
 	    else // Non-greedy mode
 	      {
 		if (__dfs_mode)
 		  {
 		    // vice-versa.
-		    _M_dfs<__match_mode>(__state._M_next);
+		    _M_dfs(__match_mode, __state._M_next);
 		    if (!_M_has_sol)
-		      _M_rep_once_more<__match_mode>(__i);
+		      _M_rep_once_more(__match_mode, __i);
 		  }
 		else
 		  {
 		    // DON'T attempt anything, because there's already another
-		    // state with higher priority accepted. This state cannot be
-		    // better by attempting its next node.
+		    // state with higher priority accepted. This state cannot
+		    // be better by attempting its next node.
 		    if (!_M_has_sol)
 		      {
-			_M_dfs<__match_mode>(__state._M_next);
+			_M_dfs(__match_mode, __state._M_next);
 			// DON'T attempt anything if it's already accepted. An
 			// accepted state *must* be better than a solution that
 			// matches a non-greedy quantifier one more time.
 			if (!_M_has_sol)
-			  _M_rep_once_more<__match_mode>(__i);
+			  _M_rep_once_more(__match_mode, __i);
 		      }
 		  }
 	      }
@@ -258,7 +249,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    auto& __res = _M_cur_results[__state._M_subexpr];
 	    auto __back = __res.first;
 	    __res.first = _M_current;
-	    _M_dfs<__match_mode>(__state._M_next);
+	    _M_dfs(__match_mode, __state._M_next);
 	    __res.first = __back;
 	  }
 	  break;
@@ -268,27 +259,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    auto __back = __res;
 	    __res.second = _M_current;
 	    __res.matched = true;
-	    _M_dfs<__match_mode>(__state._M_next);
+	    _M_dfs(__match_mode, __state._M_next);
 	    __res = __back;
 	  }
 	  break;
 	case _S_opcode_line_begin_assertion:
 	  if (_M_at_begin())
-	    _M_dfs<__match_mode>(__state._M_next);
+	    _M_dfs(__match_mode, __state._M_next);
 	  break;
 	case _S_opcode_line_end_assertion:
 	  if (_M_at_end())
-	    _M_dfs<__match_mode>(__state._M_next);
+	    _M_dfs(__match_mode, __state._M_next);
 	  break;
 	case _S_opcode_word_boundary:
 	  if (_M_word_boundary(__state) == !__state._M_neg)
-	    _M_dfs<__match_mode>(__state._M_next);
+	    _M_dfs(__match_mode, __state._M_next);
 	  break;
 	// Here __state._M_alt offers a single start node for a sub-NFA.
 	// We recursively invoke our algorithm to match the sub-NFA.
 	case _S_opcode_subexpr_lookahead:
 	  if (_M_lookahead(__state) == !__state._M_neg)
-	    _M_dfs<__match_mode>(__state._M_next);
+	    _M_dfs(__match_mode, __state._M_next);
 	  break;
 	case _S_opcode_match:
 	  if (__dfs_mode)
@@ -296,14 +287,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      if (_M_current != _M_end && __state._M_matches(*_M_current))
 		{
 		  ++_M_current;
-		  _M_dfs<__match_mode>(__state._M_next);
+		  _M_dfs(__match_mode, __state._M_next);
 		  --_M_current;
 		}
 	    }
 	  else
 	    if (__state._M_matches(*_M_current))
-	      _M_match_queue->push_back(make_pair(__state._M_next,
-						  _M_cur_results));
+	      _M_states._M_queue(__state._M_next, _M_cur_results);
 	  break;
 	// First fetch the matched result from _M_cur_results as __submatch;
 	// then compare it with
@@ -328,11 +318,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		  {
 		    auto __backup = _M_current;
 		    _M_current = __last;
-		    _M_dfs<__match_mode>(__state._M_next);
+		    _M_dfs(__match_mode, __state._M_next);
 		    _M_current = __backup;
 		  }
 		else
-		  _M_dfs<__match_mode>(__state._M_next);
+		  _M_dfs(__match_mode, __state._M_next);
 	      }
 	  }
 	  break;
@@ -340,7 +330,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  if (__dfs_mode)
 	    {
 	      _GLIBCXX_DEBUG_ASSERT(!_M_has_sol);
-	      if (__match_mode)
+	      if (__match_mode == _Match_mode::_Exact)
 		_M_has_sol = _M_current == _M_end;
 	      else
 		_M_has_sol = true;
@@ -355,7 +345,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      if (_M_current == _M_begin
 		  && (_M_flags & regex_constants::match_not_null))
 		break;
-	      if (!__match_mode || _M_current == _M_end)
+	      if (__match_mode == _Match_mode::_Prefix || _M_current == _M_end)
 		if (!_M_has_sol)
 		  {
 		    _M_has_sol = true;
@@ -364,9 +354,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    }
 	  break;
 	case _S_opcode_alternative:
-	  _M_dfs<__match_mode>(__state._M_alt);
+	  _M_dfs(__match_mode, __state._M_alt);
 	  if (!__dfs_mode || !_M_has_sol)
-	    _M_dfs<__match_mode>(__state._M_next);
+	    _M_dfs(__match_mode, __state._M_next);
 	  break;
 	default:
 	  _GLIBCXX_DEBUG_ASSERT(false);
@@ -375,7 +365,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   // Return whether now is at some word boundary.
   template<typename _BiIter, typename _Alloc, typename _TraitsT,
-    bool __dfs_mode>
+	   bool __dfs_mode>
     bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
     _M_word_boundary(_State<_TraitsT> __state) const
     {
diff --git a/libstdc++-v3/include/bits/regex_scanner.tcc b/libstdc++-v3/include/bits/regex_scanner.tcc
index f501ff6..818e47b 100644
--- a/libstdc++-v3/include/bits/regex_scanner.tcc
+++ b/libstdc++-v3/include/bits/regex_scanner.tcc
@@ -227,14 +227,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    }
 	}
       // In POSIX, when encountering "[]" or "[^]", the ']' is interpreted
-      // literally. So "[]]" or "[^]]" is valid regex. See the testcases
+      // literally. So "[]]" and "[^]]" are valid regexes. See the testcases
       // `*/empty_range.cc`.
       else if (__c == ']' && (_M_is_ecma() || !_M_at_bracket_start))
 	{
 	  _M_token = _S_token_bracket_end;
 	  _M_state = _S_state_normal;
 	}
-      // ECMAScirpt and awk permmits escaping in bracket.
+      // ECMAScript and awk permits escaping in bracket.
       else if (__c == '\\' && (_M_is_ecma() || _M_is_awk()))
 	(this->*_M_eat_escape)();
       else
@@ -344,7 +344,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    }
 	  _M_token = _S_token_hex_num;
 	}
-      // ECMAScript recongnizes multi-digit back-references.
+      // ECMAScript recognizes multi-digit back-references.
       else if (_M_ctype.is(_CtypeT::digit, __c))
 	{
 	  _M_value.assign(1, __c);
@@ -392,6 +392,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       else
 	{
 #ifdef __STRICT_ANSI__
+	  // POSIX says it is undefined to escape ordinary characters
 	  __throw_regex_error(regex_constants::error_escape);
 #else
 	  _M_token = _S_token_ord_char;
@@ -435,8 +436,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__throw_regex_error(regex_constants::error_escape);
     }
 
-  // Eats a character class or throwns an exception.
-  // __ch cound be ':', '.' or '=', _M_current is the char after ']' when
+  // Eats a character class or throws an exception.
+  // __ch could be ':', '.' or '=', _M_current is the char after ']' when
   // returning.
   template<typename _CharT>
     void
diff --git a/libstdc++-v3/testsuite/performance/28_regex/range.cc b/libstdc++-v3/testsuite/performance/28_regex/range.cc
new file mode 100644
index 0000000..891cc2e
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/28_regex/range.cc
@@ -0,0 +1,41 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <regex>
+#include <testsuite_performance.h>
+
+using namespace __gnu_test;
+
+int main()
+{
+  time_counter time;
+  resource_counter resource;
+
+  start_counters(time, resource);
+
+  // this should get compiled to just L"[abcd]"
+  auto re = std::wregex(L'[' + std::wstring(300, L'a') + L"bc"
+                        + std::wstring(1000, 'a') + L"d]");
+  bool ok = true;
+  for (int i = 0; i < 100000; ++i)
+    ok = ok && (std::regex_match(L"b", re) && std::regex_match(L"d", re));
+
+  stop_counters(time, resource);
+  report_performance(__FILE__, "", time, resource);
+
+  return ok ? 0 : 1;
+}