I am writing a binary sorting algorithm (for training purposes). Compiler - MinGW-w64 with optimization flag -o0

The fact is that my code consumes more memory than I expect ..

Structure {key, value, pointer to the left and right ancestor} When using size_t types in the first and second values ​​in the x64 system, it is logical to assume that the total size of the structure is 8 + 8 + 8 + 8 = 32 bytes. But in reality, when creating 100,000,000 Objects of the application does not eat 3.0GB and 4.5GB, which is significantly higher than expected.

I read about the alignment of memory and the use of #pragma pack (push, 1) in the global area does not affect the situation (which, incidentally, is logical, is a flat structure).

I also used an additional function to allocate memory through malloc, as I was told that the problem might be with new calls. Unfortunately, it also did not help, but at least made it possible to monitor the size of the allocated memory during execution .. From what I concluded that the size of the allocated memory is correct - 3,200,000,000 bytes, at least during the allocation phase.

That is, most likely it is still some kind of compiler optimization. However, when creating a simple array of 32 byte structures, the application consumes as much as needed. Therefore, it is a matter of the memory allocation logic (Insert (...) function)

The code I use is: size_t memCount = 0;

template<typename Type, typename... Args> Type* Alloc(Args... args) { uint8* result = reinterpret_cast<uint8*>(malloc(sizeof(Type))); memCount += sizeof(Type); if(result) return new(reinterpret_cast<Type*>(result)) Type(args...); return nullptr; } template<typename kType, typename Type> 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<Node>(key, value); return true; } else return left->Insert(key, value, min, halfMax); } else { if(!right) { right = Alloc<Node>(key, value); return true; } else return right->Insert(key, value, halfMax, max); } return true; } }; int main(void) { Node<size_t, size_t>* arr = Alloc<Node<size_t, size_t>>(0, 0); for(size_t x = 1; x < 100000000; x++) arr->Insert(x, x, numeric_limits<size_t>::min(), numeric_limits<size_t>::max()); cout << "mem - "<< memCount << endl; // здесь видим 3 200 000 000 (2,9гб), как и должно было быть system("pause"); return 0; };
  • As far as I remember, malloc usually adds 16 bytes of service data to the allocated memory. That's the difference 1.5 times. Get large blocks through malloc and already use your own allocator (it can be very simple if you don’t need to reuse memory) 32-byte structures. - avp

1 answer 1

Observable behavior is absolutely logical. You do not take into account the overhead of the allocator and other hidden "costs" of runtime. Each call to new usually stores the attributes of the allocated memory somewhere - size, position (so that later delete can delete correctly). But this is not reflected in your calculations.

If we assume that even byte 8 is allocated for this (but I do not know either the compiler or the environment, so I can only guess), then the total amount of memory consumed is close to the observed one.

What to do?

  • Try another allocator jmalloc , tmalloc .
  • Write your allocator :)
  • Use placement new . As a result, it will be possible to allocate 3 gigabytes and place all the objects there (unless it is a 64-bit system, on a 32-bit one is unlikely)
  • Stop worrying and come to terms.
  • Hmm, you are probably right. I did not take into account the fact that when using Insert, for each object, memory is allocated separately. In other matters, in my case this is not a problem, since in the future I was going to use just the "placement new" that you described .. Thank you! - Dylan993