Tcl Source Code

View Ticket
Login
Ticket UUID: 0b3595a8191076b07b0603ae745d0c7c1a849666
Title: Invocation of imported nested command is affected by recursionlimit and has O(n) instead of O(1)
Type: Bug Created on: 2025-03-29 18:07:18
Submitter: sebres Assigned to: sebres
Subsystem: 21. [namespace] Severity: Severe
Priority: 5 Medium Last modified: 2025-03-29 18:37:05
Status: Open Closed by: nobody
Resolution: None Closed on:
Version: any
Description:

Similar to [62dafd9c53882dc2], but this time it is about execution and going to missing direct pointer to the real command by nesting the imports (e. g. like nested inheritances of NS) - during the execution it always need to iterate over all nested imports up to the real command and therefore:

  1. is affected by recursionlimit of interpreter;
  2. has O(n) instead of O(1) by command invocation;

PoC:

  namespace eval ::A { proc c {} {}; namespace export * }
  foreach count {100 1000 10000} {
    puts "=== $count ==="
    for {set i 0} {$i < $count} {} {
      if {$i} {
        set imp "namespace import -force ::B${i}::*"
      } else {
        set imp "namespace import -force ::A::*"
      }
      namespace eval ::B[incr i] "$imp; namespace export *"
    }
    puts [timerate " ::B${i}::c " 1000]
    while {$i} { namespace delete ::B$i; incr i -1 }
  }

Firstly it'd fail (due to incorrect exceeding of limit) with "too many nested evaluations (infinite loop?)"...

By repeat after interp recursionlimit {} 100000, the result would look like:

  === 100 ===
  3.397699 µs/# 291567 # 294316 #/sec 990.657 net-ms
  === 1000 ===
  40.9938 µs/# 24375 # 24393.9 #/sec 999.225 net-ms
  === 10000 ===
  467.815 µs/# 2137 # 2137.6 #/sec 999.721 net-ms

If solved, it looks like this (without the necessity to increase recursionlimit):

  === 100 ===
  0.202850 µs/# 4249839 # 4929744 #/sec 862.081 net-ms
  === 1000 ===
  0.206966 µs/# 4176792 # 4831722 #/sec 864.452 net-ms
  === 10000 ===
  0.201285 µs/# 4278305 # 4968083 #/sec 861.158 net-ms

I'll provide the fix for this together with [62dafd9c53882dc2] (back-ported from my fork in the single branch).