| Ticket UUID: | b7abf0d8179a7f1fdad976d223c617d0d8bd868d | |||
| Title: | ttk::treeview shows O(n^2) destruction time | |||
| Type: | Bug | Version: | Tk9.0b1 | |
| Submitter: | emiliano | Created on: | 2024-01-04 17:39:05 | |
| Subsystem: | 88. Themed Tk | Assigned To: | fvogel | |
| Priority: | 5 Medium | Severity: | Important | |
| Status: | Closed | Last Modified: | 2024-01-09 22:03:36 | |
| Resolution: | Fixed | Closed By: | fvogel | |
| Closed on: | 2024-01-09 22:03:36 | |||
| Description: |
The folllowing script shows quadratic destruction times for ttk::treeview widgets.
package require Tk
set img [lindex [image names] 0]
foreach nr {1000 2000 5000 10000 20000 50000 100000 200000} {
puts $nr
scan [time {
pack [ttk::treeview .tv]
for {set i 0} {$i < $nr} {incr i} {
.tv insert {} end -text "Element nr $i" -image $img
}
}] %d c
scan [time {destroy .tv}] %d d
lappend res [list $nr $c $d]
}
puts " nr Creation Destruction"
foreach n $res {
puts [format {%6d%15d%15d} {*}$n]
}
On a (rather slow) i386 machine the final report reads
nr Creation Destruction
1000 140513 7815
2000 137121 27321
5000 237192 224060
10000 418525 1028275
20000 774839 8200893
50000 1835814 29412184
100000 3599074 125016080
200000 7186131 640470106
showing linear times for insertion, quadratic times for destruction | |||
| User Comments: |
fvogel added on 2024-01-09 22:03:36:
Merged. fvogel added on 2024-01-08 22:32:44: Yeah, I was working on this as well and have found the fix you mention. This removes the panic. And then one can further simplify the code, please see [9030824a]. emiliano added on 2024-01-08 21:48:27: Destruction times are now are O(n). Great work!!. Reading the change, however, I found the lines 702 and 713 from this checkin (latest of bug-b7abf0d817 branch) https://core.tcl-lang.org/tk/artifact?name=a1212acf4c27036f confusing. Should't they read - imagePtr->nextPtr->prevPtr = NULL; + imagePtr->nextPtr->prevPtr = imagePtr->prevPtr; and - imagePtr->prevPtr->nextPtr = NULL; + imagePtr->prevPtr->nextPtr = imagePtr->nextPtr; instead? fvogel added on 2024-01-07 16:27:02:
The test suite panics in ttk.test when executing the last instruction from this file (i.e. The panic happens exactly here (observe this location is in Tcl, not in Tk). The panic says: "alloc: invalid block: ... ef ef 0", that is: the two magic numbers are the right ones (0xef), but the third number is not correct (zero instead of the expected 0xef). This must indicate some sort of memory corruption but I'm at a loss to guess what and how. The call stack is entirely in Tcl except for the first two levels (wWinMain and Tk_MainEx which evaluates the ttk.test file). Strangely, this happens for some debug builds but not all, e.g. it triggers on Windows with MSVC with debug (OPTS=symbols), but not on Linux where all builds at Github Actions are fine (although running under valgrind allows to detect this problem). fvogel added on 2024-01-06 21:44:58: The issue arises from the fact Image instances are in a linked list. When destroying an image, this linked list must be swept from its beginning until the right image is found. I propose to fix this by doubly linking the list of Image instances referring to a given ImageModel struct. Please see [a5ad9e81], which removes the while loop. The test script now gives linear destruction time: 1000 17440 2315 2000 14435 1173 5000 23510 2210 10000 47526 4608 20000 96080 9079 50000 235674 23534 100000 467423 53175 200000 953798 109328 fvogel added on 2024-01-06 17:30:14: Brute force profiling shows that 99 % of the time is spent in Tk_FreeImage() in this loop. emiliano added on 2024-01-05 14:04:22: The problem is related to images. By omitting the -image option, destruction times drop below 200ms for ~30000 items | |||
Home
Timeline
Branches
Tags
Forum
Tickets
Download
Wiki