KPropertiesDialog slow/no response when calculating the size of a big folder #309

Step to reproduce it:

right click on tdehwdevice tray, select properties and select a big storage disk. The Properties dialog opens
Click the "Calculate" button (in some cases it seems the "Calculate" functions starts as soon as the dialog opens)
press "Stop" while the size calculation is on going. Try to press "Cancel" to close the dialog. The dialog is unresponsive until the original calculation has completed. This can be monitored in htop, where the cpu usage of tdehwdevicetray is 100% while the calculation is ongoing.

The same behavior can also be reproduce in Konqueror when opening the Properties of a folder

While a full fix requires changes in TQt3 that will only be made in R14.2.0 (due to release cycle timing - see TDE/tqt3#67), good mitigation fixes have been made in TDE/tqt3#66 and TDE/tdelibs#191. which are appropriate for upcoming R14.1.0.

For future reference here is an explanation of the issue taken from a conversation between me and Slavek, just in case.

The problem with tdebase#309 is when you have a huge folder with lots of subfolders. For example you can think of the tde repository and worktrees in your disk or some other densily populated folders. If you open Konqueror, right click on the folder and show the Properties, it will start calculating the size of the folder. If you press the Stop button, the process stops, but the dialog remains unresponsive for quite some time (30+ seconds in my case).

What happens is that:

when you open the dialog, a ListJob recursive process starts. This lists the entry of the folder.
for each sub folder, a new ListJob is started to list the subfolder and things are repeated this way
with a big folder, you can have thousands of jobs created in a very short time (for my case, 25 thousands jobs created in 2 or 3 seconds
when you press the Stop button, the jobs get killed almost immediately, but before we can interact with the dialog again, things needs to get clean up and this in my case took 30+ seconds to do.

After profiling execution and investigating in depth, I root the problem at how TQt3 keeps track of TQObjects. As you know, TQObjects have parents and childrens, so things in TQt3 are mostly arranged in object trees. Deleting a root object will automatically clean up all the children in the tree, and this works fine. TQt3 keeps track of the object tree roots in a list
https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/kernel/qobject.cpp#L555

If a TQObject is created without a parent, it becomes a tree and it is inserted into this list
https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/kernel/qobject.cpp#L682

When a object tree is removed, TQt3 will search this lit to remove the object
https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/kernel/qobject.cpp#L734
https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/kernel/qobject.cpp#L595
https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/tools/qglist.cpp#L672
https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/tools/qglist.cpp#L926

Each TDEIO::Job is created as a tree object and ends up in the tree list.
https://mirror.git.trinitydesktop.org/gitea/TDE/tdelibs/src/branch/master/tdeio/tdeio/job.cpp#L109

Moreover each TDEIO::Job has a TQGuardedPtr in its private class
https://mirror.git.trinitydesktop.org/gitea/TDE/tdelibs/src/branch/master/tdeio/tdeio/job.cpp#L100

This guarded pointer also ends up in the object tree list
https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/kernel/qguardedptr.cpp#L199

When you open the Properties dialog, you get thousands of objects in the list. By gdb inspections I saw more that 30 thousands objects in my case
Adding a new object to the list is fast, it is usually appended. But removing an object from the list requires going thorugh the whole list till you find the object and this takes some time. Not a big deal if the list is short, but with a long list it matters
What was happening was that inserting 25 thousands objects took less than 3 seconds, but cleaning up the mess after pressing Stop took 30 seconds, 90% of it spend in the "findRef" method
https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/tools/qglist.cpp#L926

90.05%  90.03%  tdehwdevicetray  libtqt-mt.so.3.5.0  [.] TQGList::findRef
89.77%   0.00%  tdehwdevicetray  libtqt-mt.so.3.5.0  [.] TQMutex::~TQMutex
89.77%   0.00%  tdehwdevicetray  [unknown]           [.] 0x8b4807894810c083
89.73%   0.00%  tdehwdevicetray  [unknown]           [.] 0x000055ca593bc130
3.56%    0.00%  tdehwdevicetray  [unknown]           [k] 0x9066000000000084
3.11%    0.00%  tdehwdevicetray  [unknown]           [.] 0x00007f3dfcdf1c01

From logging I could see in 1ms that 10 or more objects were added, but that it took 2-3 milliseconds to delete a single object from the tree.
As the list gets shorter, the delete times get quicker and towards the end I can see 8-10 objects removed in 1ms, because the list is very short
so, this long description was to explain the problem. You can probably see a similar issue if you try the test I mentioned above. Make sure to use a folder with lots of subfolders in many levels. tde source code and worktree are ideal for that :-)

The correct way to fix this is to change the list of object tree to a map, this way the search will be much quicker because instead of going thorugh 30 thousands element each time, we probably go through 20 levels in a tree. We go from O(n) to O(log(n)) complexity. Nevertheless, it is a big change at the core of TQt3, so now this is not the right time to do it, too risky in case something goes wrong. [note: R14.1.0 is about to be released in less than 3 months].

So the work around that I have come up with, is to have a static TQObject as root for all guarded pointers created in an application. And one static objects as root for all TDEIO::Jobs as well. By using only two object tree instead of thousands, the unresponsive time of the dialog goes from 30+ seconds to about 2 seconds, which is probably the time required to kill off and delete 25 thousands of ListJobs.

For future reference here is an explanation of the issue taken from a conversation between me and Slavek, just in case.<hr/> The problem with tdebase#309 is when you have a huge folder with lots of subfolders. For example you can think of the tde repository and worktrees in your disk or some other densily populated folders. If you open Konqueror, right click on the folder and show the Properties, it will start calculating the size of the folder. If you press the Stop button, the process stops, but the dialog remains unresponsive for quite some time (30+ seconds in my case). What happens is that: 1. when you open the dialog, a ListJob recursive process starts. This lists the entry of the folder. 2. for each sub folder, a new ListJob is started to list the subfolder and things are repeated this way 3. with a big folder, you can have thousands of jobs created in a very short time (for my case, 25 thousands jobs created in 2 or 3 seconds 4. when you press the Stop button, the jobs get killed almost immediately, but before we can interact with the dialog again, things needs to get clean up and this in my case took 30+ seconds to do. After profiling execution and investigating in depth, I root the problem at how TQt3 keeps track of TQObjects. As you know, TQObjects have parents and childrens, so things in TQt3 are mostly arranged in object trees. Deleting a root object will automatically clean up all the children in the tree, and this works fine. TQt3 keeps track of the object tree roots in a list https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/kernel/qobject.cpp#L555 If a TQObject is created without a parent, it becomes a tree and it is inserted into this list https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/kernel/qobject.cpp#L682 When a object tree is removed, TQt3 will search this lit to remove the object https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/kernel/qobject.cpp#L734 https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/kernel/qobject.cpp#L595 https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/tools/qglist.cpp#L672 https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/tools/qglist.cpp#L926 Each TDEIO::Job is created as a tree object and ends up in the tree list. https://mirror.git.trinitydesktop.org/gitea/TDE/tdelibs/src/branch/master/tdeio/tdeio/job.cpp#L109 Moreover each TDEIO::Job has a TQGuardedPtr in its private class https://mirror.git.trinitydesktop.org/gitea/TDE/tdelibs/src/branch/master/tdeio/tdeio/job.cpp#L100 This guarded pointer also ends up in the object tree list https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/kernel/qguardedptr.cpp#L199 When you open the Properties dialog, you get thousands of objects in the list. By gdb inspections I saw more that 30 thousands objects in my case Adding a new object to the list is fast, it is usually appended. But removing an object from the list requires going thorugh the whole list till you find the object and this takes some time. Not a big deal if the list is short, but with a long list it matters What was happening was that inserting 25 thousands objects took less than 3 seconds, but cleaning up the mess after pressing Stop took 30 seconds, 90% of it spend in the "findRef" method https://mirror.git.trinitydesktop.org/gitea/TDE/tqt3/src/branch/master/src/tools/qglist.cpp#L926 ``` 90.05% 90.03% tdehwdevicetray libtqt-mt.so.3.5.0 [.] TQGList::findRef 89.77% 0.00% tdehwdevicetray libtqt-mt.so.3.5.0 [.] TQMutex::~TQMutex 89.77% 0.00% tdehwdevicetray [unknown] [.] 0x8b4807894810c083 89.73% 0.00% tdehwdevicetray [unknown] [.] 0x000055ca593bc130 3.56% 0.00% tdehwdevicetray [unknown] [k] 0x9066000000000084 3.11% 0.00% tdehwdevicetray [unknown] [.] 0x00007f3dfcdf1c01 ``` From logging I could see in 1ms that 10 or more objects were added, but that it took 2-3 milliseconds to delete a single object from the tree. As the list gets shorter, the delete times get quicker and towards the end I can see 8-10 objects removed in 1ms, because the list is very short so, this long description was to explain the problem. You can probably see a similar issue if you try the test I mentioned above. Make sure to use a folder with lots of subfolders in many levels. tde source code and worktree are ideal for that :-) The correct way to fix this is to change the list of object tree to a map, this way the search will be much quicker because instead of going thorugh 30 thousands element each time, we probably go through 20 levels in a tree. We go from O(n) to O(log(n)) complexity. Nevertheless, it is a big change at the core of TQt3, so now this is not the right time to do it, too risky in case something goes wrong. [note: R14.1.0 is about to be released in less than 3 months]. So the work around that I have come up with, is to have a static TQObject as root for all guarded pointers created in an application. And one static objects as root for all TDEIO::Jobs as well. By using only two object tree instead of thousands, the unresponsive time of the dialog goes from 30+ seconds to about 2 seconds, which is probably the time required to kill off and delete 25 thousands of ListJobs.