RHS *16March2005*

I was doing some coding for the Language Shootout, and implemented the nsieve test using both arrays and dicts. While I was aware that dicts are faster than arrays, I was amazed at the difference.

UPDATE: The diff was due to using pattern match on array unset - see end notes RT

The array version:

proc main {n} { foreach value [list $n [incr n -1] [incr n -1]] { set num [expr { int(pow(2, $value) * 10000) }] puts [format "Primes up to %8d %8d" $num [nsieve $num]] } } proc nsieve {n} { set inData {} for {set i 2} {$i <= $n} {incr i} { lappend inData $i {} } set data {}; unset data array set data $inData for {set i 2} {$i <= $n} {incr i} { if { ! [info exists data($i)] } { continue } for {set j [expr {$i * $i}]} {$j <= $n} {incr j $i} { array unset data $j } } llength [array names data] } main [lindex $argv 0]

The dict version:

proc main {n} { foreach value [list $n [incr n -1] [incr n -1]] { set num [expr { int(pow(2, $value) * 10000) }] puts [format "Primes up to %8d %8d" $num [nsieve $num]] } } proc nsieve {n} { set data {} for {set i 2} {$i <= $n} {incr i} { lappend data $i {} } for {set i 2} {$i <= $n} {incr i} { if { ! [dict exists $data $i] } { continue } for {set j [expr {$i * $i}]} {$j <= $n} {incr j $i} { dict unset data $j } } llength [dict keys $data] } main [lindex $argv 0]

The timings:

(11)>> time ./nsieve.tcl 2 Primes up to 40000 4203 Primes up to 20000 2262 Primes up to 10000 1229 real 12m3.968s user 12m1.470s sys 0m0.030s (8)>> time ./nsieve.dict.tcl 2 Primes up to 40000 4203 Primes up to 20000 2262 Primes up to 10000 1229 real 0m4.115s user 0m2.020s sys 0m0.000s

**DGP** Is most of the difference due to [array unset] versus [dict unset] ? Note that [aray unset] operates on a *pattern* argument that must be matched against all elements of the array. While [dict unset] does not respect patterns and operates on exactly one key. That's an **N** vs **N-squared** difference in the algorithms.

Try replacing [array unset data $j] with [unset -nocomplain data($j)] and see whether that brings the two implementations into closer alignment.

**RHS** Indeed, that change alters the array timing to almost as fast as the dict:

(13)>> time ./nsieve.tcl 2 Primes up to 40000 4203 Primes up to 20000 2262 Primes up to 10000 1229 real 0m2.737s user 0m2.710s sys 0m0.030s

Moral of the story: Don't use pattern matching operations unless you need to.

DKF: There are additional opts possible on both: [**array size**] and [**dict size**] both skip the producing the actual list of all primes.

RLE (16 Aug 2011): Is there a reason why this difference in speed should exist:

% set arr(5) 5 5 % time { info exists arr(5) } 1000000 0.685363 microseconds per iteration % dict set dict 5 5 5 5 % time { dict exists $dict 5 } 1000000 1.368874 microseconds per iteration % set tcl_patchLevel 8.6b2 %

Ro According to aspect this problem doesn't exist in 8.6

tclsh8.6 [~]dict set dict 5 5 5 5 tclsh8.6 [~]set arr(5) 5 5 tclsh8.6 [~]time {info exists arr(5)} 10000000 0.1506702 microseconds per iteration tclsh8.6 [~]time {dict exists $dict 5} 10000000 0.1621209 microseconds per iteration tclsh8.6 [~]time {info exists arr(4)} 10000000 0.1820209 microseconds per iteration tclsh8.6 [~]time {dict exists $dict 4} 10000000 0.1612164 microseconds per iteration

DKF: If you're really going to compare performance, use the latest 8.6 and make sure you carry out the test inside a procedure (or lambda term) so that you're not being over-impacted by variable name lookup.