Почему перевод этого фрагмента кода из 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];
        }
    }
}

В обоих случаях я создаю дерево суффиксов, а затем использую его в гораздо большей функции, которая не имеет отношения к посту (назовем его F()). Я протестировал оба на двух случайно сгенерированных строках длиной 100000. Версия C# создала мое дерево суффиксов и использовала его в F () за общее время выполнения: 480 мс, пока выполнялся код, который я "перевел на C++". через 48 секунд

Я подробно остановился на этом, и кажется, что в моем коде на C++ конструктор занимает 47 секунд, а использование дерева в F () выполняется за 48 мс, что в 10 раз быстрее, чем в C#.

Заключение

Кажется, что главная проблема в insertSuffix (), возможно, мое отсутствие знаний и понимания структуры unordered_map. Кто-нибудь может пролить свет на это? Я сделал ошибку новичка в варианте C++, из-за которого создание объекта заняло так много времени?

Дополнительная информация

Я скомпилировал программы на C# и C++ для максимальной скорости /O2 (выпуск)

Answer 1

В C# System.String включает свою длину, поэтому вы можете получить длину в постоянное время. В C++ std::stringтакже включает в себя его размер, поэтому он также доступен в постоянное время.

Тем не менее, вы не используете C++ std::string (каким вы должны быть, для хорошего перевода алгоритма); вы используете ноль-терминированный в стиле C char массив. Тот char* буквально означает "указатель на char ”И просто говорит вам, где находится первый символ строки. strlen функция смотрит на каждого char от указанного к следующему, пока он не найдет нулевой символ '\0' (не путать с нулевым указателем); это дорого, и вы делаете это на каждой итерации цикла в insertSuffix, Это, вероятно, составляет как минимум разумную долю вашего замедления.

При выполнении C++, если вы работаете с необработанными указателями (любой тип, включающий *), вы всегда должны задаться вопросом, есть ли более простой способ. Иногда ответ - "нет", но часто это "да" (и это становится все более распространенным по мере развития языка). Например, рассмотрим ваш struct node а также node* root, Оба используют node указатели, но в обоих случаях вы должны были использовать node непосредственно, потому что нет необходимости иметь эту косвенность (в случае node некоторая косвенность необходима, чтобы у вас не было каждого узла, содержащего другой узел до бесконечности, но это обеспечивается std::unordered_map).

---

Пара других советов:

• В C++ вы часто не хотите выполнять какую-либо работу в теле конструктора, а вместо этого используете списки инициализации.
• Если вы не хотите копировать что-то, что передаете в качестве параметра, вы должны сделать параметр ссылкой; вместо смены insertSuffix взять std::string в качестве первого параметра, сделайте так std::string const&; так же, contains должен взять std::string const&, Еще лучше, так как insertSuffix можно увидеть text член, он не должен принимать этот первый параметр вообще и может просто использовать from,
• C++ поддерживает foreach-подобную конструкцию, которую вы, вероятно, должны предпочесть стандарту for цикл при переборе по символам строки.
• Если вы используете новейшую версию C++, C++17, не технически завершенную, но достаточно близкую, вам следует использовать std::string_view вместо std::string всякий раз, когда вы просто хотите взглянуть на строку, и вам не нужно ее менять или хранить ссылку на нее. Это было бы полезно для contains и так как вы хотите сделать локальную копию в text член, даже для конструктора; это не будет полезно в text сам член, потому что просматриваемый объект может быть временным. Время жизни может иногда быть сложным в C++, и пока вы не освоитесь, вы можете просто захотеть использовать std::string быть на безопасной стороне.
• поскольку node не полезно вне концепции suffixTree должно быть внутри, как в версии C#. В отличие от версии C#, вы можете захотеть сделать тип node и члены данных root а также text в private вместо public члены.