Array VS Pointers

Question

У меня есть класс, который выглядит примерно так:

class node{// case 1
    float points[maxCap][d];
    ...
}

Я также могу сделать это следующим образом:

class node{// case 2
    float** points;

    node(){
        points = (float**)malloc(maxCap*sizeof(float*));
        if(points)
            for(int i=0; i<maxCapacity; i++)
                points[i] = (float*)malloc(d*sizeof(float));
        else{
            cout<<"Unable to get memory"<<endl;
            exit(1);
        }
    }
    ...
}

Они в основном являются узлами в дереве. Я создаю приблизительно от 500 000 до 1 000 000 из них.

Когда я ищу точку, причем каждая вещь в алгоритме поиска одинакова, случай 2 получается примерно 0,2 секунд медленнее, чем в случае 1 (в среднем за 3 прогона - хотя время более или менее одинаково для всех 3 прогонов). Время для случая 1 составляет приблизительно 0.88s, а для случая 2 - приблизительно 1.07s. Может кто-нибудь сказать мне, что здесь происходит? Разве это не должно быть примерно таким же?

Answer 1

К сожалению, вы не предоставили код, который выполняет фактический поиск. Но, предполагая, что для поиска действительно необходим доступ к данным внутри / за points, проблема ясна:

• С массивом данные сохраняются прямо в node объект, и арифметика простого указателя c выполняется для определения местоположения points[a][b]. Только один доступ к памяти необходим для фактического извлечения значения из памяти.

• При подходе с указателем узел содержит только адрес, где находится массив адресов хранится. Таким образом, points загружает значение указателя из памяти, points[a] загружает второе значение указателя из памяти, и points[a][b] наконец загружает фактическое значение в CPU, готовый для сравнения. Это три обращения к памяти, при которых в случае массива достаточно одного.

Даже если ваш кэш и предварительная выборка хорошо справляются с задачей уменьшения влияния дополнительной памяти доступы, один доступ к памяти легко превосходит три.

Answer 2

Рассмотрим points[1][2].

Указатели, за которыми следует float** points; вдвое больше, чем float points[10][3];.

В качестве эскиза это:

float* inner = *(points + 1);
float result = *(inner + 2);

В отличие от

float result = *(points + (3 * 2) + (1));