Что быстрее? Обращение к элементу массива или к элементу структуры?

@kozlik_kozlik · Регистрация: 01.08.2012

Студворк — интернет-сервис помощи студентам

Обращение к элементу массива или к элементу структуры?
Экспериментирую с кодом и получается примерно одинаково. Что интересно, время на вызов функции do_nothing получилось примерно такое же. Оптимизация отключена.

Верен ли вывод, что обращение к элементу массива, элементу структуры и вызов функции занимают одинаковое время?

Использую MinGW 4.4 с Qt 4.7.4.

C++ (Qt)

#include <iostream>
#include <ctime>
 
using namespace std;
 
struct st
{
    int a, b;
    int c;
};
 
void do_nothing() {}
 
int main()
{
    int x[10]={0};
    st s;
    s.a=5; s.b=4; s.c=12;
 
    int y=0;
 
    int t0=clock();
 
    for (int i=0; i<=100000000; i++)
    {
        //y=x[5];
        y=s.c;
        //do_nothing();
    }
 
    int t1=clock();
 
    cout << "ticks=" << t1-t0 << "\t" << endl;
 
    cout << "Hello World!" << endl;
    return 0;
}

Croessmah · 14.07.2015, 23:08

Сообщение от kozlik_kozlik

Использую MinGW 4.4

опции компилятора какие?
Вот то, что получилось из Вашего цикла при O3:

Assembler

1
2
3

    call    clock
    movq    %rax, %rbp
    call    clock

Как видите, цикл просто вырезали.

Evg · 14.07.2015, 23:15

Сообщение от kozlik_kozlik

Обращение к элементу массива или к элементу структуры?

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

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

@kozlik_kozlik · 14.07.2015, 23:16 **[ТС]**

опции компилятора какие?

O0

Код по проведению эксперимента, очевидно, неправильный

Чем?

Evg · 14.07.2015, 23:19

Да и сам код для замеров нужно правильно строить. При том коде, который написан, условные 70% (хз сколько в точности, может и больше) будут занимать накладные расходы по организации цикла, и только оставшиеся условные 30% - сам полезный код, который хочется замерить

Добавлено через 56 секунд

Сообщение от kozlik_kozlik

Чем?

Выше написано. В посте #2 показано, что будет при работе оптимизаций. В посте #3 написано, что ты вообще замеришь без оптимизаций. Как минимум этих двух пунктов достаточно

@kozlik_kozlik · 14.07.2015, 23:24 **[ТС]**

При том коде, который написан, условные 70% (хз сколько в точности, может и больше) будут занимать накладные расходы по организации цикла, и только оставшиеся условные 30% - сам полезный код, который хочется замерить

Большая разница будет видна.

Как организовать код, чтобы в замер попало больше времени в % от полезного кода?

В посте #3 написано, что ты вообще замеришь без оптимизаций

Мне важно посмотреть именно без оптимизаций.

Evg · 15.07.2015, 09:30

Сообщение от kozlik_kozlik

Как организовать код, чтобы в замер попало больше времени в % от полезного кода?

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

Сообщение от kozlik_kozlik

Мне важно посмотреть именно без оптимизаций

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

Croessmah · 15.07.2015, 09:46

Да и вызов функции понятие достаточно толстое.
С одной стороны - это просто "прыжок" в коде, но ведь к данному прыжку нужно подготовиться. Положить что куда нужно, сохранить что нужно. А назад мы придем только когда фукция завершится, а это опять "пыжок", "укладка", восстановление. Всё это накладные расходы, которые прибавятся к расходам на сам вызов (прыжок).

Добавлено через 6 минут
Evg, 70% на 30%? Так здесь в эти 30% еще и присваивание войдет, так что можно снижать минимум вдвое.

Evg · 15.07.2015, 11:43

Сообщение от Croessmah

Evg, 70% на 30%? Так здесь в эти 30% еще и присваивание войдет, так что можно снижать минимум вдвое

Для присваивания как такового отдельной операции нет. Есть load, который одновременно читает из памяти и пишет в регистр. Т.е. он сразу же делает и присваивание. В своей оценке я исходил из того, что счётчик цикла и переменная y (которая там нафиг не нужна) располагаются на регистрах, а массив или структура - в памяти. Обращение в память - длинная операция с точки зрения процессора, а потому она имеет бОльший вес, чем какая-либо другая арифметическая операция из обслуживающего цикла. Переход назад в длинном цикле будет работать быстро (т.к. предсказатель переходов на intele очень быстро настроится)

Croessmah · 15.07.2015, 12:10

Evg, ну лично у меня, с -O0, вылилось в

Assembler

1 2	movl -44(%ebp), %eax movl %eax, -32(%ebp)

По сути, нас интересует только первая операция, вторая - это уже пихание результата в y

Evg · 15.07.2015, 13:21

Сообщение от Croessmah

Evg, ну лично у меня, с -O0, вылилось в

Потому что "y" распределился в стеке, а не на регистре. Кстати, наглядная демонстрация того, что тест меряет не то, что надо

Добавлено через 33 секунды
Точнее, не тест, а его запуск в режиме без оптимизаций

@VD · 16.07.2015, 21:37

Обращение к массиву:
y=x[5];

Assembler

    mov eax, 4
    imul    ecx, eax, 5
    mov edx, DWORD PTR _x$[ebp+ecx]
    mov DWORD PTR _y$[ebp], edx

Обращение к структуре:
y = s.c;

Assembler

1 2	mov eax, DWORD PTR _s$[ebp+8] mov DWORD PTR _y$[ebp], eax

Вот так генерирует VS2013.
Из чего вроде как бы следует что обращение к структуре быстрее.

@Renji · 16.07.2015, 21:46

Сообщение от VD

Вот так генерирует VS2013.

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

@VD · 16.07.2015, 21:53

Renji, у точно и правда можно выкинуть. И зачем же компилятор так делает...

Evg · 16.07.2015, 21:54

Сообщение от VD

И зачем же компилятор так делает

Потому что оптимизации не включены

@VD · 16.07.2015, 21:59

А почему он генерирует именно так а не иначе, без включенных оптимизаций?

@Renji · 16.07.2015, 22:42

Сообщение от VD

А почему он генерирует именно так а не иначе, без включенных оптимизаций?

Потому что считает адрес элемента по формуле адрес массива+индекс элемента*размер элемента. А упрощать эту формулу, это уже считается за оптимизацию.

@Renji 2765 / 1919 / 569 Регистрация: 05.06.2014 Сообщений: 5,576
	16.07.2015, 22:42	17
	Сообщение от VD А почему он генерирует именно так а не иначе, без включенных оптимизаций? Потому что считает адрес элемента по формуле адрес массива+индекс элемента*размер элемента. А упрощать эту формулу, это уже считается за оптимизацию. 0

Evg 21274 / 8291 / 637 Регистрация: 30.03.2009 Сообщений: 22,654 Записей в блоге: 30
	14.07.2015, 23:15	3
	Сообщение от kozlik_kozlik Обращение к элементу массива или к элементу структуры? В общем случае одинаково при условии, что обращение к элементу массива делается с константными индексами. В обоих случаях читается значение из "адрес объекта плюс константное смещение". В частном случае нужно учитывать, что для некоторых машин начинает играть роль конкретное значение смещения из-за того, что короткие литералы (константы) можно закодировать прямо в операции, а длинные константы требуют пересылки на регистр. Т.е. при сравнении нужно проверять, чтобы обращение было по одинаковому байтовому смещению Код по проведению эксперимента, очевидно, неправильный. Да и эксперименты нужно проводить в режиме с оптимизациями, потому что в режиме без оптимизации ты будешь замерять особенности работы компилятора, а вовсе не полученный код 0

@kozlik_kozlik 7 / 11 / 0 Регистрация: 01.08.2012 Сообщений: 99
	14.07.2015, 23:16 [ТС]	4
	опции компилятора какие? O0 Код по проведению эксперимента, очевидно, неправильный Чем? 0

Evg 21274 / 8291 / 637 Регистрация: 30.03.2009 Сообщений: 22,654 Записей в блоге: 30
	14.07.2015, 23:19	5
	Да и сам код для замеров нужно правильно строить. При том коде, который написан, условные 70% (хз сколько в точности, может и больше) будут занимать накладные расходы по организации цикла, и только оставшиеся условные 30% - сам полезный код, который хочется замерить Добавлено через 56 секунд Сообщение от kozlik_kozlik Чем? Выше написано. В посте #2 показано, что будет при работе оптимизаций. В посте #3 написано, что ты вообще замеришь без оптимизаций. Как минимум этих двух пунктов достаточно 0

@kozlik_kozlik 7 / 11 / 0 Регистрация: 01.08.2012 Сообщений: 99
	14.07.2015, 23:24 [ТС]	6
	При том коде, который написан, условные 70% (хз сколько в точности, может и больше) будут занимать накладные расходы по организации цикла, и только оставшиеся условные 30% - сам полезный код, который хочется замерить Большая разница будет видна. Как организовать код, чтобы в замер попало больше времени в % от полезного кода? В посте #3 написано, что ты вообще замеришь без оптимизаций Мне важно посмотреть именно без оптимизаций. 0

Evg 21274 / 8291 / 637 Регистрация: 30.03.2009 Сообщений: 22,654 Записей в блоге: 30
	15.07.2015, 09:30	7
	Сообщение от kozlik_kozlik Как организовать код, чтобы в замер попало больше времени в % от полезного кода? Например, внутри цикла 10 раз повторить интересующую тебя операцию. Ну а в реальной жизни никто не занимается такими вещами, как измерение скорости работы одной операции языка. Для этого всегда можно посмотреть код и почитать систему команд Сообщение от kozlik_kozlik Мне важно посмотреть именно без оптимизаций Да смотри ради бога. Но понимай при этом, что ты измеряешь попугаев, а не скорость кода 0

Croessmah Неэпический 17848 / 10616 / 2049 Регистрация: 27.09.2012 Сообщений: 26,686 Записей в блоге: 1
	15.07.2015, 09:46	8
	Да и вызов функции понятие достаточно толстое. С одной стороны - это просто "прыжок" в коде, но ведь к данному прыжку нужно подготовиться. Положить что куда нужно, сохранить что нужно. А назад мы придем только когда фукция завершится, а это опять "пыжок", "укладка", восстановление. Всё это накладные расходы, которые прибавятся к расходам на сам вызов (прыжок). Добавлено через 6 минут Evg, 70% на 30%? Так здесь в эти 30% еще и присваивание войдет, так что можно снижать минимум вдвое. 0

Evg 21274 / 8291 / 637 Регистрация: 30.03.2009 Сообщений: 22,654 Записей в блоге: 30
	15.07.2015, 11:43	9
	Сообщение от Croessmah Evg, 70% на 30%? Так здесь в эти 30% еще и присваивание войдет, так что можно снижать минимум вдвое Для присваивания как такового отдельной операции нет. Есть load, который одновременно читает из памяти и пишет в регистр. Т.е. он сразу же делает и присваивание. В своей оценке я исходил из того, что счётчик цикла и переменная y (которая там нафиг не нужна) располагаются на регистрах, а массив или структура - в памяти. Обращение в память - длинная операция с точки зрения процессора, а потому она имеет бОльший вес, чем какая-либо другая арифметическая операция из обслуживающего цикла. Переход назад в длинном цикле будет работать быстро (т.к. предсказатель переходов на intele очень быстро настроится) 1

Evg 21274 / 8291 / 637 Регистрация: 30.03.2009 Сообщений: 22,654 Записей в блоге: 30
	15.07.2015, 13:21	11
	Сообщение от Croessmah Evg, ну лично у меня, с -O0, вылилось в Потому что "y" распределился в стеке, а не на регистре. Кстати, наглядная демонстрация того, что тест меряет не то, что надо Добавлено через 33 секунды Точнее, не тест, а его запуск в режиме без оптимизаций 1

@Renji 2765 / 1919 / 569 Регистрация: 05.06.2014 Сообщений: 5,576
	16.07.2015, 21:46	13
	Сообщение от VD Вот так генерирует VS2013. Плохо генерирует. В вашем коде imul умножает четыре на пять. То есть, константу на константу. Результат такого умножения можно посчитать на стадии компиляции, а imul выкинуть за ненадобностью. А вот если индекс элемента массива заранее неизвестен, тогда да, обращение к элементу будет медленнее обращения к элементу структуры. 0

@VD 24 / 13 / 3 Регистрация: 02.08.2012 Сообщений: 160
	16.07.2015, 21:53	14
	Renji, у точно и правда можно выкинуть. И зачем же компилятор так делает... 0

Evg 21274 / 8291 / 637 Регистрация: 30.03.2009 Сообщений: 22,654 Записей в блоге: 30
	16.07.2015, 21:54	15
	Сообщение от VD И зачем же компилятор так делает Потому что оптимизации не включены 0

@VD 24 / 13 / 3 Регистрация: 02.08.2012 Сообщений: 160
	16.07.2015, 21:59	16
	А почему он генерирует именно так а не иначе, без включенных оптимизаций? 0