|
2026-10-21
| ||
| 10:03 | • Closed ticket [1483802fff]: lsort inconsistant behavior for negative value of -... artifact: 1bafbcc27e user: serhiy.storchaka | |
|
2024-10-02
| ||
| 07:47 | • Ticket [db36fa5122] compiled lindex botches index artihmetic status still Cl... artifact: 16e185335b user: pooryorick | |
|
2018-03-10
| ||
| 14:55 | [db36fa5122] Upgrade the index value parsing and encoding machinery. Refactor many systems to make c... check-in: 02721ee263 user: dgp tags: core-8-branch | |
|
2018-03-09
| ||
| 22:19 | • Closed ticket [db36fa5122]: compiled lindex botches index artihmetic plus 7 ... artifact: 45bccf89ac user: dgp | |
| 22:18 | [db36fa5122] Upgrade the index value parsing and encoding machinery. Refactor many systems to make c... check-in: 71c0a83836 user: dgp tags: core-8-6-branch | |
| 12:31 | • Ticket [db36fa5122] compiled lindex botches index artihmetic status still Op... artifact: 0a0f560677 user: dgp | |
|
2018-03-07
| ||
| 20:41 | • Ticket [db36fa5122]: 3 changes artifact: 444f88b585 user: sebres | |
| 16:14 | • Ticket [db36fa5122]: 3 changes artifact: a30bf24dc7 user: sebres | |
| 15:31 | • Ticket [db36fa5122]: 3 changes artifact: dfd44a4f58 user: dgp | |
| 15:29 | • Ticket [db36fa5122]: 3 changes artifact: d6132a0b84 user: dgp | |
|
2018-03-06
| ||
| 21:59 | try to fix [db36fa5122]: better compiled variants of several indices-related commands, test-cases ex... check-in: 82d6ec9fbb user: sebres tags: sebres-bug-db36fa5122 | |
| 20:31 | • Ticket [db36fa5122] compiled lindex botches index artihmetic status still Op... artifact: 84bda65dfb user: sebres | |
| 20:08 | • Ticket [db36fa5122]: 3 changes artifact: 0f82b94cd3 user: dgp | |
| 17:44 | • Ticket [db36fa5122]: 3 changes artifact: 9819f3c631 user: sebres | |
| 17:41 | • Ticket [db36fa5122]: 3 changes artifact: d5da71b806 user: dgp | |
| 15:53 | • Ticket [db36fa5122]: 3 changes artifact: 146fe88cb8 user: dgp | |
| 15:49 | • Ticket [db36fa5122]: 3 changes artifact: 01c4a060da user: dgp | |
| 15:39 | • Ticket [db36fa5122]: 3 changes artifact: d44d071ced user: dgp | |
| 15:36 | • Ticket [db36fa5122]: 3 changes artifact: a48afc79a6 user: dgp | |
| 15:31 | • Ticket [db36fa5122]: 3 changes artifact: b70bf03ac2 user: dgp | |
| 14:51 | • Ticket [db36fa5122]: 3 changes artifact: f10551dbef user: dgp | |
| 14:48 | • Ticket [db36fa5122]: 3 changes artifact: 32da801af5 user: dgp | |
| 14:41 | • Ticket [db36fa5122]: 3 changes artifact: d0a3c1d0e8 user: dgp | |
| 14:31 | • Ticket [db36fa5122]: 3 changes artifact: 71ffb9db1e user: dgp | |
|
2018-03-01
| ||
| 23:16 | • Ticket [db36fa5122]: 3 changes artifact: cef68870ce user: sebres | |
| 19:10 | • Ticket [db36fa5122]: 4 changes artifact: 2026945604 user: dgp | |
| 18:24 | • New ticket [db36fa5122]. artifact: 2369e70516 user: dgp | |
| 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]. | ||||||
