Date: Mon, 26 May 2025 22:21:02 +0000
On Sunday, May 25th, 2025 at 1:48 AM, Sebastian Wittmeier via Std-Proposals <std-proposals_at_[hidden]> wrote:
> So you see it as a way to make optimizations by compiler implementers more likely?
Yes, plus one step further [see below]
> Wouldn't it be primarily the opposite:
>
> switch (string) would be translated into the same code as current if (string ...)?
No, because we can require `switch (string)` to
perform O(log(N)) comparisons, where N is the
number of cases. This is why I mentioned that
the C++20 structural type is worth noticing. It
showed a way to defining value equivalence without
involving user-defined `operator==`.
> And why should pattern matching without fall-through not give the same incentive to optimize string comparisons?
There are lots of things to consider:
- what are the types we can ignore pattern
matching protocols and use builtins?
- is this possible to apply to QString?
- what was user's motivation of testing
strings with `match` expression? Isn't
just because it looks nicer than `if...else`?
- is this optimization portable between
compilers? If not, users may end up with
finding portable solutions anyway.
- there're so many things in pattern
matching that need to be optimized,
is this the most important thing to do?
> So you see it as a way to make optimizations by compiler implementers more likely?
Yes, plus one step further [see below]
> Wouldn't it be primarily the opposite:
>
> switch (string) would be translated into the same code as current if (string ...)?
No, because we can require `switch (string)` to
perform O(log(N)) comparisons, where N is the
number of cases. This is why I mentioned that
the C++20 structural type is worth noticing. It
showed a way to defining value equivalence without
involving user-defined `operator==`.
> And why should pattern matching without fall-through not give the same incentive to optimize string comparisons?
There are lots of things to consider:
- what are the types we can ignore pattern
matching protocols and use builtins?
- is this possible to apply to QString?
- what was user's motivation of testing
strings with `match` expression? Isn't
just because it looks nicer than `if...else`?
- is this optimization portable between
compilers? If not, users may end up with
finding portable solutions anyway.
- there're so many things in pattern
matching that need to be optimized,
is this the most important thing to do?
-- Zhihao Yuan, ID lichray The best way to predict the future is to invent it. _______________________________________________ > > -----Ursprüngliche Nachricht----- > > Von: Zhihao Yuan <zy_at_[hidden]> > > Gesendet: So 25.05.2025 05:35 > > Betreff: Re: [std-proposals] A draft for modern switch > > Anlage: signature.asc > > An: std-proposals_at_[hidden]; > > CC: Sebastian Wittmeier <wittmeier_at_[hidden]>; > > body { font-family: monospace; } > > > > On Saturday, May 24th, 2025 at 12:10 AM, Sebastian Wittmeier via Std-Proposals <std-proposals_at_[hidden]> wrote: > > > > > The question is, do we need switch in the programming language to express this functionality? The compiler can do those optimizations from an if else tree as well. Or from pattern matching. > > > > > > Is it easier for the compiler to detect the possibility of multi-way branching from switch? > > > > Multi-way branch extended to strings etc. does > > not enable a particular optimization that couldn't > > be done for an if...else tree or pattern matching, > > but a world with such a feature and a world > > without can still leave us different outcome of > > if...else tree and pattern matching. There're > > two things to consider: > > > > 1. Without multi-way branch extended to > > strings, will compilers optimize if...else tree > > that compares std::string etc. and pattern > > matching that matches among them? > > 2. Since if...else and pattern matching do not > > support fall through, if a user replicates > > code in order to simulate fall through, > > will compiler detects and merges the > > control flows? > > > > Correct me if I'm wrong, in the past 30 years, > > no compiler optimizes an if...else tree that > > compares std::string to run a sub-linear > > algorithm under as-if rule. But in the same > > time frame, the compilers start to rewriting > > integer-based if...else chains into switch > > statements as an optimization. > > > > My interpretation is this: people who look for > > sub-linear algorithm comparing string will > > look for other solutions, and people who > > do write an if...else tree to compare std::string > > are satisfied with what they got. Since all > > users are satisfied, no further optimization > > needed. That's one implication of as-if rule: > > because it is based on code patterns, the > > code pattern must be prevailing, otherwise > > the users have no right to complain. > > > > Then why compilers are happy to optimize > > integer-based if...else chains into switch > > statements? First, that's what ordinary users > > do in real world, second, the implementation > > cost of the optimization (a rewrite) is low. > > That's the another implication of as-if rule: > > the benefit must out weight the cost. > > > > Then we can reach this intermediate > > conclusion: unless the compilers implement > > a highly dedicated optimization for a > > disjointed, string-only pattern matching > > (under as-if rule, because pattern matching > > is specified in terms of ==), if...else chain > > that compares strings will continue not > > receiving an algorithmic optimization. > > > > Then the question becomes, will compilers > > implement that optimization for pattern > > matching? I don't know, because this > > by itself is again under as-if rule, so cost- > > benefit weights in. What we know are the > > following: First, LLVM has a dedicated IR > > for `switch` statements, but you should not > > expect an IR for pattern matching. Second, > > this type of optimization is rather fragile, > > any newly inserted, out-of-pattern code > > is enough to prohibit it. > > > > Finally, given the implications of as-if rule, > > you should be able to predict that any > > optimization targeting if...else comparing > > strings to simulate fall through with goto > > or pattern matching among strings > > that replicates branches to simulate fall > > through won't happen. > > > > -- > > Zhihao Yuan, ID lichray > > The best way to predict the future is to invent it. > > _______________________________________________ > > > > > Is the syntax nicer for the user? The features like fall-through and wild jumps were left out on purpose with pattern-matching. > > > > > > I would guess, the compilers can or could do the same performance improvements with if/else and pattern matching. > > > > > > If you need fall-through and other shenanigans use if/else), loops or even goto. > > > > > > Otherwise use pattern matching. > > > > > > If your compiler does not optimize as well as it could, manually optimize the conditions in your code and send a feature request or patch to the implementers. > > > > > > > -----Ursprüngliche Nachricht----- > > > > Von: Zhihao Yuan via Std-Proposals <std-proposals_at_[hidden]> > > > > Gesendet: Sa 24.05.2025 08:14 > > > > Betreff: Re: [std-proposals] A draft for modern switch > > > > Anlage: signature.asc > > > > An: std-proposals_at_[hidden]; > > > > CC: Zhihao Yuan <zy_at_[hidden]>; > > > > On Friday, May 23rd, 2025 at 7:27 PM, Jason McKesson via Std-Proposals <std-proposals_at_[hidden]> wrote: > > > > > > > > > > > > > > I guess that depends on what you mean by "jump table". I've always > > > > > understood that term to refer to an array of pointers to various > > > > > locations in code, with the indices in that table representing > > > > > something in particular. > > > > > > > > > > > > > > [...] > > > > > > > > > > > > > > The code being jumped into is not the table. It's just code. > > > > > > > > > > > > > > > > > I apologize. "Multiway branch" seems to be the > > > > right term https://www.researchgate.net/publication/245584786_A_Superoptimizer_Analysis_of_Multiway_Branch_Code_Generation > > > > > > > > -- > > > > Zhihao Yuan, ID lichray > > > > The best way to predict the future is to invent it. > > > > _______________________________________________ > > > > -- > > > > Std-Proposals mailing list > > > > Std-Proposals_at_[hidden] > > > > https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
Received on 2025-05-26 22:21:14