Ok. We've really put a lot of irons in the fire now, so please let me explain.
First of all I want to point out the purpose of my first post: though it is specifically addressed static_log2 it is actually a reaction to a general trend of boost, i.e. that of having complicated solutions for simple problems. I don't say this is the case for all libraries (also because I do not know every single boost library, and I didn't even know the Integer library until Dave indicated it to me a few days ago) but in many cases boost has implementations enormously more complicated than necessary. This state of affairs makes me often revert to my own code for things that are already into boost. Speaking of static_log2 I really didn't understand why we should have such a complicated implementation, and that's why I made a provocation with the stupid snippet I posted initially. The point was that even such a stupid implementation is not only simpler but competes in performances with the current one. I'm well aware that mine is "bad", but the point was exactly that I don't see how the current one is better (also considering in how much trouble it goes due to its use of pts, etc..etc..). Also I want to make clear that this is not an attack to Daryle or to anyone. It may well be that there's a good reason to have the implementation we have and that *I* am just missing it. If not, however, I think we should change it. I see often that people who are very expert in a given field tend to find solutions more complicated than inexpert people, even when the implied complexity buys nothing. To me instead simplicity is important as much as other aspects, and should be abandoned _only_ when it comes, for instance, at correctness' or completeness' cost. I'm under the impression that the current implementation has been chosen a little ingenuously, without thinking how overkilling it is for such a simple task. Of course, and I repeat myself, my "implementation" is the shame of any C++ programmer, but it was just a provocation. Now here are the results of your shell script on my machine: boost::static_log2.hpp real 0m49.182s user 0m23.610s sys 0m22.621s vesa impl (starting from n = 16): real 0m33.693s user 0m10.280s sys 0m22.140s "my" trivial implementation: real 0m31.667s user 0m8.040s sys 0m22.120s Of course there are the result on a particular compiler on a particular platform, but they make us think. Now I'll reply to the other points, which are, to say, a digression from the main topic, because they simply address some aspects of the specific implementation you posted. On Tue, 21 Jan 2003 11:56:31 +0200, "Vesa Karvonen" <[EMAIL PROTECTED]> wrote: >Gennaro Prota: >>Vesa Karvonen: >> > enum {c = (1 << n) <= x}; > >The above should preferably read: > > enum {c = (1ul << n) <= c}; I think you are missing something here, maybe the important fact that an integer type (unsigned long included) may have padding bits or the rules about shift operators. In this case you can still have undefined behavior on an implementation where unsigned long occupies 64 bits but 32 of them are padding (i.e. when unsigned long has a precision of 32). I do know that it is unlikely but this is boost. Please read paragraph 5.8/1 of the standard: "The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand." The meaning of "length in bits" isn't defined in the standard (hence the DR I hinted at) but, believe me, it is the number of bits that contribute to the value, not the number of bits in the object representation. >>Wrong. The left-shift may give undefined behavior, because n can be >>greater than or equal to the number of value bits in an unsigned long >[...] >>The problem is that the C standard (and so C++) provides a xx_BIT macro >>only for the type char. You don't have e.g. INT_BIT or LONG_BIT, and you >>can't use CHAR_BIT*sizeof(int) and CHAR_BIT*sizeof(long) in their place, >>at least not portably, because those expressions give you the number of >>bits in the object representation, and that's not necessarily the same >>as the number of bits used to represent values. > >In this case it is not necessary to know the exact number of value bits. >What is required of n is that it should be a power of two (not guaranteed by >the simple formula used) and (1ul << n) should be less than ULONG_MAX and >((1ul << n) << n) should be less than ULONG_MAX. A value that would fulfill >these requirements can be computed rather easily (and also quite >efficiently, as you don't have to start guessing from 0 or even 1). I'll >leave the construction of such a metafunction as an exercise for the reader. > >>PS: Another problem with your implementation I'll leave it as an >>exercise ;-) This is a hint: > >As you seem to have discovered, there is no such problem. Proof please? There's such a problem When the width w (i.e. the number of value bits) of unsigned long is odd, there are no padding bits, and n is of the form (2**w)-1: since you start from n/2 == (w-1)/2 then you reach n == 0 *before* reaching x == 0. I know no C++ implementation where width is odd but, again, this is *boost*. We must not make unportable assumptions. >[...] >Also, I must point out that timings from one-shot compilations are highly >unreliable. You should average the timings from multiple runs: Done (but just for the sake of discussion, as I said) >[...] >You should also be very careful about what you are measuring. In your test, >you repeated the same assertions twice. I made that intentionally, because I thought someone would have objected that, in real code, it's unlikely that so many different instantiations are made and/or it's unlikely that each of them is made once. >You should be aware that the second >time around, on most reasonable c++ compilers, none of those templates are >really recursed for the second time, because the fully constructed classes >have been cached. I know. Either because I've experimented myself and because I've read Dave's paper in the boost files ;-) >Another problem is that the usage pattern employed in your test is not very >reasonable. static_log2<> is a metafunction that will be used in the >implementation of other metafunctions. Most of the time it is not used in >the top-level and the parameter given to it is dependent on some other >template parameter. Try using the following tester template (where LOG2 is a >macro expanding to the name of the tested static_log2 implementation): > >template<int i> >struct tester { > BOOST_STATIC_CONSTANT(int, > value = > LOG2<i+(1<<0)>::value + > LOG2<i+(1<<1)>::value + > LOG2<i+(1<<2)>::value + > LOG2<i+(1<<3)>::value + > LOG2<i+(1<<4)>::value + > LOG2<i+(1<<5)>::value + > LOG2<i+(1<<6)>::value + > LOG2<i+(1<<7)>::value + > LOG2<i+(1<<8)>::value + > LOG2<i+(1<<9)>::value + > LOG2<i+(1<<10)>::value + > LOG2<i+(1<<11)>::value + > LOG2<i+(1<<12)>::value + > LOG2<i+(1<<13)>::value + > LOG2<i+(1<<14)>::value + > LOG2<i+(1<<15)>::value + > LOG2<i+(1<<16)>::value + > LOG2<i+(1<<17)>::value + > LOG2<i+(1<<18)>::value + > LOG2<i+(1<<19)>::value + > LOG2<i+(1<<20)>::value + > LOG2<i+(1<<21)>::value + > LOG2<i+(1<<22)>::value + > LOG2<i+(1<<23)>::value + > LOG2<i+(1<<24)>::value + > LOG2<i+(1<<25)>::value + > LOG2<i+(1<<26)>::value + > LOG2<i+(1<<27)>::value + > LOG2<i+(1<<28)>::value + > LOG2<i+(1<<29)>::value); >}; > >On g++ 2.96, by the way, the expression > > tester<1>::value + tester<2>::value, > >fails to compile on default settings with the naïve algorithm, because it >exceeds the maximum template recursion depth. I know. In some tests that I did with g++ 2.95 I tried either bumping the maximum with -ftemplate-depth and adding specializations at "regular intervals", i.e. template <> struct log2<16> .. template <> struct log2<256> ... template <> struct log2<4096> ... In both cases the timings were practically the same (g++ 2.95 under Cygwin) Genny. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost