无法重现：C ++ Vector性能优于C＃List性能

在微软的BUILD大会上，Herb Sutter解释说C ++有“Real Arrays”和C＃/ Java语言没有相同或类似。

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

这是幻灯片的快照，他描述了这一点。 http://sofzh.miximages.com/c%23/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) 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  #include  #include  #include  #include  #include  #include  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(time_now() - start).count(); //return std::chrono::duration_cast<std::chrono::duration>(time_now() - start).count(); } int _tmain(int argc, _TCHAR* argv []) { int count = _wtoi(argv[1]); vector 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 vs2; vector::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 vs2; vector::const_iterator iter; for (iter = vs.begin(); iter != vs.end(); iter++) { vs2.push_back(*iter); // STRING IS COPIED HERE } 

这段代码实际上是每个字符串的副本。 你最终得到了所有字符串的副本，并将使用更多的内存。 由于明显的原因，这种情况较慢

如果您按如下方式重写循环：

 vector 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 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 vs = new List(); 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& 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 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毫秒 。 为什么速度增加？ 因为“真正的arrays”。

所有的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是不可变的。 这意味着可以共享两个C＃ string的数据：复制C＃ string复制指针（也称为引用），并进行连锁生命周期管理工作。 复制std::string复制内容（写入C ++ std::string复制不合法）。

要创建更相似的C ++代码集，请在vector s中存储std::shared_ptr 。 当你填充重复的vector s时，请确保只复制智能指针。 现在你有（智能）指向不可变数据的指针，就像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::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(*data) ); return *data; } template void emplace( Args&&... args ) { data = std::make_shared(std::forward(args)...); } template void modify( F&& f ) { std::string tmp = std::move(*this).get(); std::forward(f)(tmp); emplace(std::move(tmp)); } private: std::shared_ptr data; static std::shared_ptr empty_string() { static auto nothing = std::make_shared(); return nothing; } }; 

这给了我们COW。 要编辑，请调用immutable_string s; s.modify( [&](std::string& s){ immutable_string s; s.modify( [&](std::string& s){ code goes here }); 。