Tk Source Code

View Ticket
Login
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. eval destroy [winfo children .]).

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