二次时间排列不可见的图标

一月底，我被指到了一个推特线程，一个拥有强大计算机的Windows用户正在浏览器中随机挂起。提出了许多不科学的理论。我通常不会对陌生人的表现问题进行随机分析，但此案听起来很有趣，所以我想看看。

Freya分享了她的计算机上发生的事件的ETW跟踪信息，我使用Windows Performance Analyzer（WPA）进行了研究。我注意到的第一件事是，UI延迟图显示，正如所承诺的那样，explorer.exe的线程7888在20.531秒内未能检查消息。它挂了。

现在，explorer.exe具有许多UI线程，因此它好像不是整个过程都被挂起了，但是它的一个窗口肯定被挂起了，这导致了其他地方的挂起，这很糟糕。

如果线程无法发送消息，则可能是因为它正在忙于执行其他操作（消耗CPU），或者是在等待其他操作（空闲CPU）。放大20.531秒的MsgCheck Delay时间段后，我检查了CPU使用率（精确）数据（来自上下文切换工具，准确度为100％），发现线程9228运行99.2％的时间–它消耗大量CPU 。

下一个任务是弄清楚它在做什么。 CPU使用率（采样）数据（来自1 kHz采样分析器）告诉我，线程9,228在BatchPositionChangesHelper析构函数（第21行）及其子代（第23行）中花费了大约99.7％的时间（在27074个样本中占26994）。 -25）。那是一个非常昂贵的析构函数。

我没有访问此源代码的权限，但我对堆栈进行了仔细的浏览，似乎表明explorer.exe花了20多秒钟来完成许多与……安排图标位置有关的任务。

在桌面上排列图标非常简单。您只需要在各列中堆叠然后溢出到下一列，然后在屏幕满时停止即可。因此，排列图标20秒似乎不太合理，我认为根本原因是某些奇怪的Shell扩展程序或其他第三方软件，但最终我尝试以最简单的方式重现该错误。我心想，如果我只是在桌面上制作一千个.jpg图像的小副本，然后查看explorer.exe的行为不正常怎么办。这太愚蠢了，不足以解决问题，但是：

src = os.path.join（script_path，'SunsetWhales.jpg'）dst = os.path.join（desktop_path，'TestFiles％04d.jpg'）适用于范围（file_count）中的i：一世）

我使用file_count为1000运行了这个简单的脚本，然后explorer.exe像疯了似的旋转了二十多秒钟。真的就是这么简单。

今天的计算机确实非常快。原始报告程序（OP）的CPU运行在4.6 GHz上，台式机上大约有950个GIF文件。在20秒内，他们的CPU将完成920亿个周期，即每个图像9700万个周期。好多

我的猜测是，这再次归因于我观察到的一种称为Dawson的第一个计算定律：O（n ^ 2）是缩放算法很差的地方：足够快以使其投入生产，但足够慢使事情一到就掉下来。

就是说，最有可能解释为什么安排图标花这么长时间的原因是，图标重新排列代码使用了O（n ^ 2）（又称二次方）算法，使得图标的数量增加了两倍，而排列它们的时间增加了四倍。这种性能扩展可以采用一种算法，该算法可以很好地处理十个项目，而仅用1,000个项目就可能导致失败。

我首先编写了一个脚本，该脚本将用指定数量的图像填充桌面。我用越来越多的图像反复运行，并记录了ETW轨迹，以便可以测量性能。我还使用任务管理器监视了explorer.exe，这样我就可以知道它何时完成一项工作并为下一项做好准备。

我的第一个测试给出了混乱的结果–看起来像是非线性的增长，但是任何进行直线拟合的尝试都将更多地是希望和魔术，而不是跟随数据。我需要了解正在发生的事情，以便更好地检验我的理论。

在查看跟踪时，我意识到BatchPositionChangesHelper析构函数在大多数时间（蓝色区域）都在运行，但在资源管理器的所有时间（绿色区域）中都没有运行：

我意识到，除其他外，布局工作被显示工作打断了，然后我理解了变化的原因。

当我的Python脚本开始创建图像时，explorer.exe进程会注意到并立即开始尝试布局图标。在创建图像时，它可能会多次执行此操作，而这会产生不可预测的结果。这是一个竞赛条件，使总成本不一致。由于我无法访问explorer.exe源代码，因此我不得不寻找一种方法，使其等待所有图像创建完成后再进行任何布局。在创建映像时，我通过使用psutil暂停了explorer.exe进程来做到这一点。然后，当我恢复该过程时，它将完成所有工作。代码看起来像这样：

有了这个，我在记录ETW跟踪的同时运行了我的测试批处理文件。为了最大程度地减少噪声和跟踪大小，我禁用了上下文切换调用堆栈（不需要），并且关闭了桌面文件夹的索引编制功能。我使用任务管理器监视explorer.exe的CPU使用情况，并在输入为零时按Enter键进入下一个测试。这给了我explorer.exe CPU使用率的这张非常漂亮的图表：

各个块代表100、200、300等的CPU使用率，以此类推，直到1,000张图像。如果您有敏锐的眼光，那么您会发现CPU使用率的增加快于线性速度，但慢于平方速度。即，初始数据表明布局算法不是相当-O（n ^ 2）。

但是，资源管理器所做的工作不仅仅是图标布局。如果其某些任务是O（n）（线性），那么它们将分散O（n ^ 2）任务的影响。随着'n'的增加，O（n ^ 2）任务最终将占主导地位，但我不希望我的测试工具的运行时间超过已经花费的160秒。

因此，我的下一个任务是找出在BatchPositionChangesHelper析构函数中花费的时间。在我的测试跟踪中，它花费了78.4％的时间用于explorer.exe，而在繁忙的线程中则花费了92.3％的时间，如果我能证明它是二次方的，那么我会证明随着'n'的增加将永远统治。

为此，我查看了CPU使用率（采样）数据并将其过滤掉，以仅在BatchPositionChangesHelper析构函数及其子代中显示样本。然后，我查看了图形的十个不同区域，并绘制了样本计数的图形。曲线是如此平滑，以致看起来是假的，但这是实际数据。

如果查看图形上的关键点（例如，当图像计数为500时，然后是1,000时），则可以看到性能缩放比O（n ^ 2）稍差。也就是说，布置1,000个图标所需的时间是布置500个图标所需时间的四倍以上。

我的桌面上通常不会有很多图标，因此我几乎不受此错误的影响。但是，我看到人们的桌面上完全装有图标，他们可能正在使用次要版本。

OP使用其桌面存储GIF文件。他们将其视为一个文件夹（可以在其中轻松存储图像）。他们很少使用桌面上的图标。因此，当图标的数量最终变得过多时，他们决定取消选中“显示桌面图标”以减少混乱。图标被隐藏，它们可以继续将图像存储在该文件夹中。

他们看到的死机是，资源管理器反复花费20多秒钟在桌面上排列图标，而资源管理器正在消耗920亿个CPU周期以使图标定位正确……这是在隐藏图标的情况下发生的。

在网格上布置图标应该是一种固有的线性操作，但是以某种方式将其编写为二次方，即使未显示图标也可以执行。

而已。如果您编写将由其他人运行的代码，请确保其伸缩性足够好以处理任何可能的数据集（无论是否合理）。二次算法通常无法通过该测试。

最初的错误似乎与重新排列多显示器设置有关（据告诉，这对拖缆有工作危险），所以一段时间以来，我一直在通过插拔外部显示器进行测试。这对于有效的测试而言效果不佳，而且似乎也耗尽了我个人笔记本电脑上的外接显示器连接。我的笔记本电脑不再能看到我的外接显示器。哎呀。

在分析OP的轨迹时，我只是将其加载到Windows Performance Analyzer（WPA）中并等待。我不必查看运行的Windows版本或已安装的补丁程序。 WPA只是查看了所有EXE和PE文件的调试信息，并从Microsoft的符号服务器（以及Chrome浏览器，因为我也配置了它们）下载了符号文件。符号服务器很好。如果您使用的是Windows，请确保使用符号服务器。如果您使用的不是Windows，则非常抱歉。

我不知道此错误会影响多少人（任何带有200-300个图标的人都遇到了该错误的中等版本，并且随着更多的使用，它会变得越来越糟），而且我无力修复。因此，我提交了一个错误。我不希望它会解决。自几个月前提交以来，我的上一个Windows二次方错误已被零评论。

我的测试的原始测量值在这里，测试本身在github上。此错误非常容易重现。如果有人想要“反馈中心”条目，则应创建一个。我建议在桌面挂起时使用UIforETW的“浏览文件夹”选项-在整个操作过程中，该操作将被阻止。

在我的职业生涯中，我经历了许多采访循环。经常有人要求我提出一种算法来完成一些人工任务。显而易见的“蛮力”算法通常是二次方（O（n ^ 2））或偶尔是指数方（O（2 ^ n））。这样通常会引起以下讨论：

尽管对这个问题有明显的了解，但作为一个行业，我们仍然保持二次运输代码。足够快的代码可以将其投入生产，但是足够慢的代码可以使它在投入生产后就崩溃了。例如，请参见此，此，此，此以及更多。我们真的需要停下来。

厌倦了阅读枯燥的性能分析？相反，您可以了解我在2018年9月如何使用19种不同的通勤方法，或者在2017年4月如何使用20种不同的通勤方法。