On Tue, May 27, 2025 at 9:23 AM Thiago Macieira via Std-Proposals <
std-proposals_at_[hidden]> wrote:

> On Monday, 26 May 2025 12:14:14 Brasilia Standard Time Arthur O'Dwyer via
> Std-
> Proposals wrote:
> > So (this is a probably-rhetorical question directed at @ZhaoYunshan) what
> > API would you have to require of the author of WrappedInt in order to
> make
> > their type "switch-able"?
>
> I'm going to guess that [...]


Unfortunately, this means you've done the low-hanging fruit that Zhao
Yunshan might have been able to puzzle through on his own, without solving
the high-hanging fruit. This is like the worst of both worlds. :P

To me, a `switch` implies a jump table. Of course the *optimizer* can
*rewrite* that jump table's codegen if it thinks it will be more optimum to
do so; but fundamentally a switch is an O(1) jump table, says I. A solution
to "user-defined `switch`" that requires O(lg N) potentially-expensive
lexicographical comparisons (instead of an O(1) dispatch) isn't really
`switch` — it's some other primitive, for which modern programming
languages lack a name.

As you say, the ordering of the case-labels must not matter.
As you say later-in-thread, it seems to be important that the compiler
reject *duplicate* case-labels at compile time.

A `switch` over integers has at least three possible implementations:
- O(1) jump table with integer values
- O(lg N) binary search with operator<=>
- O(N) if-else-if chain with operator==
We *might* imagine a user-defined `switch` that can "fall back" from one of
those to another, depending on the operations T provides. Personally I'd be
very wary of that; I'd consider it a potential pitfall and debacle similar
to the std::ranges algorithms which can "fall back" from more-efficient
random-access algorithms to less-efficient bidirectional algorithms simply
because your iterator type is missing an `operator[]` or whatever. The
mitigating factor with Ranges is that it's easy to static_assert
`std::random_access_iterator<MyIter>` or whatever. *If* a user-defined
`switch` facility permitted silent fallback (which I'm not convinced is a
good idea), it would need to provide some way for the user to easily
static_assert that their T would in fact generate a jump table, or a binary
search, or whatever their intent was.
We "trust" the optimizer when it's dealing with simple integers, firstly
because we know the compiler has good insight into the tradeoffs involved
(none of the comparison/hash/index operations will run arbitrary
user-defined code). Secondly because we have no choice. Thirdly because we
have a little semblance of control with things like [[likely]]/[[unlikely]]
(not that we should use them
<https://blog.aaronballman.com/2020/08/dont-use-the-likely-or-unlikely-attributes/>
).
I do not think I would trust the optimizer when it's dealing with
user-defined T. An actual proposal would have to juggle these motivations:
- How can we give the compiler more insight into the costs and tradeoffs of
the user-defined operations involved? How can we extract the biggest
performance benefit while giving up the least insight?
- Should the user have more choice? Should there be two or three "kinds" of
user-defined switch, in some sense (e.g. via an attribute on the switch)?
(IMHO no; but it's part of the *possible* design space.)
- How does the new thing interact with [[likely]]/[[unlikely]] and other
"semblance of control" mechanisms in existing C++? (This cannot be hashed
out in a mailing-list thread; it requires the person to actually think
about it, and implement it, and evaluate it.)

[...] For a large string table, what
> I'd manually do is switch on the first letter, which *can* often be placed
> in a
> jump table, and then perform comparisons from the second letter onwards.
> [...]
> But I have no clue how to teach the compiler on how to do the first-letter-
> switching automatically.
>

Yep, that's the high-hanging fruit that must form the core of an actual
proposal.

–Arthur