Either way thank you for all the amazing free content you've already put out and good luck on the new endeavor!

Seems like they don't believe that it solved the 3200 rated problem (https://codeforces.com/contest/1810/problem/G) w/o data leakage

For context, there are only around 20 humans above 3200 rating in the world. During the contest, there were only 21 successful submissions from 25k participants for that problem.

Comments URL: https://news.ycombinator.com/item?id=38521818

Points: 3

# Comments: 0

DEF CON 25 - John Sotos - Genetic Diseases to Guide Digital Hacks of the Human Genome (2017): https://www.youtube.com/watch?v=HKQDSgBHPfY

PyPy is pretty well stress-tested by the competitive programming community.

https://codeforces.com/contests has around 20-30k participants per contest, with contests happening roughly twice a week. I would say around 10% of them use python, with the vast majority choosing pypy over cpython.

I would guesstimate at least 100k lines of pypy is written per week just from these contests. This covers virtually every textbook algorithm you can think of and were automatically graded for correctness/speed/memory. Note that there's no special time multiplier for choosing a slower language, so if you're not within 2x the speed of the equivalent C++, your solution won't pass! (hence the popularity of pypy over cpython)

The sheer volume of advanced algorithms executed in pypy gives me huge amount of confidence in it. There was only one instance where I remember a contestant running into a bug with the jit, but it was fixed within a few days after being reported: https://codeforces.com/blog/entry/82329?#comment-693711 https://foss.heptapod.net/pypy/pypy/-/issues/3297.

New edit from that previous comment: there's now a Legendary Grandmaster (ELO rating > 3000, ranking 33 out of hundreds of thousands) who almost exclusively use pypy: https://codeforces.com/submissions/conqueror_of_tourist

There's no reason to build the repeats up by doubling since the string concatenation of two same string is still linear time.

For example, using CPython, if you try to make an array of a million ints, you won't get `int[1000000]` in your memory layout. Each int would actually be an object, which is huge and inefficient to reference (they are something like 24+ bytes each).

PyPy on the other hand, works as expected.

I think the more important point is that PyPy when written like C code, can actually get within 2x of the performance of C code. If it's any slower, python won't be a viable language in competitive programming at all.

(CPython is sometimes still used on other platforms like atcoder.jp, but only because they allow third party libraries like numba and numpy which can fill the same role pypy does)

https://codeforces.com/contests has around 20-30k participants per contest, with contests happening roughly twice a week. I would say around 10% of them use python, with the vast majority choosing pypy over cpython.

I would guesstimate at least 100k lines of pypy is written per week just from these contests. This covers virtually every textbook algorithm you can think of and were automatically graded for correctness/speed/memory. Note that there's no special time multiplier for choosing a slower language, so if you're not within 2x the speed of the equivalent C++, your solution won't pass! (hence the popularity of pypy over cpython)

The sheer volume of advanced algorithms executed in pypy gives me huge amount of confidence in it. There was only one instance where I remember a contestant running into a bug with the jit, but it was fixed within a few days after being reported: https://codeforces.com/blog/entry/82329?#comment-693711 https://foss.heptapod.net/pypy/pypy/-/issues/3297.

I think it's still a relatively low effort way (just need to write a scraper) to create a benchmark on a diverse set of algorithmic tasks that have clearcut criteria on AC/TLE/WA. PyPy is often 10x faster than cpython on these problems (and just 2x slower than equivalent C++ solution) so it will be a much nicer headline too if you can achieve similar performances!

Though I can also see how it can be completely irrelevant for server workloads. Pypy's unicode is so slow, some people on codeforces still use pypy2 over pypy3 just to avoid it. And c extensions is so bad on pypy, you can often get better performance on cpython if you need to use numpy.

I wonder if he would be interested in optimizing for purely algorithmic tasks?

There are a lot active and successful CPython and PyPy users on https://atcoder.jp/. For example:

https://atcoder.jp/contests/practice2/submissions?f.Task=&f.... (the user "maspy" is rated at 2750 using only cpython!!!)

https://atcoder.jp/contests/practice2/submissions?f.Task=&f.... (though pypy is more practical)

I am linking to atcoder because their testing data is public so you can rerun contestants solutions using both pyston/cpython/pypy for benchmarking purposes: https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAk_SECQ2Nc6SVGi...

Right now, other than a handful of people who figured out how to make numba's jit work, only pypy is viable for competitive programming. I wonder if you can do better than pypy?

There are also a few red coders on codeforces.com who mostly use pypy (cpython is completely unviable there because numpy and numba is not installed)

https://codeforces.com/submissions/pajenegod

https://codeforces.com/submissions/conqueror_of_tourist

But codeforces' test cases aren't public anyway so it's not as relevant.

But yea, not while you're trying to ship.

For typing hinting, I've been annotating with @overload which is just god awful ugly. And you still need to switch based on instance type for the actual implementation.

I will try this way instead!

[1] https://www.python.org/dev/peps/pep-0484/#function-method-ov...

BST supports log(n) min/max/inserts/removes (among other stuff).

It supports O(1) push_front/pop_front/push_back/pop_back/operator[]/at (like you would expect from a deque) but also O(sqrt(N)) insert and remove from middle!!!

The paper was from 1999 and 2001 but I only learned about it from a recent HN post[3] where some guy rediscovered it (20 years too late). I still wonder why this design lost to the std::deque we have in STL today.

[1] http://www.cphstl.dk/Report/Deque-first-attempt/cphstl-repor...

[2] https://www.ics.uci.edu/~goodrich/pubs/wads99.pdf

[3] https://news.ycombinator.com/item?id=20872696