ReSQL.ru
     
powered by simpleCommunicator - 2.0.58     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / аллокация вектора
25 сообщений из 68, страница 1 из 3
  1  все
аллокация вектора
    #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:16
| Ответить | Цитировать | Написать  
аллокация вектора
    #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, 22:25
| Ответить | Цитировать | Написать  
аллокация вектора
    #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:07
| Ответить | Цитировать | Написать  
аллокация вектора
    #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
30.09.2019, 23:57
| Ответить | Цитировать | Написать  
аллокация вектора
    #39869635
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
полудухя так понимаю, эффективность надо высчитывать по инструкциям?

Это бесполезно. Современные процессора могут много странных гитик и "идеальный ассемблер"
на них тормозит.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
01.10.2019, 00:08
| Ответить | Цитировать | Написать  
аллокация вектора
    #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, 06:17
| Ответить | Цитировать | Написать  
аллокация вектора
    #39869686
alex_k
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex_k
Участник
Dima TДля замера надо время засекать и элементов побольше взять, например, миллион.
Или написать класс с журналированием конструирования и разрушения, поместить его в вектор заместо инта и посмотреть что именно происходит
...
Рейтинг: 0 / 0
01.10.2019, 09:34
| Ответить | Цитировать | Написать  
аллокация вектора
    #39869709
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Надо смотреть что под капотом ::push_back. Там не обязательно удвоение. Может быть умножение на полтора.
...
Рейтинг: 0 / 0
01.10.2019, 10:16
| Ответить | Цитировать | Написать  
аллокация вектора
    #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, 11:42
| Ответить | Цитировать | Написать  
аллокация вектора
    #39869837
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
полудух, попробуй в код вставить

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


Так ты же сделал reserve, как раз это и обошёл.
Убери reserve, и поменяй 1000 на 100000
...
Рейтинг: 0 / 0
01.10.2019, 12:07
| Ответить | Цитировать | Написать  
аллокация вектора
    #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:10
| Ответить | Цитировать | Написать  
аллокация вектора
    #39869850
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
полудух,

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

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

Ты можешь совсем ухудшить ситуацию, вызывая каждый раз после push_back()
метод shrink_to_fit(), который уменьшает ёмкость до минимально необходимой,
правда, не гарантировано.
...
Рейтинг: 0 / 0
01.10.2019, 12:12
| Ответить | Цитировать | Написать  
аллокация вектора
    #39869896
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
1000 довольно слабенький объем, чтобы в отладчике увидеть разницу в потреблении памяти приложения.
Попробуйте миллионов сто хотя бы.
...
Рейтинг: 0 / 0
01.10.2019, 13:05
| Ответить | Цитировать | Написать  
аллокация вектора
    #39869901
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
Во времена пентиумов, когда оперативная память уже достигла гигабайта, был забавный пример. Аллоцировать двумерный массив 1000_000х3 элемента было невозможно, не хватало памяти. Память аллоцировалась нелинейно, а блоками по 512 байт (по крайней мере на моей машине), поэтому не дойдя до конца вываливалась с нехваткой памяти.
Это больше имеет отношение к ленивой аллокации виртуальной памяти чем к пентиумам.
...
Рейтинг: 0 / 0
01.10.2019, 13:09
| Ответить | Цитировать | Написать  
аллокация вектора
    #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, 14:00
| Ответить | Цитировать | Написать  
аллокация вектора
    #39870004
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Чортов gcc...
...
Рейтинг: 0 / 0
01.10.2019, 15:02
| Ответить | Цитировать | Написать  
аллокация вектора
    #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:22
| Ответить | Цитировать | Написать  
аллокация вектора
    #39870022
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
и это расширение ведь должно быть видно и на 1000, зачем 1000000...
...
Рейтинг: 0 / 0
01.10.2019, 15:23
| Ответить | Цитировать | Написать  
аллокация вектора
    #39870026
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
полудухзначит та строчка в асме не про то что я спрашивал
я не про .push_back() спрашивал, а "где именно происходит расширение вектора *2/*4/*8 итд, когда вектор изначально инициализирован БЕЗ размера"
Та строчка асма за кадром осталась, ты ее код не привел. Команда call - это вызов подпрограммы. Конкретно именно в той подпрограмме (push_back()) происходит реаллокация (при необходимости).
...
Рейтинг: 0 / 0
01.10.2019, 15:26
| Ответить | Цитировать | Написать  
аллокация вектора
    #39870030
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
полудух
Участник
какой код не привёл? сырцы же там в начале

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

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

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


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