LINUX.ORG.RU

C++ жадина или я дурак? (проблема с delete)

 , ,


0

4

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

namespace Brevity {

    template <class T> class List {

    public:

        List();
        ~List();
        void add(T data);
        bool remove(size_t ind);
        bool swap(size_t src, size_t dst);
        size_t count();
        T *get(size_t ind);

    private:

        class Node {

        public:
            Node(T data);
            T data;
            Node *prev;
            Node *next;

        };

        Node *head;
        size_t length;
        Node *getNode(size_t ind);

    };

    template <class T> List<T>::Node::Node(T data) {
        this->data = data;
        this->prev = NULL;
        this->next = NULL;
    }

    template <class T> List<T>::List() {
        this->length = 0;
        head = NULL;
    }

    template <class T> List<T>::~List() {
        while (this->length > 0) {
            this->remove(0);
        }
    }

    template <class T> void List<T>::add(T data) {
        List::Node *newNode = new List::Node(data);
        if (this->length == 0) {
            newNode->prev = newNode;
            newNode->next = newNode;
            this->head = newNode;
        } else {
            newNode->prev = this->head->prev;
            newNode->next = this->head;
            this->head->prev->next = newNode;
            this->head->prev = newNode;
        }
        this->length++;
    }

    template <class T> bool List<T>::remove(size_t ind) {
        List::Node *curNode = List::getNode(ind);
        if (curNode == NULL) {
            return false;
        } else {
            if (ind == 0) {
                this->head = curNode->next;
            }
            if (this->length > 1) {
                curNode->prev->next = curNode->next;
                curNode->next->prev = curNode->prev;
            }
            delete curNode;
            this->length--;
            return true;
        }
    }

    template <class T> bool List<T>::swap(size_t src, size_t dst) {
        List::Node *srcNode, *dstNode;
        srcNode = List::getNode(src);
        dstNode = List::getNode(dst);
        if (srcNode == NULL || dstNode == NULL) {
            return false;
        } else {
            T tmp;
            tmp = srcNode->data;
            srcNode->data = dstNode->data;
            dstNode->data = tmp;
            return true;
        }
    }

    template <class T> typename List<T>::Node* List<T>::getNode(size_t ind) {
        if (this->length <= ind) {
            return NULL;
        } else {
            List::Node *curNode;
            size_t curInd;
            int increment;
            if (ind <= (size_t) (this->length / 2)) {
                curNode = this->head;
                curInd = 0;
                increment = 1;
            } else {
                curNode = this->head->prev;
                curInd = this->length - 1;
                increment = -1;
            }
            while (curInd != ind) {
                curNode = (increment > 0) ? curNode->next : curNode->prev;
                curInd += increment;
            }
            return curNode;
        }
    }

    template <class T> size_t List<T>::count() {
        size_t count = this->length;
        return count;
    }

    template <class T> T *List<T>::get(size_t ind) {
        return &List::getNode(ind)->data;
    }

}

int main(){

    Brevity::List <size_t > myList;
    for (size_t i = 0; i < 10000000; ++i) {
        myList.add(i);
    }

    for (size_t i = 0; i < 10000000; ++i) {
        myList.remove(0);
    }

    char a;
    std::cin >> a;

    for (int i = 0; i < myList.count(); ++i) {
        std::cout << *myList.get((size_t) i) << " ";
    }

}

точнее не отдает ее ОС после удаления узла из списка, судя по таск менеджеру, а только лишь после выхода. В чем может быть дело, друзья, что я делаю не так?:)

Почитай как работает аллокатор.

P.S. простыню не читал.

hateyoufeel ★★★★★ ()

Насколько я знаю, delete не обязан возвращать память операционной системе; оно просто помечает память как доступную для следующих new этого процесса. Иначе бы вызов new, delete порождал бы дикую фрагментацию. И это не фишка C++, это поведение операционной системы.

Но это не memory leak. Сделай new, delete, new - количество потребляемой памяти не увеличится.

Kroz ★★★★★ ()
Ответ на: комментарий от Kroz

Но это не memory leak. Сделай new, delete, new - количество потребляемой памяти не увеличится.

Да, читал, пробовал, заметил, но может быть есть варианты обхода подобного поведения? Суть просто такова что ожидается очень активная работа с блоками памяти и лист это лишь малая доля всего проекта

zasyadko ()
Ответ на: комментарий от zasyadko

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

anonymous ()
Ответ на: комментарий от Dron

на самом бы деле с большой радостью продолжил бы Сишничать, если б не одно но, классами уж больно удобно оперировать)

zasyadko ()

что я делаю не так?

Не используешь std::list

yoghurt ★★★★★ ()
  • Не пиши свой список
  • Проверить лик это или нет можно с помощью valgrind:
    valgrind --leak-check=full ./your_bin
    
BruteForce ★★★ ()

Написал для своих задач реализацию листа

Видимо у сишников происходит деформация личности на фоне отсутствия стандартной библиотеки в си. А потом обмазывают всё своими велосипедами.

ox55ff ★★★★ ()
Ответ на: комментарий от MimisGotAPlan

Если он хочет изучить плюсы, а не си с классами, то ему лучше начать со стандартной библиотеки. Там кстати и аллокаторы есть. А пока это похоже на замену void* на template<class T> и malloc/free на new/delete.

ox55ff ★★★★ ()

Написал для своих задач реализацию листа

Нахрена?

annulen ★★★★★ ()

Реализация, надо заметить, не только бесполезная, но и не то чтобы сильно качественная

Softwayer ★★ ()
Ответ на: комментарий от pftBest

Как будто плохое что. Хаскелисты вон и в 2027 продолжат им пользоваться.

Softwayer ★★ ()

Тут уже все написали: переставай велосипедить и начинай пользоваться инструментными адекватными задаче.

buddhist ★★★★★ ()
Ответ на: комментарий от zasyadko

И в чем проблема? Тебе же говорят, что память все равно остается в рамках твоего процесса, не разрастается лишний раз.

Если хочешь прямо все контролировать, то самый простой вариант — выдели себе в начале один или несколько (по количеству возможных типов данных, например) больших блоков памяти, а внутри них уже сам выделяй/освобождай место.

buddhist ★★★★★ ()

В чем может быть дело, друзья, что я делаю не так?:)

В цепепе :-) Ведь когда ты кодил на Си, у тебя таких вопросов не возникало :-) Ты ясно представлял себе, что же на самом деле делает твой код :-) Теперь ты открыл для себя цепепе, полный сюрпризов и неожиданностей :-) Теперь главное не то, что же делает программа, а то, насколько код соответствует гайдалайнам от цепепе-гуру разных мастей :-) Ведь для того, чтобы писать на цепепе в «хорошем стиле» нужно быть хорошим зубрилкой :-) Теперь важно изучить тонну скучных книг про всякие там RAII с исключениями, про всякую шаблонную лабуду, открыть pdf стандарта с 1500 страниц и радоваться новым открытиям, как то, о которым ты объявил здесь :-) Лол :-)

anonymous ()
Ответ на: комментарий от annulen

vector (или в крайнем случае deque). связные списки годятся только чтоб сэкономить немножко памяти. Хотя и это тоже спорно, потому что на список придется хранить +8 байт каждый элемент, а вектор в худшем случае будет только в 1.5 больше своего размера.

pftBest ★★★★ ()
Последнее исправление: pftBest (всего исправлений: 1)

zasyadko, не слушай этих диванных кукаретиков, 19 ответов, ни одного по теме. На сях то же самое поведение, просто ты не замечал. Виноват системный аллокатор. Используй `include <malloc.h>' (или что там соответствует в с++), в нем функция `malloc_trim(0);' Она просит системный аллокатор оставить в резерве N байт. Вызваешь, система отдает в пул обратно то что скопилось в куче уже освобожденного. Учти, что маны по ней очень старые, надо смотреть сорцы. Ну или вот, почитать.

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

PPP328 ★★★★ ()
Ответ на: комментарий от ox55ff

Там кстати и аллокаторы есть

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

kawaii_neko ★★★★ ()
Ответ на: комментарий от pftBest

связные списки годятся только чтоб сэкономить немножко памяти

Вот эт новости. А раньше ими пользовались для быстрой вставки...

anonymous ()
Ответ на: комментарий от anonymous

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

Silerus ★★★ ()
Ответ на: комментарий от Silerus

странно насколько я помню в связных списках быстро происходит операции добавить/удалить/заменить первый элемент.

Не «быстро», а за константное время :-) И любой элемент списка :-)

Во всех остальных случаях мы вынужденны проверять все элементы списка пока не найдем нужный

Не следует путать операции поиска и, собственно, вставки/удаления :-)

anonymous ()
Ответ на: комментарий от Silerus

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

вынужденны

А вот так писать вообще пошло и мерзко.

MimisGotAPlan ()
Ответ на: комментарий от pftBest

vector (или в крайнем случае deque)

в тех случаях, когда нужен список, от вектора толку ноль

annulen ★★★★★ ()
Ответ на: комментарий от anonymous

А раньше ими пользовались для быстрой вставки...

Ты еще splice забыл

annulen ★★★★★ ()
Ответ на: комментарий от zasyadko

худший случай перебора О(N/2)

Где переход по каждому элементу будет cache miss, и пока ты доберешься до середины списка, vector уже давно успеет все скопировать.

pftBest ★★★★ ()
Ответ на: комментарий от MimisGotAPlan
  1. Про векторы мы не говорим. Что они медленные в режиме вставка - известно всем, исключением могут являться векторы, которые заранее выделяют дополнительную память для своих нужд. Но зато мы имеем доступ к значению на уровне обычного массива, что не возможно в случае списка.
  2. Об итераторах и указателях должен позаботится сам программист. Если он этого не сделал - то O(n) на операцию. В случае с std::list на 1 и последний элемент вроде есть указатель всегда - спасибо им.
Silerus ★★★ ()
Ответ на: комментарий от Silerus

Про векторы мы не говорим. Что они медленные в режиме вставка - известно всем,

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

pftBest ★★★★ ()
Ответ на: комментарий от pftBest

Объясни почему не понимаю. Если вектор не выделяет запас памяти, то его алгоритм должен быть примерно таков:

  1. создать новый массив
  2. скопировать туда кусок предыдущего
  3. вставить новое значение
  4. скопировать все остальное
  5. отдать указатель на новый объект
  6. очистить старый объект

список

  1. найти место вставки
  2. соседу сверху отдать указатель на новый элемент
  3. новому элементу указать на соседа снизу
Silerus ★★★ ()
Ответ на: комментарий от pftBest

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

zasyadko ()
Ответ на: комментарий от Kroz

Насколько я знаю, delete не обязан возвращать память операционной системе; оно просто помечает память как доступную для следующих new этого процесса.

Да.

И это не фишка C++, это поведение операционной системы.

Чушь. Даже не проводя лекцию как осуществляется работа с изменением размера памяти процессу ядром, можно увидеть, что чушь получается у вас с тривиальным доказательством: new/delete у вас в ОС следует из первого предложения :)

vodz ★★★★★ ()
Ответ на: комментарий от PPP328

Виноват системный аллокатор. Используй `include <malloc.h>' (или что там соответствует в с++), в нем функция `malloc_trim(0);' Она просит системный аллокатор оставить в резерве N байт.

Лол :-) А с чего это ты такой уверенный, что new взял память от системного аллокатора? :-) Кто сказал, что new реализован на базе malloc() в данной конкретной системе? :-) Если советуешь malloc_trim(), то советуй уж malloc()/free() вместо new/delete :-) То есть Си вместо цепепе :-) Сказал «а», скажи и «б», как говорится :-)

anonymous ()
Ответ на: комментарий от Silerus

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

Объясни почему не понимаю.

Все верно, просто надо учитывать особенности работы современных процессоров. Обращение к оперативной памяти в 20 - 200 раз дольше чем обращение в кеш.

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

Вот например график

https://kjellkod.files.wordpress.com/2012/02/pod_x64_10k_elements.png

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

pftBest ★★★★ ()
Последнее исправление: pftBest (всего исправлений: 1)
Ответ на: комментарий от Silerus

список
найти место вставки

Тут уже вам намекали, что поиск тут не следует учитывать как присущее списку обязательное действие, для двухсвязанного списка ничего искать дополнительно не надо если есть задача: вставить после этого элемента, как-либо найденного ранее. Да, поиск N-го элемента у списка медленнее, но тогда и в вектор можно временно преобразовать при необходимости.

vodz ★★★★★ ()
Ответ на: комментарий от vodz

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

Silerus ★★★ ()
Ответ на: комментарий от zasyadko

а большинство операций планируется производить с головой и хвостом

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

pftBest ★★★★ ()
Ответ на: комментарий от anonymous

Я тебя расстрою, анон, но если он не юзает какую-нибудь экзотическую ардуину со своим собственным xxxlibc++ то new/delete там будет на основе malloc. Потому что ни один нормальный человек не будет дублировать один и тот же функционал в двух функциях.

The details of how operator new is implemented are property of a particular implementation of standard library - not even a compiler or operation system. I am familiar with one (gnu) and aware of 3 others - CLang, Apache and MSFT. All of them are using malloc() within operator new, because it just makes a life of library developer so much easier.

If malloc() were not used, said developer would have to reimplement a lot in terms of memory allocation, and sprinkle the code heavily with OS-dependent logic to actually request memory. No one wants to do this when malloc() is already there. But by no means they are obliged to use it.

https://stackoverflow.com/a/34813830/2932207

PPP328 ★★★★ ()
Ответ на: комментарий от Silerus

вы не внимательны, я спрашивал почему вектор может быть быстрее при вставке,

Нет, это вы невнимательны, так как я вам дал ещё один аргумент, почему последующее объяснение — типичная подгонка под желаемое. Ибо вначале надо зафиксировать условие: что нам надо — много последовательного поиска или много вставок. И куда пойдёт кеш при втором...

vodz ★★★★★ ()
Ответ на: комментарий от PPP328

Я тебя расстрою, анон, но если он не юзает какую-нибудь экзотическую ардуину со своим собственным xxxlibc++ то new/delete там будет на основе malloc. Потому что ни один нормальный человек не будет дублировать один и тот же функционал в двух функциях.

Ты меня не расстроил :-) Лол :-) Ты просто процитировал надпись на общеизвестном сайтишке, которая описывает частный случай объективной реальности :-) С другой стороны, стандарт цепепе, которым так кичатся цепепе писатели, нигде не предписывает, что new/delete обязан быть реализован на основе malloc()/free() :-) Прочитав тех же Страуструпа и Саттера, ты обнаружишь для себя, что эти известные авторы гайдлайнов и прочих «стандартов кодирования» также говорят о new/delete как о неких абстрактных операторах выделения/высвобождения оперативной памяти :-) Это правила игры для всех, кто пишет на C++ :-) Т.е. либо эти правила соблюдаются, и тогда можно гордиться званием «программиста на си плас плас», либо эти правила признаются никому не нужными (как и цепепе), и тогда работают правила старого доброго Си с его malloc(), free() и прочего прочего :-)

anonymous ()
Ответ на: комментарий от KennyMinigun

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

Вот интереснее:
https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

invy ★★★★★ ()
Последнее исправление: invy (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.