Время доступа к элементам вектора.

@PhotonDT · Регистрация: 11.05.2012

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

Суть проблемы в том, что я не могу объяснить такое расхождение во времени доступа к элементам динамического, статического массивов и вектора. Время доступа к элементам вектора больше, чем больше размерность. К одномерному в среднем на 50-100мс(1000000 элементов). К двумерному в среднем на 200мс.(1000x1000). К трехмерному (100х100х100) в среднем на 250мс.(это разница во времени между доступом к статич. и динамич. массивам и вектору) При этом учитывая, что скорость доступа к эл.статич. и динамич. массивов примерно равны.
Вот код, который я использовал для трехмерных структур:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<fstream>
#include<vector>
#include<time.h>
#pragma comment(linker, "/STACK:1000000000")
#define forn(i,n) for(int i=0;i<n;i++)
const int n=100;
using namespace std;
int main()
{
    setlocale(LC_ALL,"Russian");
    fstream f,g;
    f.open("out.txt",fstream::out);
    g.open("time.txt",fstream::app);
    clock_t clock();
    int aT1,aT2,dT1,dT2,vT1,vT2,x;
    vector<vector<vector<int>>> v(n,vector<vector<int>>(n,n));
    int aa[n][n][n];
    int ***dda=new int**[n];
    forn(i,n)
        dda[i]=new int*[n];
    forn(i,n)
        forn(p,n)
        dda[i][p]=new int[n];
    forn(i,n)
        forn(p,n)
            forn(j,n)
    {
        x=rand()%100+1;
        aa[i][p][j]=x;
        dda[i][p][j]=x;
        v[i][p][j]=x;
    }
    aT1=clock();
    forn(i,n)
        forn(p,n)
            forn(j,n)
        f<<aa[i][p][j];
    aT2=clock();
    dT1=clock();
    forn(i,n)
        forn(p,n)
            forn(j,n)
        f<<dda[i][p][j];
    dT2=clock();
    forn(i,n)
        delete[]dda[i];
    delete[]dda;
    vT1=clock();
    forn(i,n)
        forn(p,n)
            forn(j,n)
        f<<v[i][p][j];
    vT2=clock();
    g<<aT2-aT1<<endl;
    g<<dT2-dT1<<endl;
    g<<vT2-vT1;
    g.close();
    g.open("time.txt",fstream::in);
    int k1=0,k2=0,k3=0;
    float t1=0,t2=0,t3=0;
    while(!g.eof())
    {
        g>>x;
        t1+=x;
        k1++;
        g>>x;
        t2+=x;
        k2++;
        g>>x;
        t3+=x;
        k3++;
    }
    g.close();
    g.open("time.txt",fstream::app);
    g<<endl;
    t1/=k1;
    t2/=k2;
    t3/=k3;
    cout<<aT2-aT1<<" это последнее приблизительное время доступа к элементам двумерного статического массива"<<endl;
    cout<<dT2-dT1<<" это последнее приблизительное время доступа к элементам двумерного динамического массива"<<endl;
    cout<<vT2-vT1<<" это последнее приблизительное время доступа к элементам двумерного вектора"<<endl<<endl;
    cout<<t1<<" это среднее время доступа к элементам статического массива"<<endl;
    cout<<t2<<" это среднее время доступа к элементам динамического массива"<<endl;
    cout<<t3<<" это среднее время доступа к элементам вектора"<<endl;
    system("PAUSE");
    return 0;
}

Кто знает чем это объясняется, напишите пожалуйста.

@Avazart · 14.05.2012, 23:49

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

В коде я не чего не понял и нехочу, так как там сильно награмаждено.

@Toshkarik · 14.05.2012, 23:59

Согласен. Код не смотрел, но могу предположить, что вы накапливаете время доступа. У вектора безусловно скорость доступа к элементу ниже чем у простого массива, но как и сказали выше, она никак не должна зависеть от размера.

@diagon · 15.05.2012, 08:27

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

У вектора безусловно скорость доступа к элементу ниже чем у простого массива

Ну почемууу?
Если опускаться до совсем низкого уровня, то массивы - это всего лишь абстракция, на самом деле есть только непрерывный кусок памяти и указатель на его начало.
Во всех трех случаях мы имеем указатель на первый элемент. Затем мы добавляем к этому указателю i * sizeof(...), чтобы получить адрес i-того элемента.
Затем мы просто считываем значение из этого адреса.

Грубо говоря, все 3 случая эквивалентны этому.

C++
1
2
int *arr; //указатель на начало массива
*(arr + i);//получаем i-тый элемент.

@Toshkarik · 15.05.2012, 08:39

Ну так везде и пишут, да и логично это. Вектор - шаблонный класс. При доступе к элементу вызывается функция перегрузки оператора. Всегда почему то верил людям и источникам, где это было написано, так как повода сомневаться в их компетентности не было. Везде писали, включая и этот форум, причем кто то из здешних, так сказать, профи - если важна скорость доступа - используйте массивы Си. Вектор же более удобен и высокоуровен. Если Вы думаете по другом, готов услышать Вашу точку зрения.

@diagon · 15.05.2012, 08:51

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

Если Вы думаете по другом, готов услышать Вашу точку зрения.

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
#include <vector>
 
int main()
{
    std::vector< int > arr(5);
    
    asm volatile("//1");
    scanf("%d", &arr[3]);
    printf("%d", arr[3]);
    asm volatile("//2");
}

В ассемблерном листинге есть следующий кусок

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    //1
# 0 "" 2
#NO_APP
    leal    12(%eax), %eax
    movl    %eax, 4(%esp)
    movl    $.LC0, (%esp)
.LEHB1:
    call    scanf
    movl    12(%ebx), %eax
    movl    $.LC0, 4(%esp)
    movl    $1, (%esp)
    movl    %eax, 8(%esp)
    call    __printf_chk
.LEHE1:
#APP
# 11 "11.cpp" 1
    //2

Второй код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
#include <vector>
 
int main()
{
    int *arr = new int [5];
    
    asm volatile("//1");
    scanf("%d", &arr[3]);
    printf("%d", arr[3]);
    asm volatile("//2");
}

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//1
# 0 "" 2
#NO_APP
    leal    12(%eax), %eax
    movl    %eax, 4(%esp)
    movl    $.LC0, (%esp)
    call    scanf
    movl    12(%ebx), %eax
    movl    $.LC0, 4(%esp)
    movl    $1, (%esp)
    movl    %eax, 8(%esp)
    call    __printf_chk
#APP
# 11 "11.cpp" 1
    //2

Третий код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
#include <vector>
 
int main()
{
    int arr[5];
    
    asm volatile("//1");
    scanf("%d", &arr[3]);
    printf("%d", arr[3]);
    asm volatile("//2");
}

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    //1
# 0 "" 2
#NO_APP
    leal    40(%esp), %eax
    movl    %eax, 4(%esp)
    movl    $.LC0, (%esp)
    call    scanf
    movl    40(%esp), %eax
    movl    $.LC0, 4(%esp)
    movl    $1, (%esp)
    movl    %eax, 8(%esp)
    call    __printf_chk
#APP
# 11 "11.cpp" 1
    //2

Как видно, в первом случае все заинлайнилось(есть только 2 call'a - printf и scanf).
И вообще, эти 3 листинга практически эквивалентны.

@Toshkarik · 15.05.2012, 08:55

Ну возможно разница будет с более сложными алгоритмами/функциями, а с какими опциями компилировался данный код, и какой компилятор?

@diagon · 15.05.2012, 09:00

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

Ну возможно разница будет с более сложными алгоритмами/функциями, а с какими опциями компилировался данный код, и какой компилятор?

Сомневаюсь, что будет разница.
Компилятор - gcc 4.6.3
Компилировал/проверял так:

Bash
1
2
shadeware@ubunta:~$ g++ 11.cpp -O3 -S
shadeware@ubunta:~$ gedit 11.s

@Toshkarik · 15.05.2012, 09:03

Ну так c O2 и ниже думаю ситуация будет совсем другая. Я про это кстати страницу назад и говорил, что если включить встраивание функций, то будет совсем другой результат. Только вот O3 на практике почти никто не использует, разве что для тестов.

@diagon · 15.05.2012, 11:45

Вот такие результаты получаются.
-O0

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    //1
# 0 "" 2
#NO_APP
    movl    $3, 4(%esp)
    leal    28(%esp), %eax
    movl    %eax, (%esp)
    call    _ZNSt6vectorIiSaIiEEixEj
    movl    %eax, 4(%esp)
    movl    $.LC0, (%esp)
.LEHB1:
    call    scanf
    movl    $3, 4(%esp)
    leal    28(%esp), %eax
    movl    %eax, (%esp)
    call    _ZNSt6vectorIiSaIiEEixEj
    movl    (%eax), %eax
    movl    %eax, 4(%esp)
    movl    $.LC0, (%esp)
    call    printf
.LEHE1:
#APP
# 11 "11.cpp" 1
    //2

-O1

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    //1
# 0 "" 2
#NO_APP
    leal    12(%eax), %eax
    movl    %eax, 4(%esp)
    movl    $.LC0, (%esp)
.LEHB1:
    call    scanf
    movl    12(%ebx), %eax
    movl    %eax, 8(%esp)
    movl    $.LC0, 4(%esp)
    movl    $1, (%esp)
    call    __printf_chk
.LEHE1:
#APP
# 11 "11.cpp" 1
    //2

Т.е. с -O0 встраивания нету, что логично, а вот с -O1 оно уже есть.

@Toshkarik · 15.05.2012, 11:50

Ага

Не вектор

Новые блоги и статьи Все статьи Все блоги /
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений	сукцессия 14. Обновленная схема модели anaschu 28.06.2026 ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .
сукцессия 13. Питон модель трехзонного мицелия, пока что в основном арбускулярного anaschu 28.06.2026 ## Разработка агентной модели микоризной сукцессии: от выявления артефактов к созданию комплексной системы ### Аннотация Представлено исследование по разработке агентной модели микоризной. . .	сукцессия 12. краткий список проверок модели перед запуском. anaschu 27.06.2026 Скрытые отказы в моделях систем динамики (SD-models) экологических систем: два случая из практики Контекст Разбирался прототип модели систем динамики (SD-модели) микоризной сукцессии: пять. . .	Сукцессия 11. Проверка орудий перед войной: разработка через тестирование anaschu 27.06.2026 Как не дать модели соврать самой себе: проверки для симуляции микоризной сукцессии Введение Когда вы строите математическую модель живой системы — грибов, растений, почвы — главная опасность. . .	10 сукцессия. Питон код войны грибов и растений anaschu 27.06.2026 import numpy as np class PlantAgent: def __init__(self, name, strategy, initial_biomass): self. name = name self. strategy = strategy # "greedy" (широколиственные) или. . .

@Avazart 8489 / 6156 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	14.05.2012, 23:49
	Да не как не должен зависить от размера ни скорость ни доступ к элементу так как элементы хранятся строго в одном месте, а значит видут себя так же как и массивы. В коде я не чего не понял и нехочу, так как там сильно награмаждено. 0

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	14.05.2012, 23:59
	Согласен. Код не смотрел, но могу предположить, что вы накапливаете время доступа. У вектора безусловно скорость доступа к элементу ниже чем у простого массива, но как и сказали выше, она никак не должна зависеть от размера. 0

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	15.05.2012, 08:39
	Ну так везде и пишут, да и логично это. Вектор - шаблонный класс. При доступе к элементу вызывается функция перегрузки оператора. Всегда почему то верил людям и источникам, где это было написано, так как повода сомневаться в их компетентности не было. Везде писали, включая и этот форум, причем кто то из здешних, так сказать, профи - если важна скорость доступа - используйте массивы Си. Вектор же более удобен и высокоуровен. Если Вы думаете по другом, готов услышать Вашу точку зрения. 0

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	15.05.2012, 08:55
	Ну возможно разница будет с более сложными алгоритмами/функциями, а с какими опциями компилировался данный код, и какой компилятор? 0

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	15.05.2012, 09:03
	Ну так c O2 и ниже думаю ситуация будет совсем другая. Я про это кстати страницу назад и говорил, что если включить встраивание функций, то будет совсем другой результат. Только вот O3 на практике почти никто не использует, разве что для тестов. 0

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	15.05.2012, 11:50
	Ага Не вектор 0