4

I don't know what overhead there is in int array lookups. Which would perform better (in C#):

a = aLookup[i];
b = (a % 6) == 5;
c = (b ? a+1 : a-1) >> 1;  // (a + 1) / 2 or (a - 1) / 2

Or

a = aLookup[i];
b = bLookup[i];
c = cLookup[i];

Would an array lookup actually save that much time for either b or c?

Edit: I profiled it several ways. The result is that array lookups are almost four times faster.

jnm2
  • 7,960
  • 5
  • 61
  • 99
  • 1
    I don't think this will be your bottleneck either way, go with what's more readable – BrokenGlass Jun 14 '11 at 14:00
  • 6
    I am mystified as to why people ask questions like this. You've written the code both ways. Try it yourself and then you'll know which is faster, and then you can tell us. No one here can tell you which of two things is faster without trying it; there's no magic way to know "well, this takes 100 nanoseconds on your server hardware but this over here causes a bad line cache miss in 10% of cases, so that slows it down..." You just have to try it and find out. – Eric Lippert Jun 14 '11 at 14:02
  • Neither will make that big of a difference. I would suggest trying to optimize your code elsewhere. – Patrick Jun 14 '11 at 14:02
  • Regardless, this is for a CPU intensive task. The array stores all the primes under 32768 and the program would need to recalculate b and c for each prime. The whole loop may get run many times, recalculating each time. I just want to know, especially for other projects, how array speed compares to simple operations like this. – jnm2 Jun 14 '11 at 14:04
  • 1
    @Eric Lippert everyone haven't been in the industry long enough to know what is right, wrong or obvious. People take time to learn things. You will not see questions like this coming from Jon Skeet but only from newbies. Its quite possible he doesn't know how to analyze performance either. – Muhammad Hasan Khan Jun 14 '11 at 14:07
  • @jnm2: If that is the use case (4*3278 ints = 1MB) just precalculate the full tables and read it in as a blob (or memory map it from a resource... )) -- _oh and write the generator in C++ using Blitz and optimize it to death! (oh wait, this is one-time :))_ – sehe Jun 14 '11 at 14:09
  • @Eric: You're right, it's a dumb question. I do know how to analyze this, but I was expecting an easy answer. I'll take the collective advice and profile it. – jnm2 Jun 14 '11 at 14:11
  • 1
    @jnm2: You'll know when you try it. Remember, C# is a jit-compiled language; no one here knows when the jitter on your machine is going to decide that it can deduce that the array bounds check can be safely optimized away, for example. There are many different ways to generate code and data locality and therefore cache misses can play a big part in perf-sensitive algorithms. I would be using a profiler and letting that direct my efforts. – Eric Lippert Jun 14 '11 at 14:12

4 Answers4

3

It is so extremely unlikely to matter. You should go with what is most readable. And I can tell you that 

c = (b ? a+1 : a-1) >> 1;

is pointless as you aren't buying any performance but your code is less readable. Just go with explicitly dividing by two.

That said, just try it for yourself in a profiler if you really care.

jason
  • 236,483
  • 35
  • 423
  • 525
1

Both are O(1) conceptually, although you have an out of bounds check with the array access.

I don't think this will be your bottleneck either way, I would go with what's more readable and shows your intend better.

BrokenGlass
  • 158,293
  • 28
  • 286
  • 335
1

A:

  • depends on
    • element type
    • length of array
    • cache locality
      • processor affinity, L2 cache size
    • cache duration (or more importantly: how many times used till cache eviction?)

B:

Community
  • 1
  • 1
sehe
  • 374,641
  • 47
  • 450
  • 633
  • It depends on a lot more than this. Different jitters will exhibit different performance characteristics. New jitters for the same platform will exhibit different performance characteristics. Etc. – jason Jun 14 '11 at 18:52
  • Yup. I was only getting started :) Also, assuming a perfect JIT job, it will _always_ depend in (much) more elemental fashion on the things I listed (consider when the element is a reftype, or a very large valuetype...; consider when the function is actually called once in 10 iterations with scattered accesses to another large array; no JIT is going to be able to 'solve' the usage pattern impact). It's back to the basic rule: no use optimizing if you didn't select the right algorithm – sehe Jun 14 '11 at 21:39
0

also if you use reflector to check the implemention of the % operator you will find it is extremely inefficient and not to be used in a time-critical application in high frequency code so csharp game programmers tend to avoid % and use:

while (x >= n) x -= n;

but they can make assumptions about the range of x (which are verified in debug builds) unless you are doing 10,000+ of these per second I wouldn't worry about it

Jack
  • 4,684
  • 2
  • 29
  • 22