Tcl Source Code

View Ticket
Login
2025-03-29
18:07 • Ticket [62dafd9c53] Namespace import can cause quadratic big-O and affects all s... artifact: 0f17ff9d54 user: sebres
2025-03-28
13:42 • Ticket [62dafd9c53]: 3 changes artifact: 153a1cb7e7 user: sebres
2025-03-27
14:18 • Ticket [62dafd9c53]: 3 changes artifact: 11607f56db user: sebres
13:53 • Ticket [62dafd9c53]: 3 changes artifact: 7319784346 user: sebres
13:53 • New ticket [62dafd9c53]. artifact: c7383a10cc user: sebres

Ticket UUID: 62dafd9c53882dc27f4bbd68ad5b2160f06129
Title: Namespace import can cause quadratic big-O and affects all siblings of same original command
Type: Bug Created on: 2025-03-27 13:53:45
Submitter: sebres Assigned to: sebres
Subsystem: 21. [namespace] Severity: Severe
Priority: 5 Medium Last modified: 2025-03-29 18:07:09
Status: Open Closed by: nobody
Resolution: None Closed on:
Version: any
Description:

[namespace import] looks to be affected by quadratic big-O... Every NS, OO-context, etc importing the command causes that it's deletion costs O(n**2)*m, where n - number of imports for original command, and m - number of such imported commands in NS/OO/etc.

PoC:

  namespace eval A { proc c1 {} {}; proc c2 {} {}; proc c3 {} {}; namespace export * }
  foreach count {100 1000 10000 100000} {
    puts "=== $count ==="
    set i 0; puts [timerate { namespace eval ::B[incr i] {namespace import ::A::*} } 1000 $count]
    set i 0; puts [timerate { namespace delete ::B[incr i]; } 1000 $count]
  }
result:
  === 100 ===
  26.0500 µs/# 100 # 38387.7 #/sec 2.605 net-ms
  2.540000 µs/# 100 # 393700 #/sec 0.254 net-ms
  === 1000 ===
  13.8020 µs/# 1000 # 72453.3 #/sec 13.802 net-ms
  9.236000 µs/# 1000 # 108271 #/sec 9.236 net-ms
  === 10000 ===
  11.0121 µs/# 10000 # 90809.2 #/sec 110.121 net-ms
  285.814 µs/# 3498 # 3498.8 #/sec 999.776 net-ms
  === 100000 ===
  10.9604 µs/# 90967 # 91237.9 #/sec 997.031 net-ms
  14274.5 µs/# 70 # 70.055 #/sec 999.212 net-ms
(the last two are not achieved the whole set (would take a small eternity for the last), it has mastered only 70 deletions in a second, where on previous order of magnitude it was 3.5k in a second).

Causation is ImportRef *importRefPtr in Command structure, what is unidirectional list. Moreover it's existence is not justified at all - this causes drastic performance impacts in any cases, and basically needed only to pass namespace-56.6 (deletion of original command shall cause the invocation of deletion-traces on imported commands). This (if needed at all) can be achieved with other way without that list.

User Comments:
sebres added on 2025-03-27 14:18:52:

Here how it looks without the impact of importRefPtr list (I already rewrote that in my fork, with replacing importRefPtr by "default" ref-counting of cmdPtr through the import):

  === 100 ===
  7.640000 µs/# 100 # 130890 #/sec 0.764 net-ms
  0.490000 µs/# 100 # 2040816 #/sec 0.049 net-ms
  === 1000 ===
  7.243000 µs/# 1000 # 138064 #/sec 7.243 net-ms
  0.496000 µs/# 1000 # 2016129 #/sec 0.496 net-ms
  === 10000 ===
  7.788300 µs/# 10000 # 128397 #/sec 77.883 net-ms
  0.592700 µs/# 10000 # 1687194 #/sec 5.927 net-ms
  === 100000 ===
  7.683910 µs/# 100000 # 130142 #/sec 768.391 net-ms
  0.621080 µs/# 100000 # 1610098 #/sec 62.108 net-ms
The issue is now - how to backport that all and resolve 1000 conflicts.