HomePhabricator

[Dominators] Avoid potentially quadratic std::is_permutation

Authored by MaskRay on Feb 27 2019, 9:16 PM.

Description

[Dominators] Avoid potentially quadratic std::is_permutation

Summary:
If the two sequences are not equal, std::is_permutation may be O(N^2)
and indeed the case in libstdc++ and libc++. Use SmallPtrSet to prevent
pessimizing cases. On my machine, SmallPtrSet starts to outperform
std::is_permutation when there are 16 elements.

Reviewers: kuhar

Reviewed By: kuhar

Subscribers: kristina, jdoerfert, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D58373

llvm-svn: 355070

Details