resize or reserve

@bedvit · Регистрация: 20.05.2016

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

Мое почтение, джентльмены.
Нужно быстро выделить буфер для работы с адресной арифметикой.
И так, чтобы без ручного освобождения памяти.
Был предложен след подход:

C++

const DWORD  nNumberOfBytesToRead = 16777216;
std::string s;
s.resize( nNumberOfBytesToRead + 4096 * 2);
char* buf = &s[4096 - size_t(s.c_str()) % 4096]; //выравнивание

Не нравится, то что resize() - это трата времени на заполнение строки.

Вопрос знатокам:

C++

const DWORD  nNumberOfBytesToRead = 16777216;
std::string s;
s.reserve( nNumberOfBytesToRead + 4096 * 2);
char* buf = &s[4096 - size_t(s.c_str()) % 4096]; //выравнивание

Будет ли этот код UB и почему?
Компилятор (VS2017) в режиме отладки ругается (обращение к не инициализированной строке), в релиз - все норм.

@bedvit · 07.07.2020, 16:54 **[ТС]**

Алексей1153, после нескольких итераций malloc + free впереди (поправил пост), но отстаивание new небольшое.
Протестируете у себя?

Добавлено через 1 минуту
А вообще каждый раз разный результат, иногда new выигрывает. Вообщем разница небольшая у меня (VS2017)

Алексей1153 · 07.07.2020, 17:14

bedvit, вот тут я попробовал четыре варианта

GCC
http://cpp.sh/6f2pu

C++

#include <chrono>
#include <iostream>
 
int main()
{
    int N = 1000000;
    int volume=1024*2;
 
    //new без инициализации
    {
        auto start = std::chrono::steady_clock::now();
        for (int i = 0; i < N; i++) {char* p = new char[volume]; delete[] p;}
        std::cout << "new no init: " << (std::chrono::steady_clock::now() - start).count() << std::endl;
    }
    
    //new с инициализацией
    {
        auto start = std::chrono::steady_clock::now();
        for (int i = 0; i < N; i++) {char* p = new char[volume]{}; delete[] p;}
        std::cout << "new   init: " << (std::chrono::steady_clock::now() - start).count() << std::endl;
    }
 
    //malloc
    {
        auto start = std::chrono::steady_clock::now();
        for (int i = 0; i < N; i++) {char* p = (char*)malloc(volume); free(p);}
        std::cout << "malloc: " << (std::chrono::steady_clock::now() - start).count() << std::endl;
    }
    
    //calloc
    {
        auto start = std::chrono::steady_clock::now();
        for (int i = 0; i < N; i++) { char* p = (char*) calloc(volume, sizeof(char)); free(p);}
        std::cout << "calloc: " << (std::chrono::steady_clock::now() - start).count() << std::endl;
    }
 
 
    return 0;
}

new no init: 86231618

new   init: 1555100599

malloc: 42

calloc: 32

а вот тут https://wandbox.org/ то же самое выдало

new no init: 70024303

new   init: 1869763221

malloc: 59106867

calloc: 120317910

в общем, экспериментатор с памятью из меня так себе

Добавлено через 2 минуты
upd по второй ссылке с включенной оптимизацией:

new no init: 50182

new   init: 934576169

malloc: 723

calloc: 553

а при повторе аж вообще вот так

new no init: 49733

new   init: 964271557

malloc: 471

calloc: 0

@bedvit · 07.07.2020, 17:22 **[ТС]**

У меня
new no init: 37377618
new init: 79365468
malloc: 37378826
calloc: 120207779

т.е. new вполне сравним c malloc.
calloc как и предполагалось медленнее.

Алексей1153 · 07.07.2020, 17:29

Сообщение от Алексей1153

с включенной оптимизацией

я подозреваю, что с оптимизацией malloc и calloc вообще были выкинуты

@DrOffset · 07.07.2020, 17:37

Сообщение от Алексей1153

я подозреваю, что с оптимизацией malloc и calloc вообще были выкинуты

Правильно, потому что бутерброд надо есть колбасой вниз ))
Т.е. нужен побочный эффект, чтобы не выкидывал.
Например так:

C++

#include <chrono>
#include <iostream>
 
char * pg;
 
int main()
{
    int N = 1000000;
    int volume=1024*2;
 
    //new без инициализации
    {
        auto start = std::chrono::steady_clock::now();
        for (int i = 0; i < N; i++) {char* p = new char[volume]; pg = p; delete[] p;}
        auto end = (std::chrono::steady_clock::now() - start);
        std::cout << "new no init: " << end.count() << std::endl;
    }
    
    //new с инициализацией
    {
        auto start = std::chrono::steady_clock::now();
        for (int i = 0; i < N; i++) {char* p = new char[volume]{}; pg = p; delete[] p;}
        auto end = (std::chrono::steady_clock::now() - start);
        std::cout << "new   init: " << end.count() << std::endl;
    }
 
    //malloc
    {
        auto start = std::chrono::steady_clock::now();
        for (int i = 0; i < N; i++) {char* p = (char*)malloc(volume); pg = p; free(p);}
        auto end = (std::chrono::steady_clock::now() - start);
        std::cout << "malloc: " << end.count() << std::endl;
    }
    
    //calloc
    {
        auto start = std::chrono::steady_clock::now();
        for (int i = 0; i < N; i++) { char* p = (char*) calloc(volume, sizeof(char)); pg = p; free(p);}
        auto end = (std::chrono::steady_clock::now() - start);
        std::cout << "calloc: " << end.count() << std::endl;
    }
}

Алексей1153 · 07.07.2020, 17:38

DrOffset, да, wandbox подтверждает ) А первый сайт упал, не могу зайти туда

@DrOffset · 07.07.2020, 17:40

Алексей1153,
https://rextester.com/DJU13619
https://rextester.com/QDM23956

Можно кстати воочию увидеть насколько в linux лучше реализация malloc по умолчанию. Одна из самых производительных на стандартных задачах.

@Undisputed · 07.07.2020, 18:28

Не по теме:

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

Croessmah · 07.07.2020, 19:21

Не по теме:

Undisputed, такие тесты вообще бесполезно делать в отрыве от задачи и остального кода.

@Undisputed · 07.07.2020, 19:56

Не по теме:

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

@DrOffset · 07.07.2020, 20:05

Не по теме:

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

разве более быстрый алгоритм на тестах не окажется более быстрым и в боевых условиях?

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

@Undisputed · 07.07.2020, 20:36

Не по теме:

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

Croessmah · 07.07.2020, 20:42

Не по теме:

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

да, если скорость работы алгоритма зависит от данных...

Если не зависит, то можно в compile-time подсчитать. )

@DrOffset · 07.07.2020, 20:49

Не по теме:

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

я думал что речь идёт в том числе и о тех случаях когда скорость работы алгоритма независит от данных

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

Т.е. O-оценка алгоритма это хорошо, но по факту в это может вмешиваться множество разных факторов и буквально на практике перекраивать предварительные оценки. Поэтому профайлер - наш друг :)

Croessmah · 07.07.2020, 20:59

Не по теме:

DrOffset, и еще от порядка работы, производимых до и после алгоритма операций, и, естественно, от параллельно работающих потоков.

@Undisputed · 07.07.2020, 21:09

Не по теме:

Croessmah,
Не всегда же в compile time можно все упаковать что работает за О(1). Скажем если это фиксированный пул памяти, который возвращает указатель на голову и обновляет голову (ставит новый свободный блок памяти в голову). Работает за О(1), при этом это функция времени выполнения... и попадания в кэш и т.д не считается. Нет я конечно понимаю что скорость от этого тоже зависит, просто я подумал что речь о самих операциях и специально отметил, что все внешние воздействия как бы не в счёт в рамках моего вопроса )

DrOffset, про расположение в памяти, кэши и т.д согласен, но это я не принимал во внимание когда писал то сообщение.... Все эти вещи я обобщил одним "словом" сторонние эффекты которые как бы не в счёт в контексте того сообщения)

@DrOffset · 07.07.2020, 21:13

Не по теме:

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

Croessmah · 07.07.2020, 21:19

Не по теме:

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

Скажем если это фиксированный пул памяти, который возвращает указатель на голову и обновляет голову

Ну вот ты потрогал - вернул, потрогал, вернул - быстро.
А теперь в боевых условиях потрогал, вернул, снова трогаешь, а там уже кто-то другой её потрогал и уже не так быстро.
Так сказать, в тесте работал с горячей памятью, а в боевых условиях память не прогрета и алгоритм ведет себя не так.
К кешам это тоже относится. На одной машине алгоритм работает быстро, а на другой в кеш не залезает и работает медленнее. Или, например, всё работало хорошо, пока кто-то не переопределил способ аллокации памяти и, даже не трогая алгоритм, повлиял на его работу. Так что алгоритмы нужно тестировать именно в боевых условиях. Нет зависимости от внешних условий? Они всегда есть, без них никуда. Банально, вставка в начало вектора - O(n), а в начало списка O(1), но по факту, в зависимости от данных и их объема, вставка в вектор может работать быстрее. А потом, вдруг, бац и стали в списке узлы выделять из пула - может отразится на скорости, хотя алгоритм никто не менял. Ну или просто искать мелкий кусок стало проще, чем здоровенный для вектора.

@Undisputed · 07.07.2020, 22:01

Не по теме:

DrOffset, Croessmah, я понял что вы хотите мне сказать, спасибо) просто почему то подумал что будет что-то отличное от того что вы сказали мне сейчас... тогда получаются что любой бенчмарк лишён всякого смысла. Нет смысла делать бенчмарк т.к у каждого будет своя правда, но тем не менее, даже взрослые продукты делают эти бенчмарки, так ведь? ну да, они указывают на какой машине тестировали, но ничего не говорят про кеши, каким из веток выполнения компилятор отдал предпочтение (а-ля built in expect) и прочие штуки которые могут влиять на скорость... то есть если так подходить к этому вопросу тогда все бенчмарки пора бросать в корзину :)

@Avazart · 08.07.2020, 12:59

Сообщение от Алексей1153

, который может обнулять выделенный блок.

Я почему то считал что - нет, не может.
Единственное исключение скорее всего в дебаг сборке.

@bedvit 1195 / 247 / 21 Регистрация: 20.05.2016 Сообщений: 1,084 Записей в блоге: 21
	07.07.2020, 16:54 [ТС]	21
	Алексей1153, после нескольких итераций malloc + free впереди (поправил пост), но отстаивание new небольшое. Протестируете у себя? Добавлено через 1 минуту А вообще каждый раз разный результат, иногда new выигрывает. Вообщем разница небольшая у меня (VS2017) 0

@bedvit 1195 / 247 / 21 Регистрация: 20.05.2016 Сообщений: 1,084 Записей в блоге: 21
	07.07.2020, 17:22 [ТС]	23
	У меня new no init: 37377618 new init: 79365468 malloc: 37378826 calloc: 120207779 т.е. new вполне сравним c malloc. calloc как и предполагалось медленнее. 0

Алексей1153 фрилансер 5846 / 5377 / 1103 Регистрация: 11.10.2019 Сообщений: 14,376
	07.07.2020, 17:29	24
	Сообщение от Алексей1153 с включенной оптимизацией я подозреваю, что с оптимизацией malloc и calloc вообще были выкинуты 0

Алексей1153 фрилансер 5846 / 5377 / 1103 Регистрация: 11.10.2019 Сообщений: 14,376
	07.07.2020, 17:38	26
	DrOffset, да, wandbox подтверждает ) А первый сайт упал, не могу зайти туда 0

@DrOffset 19409 / 10028 / 2443 Регистрация: 30.01.2014 Сообщений: 17,678
	07.07.2020, 17:40	27
	Алексей1153, https://rextester.com/DJU13619 https://rextester.com/QDM23956 Можно кстати воочию увидеть насколько в linux лучше реализация malloc по умолчанию. Одна из самых производительных на стандартных задачах. 0

@Undisputed
	07.07.2020, 18:28 #28
	Не по теме: думаю лучше на сайтиках не мерить производительность так как это чужая машина и мы не знаем что происходит на ней в момент наших эксперементов... может сложиться такая ситуация: первый тест отработал когда машина была свободная (но в целом код первого теста медленнее чем код второго теста) а когда более быстрый код (тест) начал выполняться, удаленная машина резко получила кучу задач и наш тест неоднократно уходил на задний план... в итоге можем получить обманчивые результаты. Но конечно же если разница слишком большая то скорее всего подобных проблем наблюдать не будем 0

Croessmah
	07.07.2020, 19:21 #29
	Не по теме: Undisputed, такие тесты вообще бесполезно делать в отрыве от задачи и остального кода. 0

@Undisputed
	07.07.2020, 19:56 #30
	Не по теме: Croessmah, интересно... а почему бесполезно? Ведь скажем если мы тестируем например два разных алгоритма которые решают одинаковую задачу, то разве более быстрый алгоритм на тестах не окажется более быстрым и в боевых условиях? говоря об этом я не принимаю во внимание сторонние эффекты которые зависят от окружающей среды, а речь чисто об оценке работы самого алгоритма...или я что то не так понял? 0

@DrOffset
	07.07.2020, 20:05 #31
	Не по теме: Сообщение от Undisputed разве более быстрый алгоритм на тестах не окажется более быстрым и в боевых условиях? запросто. в боевых условиях может быть, например, специфический набор данных, который вгонит быстрый в среднем алгоритм в худший случай. 0

@Undisputed
	07.07.2020, 20:36 #32
	Не по теме: DrOffset, да, если скорость работы алгоритма зависит от данных... в таком случае причины сравнительных тормозов понятны, но так как это не уточнялось, я думал что речь идёт в том числе и о тех случаях когда скорость работы алгоритма независит от данных 0

Croessmah
	07.07.2020, 20:42 #33
	Не по теме: Сообщение от Undisputed да, если скорость работы алгоритма зависит от данных... Если не зависит, то можно в compile-time подсчитать. ) 0

@DrOffset
	07.07.2020, 20:49 #34
	Не по теме: Сообщение от Undisputed я думал что речь идёт в том числе и о тех случаях когда скорость работы алгоритма независит от данных Я полагаю, что она всегда зависит от данных, если данные вообще есть. * От характера данных, т.е. от самих значений. * От объема данных. * Даже от расположения в памяти данных может зависеть. Т.е. O-оценка алгоритма это хорошо, но по факту в это может вмешиваться множество разных факторов и буквально на практике перекраивать предварительные оценки. Поэтому профайлер - наш друг :) 0

Croessmah
	07.07.2020, 20:59 #35
	Не по теме: DrOffset, и еще от порядка работы, производимых до и после алгоритма операций, и, естественно, от параллельно работающих потоков. 0

@Undisputed
	07.07.2020, 21:09 #36
	Не по теме: Croessmah, Не всегда же в compile time можно все упаковать что работает за О(1). Скажем если это фиксированный пул памяти, который возвращает указатель на голову и обновляет голову (ставит новый свободный блок памяти в голову). Работает за О(1), при этом это функция времени выполнения... и попадания в кэш и т.д не считается. Нет я конечно понимаю что скорость от этого тоже зависит, просто я подумал что речь о самих операциях и специально отметил, что все внешние воздействия как бы не в счёт в рамках моего вопроса ) DrOffset, про расположение в памяти, кэши и т.д согласен, но это я не принимал во внимание когда писал то сообщение.... Все эти вещи я обобщил одним "словом" сторонние эффекты которые как бы не в счёт в контексте того сообщения) 0

@DrOffset
	07.07.2020, 21:13 #37
	Не по теме: Undisputed, даже если не брать в расчет аппаратуру, средняя нагрузка на оптимальный казалось бы алгоритм в реальных условиях может быть выше или ниже протестированных условий и спрогнозированных ожиданий. Программисты очень часто ошибаются в этих вещах, поэтому лучше тестировать на реальной нагрузке. 0

Croessmah
	07.07.2020, 21:19 #38
	Не по теме: Сообщение от Undisputed Скажем если это фиксированный пул памяти, который возвращает указатель на голову и обновляет голову Ну вот ты потрогал - вернул, потрогал, вернул - быстро. А теперь в боевых условиях потрогал, вернул, снова трогаешь, а там уже кто-то другой её потрогал и уже не так быстро. Так сказать, в тесте работал с горячей памятью, а в боевых условиях память не прогрета и алгоритм ведет себя не так. К кешам это тоже относится. На одной машине алгоритм работает быстро, а на другой в кеш не залезает и работает медленнее. Или, например, всё работало хорошо, пока кто-то не переопределил способ аллокации памяти и, даже не трогая алгоритм, повлиял на его работу. Так что алгоритмы нужно тестировать именно в боевых условиях. Нет зависимости от внешних условий? Они всегда есть, без них никуда. Банально, вставка в начало вектора - O(n), а в начало списка O(1), но по факту, в зависимости от данных и их объема, вставка в вектор может работать быстрее. А потом, вдруг, бац и стали в списке узлы выделять из пула - может отразится на скорости, хотя алгоритм никто не менял. Ну или просто искать мелкий кусок стало проще, чем здоровенный для вектора. 0

@Undisputed
	07.07.2020, 22:01 #39
	Не по теме: DrOffset, Croessmah, я понял что вы хотите мне сказать, спасибо) просто почему то подумал что будет что-то отличное от того что вы сказали мне сейчас... тогда получаются что любой бенчмарк лишён всякого смысла. Нет смысла делать бенчмарк т.к у каждого будет своя правда, но тем не менее, даже взрослые продукты делают эти бенчмарки, так ведь? ну да, они указывают на какой машине тестировали, но ничего не говорят про кеши, каким из веток выполнения компилятор отдал предпочтение (а-ля built in expect) и прочие штуки которые могут влиять на скорость... то есть если так подходить к этому вопросу тогда все бенчмарки пора бросать в корзину :) 0

@Avazart 8483 / 6150 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	08.07.2020, 12:59	40
	Сообщение от Алексей1153 , который может обнулять выделенный блок. Я почему то считал что - нет, не может. Единственное исключение скорее всего в дебаг сборке. 0