为什么使用`nullptr`会导致性能下降[在LeetCode上]？

Question

作为LeetCode的一部分,我编写了一个简单的递归函数来遍历二叉树并输出所有可能的路径.(没有必要考虑这个来回答我的问题.我只是提供示例代码以演示一个具体的例子.)

/**
 * 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说我的解决方案相当缓慢:

经过大量的实验,我的代码的最大改进似乎正在取代所有

foo != nullptr

简单地说

foo

例如

    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);
        }
    }

这立即将我带到了顶端:

根据Performance的答案,使用'nullptr'或只是'0'会更快吗？,它似乎不应该(这么多)有所不同.我错过了什么？

Answer 1

假设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);
       }
};

同时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);
       }
};

让我们生成asm代码并比较结果:

$ 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"

生成的asm代码没有变化(即使有-O3).所以不,没有可能的性能影响.至少不使用g++ (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609和clang version 3.8.0-2ubuntu4 (tags/RELEASE_380/final).