#629 TIP 405: mapeach implementation with bytecoding

TIP Implementation
open
5
2012-08-02
2011-01-22
Twylite
No

"mapeach" is a collecting [foreach], and arises from a discussion at http://wiki.tcl.tk/26013 . This patch provides an implementation of [mapeach] in the core, with full bytecoding support, leveraging the existing [foreach] infrastructure.

Discussion

  • Twylite
    Twylite
    2011-01-22

     
    Attachments
  • Twylite
    Twylite
    2011-01-22

     
    Attachments
  • Twylite
    Twylite
    2011-01-22

    Includes a full set up tests (partially derived from the foreach.test suite).

     
  • Twylite
    Twylite
    2012-07-31

    mapeach implementation and tests, patch to [eeed854a7b] (trunk 2012-07-31)

     
    Attachments
    • milestone: --> TIP Implementation
    • summary: mapeach implementation with bytecoding --> TIP 405: mapeach implementation with bytecoding
     
  • Twylite
    Twylite
    2012-08-02

    mapeach and dict map, with tests and man pages, patch to [1917444560] (trunk 2012-08-02)

     
    Attachments
  • Twylite
    Twylite
    2012-08-02

    # Performance tests
    # Tcl = 32-bit tclsh86t.exe from trunk [19174445] with branches bug-3545363
    # and td-mapeach merged in, built with MSVC10, OPTS=threads
    # Platform = Intel64 (AMD64) i5 @ 2.67Ghz running Windows 7 (64-bit)

    set d [lsearch -all [lrepeat 1000000 x] x] ; llength $d

    lindex $d 1000 ;# ensure list rep

    time {
    set accum {}
    foreach {k v} $::d {
    lappend accum [expr { $k * $v }]
    }
    puts [tcl::mathop::+ {*}$accum] ;# 166666416666500000
    }
    # 750919 microseconds per iteration (foreach)

    time {
    puts [tcl::mathop::+ {*}[mapeach {k v} $::d { expr { $k * $v } }]] ;# 166666416666500000
    }
    # 616432 microseconds per iteration (mapeach)

    time {
    apply {{} {
    set accum {}
    foreach {k v} $::d {
    lappend accum [expr { $k * $v }]
    }
    puts [tcl::mathop::+ {*}$accum] ;# 166666416666500000
    }}
    }
    # 382724 microseconds per iteration (apply foreach)

    time {
    apply {{} {
    puts [tcl::mathop::+ {*}[mapeach {k v} $::d { expr { $k * $v } }]] ;# 166666416666500000
    }}
    }
    # 382829 microseconds per iteration (apply mapeach)

    dict get $d 1000 ;# ensure dict rep

    time {
    set accum {}
    dict for {k v} $::d {
    lappend accum [expr { $k * $v }]
    }
    puts [tcl::mathop::+ {*}$accum] ;# 166666416666500000
    }
    # 739547 microseconds per iteration (dict for)

    time {
    puts [tcl::mathop::+ {*}[dict map {k v} $::d { expr { $k * $v } }]] ;# 166666416666500000
    }
    # 621000 microseconds per iteration (dict map)

    time {
    apply {{} {
    set accum {}
    dict for {k v} $::d {
    lappend accum [expr { $k * $v }]
    }
    puts [tcl::mathop::+ {*}$accum] ;# 166666416666500000
    }}
    }
    # 357713 microseconds per iteration (apply dict for)

    time {
    apply {{} {
    puts [tcl::mathop::+ {*}[dict map {k v} $::d { expr { $k * $v } }]] ;# 166666416666500000
    }}
    }
    # 360457 microseconds per iteration (apply dict map)

    RANK:
    # 357713 microseconds per iteration (apply dict for)
    # 360457 microseconds per iteration (apply dict map)
    # 382724 microseconds per iteration (apply foreach)
    # 382829 microseconds per iteration (apply mapeach)
    # 616432 microseconds per iteration (mapeach)
    # 621000 microseconds per iteration (dict map)
    # 739547 microseconds per iteration (dict for)
    # 750919 microseconds per iteration (foreach)

     
  • Twylite
    Twylite
    2012-08-03

    Latest implementation committed to branch 'tip-405-impl-td'. This includes 'mapeach' and 'dict map' with full test suites, a bug fix made since the last patchfile, and man pages.

    Also included is an experimental accumulating foreach tentatively named 'foreacha'. [foreacha] treats the first list variable as an accumulator. The accumulator consumes a list element on the first iteration only, and is returned by [foreacha].

    Examples of [foreacha]:

    fold with initial var: foreacha a 0 b {1 2 3 4} { incr a $b }
    fold without initial var: foreacha {a b} {1 2 3 4} { incr a $b }
    filter: foreacha a {} b {1 2 3 4} { if { ($b % 2)==0 } { lappend a $b } }
    map: foreacha a {} b {1 2 3 4} { lappend a [expr { $b * 5 }] }
    prefix: foreacha a {} b {1 2 3 4} { if { $b > 2 } break; lappend a $b }