Tcl Source Code

Removed abstract list extension from dict objtype. The implementation is far from optimal.

Handling non-pure dict values will require a complex solution.

in cases where only the internal representation exists (when we can guarantee that the list length is exactly twice the dictionary size)

Well, this is even one of the additional issues - once the string representation created (for whatever reason), it is not possible anymore to know whether dict is "pure" dict or not. The lists have a "canonical" flag, so the same must be implemented for dict (it is canonical unless obtained from string representation), so TclIsPureDict could be replaced by TclIsCanonicalDict and in that case it is no matter whether string representation is there or not.

I was glancing at this earlier, and wondered why we were always generating the string representation of the dictionary, even in cases where only the internal representation exists (when we can guarantee that the list length is exactly twice the dictionary size).

The case is also present if SimplePERM proc returns an array.

It doesn't "return an array", because it is currently impossible in tcl - [array get] returns a dict:

   % tcl::unsupported::representation [array get env]
   value is a dict with a refcount of 1, ..., no string representation

Tcl cannot (and probably never will) directly return an array - array is just a complex variable (hash table in var in scope/NS/whatever), so [array get] generates a dict at the time of execution to be able to return it (basically for the same reason why one cannot return directly $env (that's as implemented in core-tcl, there are another tcl-engines which able to do that and even such where array and dict are the same stuff).

This definitely belongs to abstract-lists implementation of 9.0 and although it was supposed to be better (avoid shimmer of dict to list), in the reality it is rather worse now:

• list facilities previously handles pure-dicts better (even if it shimmered sometimes between list/dict).
• by retrieving of length (DictAsListLength) now it always obtain string representation of dict (also for pure-dict object), what:
  • may be slow and
  • causes that dict object is not pure anymore (basically we need a flag for that, to mark pure-dicts independently to existence of its string representation)
• DictAsListLength (but basically ObjType::LengthProc) cannot handle errors, what may be not so good for a possible fallback (if dict is not pure dict);
• retrieving of index (if one would implement it for dict), e. g. for INST_FOREACH_STEP/INST_FOREACH_START instructions, is hardly possible, because normal iteration over the dict needs some interim Tcl_DictSearch (or similar iterator handle), and without that we'll get O(n!) aka factorial big-O if it'd always start from scratch and stop at index.
• ObjType::GetElements may be too hard (for large dicts) and it is unused, and rightly so, for INST_FOREACH_STEP/INST_FOREACH_FIRST instructions.
• there is no ObjType::Iterate facility.

All that makes difficult to implement it with reasonable performance for all corner cases. However I'll take a closer look to this later.

It is only affected if the value is set from dict. Basically as already correct assumed, it is not array set - it is foreach over dict content (foreach_start/foreach_step instructions compiled internally) that cause performance regression there.

Here is an example without array set, that shows the same regression with 9.0 (also llength $v does it):

proc SimplePERM {{asdict 1}} {
    if {$asdict} {
        set permmod [dict create]
        for {set i 0} {$i < 512} {incr i} {
            dict set permmod $i 1       
        }
    } else {
        set permmod {}
        for {set i 0} {$i < 512} {incr i} {
            lappend permmod $i 1
        }
    }
    return $permmod
}

proc generateData {{n 10000} {asdict 1}} {
    array set val {}
    set v [SimplePERM $asdict]
    for {set i 0} {$i < $n} {incr i} {
        # array set val $v
        # llength $v
        foreach {en ev} $v {}
    }
}

generateData 2000; # warm-up
puts [timerate {generateData 1000 1} 10000 1]
puts [timerate {generateData 2000 1} 10000 1]

generateData 2000 0; # warm-up
puts [timerate {generateData 1000 0} 10000 1]
puts [timerate {generateData 2000 0} 10000 1]

This is not platform-related, I see this on both windows and linux pretty well:

- 3263936 µs/# 1 # 0.306 #/sec 3263.936 net-ms - 8.6.14 (core-8-6-branch)
+ 9344194 µs/# 1 # 0.107 #/sec 9344.194 net-ms - 9.0    (trunk)

Trying this on both versions:

timerate -calibrate {}

proc SimplePERM {} {
    set permmod [dict create]
    for {set i 0} {$i < 512} {incr i} {
        dict set permmod $i [expr {$i + int(rand() * (256 - $i))}]
    }
    return $permmod
}

proc test {} {
    array set val0 {} ; array set val1 {} ; array set val2 {}
    puts PERM:\t[timerate {
       set v [SimplePERM]
    } 10000 9261]
    puts ASET:\t[timerate {
       array set val0 $v
       array set val1 $v
       array set val2 $v
    } 10000 9261]
    array set val0 {} ; array set val1 {} ; array set val2 {}
    puts BOTH:\t[timerate {
       set v [SimplePERM]
       array set val0 $v
       array set val1 $v
       array set val2 $v
    } 10000 9261]
    array set val0 {} ; array set val1 {} ; array set val2 {}
    puts CYCL:\t[timerate {
       for {set i 0} {$i <= 20} {incr i} {
          for {set j 0} {$j <= 20} {incr j} {
              for {set k 0} {$k <= 20} {incr k} {
              }
          }
       }
    } 10000 1]
}

test

doesn't explain that 3x difference in the "granulated" times (it is slower but few percent only, e. g. array set shows in 9.0 ca. 5% degradation only, and all others are similar, if not even less). The same happens if I put timerate into generateData to measure whole code once.

However if timerate is outside of original generateData (measures single or multiple invocations of generateData), there is indeed 3x difference between 8.6 and 9.0 (8.7 seems to be not affected).
It looks like something with compilation cycles or so, or inside the TEBCResume (NRE, whatever), because disassemble of both procs shows the same code. It happens also if I unfold 3 nested cycles to single one (with 10k iterations) or rewrite it to foreach i [lseq 10000].

Here is the original example rewrote as much simpler version with 10x performance degradation (however still O(n) just 10x larger), which also illustrates difference with inlined in proc timerate (without degradation):

# timerate -calibrate {}

proc SimplePERM {} {
    set permmod [dict create]
    for {set i 0} {$i < 512} {incr i} {
        dict set permmod $i 1       
    }
    return $permmod
}

proc generateData {{n 10000}} {
    array set val {}
    set v [SimplePERM]
    for {set i 0} {$i < $n} {incr i} {
        array set val $v
    }
}

generateData 20000; # warm-up
puts [timerate {generateData 10000} 10000 1]
puts [timerate {generateData 20000} 10000 1]

# to illustrate strange behaviour if timerate compiles the body instead of proc itself:
puts "# timerate inside proc:"
proc generateData {{n 10000}} "puts \[timerate {\n[info body generateData]\n} 10000 1\]"
generateData 10000
generateData 20000

Result as diff between 9.0 (bad -) and 8.6/8.7 (good +):

- 2302136 µs/# 1 # 0.434 #/sec 2302.136 net-ms
+ 200457.0 µs/# 1 # 4.989 #/sec 200.457 net-ms
- 4640549 µs/# 1 # 0.215 #/sec 4640.549 net-ms
+ 475257.0 µs/# 1 # 2.104 #/sec 475.257 net-ms
# timerate inside proc:
- 157615.0 µs/# 1 # 6.345 #/sec 157.615 net-ms
+ 136238.0 µs/# 1 # 7.340 #/sec 136.238 net-ms
- 320462.0 µs/# 1 # 3.120 #/sec 320.462 net-ms
+ 286145.0 µs/# 1 # 3.495 #/sec 286.145 net-ms

Anyway I don't think it is array set command alone.