linkedlist.3.0.120823」への10件のフィードバック

  1. gustafn

    By using xotcl2/nx (http://next-scripting.org) you can obtain significant improvements. while in your example at size 1000, the xotcl version was 13 times slower than the native implementation, with xotcl2 it is just 9 times, and with nx it is 5 times. Now, the break-even point is below 10000 elements, with 30.000 elements, it takes 14% of the time of the nativelist in nx (26% with xotcl2), while with xotcl 1.* (your testcases), the oo version took 48%.

    Below is the output and a straight-forward translation from xotcl to nx. I am pretty sure, some more improvments are possible.
    best regards
    -g

    size=1000
    xolinkedlist 19388.55 microseconds per iteration
    nxlinkedlist 10965.7245 microseconds per iteration
    nativelist 2111.4005 microseconds per iteration

    size=10000
    xolinkedlist 188334.7815 microseconds per iteration
    nxlinkedlist 111429.6075 microseconds per iteration
    nativelist 229196.538 microseconds per iteration

    size=15000
    xolinkedlist 291550.7435 microseconds per iteration
    nxlinkedlist 170288.813 microseconds per iteration
    nativelist 549899.786 microseconds per iteration

    size=20000
    xolinkedlist 386649.6695 microseconds per iteration
    nxlinkedlist 217869.6185 microseconds per iteration
    nativelist 987030.1815 microseconds per iteration

    size=30000
    xolinkedlist 589272.71 microseconds per iteration
    nxlinkedlist 325571.504 microseconds per iteration
    nativelist 2242795.3885 microseconds per iteration

    ========================
    package req nx
    namespace eval NxLinkedList {
    nx::Class create Container {

    :property {first {}}
    :property {last {}}
    :property {size 0}

    :public method destroy {} {
    set es [:list]
    foreach e $es {
    :drop $e
    }
    next
    return $es
    }

    :public method clear {} {
    set es [:list]
    foreach e $es {
    $e destroy
    }
    return {}
    }

    :public method unlink {element} {

    if {![nsf::object::exists $element]} {return -1}
    if {[$element container] ne [self]} {return -1}

    set prev [$element prev_p]
    set next [$element next_p]

    $element prev_p {}
    $element next_p {}
    $element container {}

    if {$prev eq {}} {
    set :first $next
    } else {
    $prev next_p $next
    }
    if {$next eq {}} {
    set :last $prev
    } else {
    $next prev_p $prev
    }

    incr :size -1
    }

    :public method add {element} {
    if {[$element next_p] eq ${:first}} {
    set :first $element
    }
    if {[$element prev_p] eq ${:last}} {
    set :last $element
    }
    $element container [self]
    incr :size
    return $element
    }

    :protected method scan {key value} {
    for {set e ${:first}} {$e ne {}} {set e [$e next_p]} {
    if {[$e $key] eq $value} {return $e}
    }
    }

    :protected method at {index} {
    if {$index eq "end"} {return ${:last}}
    if {$index < 0 || ${:size} = 0} {
    return $element
    }
    }

    :public method delete {element} {
    #### FIXME
    if {![nsf::object::exists $element]} {
    $element destroy
    }
    }
    }

    # InstMixin this class into element class to use container
    nx::Class create Element {
    :property {prev_p {}}
    :property {next_p {}}
    :property {container {}}

    :public method destroy {} {
    :drop
    next
    return [self]
    }

    :protected method drop {} {
    if {${:container} ne ""} {
    ${:container} drop [self]
    }
    }

    :public method index {} {
    if {${:container} ne {}} {
    ${:container} index [self]
    }
    }

    :public method append {element} {
    if {${:container} ne {}} {
    $element prev_p [self]
    $element next_p ${:next_p}
    if {${:next_p} ne {}} {
    ${:next_p} prev_p $element
    }
    :next_p $element
    ${:container} add $element
    }
    }

    :public method prepend {element} {
    if {${:container} ne {}} {
    $element prev_p ${:prev_p}
    $element next_p [self]
    if {${:prev_p} ne {}} {
    ${:prev_p} next_p $element
    }
    :prev_p $element
    ${:container} add $element
    }
    }

    :public method status {} {
    append stat " container = [:container]\n"
    append stat " index = [:index]\n"
    append stat " element = [self]\n"
    append stat " neighbors = ([:prev_p]) => ([self]) => ([:next_p])\n"
    }
    }
    }

    nx::Class create NxListContainer -superclass {NxLinkedList::Container}
    nx::Class create NxListElement -superclass {NxLinkedList::Element}

    返信
    1. Yusuke Yamasaki 投稿作成者

      Thank you gustafn.
      You are the first commenter of my blog except myself!

      Actually, I doubted myself if there are cases that I need more than 15,000 elements.
      I would be happy when a linked list gets faster in a smaller size.

      I have been using XOTcl 1.x.x with my Windows desktop application for many years and my sources are deeply dependent to XOTcl 1.*. At first, I needed it to make Ruby on Rails like system that requires many reflection techniques. Now I use it even in the case where I don't need such techniques.

      I was sad when I heard that XOTcl did not marry with Tcl core.
      But I was happy that XOTcl team started the next project.

      Currently, XOTcl 2.x is not compatible with my code working on XOTcl 1.6.7.
      My application crashes by calling "next" in the descendent classes.
      I guess it is related to the meta-class mechanism. But I'm not sure for now.
      Such issues do not happen in a simple test code.

      I think I will make some test case some day.

      返信
  2. gustafn

    Google finds everthing!

    Well, a downstripped version of XOTcl made it into to the tcl core, called TclOO :). The basics of the core object system of TclOO and XOTcl are the same, several of the advanced features made it as well into TclOO. Being not part of the core has it advantages as well, since it allows us to develop the system without the need of approvals for every step by the core team. The merits of the OO work are recognized by the Tcl-community: the last Tcl-community award was given to Donal and me, which was a very nice draw.

    i am curious about the problem you are mentioning with XOTcl 2. Did you use the head version from git? can you produce a downstripped version causing the crash?

    返信
    1. Yusuke Yamasaki 投稿作成者

      I compiled nsf2.0b3 source code with MinGW.
      http://sourceforge.net/projects/next-scripting/files/2.0b3/nsf2.0b3.tar.gz/download

      The first issue is that "myvar" seems to have a dependency on "requireNamespace".
      But the requireNamespace is obsolete.

      http://yusuke-blog.info/?attachment_id=385
      (see debug.log)

      The second issue is similar to the first issue.
      I could not make a simple code to reproduce this error.
      Does the following stack trace help?

      no current object; command called outside the context of a Next Scripting method
      while executing
      "::nsf::self"
      ("uplevel" body line 1)
      invoked from within
      "uplevel ::nsf::self"
      (procedure "::xotcl::self" line 3)
      invoked from within
      "::xotcl::self"
      (procedure "myproc" line 1)
      invoked from within
      "myproc updateTriggerButton"
      (procedure "init" line 65)
      invoked from within
      "next"
      (procedure "init" line 3)
      ::icpms ::CallBack->init
      ::IcpmsController ::xotcl::Class->create
      invoked from within
      "::IcpmsController create icpms -iobox ::iobox"
      ("uplevel" body line 1)
      invoked from within
      "uplevel [list [self] create {*}$args]"
      (procedure "unknown" line 3)
      ::IcpmsController ::xotcl::Class->unknown
      invoked from within
      "IcpmsController icpms -iobox $iobox"
      invoked from within
      "set icpms [IcpmsController icpms -iobox $iobox]"
      (file "C:\Users\yusuke\Documents\devel\IAS\VPD_NAGANO\VIS_NAGANO\init.tcl" line 460)

      返信
  3. gustafn

    xotcl2 has more strict rules about stack frame (a self has to be called from a method frame; since myproc/myvar are tcl-procs, it is not allowed to call "self" on these). The problem is not in your code, but in xotcl2.tcl, which i fixed already in my local copy; will commit soon). If you add the following two lines after "package req XOTcl", the code should work with nsf2.0b3

    proc myproc {args} {linsert $args 0 [uplevel ::nsf::self]}
    proc myvar {var} {[uplevel ::nsf::self] requireNamespace; return [uplevel ::nsf::self]::$var}

    i am currently on vacation in an arabian desert, i have just tested with the head version. With the change the tests from the init file run fine.

    返信
    1. Yusuke Yamasaki 投稿作成者

      Nothing changed by the following code. But you don't have to fix it in hurry. Enjoy your vacation.

      package require -exact XOTcl 2.0b3
      namespace import xotcl::*
      proc myproc {args} {linsert $args 0 [uplevel ::nsf::self]}
      proc myvar {var} {[uplevel ::nsf::self] requireNamespace; return [uplevel ::nsf::self]::$var}

      I needed to remove "namespace import xotcl::*" from every files because it complains that "myproc" already exists. After that, I saw the same errors as before.

      返信
  4. gustafn

    Dear Yusuke, i tried now with 2.0b3 instead of the head version. One needs

    package require -exact XOTcl 2.0b3
    proc ::xotcl::myproc {args} {linsert $args 0 [uplevel ::nsf::self]}
    proc ::xotcl::myvar {var} {[uplevel ::nsf::self] requireNamespace; return [uplevel ::nsf::self]::$var}

    instead of the version without the "::xotcl::" prefix. It depends, in which context myproc/myvar is called. Seems to work for the test cases. Please check, if this works as well with your full application.

    all the best -gustaf

    返信
  5. Yusuke Yamasaki 投稿作成者

    Dear gustafn,

    It worked for both sample code above and my full application!

    XOSql 0.78 generates a warning, but it seems not harmful for my application.
    "Warning: Arguments 'component xdobry::sqlite' to constructor of object ::idemeta are most likely not processed"

    I guess it's about xodoc.

    Now my application is ready for XOTcl 2. Thank you!

    Regards,
    Yusuke

    返信
  6. gustafn

    XOTclIDE uses in version up to 0.84 absolute object names as method names for the meta-data object "@". Version 0.85 changed this. In XOSql 0.78 (part of your lib) are the old names, which should be changed via:

    cd activerecord*/lib
    perl -pi -e 's/^@ ::/@ /g' `fgrep -rl '@ ::' .`

    Otherwise the meta-data is lost, when you would edit XOSql with XOTclIDE (which i think is not your intention, but anyway).

    Glad, that fixing was this easy

    all the best
    -gustaf neumann

    返信

コメントを残す