Page 2 of 2
Re: To shift or not to shift
Posted: Tue Oct 06, 2015 1:52 pm
by H.G.Muller
thevinenator wrote:void BitmapTest()
{
U64 i,j,val;
U64 PowerOf2[64];
for (i = 0; i <= 63; i++)
PowerOf2 = (1ULL << i);
clock_t begin = clock();
for (j = 1; j < 1000000000; j++)
for (i = 0; i < 64; i++)
{
// try using shifts
val = 1ULL << i;
// try array
// val = PowerOf2;
}
printf("%llu\n", val); // needed to keep the optimizer from not doing the loops
}
If the compiler truly optimizes, this should always execute in zero time. At least, that is what such test attempts always do for me. With gcc -O2 the compiler is clever enough to see that the assignment to val is never used within the loop, and deletes the entire loop! It only generates the code for printf("%llu\n", 1ULL<<63);.
Btw, 1ULL<<i would normally be faster, if your shift unit is not overloaded. Note that i7 has only one shift unit, so it can be a bottleneck.
Re: To shift or not to shift
Posted: Tue Oct 06, 2015 7:55 pm
by hyatt
H.G.Muller wrote:thevinenator wrote:void BitmapTest()
{
U64 i,j,val;
U64 PowerOf2[64];
for (i = 0; i <= 63; i++)
PowerOf2 = (1ULL << i);
clock_t begin = clock();
for (j = 1; j < 1000000000; j++)
for (i = 0; i < 64; i++)
{
// try using shifts
val = 1ULL << i;
// try array
// val = PowerOf2;
}
printf("%llu\n", val); // needed to keep the optimizer from not doing the loops
}
If the compiler truly optimizes, this should always execute in zero time. At least, that is what such test attempts always do for me. With gcc -O2 the compiler is clever enough to see that the assignment to val is never used within the loop, and deletes the entire loop! It only generates the code for printf("%llu\n", 1ULL<<63);.
Btw, 1ULL<<i would normally be faster, if your shift unit is not overloaded. Note that i7 has only one shift unit, so it can be a bottleneck.
I had told him to look at the asm output (gcc -s). His loop is gone. All that is left is the loop with the print, since a function call prevents optimizing the loop away unless the function can be inlined and it also does nothing...
Re: To shift or not to shift
Posted: Wed Oct 07, 2015 9:56 am
by H.G.Muller
Indeed. And even if not (i.e. when compiled without any optimalization) the execution time should be completely dominated by the printf. His program prints a billion lines. How much time would it take to print one line (and scroll the window) compared to doing 64 shifts or loads...?
Re: To shift or not to shift
Posted: Mon Oct 26, 2015 2:30 pm
by MathAddict
On a side note, are addition and multiplication operators faster than array lookups?
Re: To shift or not to shift
Posted: Wed Oct 28, 2015 2:39 am
by hyatt
Impossible to answer. If the table lookup comes from L1, no. If it comes from L2 it might be a tossup for multiply but add will be faster. If it comes from L3 or even main memory most anything is faster...