为什么使用 `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 wise, is it faster to use 'nullptr' or just '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).

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

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

c++

performance

nullptr