Message ID | 20110927195930.54e0d0df@shotwell |
---|---|
State | New |
Headers | show |
Benjamin, I think tuple is wrong both for performance reasons (I believe these are likely to be serious enough to depress use due to inordinately long compiles) and because it prematurely locks us into a rigid choice of how our typelists are implemented. My inclination is to make it type-independent by returning an unspecified type that can have a sequence of types extracted from it (this is the approach taken by boost::mpl and has loads of experience that shows it is a good approach to metaprogramming). In other words, first<bases<A>>::type would be the first base of A, etc. I've coded this up, and it seems to work very well without committing us to any particular typelist implementation. I don't think it has any downsides relative to tuple. I'll do a little benchmarking to compare it to tuple (I suspect it will be far faster) and then send to the library list, Mike Sent from my iPhone On Sep 27, 2011, at 9:59 PM, "Benjamin Kosnik" <bkoz@redhat.com> wrote: > >> This patch consists intrinsics to properly create the bases and >> direct_bases of a class in the correct order (including multiple >> nested ambiguous virtual and non-virtual classes) for N2965 >> (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2965.html). >> This allows you to create type traits for giving the base classes of >> the class: >> >> template<typename _Tp> >> struct bases >> { >> typedef tuple<__bases(_Tp)...> type; >> }; > > Cool! So glad to see this. > >> I didn't modify the standard library to include the above type trait >> in the patch because it is not yet clear what type it should return >> (e.g., a tuple, a "typelist," something satisfying the requirements >> of a boost::mpl sequence, or a generalization of parameter packs). I >> have (cursorily) tested it with the above type trait and the >> corresponding direct_bases trait. > > OK. > > Here's a patch for the above. What's wrong with tuple? I kind of like > it.... seems simple. It's what's in N2965, so let's start there. > > Since it's the first TR2 header, I did the build bits for you. > > Also, I cc'd the library list. > > best, > benjamin > <20110927-4.patch>
On 28 September 2011 04:22, Michael Spertus wrote: > Benjamin, > I think tuple is wrong both for performance reasons (I believe these are likely to be serious enough to depress use due to inordinately long compiles) and because it prematurely locks us into a rigid choice of how our typelists are implemented. > > My inclination is to make it type-independent by returning an unspecified type that can have a sequence of types extracted from it (this is the approach taken by boost::mpl and has loads of experience that shows it is a good approach to metaprogramming). In other words, first<bases<A>>::type would be the first base of A, etc. Citing Boost MPL as a good way to avoid inordinately long compiles ... interesting! Have you ever tried to reduce a GCC bug report from 20k lines to 20, because most Boost libs include every MPL header?! I hope we can get a simple typelist _without_ needing everything else in MPL, such as the apply and lambda metafunctions (and maybe a lot of that could be massively simplified using variadic templates anyway.)
Don't worry, I'm not suggesting including boost::mpl at all, just leaving the return type of the bases trait unspecified. IMO, your example illustrates my point that without performance tuning, compiling metaprograms can be prohibitively expensive, so I want to avoid running the tuple metaprogram that creates the fields when we never need to instantiate the type. Benchmarks soon. Mike On 9/28/2011 2:53 AM, Jonathan Wakely wrote: > On 28 September 2011 04:22, Michael Spertus wrote: > >> Benjamin, >> I think tuple is wrong both for performance reasons (I believe these are likely to be serious enough to depress use due to inordinately long compiles) and because it prematurely locks us into a rigid choice of how our typelists are implemented. >> >> My inclination is to make it type-independent by returning an unspecified type that can have a sequence of types extracted from it (this is the approach taken by boost::mpl and has loads of experience that shows it is a good approach to metaprogramming). In other words, first<bases<A>>::type would be the first base of A, etc. >> > Citing Boost MPL as a good way to avoid inordinately long compiles ... > interesting! Have you ever tried to reduce a GCC bug report from 20k > lines to 20, because most Boost libs include every MPL header?! > > I hope we can get a simple typelist _without_ needing everything else > in MPL, such as the apply and lambda metafunctions (and maybe a lot of > that could be massively simplified using variadic templates anyway.) > > . > >
OK. Here are some simple benchmarks. I simulated heavy use of reflection with 1000 classes that each had about a thousand base classes. I also created a super-simple typelist class template<typename... T> struct typelist {}; // Variadic templates rock If bases returns a typelist, the program takes about 4 sec. If bases returns a tuple, the program takes about 4 min. If I make the program any bigger, the tuple case fails to compile with spurious error messages, while the typelist version stays quick. Given that metaprograms typically create large class hierarchies (look at Alexandrescu's CreateScatterHierarchy that he uses to implement factory in the Modern C++ design book) and that compile times are an enormous obstacle to metaprogramming, I don't think these tests are at all ridiculous. I think this shows we need to return a typelist instead of a tuple. As I mentioned earlier, I could just return the typelist, or hide it by returning an unspecified type (which would actually be a typelist) that you would apply a first<> and a rest<> template to walk through. This would give us more flexibility for the future (e.g., if a standard typelist type is adopted. Likewise, we would be covered if wanted to change bases implementation in the future to return an associative container. For example, if using size<grep<A, bases<E>::type>>::value to count the number of occurrences of A as a base class of E turns out to be useful). Thanks, Mike On 9/28/2011 6:54 AM, Mike Spertus wrote: > Don't worry, I'm not suggesting including boost::mpl at all, just > leaving the return type of the bases trait unspecified. IMO, your > example illustrates my point that without performance tuning, > compiling metaprograms can be prohibitively expensive, so I want to > avoid running the tuple metaprogram that creates the fields when we > never need to instantiate the type. Benchmarks soon. > > Mike > > On 9/28/2011 2:53 AM, Jonathan Wakely wrote: >> On 28 September 2011 04:22, Michael Spertus wrote: >>> Benjamin, >>> I think tuple is wrong both for performance reasons (I believe these >>> are likely to be serious enough to depress use due to inordinately >>> long compiles) and because it prematurely locks us into a rigid >>> choice of how our typelists are implemented. >>> >>> My inclination is to make it type-independent by returning an >>> unspecified type that can have a sequence of types extracted from it >>> (this is the approach taken by boost::mpl and has loads of >>> experience that shows it is a good approach to metaprogramming). In >>> other words, first<bases<A>>::type would be the first base of A, etc. >> Citing Boost MPL as a good way to avoid inordinately long compiles ... >> interesting! Have you ever tried to reduce a GCC bug report from 20k >> lines to 20, because most Boost libs include every MPL header?! >> >> I hope we can get a simple typelist _without_ needing everything else >> in MPL, such as the apply and lambda metafunctions (and maybe a lot of >> that could be massively simplified using variadic templates anyway.) >> >> . >> >
> OK. Here are some simple benchmarks. I simulated heavy use of > reflection with 1000 classes that each had about a thousand base > classes. I also created a super-simple typelist class > > template<typename... T> struct typelist {}; // Variadic templates rock > > If bases returns a typelist, the program takes about 4 sec. > If bases returns a tuple, the program takes about 4 min. > > If I make the program any bigger, the tuple case fails to compile > with spurious error messages, while the typelist version stays quick. > > Given that metaprograms typically create large class hierarchies > (look at Alexandrescu's CreateScatterHierarchy that he uses to > implement factory in the Modern C++ design book) and that compile > times are an enormous obstacle to metaprogramming, I don't think > these tests are at all ridiculous. > > I think this shows we need to return a typelist instead of a tuple. Yes, compelling. > As I mentioned earlier, I could just return the typelist, or hide it > by returning an unspecified type (which would actually be a typelist) > that you would apply a first<> and a rest<> template to walk through. The interface is still simple, I like it. > This would give us more flexibility for the future (e.g., if a > standard typelist type is adopted. Likewise, we would be covered if > wanted to change bases implementation in the future to return an > associative container. For example, if using size<grep<A, > bases<E>::type>>::value to count the number of occurrences of A as a > base class of E turns out to be useful). This plan sounds excellent to me. -benjamin
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index a59a0b6..e1176ee 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,5 +1,14 @@ 2011-09-27 Benjamin Kosnik <bkoz@redhat.com> + * doc/Makefile.am: Add tr2 support. + * doc/Makefile.in: Regenerate. + +2011-09-27 Mike Spertus <mike_spertus@symantec.com> + + * include/tr2/type_traits (bases, direct_bases): New. + +2011-09-27 Benjamin Kosnik <bkoz@redhat.com> + * doc/html/*: Regenerate. * doc/Makefile.am: Un-nest the ext output directory. diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 4016882..9fdaa8d 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -604,6 +604,11 @@ tr1_headers = \ ${tr1_srcdir}/wchar.h \ ${tr1_srcdir}/wctype.h +tr2_srcdir = ${glibcxx_srcdir}/include/tr2 +tr2_builddir = ./tr2 +tr2_headers = \ + ${tr2_srcdir}/type_traits + decimal_srcdir = ${glibcxx_srcdir}/include/decimal decimal_builddir = ./decimal decimal_headers = \ @@ -887,7 +892,7 @@ endif # CLEANFILES and all-local are kept up-to-date. allstamped = \ stamp-std stamp-bits stamp-bits-sup stamp-c_base stamp-c_compatibility \ - stamp-backward stamp-ext stamp-pb stamp-tr1 stamp-decimal \ + stamp-backward stamp-ext stamp-pb stamp-tr1 stamp-tr2 stamp-decimal \ stamp-debug stamp-parallel stamp-profile stamp-profile-impl \ stamp-host @@ -1002,6 +1007,11 @@ stamp-tr1: ${tr1_headers} @-cd ${tr1_builddir} && $(LN_S) $? . 2>/dev/null @$(STAMP) stamp-tr1 +stamp-tr2: ${tr2_headers} + @-mkdir -p ${tr2_builddir} + @-cd ${tr2_builddir} && $(LN_S) $? . 2>/dev/null + @$(STAMP) stamp-tr2 + stamp-decimal: ${decimal_headers} @-mkdir -p ${decimal_builddir} @-cd ${decimal_builddir} && $(LN_S) $? . 2>/dev/null @@ -1245,6 +1255,9 @@ install-headers: $(mkinstalldirs) $(DESTDIR)${gxx_include_dir}/${tr1_builddir} for file in ${tr1_headers}; do \ $(INSTALL_DATA) $${file} $(DESTDIR)${gxx_include_dir}/${tr1_builddir}; done + $(mkinstalldirs) $(DESTDIR)${gxx_include_dir}/${tr2_builddir} + for file in ${tr2_headers}; do \ + $(INSTALL_DATA) $${file} $(DESTDIR)${gxx_include_dir}/${tr2_builddir}; done $(mkinstalldirs) $(DESTDIR)${gxx_include_dir}/${decimal_builddir} for file in ${decimal_headers}; do \ $(INSTALL_DATA) $${file} $(DESTDIR)${gxx_include_dir}/${decimal_builddir}; done @@ -1291,7 +1304,7 @@ clean-local: # developer tries to create them via make in the include build # directory. (This is more of an example of how this kind of rule can # be made.) -.PRECIOUS: $(std_headers) $(c_base_headers) $(tr1_headers) +.PRECIOUS: $(std_headers) $(c_base_headers) $(tr1_headers) $(tr2_headers) $(decimal_headers) $(ext_headers) $(std_headers): ; @: $(c_base_headers): ; @: diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index 58dbfc4..5ad5932 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -854,6 +854,11 @@ tr1_headers = \ ${tr1_srcdir}/wchar.h \ ${tr1_srcdir}/wctype.h +tr2_srcdir = ${glibcxx_srcdir}/include/tr2 +tr2_builddir = ./tr2 +tr2_headers = \ + ${tr2_srcdir}/type_traits + decimal_srcdir = ${glibcxx_srcdir}/include/decimal decimal_builddir = ./decimal decimal_headers = \ @@ -1125,7 +1130,7 @@ PCHFLAGS = -x c++-header -nostdinc++ $(CXXFLAGS) # CLEANFILES and all-local are kept up-to-date. allstamped = \ stamp-std stamp-bits stamp-bits-sup stamp-c_base stamp-c_compatibility \ - stamp-backward stamp-ext stamp-pb stamp-tr1 stamp-decimal \ + stamp-backward stamp-ext stamp-pb stamp-tr1 stamp-tr2 stamp-decimal \ stamp-debug stamp-parallel stamp-profile stamp-profile-impl \ stamp-host @@ -1402,6 +1407,11 @@ stamp-tr1: ${tr1_headers} @-cd ${tr1_builddir} && $(LN_S) $? . 2>/dev/null @$(STAMP) stamp-tr1 +stamp-tr2: ${tr2_headers} + @-mkdir -p ${tr2_builddir} + @-cd ${tr2_builddir} && $(LN_S) $? . 2>/dev/null + @$(STAMP) stamp-tr2 + stamp-decimal: ${decimal_headers} @-mkdir -p ${decimal_builddir} @-cd ${decimal_builddir} && $(LN_S) $? . 2>/dev/null @@ -1630,6 +1640,9 @@ install-headers: $(mkinstalldirs) $(DESTDIR)${gxx_include_dir}/${tr1_builddir} for file in ${tr1_headers}; do \ $(INSTALL_DATA) $${file} $(DESTDIR)${gxx_include_dir}/${tr1_builddir}; done + $(mkinstalldirs) $(DESTDIR)${gxx_include_dir}/${tr2_builddir} + for file in ${tr2_headers}; do \ + $(INSTALL_DATA) $${file} $(DESTDIR)${gxx_include_dir}/${tr2_builddir}; done $(mkinstalldirs) $(DESTDIR)${gxx_include_dir}/${decimal_builddir} for file in ${decimal_headers}; do \ $(INSTALL_DATA) $${file} $(DESTDIR)${gxx_include_dir}/${decimal_builddir}; done @@ -1673,7 +1686,7 @@ clean-local: # developer tries to create them via make in the include build # directory. (This is more of an example of how this kind of rule can # be made.) -.PRECIOUS: $(std_headers) $(c_base_headers) $(tr1_headers) +.PRECIOUS: $(std_headers) $(c_base_headers) $(tr1_headers) $(tr2_headers) $(decimal_headers) $(ext_headers) $(std_headers): ; @: $(c_base_headers): ; @: