无法重现:C++ Vector性能优于C#List性能

Question

在微软的BUILD大会上,Herb Sutter解释说C++有"真正的阵列"和C#/ Java语言没有相同或类似的东西.

我被卖掉了.您可以在http://channel9.msdn.com/Events/Build/2014/2-661观看完整的演讲

这是幻灯片的快照,他描述了这一点.http://i.stack.imgur.com/DQaiF.png

但是我想知道我会有多大的不同.

所以我编写了非常天真的测试程序,它从一个文件中创建一个大的字符串向量,行数从5个字符到50个字符不等.

链接到文件:

www (dot) dropbox.com/s/evxn9iq3fu8qwss/result.txt

然后我按顺序访​​问它们.

我在C#和C++中都做过这个练习.

注意:我做了一些修改,删除了循环中的复制,如建议的那样.感谢您帮助我理解Real数组.

在C#中,我使用了List和ArrayList,因为不推荐使用ArrayList而使用List.

以下是戴尔Core i7处理器的戴尔笔记本电脑的结果:

count       C# (List<string>)   C# (ArrayList)     C++   

1000           24 ms              21 ms             7 ms       
10000         214 ms             213 ms            64 ms     
100000  2 sec 123 ms       2 sec 125 ms           678 ms    

---

C#代码:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
namespace CSConsole
{
    class Program
    {
        static void Main(string[] args)
        {
            int count;
            bool success = int.TryParse(args[0], out count);

            var watch = new Stopwatch();
            System.IO.StreamReader isrc = new System.IO.StreamReader("result.txt");

            ArrayList list = new ArrayList();
            while (!isrc.EndOfStream)
            {
                list.Add(isrc.ReadLine());
            }
            double k = 0;
            watch.Start();
            for (int i = 0; i < count; i++)
            {
                ArrayList temp = new ArrayList();
                for (int j = 0; j < list.Count; j++)
                {
                   // temp.Add(list[j]);
                    k++;
                }
            }

            watch.Stop();
            TimeSpan ts = watch.Elapsed;

            //Console.WriteLine(ts.ToString());
            Console.WriteLine("Hours: {0} Miniutes: {1} Seconds: {2} Milliseconds: {3}", ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds);
            Console.WriteLine(k);
            isrc.Close();
        }


    }
}

---

C++代码

#include "stdafx.h"
#include <stdio.h>
#include <tchar.h>

#include <vector>
#include <fstream>
#include <chrono>
#include <iostream>
#include <string>

using namespace std;

std::chrono::high_resolution_clock::time_point time_now()
{
    return std::chrono::high_resolution_clock::now();
}

float time_elapsed(std::chrono::high_resolution_clock::time_point const & start)
{

    return std::chrono::duration_cast<std::chrono::milliseconds>(time_now() - start).count();
    //return std::chrono::duration_cast<std::chrono::duration<float>>(time_now() - start).count();
}


int _tmain(int argc, _TCHAR* argv [])
{
    int  count = _wtoi(argv[1]);

    vector<string> vs;
    fstream fs("result.txt", fstream::in);
    if (!fs) return -1;

    char* buffer = new char[1024];
    while (!fs.eof())
    {
        fs.getline(buffer, 1024);
        vs.push_back(string(buffer, fs.gcount()));
    }
    double k = 0;
    auto const start = time_now();
    for (int i = 0; i < count; i++)
    {
        vector<string> vs2;
        vector<string>::const_iterator iter;
        for (iter = vs.begin(); iter != vs.end(); iter++)
        {
            //vs2.push_back(*iter);
            k++;
        }
    }

    auto const elapsed = time_elapsed(start);
    cout << elapsed << endl;
    cout << k;
    fs.close();
    return 0;
}

Answer 1

示例程序发现的差异与列表或其结构无关.

这是因为在C#中,字符串是引用类型,而在C++代码中,您将它们用作值类型.

例如:

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

分配b = a只是复制指针.

这通过列表进行.将字符串添加到C#列表只是添加指向列表的指针.在主循环中,您将创建N个列表,所有这些列表都包含指向相同字符串的指针.

因为您在C++中按值使用字符串,所以每次都必须复制它们.

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

那么你现在正在创建指针列表而不是副本列表,并且与C#平等.

在我的系统上,C#程序在大约138毫秒内以N为1000运行,而C++程序在44毫秒内运行,这是C++的明显胜利.

评论:

根据草药sutter的图片,C++向量的主要好处之一是内存布局可以是连续的(即所有项目在内存中彼此相邻).std::string但是,你永远不会看到这个工作,因为字符串需要动态内存分配(你不能在数组中彼此相邻的字符串加载,因为每个字符串有不同的长度)

如果你想快速迭代它们,这将带来很大的好处,因为它对CPU缓存更友好,但权衡是你必须复制所有项目以使它们进入列表.

这是一个更好地说明它的例子:

C#代码:

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

C++代码:

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

我们从原来的问题中已经知道,在C#中创建一堆重复列表会比在C++中快得多,但是如何在列表中搜索呢？

这两个程序只是做一个愚蠢的线性列表扫描,只是为了表明这一点.

在我的电脑上,C++版本运行72毫秒,C#版本需要620毫秒.为什么速度增加？因为"真正的阵列".

所有的C++ ValueHolders都紧挨着彼此std::vector.当循环想要读取下一个循环时,这意味着它很可能已经在CPU cacue中.

C#ValueHolders位于各种随机内存位置,列表中只包含指向它们的指针.当循环想要读取下一个循环时,它几乎肯定不在 CPU缓存中,所以我们必须去阅读它.内存访问速度很慢,因此C#版本的使用时间将近10倍.

如果你将C#ValueHolder从更改class为struct,那么C#List可以将它们全部放在内存中彼此相邻,时间下降到161ms.Buuut现在它必须在你插入列表时制作副本.

C#的问题在于,在许多情况下,您不能或不想使用结构,而在C++中,您可以更好地控制此类事物.

PS:Java没有结构,所以你根本不能这样做.你坚持使用10x作为慢速缓存不友好版本

Answer 2

虽然C#string和C++ std::string共享一个名称,并且两者都是字符类型的有序集合,但它们却非常不同.

std::string是一个可变容器,C#string是不可变的.这意味着string可以共享两个C#中的数据:复制C#string复制指针(也称为引用),并进行连锁生命周期管理工作.复制std::string内容副本(写入C++时复制std::string不合法).

要创建更相似的C++代码集,请存储std::shared_ptr<const std::string>在您的vectors中.当你填写副本时vector,请确保只复制智能指针.现在你有了(智能)指向不可变数据的指针,就像C#一样.

请注意,这可能会提高C++中的复制性能,但会使大多数其他操作变慢(如果您想编辑,则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){ 代码就在这里 });.