Search code examples
c++performancenullptr

Why does using `nullptr` cause a performance hit [on LeetCode]?

As part of LeetCode, I wrote a simple recursive function to traverse a binary tree and output all the possible paths. (It's not necessary to think about this to answer my question. I'm just providing sample code in order to demonstrate a concrete example.)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> paths;
        if( root != nullptr ) {
            string str;
            binaryTreePathsHelper(root, paths, str);
        }
        return paths;
    }

    void binaryTreePathsHelper(TreeNode* node, vector<string>& paths, string str) {

        str += std::to_string(node->val);

        if( node->left  == nullptr &&
            node->right == nullptr ) {
            paths.push_back(str);
        } else {
            str += "->";
        }

        if( node->left != nullptr ) {
            binaryTreePathsHelper(node->left, paths, str);
        }

        if( node->right != nullptr ) {
            binaryTreePathsHelper(node->right, paths, str);
        }
    }
};

LeetCode was saying my solution was rather slow, compared to other submissions:

enter image description here

After a good deal of experimentation, the biggest improvement to my code seemed to be replacing all

foo != nullptr

with simply

foo

e.g.

    void binaryTreePathsHelper(TreeNode* node, vector<string>& paths, string str) {

        str += std::to_string(node->val);

        if( !node->left && !node->right ) {
            paths.push_back(str);
        } else {
            str += "->";
        }

        if( node->left ) {
            binaryTreePathsHelper(node->left, paths, str);
        }

        if( node->right ) {
            binaryTreePathsHelper(node->right, paths, str);
        }
    }

which instantly brings me to the top:

enter image description here

According to the answers at Performance wise, is it faster to use 'nullptr' or just '0'?, it seems it shouldn't make (this much of) a difference. What am I missing?

Solution

  • Assuming that main.cpp:

    #include <vector>
#include <string>

using namespace std;

struct TreeNode {
 int val;
 TreeNode *left;
 TreeNode *right;
 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root);
    void binaryTreePathsHelper(TreeNode* node, vector<string>& paths, string str);
};

vector<string> Solution::binaryTreePaths(TreeNode* root) {
       vector<string> paths;
       if( root != nullptr ) {
          string str;
          binaryTreePathsHelper(root, paths, str);
       }
       return paths;
    }


 void Solution::binaryTreePathsHelper(TreeNode* node, vector<string>& paths, string str) {

       str += std::to_string(node->val);

       if( node->left  == nullptr &&
           node->right == nullptr ) {
           paths.push_back(str);
       } else {
           str += "->";
       }

       if( node->left != nullptr ) {
            binaryTreePathsHelper(node->left, paths, str);
       }

       if( node->right != nullptr ) {
            binaryTreePathsHelper(node->right, paths, str);
       }
};

    While main2.cpp:

    #include <vector>
#include <string>

using namespace std;

struct TreeNode {
 int val;
 TreeNode *left;
 TreeNode *right;
 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root);
    void binaryTreePathsHelper(TreeNode* node, vector<string>& paths, string str);
};

vector<string> Solution::binaryTreePaths(TreeNode* root) {
       vector<string> paths;
       if( root ) {
          string str;
          binaryTreePathsHelper(root, paths, str);
       }
       return paths;
    }


void Solution::binaryTreePathsHelper(TreeNode* node, vector<string>& paths, string str) {

       str += std::to_string(node->val);

       if( !(node->left) &&
           !(node->right) ) {
           paths.push_back(str);
       } else {
           str += "->";
       }

       if( node->left ) {
           binaryTreePathsHelper(node->left, paths, str);
       }

       if( node->right ) {
           binaryTreePathsHelper(node->right, paths, str);
       }
};

    Let's generate asm code and compare results:

    $ gcc -S main.cpp -o main.S -std=c++11
$ gcc -S main2.cpp -o main2.S -std=c++11
$ diff main.S main2.S
1c1
<       .file   "main.cpp"
---
>       .file   "main2.cpp"

    There is no change in generated asm code (even with -O3). So no, there is no performance hit possible. At least not with the use of g++ (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609 and clang version 3.8.0-2ubuntu4 (tags/RELEASE_380/final).