Ответ 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