| Ticket UUID: | 322720f99dbe67f791e557876bd46e734544b988 | ||
| Title: | Poor bytecode (optimizations?) for || and && | ||
| Type: | Bug | Created on: | 2017-02-06 18:37:28 |
| Submitter: | dgp | Assigned to: | nobody |
| Subsystem: | 47. Bytecode Compiler | Severity: | Minor |
| Priority: | 5 Medium | Last modified: | 2017-03-04 12:38:12 |
| Status: | Open | Closed by: | nobody |
| Resolution: | None | Closed on: | |
| Version: | 8.6.6 | ||
| Description: | ||||
Code example: http://ideone.com/swBln7
proc isTest-1 {arg} {
if {[string match "0" $arg] || [string match "1" $arg] || [string match "2" $arg] || [string match "3" $arg] || [string match "4" $arg]} {
return 1
}
return 0
}
proc isTest-2 {arg} {
if {[string match "0" $arg]} {
return 1
}
if {[string match "1" $arg]} {
return 1
}
if {[string match "2" $arg]} {
return 1
}
if {[string match "3" $arg]} {
return 1
}
if {[string match "4" $arg]} {
return 1
}
return 0
}
set script(1) {if {[isTest-1 "10"] == "-"} {} else {}}
puts "1: Result: [isTest-1 "10"] | Time: [time $script(1) 10000]"
set script(2) {if {[isTest-2 "10"] == "-"} {} else {}}
puts "2: Result: [isTest-2 "10"] | Time: [time $script(2) 10000]"
puts [tcl::unsupported::disassemble proc isTest-1]
puts [tcl::unsupported::disassemble proc isTest-2]
Same problem when it comes to the && Operator
proc isTest-3 {arg} {
if {[string match "0" $arg] && [string match "1" $arg] && [string match "2" $arg] && [string match "3" $arg] && [string match "4" $arg]} {
return 1
}
return 0
}
proc isTest-4 {arg} {
if {[string match "0" $arg]} {
if {[string match "1" $arg]} {
if {[string match "2" $arg]} {
if {[string match "3" $arg]} {
if {[string match "4" $arg]} {
return "1"
}
}
}
}
}
return 0
}
set script(3) {if {[isTest-3 "10"] == "-"} {} else {}}
puts "3: Result: [isTest-3 "10"] | Time: [time $script(3) 10000]"
set script(4) {if {[isTest-4 "10"] == "-"} {} else {}}
puts "4: Result: [isTest-4 "10"] | Time: [time $script(4) 10000]"
puts [tcl::unsupported::disassemble proc isTest-3]
puts [tcl::unsupported::disassemble proc isTest-4]
| ||||
| User Comments: | ||||
dgp added on 2017-02-06 18:38:08:
1: Result: 0 | Time: 0.96 microseconds per iteration
2: Result: 0 | Time: 0.9339 microseconds per iteration
ByteCode 0x0x261dd40, refCt 1, epoch 15, interp 0x0x25d15b0 (epoch 15)
Source "\n if {[string match \"0\" $arg] || [string match ..."
File "/home/dgp/erp.tcl" Line 8
Cmds 8, src 190, inst 78, litObjs 6, aux 0, stkDepth 2, code/src 0.00
Proc 0x0x2629130, refCt 1, args 1, compiled locals 1
slot 0, scalar, arg, "arg"
Commands 8:
1: pc 0-74, src 7-169 2: pc 0-4, src 12-32
3: pc 7-11, src 39-59 4: pc 22-26, src 66-86
5: pc 37-41, src 93-113 6: pc 52-56, src 120-140
7: pc 67-69, src 154-161 8: pc 75-77, src 177-184
Command 1: "if {[string match \"0\" $arg] || [string match \"1\" $a..."
Command 2: "string match \"0\" $a..."
(0) push1 0 # "0"
(2) loadScalar1 %v0 # var "arg"
(4) streq
(5) jumpTrue1 +13 # pc 18
Command 3: "string match \"1\" $a..."
(7) push1 1 # "1"
(9) loadScalar1 %v0 # var "arg"
(11) streq
(12) jumpTrue1 +6 # pc 18
(14) push1 0 # "0"
(16) jump1 +4 # pc 20
(18) push1 1 # "1"
(20) jumpTrue1 +13 # pc 33
Command 4: "string match \"2\" $a..."
(22) push1 2 # "2"
(24) loadScalar1 %v0 # var "arg"
(26) streq
(27) jumpTrue1 +6 # pc 33
(29) push1 0 # "0"
(31) jump1 +4 # pc 35
(33) push1 1 # "1"
(35) jumpTrue1 +13 # pc 48
Command 5: "string match \"3\" $a..."
(37) push1 3 # "3"
(39) loadScalar1 %v0 # var "arg"
(41) streq
(42) jumpTrue1 +6 # pc 48
(44) push1 0 # "0"
(46) jump1 +4 # pc 50
(48) push1 1 # "1"
(50) jumpTrue1 +13 # pc 63
Command 6: "string match \"4\" $a..."
(52) push1 4 # "4"
(54) loadScalar1 %v0 # var "arg"
(56) streq
(57) jumpTrue1 +6 # pc 63
(59) push1 0 # "0"
(61) jump1 +4 # pc 65
(63) push1 1 # "1"
(65) jumpFalse1 +7 # pc 72
Command 7: "return 1..."
(67) push1 1 # "1"
(69) done
(70) nop
(71) nop
(72) push1 5 # ""
(74) pop
Command 8: "return 0..."
(75) push1 0 # "0"
(77) done
ByteCode 0x0x261ed40, refCt 1, epoch 15, interp 0x0x25d15b0 (epoch 15)
Source "\n if {[string match \"0\" $arg]} {\n retur..."
File "/home/dgp/erp.tcl" Line 15
Cmds 16, src 330, inst 83, litObjs 6, aux 0, stkDepth 2, code/src 0.00
Proc 0x0x2628430, refCt 1, args 1, compiled locals 1
slot 0, scalar, arg, "arg"
Commands 16:
1: pc 0-15, src 7-61 2: pc 0-4, src 12-32
3: pc 8-10, src 46-53 4: pc 16-31, src 69-123
5: pc 16-20, src 74-94 6: pc 24-26, src 108-115
7: pc 32-47, src 131-185 8: pc 32-36, src 136-156
9: pc 40-42, src 170-177 10: pc 48-63, src 193-247
11: pc 48-52, src 198-218 12: pc 56-58, src 232-239
13: pc 64-79, src 255-309 14: pc 64-68, src 260-280
15: pc 72-74, src 294-301 16: pc 80-82, src 317-324
Command 1: "if {[string match \"0\" $arg]} {\n return 1\n ..."
Command 2: "string match \"0\" $a..."
(0) push1 0 # "0"
(2) loadScalar1 %v0 # var "arg"
(4) streq
(5) nop
(6) jumpFalse1 +7 # pc 13
Command 3: "return 1..."
(8) push1 1 # "1"
(10) done
(11) nop
(12) nop
(13) push1 2 # ""
(15) pop
Command 4: "if {[string match \"1\" $arg]} {\n return 1\n ..."
Command 5: "string match \"1\" $a..."
(16) push1 1 # "1"
(18) loadScalar1 %v0 # var "arg"
(20) streq
(21) nop
(22) jumpFalse1 +7 # pc 29
Command 6: "return 1..."
(24) push1 1 # "1"
(26) done
(27) nop
(28) nop
(29) push1 2 # ""
(31) pop
Command 7: "if {[string match \"2\" $arg]} {\n return 1\n ..."
Command 8: "string match \"2\" $a..."
(32) push1 3 # "2"
(34) loadScalar1 %v0 # var "arg"
(36) streq
(37) nop
(38) jumpFalse1 +7 # pc 45
Command 9: "return 1..."
(40) push1 1 # "1"
(42) done
(43) nop
(44) nop
(45) push1 2 # ""
(47) pop
Command 10: "if {[string match \"3\" $arg]} {\n return 1\n ..."
Command 11: "string match \"3\" $a..."
(48) push1 4 # "3"
(50) loadScalar1 %v0 # var "arg"
(52) streq
(53) nop
(54) jumpFalse1 +7 # pc 61
Command 12: "return 1..."
(56) push1 1 # "1"
(58) done
(59) nop
(60) nop
(61) push1 2 # ""
(63) pop
Command 13: "if {[string match \"4\" $arg]} {\n return 1\n ..."
Command 14: "string match \"4\" $a..."
(64) push1 5 # "4"
(66) loadScalar1 %v0 # var "arg"
(68) streq
(69) nop
(70) jumpFalse1 +7 # pc 77
Command 15: "return 1..."
(72) push1 1 # "1"
(74) done
(75) nop
(76) nop
(77) push1 2 # ""
(79) pop
Command 16: "return 0..."
(80) push1 0 # "0"
(82) done
dgp added on 2017-02-06 18:39:16:
It's a micro-difference; low priority, but it does look like the generated bytecode is missing out on optimizations. Something to look at another day. sebres added on 2017-02-06 20:03:21:
It's not so micro, if you'll use much better test cases (without overhead and differentiate positive and negative case).
You'll see a difference up to 10%.
I've done it with following case:
proc isTest-1 {arg0 {arg1 {}} {arg2 {}} {arg3 {}} {arg4 {}}} {
if {"0" eq $arg0 || "1" eq $arg1 || "2" eq $arg2 || "3" eq $arg3 || "4" eq $arg4} {
return 1
}
return 0
}
proc isTest-2 {arg0 {arg1 {}} {arg2 {}} {arg3 {}} {arg4 {}}} {
if {"0" eq $arg0} {
return 1
}
if {"1" eq $arg1} {
return 1
}
if {"2" eq $arg2} {
return 1
}
if {"3" eq $arg3} {
return 1
}
if {"4" eq $arg4} {
return 1
}
return 0
}
proc isTest-3 {arg0 {arg1 {}} {arg2 {}} {arg3 {}} {arg4 {}}} {
if {"0" eq $arg0 && "1" eq $arg1 && "2" eq $arg2 && "3" eq $arg3 && "4" eq $arg4} {
return 1
}
return 0
}
proc isTest-4 {arg0 {arg1 {}} {arg2 {}} {arg3 {}} {arg4 {}}} {
if {"0" eq $arg0} {
if {"1" eq $arg1} {
if {"2" eq $arg2} {
if {"3" eq $arg3} {
if {"4" eq $arg4} {
return "1"
}
}
}
}
}
return 0
}
And my timerate branch (so without overhead for the measurenment):
_test_run 1000 {
{isTest-1 "0"}
{isTest-2 "0"}
{isTest-1 "10"}
{isTest-2 "10"}
{isTest-3 "0" "1" "2" "3" "4"}
{isTest-4 "0" "1" "2" "3" "4"}
{isTest-3 "10"}
{isTest-4 "10"}
}
% isTest-1 "0"
1
0.288243 µs/# 2974460 # 3469300 #/sec 857.366 nett-ms
% isTest-2 "0"
1
0.260195 µs/# 3245198 # 3843277 #/sec 844.383 nett-ms
% isTest-1 "10"
0
0.383712 µs/# 2316612 # 2606120 #/sec 888.912 nett-ms
% isTest-2 "10"
0
0.348312 µs/# 2523563 # 2870986 #/sec 878.988 nett-ms
% isTest-3 "0" "1" "2" "3" "4"
1
0.362434 µs/# 2436722 # 2759119 #/sec 883.152 nett-ms
% isTest-4 "0" "1" "2" "3" "4"
1
0.303204 µs/# 2847730 # 3298110 #/sec 863.443 nett-ms
% isTest-3 "10"
0
0.315672 µs/# 2750085 # 3167844 #/sec 868.125 nett-ms
% isTest-4 "10"
0
0.257093 µs/# 3278192 # 3889639 #/sec 842.801 nett-ms
dkf added on 2017-03-04 12:38:12:
The problem is that the optimiser is not detecting this:
Whereas it is clearly provable that converting it into just this:
would work fine (provided there are no other branches targeting anywhere inside the instruction sequence). Note that the optimiser as it stands needs to keep the instructions that are placed in the same location (hence the nops) but a compacting optimiser is entirely possible provided someone does the work.
There may be related issues with the instruction sequence for && and that should be checked at the same time. Test code should use tcl::unsupported::getbytecode instead of attempting to parse the disassembler output. | ||||
