0

I'm working on Splay Tree. I have a lot of command input (add, delete and etc), Hence the output is also huge (32MB of text in a txt file (very long string (more than 1000-10000 characters)))

I have a memory problem, I am currently using two Vector and my program take over 250 MB of virtual memory (128 MB is needed for the project) I run on Linux with the command:

$ g++ -std=c++17 -g -O3 -fno-asm -lm main.cpp

$ /usr/bin/time -v valgrind ./a.out

result: Maximum resident set size (kbytes): 277832 (With each launch different sizes but about 250)

how can i reduce the size? The vector changes when I output a new line of one vertex of the tree

using namespace std;

class SplayTree {
public:

    class Node;

    Node *ROOT = nullptr;

    class Node {
    public:
        long long key;
        string value;
        Node *_parent;
        Node *_RightChild;
        Node *_LeftChild;

        Node(long long _key = 0, string _value = NULL) {
            this->key = _key;
            this->value = _value;
            this->_parent = nullptr;
            this->_RightChild = nullptr;
            this->_LeftChild = nullptr;
        }
    ..........

        void PrintNode() {
            if (_parent == nullptr) {
                cout << "[" << key << " " << value << "]";
            } else {
                cout << "[" << key << " " << value << " " << _parent->key << "]";
            }
        }
    };

    .......... 

    //here problems
    void Print() { //string
        if (ROOT == nullptr) {
            //return "_\n";
            cout << "_\n";
        } else {

            ROOT->PrintNode();
            cout << "\n";

            long long n = 1;
            vector<Node *> NOWqueueVec; //to store the current descendants
            NOWqueueVec.push_back(ROOT);
            vector<Node *> BABYqueue;   //for storing future descendants

            long long h = height(ROOT);
            for (size_t v = 0; v < h-1; v++) {
                for (size_t i = 0; i < NOWqueueVec.size(); i++) {
                    if (NOWqueueVec[i] != nullptr) {
                        // left
                        if (NOWqueueVec[i]->haveLeftBaby()) {
                            BABYqueue.push_back(NOWqueueVec[i]->_LeftChild);
                            NOWqueueVec[i]->_LeftChild->PrintNode();
                        } else {
                            BABYqueue.push_back(nullptr);
                            cout << "_"; // << endl;
                        }
                        cout << " ";

                        // right
                        if (NOWqueueVec[i]->haveRightBaby()) {
                            BABYqueue.push_back(NOWqueueVec[i]->_RightChild);
                            NOWqueueVec[i]->_RightChild->PrintNode();
                        } else {
                            //BABYqueue[pos] = null
                            BABYqueue.push_back(nullptr);
                            cout << "_";
                        }
                    } else { // if empty then + 2 "_"
                        BABYqueue.push_back(nullptr);
                        BABYqueue.push_back(nullptr);
                        cout << "- -";
                    }
                }


                NOWqueueVec.clear();

        // Is there a problem here? ////////////
                for (Node* b : BABYqueue) { // for  NOWqueueVec=BABYqueue 
                    NOWqueueVec.push_back(b); 
                }

                cout << endl;
                BABYqueue.clear();

            }

            NOWqueueVec.clear();
            BABYqueue.clear();
        }
    }
};


int main() {
    SplayTree SPLAY;
    ..........
    ..........
    return 0;
}

I think the problem is in this block

     for (Node* b : BABYqueue) { // for  NOWqueueVec=BABYqueue 
           NOWqueueVec.push_back(b); 
     }

Are there any ways to optimize memory ?

Sudar Kudr
  • 11
  • 1
  • 1
    If `NOWqueueVec` has no `reserve()`d memory, `push_back` would indeed result in many reallocations and more memory consumption. But there's nowhere near enough info for use to solve that issue for you. – Yksisarvinen Oct 29 '22 at 21:44
  • 1
    those names begining with an underscore and an uppercase are reserved in c++ – Neil Butterworth Oct 29 '22 at 22:05
  • Two ways to reduce size; 1) arrange your class members so that padding inserted between members by the compiler for alignment reason is minimal. 2) tell your compiler to optimize for size rather than speed (the `-Os` flag for gcc and clang). – Jesper Juhl Oct 29 '22 at 23:16
  • [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) – Jesper Juhl Oct 29 '22 at 23:20
  • Another way to reduce size (at least with the GNU ld and gold linkers) is the `--gc-sections` linker flag. – Jesper Juhl Oct 29 '22 at 23:21
  • Also consider turning on LTO (Link Time Optimization) - it can often result in both faster *and* smaller binaries. – Jesper Juhl Oct 29 '22 at 23:22
  • Also experiment with not exporting all functions (default for most compilers on *nix systems is to export everything). Change to hidden visibility by default and explicitly only export what needs to be exported. Can lead to smaller binaries, fewer symbols for the dynamic linker to handle (faster program startup) etc. – Jesper Juhl Oct 29 '22 at 23:29

0 Answers0