"Новый взгляд" на контейнеры , по версии явиста

[OpenGL]

Цитата settler @ 01.06.18, 13:27

Не Вероятно, bad_alloc может у вектора случиться раньше , а случиться на 100%,

То есть вот тут произошло событие с нулевой вероятностью?

Code

#include <vector>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
#include <optional>
#include <memory>
#include <type_traits>
#include <list>
#include <sys/time.h>
#include <sys/resource.h>
 
template<class C> void gen()
{
    C v;        
    for(int i = 0; i < 5000; ++i) v.push_back(i);
}
 
int main()
{
    rlimit lim;
    lim.rlim_cur = 0;
    lim.rlim_max = 1000000;
    setrlimit(RLIMIT_AS, &lim);
    gen<std::vector<int>>();
    std::cout << "Vector was generated\n";
    
    //gen<std::vector<int>>();
    //std::cout << "Vector2 was generated\n";
    
    gen<std::list<int>>();
    std::cout << "List was generated\n";
}
}

Вывод:

terminate called after throwing an instance of 'St9bad_alloc'
Vector was generated
  what():  std::bad_alloc
Aborted

Если ты заменишь std::list в последнем примере на std::vector - внезапно всё отработает. Как это поведение объяснимо в твоей картине мира?

Это сообщение было перенесено сюда или объединено из темы "Что несет Бьёрн Страуструп?"

Сообщение отредактировано: OpenGL - 10.06.18, 14:29

[Олег М]

Цитата OpenGL @ 07.06.18, 06:48

Если ты заменишь std::list в последнем примере на std::vector - внезапно всё отработает. Как это поведение объяснимо в твоей картине мира?

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

Вообще, сравнивать vector и list - это примерно как сравнивать пароход с паровозом - который из них лучше?
Это совершенно разные структуры для реализации разных задач. Проблемы возникают ене потому что, один хуже или лучше другого, а потому, что для решения конкретной задачи используется не тот контейнер.

Это сообщение было перенесено сюда или объединено из темы "Что несет Бьёрн Страуструп?"

[OpenGL]

Цитата Олег М @ 07.06.18, 07:29

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

Это понятно. Тут спорят с бредом "вектор потребляет больше памяти", которые его срасчёты вроде как по его мнению показывают.

Это сообщение было перенесено сюда или объединено из темы "Что несет Бьёрн Страуструп?"

[settler]

Цитата OpenGL @ 07.06.18, 08:38

Это понятно. Тут спорят с бредом "вектор потребляет больше памяти", которые его срасчёты вроде как по его мнению показывают.

Ты понимаешь как вектор добавляет новый елемент ?
Сколько он выделает памяти ? Сколько выделяет список ?

Это сообщение было перенесено сюда или объединено из темы "Что несет Бьёрн Страуструп?"

[OpenGL]

Цитата settler @ 07.06.18, 21:06

Ты понимаешь как вектор добавляет новый елемент ?

А почему ты спрашиваешь? Ты не догадываешься, что я на этот вопрос отвечу?
Ответь лучше на вопрос выше - почему мой код падает с bad_alloc в случае списка и не падает в случае вектора если вектор занимает памяти больше

Это сообщение было перенесено сюда или объединено из темы "Что несет Бьёрн Страуструп?"

[amk]

Олег М, как ты понимаешь значение слова "дефрагментирована"?
Потому как у меня при прочтении твоих постов возникают некоторые сомнения, что ты полностью понимаешь, что в них пишешь.

Это сообщение было перенесено сюда или объединено из темы "Что несет Бьёрн Страуструп?"

[settler]

Цитата OpenGL @ 08.06.18, 07:09

Цитата settler @ 07.06.18, 21:06

Ты понимаешь как вектор добавляет новый елемент ?

А почему ты спрашиваешь? Ты не догадываешься, что я на этот вопрос отвечу?
Ответь лучше на вопрос выше - почему мой код падает с bad_alloc в случае списка и не падает в случае вектора если вектор занимает памяти больше

Ну так твой код, Я так писать еще не научился,
Вектор увеличивает памать в два раза, то есть выделил памать под 1000
элементов - а надо 1001, так вот на 1001 он выделает *2 то есть 2000, (999байт коту под хвост)
на 2001 - 4000, и т.д. Tак пишут в книгах по OS,
в какой то момент будет out of memory, памяти всего может быть, но может не быть
linear memory block, до сих что не так ?

Лист не занимает больше памяти он больше выделает,(sizeof() = 24 дважды) и потом стирает,(см сорцы)
фактически у него не два поинтера а три (третий temp каждый раз выделает и делилит память),
возможно при больших обьемах он не увеличивает размер на два, возможно оптимизатор
собирает статистику и выделает память более умно, но это мои догадки,

так вот в твоем случае память не дефрагментирована, по сути пустая, нету с чего, и с тем что я написал не столкнулся, то есть нет проблем выделить linear memory block,


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

Это сообщение было перенесено сюда или объединено из темы "Что несет Бьёрн Страуструп?"

[Qraizer]

settler, можешь объяснить, почему из своих наблюдений ты делаешь выводы, а из наблюдений других не делаешь никаких? Сколько тебе кода уже предоставили? Сам посчитаешь? Сколько коду было от тебя? Я уже посчитал.

Сообщения были разделены в тему "Новый взгляд на контейнеры"

Это сообщение было перенесено сюда или объединено из темы "Что несет Бьёрн Страуструп?"

[Qraizer]

!

JoeUser, заряжай.

Эта тема была разделена из темы "Что несет Бьёрн Страуструп?"

Сообщение отредактировано: JoeUser - 09.06.18, 04:29

[Олег М]

Цитата amk @ 08.06.18, 15:40

Олег М, как ты понимаешь значение слова "дефрагментирована"?
Потому как у меня при прочтении твоих постов возникают некоторые сомнения, что ты полностью понимаешь, что в них пишешь.

Ну, для начала расскажи как ты понимаешь значение этого слова, а то что-то у меня возникают сомнения.

[OpenGL]

Цитата settler @ 09.06.18, 00:45

Вектор увеличивает памать в два раза, то есть выделил памать под 1000
элементов - а надо 1001, так вот на 1001 он выделает *2 то есть 2000, (999байт коту под хвост)
на 2001 - 4000, и т.д. Tак пишут в книгах по OS,

Во-первых, если мне надо 1001 элемент, я выделю 1001 элемент, а не 1000, как это ни странно Во-вторых, это будет только при реаллокации, так что не страшно. В-третьих, на практике коэфициент 2 используют редко - обычно он меньше. И в-чётвёртых даже если предположить, что у меня действительно capacity вдвое больше, чем size, занимаемая память всё равно будет меньше из-за того, что sizeof(void*) в данном случае вдвое больше самого int-а, а это значит в твоём сценарии памяти съест вектор всё равно в полтора раза меньше, чем такой список

Добавлено 09.06.18, 06:38

Цитата Олег М @ 09.06.18, 06:21

Ну, для начала расскажи как ты понимаешь значение этого слова, а то что-то у меня возникают сомнения.

Вероятно, он о том, что реально ты хотел сказать "в реальных задачах паметь фрагментирована"

[Олег М]

Цитата OpenGL @ 09.06.18, 06:36

Вероятно, он о том, что реально ты хотел сказать "в реальных задачах паметь фрагментирована"

Да, точно, ошибся.

[amk]

settler, вектор старается уменьшитьчисло перераспределений памяти, но не настолько. Ёмкость удваивается только пока вектор относительно небольшой. при средних размерах ёмкость увеличивается наполовину, Большие вектора увеличиваются при перераспределении где-то на четверть. При этом вектор всё так же имеет линейные затраты, просто константа увеличивается. При этом мы ещё и избавляемся от одного неприятного явления, проявляющегося при удвоении ёмкости, когда освобождённой ранее вектором памяти, даже после склейки освобождённых кусков всё время не хватает для нового буфера (память становится одноразовой).
Кроме того, если примерное количество мест в векторе известно, всегда можно запросить нужный размер вручную сразу, тогда вектор вообще перераспределять память не будет.

Добавлено 09.06.18, 18:34
Олег М, просто ты такую ошибку допустил в каждом из мест, где писал о фрагментации.

[settler]

Цитата amk @ 09.06.18, 18:33

settler, вектор старается уменьшитьчисло перераспределений памяти, но не настолько. Ёмкость удваивается только пока вектор относительно небольшой. при средних размерах ёмкость увеличивается наполовину, Большие вектора увеличиваются при перераспределении где-то на четверть. При этом вектор всё так же имеет линейные затраты, просто константа увеличивается. При этом мы ещё и избавляемся от одного неприятного явления, проявляющегося при удвоении ёмкости, когда освобождённой ранее вектором памяти, даже после склейки освобождённых кусков всё время не хватает для нового буфера (память становится одноразовой).

Это вполне логично,(свои вектора примерно так и делают),как ты понимаешь это тема есть в любом языке, в Ява сорцах явно видно как умножается на два (если надо могу выложить),
ArrayList на 3/2, где сказано про c++ vector что в нем так как ты говоришь, и как это
грамотно изменить для конкретной задачи ? В яве наследуют тут надо писать свой алокатор ?
или что ?

Добавлено 09.06.18, 19:46

Цитата amk @ 09.06.18, 18:33

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

Это понятно, я говорю о том когда неизвестно , лист для того и придумал,
да там оверхад в 16байт(два поинтера) и memory overflow будет как в примере OpenGL но когда сам обьект большой оно мало влияет, ну кто мешает юзать sigleList он есть в C++11 ЕМНИП.

Добавлено 09.06.18, 19:52

Цитата OpenGL @ 09.06.18, 06:36

Во-первых, если мне надо 1001 элемент, я выделю 1001 элемент, а не 1000, как это ни странно

Как ни странно ты об этом не всегда заранее знаешь
И представь себе что данные постоянно то стираються то добавляются снова,
В этом случае нужен лист и лучше single,

Добавлено 09.06.18, 19:55

Цитата OpenGL @ 09.06.18, 06:36

Во-вторых, это будет только при реаллокации, так что не страшно.

Если реаллокации много то может и страшно, от задачи зависит.

Добавлено 09.06.18, 20:07

Цитата OpenGL @ 09.06.18, 06:36

В-третьих, на практике коэфициент 2 используют редко - обычно он меньше.

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

Добавлено 09.06.18, 20:31

Цитата OpenGL @ 09.06.18, 06:36

И в-чётвёртых даже если предположить, что у меня действительно capacity вдвое больше, чем size, занимаемая память всё равно будет меньше из-за того, что sizeof(void*) в данном случае вдвое больше самого int-а, а это значит в твоём сценарии памяти съест вектор всё равно в полтора раза меньше, чем такой список

Не понял , кто у тебя void*

смотри еще раз мои расчеты, what is wrong here ?

class Node<T>{
 node* prev;
 node* next;
 T value;
 
}

sizeof(node) = sizeof(T) + sizeof(next) +sizeof(prev) для 64бит
будет sizeof(T) + 16,

для листа будет n(sizeof(T) + 16) ,

для вектора n*sizeof(T) , при увиличении на 2 или на х , то есть при первой перелокации
имеем
для листа будет (n+1)(sizeof(T) + 16) ,
для вектора х*n*sizeof(T)

если х небольшой то проблем нет если он 2 или 1.5 и Т большой то лист выигрывает и очень не слабо,
Понимаешь что все не однозначто еще есть cashing line problem , о которой програмисты C++, c 15-20 опытом молчат как партизаны и вектор можно гонять потоками, как в яве 8,
а с листом (у него нет индекса) это сложнее.

В общем разные контейнеры для разных задач, и говорить что один лучше, есть показатель
собсвенных lack of knowledge ( не путать с luck слышиться одинаково )

Все .

[settler]

Цитата Qraizer @ 09.06.18, 02:35

settler, можешь объяснить, почему из своих наблюдений ты делаешь выводы, а из наблюдений других не делаешь никаких? Сколько тебе кода уже предоставили? Сам посчитаешь? Сколько коду было от тебя? Я уже посчитал.

Почему из других не делаю? вот код openGL
и навел, точнее дополнил, трех строк хватило,
а что в моих выводах не устраивает(они не мои а Вирта или
Таненбаума, и лет им по 20-25 если не больше ) . А ты типо про работу OS
никогда не слышал , ага счас поверил,

А месть за КрымНеНашь (джо зажигай) это глупо, ты же не ватник типа Кили,
или програма , Или Я ошибаюсь ?