<regex>: Implement small buffer optimization for capture groups#6127
Conversation
| _Tgt_state._Grp_valid._Clear_range_at_least_until( | ||
| _Capture_first, _Capture_back + 1U); |
There was a problem hiding this comment.
This call might clear bits beyond _Capture_back. But this is fine here, because all of these bits must already be unset in ECMAScript grammars due to the rule that capture groups are reset when repeating a subexpression. Other grammars don't have lookahead assertions.
| _Offset = 0U; | ||
| _Buf_size = 0U; | ||
| } | ||
| } |
There was a problem hiding this comment.
This protects against user-defined iterator types with an alignment of 8192. (Or bigger: MSVC errors on such an alignment, but Clang in general supports it; I haven't tried Clang-imitating-MSVC.)
It also ensures correct behavior if the buffer is changed to have a size that is not a power-of-two.
StephanTLavavej
added
performance
| return _Data._First[_Pos]; | ||
| } | ||
|
|
||
| _NODISCARD _Ty* _Begin() { |
There was a problem hiding this comment.
I believe it's conforming to use pretty names begin, end, and size, which is somehow similar to type and value in internal type traits.
Do we want to deliberately make this not a range type?
There was a problem hiding this comment.
I suppose it could be nice to use range-for, algorithms, etc. so I would have no objection to making an exception to our usual rule that type and value are the only pretty names we take. That said, if we don't need to do that now, I also wouldn't go out of my way to make the exception pre-emptively.
|
I'm mirroring this to the MSVC-internal repo. Please notify me if any further changes are pushed, otherwise no action is required. |
4 participants
Towards #5969.
This implements small buffer optimizations for capture group ranges and validity markers. The same storage is used as for the loop state. The elements stored in the different buffers might have different alignment because some of them store user-defined types, so the offset might have to be adjusted if the elements of the buffer initialized next have stricter alignment requirements. But in the default setting, all of these elements have the same alignment, so no offset adjustments will be applied (because the
if constexprconditions are all false).Validity markers have been stored in
vector<bool>until now, so this PR adds a minimal SBO-enabled fixed-size (but not constant-size) bitset for them.The capture group indices in the NFA nodes start from 1 (as the whole match is represented by capture group 0), and the matcher stored the capture group data at the same indexes in the vectors. This meant that the space at index 0 was wasted, but it wasn't really worth the effort to avoid this because it didn't change the number of allocations. But with this shared stack storage, avoiding wasted space might mean less (or no) allocations by the matcher. For this reason, I also adjusted the matcher to use 0-based indexing for the capture groups and no longer 1-based indexing. This is achieved by subtracting 1 whenever a capture group index from the NFA is read (after checking that it isn't 0 if necessary) or the capture groups are assigned to the
match_resultsobject.Benchmark
Some
regex_searchbenchmarks reliably show a speedup because allocations are saved in these cases (highlighted in bold). In the other benchmarks, differences vanish in the noise.