示例程序发现的差异与列表或其结构无关。
这是因为在 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# 程序的运行时间约为 N of 1000138 毫秒,而 C++ 则运行在44毫秒,C++ 明显获胜。
评论:
根据 Herb sutter 的图片,C++ 向量的主要优点之一是内存布局可以是连续的(即所有项目在内存中彼此相邻)。
你永远不会看到这个作品std::string
但是,由于字符串需要动态内存分配(您不能在数组中将一堆字符串彼此相邻放置,因为每个字符串都有不同的长度)
如果您想快速遍历所有项目,这将带来很大的好处,因为它对 CPU 缓存更加友好,但代价是您必须复制所有项目才能将它们放入列表中。
这是一个更好地说明它的例子:
C# Code:
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++ 版本运行在72ms而 C# 则需要620ms。为什么速度会增加?因为“真实数组”。
所有的C++ValueHolders
被困在彼此旁边std::vector
。当循环想要读取下一个时,这意味着它很可能已经在 CPU 缓存中。
C# ValueHolder 位于各种随机内存位置,列表仅包含指向它们的指针。当循环想要读取下一个时,几乎可以肯定not在CPU缓存中,所以我们必须去读取它。内存访问速度很慢,因此 C# 版本需要近 10 倍的时间。
如果您将 C# ValueHolder 从class
to struct
,那么 C# 列表可以将它们全部粘贴在内存中,时间会下降到161ms。但现在,当您插入列表时,它必须制作副本。
C# 的问题是,在很多情况下您不能或不想使用结构体,而在 C++ 中您对这种事情有更多的控制权。
PS:Java没有结构体,所以你根本不能这样做。你被困在 10 倍慢的缓存不友好版本中