Date: Tue, 16 Sep 2025 03:53:25 +0000
> On Sep 15, 2025, at 08:54, Thiago Macieira via Std-Discussion <std-discussion_at_[hidden]> wrote:
>
> On Monday, 15 September 2025 06:59:34 Pacific Daylight Time Nate Eldredge via
> Std-Discussion wrote:
>> Cost. std::less may be more expensive than < , and the programmer should
>> not have to pay that cost for the common case of comparing pointers within
>> the same array.
>
> There may be a higher cost to compile, but runtime the cost should be exactly
> the same.
No, there's a definite runtime cost in the case I have in mind.
>> The classic example was x86-16 with the "compact" or "large" code models, in
>> which a data pointer is a "far" pointer consisting roughly of struct {
>> unsigned offset; unsigned segment; };. (Here `unsigned` is 16 bits.) A
>> 20-bit linear address is formed by (unsigned long)segment << 4 + offset.
>>
>> In these code models, every individual array exists within a single segment
>> (and so is limited to 65535 bytes) but distinct arrays may be in different
>> segments. So p1 < p2 can simply compare the offset parts, because the
>> segments must agree if they point within the same array, which costs one
>> cheap 16-bit compare instruction (cmp si, di). But std::less<T *>{}(p1,
>> p2) must compute and compare the linear addresses, requiring several shifts
>> and 32-bit adds, and being about an order of magnitude slower and larger.
>
> Indeed, but in the medium and large memory models (__far function pointers),
> you'd need to do the above anyway to compare function pointers, because you
> couldn't be sure whether they were in the same segment or not. For example,
> how do you order 0010:0108 vs 0200:0010 ?
Sure, but since you can't have an array of functions, comparing function pointers falls outside the common case of "comparing pointers within the same array" that the < operator is meant for. Here, I agree, you have to pay the runtime cost of std::less regardless, and all that your proposal changes is the syntax.
> Besides, std::less<T __far *> can be different from std::less<T __near *>.
Yes, of course they would be different. But that's beside my point.
What I have in mind is this. Consider the large or compact code models, where all data pointers are far, and think about how we compile
int sum_array(const int *arr, const int *endp) {
int sum = 0;
for (const int *p = arr; p < endp; p++) {
sum += *arr;
}
return sum;
}
This function is only intended to be called with both arguments being pointers into the same array, and would be documented as such (no other usage would make sense anyway).
In this code model, any two pointers within the same array (or class object) must have the same segment part, and the < operator is only specified for comparisons of such pointers; so the compiler may *assume* the segments are equal, and compare the offsets only. (Likewise in this code model, `p++` increments the offset only, and doesn't touch the segment.) So as it stands, the test `p < endp` consists of one cheap `cmp` instruction.
But under your proposal, the compiler would be required to emit code for `p < endp` that would have well-specified behavior even if `p` and `endp` do not point into the same array. That means it does have to compare the segment as well as the offset parts, which at least doubles the runtime cost - and much more if we have to handle overlapping segments by computing linear addresses (I'm not sure if x86-16 ABIs allowed that).
In this example, a smart compiler (which typical x86-16 compilers were not) could hoist the segment part of the comparison out of the loop, but we could certainly construct an example where this would not be possible. (And I realize this example has UB if `endp` has a higher address than all of `arr`; but greater than all its elements; we could assume the calling code avoids that case, or modify this function to handle it.)
All that said, you certainly could make an argument that the benefits of the proposal outweigh the costs, but IMHO you'd need data to quantify them. The costs do exist.
>
> On Monday, 15 September 2025 06:59:34 Pacific Daylight Time Nate Eldredge via
> Std-Discussion wrote:
>> Cost. std::less may be more expensive than < , and the programmer should
>> not have to pay that cost for the common case of comparing pointers within
>> the same array.
>
> There may be a higher cost to compile, but runtime the cost should be exactly
> the same.
No, there's a definite runtime cost in the case I have in mind.
>> The classic example was x86-16 with the "compact" or "large" code models, in
>> which a data pointer is a "far" pointer consisting roughly of struct {
>> unsigned offset; unsigned segment; };. (Here `unsigned` is 16 bits.) A
>> 20-bit linear address is formed by (unsigned long)segment << 4 + offset.
>>
>> In these code models, every individual array exists within a single segment
>> (and so is limited to 65535 bytes) but distinct arrays may be in different
>> segments. So p1 < p2 can simply compare the offset parts, because the
>> segments must agree if they point within the same array, which costs one
>> cheap 16-bit compare instruction (cmp si, di). But std::less<T *>{}(p1,
>> p2) must compute and compare the linear addresses, requiring several shifts
>> and 32-bit adds, and being about an order of magnitude slower and larger.
>
> Indeed, but in the medium and large memory models (__far function pointers),
> you'd need to do the above anyway to compare function pointers, because you
> couldn't be sure whether they were in the same segment or not. For example,
> how do you order 0010:0108 vs 0200:0010 ?
Sure, but since you can't have an array of functions, comparing function pointers falls outside the common case of "comparing pointers within the same array" that the < operator is meant for. Here, I agree, you have to pay the runtime cost of std::less regardless, and all that your proposal changes is the syntax.
> Besides, std::less<T __far *> can be different from std::less<T __near *>.
Yes, of course they would be different. But that's beside my point.
What I have in mind is this. Consider the large or compact code models, where all data pointers are far, and think about how we compile
int sum_array(const int *arr, const int *endp) {
int sum = 0;
for (const int *p = arr; p < endp; p++) {
sum += *arr;
}
return sum;
}
This function is only intended to be called with both arguments being pointers into the same array, and would be documented as such (no other usage would make sense anyway).
In this code model, any two pointers within the same array (or class object) must have the same segment part, and the < operator is only specified for comparisons of such pointers; so the compiler may *assume* the segments are equal, and compare the offsets only. (Likewise in this code model, `p++` increments the offset only, and doesn't touch the segment.) So as it stands, the test `p < endp` consists of one cheap `cmp` instruction.
But under your proposal, the compiler would be required to emit code for `p < endp` that would have well-specified behavior even if `p` and `endp` do not point into the same array. That means it does have to compare the segment as well as the offset parts, which at least doubles the runtime cost - and much more if we have to handle overlapping segments by computing linear addresses (I'm not sure if x86-16 ABIs allowed that).
In this example, a smart compiler (which typical x86-16 compilers were not) could hoist the segment part of the comparison out of the loop, but we could certainly construct an example where this would not be possible. (And I realize this example has UB if `endp` has a higher address than all of `arr`; but greater than all its elements; we could assume the calling code avoids that case, or modify this function to handle it.)
All that said, you certainly could make an argument that the benefits of the proposal outweigh the costs, but IMHO you'd need data to quantify them. The costs do exist.
Received on 2025-09-16 03:53:27