3 ms·

> It's useful to allow it to make `if (ptr < end)` with exclusive `end` possible. The alternative of only allowing `if (ptr <= end)` with inclusive `end` is not

> It's useful to allow it to make `if (ptr < end)` with exclusive `end` possible. The alternative of only allowing `if (ptr <= end)` with inclusive `end` is not as trivial if it needs to handle empty ranges (the exclusive version can just use `end = start` to denote an empty range). As an aside: I find it fascinating that half-open ranges turn out to be - universally as far as I can tell - the right choice for ranges in software. As well as being able to store an empty range, they also allow you to calculate the length of the range by trivially subtracting end - start.

tialaramex 2y ago
For the growable array and slice types (C++ std::vector and std::span) at a low level we should actually store ptr and length not start and end, it makes a tiny but measurable performance difference. This is one of the tiny perf leaks from C++ ABI conservation. IIRC All three popular std::vector implementations got this wrong decades ago and are now ABI frozen so too bad. The design of std::span is correct though for whatever that's worth.
- adrian_b 2y ago
  Storing the length instead of the address past the last element does not change anything in the answer to the question posed by the previous poster. The length of an array is the index of an element beyond the limit of the array, which would be invalid in an indexed expression for accessing an array element. Exactly like when using pointers the address beyond the last element of the array is useful, when using indices the length, i.e. the index beyond the last element of the array, is useful. Moreover, regardless how the arrays are handled in a high-level programming language, on CPU architectures that provide SIB (scaled index + base) addressing modes instead of auto-incremented/auto-decremented addressing modes, e.g. on x86-64, there are frequently encountered cases when the optimal implementation of a loop in machine instructions requires a base register initialized to the address of the element beyond the array limit, together with an index register that contains negative indices, which is incremented at each iteration until it becomes non-negative, in order to access the array in increasing order. (Positive indices that are decremented until becoming negative, together with a base register containing the address of the first array element, are used when the arrays must be accessed in decreasing order.) In optimal implementations on x86-64 and similar ISAs it does not matter much which value between length and address past the array you choose to store in an array descriptor. When the loop is initialized in machine instructions you may need frequently the third value that is not stored, but that is pretty much irrelevant, because an extra addition or subtraction is usually done in zero time on modern CPUs (i.e. concurrently with the other instructions that would have been executed anyway, even when the extra addition/subtraction would not have been necessary). Because arrays are more frequently accessed in increasing order, even when that is not necessary, for the purpose of just accessing the array it would be optimal to store in the array descriptor the length together with the address of the element beyond the array. However this would be worse in conjunction with legacy APIs that would expect the address of the first element, which would require an extra subtraction, and also when accessing just an array element, not the whole array, when an extra subtraction would also be needed. In any case, on x86-64 storing both addresses instead of the first address with the length does not have any measurable performance difference in correct implementations, because the number of machine instructions needed for implementing a loop is the same in the most frequent cases. If there are performance differences, it is likely that the machine code generation is bad.
SkiFire13 2y ago
> I find it fascinating that half-open ranges turn out to be - universally as far as I can tell - the right choice for ranges in software. There is a famous letter from Dijkstra on this topic. https://www.cs.utexas.edu/~EWD/transcriptions/EWD08xx/EWD831.html https://www.cs.utexas.edu/~EWD/transcriptions/EWD08xx/EWD831...

tialaramex 2y ago

For the growable array and slice types (C++ std::vector and std::span) at a low level we should actually store ptr and length not start and end, it makes a tiny but measurable performance difference. This is one of the tiny perf leaks from C++ ABI conservation. IIRC All three popular std::vector implementations got this wrong decades ago and are now ABI frozen so too bad. The design of std::span is correct though for whatever that's worth.

adrian_b 2y ago
Storing the length instead of the address past the last element does not change anything in the answer to the question posed by the previous poster. The length of an array is the index of an element beyond the limit of the array, which would be invalid in an indexed expression for accessing an array element. Exactly like when using pointers the address beyond the last element of the array is useful, when using indices the length, i.e. the index beyond the last element of the array, is useful. Moreover, regardless how the arrays are handled in a high-level programming language, on CPU architectures that provide SIB (scaled index + base) addressing modes instead of auto-incremented/auto-decremented addressing modes, e.g. on x86-64, there are frequently encountered cases when the optimal implementation of a loop in machine instructions requires a base register initialized to the address of the element beyond the array limit, together with an index register that contains negative indices, which is incremented at each iteration until it becomes non-negative, in order to access the array in increasing order. (Positive indices that are decremented until becoming negative, together with a base register containing the address of the first array element, are used when the arrays must be accessed in decreasing order.) In optimal implementations on x86-64 and similar ISAs it does not matter much which value between length and address past the array you choose to store in an array descriptor. When the loop is initialized in machine instructions you may need frequently the third value that is not stored, but that is pretty much irrelevant, because an extra addition or subtraction is usually done in zero time on modern CPUs (i.e. concurrently with the other instructions that would have been executed anyway, even when the extra addition/subtraction would not have been necessary). Because arrays are more frequently accessed in increasing order, even when that is not necessary, for the purpose of just accessing the array it would be optimal to store in the array descriptor the length together with the address of the element beyond the array. However this would be worse in conjunction with legacy APIs that would expect the address of the first element, which would require an extra subtraction, and also when accessing just an array element, not the whole array, when an extra subtraction would also be needed. In any case, on x86-64 storing both addresses instead of the first address with the length does not have any measurable performance difference in correct implementations, because the number of machine instructions needed for implementing a loop is the same in the most frequent cases. If there are performance differences, it is likely that the machine code generation is bad.

SkiFire13 2y ago

> I find it fascinating that half-open ranges turn out to be - universally as far as I can tell - the right choice for ranges in software. There is a famous letter from Dijkstra on this topic. https://www.cs.utexas.edu/~EWD/transcriptions/EWD08xx/EWD831.html https://www.cs.utexas.edu/~EWD/transcriptions/EWD08xx/EWD831...