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?
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 {