Do you think you could try my library [1] and let me know how it performs in comparison? I've been curious about its compile-time performance, but I've never tried to compare its performance against that of magic_enum.
Wow! I independently came up with this algorithm a few years ago and wasn't even sure what to search for to find the prior art. Happy to see someone finally gave it a name and attempted to find the history.
Fun fact #1 that I also realized, which I have yet to see mentioned elsewhere (though people have almost surely realized this in various contexts):
This is not limited to binary search or mergesort.
This is a very general-purpose meta-algorithm for turning any batch algorithm into a streaming one. (!)
The merge() step is basically "redo computation on a batch 2x the size". You pay a log(n) cost for this ability. You can combine the batches in any way you want there. Here it happens to be a merge of two sorted arrays. But you can imagine this being anything, like "train your ML model again on the larger batch".
Fun fact #2: I believe you can add deletion support as well. This can be done with a hierarchical bitmap to help you quickly search for occupied slots. It comes at the cost of another log(n) factor in some operations. I have yet to search if there is a name for the hierarchical bitmap structure I have in mind, so I'm just calling it that for now.
For deletion, I think you can augment the current data structure so that instead of just storing each value, you pair it up with a Boolean telling whether the value is actually still included or not.
But you lose out on insertion and search efficiency; the worst case is dependent on the maximum number of values ever inserted, not the number of currently valid values.
It's indeed a lot of boilerplate that this library can hopefully reduce (which was one of my main goals). I don't know for sure, but I can guess some reasons why the standard doesn't support it:
- The problem is somewhat underspecified. There are lots of degrees of freedom—what delimiters you support, what character encodings you support, what inputs to accept (numeric vs. names), how exactly to deal with flags, etc. These make a generic solution more involved. It's in some sense a more complex version of the problem of number parsing, which has had quite a long journey and is still not entirely ergonomic in C++. (Even std::from_chars only came out in C++17, for example.)
- Lack of more general reflection capabilities, especially ones that provide string metadata, especially at compile-time. Given reflection isn't coming in C++23, it might be a while before we get support on this front.
Ah sorry about that, thanks for the feedback! I can try to answer these here (and hopefully update the documentation as well when I get the chance):
- The problem is basically twofold. Part (a) is that there are no facilities for dealing with enums in C++. "Dealing with" could be anything, such as: bitwise-combining enums as flags, converting enums to/from strings, verifying that a given value is valid for an enum, decomposing flags into their constituent values, and anything else people might typically want to do with enums. Part (b) is that people end up manually writing enum-specific functions for these over and over again, and that often results in brittle and non-reusable code that quickly gets out of sync with the actual enum as it evolves over time (e.g., handwritten parsing code might stop working when a new member is added). This library aims to address most if not all of these problems.
- There are 3 main "tricks" I've used (and a ton of boilerplate on top of that): (a) I use the auto-return-type-with-hidden-friends trick to "tag" the enum with metadata for later retrieval, (b) I overload the comma operator to be able to utilize the same text for both the enum definition as well as for storing relevant metadata, and (c) I use constexpr string parsing to extract the enum names from the definition passed to the macro. Part (a) is confusing and better explained in the link I put in the credits. Part (b) is somewhat tricky but hopefully not too bad. Part (c) seems obvious in hindsight now that I mention it, but I haven't seen it used elsewhere in this manner. (Edit: While digging further just now, I found someone has indeed tried a similar approach with constexpr string parsing in [1], though it appears less comprehensive.)
- No other libraries that I'm aware of support all the features of this one. Typical restrictions include: limiting the ranges of the underlying values, limiting the number of enumerators to some amount, not supporting enum members with duplicate values, not supporting 'enum class', etc.
Hope this helps! If I can clarify anything else please let me know.
To my knowledge magic_enum has some severe limitations; for example, it limits the range of enum values, it cannot handle duplicate enum values, it uses compiler-specific hackes, etc. There is a list of them outlined at [1]. Before writing this library I did take a look around for existing ones (there's also wise_enum [2] for example), but I couldn't find any that supports all of the functionality implemented here.
Update: And I'm glad to see interest! I just updated the repo to add a parse_enum function for converting strings to enums as well.
> I wonder (genuinely asking, not being snarky) what it is about C/C++ that seems to make these issues more common? It's also possible my perception of "more common" has just been inflated by seeing multiple examples in a single week
It's an interesting question. There isn't a whole lot in common between the std::set and scanf issues except that they're both multi-pass algorithms (which I posted a comment about there), so I guess as far as the language is concerned, the question might reduce to "(Why) are multi-pass algorithms more common in C++?" I suppose one possible response, to the extent that this might be the case, might be that in C and C++ operations are so cheap (due to inlining and fewer indirections and such) that people don't blink twice before performing them multiple times, without thinking about the implications. Whereas in Python, everything is already so slow that you would try to factor out common operations if you were optimizing code. However, I'm not sure this is a broad pattern in general; e.g., the hashing example is just as bad in Python.
I think the bigger explanation might be more mundane as far as the language is concerned. Some of it is likely just accidental (there's no particular reason Python couldn't have made the same decision as C++ to implement == in terms of <, for example), and some of it is just a consequence of C and C++ programmers being more likely to look into performance issues, since that's probably why they chose said languages to begin with. Even the C++ example only dawned on me after years of experience optimizing things for performance, so given that Python is already incredibly slow to begin with, if I did see this in Python, chances are pretty good I would just assume it's just the interpreted nature of Python (or a poor set implementation) that's slow and not look into it further.
C++20 doesn't quite rectify this unfortunately! The data structures still use std::less even in C++20, meaning the 2-way comparisons would happen twice. Except now each 2-way comparison is potentially implemented on top of 3-way comparisons. Perhaps I or someone else should get in touch with the committee to try to change that, otherwise things are going to be slower rather than faster if we still use 2-way comparisons but now they have to do 3-way comparisons underneath!
I think the sibling comment may have already answered your question, but if not, I think an earlier response I had might help clarify what exactly I'm comparing & why: https://news.ycombinator.com/item?id=26340952
Note that you do need to read the entire paper to see the overall picture and its consequences; if you stop halfway then it might appear like I'm comparing things unfairly. Feel free to let me know if anything is still confusing after reading the other comments and taking another look at the paper and I'll try to clarify!
let me rephrase, as I indeed have read the paper, before posting.
1. the lt2 definition in the paper is wrong.
A lexicographical compare is linear in the size. the derived cmp2 is correct and has a run time twice that of cmp3. which matches the stl definitions of lexicographical_compare, see below.
2. the c++ behaviour in 2.4.2 is puzzling and most likely bug, worth reporting to and discussing with STL implementors.
Would you mind providing a counterexample to illustrate what incorrect output it's producing?
> A lexicographical compare is linear in the size.
Indeed, lt2() also has a loop that iterates a linear number of times as you mention. It is consistent with this.
> the derived cmp2 is correct and has a run time twice that of cmp3. which matches the stl definitions of lexicographical_compare, see below.
Perhaps you might be confused about what lexicographical_compare does? It does not "compare" in the 3-way sense. It only performs a "less-than" comparison. The name is rather misleading.
2. the c++ behaviour in 2.4.2 is puzzling and most likely bug, worth reporting to and discussing with STL implementors.
I'm not sure what to report to anyone, as I don't find it puzzling; it is entirely consistent with everything I'm aware of and have tried to explain in the paper. It is also not specific to any particular implementation; I believe you will see this behavior on any correct implementation you try it on. It might be helpful if you try to produce a counterexample using what you believe would be a correct & efficient implementation to validate or invalidate this.
Haha, thank you! It was pretty demotivating to see so many people immediately dismiss it as clickbait without any attempt to discuss the topic at all, so it actually means a lot to hear that you think differently now. I hope it was fun & worth the read. I know I had a lot of fun writing it. :)
[1] https://news.ycombinator.com/item?id=32236447