I've come up with an alternative way to invoke the typeof emulations that have been posted. It basically works by defining an iterator over the encoded type. Unfortunately, it can't be used inside a function, and is awkward to use in general, but has the advantage is that it only has to define the call to foo once, which might result in faster compile times. It could possibly also remove the limit on the complexity of the type. Arkadiy's version would require a some changes to do this, but I think Peder's could quite easily. Although I'm not sure as I've only had a brief look at his version. I've implemented it as a sort of typedef, which seems like the easiest way to use it. It's probably easier to understand the code than my explanation, so here it is. It's based on Arkadiy's version in the yahoo groups file section. #define BOOST_TYPEOF_TYPEDEF_ITERATOR_NAME(Name) \ BOOST_PP_CAT(BOOST_TYPEOF_TYPEDEF_ITERATOR_##Name##_, __LINE__) #define BOOST_TYPEOF_TYPEDEF_ITERATOR(Expr, Name) \ struct BOOST_TYPEOF_TYPEDEF_ITERATOR_NAME(Name) { \ template <int pos> \ struct iterator { \ typedef boost::mpl::int_< \ sizeof(boost::type_of::foo<pos>(Expr))> type; \ typedef iterator<pos+1> next; \ }; \ }; #define BOOST_TYPEOF_TYPEDEF(Expr, Name) \ BOOST_TYPEOF_TYPEDEF_ITERATOR(Expr, Name) \ typedef boost::type_of::decode_type< \ BOOST_TYPEOF_TYPEDEF_ITERATOR_NAME(Name)::iterator<0> \ >::type Name; #define BOOST_TYPEOF_TPL_TYPEDEF(Expr, Name) \ BOOST_TYPEOF_TYPEDEF_ITERATOR(Expr, Name) \ typedef typename boost::type_of::decode_type< \ BOOST_TYPEOF_TYPEDEF_ITERATOR_NAME(Name)::iterator<0> \ >::type Name; Here is an example of it's use: template <class Op> struct result_of_nullary_functor { static Op op; BOOST_TYPEOF_TPL_TYPEDEF(op(), type); }; struct g { int operator()(); }; BOOST_MPL_ASSERT_IS_SAME(result_of_nullary_functor<g>::type, int); I've only tested on the intel linux compiler. Daniel
On Sat, 28 Aug 2004 12:47:23 +0100, Daniel James <daniel@calamity.org.uk> wrote:
I've come up with an alternative way to invoke the typeof emulations that have been posted. It basically works by defining an iterator over the encoded type. Unfortunately, it can't be used inside a function, and is awkward to use in general, but has the advantage is that it only has to define the call to foo once, which might result in faster compile times.
It could possibly also remove the limit on the complexity of the type. Arkadiy's version would require a some changes to do this, but I think Peder's could quite easily. Although I'm not sure as I've only had a brief look at his version.
I've implemented it as a sort of typedef, which seems like the easiest way to use it.
It's probably easier to understand the code than my explanation, so here it is. It's based on Arkadiy's version in the yahoo groups file section.
#define BOOST_TYPEOF_TYPEDEF_ITERATOR_NAME(Name) \ BOOST_PP_CAT(BOOST_TYPEOF_TYPEDEF_ITERATOR_##Name##_, __LINE__)
#define BOOST_TYPEOF_TYPEDEF_ITERATOR(Expr, Name) \ struct BOOST_TYPEOF_TYPEDEF_ITERATOR_NAME(Name) { \ template <int pos> \ struct iterator { \ typedef boost::mpl::int_< \ sizeof(boost::type_of::foo<pos>(Expr))> type; \ typedef iterator<pos+1> next; \ }; \ };
#define BOOST_TYPEOF_TYPEDEF(Expr, Name) \ BOOST_TYPEOF_TYPEDEF_ITERATOR(Expr, Name) \ typedef boost::type_of::decode_type< \ BOOST_TYPEOF_TYPEDEF_ITERATOR_NAME(Name)::iterator<0> \ >::type Name;
#define BOOST_TYPEOF_TPL_TYPEDEF(Expr, Name) \ BOOST_TYPEOF_TYPEDEF_ITERATOR(Expr, Name) \ typedef typename boost::type_of::decode_type< \ BOOST_TYPEOF_TYPEDEF_ITERATOR_NAME(Name)::iterator<0> \ >::type Name;
Here is an example of it's use:
template <class Op> struct result_of_nullary_functor { static Op op; BOOST_TYPEOF_TPL_TYPEDEF(op(), type); };
struct g { int operator()(); }; BOOST_MPL_ASSERT_IS_SAME(result_of_nullary_functor<g>::type, int);
I like the idea, and it is compatible with the first version of typedef that I implemented. In this version, a function returns the size of element # N in a sequence: sizeof(encode_fn<N>::encode(expr)); The problem with this expression, is that because of the lack of partial template specialization, you have to use functions to deduce the type of an expression, and you have to use sizeof for every step in order to get something sensible out of the function expression: Typically, to deduce a pointer expression, you have to do something like: template<typename U> static typename sizer<encode_indirection<Level-1,U,Types>::value>::type encode(U const volatile*); BOOST_STATIC_CONSTANT(unsigned,value=sizeof( encode((T)NULL) )); The compiler did not like deep nesting of sizeof calls. This caused the compiler to complain after 9 or 10 levels. The solution was to roll out the nesting, so now I have functions returning function pointers: template<typename T,typename Types> typename modifiers<T,Types>::type foo(void (*)(sizer<CV_POINTER>,T const volatile*,Types)); where modifiers<T,Types> deduces the proper function pointer to decode T. In this way, foo(foo(foo_start(expr))) points to the 3'rd element in the expression. I have tested this approach with an expression with the depth 120 and BOOST_MAX_TYPEOF_SIZE 150 (with mindboggingly slow compilation times) and it managed to deduce its type correctly. The problem of my current implementation, is that this is an N^2 process: value_type<sizeof(foo_start(expr)), //Level 1 value_type<sizeof(foo(foo_start(expr))),//Level 2 value_type<sizeof(foo(foo(foo_start(expr)))),Level 3 ...
What would be very nice (but probably unattainable) was to reduce this into an N process. Any suggestions would be most welcome.
-- Peder Holt
I've only tested on the intel linux compiler.
Daniel
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Peder Holt wrote:
What would be very nice (but probably unattainable) was to reduce this into an N process. Any suggestions would be most welcome.
I've no idea how to do that, but I know how to get it to work with a macro like mine. And possibly improve normal use as well (although, I'm not sure about that). You can change foo so that as part of it's return type it returns a value_list containing the encoded types so far, and keeps adding the encoded types to it. Then each iteration you call foo the same number of times (this actually makes things worse, but bear with me...) and change enocode to pick the appropriate value from the value_list. Now, since foo can add more than one value to the value_list at a time, this means you can do more encoding per call to foo. So, it might be possible to reduce the number times you call foo. Also, since foo is called the same number of times every iteration, you can use my iterator macro, which means that the number of calls becomes o(nm), where n is the preset value, and m is the complexity of the type - this can be a real gain for simple types. I've tried adapting your version to do this, I've put the code at: http://myweb.tiscali.co.uk/calamity/code/typeof_vintage2.zip If you look at typeof.hpp and modifiers.hpp you should get a good idea of what I've done. It's only tested on Visual C++ v6.0, and I expect it will probably require some changes to work on more recent versions. It needs to be cleaned up considerably, it's only really meant as a demonstration of the idea. I haven't really taken advantage of being able to do more encoding per call, that will probably require another rewrite and might not be practicle. So for normal use it's currently worse. But, when using BOOST_TYPEOF_TYPEDEF it does allow you to specify a higher number of calls to foo without loosing out for simpler types (since they only iterate a small number of times). It also generates slightly shorter value_lists, which reduces the number of iterations required. This could possibly be worthwhile? If you've still got it, could I have another look at your original version? I deleted it when I downloaded your new one. It might be possible to use the techniques you used there for this type of implementation. thanks, Daniel
On Sun, 29 Aug 2004 16:34:54 +0100, Daniel James <daniel@calamity.org.uk> wrote:
Peder Holt wrote:
What would be very nice (but probably unattainable) was to reduce this into an N process. Any suggestions would be most welcome.
I've no idea how to do that, but I know how to get it to work with a macro like mine. And possibly improve normal use as well (although, I'm not sure about that). <snip>
http://myweb.tiscali.co.uk/calamity/code/typeof_vintage2.zip
If you look at typeof.hpp and modifiers.hpp you should get a good idea of what I've done.
Neat. Definitely a saver for small types. I thought of one potentially useful trick, that might theoretically could reduce the number of calls to order N. By using the trick presented by Daniel Wallin and Goran Mitrovic in another post, conserning compile time constants: template<int N> struct counter : counter<N - 1> {}; template<> struct counter<0> {}; template<int N> struct size_type { enum{value=N}; typedef char(&type)[value + 1]; }; size_type<0>::type check(...); template<class T, int N, int ID> struct set_variable { typedef counter<10> start_type; enum { current = sizeof(check((T*)0, (start_type*)0)) - 1, next = current + 1 }; friend typename size_type<next>::type check(T*, counter<next>*) {} friend typename size_type<ID>::type value(T*, counter<N>*) {} }; #define CURRENT(T) (sizeof(check((T*)0, (counter<10>*)0)) - 1) #define VALUE(T,N) (sizeof(value((T*)0, (counter<N>*)0)) - 1) #define SET(T, N, ID) set_variable<T, N, ID>() //TYPEOF macro... typedef mpl::int_<CURRENT(int)> iterator_start; invoke foo(expr,mpl::int_<CURRENT(int)>) somehow; typedef mpl::int_<CURRENT(int)> iterator_end; typedef decode<iterator_start,iterator_end>::type type; Let each foo call SET(int,CURRENT(int)+1,CODE), where CODE represents the type. Then VALUE(int,iterator_start::value) would give the compile time constant of the first element, and VALUE(int,iterator_start::value+1) for the next etc. etc. This way, foo() would be called exactly as many times as the expression is deep, and have no restrictions whatsoever (except compiler limitations on template complexity) of the expression depth. Only problem I have so far, is how to get the SET calls occur inside a foo call before the type is defined. Perhaps do something like this: template<typename T,int N> foo(T*,set_variable<int,N,POINTER>); template<typename T,int N> foo(T&,set_variable<int,N,REFERENCE>); and use sizeof of the expression in the end. I haven't tried this trick yet, but I will certainly give it a shot.
It's only tested on Visual C++ v6.0, and I expect it will probably require some changes to work on more recent versions. It needs to be cleaned up considerably, it's only really meant as a demonstration of the idea.
I haven't really taken advantage of being able to do more encoding per call, that will probably require another rewrite and might not be practicle. So for normal use it's currently worse.
But, when using BOOST_TYPEOF_TYPEDEF it does allow you to specify a higher number of calls to foo without loosing out for simpler types (since they only iterate a small number of times). It also generates slightly shorter value_lists, which reduces the number of iterations required. This could possibly be worthwhile?
Definitely. I will be looking at this approach more in detail if my over-ambitious approach above fails :)
If you've still got it, could I have another look at your original version? I deleted it when I downloaded your new one. It might be possible to use the techniques you used there for this type of implementation.
I put the source under: http://groups.yahoo.com/group/boost/files/typeof_vintage_old.zip I got an idea of how to improve the limit of this method. Here is the way I encode templates: template<> struct encode_impl<BOOST_TYPEOF_UNIQUE_ID()> { template<int Level> struct level { template<typename A0,typename A1,typename Types> struct encoder { typedef type_list<A0,type_list<A1,Types> > type_list; typedef Types BOOST_PP_CAT(types_,template_size); BOOST_STATIC_CONSTANT(int,value =(encode_type<Level-1,types_0::type,types_1>::value)); }; }; template<> struct level<0> { template<typename A0,typename A1,typename Types> struct encoder { BOOST_STATIC_CONSTANT(int,value = BOOST_TYPEOF_UNIQUE_ID()); }; }; }; Instead, It might be possible to do something like this: template<> struct encode_impl<BOOST_TYPEOF_UNIQUE_ID()> { template<int Level> struct level { template<typename A0,typename A1,typename Types> struct encoder { BOOST_STATIC_CONSTANT(unsigned, depth0=depth<A0>::value); BOOST_STATIC_CONSTANT(unsigned, depth1=depth<A1>::value+depth0); BOOST_STATIC_CONSTANT(unsigned, depth=depth1+1); /* if Level<depth0, encode_type<Level-1,A0> else encode_type<Level-1,A1> I am not sure how the depth template should be implemented, but this method should improve the limit from 10 values in value_list to 10 template nestings. }; }; -- Peder Holt
thanks,
Daniel
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
"Daniel James" <daniel@calamity.org.uk> wrote
I've come up with an alternative way to invoke the typeof emulations that have been posted. It basically works by defining an iterator over the encoded type. Unfortunately, it can't be used inside a function, and is awkward to use in general, but has the advantage is that it only has to define the call to foo once, which might result in faster compile times.
I believe (and please correct me if I am wrong) that what you actually mean is the call to foo need to be defined as many times as actually needed as opposed to always BOOST_MPL_LIMIT_VECTOR_SIZE times in my implementation. I don't see how you can get away with defining call to foo just "once" 'cause you still need to do it for every "pos". Being able to call foo exactly as many times as actually needed would be very attractive, but I think, any attempt to implement this (including yours) would suffer from the same problem: new templates need to be created at the time typeof us used. This results from unability to pass expression into a template, so templates have to be re-created on the call site for any given expression by the means of preprocessor. This introduces the problem of naming such classes. You employ __LINE__ to solve it, but I don't believe it's enough, since problems can easily pop up when envoking typeof from different files. So I still better like the approach where TYPEOF macro expands to a single call to a template meta-function, with no need to automatically create intermediate classes. This way it can be used in any context, and we don't introduce additional issues related to automatic class generation at the call site. Regards, Arkadiy
Arkadiy Vertleyb wrote:
I believe (and please correct me if I am wrong) that what you actually mean is the call to foo need to be defined as many times as actually needed as opposed to always BOOST_MPL_LIMIT_VECTOR_SIZE times in my implementation. I don't see how you can get away with defining call to foo just "once" 'cause you still need to do it for every "pos".
When I said defined, I was talking about the code generated by the macro. I think you mean the number of times it is instantiated, so you're right.
This introduces the problem of naming such classes. You employ __LINE__ to solve it, but I don't believe it's enough, since problems can easily pop up when envoking typeof from different files.
I don't just use __LINE__, I also use the name of the typedef. I think this should be unique within the current namespace. The line number probably isn't needed at all. But, if this isn't acceptable then it could define a named struct, with the type as a member, i.e. the user would name the struct, and then get the type using 'name::type'.
So I still better like the approach where TYPEOF macro expands to a single call to a template meta-function, with no need to automatically create intermediate classes. This way it can be used in any context, and we don't introduce additional issues related to automatic class generation at the call site.
I'm actually inclined to agree here. I came up with the idea a little while ago when I first tried your typeof. I didn't think it was that useful so I left it on the shelf. But when I saw that Peder was doing, I saw a use for it. Daniel
"Daniel James" <daniel@calamity.org.uk> wrote
Arkadiy Vertleyb wrote:
This introduces the problem of naming such classes. You employ __LINE__ to solve it, but I don't believe it's enough, since problems can easily pop up when envoking typeof from different files.
I don't just use __LINE__, I also use the name of the typedef. I think this should be unique within the current namespace. The line number probably isn't needed at all. But, if this isn't acceptable then it could define a named struct, with the type as a member, i.e. the user would name the struct, and then get the type using 'name::type'.
Agreed, but this makes typedef-oriented syntax a pre-requisit rather than just an example. Actually I agree that comming up with a solution that would require only as many foo<pos>() instantiations as needed (maybe it's already time to change this function's name) would be very attractive, since it would remove that constant time that can become quite noticable for simple types. Unfortunaly, for the reasons I mentioned in my previous post, I don't believe that it can be achieved without generating templates on the call site... Regards, Arkadiy
Arkadiy Vertleyb <vertleyb <at> hotmail.com> writes:
Actually I agree that comming up with a solution that would require only as many foo<pos>() instantiations as needed (maybe it's already time to change this function's name) would be very attractive, since it would remove that constant time that can become quite noticable for simple types. Unfortunaly, for the reasons I mentioned in my previous post, I don't believe that it can be achieved without generating templates on the call site...
Sorry to intrude, but, would it be possible for you to: - explain a bit algorithm on which your typeof works since the implementation is too messy to basics be stripped out - explain why is your algorithm so slow - on my Athlon 2200 and VS7.1, it takes about a second per typeof too be processed, which is, in my opinion, quite unacceptable. What is the speed bottleneck and is there a way to strip some features (function pointers, for example) to fasten compilation? Thanks.
"Goran Mitrovic" <gmit@inet.hr> wrote
Sorry to intrude, but, would it be possible for you to: - explain a bit algorithm on which your typeof works
1) The expression is passed into the function template foo(). Inside this function the required type is known. 2) To pass the type across the function boundaries, it is encoded into a list of integers. 3) Every item in the list gets passed across function boundaries individually by the means of sizeof(). 4) The list of integers gets decoded into the original type. To encode a type into a list of integers, partial template specializations are used (this is fundamental difference of my approach from one suggested by Peder). These specializations are defined mainly by the means of two macros: REGISTER_TYPE and REGISTER_TEMPLATE. Every type and template that participates in the expression needs to be registered. Every type/template is assigned a unique integer identifier. A type is encoded by a single integer (its identifier). A template is encoded by its identifier plus recursively encoding its parameters. A similar approach is employed for pointers, references, function pointers, etc., with the difference that the specializations are specified directly, by the library.
- explain why is your algorithm so slow - on my Athlon 2200 and VS7.1, it takes about a second per typeof too be processed
First of all, it can't be fast, by definition. Just think what's happenning here... The compiler already knows the type of the expression, but it wouldn't tell us. If it would, there would be no problem in the first place. So we are trying to find out indirectly, and to do this we instantiate a couple of hundreds of templates... The template metaprogramming is done by the means of template instantiation -- I don't know any other way -- if you do, please tell me. And template instantiation is not such a cheap thing. Barring this, there is an internal ineficiency in my algorithm, and I already explained it in one of my previous post. The problem is I am always passing a pre-defined number of integers, namely BOOST_MPL_LIMIT_VECTOR_SIZE of them, even if the type is simple enough to be encoded just with a couple of integers. The reason of this is that the real size of the vector becomes known at compile time. To be able to operate this compile-time constant, I need to pass it to a template meta-function. But it's impossible to also pass the expression (the original parameter of typeof ) to a metafunction. Therefore, the only way to do it is to create metafunction for this particular expression, by the means of preprocessor, at the call site. And this introduces a few very nasty (IMO) things, such as class naming issues, limitation of contexts in which typeof can be used, etc. Some people may consider these issues acceptable, for me it's a showstopper.
which is, in my opinion, quite unacceptable.
:-(
What is the speed bottleneck and is there a way to strip some features (function pointers, for example) to fasten compilation?
These features just provide additional template specializations, and IMO should not noticably affect the compilation speed. If you types are simple, reduce BOOST_MPL_LIMIT_VECTOR_SIZE -- it will get faster.
the implementation is too messy
Would you mind to elaborarate on this please -- I find this statement quite offensive. More importantly, I just find it not true. Regards, Arkadiy
participates in the expression needs to be registered. Every type/template is assigned a unique integer identifier. A type is encoded by a single integer (its identifier). A template is encoded by its identifier plus recursively encoding its parameters.
How did you made templates been recursively encoded? Is the recursion (theoretically) infinite?
Barring this, there is an internal ineficiency in my algorithm, and I already explained it in one of my previous post. The problem is I am always passing a pre-defined number of integers, namely BOOST_MPL_LIMIT_VECTOR_SIZE of them, even if the type is simple enough to be encoded just with a couple of integers. The reason of this is that the real size of the vector becomes known at compile time. To be able to operate this compile-time constant, I need to pass it to a template meta-function. But it's impossible to also pass the
Would it be possible to use different structure instead of vector? Some kind of compile-time btree structure might be a smaller stress for a compiler if that would be suitable for your algorithm.
the implementation is too messy Would you mind to elaborarate on this please -- I find this statement quite offensive. More importantly, I just find it not true.
The code that uses boost preprocessor library (mine is included) is messy by default. :) You shouldn't and please don't be offended since I haven't meant it like that! Your typeof, except for speed, works extraordinary well! I'm talking about the appearance of the code - I might be a weak in the terms of generic programming, but, it's practically impossible to find out how your method works just looking at the code! :(
I think i am closing in on the ultimate typeof implementation. Given the maximum depth of an expression = N (BOOST_MPL_LIMIT_VECTOR_SIZE) and the depth of the expression we are evaluating = m My earlier implementation was of the order (N^2) Arkadiys implementation (if I am correct) is of the order (m*N) My new implementation is of the order (m) !! Meaning it is linear. I only need to evaluate an expression once, and if the expression is simple, very few templates need to be instantiated. There is only the compiler limit to the complexity of an expression. Here is the define for BOOST_TYPEOF: #define BOOST_TYPEOF(expr) \ boost::type_of::decode<\ boost::type_of::value_iterator<\ sizeof(boost::type_of::encode_start(expr))\
\ ::type
I think this is about as simple as it can get without the real thing. encode_start(expr) does not return the size of an item in the expression. It returns the starting index of an iterator. Every level in the expression instantiates a template class. Every template class instantiates two friend functions. The first function: encode_value() takes the current index as input argument, and returns the encoded value of the current level. The other function: encode_index() incremets the current index count. (Up to a maximum of BOOST_MAX_TYPEOF_COUNTER, defaulted to 1000) This is the maximum number of levels that can be encoded in a single c++ file. To access these values: sizeof(boost::type_of::encode_value((boost::type_of::encode_counter<N>*)0) returns the value at iterator N. (sizeof(*boost::type_of::encode_index((boost::type_of::encode_counter<BOOST_MAX_TYPEOF_COUNTER>*)0))) returns the next available index These are defined as BOOST_TYPEOF_VALUE(N) and BOOST_TYPEOF_INDEX() respectively I tested my 120 level deep type with very little overhead in compile time. Since I rely heavily on the order of template instantiation, it may be fragile to compiler errors (I am compiling this on VC 6.5) I have had some problems with ETI screwing up the scheme when typeof is used inside templates, but this is workaroundable by being more relaxed on the indexing. The source can be found at: http://groups.yahoo.com/group/boost/files/typeof_fast.zip
"Peder Holt" <peder.holt@gmail.com> wrote
I think i am closing in on the ultimate typeof implementation.
Given the maximum depth of an expression = N (BOOST_MPL_LIMIT_VECTOR_SIZE) and the depth of the expression we are evaluating = m My earlier implementation was of the order (N^2) Arkadiys implementation (if I am correct) is of the order (m*N)
How do you estimate this? I believe my implementation has an order of N (BOOST_MPL_LIMIT_VECTOR_SIZE).
My new implementation is of the order (m) !!
Without automatically creating classes at the typeof invocation? Regards, Arkadiy
On Tue, 31 Aug 2004 07:09:10 -0400, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
"Peder Holt" <peder.holt@gmail.com> wrote
I think i am closing in on the ultimate typeof implementation.
Given the maximum depth of an expression = N (BOOST_MPL_LIMIT_VECTOR_SIZE) and the depth of the expression we are evaluating = m My earlier implementation was of the order (N^2) Arkadiys implementation (if I am correct) is of the order (m*N)
How do you estimate this? I believe my implementation has an order of N (BOOST_MPL_LIMIT_VECTOR_SIZE).
My new implementation is of the order (m) !!
Without automatically creating classes at the typeof invocation?
To be precise, m*N/2 To deduce the type of an expression int* a[10], sizeof(foo<n>(a)), n=1..N the compiler needs to generate the following types (names may vary) encode_array<T[10],1> encode_array<T[10],2> encode_pointer<T*,1> encode_array<T[10],3> encode_pointer<T*,2> encode_impl<int,1> encode_array<T[10],4> encode_pointer<T*,3> encode_impl<int,2> encode_dummy ... -> N. that is, N*m/2 types needs to be generated by the compiler. Please correct me if I'm wrong. My implementation generates the following types: encode_array<T[10],1> encode_pointer<T*,2> encode_impl<int,3> encode_dummy<4> (plus dummy functions due to lack of partial template specialization) m functions, m class types. m*2 template types On a conforming compiler, m template types. -- Peder Holt
Regards, Arkadiy
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
"Peder Holt" <peder.holt@gmail.com> wrote
To be precise, m*N/2
To deduce the type of an expression int* a[10], sizeof(foo<n>(a)), n=1..N the compiler needs to generate the following types (names may vary) encode_array<T[10],1>
encode_array<T[10],2> encode_pointer<T*,1>
encode_array<T[10],3> encode_pointer<T*,2> encode_impl<int,1>
encode_array<T[10],4> encode_pointer<T*,3> encode_impl<int,2> encode_dummy ... -> N.
that is, N*m/2 types needs to be generated by the compiler. Please correct me if I'm wrong.
In my implementation there is no encode_array<T[10], 1>, encode_array<T[10],2>, etc. There is: template<class V, class T, int Size> struct encode_type_impl<V, const T[Size]> Which is the same type throughout BOOST_TYPEOF invocation, and therefore gets instantiated only once. So I insist that the order of my algorithm is O(N), which results from the need to instantiate "foo<n>(expr)" for every n from 0 to N-1. If you came up with an O(M) rather than O(N) algorithm, where M is the real size of the encoding sequence, this is really great for simple types. I'll do my best to understand your solution and adapt it to my implementation (if possible). For now, it really looks more like a miracle to me...
I think i am closing in on the ultimate typeof implementation.
The "ultimate" implementation will come from the compiler vendors :) Regards, Arkadiy
Arkadiy Vertleyb wrote:
"Peder Holt" <peder.holt@gmail.com> wrote
In my implementation there is no encode_array<T[10], 1>, encode_array<T[10],2>, etc.
There is:
template<class V, class T, int Size> struct encode_type_impl<V, const T[Size]>
Which is the same type throughout BOOST_TYPEOF invocation, and therefore gets instantiated only once. So I insist that the order of my algorithm is O(N), which results from the need to instantiate "foo<n>(expr)" for every n from 0 to N-1.
I think some (older?) compilers might not reuse the encode_type_impl instance, so they recalculate the list of integers (which takes o(m)) for all N instantiations of foo, giving a total O(Nm). Hopefully, this isn't the case for the newer compilers, that your implementation targets. So on them it's o(N), as you say. I wonder if it's worth combinig the two techniques. That is, using partial specialisation to encode the type, but storing the value list as 'compile-time constants' as in Peder's version. I think it should be possible.
I think i am closing in on the ultimate typeof implementation.
The "ultimate" implementation will come from the compiler vendors :)
Still, his implementation is fantastic, considering that it runs on Visual C++ 6. Since my last post, I've made quite a lot of progress at getting my variation to cope with complicated expressions with less calls to 'foo'. But Peder's version takes about half the time to run my tests, and will scale a lot better. Daniel
"Daniel James" <daniel@calamity.org.uk> wrote
Still, his [Peder's] implementation is fantastic, considering that it runs on Visual C++ 6.
No doubt about this. As you can see, I hadn't even made this to be my goal. I've spent so much time in the past coping with various ICEs, ISOs, and ETIs, that I really, really want to avoid dealing with this compiler...
I wonder if it's worth combinig the two techniques. That is, using partial specialisation to encode the type, but storing the value list as 'compile-time constants' as in Peder's version. I think it should be possible.
At this point I am not even able to understand Peder's implementation, let alone the ability to combine techniques. It really looks more like a miracle to me: #define BOOST_TYPEOF(expr) \ boost::type_of::decode<\ boost::type_of::value_iterator<\ sizeof(boost::type_of::encode_start(expr))\
\
The value_iterator<> has just one integer parameter. How can decode<> deduce any type from it?! Regards, Arkadiy
On Tue, 31 Aug 2004 13:42:17 -0400, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
"Daniel James" <daniel@calamity.org.uk> wrote
Still, his [Peder's] implementation is fantastic, considering that it runs on Visual C++ 6.
No doubt about this. As you can see, I hadn't even made this to be my goal. I've spent so much time in the past coping with various ICEs, ISOs, and ETIs, that I really, really want to avoid dealing with this compiler...
I wonder if it's worth combinig the two techniques. That is, using partial specialisation to encode the type, but storing the value list as 'compile-time constants' as in Peder's version. I think it should be possible.
At this point I am not even able to understand Peder's implementation, let alone the ability to combine techniques. It really looks more like a miracle to me:
#define BOOST_TYPEOF(expr) \ boost::type_of::decode<\ boost::type_of::value_iterator<\ sizeof(boost::type_of::encode_start(expr))\
\
The value_iterator<> has just one integer parameter. How can decode<> deduce any type from it?!
Regards, Arkadiy
Ok. I see what you do, and agree that on newer compilers, your code is of the order O(N) (with your newest adjustments, even O(m)) I also see that your implementation requires the use of mpl, as you require random access to the list of generated integers. This introduces the before mentioned mpl limit of 60 (or around there) which it turns out is difficult to bypass. It would be awesome to have a forward iterator approach for the access of integer values, as it would free you from the "chains" of mpl. As to the implementation of my code, I got the inspiration to my implementation from Daniel Wallins post some time back on compile time constants: http://lists.boost.org/MailArchives/boost/msg69842.php As he states in his post, the solution is not portable. It relies on a common compiler defect. Just for once MSVC's defects work with us in stead of against us :) I struggled quite a bit with the code myself before it dawned on me. What gave me the insight, is that start_type (counter<10>) in reality sets the maximum number of static constants you are allowed to define. Each time a template class is instantiated, it generates two template function overloads. Before the compilation starts, a predefined check functions is defined: size_type<0>::type check(...); At the first instantiation of set_variable, the function size_type<1>::type check(counter<1>*) is added to the function overload map. (forget the T variable in the original post. It is of no use in understanding the problem) sizeof(check((counter<10>*)NULL)) will search for the best overload available, and find the size_type<1>::type check(counter<1>*) overload. The next time set_variable is instantiated, the function size_type<2>::type check(counter<2>*) is added to the function overload map. sizeof(check((counter<10>*)NULL)) will search for the best overload available, and find the size_type<2>::type check(counter<2>*) overload. This is because counter<10> inherits from counter<9> inherits from ... inherits from counter<2> inherits from counter<1>. Hence, counter<2> is a better candidate then counter<1> because of the way the compiler traverses the code, In addition, another function is installed: counter<N> value(counter<2>). In my code, i use sizeof(check(counter<10>*)NULL)) to find the first available counter index. I then use sizeof(value((counter<iterator_value>*)NULL)) to find the next encoded integer. I am all for joining our efforts and creating a single typeof implementation. typeof is even more needed for non-conforming compilers to manage simple tasks as remove_pointer, remove_bounds etc.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
"Peder Holt" <peder.holt@gmail.com> wrote
Ok. I see what you do, and agree that on newer compilers, your code is of the order O(N) (with your newest adjustments, even O(m)) I also see that your implementation requires the use of mpl, as you require random access to the list of generated integers. This introduces the before mentioned mpl limit of 60 (or around there) which it turns out is difficult to bypass.
It's not really difficult (see http://lists.boost.org/MailArchives/boost/msg10949.php). I will probably stop using BOOST_MPL_LIMIT_VECTOR_SIZE, and introduce my own #define, something like BOOST_TYPEOF_LIMIT_SIZE. Then I will generate necessary vector definitions based on this limit.
It would be awesome to have a forward iterator approach for the access of integer values, as it would free you from the "chains" of mpl.
I don't really view MPL as "chains". Sure, it introduces certain overhead (very annoying with VC6, by the way), but, when working with newer and more conformant compilers, it behaves nicely and really enables one to remove a lot of complexity from the code. Do you still write your own linked lists or do you use ones provided by STL? :)
I am all for joining our efforts and creating a single typeof implementation. typeof is even more needed for non-conforming compilers to manage simple tasks as remove_pointer, remove_bounds etc.
I am not sure about "single typeof implementation". You may have started with some of my code, but by now two implementations look totaly different. Since you are not going to adapt my approach (because of limitations of VC6), and I am (most likely) not going to adapt yours (because, despite the fact that I admire what you were able to achieve with VC6, I still happen to like my approach better), there is not much opportunity for code reuse. What we probably should do is to keep our "interfaces" in-sync. This way we'll be able to dispatch at the configuration level, in a similar way I am doing now with the native typeof. How about that? Regards, Arkadiy
On Wed, 1 Sep 2004 11:36:16 -0400, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
"Peder Holt" <peder.holt@gmail.com> wrote
Ok. I see what you do, and agree that on newer compilers, your code is of the order O(N) (with your newest adjustments, even O(m)) I also see that your implementation requires the use of mpl, as you require random access to the list of generated integers. This introduces the before mentioned mpl limit of 60 (or around there) which it turns out is difficult to bypass.
It's not really difficult (see http://lists.boost.org/MailArchives/boost/msg10949.php). I will probably stop using BOOST_MPL_LIMIT_VECTOR_SIZE, and introduce my own #define, something like BOOST_TYPEOF_LIMIT_SIZE. Then I will generate necessary vector definitions based on this limit.
The problem with this is compile times. As the message thread specified above. This will causes the preprocessor to generate a lot of code (for vector1,vector2,vector3,vector4 etc. etc), causing the compile times to plummet as the vector size goes up. Also, you force all users of typeof to work with very large mpl vectors. I am not so sure this would be a generally accepted penalty for working with typeof... My guess is that implementing a linked list, and searching for the element at position N would require less compile time. Alternatively, make your own vector type, with a predefined BOOST_TYPEOF_LIMIT_SIZE number of arguments. mpl::vector is a general type vector with many advanced features. All you really need is to know the integral value at position N.
It would be awesome to have a forward iterator approach for the access of integer values, as it would free you from the "chains" of mpl.
I don't really view MPL as "chains". Sure, it introduces certain overhead (very annoying with VC6, by the way), but, when working with newer and more conformant compilers, it behaves nicely and really enables one to remove a lot of complexity from the code. Do you still write your own linked lists or do you use ones provided by STL? :)
I am all for joining our efforts and creating a single typeof implementation. typeof is even more needed for non-conforming compilers to manage simple tasks as remove_pointer, remove_bounds etc.
I am not sure about "single typeof implementation". You may have started with some of my code, but by now two implementations look totaly different. Since you are not going to adapt my approach (because of limitations of VC6), and I am (most likely) not going to adapt yours (because, despite the fact that I admire what you were able to achieve with VC6, I still happen to like my approach better), there is not much opportunity for code reuse.
What we probably should do is to keep our "interfaces" in-sync. This way we'll be able to dispatch at the configuration level, in a similar way I am doing now with the native typeof.
How about that?
That was what I was thinking of, yes. Since my method uses a common compiler bug, it can not be made to work with all the compilers anyway. Conditional compile is a nice thing :) The two (or more) emulations of typeof should probably be tested with different compilers to see which implementation is best suited for that compiler.
Regards, Arkadiy
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Peder Holt wrote:
My guess is that implementing a linked list, and searching for the element at position N would require less compile time. Alternatively, make your own vector type, with a predefined BOOST_TYPEOF_LIMIT_SIZE number of arguments. mpl::vector is a general type vector with many advanced features. All you really need is to know the integral value at position N.
Using mpl views might be better. Currently the implementation works by passing a list/vector to encode and adding to it. Instead encode could just return the sequence for it's sub-type, which can then be combined using mpl::joint_view, or similar. For example, in the current implementation: template<class V, class T> struct encode_type_impl<V, const T> { typedef typename encode_type< typename detail::push_back< V , mpl::int_<CONST_ID> >::type , T>::type type; }; Would become something like: template<class T> struct encode_type_impl<const T> { typedef boost::mpl::joint_view< boost::mpl::single_view<mpl::int_<CONST_ID> >, encode_type<T> >; }; The big advantage here is that if T has already been encoded (even as part of a completely different type) it can be reused. For example if the following were encoded: std::pair<int, int> std::pair<std::pair<int, int>, std::pair<int, int> > The existing versions would encode std::pair<int, int> 3 times, this would do it once. Another advantage is that the templates would be less deeply nested than with a list. It's also a bit cleaner to implement. I hope that makes sense. I was playing around with this idea a little while ago, but didn't quite finish it. I might have another go in the future (I'll wait for Arkadiy's new version) if no one else does. If you do want to try, you should probably wait for the new version of mpl, which will fix a bug that causes problems here. By the way, in the above example joint_view is probably a little too complex. Something like this can be used instead: template<class Seq, class T> struct push_front_view { struct begin { typedef boost::mpl::forward_iterator_tag category; typedef T type; typedef typename Seq::begin next; }; typedef typename Seq::end end; }; Daniel
"Daniel James" <daniel@calamity.org.uk> wrote
Using mpl views might be better. Currently the implementation works by passing a list/vector to encode and adding to it. Instead encode could just return the sequence for it's sub-type, which can then be combined using mpl::joint_view, or similar.
Note that push_back<mpl::vector<...> > requires just one template instantiation. I am not sure why views are better. And views definitely don't provide constant-time lookup.
For example, in the current implementation:
template<class V, class T> struct encode_type_impl<V, const T> { typedef typename encode_type< typename detail::push_back< V , mpl::int_<CONST_ID> >::type , T>::type type; };
Would become something like:
template<class T> struct encode_type_impl<const T> { typedef boost::mpl::joint_view< boost::mpl::single_view<mpl::int_<CONST_ID> >, encode_type<T> >; };
The big advantage here is that if T has already been encoded (even as part of a completely different type) it can be reused. For example if the following were encoded:
std::pair<int, int> std::pair<std::pair<int, int>, std::pair<int, int> >
The existing versions would encode std::pair<int, int> 3 times, this would do it once.
Agreed, but this should be weighted against not having direct access. Regards, Arkadiy
Arkadiy Vertleyb wrote:
"Daniel James" <daniel@calamity.org.uk> wrote
Using mpl views might be better. Currently the implementation works by passing a list/vector to encode and adding to it. Instead encode could just return the sequence for it's sub-type, which can then be combined using mpl::joint_view, or similar.
Note that push_back<mpl::vector<...> > requires just one template instantiation. I am not sure why views are better. And views definitely don't provide constant-time lookup.
I didn't mean to suggest that they're better in that regard. If the lookup time proves to be an obstacle, then the sequence can be copied into a mpl::vector, or Peder's compile time variables. The real advantage is losing the extra template parameter, which might not make much of a difference at all. But it might make the code a bit cleaner and more 'functional'. It's probably not worth your time looking into it. But I might have a go when you release your next version (so I'm not working against a moving target). And I'd like to wait for the new version of mpl. Daniel
Daniel James <daniel@calamity.org.uk> writes:
Arkadiy Vertleyb wrote:
"Daniel James" <daniel@calamity.org.uk> wrote
Using mpl views might be better. Currently the implementation works by passing a list/vector to encode and adding to it. Instead encode could just return the sequence for it's sub-type, which can then be combined using mpl::joint_view, or similar. Note that push_back<mpl::vector<...> > requires just one template instantiation. I am not sure why views are better. And views definitely don't provide constant-time lookup.
I didn't mean to suggest that they're better in that regard. If the lookup time proves to be an obstacle, then the sequence can be copied into a mpl::vector, or Peder's compile time variables. The real advantage is losing the extra template parameter, which might not make much of a difference at all. But it might make the code a bit cleaner and more 'functional'.
It's probably not worth your time looking into it. But I might have a go when you release your next version (so I'm not working against a moving target). And I'd like to wait for the new version of mpl.
Apparently it's already on the main trunk. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
Peder Holt <peder.holt@gmail.com> writes:
On Wed, 1 Sep 2004 11:36:16 -0400, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
"Peder Holt" <peder.holt@gmail.com> wrote
Ok. I see what you do, and agree that on newer compilers, your code is of the order O(N) (with your newest adjustments, even O(m)) I also see that your implementation requires the use of mpl, as you require random access to the list of generated integers. This introduces the before mentioned mpl limit of 60 (or around there) which it turns out is difficult to bypass.
It's not really difficult (see http://lists.boost.org/MailArchives/boost/msg10949.php). I will probably stop using BOOST_MPL_LIMIT_VECTOR_SIZE, and introduce my own #define, something like BOOST_TYPEOF_LIMIT_SIZE. Then I will generate necessary vector definitions based on this limit.
The problem with this is compile times. As the message thread specified above. This will causes the preprocessor to generate a lot of code (for vector1,vector2,vector3,vector4 etc. etc), causing the compile times to plummet as the vector size goes up. Also, you force all users of typeof to work with very large mpl vectors. I am not so sure this would be a generally accepted penalty for working with typeof...
My guess is that implementing a linked list, and searching for the element at position N would require less compile time.
MPL vectors contain optimizations that a naive type vector (and _especially_ a typelist) does not, so I wouldn't be so confident about that prediction. But why guess? Benchmark it yourself. Oh, and test it against the mplbook branch of boost/mpl, so you get an accurate view of the next release.
Alternatively, make your own vector type, with a predefined BOOST_TYPEOF_LIMIT_SIZE number of arguments. mpl::vector is a general type vector with many advanced features. All you really need is to know the integral value at position N.
You mean iterators? What makes you think their presence is going to cause compilation to slow down? This is starting to ring of MPL FUD. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
On Thu, 02 Sep 2004 06:40:12 -0400, David Abrahams <dave@boost-consulting.com> wrote:
Peder Holt <peder.holt@gmail.com> writes:
On Wed, 1 Sep 2004 11:36:16 -0400, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
"Peder Holt" <peder.holt@gmail.com> wrote
Ok. I see what you do, and agree that on newer compilers, your code is of the order O(N) (with your newest adjustments, even O(m)) I also see that your implementation requires the use of mpl, as you require random access to the list of generated integers. This introduces the before mentioned mpl limit of 60 (or around there) which it turns out is difficult to bypass.
It's not really difficult (see http://lists.boost.org/MailArchives/boost/msg10949.php). I will probably stop using BOOST_MPL_LIMIT_VECTOR_SIZE, and introduce my own #define, something like BOOST_TYPEOF_LIMIT_SIZE. Then I will generate necessary vector definitions based on this limit.
The problem with this is compile times. As the message thread specified above. This will causes the preprocessor to generate a lot of code (for vector1,vector2,vector3,vector4 etc. etc), causing the compile times to plummet as the vector size goes up. Also, you force all users of typeof to work with very large mpl vectors. I am not so sure this would be a generally accepted penalty for working with typeof...
My guess is that implementing a linked list, and searching for the element at position N would require less compile time.
MPL vectors contain optimizations that a naive type vector (and _especially_ a typelist) does not, so I wouldn't be so confident about that prediction. But why guess? Benchmark it yourself.
Oh, and test it against the mplbook branch of boost/mpl, so you get an accurate view of the next release.
Alternatively, make your own vector type, with a predefined BOOST_TYPEOF_LIMIT_SIZE number of arguments. mpl::vector is a general type vector with many advanced features. All you really need is to know the integral value at position N.
You mean iterators? What makes you think their presence is going to cause compilation to slow down? This is starting to ring of MPL FUD.
I agree. I will do some more research before I criticise mpl for being overweight. Sorry. My other comment still stands, though. When BOOST_MPL_LIMIT_VECTOR_SIZE is increased to encompass more parameters for typeof, this will affect the compile times for other uses of mpl::vector in the project as well. -- Peder Holt
-- Dave Abrahams Boost Consulting http://www.boost-consulting.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Peder Holt <peder.holt@gmail.com> writes:
overweight. Sorry. My other comment still stands, though. When BOOST_MPL_LIMIT_VECTOR_SIZE is increased to encompass more parameters for typeof, this will affect the compile times for other uses of mpl::vector in the project as well.
Which is why you don't do that. You do what Aleksey suggested and Arkadiy is planning to do instead. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
"David Abrahams" <dave@boost-consulting.com> wrote
MPL vectors contain optimizations that a naive type vector (and _especially_ a typelist) does not
Just out of curiosity, what's a "naive type vector"?
You mean iterators? What makes you think their presence is going to cause compilation to slow down?
Well, iterators are separate templates, and require to be instantiated... Also if you dereference them through meta-function, like mpl::dereference<Iter>::type, that's one more instantiation. (Not that I think it's critical for the typeof implementation) Regards, Arkadiy
"Arkadiy Vertleyb" <vertleyb@hotmail.com> writes:
"David Abrahams" <dave@boost-consulting.com> wrote
MPL vectors contain optimizations that a naive type vector (and _especially_ a typelist) does not
Just out of curiosity, what's a "naive type vector"?
A type vector you might implement after thinking about it for 5 minutes.
You mean iterators? What makes you think their presence is going to cause compilation to slow down?
Well, iterators are separate templates, and require to be instantiated...
Only if used. The template does need to be parsed, but that's not a big hit. mpl::at<some_mpl_vector, N>::type doesn't use iterators.
Also if you dereference them through meta-function, like mpl::dereference<Iter>::type, that's one more instantiation.
Of course, but only if you use iterators. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
"David Abrahams" <dave@boost-consulting.com> wrote
Just out of curiosity, what's a "naive type vector"?
A type vector you might implement after thinking about it for 5 minutes.
Sorry, I mistakingly read it as a "NATIVE type vector" :)
You mean iterators? What makes you think their presence is going to cause compilation to slow down?
Well, iterators are separate templates, and require to be instantiated...
Only if used. The template does need to be parsed, but that's not a big hit. mpl::at<some_mpl_vector, N>::type doesn't use iterators.
Also if you dereference them through meta-function, like mpl::dereference<Iter>::type, that's one more instantiation.
Of course, but only if you use iterators.
Of course, if used. What I meant is that if you want to get all elements of an mpl::vector<> it _might_ be faster to get them by index rather then through iterators... Regards, Arkadiy
"Peder Holt" <peder.holt@gmail.com> wrote
The problem with this is compile times. As the message thread specified above. This will causes the preprocessor to generate a lot of code (for vector1,vector2,vector3,vector4 etc. etc), causing the compile times to plummet as the vector size goes up.
Note that this is done once per compilation unit (and can be easily taken care of by the pre-compiled headers feature on the systems that support them). When considering performance we should clearly separate what's happenning once per translation unit, and what's happenning on the per-typeof invocation basis. Please also note that your "compile-time variables" require to instantiate a template (or maybe even 3 templates) every time a variable is set.
Also, you force all users of typeof to work with very large mpl vectors.
I don't think so. As I said, I will most likely stop using BOOST_MPL_LIMIT_VECTOR_SIZE, and use my own limit N to directly work with mpl::vectorN<>. And as far as I understand MPL, the fact that I am working with, e.g., mpl::vector256<> doesn't prevent other facilities in the same translation unit from using mpl::vector3<>. Regards, Arkadiy
On Thu, 2 Sep 2004 09:24:11 -0400, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
"Peder Holt" <peder.holt@gmail.com> wrote
The problem with this is compile times. As the message thread specified above. This will causes the preprocessor to generate a lot of code (for vector1,vector2,vector3,vector4 etc. etc), causing the compile times to plummet as the vector size goes up.
Note that this is done once per compilation unit (and can be easily taken care of by the pre-compiled headers feature on the systems that support them).
When considering performance we should clearly separate what's happenning once per translation unit, and what's happenning on the per-typeof invocation basis.
Please also note that your "compile-time variables" require to instantiate a template (or maybe even 3 templates) every time a variable is set.
Also, you force all users of typeof to work with very large mpl vectors.
I don't think so. As I said, I will most likely stop using BOOST_MPL_LIMIT_VECTOR_SIZE, and use my own limit N to directly work with mpl::vectorN<>.
And as far as I understand MPL, the fact that I am working with, e.g., mpl::vector256<> doesn't prevent other facilities in the same translation unit from using mpl::vector3<>.
Ok. I agree. If you work directly on the vectorN templates, mpl::vector is not affected. Given the need for random access, mpl is probably the best choice after all. I'll do some research on your code (when I get the time, and you have the new version ready) to test some of my ideas to see if I have a point or not :) -- Peder Holt
Regards, Arkadiy
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Thu, 2 Sep 2004 09:28:00 -0400, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
"Peder Holt" <peder.holt@gmail.com> wrote in message
My guess is that implementing a linked list, and searching for the element at position N would require less compile time.
Why?
Basically the same argument that Daniel had. Probably cheaper to build than a vector, but since the lookup times are greater (at least for the latter elements in the sequence) you will probably not gain much anyway.
Again, please keep in mind per-translation unit versus per-typeof invocation issue.
Regards, Arkadiy
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Peder Holt wrote:
Basically the same argument that Daniel had. Probably cheaper to build than a vector, but since the lookup times are greater (at least for the latter elements in the sequence) you will probably not gain much anyway.
That wasn't actually my argument. The main advantage that I saw was replacing: template <typename Vector, typename T> struct encode; with: template <typename T> struct encode; The possible advantage is that compilers can reuse more instantiations of encode. It might also simplify this heavily specialised template. Unfortunately, this is all speculation. I haven't done anything to back it up. Since I can't use the more recent versions of Visual C++, I can't even test on that compiler. Daniel
"Peder Holt" <peder.holt@gmail.com> wrote
As to the implementation of my code, I got the inspiration to my implementation from Daniel Wallins post some time back on compile time constants: http://lists.boost.org/MailArchives/boost/msg69842.php
I compiled this code in VC7.1, and it did compile although with warnings. But then I modified main to look like this: int main() { SET(X, 10); std::cout << CURRENT(X) << "\n"; std::cout << VALUE(X) << "\n"; SET(X, 15); std::cout << CURRENT(X) << "\n"; std::cout << VALUE(X) << "\n"; SET(X, 20); std::cout << CURRENT(X) << "\n"; std::cout << VALUE(X) << "\n"; SET(X, 15); std::cout << CURRENT(X) << "\n"; std::cout << VALUE(X) << "\n"; } the output was somewhat different than one would expect: 1 10 2 15 3 20 3 -- wrong 20 -- wrong How do you handle this in your typeof implementation? Do you reset it somehow between typeofs? Or do you start from the next available number? Regards, Arkadiy
On Wed, 1 Sep 2004 14:26:30 -0400, Arkadiy Vertleyb <vertleyb@hotmail.com> wrote:
"Peder Holt" <peder.holt@gmail.com> wrote
As to the implementation of my code, I got the inspiration to my implementation from Daniel Wallins post some time back on compile time constants: http://lists.boost.org/MailArchives/boost/msg69842.php
I compiled this code in VC7.1, and it did compile although with warnings.
But then I modified main to look like this:
int main() { SET(X, 10); std::cout << CURRENT(X) << "\n"; std::cout << VALUE(X) << "\n"; SET(X, 15); std::cout << CURRENT(X) << "\n"; std::cout << VALUE(X) << "\n"; SET(X, 20); std::cout << CURRENT(X) << "\n"; std::cout << VALUE(X) << "\n"; SET(X, 15); std::cout << CURRENT(X) << "\n"; std::cout << VALUE(X) << "\n"; }
the output was somewhat different than one would expect:
1 10 2 15 3 20 3 -- wrong 20 -- wrong
How do you handle this in your typeof implementation? Do you reset it somehow between typeofs? Or do you start from the next available number?
That is because the class set_variable<X,15> has already been instantiated. When you instantiate it again, you get the old implementation of set_variable. To overcome this problem, you need to add an additional template parameter to the set_variable class: template<int N> struct counter : counter<N - 1> {}; template<> struct counter<0> {}; template<int N> struct size_type { typedef char(&type)[N + 1]; }; size_type<0>::type check(...); template<class T, int Current, int N> struct set_variable { typedef counter<10> start_type; enum { current = Current, next = current + 1 }; friend typename size_type<next>::type check(T*, counter<next>*) {} friend typename size_type<N>::type value(T*, counter<current>*) {} }; #define CURRENT(T) (sizeof(check((T*)0, (counter<10>*)0)) - 1) #define VALUE(T) (sizeof(value((T*)0, (counter<10>*)0)) - 1) #define SET(T, N) set_variable<T,CURRENT(T), N>() #include <iostream> struct X {}; int main() { SET(X, 10); std::cout << CURRENT(X) << "\n"; std::cout << VALUE(X) << "\n"; SET(X, 15); std::cout << CURRENT(X) << "\n"; std::cout << VALUE(X) << "\n"; SET(X, 20); std::cout << CURRENT(X) << "\n"; std::cout << VALUE(X) << "\n"; SET(X, 15); std::cout << CURRENT(X) << "\n"; std::cout << VALUE(X) << "\n"; } voila. -- Peder Holt
Regards, Arkadiy
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
"Daniel James" <daniel@calamity.org.uk> wrote
Still, his implementation is fantastic, considering that it runs on Visual C++ 6. Since my last post, I've made quite a lot of progress at getting my variation to cope with complicated expressions with less calls to 'foo'. But Peder's version takes about half the time to run my tests, and will scale a lot better.
Besides... I've just made a little improvement to my implementation: I added another function to determine the size of encoded expression: template<class T> char(&size(const T&))[ mpl::size<typename encode_type<mpl::vector0<>, T>::type>::value ]; Then I modified the nth item extraction to look like this: #define BOOST_TYPEOF_TYPEITEM(z, n, expr)\ boost::mpl::int_<sizeof(boost::type_of::foo<(n < sizeof(boost::type_of::size(expr)))?n:sizeof(boost::type_of::size(expr))>(ex pr))> Note that now no new templates gets instantiated for n larger than size. I tried it at work, and this improvement cuts almost in half the compile time of my example (with Spirit, Lambda, etc.), presumably having taken care of smaller types. I'll post the modified system later, when I am done with integral template parameters. Regards, Arkadiy
I've been trying out your new version, and I found that it was fairly easy to run out of indicies when using it repeatedy. Looking at the code, I think it should be possible to only generate one value per encoding. Basically my idea is that instead of using: friend sizer<VOLATILE> encode_value(encode_counter<Index>*); You could use: template<unsigned EncodingId, unsigned Index = 0> struct value_pair { typedef value_pair<EncodingId, Index+1> next; }; friend sizer<VOLATILE> encode_value(value_pair<EncodingId, Index>*); The existing compile time variable mechanism would just be used to generate the increasing EncodingId's - one per typedef. I included the next member so that the value_pair could be passed by type, replacing the existing Index parameter. Then whenever you currently use Index+1, you can use 'typename ValuePair::next'. I guess this is a little obvious, so sorry if you're already doing something like it. If it doesn't make sense I can put together an implementation. Daniel
On Thu, 02 Sep 2004 10:43:36 +0100, Daniel James <daniel@calamity.org.uk> wrote:
I've been trying out your new version, and I found that it was fairly easy to run out of indicies when using it repeatedy. Looking at the code, I think it should be possible to only generate one value per encoding. Basically my idea is that instead of using:
friend sizer<VOLATILE> encode_value(encode_counter<Index>*);
You could use:
template<unsigned EncodingId, unsigned Index = 0> struct value_pair { typedef value_pair<EncodingId, Index+1> next; };
friend sizer<VOLATILE> encode_value(value_pair<EncodingId, Index>*);
The existing compile time variable mechanism would just be used to generate the increasing EncodingId's - one per typedef. I included the next member so that the value_pair could be passed by type, replacing the existing Index parameter. Then whenever you currently use Index+1, you can use 'typename ValuePair::next'.
I guess this is a little obvious, so sorry if you're already doing something like it. If it doesn't make sense I can put together an implementation.
Daniel
In the current version of typeof that you have, I made a very quick and dirty workaround for a MSVC ETI problem. The problem arose from typeof being used inside a template class, and caused the starting index values to be garbled. As a quick workaround, every time BOOST_TYPEOF is used, the index is incremented by 100, meaning you can only use BOOST_TYPEOF 10 times (with the current BOOST_MAX_TYPEOF_COUNTER) When I analyzed the problem later, I discovered that all that is needed is to set the starting index to 100, and the problem goes away. I fixed the problem and resubmitted it to boost/files. In this implementation, the index is greedy, meaning that a type with depth of 2 will only occupy 2 indices. If you still encounter problems, try to increase BOOST_MAX_TYPEOF_COUNTER I also made some additional fixes to make typeof compile in release (VC 6.5) (Requires Multithreaded DLL compile condition in order to not ICE...) Good luck. Thank you for the feedback.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (5)
-
Arkadiy Vertleyb -
Daniel James -
David Abrahams -
Goran Mitrovic -
Peder Holt