为什么将此代码片段从 C# 转换为 C++ 会降低性能？

Question

我对C#比C++熟悉得多，所以我必须就此问题寻求建议。我不得不将一些代码片段重写为 C++，然后（令人惊讶地）运行陷入性能问题。

我已将问题缩小到这些片段：

C#

   public class SuffixTree
    {
        public class Node
        {
            public int Index = -1;
            public Dictionary<char, Node> Children = new Dictionary<char, Node>();
        }

        public Node Root = new Node();
        public String Text;

        public SuffixTree(string s)
        {
            Text = s;
            for (var i = s.Length - 1; i >= 0; --i)
                InsertSuffix(s, i);
        }

        public void InsertSuffix(string s, int from)
        {
            var cur = Root;
            for (int i = from; i < s.Length; ++i)
            {
                var c = s[i];
                if (!cur.Children.ContainsKey(c))
                {
                    var n = new Node() { Index = from };
                    cur.Children.Add(c, n);

                    return;
                }
                cur = cur.Children[c];
            }
        }

        public bool Contains(string s)
        {
            return FindNode(s) != null;
        }

        private Node FindNode(string s)
        {
            var cur = Root;
            for (int i = 0; i < s.Length; ++i)
            {
                var c = s[i];
                if (!cur.Children.ContainsKey(c))
                {
                    for (var j = i; j < s.Length; ++j)
                        if (Text[cur.Index + j] != s[j])
                            return null;
                    return cur;
                }
                cur = cur.Children[c];
            }
            return cur;
        }
    }
}

C++

struct node
{
    int index;
    std::unordered_map<char, node*> children;

    node() { this->index = -1; }
    node(int idx) { this->index = idx; }
};

struct suffixTree
{
    node* root;
    char* text;

    suffixTree(char* str)
    {
        int len = strlen(str) + 1;
        this->text = new char[len];
        strncpy(this->text, str, len);

        root = new node();
        for (int i = len - 2; i >= 0; --i)
            insertSuffix(str, i);
    }

    void insertSuffix(char* str, int from)
    {
        node* current = root;
        for (int i = from; i < strlen(str); ++i)
        {
            char key = str[i];
            if (current->children.find(key) == current->children.end())
            {
                current->children[key] = new node(from);
                return;
            }
            current = current->children[key];
        }
    }

    bool contains(char* str)
    {
        node* current = this->root;
        for (int i = 0; i < strlen(str); ++i)
        {
            char key = str[i];
            if (current->children.find(key) == current->children.end())
            {
                for (int j = i; j < strlen(str); ++j)
                    if (this->text[current->index + j] != str[j])
                        return false;
                return true;
            }
            current = current->children[key];
        }
    }
}

在这两种情况下，我都创建了一个后缀树，然后在与 post 无关的更大的函数中使用它（我们称之为 F()）。我已经在两个运行domly 生成的长度为 100000 的字符串上进行了测试。C# 版本构建了我的后缀树并在 F() 中使用它，总执行时间为：480 ms 而我 "translated to C++" 在 48 秒

中执行的代码

我对此进行了进一步深入研究，似乎在我的 C++ 代码中，构造函数需要 47 秒，而在 F() 中使用树运行在 48 毫秒，比 C# 快 10 倍。

结论

看来问题主要出在insertSuffix()，可能是我对unordered_map[=44=的认识和理解不够] 结构体。任何人都可以阐明这一点吗？我是否在 C++ 变体中犯了一些新手错误导致对象构造花费这么长时间？

附加信息

我已经为最大速度编译了 C# 和 C++ 程序 /O2（发布）

Answer 1

在C#中，一个System.String includes its Length, so you can get the length in constant time. In C++, a std::string also includes its size，所以在常数时间内也是可用的

但是，您没有使用 C++ std::string（您应该使用 C++，以便更好地翻译算法）；你正在使用 C-style null-terminated char array. That char* literally means “pointer to char”, and just tells you where the first character of the string is. The strlen function looks at each char from the one pointed to forward, until it finds a null character '[=17=]' (not to be confused with a null pointer);这很昂贵，并且您在 insertSuffix 中循环的每次迭代中都这样做。这可能至少占了您减速的合理部分。

在使用 C++ 时，如果您发现自己在使用原始指针（任何涉及 * 的类型），您应该总是想知道是否有更简单的方法。有时答案是“否”，但通常是“是”（随着语言的发展，这种情况变得越来越普遍）。例如，考虑您的 struct node 和 node* root。两者都使用 node 指针，但在这两种情况下你都应该直接使用 node 因为没有必要使用间接寻址（在 node、some[ 的情况下=69=] 间接数量是必要的，因此您不会让每个节点都包含另一个节点 ad infinitum，但这是由 std::unordered_map).

提供的

其他一些提示：

在 C++ 中，您通常不想在构造函数的主体中做任何工作，而是使用 initialization lists.

当您不想复制作为参数传递的内容时，您应该将参数设为引用；与其将 insertSuffix 更改为将 std::string 作为第一个参数，不如将其设为 std::string const&；同样，contains 应该取 std::string const&。更好的是，由于 insertSuffix 可以看到 text 成员，它根本不需要采用第一个参数，只需使用 from.

C++ 支持 foreach-like construct，在遍历字符串的字符时，您可能更喜欢使用标准 for 循环。

如果您使用的是最新的 C++ 版本，C++17，技术上尚未最终确定，但已经足够接近，您应该使用 std::string_view 而不是 std::string，只要您只是想要查看一个字符串，不需要更改它或保留对它的引用。这对 contains 很有用，因为你想在 text 成员中创建一个本地副本，即使对于构造函数也是如此；它在 text 成员本身中没有用处，因为正在查看的对象可能是临时的。不过，在 C++ 中，生命周期有时会很棘手，在您掌握它之前，您可能只想使用 std::string 以确保安全。

因为 node 在 suffixTree 的概念之外没有用，它应该在它里面，就像在 C# 版本中一样。作为与 C# 版本的偏差，您可能希望将类型 node 和数据成员 root 和 text 变为 private 而不是 public 成员。

为什么将此代码片段从 C# 转换为 C++ 会降低性能？

Why does translating this code snippet from C# to C++ degrade performance?

c#

c++

algorithm

optimization

suffix-tree