You can improve speed in TCL (and probably python as well) by:

stop searching down any column once the position is past the current shortest sequence found.

when a new short sequence is found, save only enough information to generate the result. Only when all columns are searched, do the work to generate the result. Saving copies of even large structures is very fast in TCL (the C code just copies of a pointer, and increments a reference count).

In TCL if the data is organized as a list of sequences (which are lists of 0 and 1) the foreach command can be used to process the list of columns and the list of bits in each column.

I'm seeing about a 10x speed up over the original code by using these suggestions, where both are procedures (to get them compiled).

Dave B

clt.to...@dfgh.net 在 2023年4月22日 星期六晚上8:04:24 [UTC+12] 的信中寫道：
> You can improve speed in TCL (and probably python as well) by:
>
> stop searching down any column once the position is past the current shortest sequence found.
>
> when a new short sequence is found, save only enough information to generate the result. Only when all columns are searched, do the work to generate the result. Saving copies of even large structures is very fast in TCL (the C code just copies of a pointer, and increments a reference count).
>
> In TCL if the data is organized as a list of sequences (which are lists of 0 and 1) the foreach command can be used to process the list of columns and the list of bits in each column.
>
> I'm seeing about a 10x speed up over the original code by using these suggestions, where both are procedures (to get them compiled).
>
> Dave B

Hi Dave

thanks for your advice , already change the search method ,as you mention get the ideal speed
what I post the topic is search for more help , if the search method no room to improve , how to improve tcl performance ...
different lang have performance gap..
Could you point out my code where to improve with same search method.

BR
Rolance

On 4/22/2023 2:28 AM, rola...@gmail.com wrote:
> clt.to...@dfgh.net 在 2023年4月22日 星期六晚上8:04:24 [UTC+12] 的信中寫道：
>> You can improve speed in TCL (and probably python as well) by:
>>
>> stop searching down any column once the position is past the current shortest sequence found.
>>
>> when a new short sequence is found, save only enough information to generate the result. Only when all columns are searched, do the work to generate the result. Saving copies of even large structures is very fast in TCL (the C code just copies of a pointer, and increments a reference count).
>>
>> In TCL if the data is organized as a list of sequences (which are lists of 0 and 1) the foreach command can be used to process the list of columns and the list of bits in each column.
>>
>> I'm seeing about a 10x speed up over the original code by using these suggestions, where both are procedures (to get them compiled).
>>
>> Dave B
>
> Hi Dave
>
> thanks for your advice , already change the search method ,as you mention get the ideal speed
> what I post the topic is search for more help , if the search method no room to improve , how to improve tcl performance ...
> different lang have performance gap..
> Could you point out my code where to improve with same search method.
>
> BR
> Rolance

As Dave suggested, using a list of lists is likely the best bet. Then
you could use [lindex $matrix $i $j] for the test, and don't test against
being = to 1, just do a boolean test.

you can see the bytecode with

tcl::unsupported::disassemble proc find_shortest_hit_org

or

tcl::unsupported::disassemble script {if {[lindex $lst 1 1]} {set x 1}}

where one would see (partially shown):
...
Command 1: "if {[lindex $lst 1 1]} {set x 1}"
Command 2: "lindex $lst 1 1..."
(0) push1 0 # "lst"
(2) loadStk
(3) push1 1 # "1"
(5) push1 1 # "1"
(7) lindexMulti 3
(12) nop
(13) jumpFalse1 +9 # pc 22

so there is a specific byte code for an lindex with more than 1 index
and you can use the [time] command to just test small script code, say
to compare an array lookup vs. a list lookup.

et99 在 2023年4月23日 星期日凌晨4:39:55 [UTC+12] 的信中寫道：
> On 4/22/2023 2:28 AM, rola...@gmail.com wrote:
> > clt.to...@dfgh.net 在 2023年4月22日 星期六晚上8:04:24 [UTC+12] 的信中寫道：
> >> You can improve speed in TCL (and probably python as well) by:
> >>
> >> stop searching down any column once the position is past the current shortest sequence found.
> >>
> >> when a new short sequence is found, save only enough information to generate the result. Only when all columns are searched, do the work to generate the result. Saving copies of even large structures is very fast in TCL (the C code just copies of a pointer, and increments a reference count).
> >>
> >> In TCL if the data is organized as a list of sequences (which are lists of 0 and 1) the foreach command can be used to process the list of columns and the list of bits in each column.
> >>
> >> I'm seeing about a 10x speed up over the original code by using these suggestions, where both are procedures (to get them compiled).
> >>
> >> Dave B
> >
> > Hi Dave
> >
> > thanks for your advice , already change the search method ,as you mention get the ideal speed
> > what I post the topic is search for more help , if the search method no room to improve , how to improve tcl performance ...
> > different lang have performance gap..
> > Could you point out my code where to improve with same search method.
> >
> > BR
> > Rolance
> As Dave suggested, using a list of lists is likely the best bet. Then
> you could use [lindex $matrix $i $j] for the test, and don't test against
> being = to 1, just do a boolean test.
>
> you can see the bytecode with
>
> tcl::unsupported::disassemble proc find_shortest_hit_org
>
> or
>
> tcl::unsupported::disassemble script {if {[lindex $lst 1 1]} {set x 1}}
>
> where one would see (partially shown):
> ...
> Command 1: "if {[lindex $lst 1 1]} {set x 1}"
> Command 2: "lindex $lst 1 1..."
> (0) push1 0 # "lst"
> (2) loadStk
> (3) push1 1 # "1"
> (5) push1 1 # "1"
> (7) lindexMulti 3
> (12) nop
> (13) jumpFalse1 +9 # pc 22
>
>
> so there is a specific byte code for an lindex with more than 1 index
> and you can use the [time] command to just test small script code, say
> to compare an array lookup vs. a list lookup.

hi et99

thanks your suggestion , will try and report later.

BR
Rolance

On 4/22/2023 2:54 PM, rola...@gmail.com wrote:
> et99 在 2023年4月23日 星期日凌晨4:39:55 [UTC+12] 的信中寫道：
>> On 4/22/2023 2:28 AM, rola...@gmail.com wrote:
>>> clt.to...@dfgh.net 在 2023年4月22日 星期六晚上8:04:24 [UTC+12] 的信中寫道：
>>>> You can improve speed in TCL (and probably python as well) by:
>>>>
>>>> stop searching down any column once the position is past the current shortest sequence found.
>>>>
>>>> when a new short sequence is found, save only enough information to generate the result. Only when all columns are searched, do the work to generate the result. Saving copies of even large structures is very fast in TCL (the C code just copies of a pointer, and increments a reference count).
>>>>
>>>> In TCL if the data is organized as a list of sequences (which are lists of 0 and 1) the foreach command can be used to process the list of columns and the list of bits in each column.
>>>>
>>>> I'm seeing about a 10x speed up over the original code by using these suggestions, where both are procedures (to get them compiled).
>>>>
>>>> Dave B
>>>
>>> Hi Dave
>>>
>>> thanks for your advice , already change the search method ,as you mention get the ideal speed
>>> what I post the topic is search for more help , if the search method no room to improve , how to improve tcl performance ...
>>> different lang have performance gap..
>>> Could you point out my code where to improve with same search method.
>>>
>>> BR
>>> Rolance
>> As Dave suggested, using a list of lists is likely the best bet. Then
>> you could use [lindex $matrix $i $j] for the test, and don't test against
>> being = to 1, just do a boolean test.
>>
>> you can see the bytecode with
>>
>> tcl::unsupported::disassemble proc find_shortest_hit_org
>>
>> or
>>
>> tcl::unsupported::disassemble script {if {[lindex $lst 1 1]} {set x 1}}
>>
>> where one would see (partially shown):
>> ...
>> Command 1: "if {[lindex $lst 1 1]} {set x 1}"
>> Command 2: "lindex $lst 1 1..."
>> (0) push1 0 # "lst"
>> (2) loadStk
>> (3) push1 1 # "1"
>> (5) push1 1 # "1"
>> (7) lindexMulti 3
>> (12) nop
>> (13) jumpFalse1 +9 # pc 22
>>
>>
>> so there is a specific byte code for an lindex with more than 1 index
>> and you can use the [time] command to just test small script code, say
>> to compare an array lookup vs. a list lookup.
>
> hi et99
>
> thanks your suggestion , will try and report later.
>
> BR
> Rolance

I did a test using the [lindex $matrix $i $j] and found about a 40% reduction
in time.

It appears that the overhead is beginning to get down to the "if test" and the
"for loop".

This is why Dave is suggesting you use foreach, which has less to do on each
iteration, since the test for the end and incrementing the index is effectively
done in the C code whereas a for loop does that in script code:

% tcl::unsupported::disassemble script {for {set i 1} {$i < $num_rows} {incr i} {doit}}
ByteCode 0x05902750, refCt 1, epoch 17, interp 0x00939060 (epoch 17)
Source "for {set i 1} {$i < $num_rows} {incr i} {doit}"
Cmds 4, src 46, inst 39, litObjs 5, aux 0, stkDepth 2, code/src 0.00
Exception ranges 2, depth 1:
0: level 0, loop, pc 8-11, continue 13, break 36
1: level 0, loop, pc 13-25, continue -1, break 36
Commands 4:
1: pc 0-37, src 0-45 2: pc 0-4, src 5-11
3: pc 8-11, src 41-44 4: pc 13-25, src 32-37
Command 1: "for {set i 1} {$i < $num_rows} {incr i} {doit}"
Command 2: "set i 1..."
(0) push1 0 # "i"
(2) push1 1 # "1"
(4) storeStk
(5) pop
(6) jump1 +21 # pc 27
Command 3: "doit..."
(8) push1 2 # "doit"
(10) invokeStk1 1
(12) pop
Command 4: "incr i..."
(13) startCommand +13 1 # next cmd at pc 26, 1 cmds start here
(22) push1 0 # "i"
(24) incrStkImm +1
(26) pop
(27) push1 0 # "i"
(29) loadStk
(30) push1 3 # "num_rows"
(32) loadStk
(33) lt
(34) jumpTrue1 -26 # pc 8
(36) push1 4 # ""
(38) done

% tcl::unsupported::disassemble script {foreach i $list {doit}}
ByteCode 0x05902650, refCt 1, epoch 17, interp 0x00939060 (epoch 17)
Source "foreach i $list {doit}"
Cmds 1, src 22, inst 12, litObjs 4, aux 0, stkDepth 4, code/src 0.00
Commands 1:
1: pc 0-10, src 0-21
Command 1: "foreach i $list {doit}"
(0) push1 0 # "foreach"
(2) push1 1 # "i"
(4) push1 2 # "list"
(6) loadStk
(7) push1 3 # "doit"
(9) invokeStk1 4
(11) done

On 4/22/2023 3:23 PM, et99 wrote:
> On 4/22/2023 2:54 PM, rola...@gmail.com wrote:
>> et99 在 2023年4月23日 星期日凌晨4:39:55 [UTC+12] 的信中寫道：
>>> On 4/22/2023 2:28 AM, rola...@gmail.com wrote:
>>>> clt.to...@dfgh.net 在 2023年4月22日 星期六晚上8:04:24 [UTC+12] 的信中寫道：
>>>>> You can improve speed in TCL (and probably python as well) by:
>>>>>
>>>>> stop searching down any column once the position is past the current shortest sequence found.
>>>>>
>>>>> when a new short sequence is found, save only enough information to generate the result. Only when all columns are searched, do the work to generate the result. Saving copies of even large structures is very fast in TCL (the C code just copies of a pointer, and increments a reference count).
>>>>>
>>>>> In TCL if the data is organized as a list of sequences (which are lists of 0 and 1) the foreach command can be used to process the list of columns and the list of bits in each column.
>>>>>
>>>>> I'm seeing about a 10x speed up over the original code by using these suggestions, where both are procedures (to get them compiled).
>>>>>
>>>>> Dave B
>>>>
>>>> Hi Dave
>>>>
>>>> thanks for your advice , already change the search method ,as you mention get the ideal speed
>>>> what I post the topic is search for more help , if the search method no room to improve , how to improve tcl performance ...
>>>> different lang have performance gap..
>>>> Could you point out my code where to improve with same search method.
>>>>
>>>> BR
>>>> Rolance
>>> As Dave suggested, using a list of lists is likely the best bet. Then
>>> you could use [lindex $matrix $i $j] for the test, and don't test against
>>> being = to 1, just do a boolean test.
>>>
>>> you can see the bytecode with
>>>
>>> tcl::unsupported::disassemble proc find_shortest_hit_org
>>>
>>> or
>>>
>>> tcl::unsupported::disassemble script {if {[lindex $lst 1 1]} {set x 1}}
>>>
>>> where one would see (partially shown):
>>> ...
>>> Command 1: "if {[lindex $lst 1 1]} {set x 1}"
>>> Command 2: "lindex $lst 1 1..."
>>> (0) push1 0 # "lst"
>>> (2) loadStk
>>> (3) push1 1 # "1"
>>> (5) push1 1 # "1"
>>> (7) lindexMulti 3
>>> (12) nop
>>> (13) jumpFalse1 +9 # pc 22
>>>
>>>
>>> so there is a specific byte code for an lindex with more than 1 index
>>> and you can use the [time] command to just test small script code, say
>>> to compare an array lookup vs. a list lookup.
>>
>> hi et99
>>
>> thanks your suggestion , will try and report later.
>>
>> BR
>> Rolance
>
>
> I did a test using the [lindex $matrix $i $j] and found about a 40% reduction
> in time.
>
> It appears that the overhead is beginning to get down to the "if test" and the
> "for loop".
>
> This is why Dave is suggesting you use foreach, which has less to do on each
> iteration, since the test for the end and incrementing the index is effectively
> done in the C code whereas a for loop does that in script code:
>
>
>
> % tcl::unsupported::disassemble script {for {set i 1} {$i < $num_rows} {incr i} {doit}}
> ByteCode 0x05902750, refCt 1, epoch 17, interp 0x00939060 (epoch 17)
>   Source "for {set i 1} {$i < $num_rows} {incr i} {doit}"
>   Cmds 4, src 46, inst 39, litObjs 5, aux 0, stkDepth 2, code/src 0.00
>   Exception ranges 2, depth 1:
>       0: level 0, loop, pc 8-11, continue 13, break 36
>       1: level 0, loop, pc 13-25, continue -1, break 36
>   Commands 4:
>       1: pc 0-37, src 0-45        2: pc 0-4, src 5-11
>       3: pc 8-11, src 41-44        4: pc 13-25, src 32-37
>   Command 1: "for {set i 1} {$i < $num_rows} {incr i} {doit}"
>   Command 2: "set i 1..."
>     (0) push1 0     # "i"
>     (2) push1 1     # "1"
>     (4) storeStk
>     (5) pop
>     (6) jump1 +21     # pc 27
>   Command 3: "doit..."
>     (8) push1 2     # "doit"
>     (10) invokeStk1 1
>     (12) pop
>   Command 4: "incr i..."
>     (13) startCommand +13 1     # next cmd at pc 26, 1 cmds start here
>     (22) push1 0     # "i"
>     (24) incrStkImm +1
>     (26) pop
>     (27) push1 0     # "i"
>     (29) loadStk
>     (30) push1 3     # "num_rows"
>     (32) loadStk
>     (33) lt
>     (34) jumpTrue1 -26     # pc 8
>     (36) push1 4     # ""
>     (38) done
>
> % tcl::unsupported::disassemble script {foreach i $list {doit}}
> ByteCode 0x05902650, refCt 1, epoch 17, interp 0x00939060 (epoch 17)
>   Source "foreach i $list {doit}"
>   Cmds 1, src 22, inst 12, litObjs 4, aux 0, stkDepth 4, code/src 0.00
>   Commands 1:
>       1: pc 0-10, src 0-21
>   Command 1: "foreach i $list {doit}"
>     (0) push1 0     # "foreach"
>     (2) push1 1     # "i"
>     (4) push1 2     # "list"
>     (6) loadStk
>     (7) push1 3     # "doit"
>     (9) invokeStk1 4
>     (11) done
>
>

On last thought on using foreach, the index is the item itself, 0 or 1, and so
the if test doesn't have to do an array or lindex list lookup.
Something like this:

foreach row {list of the rows}
foreach column $row
if {$column} ....

Actually, I couldn't really tell if you searching a row or a column,
so adjust as needed.