[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
======

<<categories>> Performance