Mindeveloped's blog

By Mindeveloped, history, 9 months ago, In English

Hello, everyone. I'd like to share an issue I met recently of which passing an STL container as a parameter through a function call caused MLE.

Look at this submission: 244198211. I was debugging it when I realized such line is causing MLE.

void insert (int p, string str, int len, int i, int id) {

I thought passing a string as a parameter might be the problem, so I changed my code and passed the index instead, and it got AC (there are other bugs but they don't matter): 244220216

So why is the problem?

The problem is, passing a parameter in non-reference calls the copy constructor and the destructor of the object each once, which means the object is being copied once every function call until it's finished. In normal situations it doesn't seems to be a big problem, but when you try to pass the object multiple times (especially if you're calling the function recursively) the memory usage is getting stacked up.

Note that this situation is the most common that people prefer to pass STL containers, especially string and vector in function parameters.

To make it clear I did some experiment, shown below:

#include<iostream>
using namespace std;

struct node {
	node () {
		cout << "Constructor called" << endl;
	}
	node (node &obj) {
		cout << "Copy constructor called" << endl;
	}
	~node () {
		cout << "Destructor called" << endl;
	}
};
node x;
void normal (node y) {
	cout << "Normal function body" << endl;
}
void reference (node &y) {
	cout << "Reference function body" << endl;
}
int main () {
	cout << "Calling normal function" << endl;
	normal (x);
	cout << "Finished calling normal function. Calling reference function" << endl;
	reference (x);
	cout << "Finished calling reference function" << endl;
	return 0;
}

And the result is:

Constructor called
Calling normal function
Copy constructor called
Normal function body
Destructor called
Finished calling normal function. Calling reference function
Reference function body
Finished calling reference function
Destructor called

From upon you can see that passing object as normal parameter calls copy constructor and destructor each once, and passing as reference does not do anything to the object.

So here are some suggestions to avoid this:

  1. Pass indices or pointers instead of the original object. The straightforward way, though it might makes the code look bad (imo).
  2. Use arrays instead of strings or vectors. Arrays are passed as pointers of the initial address (in other ways, they are passed as references automatically).
  3. Pass reference if you can. It makes the code more readable compared to 1.

EDIT: The idea was originally wrong, but thanks to the guy in comment I've corrected. The point is still valid, but the description needs a bit changing.

Thanks for reading.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it
Test program

$ ./t
S: 3584
T: 3584

It seems the memory allocator you have used is broken ;)

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I don't know exactly, but I think Codeforces measures the memory differently from getrusage, by measuring the largest segment of used memory rather than currently occupied memory. For evidence, 244242383 got MLE with only the way of passing parameters modified from the original submission.

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      I ran two versions of your code on generated sample data with parameters as in the failed test case. These are results:

      Pass by value (): Maximum resident set size (kbytes): 9788800
      Pass by reference: Maximum resident set size (kbytes): 9789056

      I think, the issue does not relate to the parameters of the search() method.

      Edit: the issue is here:

             void insert (int &p, string str, int len, int i, int id) {
                      ...
                      insert (son[p][str[i] - 'a'], str, len, i + 1, id);
             }
      

      After modification of the insert()'s signature to insert(int&, string&, int, int, int):

      Maximum resident set size (kbytes): 24812

»
9 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Why don't you passing by reference? I saw it is advice #3 but is it not a common knowledge?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In C++ there is a concept called move semantics which let's you pass arguments without explicit pointers and references efficiently. But there are so many caveats making it very easy to accidentally invoke copying that for example for Firefox it turned out simpler to invent new language and rewrite it in Rust with move by default than to use c++

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

rust fixes this