Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / аллокация вектора / 25 сообщений из 68, страница 1 из 3
  1  все
30.09.2019, 22:16
    #39869595
полудух
полудух
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
потестировал простой код:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
#include <iostream>
#include <vector>

using namespace std;

//##############################################################################
int main(int argc, char *argv[])
{
    system("clear");

    // вар1 (155 тактов в gdb):
    vector<int> v;
    v.reserve(1000);

    // вар 2 (197):
//    vector<int> v(1000);

    // вар 3, БЕЗ аллокации (133 !!!):
//    vector<int> v;

    for (int i = 0;   i < 1000;   ++i)
        {v.push_back(i);}
}



тут вопрос: а куда делась страшилка про то, что вектор, которому сразу не выдали 1000 эл-тов, будет сначала рожать 2, потом 4, 8, 16, ... ,1024
через delete + new...
где оно??

компилировал так: g++ -ggdb3 main.cpp
gdb a.out
(gdb) start
(gdb) disas

у варианта 3 asm такой:
Код: plaintext
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.
   0x0000555555554b70 <+0>:     push   %rbp
   0x0000555555554b71 <+1>:     mov    %rsp,%rbp
   0x0000555555554b74 <+4>:     push   %rbx
   0x0000555555554b75 <+5>:     sub    $0x48,%rsp
   0x0000555555554b79 <+9>:     mov    %edi,-0x44(%rbp)
   0x0000555555554b7c <+12>:    mov    %rsi,-0x50(%rbp)
=> 0x0000555555554b80 <+16>:    lea    0xbbe(%rip),%rdi        # 0x555555555745
   0x0000555555554b87 <+23>:    callq  0x5555555549b0 <system@plt>;
   0x0000555555554b8c <+28>:    lea    -0x30(%rbp),%rax
   0x0000555555554b90 <+32>:    mov    %rax,%rdi
   0x0000555555554b93 <+35>:    callq  0x555555554c6c <std::vector<int, std::allocator<int> >::vector()>
   0x0000555555554b98 <+40>:    movl   $0x0,-0x34(%rbp)
   0x0000555555554b9f <+47>:    mov    -0x34(%rbp),%eax
   0x0000555555554ba2 <+50>:    cmp    $0x3e7,%eax
   0x0000555555554ba7 <+55>:    jg     0x555555554bc7 <main(int, char**)+87>
   0x0000555555554ba9 <+57>:    lea    -0x34(%rbp),%rdx
   0x0000555555554bad <+61>:    lea    -0x30(%rbp),%rax
   0x0000555555554bb1 <+65>:    mov    %rdx,%rsi
   0x0000555555554bb4 <+68>:    mov    %rax,%rdi
   0x0000555555554bb7 <+71>:    callq  0x555555554ccc <std::vector<int, std::allocator<int> >::push_back(int const&)>
   0x0000555555554bbc <+76>:    mov    -0x34(%rbp),%eax
   0x0000555555554bbf <+79>:    add    $0x1,%eax
   0x0000555555554bc2 <+82>:    mov    %eax,-0x34(%rbp)
   0x0000555555554bc5 <+85>:    jmp    0x555555554b9f <main(int, char**)+47>
   0x0000555555554bc7 <+87>:    lea    -0x30(%rbp),%rax
   0x0000555555554bcb <+91>:    mov    %rax,%rdi
   0x0000555555554bce <+94>:    callq  0x555555554c88 <std::vector<int, std::allocator<int> >::~vector()>
   0x0000555555554bd3 <+99>:    mov    $0x0,%eax
   0x0000555555554bd8 <+104>:   jmp    0x555555554bf4 <main(int, char**)+132>
   0x0000555555554bda <+106>:   mov    %rax,%rbx
   0x0000555555554bdd <+109>:   lea    -0x30(%rbp),%rax
   0x0000555555554be1 <+113>:   mov    %rax,%rdi
   0x0000555555554be4 <+116>:   callq  0x555555554c88 <std::vector<int, std::allocator<int> >::~vector()>
   0x0000555555554be9 <+121>:   mov    %rbx,%rax
   0x0000555555554bec <+124>:   mov    %rax,%rdi
   0x0000555555554bef <+127>:   callq  0x555555554a20 <_Unwind_Resume@plt>;
   0x0000555555554bf4 <+132>:   add    $0x48,%rsp
   0x0000555555554bf8 <+136>:   pop    %rbx
   0x0000555555554bf9 <+137>:   pop    %rbp
   0x0000555555554bfa <+138>:   retq


у двух других они длиннее...

зы: я правильно угадал, что <+138> это такты?
зыы: gcc version 6.3.0 20170516 (Debian 6.3.0-18+deb9u1)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.09.2019, 22:25
    #39869600
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
полудухзы: я правильно угадал, что <+138> это такты?

Нет, адресное смещение.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.09.2019, 22:25
    #39869601
exp98
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
Путаешь слова, в листинге же д.б. длина команды в байтах. А такты - я нынче не знаю, насколько это пропорционально байтам команды.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.09.2019, 23:07
    #39869616
полудух
полудух
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
ну тогда, я так понимаю, эффективность надо высчитывать по инструкциям?
по ним там вроде как тоже не особо разницу видно...
вот вар1 (.reserve()):
Код: plaintext
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.
   0x0000555555554b70 <+0>:     push   %rbp
   0x0000555555554b71 <+1>:     mov    %rsp,%rbp
   0x0000555555554b74 <+4>:     push   %rbx
   0x0000555555554b75 <+5>:     sub    $0x48,%rsp
   0x0000555555554b79 <+9>:     mov    %edi,-0x44(%rbp)
   0x0000555555554b7c <+12>:    mov    %rsi,-0x50(%rbp)
=> 0x0000555555554b80 <+16>:    lea    0xdce(%rip),%rdi        # 0x555555555955
   0x0000555555554b87 <+23>:    callq  0x5555555549b0 <system@plt>;
   0x0000555555554b8c <+28>:    lea    -0x30(%rbp),%rax
   0x0000555555554b90 <+32>:    mov    %rax,%rdi
   0x0000555555554b93 <+35>:    callq  0x555555554c7c <std::vector<int, std::allocator<int> >::vector()>
   0x0000555555554b98 <+40>:    lea    -0x30(%rbp),%rax
   0x0000555555554b9c <+44>:    mov    $0x3e8,%esi
   0x0000555555554ba1 <+49>:    mov    %rax,%rdi
   0x0000555555554ba4 <+52>:    callq  0x555555554cdc <std::vector<int, std::allocator<int> >::reserve(unsigned long)>
   0x0000555555554ba9 <+57>:    movl   $0x0,-0x34(%rbp)
   0x0000555555554bb0 <+64>:    mov    -0x34(%rbp),%eax
   0x0000555555554bb3 <+67>:    cmp    $0x3e7,%eax
   0x0000555555554bb8 <+72>:    jg     0x555555554bd8 <main(int, char**)+104>
   0x0000555555554bba <+74>:    lea    -0x34(%rbp),%rdx
   0x0000555555554bbe <+78>:    lea    -0x30(%rbp),%rax
   0x0000555555554bc2 <+82>:    mov    %rdx,%rsi
   0x0000555555554bc5 <+85>:    mov    %rax,%rdi
   0x0000555555554bc8 <+88>:    callq  0x555555554e1e <std::vector<int, std::allocator<int> >::push_back(int const&)>
   0x0000555555554bcd <+93>:    mov    -0x34(%rbp),%eax
   0x0000555555554bd0 <+96>:    add    $0x1,%eax
   0x0000555555554bd3 <+99>:    mov    %eax,-0x34(%rbp)
   0x0000555555554bd6 <+102>:   jmp    0x555555554bb0 <main(int, char**)+64>
   0x0000555555554bd8 <+104>:   lea    -0x30(%rbp),%rax
   0x0000555555554bdc <+108>:   mov    %rax,%rdi
   0x0000555555554bdf <+111>:   callq  0x555555554c98 <std::vector<int, std::allocator<int> >::~vector()>
   0x0000555555554be4 <+116>:   mov    $0x0,%eax
   0x0000555555554be9 <+121>:   jmp    0x555555554c05 <main(int, char**)+149>
   0x0000555555554beb <+123>:   mov    %rax,%rbx
   0x0000555555554bee <+126>:   lea    -0x30(%rbp),%rax
   0x0000555555554bf2 <+130>:   mov    %rax,%rdi
   0x0000555555554bf5 <+133>:   callq  0x555555554c98 <std::vector<int, std::allocator<int> >::~vector()>
   0x0000555555554bfa <+138>:   mov    %rbx,%rax
   0x0000555555554bfd <+141>:   mov    %rax,%rdi
   0x0000555555554c00 <+144>:   callq  0x555555554a20 <_Unwind_Resume@plt>;
   0x0000555555554c05 <+149>:   add    $0x48,%rsp
   0x0000555555554c09 <+153>:   pop    %rbx
   0x0000555555554c0a <+154>:   pop    %rbp
   0x0000555555554c0b <+155>:   retq


какой эффективнее?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.09.2019, 23:57
    #39869631
blonduser
blonduser
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
полудухпотестировал простой код:
тут вопрос: а куда делась страшилка про то, что вектор, которому сразу не выдали 1000 эл-тов, будет сначала рожать 2, потом 4, 8, 16, ... ,1024
через delete + new...
где оно??


оно здесь прячется.
Код: plaintext
1.
   0x0000555555554bb7 <+71>:    callq  0x555555554ccc <std::vector<int, std::allocator<int> >::push_back(int const&)>
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 00:08
    #39869635
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
полудухя так понимаю, эффективность надо высчитывать по инструкциям?

Это бесполезно. Современные процессора могут много странных гитик и "идеальный ассемблер"
на них тормозит.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 06:17
    #39869662
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
полудухну тогда, я так понимаю, эффективность надо высчитывать по инструкциям?
Забавная методика. А как быть с циклами и ветвлениями? Код может многократно выполняться или вообще не выполняться.

Перевыделение памяти происходит внутри push_back() как уже выше заметили 21983365 . При этом выполняется копирование текущего массива, т.е. в первый раз 2 элемента, во второй 4, затем 8, 16, ...
В твоем случае при 1000 элементов будут скопированы 2+4+8+...512=1022 элемента. Для int это относительно быстро, но замени int на какой-нибудь объект, у которого еще надо конструктор копирования и деструктор вызвать, и получишь более ощутимые тормоза.

Для замера надо время засекать и элементов побольше взять, например, миллион.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 09:34
    #39869686
alex_k
alex_k
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
Dima TДля замера надо время засекать и элементов побольше взять, например, миллион.
Или написать класс с журналированием конструирования и разрушения, поместить его в вектор заместо инта и посмотреть что именно происходит
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 10:16
    #39869709
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
Надо смотреть что под капотом ::push_back. Там не обязательно удвоение. Может быть умножение на полтора.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 11:42
    #39869813
полудух
полудух
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
blonduserполудухпотестировал простой код:
тут вопрос: а куда делась страшилка про то, что вектор, которому сразу не выдали 1000 эл-тов, будет сначала рожать 2, потом 4, 8, 16, ... ,1024
через delete + new...
где оно??


оно здесь прячется.
Код: plaintext
1.
   0x0000555555554bb7 <+71>:    callq  0x555555554ccc <std::vector<int, std::allocator<int> >::push_back(int const&)>


хмм, так оно и в варианте с .reserve() есть... почему?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 12:03
    #39869837
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
полудух, попробуй в код вставить

Код: plaintext
1.
#pragma optimize( "", off )
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 12:07
    #39869843
MasterZiv
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
полудух
тут вопрос: а куда делась страшилка про то, что вектор, которому сразу не выдали 1000 эл-тов, будет сначала рожать 2, потом 4, 8, 16, ... ,1024
через delete + new...
где оно??


Так ты же сделал reserve, как раз это и обошёл.
Убери reserve, и поменяй 1000 на 100000
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 12:10
    #39869846
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
полудуххмм, так оно и в варианте с .reserve() есть... почему?
Потому что ты ее вызываешь
Код: plaintext
1.
2.
    for (int i = 0;   i < 1000;   ++i)
        {v.push_back(i);}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 12:12
    #39869850
MasterZiv
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
полудух,

Ну и да, ёмкость увеличивается не на 1 элемент за каждый push_back(), а скачками,
в два раза или что-то такое.

Как именно -- не специфицированно.

Ты можешь совсем ухудшить ситуацию, вызывая каждый раз после push_back()
метод shrink_to_fit(), который уменьшает ёмкость до минимально необходимой,
правда, не гарантировано.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 13:05
    #39869896
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
1000 довольно слабенький объем, чтобы в отладчике увидеть разницу в потреблении памяти приложения.
Попробуйте миллионов сто хотя бы.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 13:09
    #39869901
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
Во времена пентиумов, когда оперативная память уже достигла гигабайта, был забавный пример. Аллоцировать двумерный массив 1000_000х3 элемента было невозможно, не хватало памяти. Память аллоцировалась нелинейно, а блоками по 512 байт (по крайней мере на моей машине), поэтому не дойдя до конца вываливалась с нехваткой памяти.
Это больше имеет отношение к ленивой аллокации виртуальной памяти чем к пентиумам.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 14:00
    #39869939
ёёёёё
ёёёёё
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
maytonНадо смотреть что под капотом ::push_back. Там не обязательно удвоение. Может быть умножение на полтора.
:)
В MSVS 2017 - увеличивается экспоненциально, всякий раз на половину предыдущей емкости.
Но только если есть такая возможность! Иначе - увеличивается на столько, сколько запрошено.
У GCC - вроде бы все еще в 2 раза.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
	size_type _Calculate_growth(const size_type _Newsize) const
		{	// given _Oldcapacity and _Newsize, calculate geometric growth
		const size_type _Oldcapacity = capacity();

		if (_Oldcapacity > max_size() - _Oldcapacity / 2)
			{
			return (_Newsize);	// geometric growth would overflow
			}

		const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2;

		if (_Geometric < _Newsize)
			{
			return (_Newsize);	// geometric growth would be insufficient
			}

		return (_Geometric);	// geometric growth is sufficient
		}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 15:02
    #39870004
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
Чортов gcc...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 15:22
    #39870021
полудух
полудух
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
MasterZivполудухтут вопрос: а куда делась страшилка про то, что вектор, которому сразу не выдали 1000 эл-тов, будет сначала рожать 2, потом 4, 8, 16, ... ,1024
через delete + new...
где оно??
Так ты же сделал reserve, как раз это и обошёл.
Убери reserve, и поменяй 1000 на 100000
.reserve() только в 1м варианте. В 3м как раз без ничего: vector<int> v;
MasterZivполудух,

Ну и да, ёмкость увеличивается не на 1 элемент за каждый push_back(), а скачками,
в два раза или что-то такое.
и про это я написал тоже.

Dima Tполудуххмм, так оно и в варианте с .reserve() есть... почему?
Потому что ты ее вызываешь
Код: plaintext
1.
2.
    for (int i = 0;   i < 1000;   ++i)
        {v.push_back(i);}


значит та строчка в асме не про то что я спрашивал
я не про .push_back() спрашивал, а "где именно происходит расширение вектора *2/*4/*8 итд, когда вектор изначально инициализирован БЕЗ размера"
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 15:23
    #39870022
полудух
полудух
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
и это расширение ведь должно быть видно и на 1000, зачем 1000000...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 15:26
    #39870026
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
полудухзначит та строчка в асме не про то что я спрашивал
я не про .push_back() спрашивал, а "где именно происходит расширение вектора *2/*4/*8 итд, когда вектор изначально инициализирован БЕЗ размера"
Та строчка асма за кадром осталась, ты ее код не привел. Команда call - это вызов подпрограммы. Конкретно именно в той подпрограмме (push_back()) происходит реаллокация (при необходимости).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 15:31
    #39870030
полудух
полудух
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
какой код не привёл? сырцы же там в начале

так страшилка в том, что БЕЗ инициализации с размером этот .push_back() должен в цикле расширять вектор постепенно в 2 раза (*2 *4 *8 *16 ... *1024), чем сильно тормозит процесс
вот его я и не вижу в асме
вы говорите "вот он"
а потом "это не он", а push_back()
ну инструкции то по самому расширению где?? Где delete + new и прочие телодвижения?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 15:32
    #39870034
полудух
полудух
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
может gdb не всё показал...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 15:33
    #39870035
полудух
полудух
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
"objdump -d" показывает очень сильно больше асма...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
01.10.2019, 15:41
    #39870040
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
аллокация вектора
полудухкакой код не привёл? сырцы же там в начале
Это только main(), а остальное?

Код push_back() начинается с адреса 0x555555554ccc

PS Фигней занимаешься. Код там есть, и в нем все вызовы new/delete есть. От вызова reserve() зависит как часто будет тот код вызываться. Тот код как минимум один раз отрабатывает внутри reserve()
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / аллокация вектора / 25 сообщений из 68, страница 1 из 3
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
созд. / загр.: 405ms
Закрыть
start [/forum/topic.php?fid=57&mobile=1&tid=2017561]:
 0ms
get settings:
 10ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 37ms
get topic data:
 9ms
get forum data:
 3ms
get page messages:
 64ms
get tp. blocked users:
 1ms
others: 259ms
total:  405ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]