HN user
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.
The reason I mentioned using a hierarchical bitmap was precisely the inefficiency of just having one bool per element.
Wow, thank you. Were you already aware of the name? Or if not, how did you search for it?
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.
That's supported here! You can do:
for (auto const &member : enum_traits<E>::members())
{ std::cout << member.name() << std::endl; }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.
[1] https://github.com/therocode/meta_enum/blob/master/include/m...
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.
[1] https://github.com/Neargye/magic_enum/blob/master/doc/limita...
Should applicants mention if they saw this posting on HN? I just realized I neglected to do this when applying.
1. the lt2 definition in the paper is wrong.
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.
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!
There are lots of reasons to prefer trees (and, correspondingly, lots of reasons to prefer hashtables); I just pointed out ordering isn't the only one, and I merely gave another (worst-case performance guarantee). For example, yet another one is iterator stability; insertion can invalidate iterators for unordered containers, making them useless for some applications that need to analyze data efficiently as they insert.
I could go on, but it's very much detracting from the point of the paper to argue about the data structure choice when the paper isn't on this topic at all or trying to analyze any particular application to begin with.
Yeah—I think I laid out the paper more like a story, but I might indeed need to change that as it appears it leaves people confused before they get to the punchline. Thanks for the feedback! Glad you found it interesting.
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!
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. :)
You're right!! Thanks for pointing this out! I indeed tried to hint at the DAG case in the footnote, but didn't try to explore what happens when the DAG degenerates to a linked list. The biggest obstacle here is, honestly, motivating that an exponential slowdown is a real-world issue that concerns the average programmer, because I know for sure that many would immediately blame the data structure and tell you it's your fault for designing it that way. :-) Whereas if I can illustrate a problem that's fundamentally ingrained into language's built-in data structures by design, and that people would actually encounter in the real world, that's far more compelling.
I know this because I already received such criticism for my examples, with people telling me that it's unclear how wide-reaching the ramifications are in real-world applications (which I suppose is fair enough). People really want to see examples of real-world software being improved with such small tweaks in the algorithms, whereas I didn't have the bandwidth to try to investigate that, and just tried to settle for plausible examples. That criticism would be magnified many times further for DAGs and (especially) degenerate linked lists. (I'm not claiming these are the only relevant scenarios by the way—just saying this is how it is likely to be seen by many readers.) I moved on and didn't spend more time on this (it was kind of a random paper idea I had and not related to anything else), but I think it would be awesome to flesh this out further into something more interesting and compelling and properly publish it.
If you find this interesting and have the time to help joint-author & actually publish a paper on this, please grab my email from arXiv and email me! It would be great to flesh out more consequences and find more interesting examples together. I feel like there's a lot more underneath the surface that I might not have touched (both theoretically and practically), but I hadn't managed to gather enough interest from others in the topic (let alone the examples) to motivate me to look further until now!
Sure, but this isn't a benchmarking paper.
Even more trivial: sum from 1 to n, then never use the result. It should get optimized out entirely!
Ordering is not the only concern here. std::set actually provides a logarithmic worst-case guarantee, whereas std::unordered_set does not. This is a factor to consider depending on the application, regardless of whether ordering is necessary. Whichever one prefers in any case, though, is beside my point—I'm merely trying to use trees and hashtables to illustrate a far more general CS phenomenon that can occur in lots of data structures and languages.
I'm not trying to write the most horrible comparison at all. Perhaps the most important thing to keep in mind here is that this is a general computer science paper, and my comparison of C++ and Python is just intended to serve as a familiar (and vivid) illustrative example of the general phenomenon I'm trying to describe. The paper is emphatically not intended to be a "Python vs. C++" paper. Everything you see there that is "concrete" (the language, the running times, etc.) is intended to be a mere illustration of the overarching concept (design decisions & their consequences) being discussed, and it could manifest itself in any language.
The context to keep in mind when reading the paper is: When designing a programming language & its standard library (or any API), we need to define an interface we can use as a building block, and we're analyzing the consequences of our choice of building blocks. In particular, we first examine the case of comparison-based data structures, which requires defining ordering primitives. In C++, the primitive is the < operator. In Python 2, it's cmp(). (In Python 3, it's a mix of < and ==, whose implications I discuss as well.) We assume user-provided types implement that basic interface, and we implement everything else we need on top of that.
So the question I'm analyzing in that example is: What happens if my primitive comparison operation is a 2-way comparison (lt(), like in C++) and then I implement 3-way comparison in terms of that (such as when I need it for for a binary search tree)? Now, what if we do the opposite: what happens if instead my primitive comparison operation is a 3-way comparison (cmp(), like in Python 2) and I only need to perform a 2-way comparison later? What are the trade-offs?
To do this, I take both approaches, implementing each in terms of the other, and compare how they behave complexity-wise. The conclusion I come to is that the choice of the primitive (which is often made by the language designers) isn't merely a question of aesthetics, but rather, it actually affects the time complexity of common operations (like traversing search trees). Similarly, the decision to cache a hash code doesn't just result in a constant-factor improvement, but it can actually change the time complexity of a program. And so on.
I think if you re-read the paper with these in mind, it should hopefully make more sense. The rest of what you said doesn't enter the picture at all... these are already balanced binary trees, the decision to use less<> is fundamentally independent of what C++ stdlib implementation you use, and the time of the vector concatenation isn't even being measured. Those things are unrelated to the point of the paper entirely. I was just trying to minimize the extraneous lines of code so we can focus on the heart of the problem instead of getting distracted by boilerplate.
At least GCC was (and by now Clang and probably others are) known for occasionally optimizing out certain uses of functions like strlen(), which can change the time complexity in some trivial cases.
For instance, if you consider strcmp(x, y, strlen(y)) where x is of fixed length, then the whole function would be constant-time if strlen(y) is optimized out, whereas it would take linear time (linear in strlen(y)) otherwise. GCC et al. can optimize out strlen() in some such cases.
In practice you wouldn't want to rely on this, both because compilers aren't anywhere near smart enough to figure out complicated cases and also because these wouldn't happen in debug mode either, but it's not impossible for time complexity to change through optimization.
Oh yeah I think you did find a bug, thanks for pointing it out! I need to check the lengths as well. It shouldn't affect the conclusion (in fact I think I made all comparisons equal-length in the paper?) but I should revise it when I get the chance.
If you're wondering whether this is a theoretical or practical problem: I actually observed some of this effect in practice first, and only after thinking about it for a while did the larger issue (and the complexity implications) dawn on me.
I had something like a set<string> or a set<set<string>> (or map... I can't remember which) somewhere in my program a few years ago, and I was trying to improve the program's performance. I tried breaking into it several times and found it quite perplexing that the bottleneck appeared to be the set<> container. I mean, I get that cache locality and all has an effect, but it seemed to be having a little too much of an effect. Why did I find this odd? Because other languages (like C#) have tree-based sets and maps too, but I'd never felt they were quite as slow as I was seeing them in C++. So I felt something weird must be going on.
I tried to step through the program for a while and observe what's going on, and at some point, I realized (perhaps I hit the same breakpoint twice? I don't recall) that these functions were being called more often than I intuitively thought would be necessary. Which was obvious in hindsight, as less() needs to be called multiple times on the same objects (4 times at level 2). Now, this hadn't resulted in quadratic behavior, but that was only because my data structures weren't arbitrarily deep—the slowdown was nevertheless a significant constant factor at the core of my program, only linear because the data structure's depth was bounded.
So once I had realized the implications of this, including that constant-factor differences can actually turn into polynomial ones, I eventually decided to post an article about it on arXiv... hence this article. Aside from the complexity issue illustrated in the article, one of my (unexpected) higher-level takeaways was that you can't just take any utility function in a program and blindly put it into a library: even if it's correct, you probably have hidden assumptions about its use cases that won't hold true in general. You really need to think about how it could be used in ways you didn't initially expect, and this may well require a different kind of code review with an entirely different mindset than before. It really drove home the point for me that writing a library is quite a bit different (and in some ways more difficult) than writing an application.
It's possible there is more theory lying underneath this that I haven't touched on—it would be interesting if someone can take this and find more interesting consequences of it. For example, maybe when analyzing algorithms we need to consider something akin to a "recursive time complexity", too? Is there another useful notion of complexity that we can generalize here?
Anyway, hope people enjoy reading it and take something useful away from it. :)
Given everyone's interest in the topic, can I also share something I wrote under "accidentally quadratic"? I think people might enjoy reading it: https://news.ycombinator.com/item?id=26337913
It turns out that multi-pass algorithms in general can be quite susceptible to this issue, and it can be far from obvious in general.
It might be common practice but it shouldn't be. There are lots of reasons this is a bad idea; here's just a sampling:
1. "My return type is whatever I happen to return" circumvents the ability of the type checker to ensure correctness.
2. More generally, the purpose of a specification (a function declaration in this case) is to declare what is required of a compliant implementation, and to provide a way to check the validity of that implementation. But when you make the types all become auto-deduced, you're basically reducing the specification to a ~ shoulder shrug "it does whatever it does" ~.
3. Moreover, as I alluded to in the comment, it quickly becomes near-impossible to meaningfully separate the definition from the declaration, whether that's because you want to hide it or because you want to compile it separately. Simply put, you lose modularity. It seems like a minor thing when (as in the example) the return value doesn't depend on types inferred from other callees' return values, but as soon as that ceases to be true, you suddenly tie together the implementations of multiple functions. At that point, your functions lose much of their power to abstract away anything, since as soon as you change the return expression for one function, it has the potential to break code (up to and including causing compilation errors) in the the entire chain of callers. (!)
4. Templates end up getting re-instantiated far more often than they need to be (which can slow down both the compilation and the runtime efficiency). You almost certainly don't want '0' and '(size_t)0' to result in duplicate instantiations when dealing with sizes, for instance.
5. Issue #4 can also result warnings/errors/bugs, since now you have a function that returns a different concrete type than you likely intended, which can result in everything from spurious warnings (signed/unsigned casts, for instance) to actual bugs (later truncation of other variables whose types were inferred incorrectly as a result).
6. The code becomes difficult for a human to read too. You now no longer have any idea what types some variables are supposed to be. Not only does this hamper your ability to cross-check the correctness of the implementation itself (just as with the declarations, in #1) but unless your function is trivial, this quickly makes it harder to even understand what the code is doing in the first place, never mind what it's supposed to do.
7. Proxy types become impossible to implement, since they won't undergo the intended conversions anymore.
All this just to reduce keystrokes might be a common trade-off, but a poor one. I can come up with more reasons, but hopefully this gets the point across.
Probably not a good idea since the caller won't know what the return type is at that point, and the return type would become dependent on the implementation, which breaks function abstraction.
And imagine what would happen when you get a few more 'auto' variables in the return expression. Suddenly your return type will depend on the implementation of your callees. And the code can then quickly become impossible to understand.
auto is overused.
It's not just the latest version though? C++11 could already do what you wanted.
No, I'm saying even in that case you know it was intended to be a copy. If you wanted that to be a reference then you'd either (a) just do the obvious thing which is to just use the original variable name instead of creating a new variable out of the blue for no reason, (b) leave a comment explaining why you're not doing the aforementioned obvious thing, or (c) use a self-explanatory variable name to provide the explanation instead of a comment.
+1 for auto being overused. I always felt I was shouting into the void (hah) by saying the same thing... it's nice to see someone else agrees.