Paul C. Anagnostopoulos via llvm-dev
2020-Oct-28 18:09 UTC
[llvm-dev] StringSwitch efficiency
StringSwitch just uses a series of Case functions that compare the target against each case string. Once the target is matched, the remaining Case functions bypass the comparison. One way or the other, it goes through all the Case's. I don't think there is any way to optimize this. Does anyone know if the compiler does something clever? At 10/28/2020 12:58 PM, David Blaikie wrote:>On Wed, Oct 28, 2020 at 9:56 AM Paul C. Anagnostopoulos via llvm-dev <<mailto:llvm-dev at lists.llvm.org>llvm-dev at lists.llvm.org> wrote: >At what point should I consider changing from a StringSwitch construct to something more efficient? TableGen has a few of them. In particular, the switch for looking up a bang operator has about 40 cases, all short strings. > >One trivial improvement would be to split it into two StringSwitch's based on the first letter of the operator name. > >If that improves performance, then it sounds like a bug/area for improvement in StringSwitch itself, perhaps?Â
On Wed, Oct 28, 2020 at 11:13 AM Paul C. Anagnostopoulos <paul at windfall.com> wrote:> StringSwitch just uses a series of Case functions that compare the target > against each case string.Fair point - your proposal is to take advantage of sorting, essentially? Knowing which subset start with certain characters or not. Perhaps there could be a version of StringSwitch that only works on sorted input (a named variant, an extra flag, etc) - asserts if the inputs aren't sorted, and then relies on that sorting to be able to take advantage, maybe make a short trie or the like. But yeah, that's probably a bigger design problem you might not be able to/interested in changing right now, coming back to your original question of "when should I use StringSwitch and when should I do something else (hash map, etc)". I don't know what the current tipping point is there.> Once the target is matched, the remaining Case functions bypass the > comparison. One way or the other, it goes through all the Case's. I don't > think there is any way to optimize this. Does anyone know if the compiler > does something clever? > > At 10/28/2020 12:58 PM, David Blaikie wrote: > > >On Wed, Oct 28, 2020 at 9:56 AM Paul C. Anagnostopoulos via llvm-dev > <<mailto:llvm-dev at lists.llvm.org>llvm-dev at lists.llvm.org> wrote: > >At what point should I consider changing from a StringSwitch construct to > something more efficient? TableGen has a few of them. In particular, the > switch for looking up a bang operator has about 40 cases, all short strings. > > > >One trivial improvement would be to split it into two StringSwitch's > based on the first letter of the operator name. > > > >If that improves performance, then it sounds like a bug/area for > improvement in StringSwitch itself, perhaps? > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20201028/4c585098/attachment.html>
> On Oct 28, 2020, at 14:09, Paul C. Anagnostopoulos via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > StringSwitch just uses a series of Case functions that compare the target against each case string. Once the target is matched, the remaining Case functions bypass the comparison. One way or the other, it goes through all the Case's. I don't think there is any way to optimize this. Does anyone know if the compiler does something clever?Hi Paul, This has come up on the list before [1]. The suggestion at the end of that thread was to look at the optimized code produced by the compiler [2]. Cheers, Steve 1. http://lists.llvm.org/pipermail/llvm-dev/2016-February/095075.html 2. http://lists.llvm.org/pipermail/llvm-dev/2016-February/095265.html -- Stephen Checkoway
Yeah, years ago, the compiler did the right thing through a combination of jump threading and simple redundancy elimination. StringSwitch does a first character specialization IIRC. -Chris> On Oct 28, 2020, at 9:01 PM, Stephen Checkoway via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > > >> On Oct 28, 2020, at 14:09, Paul C. Anagnostopoulos via llvm-dev <llvm-dev at lists.llvm.org> wrote: >> >> StringSwitch just uses a series of Case functions that compare the target against each case string. Once the target is matched, the remaining Case functions bypass the comparison. One way or the other, it goes through all the Case's. I don't think there is any way to optimize this. Does anyone know if the compiler does something clever? > > Hi Paul, > > This has come up on the list before [1]. The suggestion at the end of that thread was to look at the optimized code produced by the compiler [2]. > > Cheers, > > Steve > > 1. http://lists.llvm.org/pipermail/llvm-dev/2016-February/095075.html > 2. http://lists.llvm.org/pipermail/llvm-dev/2016-February/095265.html > > -- > Stephen Checkoway > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev