Невозможно воспроизвести: преимущества производительности С++ Vector перед показателями С# List

Ответ 1

Различия, обнаруженные вашей программой-образцом, не имеют ничего общего с списками или их структурой.

Это потому, что в С# строки являются ссылочным типом, тогда как в С++-коде вы используете их как тип значения.

Например:

string a = "foo bar baz";
string b = a;

Назначение b = a - это просто копирование указателя.

Это следует в списках. Добавление строки в список С# просто добавляет указатель на список. В вашем основном цикле вы создаете N списков, все из которых содержат указатели только на те же строки.

Поскольку вы используете строки по значению в С++, но каждый раз приходится копировать их.

vector<string> vs2;
vector<string>::const_iterator iter;
for (iter = vs.begin(); iter != vs.end(); iter++)
{
   vs2.push_back(*iter); // STRING IS COPIED HERE
}

Этот код фактически создает копии каждой строки. Вы получаете копии всех строк и будете использовать намного больше памяти. Это медленнее по очевидным причинам.

Если вы перепишете цикл следующим образом:

vector<string*> vs2;
for (auto& s : vs)
{
    vs2.push_back(&(s));
}

Затем вы создаете списки указателей, а не списки-копии, и на равных с С#.

В моей системе программа С# работает с N из 1000 примерно в 138 миллисекунд, а С++ работает в 44 миллисекундах, явный выигрыш для С++.

Комментарий:

Одним из основных преимуществ векторов С++ в соответствии с рисунком травяного саттера является то, что макет памяти может быть смежным (т.е. все элементы застряли рядом друг с другом в памяти). Однако вы никогда не увидите эту работу с std::string, так как строки требуют динамического выделения памяти (вы не можете вставлять нагрузку строк рядом друг с другом в массив, потому что каждая строка имеет разную длину)

Это даст большую выгоду, если вы захотите быстро перебрать все их, так как это гораздо более дружелюбно относится к кэшам процессора, но компромисс заключается в том, что вам нужно скопировать все элементы, чтобы получить их в списке.

Вот пример, который лучше его иллюстрирует:

Код С#:

class ValueHolder {
    public int tag;
    public int blah;
    public int otherBlah;

    public ValueHolder(int t, int b, int o)
    { tag = t; blah = b; otherBlah = o; }
};

static ValueHolder findHolderWithTag(List<ValueHolder> buffer, int tag) {
    // find holder with tag i
    foreach (var holder in buffer) {
        if (holder.tag == tag)
            return holder;
    }
    return new ValueHolder(0, 0, 0);
}

static void Main(string[] args)
{
    const int MAX = 99999;

    int  count = 1000; // _wtoi(argv[1]);
    List<ValueHolder> vs = new List<ValueHolder>();
    for (int i = MAX; i >= 0; i--) {
        vs.Add(new ValueHolder(i, 0, 0)); // construct valueholder with tag i, blahs of 0
    }

    var watch = new Stopwatch();
    watch.Start();

    for (int i = 0; i < count; i++)
    {
        ValueHolder found = findHolderWithTag(vs, i);
        if (found.tag != i)
            throw new ArgumentException("not found");
    }

    watch.Stop();
    TimeSpan ts = watch.Elapsed;
    Console.WriteLine("Hours: {0} Miniutes: {1} Seconds: {2} Milliseconds: {3}", ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds);
}

Код С++:

class ValueHolder {
public:
    int tag;
    int blah;
    int otherBlah;

    ValueHolder(int t, int b, int o) : tag(t), blah(b), otherBlah(o) { }
};

const ValueHolder& findHolderWithTag(vector<ValueHolder>& buffer, int tag) {
    // find holder with tag i
    for (const auto& holder : buffer) {
        if (holder.tag == tag)
            return holder;
    }
    static ValueHolder empty{ 0, 0, 0 };
    return empty;
}

int _tmain(int argc, _TCHAR* argv[])
{
    const int MAX = 99999;

    int  count = 1000; // _wtoi(argv[1]);
    vector<ValueHolder> vs;
    for (int i = MAX; i >= 0; i--) {
        vs.emplace_back(i, 0, 0); // construct valueholder with tag i, blahs of 0
    }

    auto const start = time_now();
    for (int i = 0; i < count; i++)
    {
        const ValueHolder& found = findHolderWithTag(vs, i);
        if (found.tag != i) // need to use the return value or compiler will optimize away
            throw "not found";
    }

    auto const elapsed = time_elapsed(start);
    cout << elapsed << endl;
    return 0;
}

Мы уже знаем из первоначального вопроса, что создание кучи дубликатов списков будет намного быстрее в С#, чем в С++, но как насчет поиска в списке?

Обе программы просто делают глупое линейное сканирование списка в простой попытке показать это.

На моем ПК версия С++ работает в 72 мс, а на С# - 620 мс. Почему скорость увеличивается? Из-за "реальных массивов".

Все С++ ValueHolders застревают рядом с eachother в std::vector. Когда цикл хочет прочитать следующий, это означает, что он, скорее всего, уже находится в ЦП. [/P >

С# ValueHolders находятся во всех типах случайных мест памяти, и список содержит только указатели на них. Когда цикл хочет читать следующий, он почти наверняка не находится в кэше CPU, поэтому мы должны пойти и прочитать его. Доступ к памяти медленный, поэтому версия С# занимает почти 10 раз.

Если вы измените значение С# ValueHolder с class на struct, тогда список С# может привязать их все рядом друг к другу в памяти, а время опустится до 161 мс. Buuut теперь он должен делать копии, когда вы вставляете их в список.

Проблема для С# заключается в том, что существует много ситуаций, когда вы не можете или не хотите использовать структуру, тогда как на С++ у вас больше контроля над такими вещами.

PS: Java не имеет структур, поэтому вы не можете этого сделать вообще. Вы застряли с нечестной версией медленного кэша 10x

Ответ 2

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

std::string является изменяемым контейнером, С# string является неизменным. Это означает, что данные в двух С# string могут быть разделены: копирование С# string дублирует указатель (aka reference) и выполняет работу по управлению продолжительностью жизни. Дублирование a std::string копирует содержимое (копирование при записи С++ std::string не является законным).

Чтобы создать более похожий набор кода С++, сохраните std::shared_ptr<const std::string> в vector. И когда вы набираете дубликат vector s, убедитесь, что вы только скопировали интеллектуальные указатели. Теперь у вас есть (умные) указатели на неизменяемые данные, как и на С#.

Обратите внимание, что это улучшит производительность копирования, возможно, на С++, но сделает большинство других операций медленнее (если вы хотите отредактировать std::string, теперь вам нужно скопировать всю вещь, а затем изменить копию, а читать дополнительно разыменование указателя).

struct immutable_string {
  immutable_string() = default;
  immutable_string(const&) = default;
  immutable_string(&&) = default;
  immutable_string& operator=(const&) = default;
  immutable_string& operator=(&&) = default;

  immutable_string( std::string s ):data( std::make_shared<std::string>(std::move(s)) ) {}

  std::string const& get() const { if (data) return *data; return *empty_string(); }
  std::string get() && {
    if (!data) return {};
    if (data->use_count()==1) return std::move( const_cast<std::string&>(*data) );
    return *data;
  }
  template<class... Args>
  void emplace( Args&&... args ) {
    data = std::make_shared<std::string>(std::forward<Args>(args)...);
  }
  template<class F>
  void modify( F&& f ) {
    std::string tmp = std::move(*this).get();
    std::forward<F>(f)(tmp);
    emplace(std::move(tmp));
  }
private:
  std::shared_ptr<const std::string> data;
  static std::shared_ptr<const std::string> empty_string() {
    static auto nothing = std::make_shared<const std::string>();
    return nothing;
  }
};

это дает нам COW. Чтобы отредактировать, вызовите immutable_string s; s.modify( [&](std::string& s){ код здесь });.