C++ copy parts of 2D array to another 2D array, performance

Question

In my program, I have a function that is called thousands of times. The function has one argument, an array of bool values with length=30000. Based on this array of bools, I copy some of the rows from a global, 2d array variable to build a local 2d array. I then find the mean of each column in the local 2d array. I then take every value in the local 2d array and subtract it's column mean, in order to build a second local 2D array.

The program is executing as intended, but it is taking much too long since I added the function in question. Is there a faster way to take a subset of data from a 2d array and make a new 2d array? Is there a faster way to subtract the column mean from every value in a 2d array? Perhaps I should look into vectors or declaring things outside the function...

Thank you.

double FitValue(bool *X){
    int i,j,k; //loop index
    int counter;
    int numUsedVariables = 0; //
    double sum;
    //find number of selected variables
    for(i=0; i<NUMVARIABLES; i++){ //NUMVARIABLES is a globally defined variable
        if(X[i] == true){
            numUsedVariables += 1;
        }
    }   
    //declare matrix for variable subset    
    alglib::real_2d_array input;
    input.setlength(NUMINDIVS,numUsedVariables); 
    //populate matrix for variable subset
    counter = -1;
    for(i=0; i<NUMVARIABLES; i++){ //NUMVARIABLES is a globally defined variable
        if(X[i] == true){       
            counter++;
            for(j=0; j<NUMINDIVS; j++){ //NUMINDIVS is a globally defined variable      
                input[j][counter] = genotype[i][j]; //genotype is global variable
            }   
        }
    }
    //find the mean of each column
    alglib::real_1d_array colMeans;
    colMeans.setlength(numUsedVariables);
    for(i=0; i<numUsedVariables; i++){
        sum = 0;
        for(j=0; j<NUMINDIVS; j++){
            sum += input[j][i];     
        }   
        colMeans[i] = sum/NUMINDIVS;
    }   
    //declare centered selected markers matrix
    alglib::real_2d_array centeredInput;
    centeredInput.setlength(NUMINDIVS,numUsedVariables);    
    for(i=0; i<numUsedVariables; i++){   
        for(j=0; j<NUMINDIVS; j++){
            centeredInput[j][i] = input[j][i]   - colMeans[i];
        }
    }
    //perform further analysis ...
    //...

}   

Answer 1

Your code slows because the 2D arrays are accessed in a column-first order. Every time the CPU gets a number from main memory, a whole bunch of numbers are fetched into the cache. Remember, C/C++ stores array row-first, if the next number you need is on the next row, all the cached data is useless. CPU has to go back to main memory to fetch the next number. Going to main memory is a very slow process compared to access data already in the cache.
To make your code run faster, you need to think how to re-organize your data so that they are accessed in the most cache friendly way. This code
for(i=0; i<numUsedVariables; i++) for(j=0; j<NUMINDIVS; j++) centeredInput[j][i] = input[j][i] - colMeans[i]; will run much slower than
for(j=0; j<NUMINDIVS; j++) for(i=0; i<numUsedVariables; i++) centeredInput[j][i] = input[j][i] - colMeans[i];