- It'sit's a small table and is likely to be cached in the processor, and
- Youyou are running things in a quite tight loop and/or the processor can pre-loadpreload the data.
Background and why
Pfew, so what the hell is that supposed to mean?
From a processor perspective, your memory is slow. To compensate for the difference in speed, they build in a couple of caches inare built into your processor (L1/L2 cache) that compensate for that. So imagine that you're doing your nice calculations and figure out that you need a piece of memory. The processor will get its 'load' operation and loads the piece of memory into cache -- and then uses the cache to do the rest of the calculations. Because memory is relatively slow, this 'load' will slow down your program.
for (int i=0; i<array.Length; ++i)
// Use array[i]
for (int i = 0; i < array.Length; ++i)
{
// Use array[i]
}
In this case, it's obvious to the compiler that the boundary condition will never be hit. At least the Microsoft JIT compiler (but I expect Java does similar things) will notice this and remove the check altogether. WOW -, that means no branch. Similarly, it will deal with other obvious cases.
If you run into trouble with lookups onin managed languages -- the key is to add a & 0x[something]FFF
to your lookup function to make the boundary check predictable -- and watch it going faster.
// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];
Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
data[c] = random.Next(256);
}
/*To keep the spirit of the code in-tact I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/
int[] lookup = new int[256];
for (int c = 0; c < 256; ++c)
lookup[c] = (c >= 128) ? c : 0;
// Test
DateTime startTime = System.DateTime.Now();
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
// Primary loop
for (int j = 0; j < arraySize; ++j)
{
/* Here you basically want to use simple operations - so no
random branches, but things like &, |, *, -, +, etc. are fine. */
sum += lookup[data[j]];
}
}
DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();
// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];
Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
data[c] = random.Next(256);
}
/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/
int[] lookup = new int[256];
for (int c = 0; c < 256; ++c)
{
lookup[c] = (c >= 128) ? c : 0;
}
// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
// Primary loop
for (int j = 0; j < arraySize; ++j)
{
/* Here you basically want to use simple operations - so no
random branches, but things like &, |, *, -, +, etc. are fine. */
sum += lookup[data[j]];
}
}
DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();