5 ms·

Does the program need to do the map, set, vector, iterator, ect... operations or does it not? If the work needs to be done then it needs to be instantiated in

Does the program need to do the map, set, vector, iterator, ect... operations or does it not? If the work needs to be done then it needs to be instantiated in the code somehow. What is your proposed alternative?

dllthomas 12y ago
To me, the parent seemed to be complaining about multiple copies of effectively the same map (or set, or vector, ...) code for different types, not the presence of the map (or ...) code in the first place. The latter is obviously unavoidable. The former is an efficiency trade-off between the optimization opportunities afforded by specialization and inlining, and the smaller instruction footprint of keeping the code generic.
- corysama 12y ago
  So then, is the proposed alternative a library of containers and algorithms that are genericized via void pointers, memcpy sizes and function pointer predicates?
  - dllthomas 12y ago
    I'd assume so. In principle you can get there without sacrificing type safety (http://en.wikipedia.org/wiki/Type_erasure http://en.wikipedia.org/wiki/Type_erasure). In practice, I don't know whether or not you can write type safe C++ that compiles that way.
    - corysama 12y ago
      This seems like a nice article series on the subject http://akrzemi1.wordpress.com/2013/11/18/type-erasure-part-i/ http://akrzemi1.wordpress.com/2013/11/18/type-erasure-part-i... Just getting started on it, it seems that the theme is that you can't have the same binary code work on different types without having a run-time indirection in there somewhere. But, you can use templates to keep that indirection convenient and type safe. And, you can structure your templates to only specialize a minimal amount of code necessary to interface your type into a non-specialized algorithm.
      - dllthomas 12y ago
        Right, that looks like an exploration of what I was talking about (and at a skim, looks solid). "you can't have the same binary code work on different types without having a run-time indirection in there somewhere" That's certainly the case, but if you're passing by reference you already have an indirection, so that may or may not mean additional run-time overhead.
    - cbsmith 12y ago
      In truth, if you really care about it, you can take a policy based design approach to this and have explicit rules for when you may or may not do type erasure. It's definitely a bit of work, but you can actually get full compile_time type safety and yet avoid having duplicative code with various tricks like (this skips over a lot of the pain and isn't really how you'd do it... just illustrative): template <std::size_t N> struct raw { template <typename U> constexpr raw(U x, std::enable_if<.....>); template <typename U> constexpr operator U(); }; template <template ContainerType, typename T, std::enable_if<std::is_trivially_convertible<T, ....> > > struct somewhat_erased_container : private ContainerType<raw<sizeof(T)>> { }; It's particularly easy to do with containers of pointers (of course).
      - dllthomas 12y ago
        Very nice.
        cbsmith 12y ago
        Herb Sutter has prompted a variant of the Pimpl idiom that kind of goes this way, as have others. Linus was proudly showing how C was better than C++ by virtue of being able to do something much like this, but of course you can accomplish this in C++, of course there are some down sides that accompany it. Most importantly with C++ you can much more easily provide more robust compile time type safety with little or no runtime overhead.

dllthomas 12y ago

To me, the parent seemed to be complaining about multiple copies of effectively the same map (or set, or vector, ...) code for different types, not the presence of the map (or ...) code in the first place. The latter is obviously unavoidable. The former is an efficiency trade-off between the optimization opportunities afforded by specialization and inlining, and the smaller instruction footprint of keeping the code generic.

corysama 12y ago
So then, is the proposed alternative a library of containers and algorithms that are genericized via void pointers, memcpy sizes and function pointer predicates?
- dllthomas 12y ago
  I'd assume so. In principle you can get there without sacrificing type safety (http://en.wikipedia.org/wiki/Type_erasure http://en.wikipedia.org/wiki/Type_erasure). In practice, I don't know whether or not you can write type safe C++ that compiles that way.
  - corysama 12y ago
    This seems like a nice article series on the subject http://akrzemi1.wordpress.com/2013/11/18/type-erasure-part-i/ http://akrzemi1.wordpress.com/2013/11/18/type-erasure-part-i... Just getting started on it, it seems that the theme is that you can't have the same binary code work on different types without having a run-time indirection in there somewhere. But, you can use templates to keep that indirection convenient and type safe. And, you can structure your templates to only specialize a minimal amount of code necessary to interface your type into a non-specialized algorithm.
    - dllthomas 12y ago
      Right, that looks like an exploration of what I was talking about (and at a skim, looks solid). "you can't have the same binary code work on different types without having a run-time indirection in there somewhere" That's certainly the case, but if you're passing by reference you already have an indirection, so that may or may not mean additional run-time overhead.
  - cbsmith 12y ago
    In truth, if you really care about it, you can take a policy based design approach to this and have explicit rules for when you may or may not do type erasure. It's definitely a bit of work, but you can actually get full compile_time type safety and yet avoid having duplicative code with various tricks like (this skips over a lot of the pain and isn't really how you'd do it... just illustrative): template <std::size_t N> struct raw { template <typename U> constexpr raw(U x, std::enable_if<.....>); template <typename U> constexpr operator U(); }; template <template ContainerType, typename T, std::enable_if<std::is_trivially_convertible<T, ....> > > struct somewhat_erased_container : private ContainerType<raw<sizeof(T)>> { }; It's particularly easy to do with containers of pointers (of course).
    - dllthomas 12y ago
      Very nice.
      - cbsmith 12y ago
        Herb Sutter has prompted a variant of the Pimpl idiom that kind of goes this way, as have others. Linus was proudly showing how C was better than C++ by virtue of being able to do something much like this, but of course you can accomplish this in C++, of course there are some down sides that accompany it. Most importantly with C++ you can much more easily provide more robust compile time type safety with little or no runtime overhead.