| Ticket UUID: | db36fa5122259be74d0ccadd102e076094703052 | ||
| Title: | compiled lindex botches index artihmetic | ||
| Type: | Bug | Created on: | 2018-03-01 18:24:04 |
| Submitter: | dgp | Assigned to: | dgp |
| Subsystem: | 47. Bytecode Compiler | Severity: | Severe |
| Priority: | 5 Medium | Last modified: | 2024-10-02 07:47:28 |
| Status: | Closed | Closed by: | pooryorick |
| Resolution: | Fixed | Closed on: | 2024-10-02 07:47:28 |
| Version: | 8.6 | ||
| Description: | ||||||
% lindex {a b c} -1-1
c
Correct answer should be the empty string.
The bytecode compiler for [lindex] tries to
encode the indices "end", "end-1", .... etc.
as the immediate bytecode arguments -2, -3, ....
It ignores the possibility that TclGetIntForIndex()
can return those values as legit index values
resulting from index arithmetic. In this example
the index "-2" is getting interpreted as if it were "end".
| ||||||
| User Comments: | ||||||
dgp added on 2018-03-01 19:10:37:
% lrange {a b c} 0-3 0-2
b c
Same fundamental cause.
traces back to:
https://core.tcl.tk/tcl/info/533a2ba7b7d13364
sebres added on 2018-03-01 23:16:44:
Same here:
But still worse (I think it is similar to your fix [650f9e6c7c]):
The main issue here is - TclGetIntForIndex can not distinguish between Rather we need still one command, like TclGetIntForIndexC which will return I assume both may be needed. I've one minimalistic fix for it as well as one own branch, where it is already correct implemented, will try to back-port it tomorrow to 8.6th. dgp added on 2018-03-06 14:31:48:
Tcl 8.5 had two opcodes which took integer operands representing index values determined at compile time (OPERAND_IDX4). INST_LIST_INDEX_IMM INST_LIST_RANGE_IMM They agree on an encoding that the operand values -1, 0, 1, ..., INT_MAX stand for the same index values, while the operand values -2, -3, ..., INT_MIN stand for the index values end, end-1, ... end-(INT_MIN+2) If a command compiler encounters an index value known at compile time that doesn't fit in these supported ranges, it will have to emit the other instruction INST_LIST_INDEX or fallback to runtime invocation. dgp added on 2018-03-06 14:41:43:
It's an unfortunate property of that encoding that it has no room to encode useful and fairly common index values such as end+1, end+2, ... dgp added on 2018-03-06 14:48:22:
...although for these instructions, they can be translated into functional equivalents with values in the supported range. lindex $l end+1 can become "PUSH $l" INST_LIST_INDEX_IMM -1 because taking the value (none, empty) just before the start of the list is functionally the same as taking the value (none, empty) just after the end of the list. dgp added on 2018-03-06 14:51:03:
In the cases where we know at compile time the index points outside the list, we might be tempted to replace the whole thing with just "PUSH $empty" but that would miss out on any bytecode that creates $l, and miss out on the check the $l is a valid list. dgp added on 2018-03-06 15:31:13:
In Tcl 8.5, although LIST_INDEX_IMM will accept negative operand values, none of the compiled commands generate them. It's an unused facility of the bytecode execution engine. dgp added on 2018-03-06 15:36:13:
In Tcl 8.5 the opcode INST_LIST_RANGE_IMM is issued only in the compilation of [lassign] to determine the return value of the command as, effectively, [lrange $l $last+1 end]. The integer value $last+1 is an operand and "-2" is used for "end", making use of the encoding facility. The same effect could have been achieved with operand values of either LIST_MAX or INT_MAX. Conclusion: Tcl 8.5 makes little use of the index encoding, and no necessary use. Lots of excess unused capability in the execution engine. dgp added on 2018-03-06 15:39:39:
In Tcl 8.6, the new instruction INST_STR_RANGE_IMM also makes use of index value operands (OPERAND_IDX4). It respects the same encoding. dgp added on 2018-03-06 15:49:00:
Tcl 8.6 also added an assembler and provides in it access to
the INST_LIST_INDEX_IMM instruction. It botches index compiling
in the same way -- misusing TclGetIntForIndex(), like so:
% tcl::unsupported::assemble {
push {a b c};
listIndexImm end+2
}
a
% tcl::unsupported::assemble {
push {a b c};
listIndexImm -1-1
}
c
The other index-value-using instructions are not in the
instruction set of the assembler. I guess it lags.
dgp added on 2018-03-06 15:53:38:
The common fix needed for all these command compilers is access to a TclGetEndOffsetFromObj() routine that can detect exactly the end+/-N format the compilers need to detect as a separate case to properly encode. This is not difficult. Practically already done in the TIP 445 branch. dgp added on 2018-03-06 17:41:26:
After reviewing the command compilers that generate these opcodes, some of them are a true mess. The good news is that except the assembler they all route through a common routine TclGetIndexFromToken to parse index values, so we should be able to do all the fixing there. sebres added on 2018-03-06 17:44:22:
> "PUSH $empty" > miss out on the check the $l is a valid list. Don't need use it, because another hack may be applied very easy. Normally, INST_LIST_INDEX_IMM expected operand >= 0 and < -1. But, if you'll use -1 and put following code, you'll always get an empty return-value, as well as do the list validation inside: ```tcl-byte-code (0) push1 0 (2) listIndexImm -1 (7) done ``` > Practically already done in the TIP 445 branch. Are you sure, Don? I see nothing about this in this branch... WiP. I'll push soon a new branch with fix and test cases for all this mentioned. dgp added on 2018-03-06 20:08:30:
That's what I meant to say, so I think we're in agreement. I knew that TIP445 had a GetEndOffsetFromObj() routine. Now that I've had a look, it wasn't precisely what I needed. sebres added on 2018-03-06 20:31:35:
Still one inconsistency round about indices by lreplace:
Negative out of range (before start) is allowed.
Positive out of range (after end) is disallowed.
% lreplace {a b c d} end-10 end-9
a b c d
% lreplace {a b c d} -3 -2
a b c d
% lreplace {a b c d} 6 7
list doesn't contain element 6
% lreplace {a b c d} end+2 end+3
list doesn't contain element end+2
But it allows exactly +1 after end:
% lreplace {a b c d} end+1 end+3
a b c d
Which is IMHO wrong and at least inconsistent at all.
Rather it should throw an error in both cases, or (I prefer it) it should ignore out of range (in both cases also).
I assume it is not really a bug, but if it is feature, then IMHO very-very questionable.
dgp added on 2018-03-07 15:29:22:
I see [lsort] uses a parallel scheme of encoding index values as integers. dgp added on 2018-03-07 15:31:17:
If anything is clear from this and related tickets, [lreplace] is a complete abomination. sebres added on 2018-03-07 16:14:02:
> [lreplace] is a complete abomination.
Yeap, IMHO it should rather get own instruction.
For example considering the performance of resulting construct for the
byte-code, it is hardly faster as direct invocation (by special cases like remove) and
even slower! as not compiled invoke-variant (by replace).
## remove:
% tcl::unsupported::disassemble script {lreplace a 1 2}
ByteCode ...
Source "lreplace a 1 2"
Cmds 1, src 14, inst 52, litObjs 4, aux 0, stkDepth 3, code/src 0.00
Commands 1:
1: pc 0-50, src 0-13
Command 1: "lreplace a 1 2"
(0) push1 0 # "a"
(2) dup
(3) listLength
(4) push1 1 # "1"
(6) ge
(7) jumpTrue1 +19 # pc 26
(9) dup
(10) listLength
(11) jumpFalse1 +15 # pc 26
(13) push1 2 # "list doesn't contain element 1"
(15) push1 3 # "-errorcode {TCL OPERATION LREPLACE BADID..."
(17) returnImm +1 0
(26) dup
(27) listRangeImm 0 0
(36) reverse 2
(41) listRangeImm 3 end
(50) listConcat
(51) done
% tcl::unsupported::disassemble script {lreplace a end+1 end+2}
ByteCode ...
Source "lreplace a end+1 end+2"
Cmds 1, src 22, inst 11, litObjs 4, aux 0, stkDepth 4, code/src 0.00
Commands 1:
1: pc 0-9, src 0-21
Command 1: "lreplace a end+1 end+2"
(0) push1 0 # "lreplace"
(2) push1 1 # "a"
(4) push1 2 # "end+1"
(6) push1 3 # "end+2"
(8) invokeStk1 4
(10) done
% timerate {lreplace a 1 2}; # compiled
0.176311 µs/# 4526429 # 5671797 #/sec 798.059 nett-ms
% timerate {lreplace a end+1 end+2}; # invoke
0.205086 µs/# 4004816 # 4876013 #/sec 821.330 nett-ms
## replace:
% tcl::unsupported::disassemble script {lreplace a 1 2 x}
ByteCode ...
Source "lreplace a 1 2 x"
Cmds 1, src 16, inst 75, litObjs 5, aux 0, stkDepth 4, code/src 0.00
Commands 1:
1: pc 0-73, src 0-15
Command 1: "lreplace a 1 2 x"
(0) push1 0 # "a"
(2) push1 1 # "x"
(4) list 1
(9) reverse 2
(14) dup
(15) listLength
(16) push1 2 # "1"
(18) ge
(19) jumpTrue1 +19 # pc 38
(21) dup
(22) listLength
(23) jumpFalse1 +15 # pc 38
(25) push1 3 # "list doesn't contain element 1"
(27) push1 4 # "-errorcode {TCL OPERATION LREPLACE BADID..."
(29) returnImm +1 0
(38) dup
(39) listRangeImm 0 0
(48) reverse 2
(53) listRangeImm 3 end
(62) reverse 3
(67) listConcat
(68) reverse 2
(73) listConcat
(74) done
% tcl::unsupported::disassemble script {lreplace a end+1 end+2 x}
ByteCode ...
Source "lreplace a end+1 end+2 x"
Cmds 1, src 24, inst 13, litObjs 5, aux 0, stkDepth 5, code/src 0.00
Commands 1:
1: pc 0-11, src 0-23
Command 1: "lreplace a end+1 end+2 x"
(0) push1 0 # "lreplace"
(2) push1 1 # "a"
(4) push1 2 # "end+1"
(6) push1 3 # "end+2"
(8) push1 4 # "x"
(10) invokeStk1 5
(12) done
% timerate {lreplace a 1 2 x}; # compiled
0.303333 µs/# 2874003 # 3296706 #/sec 871.780 nett-ms
% timerate {lreplace a end+1 end+2 x}; # invoke
0.223937 µs/# 3723690 # 4465541 #/sec 833.872 nett-ms
Note that by invoke it does additionally NRE-, stack to local normalization (decache stack info, etc),
TEBC_YIELD, then exits from TEBCResume.
Let alone the code complexity, the growth of the byte-code size, CPU-cache washouts, etc.
It is very questionable why such constructs should be implemented with tcl byte-code instead of pure C.
> I see [lsort] uses a parallel scheme of encoding index values as integers.
Yes, as you possibly saw, I have already added a test cases for it.
Unfortunately, it affects basically many other things, that using TclGetIntForIndexM (TclGetIntForIndex)
with fixed (supplied before known) value of `endValue`,
like TCL_INDEX_END, SORTIDX_END, etc.
sebres added on 2018-03-07 20:41:51:
To [31a078bec7]:
index = opnd + (opnd <= TCL_INDEX_END)*(objc - 1 - TCL_INDEX_END);
Please don't do such optimizations, Don! See https://godbolt.org/g/T8HB8w (gcc 7.3),In case that link does not work (expired): Following C code:
#define TCL_INDEX_END (-2)
int test1(int opnd, int objc) {
int index;
index = opnd + (opnd <= TCL_INDEX_END)*(objc - 1 - TCL_INDEX_END);
return index;
}
int test2(int opnd, int objc) {
int index;
if ((index = opnd) <= TCL_INDEX_END) {
index += (objc - 1 - TCL_INDEX_END);
}
return index;
}
will get:
dgp added on 2018-03-09 12:31:27:
Another variant where the encoded index value is escaping to script level:
% lsearch -subindices -index end-1 {{a 1}} a
0 -3
Correct answer should be:
0 0
dgp added on 2018-03-09 22:19:26:
Fixed for 8.6.9 pooryorick added on 2024-10-02 07:47:28:
For reference, the commit for the fix is [02721ee263bbe32a]. | ||||||
