Gennadiy Rozental wrote: > > While I do agree O(1) is better than O(N), I would like to point out that > > it is usable only when the pseudo-variadic template interface is used (i.e., > > variant<T1, T2, ..., TN> as opposed to variant<Types>). > > Why? And to be absolutely clear: what do you mean by "it"?
By "it" I mean the use of a switch, as you propose. If variant is given types as a MPL-sequence (e.g., variant< mpl::list<T1, T2, ..., TN> > instead of variant<T1, T2, ..., TN>), then technique you propose will not work. Please prove me incorrect, but I don't think you can. (Note, however, that loop-unrolling is still possible, though ultimately it doesn't change the O(N) complexity of visitation.) > > Also, I am still not convinced that an unrolled if-else implementation > would > > not be optimized in the same manner as a switch statement. That is, > whether > > I do not know how smart are modern optimizers. But in general my > understnding was that if-else form should use O(N) comparisons, while switch > form should be compiled into jump with some computed offset. I'd be interested to know more about these assumptions before I spend a great deal of time writing code based upon them. Also possible, I'd like to note, is the use of a static array of function pointers. I'll look into this, too, but the space-overhead involved may be significant. > > Further, I would like to point out that we are debating integer O(1) vs. > > O(N) for integer-equality comparisons. While I am a proponent of limiting > > complexity, I would like to observe that you yourself suggested a cap N = > > 128. > > > > In sum, I'm not sure how pertinent this issue is at this point. > > I agree that by itself the difference is not that significant. But note that > visitation is very basic operation in regards to variant type. Almost any > activity that involve variant will include some kind of visitation (look > into your implementation for example). Some people fight to eliminate extra > level of indirection by using references vs. pointers. Or eliminate virtual > function to prevent double resolution. In this case the difference could be > much more significant (up to 128 times). > So unless it's really unreasonably difficult to implement different > visitation scheme, I see enough point to try to do this. I agree that visitation is the fundamental operation for variant. I'll look into it. Thanks, Eric _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
