Обнаружил интересное поведение в среде MS C# пока решал 415E - Машмох и операция реверс — добавление одной строки Console.Write("") неожиданно увеличило производительность на 30%.
Можно сравнить два решения 6429939 и 6429944, которые отличаются только одной этой строкой. Время выполнения для них соответственно 2105мс и 1777мс.
Несколько фактов:
- вставка этой инструкции в начале программы не даёт эффекта
- так же бесполезно оказывается вставить её непосредственно перед выводом результата
- улучшение производительности заметно при больших объёмах данных (здесь ~1МБ)
Есть идеи?
UPDATE Вышеуказанные решения в данный момент стали работать подобным образом, что похоже на рандом. Но их "полная" версия до сих пор отличается более чем в два раза, что нельзя объяснить разбросом. 6430646 и 6430655
UPDATE2 Провёл ряд экспериментов, вот что получается:
- в среде C# Mono проявляется тот же эффект
- локально повторить не удаётся
- отключение оптимизации с помощью атрибута
MethodImplприводит к нормальному исполнению программы - отключение оптимизации с помощью
#pragma optimize( "", off )не даёт никакого эффекта - замена
Console.Write("")наConsole.Out.Flush()илиConsole.In.Close()тоже даёт программе нормально выполняться - в одной из строк чтения данных по-ошибке использовалось лишнее приведение к списку, а потом к массиву
Console.ReadLine().Split().Select(int.Parse).ToList().ToArray(). УбираемToList()— и чудо, программа снова работает как положено (отдельно измерял время выполнения лишней процедуры — оно оказалось достаточно маленьким, и не объясняющим эффекта) - замена
Interlocked.Exchange()на обычные операции присвоения так же приводит к нормальному выполнению программы
Возникает предположение, что операции чтения-записи могут блокировать Interlocked.Exchange, что каким-то образом возникает после оптимизаций компилятора. Поэтому эту функции следует применять с осторожностью. Непонятным остаётся что за оптимизации мог сделать компилятор, чтобы ввод-вывод смог заблокировать Interlocked.Exchange()
Исходники: подвисающее 6434408, без Interlock-a 6434414, без ToList() 6434416
Просто небольшой рандом. Посылка, идентичная первой, без строки. Отработала за 1793мс, примерно как вторая
Весьма странно — я сделал порядка 10 разных посылок с и без указанной строки — разница всегда подтверждается.
P.S. Сделал ещё штук по 10 отправок каждого варианта — действительно, выглядит как рандом с +-20%. Но ведь два часа назад, когда я создавал пост, рандома не было, поведение чётко отслеживалось. В моём оригинальном решении эта строка сводила решение от стабильного TIME_LIMIT_EXCEEDED (а это >4с) к проходимому решению за 1.6с. И продтвердилось это с десяток раз. Вот, взял старое решение, отличается тоже одной строкой, сравните 6430646 и 6430655
А как же 6430594.
UPD Опоздал.
Несмотря на то, что в "почищенной" версии разница в данные момент перестала проявляться, в "полном" варианте она до сих пор есть, и огромная. Для меня это выглядит пока что не понятно
Если действительно такой интерес — надо смотреть MSIL код, там разница определится. А можно еще проще — в десятке следующих задач всегда добавлять эту штуку. А потом потестить их все снова без нее. Если хоть иногда помогает — пофигу, надо ставить всегда значит)
Я вот только что взял и посмотрел дизассемблированный код. Разница как раз только в наличии вызова функции
Console.Write("");.Скорее, надо смотреть исходники класса Console в .Net фреймворке. Только, подозреваю, чтобы добраться до сути, надо будет перелопатить еще очень много других классов. И то не факт, что проблема лежит там, а не в особенностях тестирования на серверах CF.
Эта тема уже обсуждалась, и все здесь очень просто. На CF несколько решений могут запускаться на одной тестирующей машине параллельно, отсюда как раз возникает разброс времени выполнения.
Предвкушая один вопрос, сразу на него отвечу: если решение получает TLE, то оно после этого запускается уже на отдельной машине (именно на этом тесте, или на всех — не в курсе).
It is more interesting why did you try putting that dummy line in the code XD