Разница в скорости работы компиляторов различных версий С++ на codeforces

№	Пользователь	Рейтинг
1	tourist	3803
2	jiangly	3707
3	Benq	3627
4	ecnerwala	3584
5	orzdevinwang	3573
6	Geothermal	3569
6	cnnfls_csy	3569
8	Radewoosh	3542
9	jqdai0815	3532
10	gyh20	3447

№	Пользователь	Вклад
1	maomao90	164
2	awoo	163
3	adamant	162
4	maroonrk	152
5	-is-this-fft-	151
6	nor	150
7	atcoder_official	147
8	TheScrasse	146
9	Petr	145
10	SecondThread	142

Почему некоторые решения работают значительно быстрее при использовании разных компиляторов С++? Так, решая 1800F - Dasha and Nightmares
я столкнулся с тем, что при использовании компилятора 20-й версии решение не проходит по времени, при этом выполняется в итоге за примерно 4200мс, в то время как 17й компилятор справился с решением в среднем за 3650мс, отсюда вопрос почему? Само решение оно вот https://mirror.codeforces.com/contest/1800/submission/241615256 , у меня было предположение что это связано с прагмой на avx инструкции, но мимо, без нее решение работает аналогично по времени, может кто-то знает в чем дело и что именно 17й компилятор делает быстрее, и соответственно, когда его лучше использовать?

Комментарии (4)

Написать комментарий?

Papercut

6 месяцев назад, # |

← Rev. 2 →

Ну, конкретно здесь разница в памяти (в блоге стоило отметить, что С++17 в твоей посылке 32битный, соответственно, все указатели в STL сущностях "весят" в 2 раза меньше), а в целом отличие в $$$15$$$% рантайма не кажется чем-то странным, так бывает и в пределах одного компилятора.
Насчет avx2: она здесь бесполезна — такие прагмы нужны, если хочется векторизовать какой-то код с простым скалярным содержимым, а у тебя все циклы плохо векторизуемы (везде обращение к каким-то объектам STL, ифы)... И, да, 0fast гораздо чаще замедляет код, чем ускоряет его (например, твой же код без этого работает чуть быстрее 241617897).
Скажу ещё, что прагмы — последний рубеж оптимизации, в твоём случае можно было бы попробовать сначала избавиться от push_back (ты же знаешь, что размер будет $$$n$$$), заменить std::vector фиксированного размера $$$26$$$ на std::array<int, 26>, который быстрее хотя бы потому, что аллоцируется не на куче, а на стеке. Возможно, хешировать пары можно так, чтобы побыстрее было (ксор вообще довольно странный выбор, обычно берут линейную функцию от хеша первого и второго элементов)

→ Ответить

MegaEnderman2009

6 месяцев назад, # ^ |

Понял, спасибо, интересное решение с использованием масства вместо вектора, но разве тогда не лучше вообще использовать обычный сишный массив int a[26]?

Разница с сишным массивом будет косметическая (если вообще будет) -std::array<T, n> на самом деле — просто довольно легковесная надстройка над T[n], и с ним удобно работать в силу того, что это всё же часть STL (например, в твоем случае std::vector<std::array<int, 26>> выглядит довольно прозрачно, а в случае сишных массивов.. std::vector<int*>(?) — как-то стрёмно.
Ну и да, на самом деле конструкция int a[n] вне глобальной области видимости (т.е. внутри какой-то функции) запрещена стандартом, и я, если честно, не знаю, что происходит потом с памятью, т.е. как она высвобождается.
Мораль такая, что если нужно именно пихать, то std::array<T, n> можно заменить на T[n], да, но это примерно такая же крайность, как прагмы, IMO))

Ну в целом да, я если честно не разбираюсь в пропихмвании, прагмах и тп, за все время прям пихать раз 5 приходилось от силы, с учетом задач с других сайтов

Блог пользователя MegaEnderman2009