O(n^2) CPU performance in explorer with many images on the desktop

[randomascii]

Environment

Item	Value
OS, Version / Build	Win32NT 10.0.19041.0 Microsoft Windows NT 10.0.19041.0
Processor Architecture	AMD64
Processor Type & Model	Intel Core i7-7820HQ @ 2.90 GHz
Memory	32 GB
Storage Type, free / capacity (e.g. C: SSD 128GB / 512GB)	SSD, 32GB / 254 GB
Relevant apps installed	Python

Description

If you have many files on your desktop then explorer occasionally goes off and rearranges icons. During this time it doesn't pump messages from one of its UI threads. This has, on some customer's machines, led to UI hangs of various types. Even without the UI hangs this is excessively inefficient.

Steps to reproduce

src = r'path_to_a_jpg_file.jpg'
for i in range(1000):
shutil.copy(src, r'c:\users\bruce\Desktop\tst%04d.jpg' % i)

That is, put a thousand files on your desktop. I tested with .jpg files but I think any images will do and probably other file types as well. Then, unplug or plug in an external monitor.

Expected behavior

Explorer should rearrange the icons so that the conform to the new desktop layout and it should do this in no more than half a second.

Actual behavior

Explorer.exe consumes 100% of a core for about two minutes. During this time that thread is not pumping messages - WPA reports it as a 110 s MsgCheck Delay in UI Delays and I think the only reason it was reported as being that short a delay was because I stopped tracing before the work was finished.

This happens even when the desktop is set to hide the icons.

Original report was here:
https://twitter.com/FreyaHolmer/status/1355971680406007810

Some twitter discussion is here:
https://twitter.com/BruceDawson0xB/status/1359784745777786882

The same issue was previously reported here:
https://qiita.com/okuoku/items/e344a81fd6494a19bb26

[randomascii]

While investigating this I used UIforETW (https://github.com/google/uiforetw) to record the traces. UIforETW has a feature to browse to the selected trace, available by selecting a trace in the list, right-clicking, and selecting "Browse folder". If explorer is busy when you invoke this then the operation doesn't happen until icon layout is complete, which may be minutes. A busy cursor is displayed if you hover over the desktop.

Other hangs have been reported but this is the only one that I have actually seen.

[randomascii]

Stress-test tool to easily trigger the bug is available here:
https://github.com/randomascii/blogstuff/tree/main/DesktopIcons

Run the script (requires python3) and specify increasingly large desktop image counts while monitoring explorer.exe CPU usage. I recommend starting with 100 and going up by 100, waiting for explorer to go quiet. The time in the children of this call stack seems to go up roughly quadratically, hitting ~36 seconds after 800 images. Note that the images are not deleted so repeated runs with lower numbers don't test anything.

ntdll.dll!RtlUserThreadStart
kernel32.dll!BaseThreadInitThunk
explorer.exe!__scrt_common_main_seh
explorer.exe!wWinMain
shell32.dll!SHDesktopMessageLoop
shell32.dll!CDesktopBrowser::_MessageLoop
user32.dll!DispatchMessageWorker
user32.dll!UserCallWinProcCheckWow
windows.storage.dll!CDefCollection::s_WndProc
windows.storage.dll!CDefCollection::_WndProc
windows.storage.dll!CDefCollection::_OnDSVDispatchQueueItem
windows.storage.dll!CTaskLock::DispatchQueueItem
windows.storage.dll!COperationNextBatchQueueItem::Dispatch
windows.storage.dll!CDefCollection::OnQIOperationNextBatch
windows.storage.dll!CDefCollection::_OnUpdateItems
windows.storage.dll!FireOnCollectionChanged
shell32.dll!CCollectionSink::OnCollectionChanged
shell32.dll!CListViewHost::OnCollectionChanged
shell32.dll!BatchPositionChangesHelper::~BatchPositionChangesHelper

[randomascii]

Hey, it's now a blog post! https://randomascii.wordpress.com/2021/02/16/arranging-invisible-icons-in-quadratic-time/

[kumarharsh]

Really liked the post. And I'd like to point out to the Windows team that from my experience (anecdotal) I've seen about 90% of my colleagues, family, friends, cyber cafe shops, etc have their desktop full of icons. This seems like a major win if fixed soon.

[randomascii]

The issue is not caused by having an NVME. Having fast hard-drive doesn't cause the problem, it just doesn't solve it.

The problem is 100% a coding bug that causes icon arrangement to take orders of magnitude longer than it should.

It will probably be quite a while (a year, perhaps?) before a fix is even possible so I would recommend deleting all of the files from your desktop, or moving them somewhere else.

[mmarinchenko]

@randomascii

However, who can guarantee that there is no another bunch of O(n^2) algorithms in the NVMe-driver/firmware :)

[ChrisGuzak]

For those at MS I filed this bug to track this: https://microsoft.visualstudio.com/OS/_workitems/edit/32056718

[theolivenbaum]

Any updates on this @ChrisGuzak?