Integer promotions, conversions, coercions and templates :(

[MikeP]

I need help (but nevermind that!) templates and the C++ integer rules are
confusing me! (No occifer, I have not been drinking, I am just dazed and
confused by C++ integer rules!).

// CheckBit
// Checks the status of individual bits of any unsigned integer type.
// Indexing of bits starts at 1, not 0.
// mask can be any unsigned integer type.
// W is the width of the type T.
//
template <typename T, unsigned int W>
bool CheckBit(T& mask, T n)
{ // The assertion should be an exception, I know.
Assert((n >= 1) && (n <= W), "Bit index out of range.")
return ((mask & ((T)1) << (n-((T)1))) != 0);
}

I wanted to use the appropriate integer type suffix as a template
parameter to use on the 1's (don't know if I needed to though), but C++
templates won't allow that so I have the casts-to-T all over the place
but I'm not sure if they are necessary. I made arg n a type T just to
avoid fld and n being different unsigned integer types.

Is CheckBit correct? If not, can it be corrected? Can it be improved?

 

[Ian Collins]

I need help (but nevermind that!) templates and the C++ integer rules are
confusing me! (No occifer, I have not been drinking, I am just dazed and
confused by C++ integer rules!).

// CheckBit
// Checks the status of individual bits of any unsigned integer type.
// Indexing of bits starts at 1, not 0.
// mask can be any unsigned integer type.
// W is the width of the type T.
//
template<typename T, unsigned int W>
bool CheckBit(T& mask, T n)
{ // The assertion should be an exception, I know.
Assert((n>= 1)&& (n<= W), "Bit index out of range.")

Missing semicolon.

return ((mask& ((T)1)<< (n-((T)1))) != 0);
}

I wanted to use the appropriate integer type suffix as a template
parameter to use on the 1's (don't know if I needed to though), but C++
templates won't allow that so I have the casts-to-T all over the place
but I'm not sure if they are necessary.

Why don't you just use

const T one(1);
return (((mask & one) << (n-one)) != 0);

I made arg n a type T just to
avoid fld and n being different unsigned integer types.
fld?

Is CheckBit correct? If not, can it be corrected? Can it be improved?

Test it!

 

[MikeP]

Missing semicolon.

The Assert macro has it.

Why don't you just use

const T one(1);
return (((mask & one) << (n-one)) != 0);

I don't know that it is better. It's a little prettier. I'll look at the
generated assembly but why bother before determining whether both or
either are valid or even necessary? Can I just use plain '1'? Will the
compiler bit-shift against a 64-bit '1' without me helping it do so?

fld?

mask. (It was 'fld' prior to being 'mask').

Test it!

Oh, I have and it does (well the code that the example herein is based on
does, anyway), but I meant correct from an implementation standpoint, not
from an algorithmic standpoint. There is a lot of potential stuff going
on with integers and stuff, especially if you remove the casts. And what
about across different compilers and platforms?

 

[MikeP]

Missing semicolon.


Why don't you just use

const T one(1);
return (((mask & one) << (n-one)) != 0);

Adds one move instruction to get '1' into 'one' (which is in a register)
over the cast-to-T implementation (2 move instructions for 64-bit T), so
I'd keep the ugly version. Using the suffix would be the way to write
CheckBit if it wasn't a template:

return ((mask & 1ui64<< (n-1ui64)) != 0);

I think it would be OK to use:

return ((mask & 1<< (n-1)) != 0);

if I didn't want allow 64-bit masks on a 32-bit platform, but I do, so I
need either your technique or the casts because templates don't allow
using the integer literal suffixes.

I tried:

template <typename T, uint32 W, const char* S>
....

return ((mask & 1 S << (n-1 S)) != 0);
....

where 'S' s the suffix string, but though the char* parameter is allowed,
it won't expand in the body of CheckBit (compiler thinks that 'S' is an
identifier).

So this is a case where templates hose-up the algorithm, apparently.

 

[Ian Collins]

Adds one move instruction to get '1' into 'one' (which is in a register)
over the cast-to-T implementation (2 move instructions for 64-bit T), so
I'd keep the ugly version. Using the suffix would be the way to write
CheckBit if it wasn't a template:

Poor job on the compiler's part!

The function should optimise down to 0 or 1.

 

[Öö Tiib]

The example is actually an inline method in a class, but even so, the
compiler didn't inline it. Weird. (My example should have had the
"inline" keyword on it also). My bad, I'm in debug mode with inlining
overridden! I'll do the release version and repost later. (Still
educational though from a learning-assembly and code generation
perspective).

It does seem that templates are trumped by a preprocessor macro this
time, for the macro does not require a change to the algorithm. Templates
defficient?

You are in debugging mode evaluating performance of compiler-generated
code? Worthless waste of time. Turn all optimizations that you plan to
use in production code on. Otherwise you get wrong impression what
compiler will really do.

 

[Öö Tiib]

I need help (but nevermind that!) templates and the C++ integer rules are
confusing me! (No occifer, I have not been drinking, I am just dazed and
confused by C++ integer rules!).

// CheckBit
// Checks the status of individual bits of any unsigned integer type.
// Indexing of bits starts at 1, not 0.
// mask can be any unsigned integer type.
// W is the width of the type T.
//
template <typename T, unsigned int W>
bool CheckBit(T& mask, T n)
{   // The assertion should be an exception, I know.
    Assert((n >= 1) && (n <= W), "Bit index out of range.")

    return ((mask & ((T)1) << (n-((T)1))) != 0);

Everybody else usually count bits starting from 0, why you count them
starting from 1?

 

[Öö Tiib]

No, read the post from the beginning. The post is about the "impedance
mismatch" between templates and the C++ type system.


Reread what I wrote above! Geez, what an opportunist.

You better retry again. I see no differences in generated code if i
use inline template function or macro when checking a bit. So you do
something wrong. Geez what a noob.

 

[Ian Collins]

The example is actually an inline method in a class, but even so, the
compiler didn't inline it. Weird. (My example should have had the
"inline" keyword on it also).

That's unnecessary in this case.

My bad, I'm in debug mode with inlining overridden!
Oops...

I'll do the release version and repost later. (Still
educational though from a learning-assembly and code generation
perspective).

It does seem that templates are trumped by a preprocessor macro this
time, for the macro does not require a change to the algorithm. Templates
defficient?

What change to what algorithm?

 

[Ian Collins]

It's necessary for a free function which the example is.

Not for a function template or a regular function that only appears in
one compilation unit.

(Please recognize the expressive liberty taken with the term "algorithm".
I'm not afraid to let the context do most of the talking).

Templates cannot generate what the programmer would write:

return ((mask& 1ui64<< (n-1ui64)) != 0);

with the appropriate suffix for the different width unsigned integers.
But a macro can. (I know the suffixes aren't standard, but they probably
should be (I've yet to check if VC++ accepts "ULL", cuz I always use the
ones as shown above). Afterall, the committee standardizes common
practice).

You are using prefixes, not suffixes! Anyway, if you were using a macro
you would have to have a parameter for the suffix. In a template you
have the type and as Öö Tiib pointed out else-thread, you only need one
template parameter, which the compiler can deduce.

The standard suffixes are (from C99 6.4.4.1):

unsigned-suffix: one of u U
long-suffix: one of l L
long-long-suffix: one of ll LL

 

[Ian Collins]

Yes, as I wanted with the template (for lack of any other way), but
templates won't allow it.

Because they don't require it. The type is known.

I thought I had it down for awhile, but I
hadn't yet called any of the member functions of the template class so
the code genrator did not generate code for those member functions and
everything seemed "way-kewl", until I wrote the test and started calling
the functions and then the compiler complained. So, I can do what I
wanted to do with the macro but not with the template, and if I do it in
"super macro" style, it may be a better solution than jumping through
hoops with the template "deficiency" (TBD).

Hoops? What could be simpler than

template <typename T>
bool CheckBit( T mask, unsigned n)
{
assert( n < std::numeric_limits<T>::digits );

return (mask & (T(1) << (n-1)));
}

bool result = CheckBit( 42ull, 4 );

?

It's not worth pulling in the header for that. All I'm trying to do is
avoid code duplication for 4 classes, but templates are fighting me. It
can be done, of course, as shown above, it's just not elegant is all.

Pulling in a header? isn't that what they are there for?

 

[Öö Tiib]

Hoops?  What could be simpler than

template <typename T>
bool CheckBit( T mask, unsigned n)
{
   assert( n < std::numeric_limits<T>::digits );

   return (mask & (T(1) << (n-1)));

}

bool result = CheckBit( 42ull, 4 );

?

Depends how simple it has to be and what is allowed by coding policy.
For example getting rid of implicit T to bool conversion and
simplifying the part with 3 nested parentheses, also adding debug
check against "n == 0 defect":

template <typename T>
bool CheckBit( T mask, unsigned n)
{
assert( 1 <= n && n < std::numeric_limits<T>::digits );

T bit = T(1) << (n-1);
return (mask & bit) != 0;

}

bool result = CheckBit( 42ull, 4 );

 

[Öö Tiib]

Depends how simple it has to be and what is allowed by coding policy.
For example getting rid of implicit T to bool conversion and
simplifying the part with 3 nested parentheses, also adding debug
check against "n == 0 defect":

 template <typename T>
 bool CheckBit( T mask, unsigned n)
 {
    assert( 1 <= n && n < std::numeric_limits<T>::digits );

    T bit = T(1) << (n-1);
    return (mask & bit) != 0;

 }

 bool result = CheckBit( 42ull, 4 );

Uh, and still it wrongly asserts on the valid case "n ==
std::numeric_limits<T>::digits". Hard to get used to the MikeP's
unusual "counting bits from 1" habit.

 

[Öö Tiib]

And you introduced an explicit temporary: bit. Why no "inline"?

Compilers optimize such simple temporaries out without problems.
Actually i have seen how they optimize out whole instantiations of
objects of classes and calls to member functions. Otherwise lot of the
template magic would be inefficient.

Not inline since "inline" keyword is only a hint to compiler. Depends
on other options if it is reasonable to add or not. "CheckBit( 42ull,
4 )" is usually optimized into "true" by modern compilers.

 

[MikeP]

Compilers optimize such simple temporaries out without problems.
Actually i have seen how they optimize out whole instantiations of
objects of classes and calls to member functions. Otherwise lot of the
template magic would be inefficient.

Well, with my hesitance to use optimization switches, I'm a bit more
conscious of the like.

Not inline since "inline" keyword is only a hint to compiler.

Well why not hint it then! It serves as documentation of intent then too.
Surely something as simple as above would be inlined? (At least if
suffixes would work, it would be "simple"! Having to introduce C++isms to
get around it is, well, lame and could have an effect on optimization).
The more that this is discussed, the more the lack of being able to use
suffixes seems like a (greater) deficiency.

Depends
on other options if it is reasonable to add or not. "CheckBit( 42ull,
4 )" is usually optimized into "true" by modern compilers.

It won't be used like that though. The arg would be a reference to a
variable.

 

[Öö Tiib]

Well, with my hesitance to use optimization switches, I'm a bit more
conscious of the like.

Probably my English again. Code is simpler to read. In debug builds
you can check the value of bit. In production build it will be gone.
Win-win-win for me.

Well why not hint it then! It serves as documentation of intent then too.
Surely something as simple as above would be inlined? (At least if
suffixes would work, it would be "simple"! Having to introduce C++isms to
get around it is, well, lame and could have an effect on optimization).
The more that this is discussed, the more the lack of being able to use
suffixes seems like a (greater) deficiency.

Because of my working process. I start hinting inlining, register
usage, switching if and else blocks (to hint branch prediction) etc.
only when i have full product profiled with real data. Before that no
hints. I have to comment inline keyword usage with real performance
issue handled.

It won't be used like that though. The arg would be a reference to a
variable.

It was just given as example to show how compiler inlines it anyway as
it sees fit, so no keyword is needed.

 

[MikeP]

Probably my English again. Code is simpler to read. In debug builds
you can check the value of bit. In production build it will be gone.
Win-win-win for me.

I'd rather it just stayed the same across builds and do the premature
optimization manually (that way, no guessing or assuming necessary) if
possible for it's a pretty easy thing to grok.

Because of my working process. I start hinting inlining, register
usage, switching if and else blocks (to hint branch prediction) etc.
only when i have full product profiled with real data. Before that no
hints. I have to comment inline keyword usage with real performance
issue handled.

OK. It's not an issue for the topic at hand anyway.

It was just given as example to show how compiler inlines it anyway as
it sees fit, so no keyword is needed.

But if the arg is not an immediate value as you had, will it still
optimize it away?

 

[MikeP]

Why don't you just use

const T one(1);
return (((mask & one) << (n-one)) != 0);

Just realized, the above should be:

return ((mask & (one << (n-one))) != 0);

 

[MikeP]

Let us assume that the outline of CheckBit is set in stone as:

template <typename T>
inline bool CheckBit(T& mask, uint32 n) // n range is 1 through the
bit-width of T.
{
// error handling here.
// main part of func here.
}

For the main part of the function, the desired, but cannot be had, code
generation from the template is something LIKE (for the case where the
type of T is uint64):

return ((mask & (1ui64 << (n-1ui32))) != 0);

which is plain-as-day, easy to grok. I added parenthesis instead of
requiring knowledge of operator precedence rules and for clarity and
added the truth comparison also for clarity and to avoid an implicit
conversion to bool.

So far, we have the following possible alternatives:

A. return ((mask & ((T)1) << (n-((T)1))) != 0);

B. const T one(1);
return ((mask & (one << (n-one)) != 0);

C. return ((mask & ((T(1) << (n-1)) != 0);

D. T bit = T(1) << (n-1);
return ((mask & bit) != 0);

The expression on the right side of "<<" is a continual source of worry.

Are all the alternatives even correct across all platforms and compilers?
Have the alternatives been exhausted? If A thru D are correct, I think
each may have to be analyzed according to the implicit transformations
that occur in order to understand (and maybe even across compilers!). All
of this is brought about because the simple and elegant way cannot be had
in this scenario (using suffixes with templates). Dilemma: which to
choose? Some other?

 

[Öö Tiib]

But if the arg is not an immediate value as you had, will it still
optimize it away?

Generally yes, but it may depend on compiler. Tried with an int got
from std::cin, MSVC 9.0 for 32 bit x86 did replace CheckBit( x, 4 )
call (where x was in edx register) with:

shr edx,3
and dl,1

Further it used the dl as returned bool value.