Is calculating the index in an array more efficient than letting the compiler do it?

Question

I'm trying to generalize a neural network function to arbitrarily many layers, and so I need multiple matrices to hold the weights for each neuron in each layer. I was originally explicitly declaring matrix objects in R to hold my weights for each layer. Instead of having one matrix per layer, I thought of a way (not saying it's original), to store all of my weights in a single array and defined an "indexing function" to map a weight to its appropriate index in the array.

I defined the function as follows:

where is the k-th weight of the j-th neuron in the i-th layer and L(r) is the number of neurons in layer r. After writing these definitions, I realize that stackoverflow doesn't allow latex like mathoverflow which is unfortunate. Now the question is: Is it more efficient to compute the index of my weights in this way, or is actually less efficient? After looking up how indices are computed for arrays in general, this is essentially what is done on compilation anyway if I just kept a matrix in each layer holding the weights, so it seems like I may just be making my code overly complicated and harder to understand if there's no difference in time efficiency.

Answer 1

There are many factors to take into consideration in each of the approaches. I'm not familiar with R but I'm assuming matrices' buffers are represented as one-dimensional arrays in memory. (Even if they are written as two dimensional arrays in the underlying C implementation the compiler stores it as one-dimensional array in memory)

The overall outline of memory operations are:

1. Case: Several matrices per layers

   • Allocation of matrices:
   • Accessing of indices:

2. Case: One matrix for all layers + index calculation

   • Allocation of matrix cost:
   • Accesing each of the indices cost:
   • Function cost:

We can clearly see that the second case, scales better, even though there's the additional cost of the function call.

Having said that, in general having a statically allocated array with all the weights for all the layers, should be faster.

In most cases, computers's bottleneck is memory bandwidth, and the best way to counteract this is to minimize the number of memory accesses.

With this in mind there's another more primitive reason why the 2nd approach will probably be faster: Caches.

Here's a good explanation of the performance difference in accesing a two-dimensional array in a loop by Good Ol' Bob Martin

TL; DR: Caches take advantage of the principle of locality, and therefore, having memory accesses spatially close to each other (as you would in one single array and accessing them in a cache-friendly way as explained in Bob Martin's answer) renders better performance than having them spatially separated (having them in several distinct arrays).

PS: I also recommend to benchmark both approaches and compare, since these nuances regarding the cache are machine-dependent. It might be the case that the Dataset/NN is small enough to fit completely in RAM or even in cache? in a very powerful server.