Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.50/6: Рейтинг темы: голосов - 6, средняя оценка - 4.50
653 / 323 / 68
Регистрация: 10.06.2014
Сообщений: 2,278
1

Почему в данном случае работа с заранее выделенной памятью медленнее чем с динамической?

12.12.2016, 18:47. Просмотров 1157. Ответов 38
Метки нет (Все метки)

Написал функцию которая на основе списка выделяет память и при каждом вызове возвращает указатель на следующий элемент для объекта.
Код где используется заранее выделенная память обернул в std::chrono::nanoseconds, что бы получить время исполнения с помощью вычисления разности ДО и ПОСЛЕ выполнения. Вариант с заранее выделенной памятью почему то оказался медленнее

Вариант с заранее выделенной памятью (результат: http://rextester.com/FNDGT52360)
под спойлером так же есть код
Кликните здесь для просмотра всего текста

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
#include <chrono>
#include <iostream>
 
struct list
{
    list *next;
};
 
class Test
{
    public:
    int a;
    int b;
};
 
void* getPtr()
{
    static int init = 0;
    static list *head;
    static list *free;
    if (!init) {
        init = 1;
        list *head = reinterpret_cast<list*>(new char(sizeof(Test)));
        free = head;
        for (int i = 0; i < 10000000; i++) {
            head->next = reinterpret_cast<list*>(new char(sizeof(Test)));
            head = head->next;
        }
    }
    
    list *ret = free;
    free = ret->next; 
    return ret;
}
 
int main()
{
    auto begin = std::chrono::high_resolution_clock::now();
    for(int i = 0; i < 10000000; i++) { 
         new(getPtr())Test();
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout<<std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count()<<" ns"<< std::endl;
}

Вариант без использования заранее выделенной памяти и placement new http://rextester.com/FVC18352
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <chrono>
#include <iostream>
 
class Test
{
    public:
    int a;
    int b;
};
 
int main()
{
    auto begin = std::chrono::high_resolution_clock::now();
    for(int i = 0; i < 10000000; i++) {
         new Test();
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout<<std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count()<<" ns"<< std::endl;
}

Почему так происходит? Вроде бы выриант с заранее выделенной памятью должен быть быстрее, а здесь наоборот
Хуже того, если функцию getPtr объявить как inline, то работает ещё медленнее

Добавлено через 1 час 9 минут
Проверил одну версию. Подумал тормоза возникают из за того что первый вызов функции, который приводит к инициализации списка находится в цикле. Вынес его из цикла, так ещё медленнее стало! В функции getPtr вывел запись Initialized что бы убедиться в том, что инициализация происходит всего один раз.
http://rextester.com/DOS20329

Откуда эти тормоза? Ведь по при вызове функции переставляется указатель на следующий свободный элемент и возвращается указатель на текущий свободный элемент списка и подставляется в placement new
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.12.2016, 18:47
Ответы с готовыми решениями:

Работа с памятью, выделенной malloc
Доброго времени суток! Есть следующая проблема: Выделяем кусок памяти из кучи: void...

Размер выделенной динамической памяти больше чем ожидается
der operator+(char *x) //obj + строка { der newObj; int y=strlen(_name)+strlen(x)+1; ...

Работа с памятью: адресация выделенной области памяти
Привет, ребят! Допустим я создал (выделил) какой-то участок памяти (функция 48h).. Вооот И мне...

Работа с динамической памятью
Создаю указатели char *s,*p; s = (char *)malloc(sizeof(char)); потом p = (char *)realloc(s,...

38
498 / 348 / 93
Регистрация: 22.03.2011
Сообщений: 1,107
12.12.2016, 20:01 2
Причин может быть много, начиная от банальной оптимизации - выкидывание цикла который ничего не делает. Дизассемблируте код смотрите что оставил Вам компилятор.

П.С. Ну и вынесите аллокацию за цикл.

Добавлено через 6 минут
Ну и почитайте что такое ПУЛ памяти. Ибо у Вас выдиление идет через постоянной нью

Добавлено через 2 минуты
П.С.С. Ну и почитайте что тако спискок и как он организован.
0
653 / 323 / 68
Регистрация: 10.06.2014
Сообщений: 2,278
12.12.2016, 20:05  [ТС] 3
Цитата Сообщение от stima Посмотреть сообщение
П.С. Ну и вынесите аллокацию за цикл.
Уже. Хуже работать стало

Цитата Сообщение от stima Посмотреть сообщение
Ибо у Вас выдиление идет через постоянной нью
память у меня в коде выделяется всего один раз, и это выделение находится за пределами цикла

Цитата Сообщение от stima Посмотреть сообщение
Ну и почитайте что тако спискок и как он организован.
Как это мне поможет если я и так знаю что такое список иначе как написал код то?

Цитата Сообщение от stima Посмотреть сообщение
Дизассемблируте код смотрите что оставил Вам компилятор.
Ассемблер не знаю
0
498 / 348 / 93
Регистрация: 22.03.2011
Сообщений: 1,107
12.12.2016, 20:15 4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void* getPtr()
{
    static int init = 0;
    static list *head;
    static list *free;
    if (!init) {
        init = 1;
        list *head = reinterpret_cast<list*>(new char(sizeof(Test))); // Это каким макаром Test стал списком?
        free = head;
        for (int i = 0; i < 10000000; i++) {
            head->next = reinterpret_cast<list*>(new char(sizeof(Test))); // Это разве одна аллокация? 
            head = head->next;
        }
    }
    
    list *ret = free;
    free = ret->next; 
    return ret;
}
Добавлено через 36 секунд
Я Вам оставил коменты. И ссылку на вики что такое лист https://en.wikipedia.org/wiki/Linked_list

Добавлено через 3 минуты
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
#include <chrono>
#include <iostream>
 
const int count = 10;
 
struct Test
{
    int a;
    int b;
};
 
struct Node
{
    Node *next;
    Test  object;
};
 
Node *head;
 
void* getPtr()
{
    void *ret = &head->object;
    head = head->next;
    return ret;
}
 
int main()
{
    Node *it = head = new Node;
    for(int i = 1; i < count; ++i)
    {
        Node *node = new Node;
        node->next = nullptr;
 
        it->next = node;
        it = node;
    }
 
    auto begin = std::chrono::high_resolution_clock::now();
    for(int i = 0; i < count; i++)
    {
        new(getPtr())Test();
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count() <<" ns" << std::endl;
 
    return 0;
}
Это так если по быстрому.
1
653 / 323 / 68
Регистрация: 10.06.2014
Сообщений: 2,278
12.12.2016, 20:35  [ТС] 5
Цитата Сообщение от stima Посмотреть сообщение
Я Вам оставил коменты. И ссылку на вики что такое лист
А мне не нужен доп. элемент в списке ввиде Test
Изначально выделяется память для каждого элемента списка и его указатель записывается в next
Далее эти указатели используются один за другим
0
12170 / 6666 / 1611
Регистрация: 30.01.2014
Сообщений: 10,915
12.12.2016, 20:37 6
Цитата Сообщение от sys_beginner Посмотреть сообщение
Откуда эти тормоза?
Этот вопрос вторичен.
Для начала нужно исправить грубейшие ошибки при работе с памятью, которые порождают UB. Если в программе есть UB, то никакими метриками ее оценивать нельзя, т.к. все они заведомо могут быть скомпрометированы.

Добавлено через 1 минуту
Цитата Сообщение от sys_beginner Посмотреть сообщение
Изначально выделяется память для каждого элемента списка и его указатель записывается в next
У тебя выделяет память для одного char, который инициализируется значением sizeof(Test). Это вообще категорически неправильно в данной ситуации
1
653 / 323 / 68
Регистрация: 10.06.2014
Сообщений: 2,278
12.12.2016, 20:39  [ТС] 7
Цитата Сообщение от DrOffset Посмотреть сообщение
У тебя выделяет память для одного char, который инициализируется значением sizeof(Test). Это вообще категорически неправильно в данной ситуации
Только пофиксил, но результат не улучшился

http://rextester.com/PJZDT31640
0
12170 / 6666 / 1611
Регистрация: 30.01.2014
Сообщений: 10,915
12.12.2016, 20:42 8
Цитата Сообщение от sys_beginner Посмотреть сообщение
А мне не нужен доп. элемент в списке ввиде Test
Это не дополнительный элемент, а единственно необходимый элемент, именно в нем будет располагаться конструируемый в цикле объект в будущем. Правда конечно это должна быть "сырая" память, а не живой объект, т.к. перезапись через placement new его опять приведет нас к UB.

Добавлено через 2 минуты
Цитата Сообщение от sys_beginner Посмотреть сообщение
Только пофиксил, но результат не улучшился
Пофиксил, да не все.

Вот, сохранил твою идею: http://rextester.com/OGAH34638
0
653 / 323 / 68
Регистрация: 10.06.2014
Сообщений: 2,278
12.12.2016, 20:56  [ТС] 9
Цитата Сообщение от DrOffset Посмотреть сообщение
Это не дополнительный элемент, а единственно необходимый элемент, именно в нем будет располагаться конструируемый в цикле объект в будущем
Не понимаю, зачем он нужен, если каждому next-у мы уже присваиваем сырую память и используем её

Цитата Сообщение от DrOffset Посмотреть сообщение
Вот, сохранил твою идею:
Спасибо. Но без пула все равно быстрее http://rextester.com/FGXEL75662
0
12170 / 6666 / 1611
Регистрация: 30.01.2014
Сообщений: 10,915
12.12.2016, 21:02 10
Лучший ответ Сообщение было отмечено Undisputed как решение

Решение

Цитата Сообщение от sys_beginner Посмотреть сообщение
Не понимаю, зачем он нужен
А объект-то ты где будешь размещать? Или выделяй тогда sizeof(Test) + sizeof(list *), и смещайся потом относительно размера указателя. Но это будет эквивалентно использованию структуры с полем memory, только гораздо менее читаемо и более ошибкоопасно.

Цитата Сообщение от sys_beginner Посмотреть сообщение
Но без пула все равно быстрее
Вообще-то нет. Ты в разрядах не запутался?
Вариант без пула дает в среднем 36 ns на аллокацию: http://rextester.com/EEDX84367
Вариант с пулом, в среднем 4 ns: http://rextester.com/UQQPD30215
1
653 / 323 / 68
Регистрация: 10.06.2014
Сообщений: 2,278
12.12.2016, 21:17  [ТС] 11
Цитата Сообщение от DrOffset Посмотреть сообщение
А объект-то ты где будешь размещать?
Я вижу это так: каждый next списка это указатель, так?
В цикле для каждого next-а который является указателем выделяется память с помощью new char, равная размеру объекта. В итоге получаем указатель который указывает на область размером sizeof(Test)
Далее по необходимости указатели возвращаются один за другим

Разве тут есть ошибка?
0
12170 / 6666 / 1611
Регистрация: 30.01.2014
Сообщений: 10,915
12.12.2016, 21:20 12
Цитата Сообщение от sys_beginner Посмотреть сообщение
Разве тут есть ошибка?
Есть.
Указатель у тебя находится "внутри" области памяти, которую ты выделил (смотрим на reinterpret_cast). В итоге этот указатель потом будет перетёрт объектом Test. Зачем нужна такая структура данных, которая сама себя уничтожает?
0
653 / 323 / 68
Регистрация: 10.06.2014
Сообщений: 2,278
12.12.2016, 21:27  [ТС] 13
Наверное туплю, но не могу понять.
Цитата Сообщение от DrOffset Посмотреть сообщение
Указатель у тебя находится "внутри" области памяти, которую ты выделил (смотрим на reinterpret_cast).
То есть? Разве когда используется new, сам указатель так же занимает место в выделенной области? Тогда всегда приходилось бы писать new[size + sizeof(void*)] sizeof(void*) - для указателя. Однако так не делают. Не понимаю...
0
12170 / 6666 / 1611
Регистрация: 30.01.2014
Сообщений: 10,915
12.12.2016, 21:35 14
Цитата Сообщение от sys_beginner Посмотреть сообщение
То есть? Разве когда используется new, сам указатель так же занимает место в выделенной области? Тогда всегда приходилось бы писать new[size + sizeof(void*)] sizeof(void*) - для указателя. Однако так не делают. Не понимаю...
Вот выделил ты sizeof(Test) char`ов.
Потом взял и наглым образом сказал, что этот массив является структурой list. Внутри которой находится указатель next.
Далее что ты делаешь? Записываешь в этот указатель адрес следующего элемента.
Потом что ты делаешь? Возвращаешь очередной list в качестве памяти свободной для размещения. Итого у тебя действительно есть память, пригодная для размещения объекта Test, но указатель next, который был там записан теперь безвозвратно утерян. Одноразовая структура получилась, ничего больше сделать с ней нельзя, например если ты захочешь вернуть элемент списка обратно в пул, то ты не сможешь это сделать, т.к. его адресация утеряна.

Добавлено через 2 минуты
Цитата Сообщение от DrOffset Посмотреть сообщение
Разве когда используется new, сам указатель так же занимает место в выделенной области?
Тот указатель, который тебе вернула new - не занимает. Но занимает тот, который ты сам там размещаешь - это next.
Итого у тебя элемент списка - это одновременно и память и структура данных для организации этой памяти. Но так не бывает. Ты или едешь, или шашечки ждешь.
1
653 / 323 / 68
Регистрация: 10.06.2014
Сообщений: 2,278
12.12.2016, 21:46  [ТС] 15
Цитата Сообщение от DrOffset Посмотреть сообщение
Одноразовая структура получилась, ничего больше сделать с ней нельзя, например если ты захочешь вернуть элемент списка обратно в пул, то ты не сможешь это сделать, т.к. его адресация утеряна.
А что мешает удаляемый элемент сразу разместить в голове списка(сохранили указатель, который может быть занят при следующей необходимости), а его next установить тот элемент который был свободным в последний раз, до того как мы вернули элемент в пул

Добавлено через 5 минут
Цитата Сообщение от DrOffset Посмотреть сообщение
Тот указатель, который тебе вернула new - не занимает. Но занимает тот, который ты сам там размещаешь - это next.
Так next это как раз таки тот указатель который получается с помощью new, а он как ты сказал
Цитата Сообщение от DrOffset Посмотреть сообщение
Тот указатель, который тебе вернула new - не занимает.
0
12170 / 6666 / 1611
Регистрация: 30.01.2014
Сообщений: 10,915
12.12.2016, 21:50 16
Цитата Сообщение от sys_beginner Посмотреть сообщение
А что мешает удаляемый элемент сразу разместить в голове списка(сохранили указатель, который может быть занят при следующей необходимости), а его next установить тот элемент который был свободным в последний раз, до того как мы вернули элемент в пул
Да, можно так сделать, но тогда элементы меньшие, чем sizeof(void *), так хранить не получится. Т.к. при попытке записывать туда указатель будешь выходить за пределы доступной памяти. Для твоего случая это, конечно, будет работать.

Добавлено через 1 минуту
Цитата Сообщение от sys_beginner Посмотреть сообщение
Так next это как раз таки тот указатель который получается с помощью new, а он как ты сказал
Как ты умудряешься одновременно делать правильные выводы и совершенно абсурдные?
В общем, твоя схема с перезаписью будет работать, но то, что ты пишешь в процитированном, демонстрирует непонимание о чем я писал выше
Такие дела.
1
653 / 323 / 68
Регистрация: 10.06.2014
Сообщений: 2,278
12.12.2016, 21:54  [ТС] 17
Цитата Сообщение от DrOffset Посмотреть сообщение
Да, можно так сделать, но тогда элементы меньшие, чем sizeof(void *), так хранить не получится.
Ну проверки размера объекта никто не отменял )) если объект меньше чем размер указателя, можно форсить размер объекта как sizeof(void*) это и будет сайзом данных указателя

Цитата Сообщение от DrOffset Посмотреть сообщение
Как ты умудряешься одновременно делать правильные выводы и совершенно абсурдные?
Это как так? )) Алгоритм вроде рабочий

Но в чем ошибка была в моем коде кроме отсутствия квадратных скобок не догнал... я сейчас очень тупой, попробую завтра с утра глянуть твой код
0
12170 / 6666 / 1611
Регистрация: 30.01.2014
Сообщений: 10,915
12.12.2016, 22:14 18
Цитата Сообщение от sys_beginner Посмотреть сообщение
Это как так?
Как-как...
Вот пишешь ты:
Цитата Сообщение от sys_beginner Посмотреть сообщение
Так next это как раз таки тот указатель который получается с помощью new
next-то ты хранишь внутри list. И там он память занимает. Абсурдно утверждать иное, да еще и ссылаться на меня, относя мою фразу совсем к другой опере... При этом ты как-то умудрился выдать правильный ответ на мое замечание насчет перезатирания. И вот у меня вопрос: ты понимаешь что у тебя в памяти происходит или нет? Вопрос, естественно, риторический.

Но схема и правда рабочая, безотносительно твоих "непоняток". Это шаманизм в чистом виде: ты сделал что-то более-менее рабочее, но того как оно на самом деле работает до конца не понял

Вот твоя схема, работает, при желании:
http://rextester.com/XGS73196
Проблема объектов, меньших, чем sizeof(void*), тут, кстати, решена.
1
653 / 323 / 68
Регистрация: 10.06.2014
Сообщений: 2,278
12.12.2016, 22:32  [ТС] 19
Цитата Сообщение от DrOffset Посмотреть сообщение
Абсурдно утверждать иное
Не суди строго Я могу ошибаться в силу того что ещё совсем-совсем зеленый, недалекий Плюсы сложная штука...

Цитата Сообщение от DrOffset Посмотреть сообщение
next-то ты хранишь внутри list. И там он память занимает
Не понял Сейчас попробую рассказать как я это себе представляю

Насколько я понимаю, само выражение struct {...} это просто языковая конструкция, а память требуется для хранения её полей, ведь так? Когда мы пишем list *next то говорим, что там будет находится указатель. То есть после описания структуры ещё никакой указатель никуда не указывает.

В процессе выделения памяти заранее, мы выделяем память char[] и делаем каст, что бы успешно присвоить его next-у. Именно тогда next начинает уже указывать в конкретную область, но так как next это указатель который пришел от new, от находится отдельно от данных.
0
12170 / 6666 / 1611
Регистрация: 30.01.2014
Сообщений: 10,915
12.12.2016, 22:53 20
sys_beginner, плаваешь около истины, но еще не до конца. Нужен рисунок:
Код
 _________ sizeof (Test)________
/                               \
| x | x | x | x | x | x | x | x |
представим, что у нас самая-самая первая итерация построения списка.
Ты выделил sizeof(Test) байт, затем скастил указатель на них к list *. list (sizeof(list) == sizeof(list*)) у нас занимает меньше, чем Test, поэтому реально использоваться из 8 байт (sizeof(Test) == 8) будут только 4 (условимся, что у нас 32-битная платформа).
Теперь перейдем ко второй итерации, head у нас уже есть, и он указывает на прежде выделенные 8 байт, первые 4 байта из которых притворяются list`ом. Настала пора присвоить next`у head-элемента полученный на второй итерации указатель (тоже, предварительно скастованный к list`у).
Внимание вопрос: где будет располагаться этот адрес? Правильно в первых 4х байтах нашего буфера, который прячется за head указателем.
Код
 _________ sizeof (Test)________
/                               \
| ! | ! | ! | ! | x | x | x | x |
Отметил восклицательными знаками.
При записи туда объекта через placement new, естественно, этот адрес будет перезаписан. Ну это ты уже понимаешь, надеюсь, раз предложил выход из ситуации.

Собственно, об этом простом факте и была моя куча текста сверху...

Добавлено через 4 минуты
Цитата Сообщение от sys_beginner Посмотреть сообщение
указатель который пришел от new, от находится отдельно от данных.
Теперь ты понимаешь, почему он НЕ находится отдельно от данных? А использует место под данные (в предыдущем выделенном элементе списка) до поры до времени?
Т.е. отдельно от данных у тебя находится только самый-самый первый указатель, который в твоей реализации сидит в static области памяти. Все остальные next`ы используют ту область памяти, которую предполагается использовать под данные и будут утеряны при конструировании там объекта. Опять-таки, речь велась только об этом.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.12.2016, 22:53

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

Работа с динамической памятью
Здравствуйте, был в пятницу на собеседовании Задали такой вопрос - написать программму, которая бы...

Работа с динамической памятью!
Привет! Такая задача: Необходимо выделить(по N Кб) и освободить всю динамическую память. Определить...

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

Работа с динамической памятью.
Привет всем. Помогите пож-та с этим примером. Создать массив динамической памяти A(n).Найти сумму...

Работа с динамической памятью
Привет всем. Я недавно начал изучать C++ и наткнулся на ошибку:&quot;двумерный динам.exe вызвал...

Работа с динамической памятью
При вызове деструктора ошибка: &quot;Ошибка C2227 выражение слева от &quot;-&gt;next&quot; должно указывать на тип...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.