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

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

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

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

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

Papercut

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

← Rev. 2 →

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

→ Ответить

MegaEnderman2009

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

Понял, спасибо, интересное решение с использованием масства вместо вектора, но разве тогда не лучше вообще использовать обычный сишный массив 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