r227808 (and r227811) changed `std::inplace_merge()` to meet the complexity guidelines of the standard, which strictly restricts the number of calls to the predicate. Unfortunately, this removed an optimization that avoided moving any elements if the sequence was already fully sorted. Moroever, any initial/final subsequence that was in the right spot would previously never be touched.
r243530, whose main purpose was to fix a latent self-move bug made more common by r227808/r227811, already brought half of this optimization back. It avoids unnecessarily moving the final subsequence. These patches close the loop, bringing back the other half of the optimization without re-introducing the extra predicate call that r227808 avoided. 0001 is an NFC refactor, while 0002 has the actual change. (The change in r227811 was to *always* malloc a temporary buffer. I wonder if something like this could safely optimize that away as well?)
0001-algorithm-Refactor-__buffered_inplace_merge-NFC.patch
Description: Binary data
0002-algorithm-Avoid-moving-initial-subsequences-in-std-i.patch
Description: Binary data
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
