C++ - std::set构造函数有时非常低效？

Question

C++ - std::set构造函数有时非常低效？

3

我正在尝试按以下方式构建一个集合：

    std::set<SomeType> mySet(aVector.begin(), aVector.end());

在大多数情况下，这条线的性能非常高效。但有10%的情况下，运行时间太长（有时高达600毫秒以上！）。为什么会这样呢？每次输入都非常相似（向量大部分已排序）。有什么想法吗？

- Andrew

4

请提供一种能够重现运行缓慢的方法（例如提供数据或生成数据的方式），并附带一些时间信息和您的平台/编译器的基本细节。 - NPE

2

一个随机的600毫秒的减速感觉就像是一个页面错误或者多个任务切换。你处理了多少数据？系统是否承受内存压力？是否有其他进程争夺CPU？你如何测量这些时间？ - Matteo Italia

为什么页面错误或上下文切换只会发生在这个集合构造代码中？当我在代码的其他区域运行指标时，我从来没有看到600毫秒的峰值。 - Andrew

600毫秒可能是一瞬间，也可能是永恒...你实际上是如何衡量性能的？ - David Rodríguez - dribeas

2

当处理 std::set 或 std::map 问题时，我总是怀疑你正在使用的比较运算符的实现。在你的示例中，你依赖于 SomeType 的 operator< 来执行比较。如果该运算符没有以使您的 SomeType 成为严格的偏序集的方式编写，则会遇到奇怪的情况。 - Stuart Berg

显示剩余7条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joseph Garvin · Accepted Answer

我看到三个可能性：

您的结构体的operator<没有实现严格弱序关系，这是std::set正常工作所必需的。请记住，如果您的double值是NaN，则会破坏这个假设（在长时间查看其中一个集合时，请检查是否存在NaN）。
偶尔您的数据排序不太好。尝试始终在向量上进行std::sort，然后查看性能是否平稳--默认构建集合，然后使用std::set::insert，该函数需要两个参数，第一个参数是一个提示，用于与第一个元素进行比较（如果您可以提供一个很好的提示）。这将使您无需重新排序即可构建集合。如果这样可以解决问题，则说明数据的初始排序性是原因。
您的堆分配器偶尔会执行一些操作，使其花费的时间比正常情况下更长。它可能正在拆分或连接块以在需要较长时间的特定std::set()调用中找到自由内存。您可以尝试使用另一个分配器（如果您的程序是多线程的，可以尝试Google's tcmalloc）。如果您有显示分配器中所花费时间的分析器，则可以排除此项。另一种选择是使用boost::intrusive_set，这将在存储集合中的项目时避免需要分配。