I6 Homework - How do I troubleshoot memory leaks?

The Partridge Family were neither partridges nor a family. Discuss.
HavocVulture
Posts: 16
Joined: October 30th, 2017, 11:50 pm

I6 Homework - How do I troubleshoot memory leaks?

Post by HavocVulture » July 12th, 2018, 2:18 am

My repo is here: https://github.com/CorpseLiquor/LinkedL ... dListStack

I'm passing all the tests but I have a few leaks. Unfortunately I'm not really clear on how I take the info in the object dump and use it to figure out what I'm doing wrong.

I have a feeling some of the elements in the stack aren't being deleted. But when I tried moving through the list and deleting as I went I kept getting access violations.

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: I6 Homework - How do I troubleshoot memory leaks?

Post by albinopapa » July 12th, 2018, 4:05 am

Might be a part of your problem

Code: Select all

	Stack& operator=( const Stack& s ) {
		Element* temp = s.e;
		while ( temp != nullptr  && temp->Previous != nullptr ) {
			temp = temp->Previous;
		}

		while ( temp != nullptr ) {
			this->Push( temp->Value );
			temp = temp->Next;
		}

		return *this;
	}
If you did:
Stack a = { some list };
Stack b = { some other list };
a = b;
What happens to the list in Stack a? You aren't releasing the current contents of a, so you are just overwriting what's in a and leaking the memory that was in Stack a. Or more likely, you are just going to extent your Stack a, because you haven't deleted any of the elements from the stack.

This is another problem:

Code: Select all

	~Stack() 
	{
		delete e;
		e = nullptr;
	}
You delete e, but what about the e->Previous and e->Next, how are they going to get deleted?
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
cyboryxmen
Posts: 190
Joined: November 14th, 2014, 2:03 am

Re: I6 Homework - How do I troubleshoot memory leaks?

Post by cyboryxmen » July 12th, 2018, 4:05 am

You had the right idea. The destructor was only deleting the top element and not every element in the stack. I made a pull request that can help you compare my results to yours.

I'm guessing that the access violations you had were probably due to you deleting the element then accessing their Previous afterwards. You can look at mine to see what a valid implementation would look like
Last edited by cyboryxmen on July 12th, 2018, 4:08 am, edited 1 time in total.
Zekilk

User avatar
cyboryxmen
Posts: 190
Joined: November 14th, 2014, 2:03 am

Re: I6 Homework - How do I troubleshoot memory leaks?

Post by cyboryxmen » July 12th, 2018, 4:07 am

There's also some redundancies in the checks you're doing for your copy constructors and copy operators but I'll leave that to you to figure that out for yourself. Overall, it was a good first effort and the program should be perfectly valid if you include the small changes I have made to the destructor.
Zekilk

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: I6 Homework - How do I troubleshoot memory leaks?

Post by albinopapa » July 12th, 2018, 4:20 am

Might try something like this:

Code: Select all

	~Stack()
	{
		while( Size() > 0 )
		{
			Pop();
		}
	}
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
cyboryxmen
Posts: 190
Joined: November 14th, 2014, 2:03 am

Re: I6 Homework - How do I troubleshoot memory leaks?

Post by cyboryxmen » July 12th, 2018, 4:46 am

I've actually been moving away from non-const member functions calling other non-const member functions. It helps to reduce bugs caused by unseen changes made by them that you didn't expect. Not to mention that it makes unit testing easier as the non-const member functions are independent from each other and can be tested individually. For reusability, I just use const member functions since they are free from side effects.

And above all else, it's just more optimal to write code specifically for the destructor instead of reusing pop.
Zekilk

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: I6 Homework - How do I troubleshoot memory leaks?

Post by albinopapa » July 12th, 2018, 6:16 am

And above all else, it's just more optimal to write code specifically for the destructor instead of reusing pop.
How?

The logic between removing one element in the pop function and one iteration to remove an element from the list is the same. So not only is it code duplication, but it also will help identify bugs. If it doesn't work as expected in the destructor as specified, then why would it work if you were popping off multiple elements. It would draw it out or expose flaws.

This would be no different if there was a Clear() function, would you really write similar or same code for Pop, Clear and the destructor? Honestly, if there was a Clear function, I would have called that from the destructor and at the same time, the Clear function would be the while loop Popping off each element from the stack.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
cyboryxmen
Posts: 190
Joined: November 14th, 2014, 2:03 am

Re: I6 Homework - How do I troubleshoot memory leaks?

Post by cyboryxmen » July 12th, 2018, 9:38 am

This isn't really a good example to help explain my personal philosophy as to why I don't like to have non-const member functions call other non-const member functions. That discussion honestly deserves its own thread.

As for the reason why my implementation will be better than just calling Pop(), it ultimately comes down to two lines of code:

Code: Select all

count--;
...
e = e->Previous;
Pop() writes to <this>'s count and <this>'s top element directly every time it pops off an element from the stack. This is bad compared to using a local variable like node_to_delete because node_to_delete doesn't need to actually "exist" in memory. You can simply set the CPU registers directly instead of writing to memory every time. When you write to any member of <this>, you're forcing the compiler to output instructions that will write to memory instead of writing to the CPU registers. This is because of how The C++ Standard strictly defines how structs and classes work in memory. This is done in order to make it easier to use C++ in systems programming; a field that requires you to use memory in well defined ways. Local variables don't have that strict requirement and the compiler can optimize writes to them more thoroughly than they can with writes to <this>. You might say that this(pun unintended) won't matter as the compiler can inline Pop() allowing it to optimize as much as it likes. You would be right since any decent compiler would inline Pop() that but as these results show, it'll still result in instructions that write to memory instead of using the registers directly.

Compiled with X64 GCC 8.1 with full -O3 optimizations

Using Pop()

Code: Select all

Stack::~Stack() [base object destructor]:
        mov     eax, DWORD PTR [rdi] // Set the current count to the stack's count
        test    eax, eax // Check if the current count is zero
        jle     .L6
        push    rbx
        mov     rbx, rdi // Load the stack
.L3:
        mov     rdi, QWORD PTR [rbx+8] // Set the current element to the stack's top element
        sub     eax, 1 // Decrement the current count
        mov     esi, 24 // Necessary for calling operator delete()
        mov     DWORD PTR [rbx], eax // Set the stack's count to the current count
        mov     rax, QWORD PTR [rdi+16] // Load the current element's previous
        mov     QWORD PTR [rbx+8], rax // Set the stack's top element to the current element's previous
        call    operator delete(void*, unsigned long) // Call delete
        mov     eax, DWORD PTR [rbx] // Set the current count to the stack's count
        test    eax, eax // Check if the current count == 0
        jg      .L3
        pop     rbx
        ret
.L6:
        ret
My implementation

Code: Select all

Stack::~Stack() [base object destructor]:
        mov     rdi, QWORD PTR [rdi+8] // Set the current element to the stack's top element
        test    rdi, rdi // Check if the current element is nullptr
        je      .L9
        push    rbx
.L3:
        mov     rbx, QWORD PTR [rdi+16] // Save current element's previous
        mov     esi, 24 // Call delete on the current element
        call    operator delete(void*, unsigned long)
        mov     rdi, rbx // Set the current element to the saved previous
        test    rbx, rbx // Check if the current element is nullptr
        jne     .L3
        pop     rbx
        ret
.L9:
        ret
Don't try to pay attention to the bigger instruction size that's being generated. That usually doesn't matter much. Instead, pay attention to those <mov>s. The <mov>s generated for the code that uses Pop() write to memory(<this>) while the one that doesn't simply writes to the CPU registers directly. Writing to memory instead of writing to CPU register is going to be such a huge bottleneck that's only going to get slower as memory lags behind the increasing CPU speeds. This is the main reason why immutable lambdas are so much more performant than mutable lambdas or lambdas that capture <this>

The ultimate takeaway from this is: Avoid changing <this> as much as possible. Const member functions are your friends in this regard. They're simple to write, intuitive to use, less bug prone, easy to test and would just preform better in a lot of cases. When writing non-const member functions that do change <this>, prefer that it does not call other non-const member functions unless it is simply a "wrapper" around that function(like a destructor that does nothing but call clear()).
Zekilk

HavocVulture
Posts: 16
Joined: October 30th, 2017, 11:50 pm

Re: I6 Homework - How do I troubleshoot memory leaks?

Post by HavocVulture » July 12th, 2018, 11:38 am

Thanks cyboryxmen and albinopapa. Both of your solutions worked. You were both able to read the code and identify the problem. Is the object dump only supposed to indicate a problem without indicating where that problem might be?

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: I6 Homework - How do I troubleshoot memory leaks?

Post by albinopapa » July 12th, 2018, 6:18 pm

@cyboryxmen: Well explained. Makes me wonder about some things.

It has to do with wrapping SSE code in classes. From my experience, wrapping SSE code in a class ( float128 wraps __m128 and all operator overloads ) usually doesn't have an impact in Release mode mostly because of inlining which in turn just uses the intrinsics to load or store directly to registers.

Although, I do get confused a lot looking at the VS Disassembler code because I'll usually see something like:
dqmova XMM0, XMMPTR[ offset ]
dqmova XMMPTR[ sameOffset ], XMM0
dqmova XMM0, XMMPTR[ sameOffset ]

Just to load something from 128bit memory to an XMM register. I'll have to watch again more closely to see if it's actually dqmovu then dqmova, perhaps it's thinking it's unaligned memory, but I'm pretty sure I always use _aligned_malloc or alignas( 16 ) float storage[4] or class alignas( 16 ) float128.

@HavocVulture, I think the dump shows the 24 bytes that make up an Element, the int value and the Element* Previous and *Next pointers. So if you decode the hex, you should be able to tell which elements didn't get deleted.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Post Reply