Неожиданное потребление памяти

#cpp

Пишу алгоритм бинарной сортировки (в целях обучения).
Компилятор - MinGW-w64 с флагом оптимизации -o0

Дело в том, что мой код потребляет больше памяти чем я ожидаю..

Структура { ключ, значение, указатель на левого и правого предка }
При использовании типов size_t в первом и втором значении в x64 системе логично предположить
что итоговый размер структуры - 8+8+8+8 = 32 байта
Но на деле при создании 100 000 000 объектов приложение кушает не 3.0гб а 4.5гб,
что существенно выше ожидаемого.

Про выравнивание памяти читал и использование #pragma pack(push,1) в глобальной области
никак не влияет на ситуацию (что впрочем логично, структура то ровная).

Так же я использовал дополнительную функцию для выделения памяти через malloc, так
как мне подсказали что проблема может быть при вызовах new. 
К сожалению это так же не помогло, но по крайней мере дало возможность следить за
размером выделяемой памяти во время исполнения.. Из чего я сделал вывод что размер
выделяемой памяти корректен - 3 200 000 000 байт, по крайней мере на этапе выделения.

То есть вероятнее всего это всё таки какая-то оптимизация компилятора.
Однако при создании простого массива 32 байтных структур приложение потребляет столько
сколько нужно. Следовательно дело в логике выделения памяти (функция Insert(...))

Код который я использую:
    size_t memCount = 0;

template
Type* Alloc(Args... args)
{
    uint8* result = reinterpret_cast(malloc(sizeof(Type)));
    memCount += sizeof(Type);
    if(result)
        return new(reinterpret_cast(result)) Type(args...);
    return nullptr;
}

template
class Node
{
private:

    kType key;
    Type value;

    Node* left;
    Node* right;

public:

    explicit Node(const kType& key,
                  const Type& value) : key(key),
                                 value(value),
                                 left(nullptr),
                                 right(nullptr) { }
    ~Node()
    {
        if(left)  delete left;
        if(right) delete right;
    }

    const bool Insert(const kType& key, const Type& value, const kType& min, const
kType& max)
    {
        if(min == max)
            return false;

        kType halfMax = (max - min) / 2 + min;

        if(key < halfMax)
        {
            if(!left)
            {
                left = Alloc(key, value);
                return true;
            }
            else
                return left->Insert(key, value, min, halfMax);
        }
        else
        {
            if(!right)
            {
                right = Alloc(key, value);
                return true;
            }
            else
                return right->Insert(key, value, halfMax, max);
        }

        return true;
    }
};

int main(void)
{
    Node* arr = Alloc>(0, 0);
    for(size_t x = 1; x < 100000000; x++)
        arr->Insert(x, x, numeric_limits::min(),
                          numeric_limits::max());

    cout <<  "mem - "<< memCount << endl; // здесь видим 3 200 000 000 (2,9гб), как
и должно было быть
    system("pause");
    return 0;
};

    

Ответы

Ответ 1

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

Если допустить, что под это отводится ещё байт 8 (но я не знаю ни компилятор, ни
среду, поэтому могу только гадать), то общий размер потребляемой памяти приближается
к наблюдаемому.

Что делать? 


Попробовать другой аллокатор jmalloc, tmalloc.
Написать свой аллокатор:)
Использовать placement new. В результате можно будет выделить 3 гигабайта и разместить
там все объекты (если только это 64битная система, на 32битной врядли)
Перестать беспокоиться и смириться.