*<it seems I accidentally hit send, sorry about that>* 2015-07-24 0:42 GMT-03:00 Bruno Dutra <brunocodutra@gmail.com>:
Peter,
I can confirm peeking at the code that at least clang ships a naive linear recursion implementation of make_index_sequence and I read somewhere that GCC doesn't do any better, however it's well known <http://stackoverflow.com/a/17426611/801438> it may be implemented in O(log(n)) plus taking full advantage of memoization. Since Part 2 of your article is all about benchmarking, have you actually tried it? I see your "duplicate immune" version of mp_contains_impl and also mp_map_find and hence mp_at depend on it, so I would expect one to see measurable improvements on their benchmarks. Following is an implementation if
Following is an implementation of it template<std::size_t...> struct indices { using type = indices; }; template<typename, typename> struct merge_indices; template<std::size_t... l, std::size_t... u> struct merge_indices<indices<l...>, indices<u...>> : indices<l..., sizeof...(l) + u...> {}; template<std::size_t n> struct make_indices; template<std::size_t n> using make_indices_t = typename make_indices<n>::type; template<std::size_t n> struct make_indices : merge_indices<make_indices_t<n/2>, make_indices_t<n - n/2>> {}; template<> struct make_indices<0U> : indices<> {}; template<> struct make_indices<1U> : indices<0U> {}; template<std::size_t n> using make_indices_t = typename make_indices<n>::type; Regards, *Bruno C. O. Dutra*