Насколько дорого обходить указатель?

Question

Сколько стоит операция разыменования для указателя?

Я могу представить, что передача памяти каким-то образом пропорциональна размеру объекта, но я хочу знать, насколько дорогая часть операции разыменования.

Answer 1

Разыменование при переводе в машинный код может означать разные вещи в зависимости от того, что вы делаете с разыменованным объектом. Доступ к одному члену класса с помощью указателя обычно дешев. Например, если c является указателем на экземпляр class C с int членом n, тогда что-то вроде этого:

int n = c->n;

Может переводиться в одну или две машинные инструкции и может загружать регистр с одним доступом к памяти.

С другой стороны, это подразумевает создание полной копии объекта, на который указывает c:

C d = *c;

Стоимость этого будет зависеть от размера C, но обратите внимание, что именно копия является основным расходом, и часть 'разыменования' на самом деле просто 'использует' адрес указателя в инструкциях по копированию.

Обратите внимание, что для доступа к элементам больших объектов обычно требуется вычисление смещения указателя и доступ к памяти независимо от того, является ли объект локальным или нет. Обычно только очень маленькие объекты оптимизированы для использования только в регистрах.

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

Answer 2

Это зависит от того, что вы делаете с разыменованным указателем. Сама операция разыменования ничего не делает сама по себе. Он просто получает значение типа T, представляющее ваш объект, если указатель имеет значение T*

struct a {
    int big[42];
};

void f(a * t) {
    // does nothing. Only interesting for standard or compiler writers.
    // it just binds the lvalue to a reference t1. 
    a & t1 = *t; 
}

Если вы на самом деле получаете значение из этого объекта, обозначенного lvalue, возвращаемым операцией разыменования, компилятор должен скопировать данные, которые содержит объект. Для простого POD это просто memcpy:

a aGlobalA;
void f(a * t) {
    // gets the value of of the object denoted by *t, copying it into aGlobalA
    aGlobalA = *t; 
}

Мой порт gcc выводит этот код для f:

    sub     $29, $29, 24       ; subtract stack-pointer, creating this frame
    stw     $31, $29, 20       ; save return address
    add     $5, $0, $4         ; copy pointer t into $5 (src)
    add     $4, $0, aGlobalA   ; load address of aGlobalA into $4 (dst)
    add     $6, $0, 168        ; put size (168 bytes) as 3rd argument
    jal     memcpy             ; call memcpy
    ldw     $31, $29, 20       ; restore return address
    add     $29, $29, 24       ; add stack-pointer, destroying this frame
    jr      $31

Оптимизированный машинный код будет использовать встроенный код вместо вызова memcpy, но это на самом деле просто деталь реализации. Важно то, что просто *t не выполняет какой-либо код, но для доступа к значению этого объекта на самом деле нужно его скопировать.

Если бы мы имели дело с типом, имеющим пользовательский оператор назначения копирования, дела более сложны:

struct a {
    int big[42];
    void operator=(a const&) { }
};

Код для той же функции f теперь выглядит так:

    sub     $29, $29, 8
    add     $29, $29, 8
    jr      $31

Хах. Но это не было таким сюрпризом, не так ли? В конце концов, компилятор должен вызывать наш operator=, и если он ничего не делает, вся функция также ничего не делает!

Заключение

Я думаю, что мы можем сделать вывод, все зависит от того, как используется возвращенное значение operator*. Если у нас есть только указатель, на который мы обращаемся, мы видим выше, что сгенерированный код во многом зависит от обстоятельств. Я не показал, как он ведет себя, если мы разыменовываем тип класса, перегруженный operator*. Но по сути, он просто ведет себя так, как мы видели с operator=. Все измерения были выполнены с -O2, поэтому компилятор правильно указывает:)

Answer 3

Самый важный фактор разыменования указателей в обычных системах - это вероятность того, что вы потеряете кеш. Произвольный доступ в памяти SDRAM стоит десятки наносекунд (например, 64). На гигагерцовых процессорах это означает, что ваш процессор бездействует сотни (или> тысяча) циклов, не имея в то же время возможности делать что-либо еще.

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

Answer 4

Разыменование может быть дорогостоящим, в основном потому, что оно требует инструкции для извлечения данных из памяти, которая может быть далеко и не демонстрирует локальность ссылки. В этом случае процессор должен извлекать данные из не кэшированной памяти и даже с жесткого диска (в случае сбоя жесткого диска).

Answer 5

Разыменование (множественная) стоимость циклов ЦП.

Вместо записи:

string name = first->next->next->next->name;
int age = first->next->next->next->age;

this is O(n)

Напишите это как:

node* billy_block = first->next->next->next;

string name = billy_block->name;
int age = billy_block->age;

this is O(1)

Таким образом, ваш код не будет «запрашивать» каждый блок только для того, чтобы добраться до четвертого блока.

Множественная разыменование - это как соседство, которое знает только соседа рядом с ним.

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

Answer 6

Разыменование указателя не должно быть намного больше, чем копирование адреса в (адресный) регистр. Вот и все.