0

I am mainly interested in C# but general answers are welcome too.

Would it take longer to iterate over an array of longs compared to ints? I imagine that the larger value types take up more memory so a contiguous array is obviously longer. But is the hop from Array[0] to Array[1] any different if that gap is 8, 16 or 32 bytes etc?

If it is, would a large struct type (because its by value) take even longer?

Or is traversing an array kinda just memory pointer to memory pointer and the gaps/location of the next item not really relevant?

lozzajp
  • 916
  • 7
  • 15
  • 2
    Why would you traverse an array without doing anything with the elements? And if you are doing something with the elements, why do you assume that wouldn't be what has more impact? And more importantly, why don't you just [race the horses yourself](https://ericlippert.com/2012/12/17/performance-rant/)? – Jeroen Mostert Sep 28 '16 at 10:50
  • If you don't read the elements then it doesn't matter (but then why do it?), if you're reading them, obviously reading more memory takes more time. – harold Sep 28 '16 at 10:58

1 Answers1

2

An Array is basically of following structure:

  • an initial memory pointer
  • a value of its length
  • reserved memory from the intial memory pointer + sizeof(type) * length

With these three informations it's trivial to point to the exact location of any value:

memory pointer + sizeof(type) * element where 0 <= element < length

When accessing a distinct value in an array the compiler will translate it to perform such a calculation and load the value at the given position (here: in primitives). There are no gaps inbetween, because the very definition of it makes the O(1) possible (and neccessary).

Mio Bambino
  • 544
  • 3
  • 15
  • In real computers, memory accesses are not O(1) but a growing function of N because of memory hierarchy. This is not a marginal effect. –  Sep 28 '16 at 13:01