Встречайте PyPy на Codeforces

9 лет назад, # ^ |

← Rev. 2 →

Выбери более насосную задачу — там поглядим... На миллисекундах статическая погрешность большая, например на разогрев jit должно время уйти... %)

→ Ответить

Igorjan94

9 лет назад, # ^ |

так-то оно так, просто я python использую как раз для таких задач див2 А-С из-за скорости тайпинга
хотелось его использовать без какой-либо боязни получить ТЛ на таких задачах, а получается, что выигрыш получается "наоборот" на сложных и долгих задачах
а так, я не мастер питона и знаю его как пару клевых фич/немного синтаксического сахара, чтобы писать на нем более сложные задачи. Наверняка кто-нибудь напишет что-то существенное и там будет значительный прирост в скорости

→ Ответить

9 лет назад, # ^ |

для таких задач див2 А-С из-за скорости тайпинга

ну да, я его для того же юзал помнится — по сравнению с толстой джавой это выглядело оч экономно :)

а получается, что выигрыш получается "наоборот" на сложных и долгих задачах

которые вообще м.б. уже можно и не на питоне писать :)

Я всецело согласен — мне вообще сомнительно что от PyPy будет много проку для спортивных задач с ограничением в 1-2 секунды. В общем кажется в этот раз команда CF проделала хорошую, но вероятно, невостребованную работу... :(

→ Ответить

omtcyf0

9 лет назад, # ^ |

← Rev. 3 →

+44

Или даже так

→ Ответить

9 лет назад, # ^ |

pypy -- это же JIT (динамический компилятор), поэтому так и должно быть. Опережать он должен на более длительных временах выполнения.

→ Ответить

dkirienko

9 лет назад, # ^ |

Pypy иногда работает медленней сpython, мы наблюдали случаи, когда pypy был в два раза медленнее, чем cpython. Но это редкие случаи, как правило, все-таки pypy быстрее.

По-видимому, трудно предсказать, в какому случае будет быстрее pypy, а в каком — сpython. Для этого нужно как минимум очень хорошо понимать, как устроен каждый из них.

→ Ответить

hellman_

9 лет назад, # |

Три сабмита, второй и третий с ручными оптимизациями.

По поводу pypy3 — разработка ведется не так давно, у разрабов основной задачей была совместимость с py3 и я думаю они пока не сильно работали над производительностью.

→ Ответить

hellman_

9 лет назад, # ^ |

← Rev. 2 →

А вот здесь >2с (не проходит) vs 0.404с:

Ещё пример, алгоритм ~2.5kk операций:

PS. Почему то в попытках в моем профиле неверная ссылка на задачу.

→ Ответить

hellman_

9 лет назад, # ^ |

Хм у pypy почему то raw_input() / print медленные. Нужно sys.stdin/stdout юзать..

→ Ответить

virtualight

9 лет назад, # ^ |

Хм у pypy почему то raw_input() / print медленные

потому что в PyPy эти функции — просто обертки над sys.stdin/stdout с кучей рефлекшна и обработки исключений. В обычном CPython такой проблемы нет, потому что они написаны на C.

→ Ответить

9 лет назад, # |

← Rev. 2 →

-37

добавьте JIT для C++ :-) в MSVC он уже есть

→ Ответить

9 лет назад, # ^ |

+28

Что?

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

хапчо. /clr:pure http://codeforces.com/blog/entry/14083

→ Ответить

9 лет назад, # ^ |

← Rev. 3 →

Это имхо не для "вообще C++" это для CLR от .NET — не важно на каком языке ты под неё пишешь.

В чём смысл (для спортивных задач) писать на C++ под .NET, чтобы получилось нарочно медленнее а потом кое-как оптимизировалось JIT-ом — я не представляю.

→ Ответить

9 лет назад, # ^ |

-30

Какая хрен разница, достаточно большое подмножество (если не всё) Си++ там работает, а через что оно уже работает, уже отдельная тема. Ты хотя бы прочитал ссылку? Я привёл пример, в котором JIT быстрее едва ли не в полтора раза. И ты, похоже, не понимаешь причины того, почему C#/Java медленее С++. Дело не столько в JIT, а другой семантике языка (там нет UB и вс ё выполняется строго слева направо) и неотключаемых проверках индексов при обращении к массиву (а если это массив ссылок, то требуется еще проверка типа объекта)

→ Ответить

9 лет назад, # ^ |

← Rev. 4 →

И вовсе он не быстрее. Мне лень перезагружаться в Windows на своей машине, поэтому я прогнал (несколько раз! один раз ничего не говорит) на соседней XP с VS2010, и нативная версия работает за 7000 тиков, а CLI — за 10000 тиков. И совершенно нет причин, по которым JIT был бы быстрее на таком коде.

Дело не столько в JIT, а другой семантике языка (там нет UB и вс ё выполняется строго слева направо) и неотключаемых проверках индексов при обращении к массиву

Вообще я согласен, но хочу заметить, что JIT на это наплевать и он всех оптимизирует одинаково, а проверки индексов, бывает, наоборот, помогают сделать циклы быстрее (когда они выносятся за цикл, а внутри производится оптимизация с учётом того, что индекс точно находится внутри границ — в частности, что индекс неотрицателен и не переполняется при прибавлении шага цикла).

(а если это массив ссылок, то требуется еще проверка типа объекта)

Совсем даже не требуется. Массивы разных типов — это разные типы; и в CLI, и в JVM. И для generic collections в CLI тоже не требуется; а вот в Джаве — да, вот там требуется. Не говоря уже о том, что не важно, C# это или C++/CLI, а массивы ссылок работают абсолютно одинаково.

[Edit для читателя: Нет, всё-таки требуется при записи в массив, см. ниже.]

→ Ответить

9 лет назад, # ^ |

← Rev. 3 →

Ненуок, я нашёл то сравнение C# с C++, которое упомянуто в твоём блоге без ссылки: http://stackoverflow.com/questions/2285864/why-is-net-faster-than-c-in-this-case

CLR JIT will inline one level of recursion, MSVC 8 SP1 will not without #pragma inline_recursion(on)

(Вроде датировано 2010 г. и версия MSVC даже меньше, чем я использовал, так что не знаю, почему у меня этого не произошло. Или, может быть, произошло, но CLI-версия всё равно медленнее?)

Ну ок. Да. JIT может так сделать. С такой же лёгкостью AOT может так сделать! MSVC этого не делает по умолчанию. Зря. Но это же не повод кричать, что JIT лучше в общем случае. Не говоря уже о том, что помогает это не шибко-то часто. Вон, как я говорю, проверка индексов тоже бывает, что ускоряет, — это же не повод кричать, что с проверкой индексов всё получается быстрее, чем без неё.

→ Ответить

9 лет назад, # ^ |

← Rev. 3 →

-14

Вообще я согласен, но хочу заметить, что JIT на это наплевать и он всех оптимизирует одинаково

Если писать на C++/CLI pure и C#/unsafe то результаты будут похожие, но, простите, когда речь заходит о скорости нормального с# кода, а не unsafe.

Совсем даже не требуется. Массивы разных типов — это разные типы;

Требуется. Допустим есть класс "фрукт" и класс "яблоко" и есть метод, принимающий массив фруктов и что-то с ним делающий. Так вот, Java позволяет передать в этот метод массив яблок (потому что каждое яблоко является фруктом) -- но там поэтому стоят рантайм проверки, чтобы никто в массив, аллоцированный как массив яблок, и имеющий формальный тип массив фруктов, не положил грушу. В общем, иди почитай про трансляторы, а не неси чушь с апломбом.

Object[] objects = new Integer[10];
objects[0] = "Hello World"; // run-time check!

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

но, простите, когда речь заходит о скорости нормального с# кода, а не unsafe

И что? Разницы никакой. Unsafe только просит компилятор не ругаться на использование указателей. Генерация кода, который и так компилируется, от этого не меняется. Ни промежуточного, ни машинного.

Так вот, Java позволяет передать в этот метод массив яблок (потому что каждое яблоко является фруктом) -- но там поэтому стоят рантайм проверки

Touché, про это я забыл. Но даже они только при записи в массив, а JIT’у ничто не мешает их соптимизировать при возможности.

И не надо грубить.

→ Ответить

9 лет назад, # ^ |

-8

Unsafe только просит компилятор не ругаться на использование указателей. Генерация кода, который и так компилируется, от этого не меняется. Ни промежуточного, ни машинного.

совершенно правильное и совершенно неуместное замечание

а JIT’у ничто не мешает их соптимизировать при возможности.

только что у вас JIT был медленее, а тут "не мешает". Ну может соптимизировать. Иногда. В общем случае нет.

а JIT’у ничто не мешает их соптимизировать при возможности.

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

Я привёл пример, в котором JIT быстрее едва ли не в полтора раза.

А потом ты скажешь что твой пример не работает на CF потому что здесь компиляторы юзают Mono...

Works on my machinie

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

А потом ты скажешь что твой пример не работает на CF потому что здесь компиляторы юзают Mono...

на CF есть как MS так и Mono.

→ Ответить

9 лет назад, # ^ |

← Rev. 4 →

При всём вышесказанном я лично не имею ничего против добавления нового пункта в список компиляторов, MSVC /clr:pure; а лучше даже просто /clr, а не /clr:pure. Помешать это никому не должно, ну так и фиг с ним. У C++/CLI как у языка программирования даже есть свои плюсы, в первую очередь доступ одновременно к библиотекам C++ и .NET. Но подаваться он должен именно как C++/CLI, а не как C++ JIT.

→ Ответить

9 лет назад, # ^ |

я лично не имею ничего против добавления нового пункта в список компиляторов

Команде разработчиков CF наверняка любопытно для начала определить сколько человек (кроме beatoriche) собираются этим пунктом воспользоваться. Это ж все же не две строчки в конфиг вписать (хотя учитывая наличие C# и F# м.б. не оч сложно).

→ Ответить

9 лет назад, # ^ |

Да, совершенно верно. Я забыл это сказать.

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

-15

Так вот как раз именно -- две строчки в конфиг вписать. C# и F# тут не при чём вообще, в новом MSVC это есть и так без дополнительных пакетов. Сложность только тут может быть, как .NET работает -- через обычный сандбокс или особый. А вот для всяких хаскелей, которыми один фиг никто не пользуется, надо сами трансляторы устанавливать.

→ Ответить

9 лет назад, # ^ |

-14

суки умрите я вас ненавижу

→ Ответить

9 лет назад, # |

+12

Сходил потестить новую фичу в "Запуск на сервере", и с ужасом (случайно) обнаружил, что тут в питоне установлена numpy. Что за страшная несправедливость? Эта библиотека не входит в стандартную поставку Python'а, и, между прочим, может дать огромное приемущество пишушим на питоне в некоторых задачах (например, если нужно умножать большие матрицы).

Например, следующий код:

import numpy as np

A = np.random.random((1500, 1500))
B = np.random.random((1500, 1500))
C = np.dot(A, B)

работает на питоне меньше секунды, а straight-forward (без built-in магии и ассемблерных вставок) перемножение таких матриц на C++ не укладывается в 10 секунд.

Я считаю, для восстановления мирового баланса надо добавить аналогичные библиотеки для C++ и Java (cblas/jblas, или хотя бы numpy4j).

→ Ответить

MikeMirzayanov

9 лет назад, # ^ |

Видимо, numpy входит в стандартный дистрибутив PyPy. Я подумаю как быть, но маловероятно, что будут установлены cblas/jblas/numpy4. Скорее либо удалю numpy из PyPy, либо оставлю как есть, следуя принципу установки дистрибутива по-умолчанию. Ведь не режем же мы Policy Based Data Structures (ext/pb_ds/assoc_container.hpp) из g++, хотя это тоже явный specific от GCC, лежащий за пределами стандарта С++.

→ Ответить

9 лет назад, # ^ |

А можно тогда добавить "-march=native -mavx -mavx2" для GCC? Чтобы можно было получить сопоставимую производительность без адского ассемблера (кстати, а зачем -fno-asm для C в параметрах? только чтобы участникам пришлось писать __asm__ вместо asm?).

→ Ответить

MikeMirzayanov

9 лет назад, # ^ |

Приведи пример кода, где -mavx -mavx2 там сильно помогут. Чтобы и потестить на нем и лучше понять.

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

Ок, вот код (на codeforces не компилируется из-за выключенного avx). Я максимально соптимизил "наивную" версию, чтобы не было вопросов про "сильную" помощь (это ускорило совсем наивную версию раза в 3, но до numpy всё равно далеко).

Моя реализация с avx явно не очень оптимальная, она всё ещё немного проигрывает numpy; однако она выигрывает в 2 раза у заоптимиженной "наивной" реализации. Думаю, если использовать _mm256_dp_ps() вместо того что у меня — должно догнать numpy.

(код в правке)

→ Ответить

9 лет назад, # ^ |

← Rev. 3 →

А что, -march=native не включает AVX?

А вообще у меня где-то был список, чего бы надо поправить во флагах и замере времени на Кодфорсах… Выкопать бы его. Но это ж надо вспоминать, куда я его сунул!

→ Ответить

Madiyar

9 лет назад, # ^ |

numpy в python 2.7 тоже работает.

→ Ответить

9 лет назад, # ^ |

+13

Да вроде не входит… Ни в PyPy, ни в CPython. Под PyPy стандартный numpy даже и не идёт-то, надо их собственный форк использовать. Вот я сейчас зашёл на сайт проверить, не вкладывают ли они его в виндовые бинарники — там отдельный раздел Installing NumPy (optional). Видать, всё-таки не вкладывают.

Зато NumPy входит во многие сторонние дистрибутивы Питона «всё в одном»: Canopy, Anaconda… Может, на Кодфорсах установлен именно один из таких дистрибутивов, а не официальный?

(Это я не агитирую против NumPy. Это мне просто интересно, как он вообще здесь оказался.)

→ Ответить

savinov

9 лет назад, # ^ |

-8

А какая, собственно, разница? Никто же не запрещает пользоваться ей, все участники в равных условиях. Таким образом можно запретить BigInteger в Java, потому что в плюсах его нет, или например, std::set в C++, хотя в паскале его тоже нет.

→ Ответить