Improve performance

[meisterT]

For some checktestdata programs performance is terrible. Are there low hanging fruits that improve the general performance of checktestdata?

[eldering]

Some issues to look into:

• FLOAT is slow: changing from REGEX("[0-9.]+") to FLOAT(0,6.2832) made reading 10^5 floats take 44 seconds longer (total runtime including reading other stuff went from 11 to 55 seconds)
• INARRAY is even slower: 10^5 checks of an INT inside an array of 10^5 INTs increased the runtime of the same testcase to 7.5 minutes.

[eldering]

These combined fixes improved checktestdata runtime on this testcase from ~8 min to ~2 sec.

[austrin]

An example where I gave up on using checktestdata and switched to python due to speed: problem I (Interception) from NCPC 2016. Problem package available here: http://ncpc.idi.ntnu.no/ncpc2016/ncpc2016-packages.tar.bz2 (there is an unused checktestdata script included).

There is lots of data so maybe there is not much to do, but one feature that would have been helpful here would be a version of the UNIQUE function that compares entries as unordered (multi)sets rather than ordered tuples. Then one could have skipped the annoying if-swap in the main loop, which takes a bit of the time (and pollutes the code). (That feature alone wouldn't have made the script fast enough, but it would at least have made it a bit less slow.)

[eldering]

I've tested this on my computer. The test case 09.max_ans.in check runs in 31 seconds, without the swap it takes 20 seconds. That's a decent bit less, but I'm not sure it warrants introducing a completely new command.
I also analyzed the call graph with callgrind and a quick glance did not show any clear targets for optimization. A fair amount of time (14%) Is spent in GMP functions, another 10% in boost::variant, and 8% just in std::__lexicographical_compare_impl over GMP integer types.

[austrin]

That's a decent bit less, but I'm not sure it warrants introducing a completely new command.

Right, I agree that this speed improvement on its own is not sufficient reason to add such a command, but there may be other small reasons as well which together make it worth it. Another such reason could be that this type of constraint is somewhat common and the swap dance is a bit annoying and makes the scripts harder to read, so such a command could be nice to have regardless of performance issues. I don't really have a strong opinion on this, but at least wanted to bring up the possibility for you to consider.

[austrin]

@eldering having been frustrated by a few slow ctd scripts in the past weeks, I was wondering a bit more about potential speed improvements. One thought: would it be possible to add some sort of pragma-ish directive to force 64-bit integer arithmetic instead of arbitrary precision (since GMP takes a lot of the time)? I guess one would then want to do overflow checks every time one does an operation (and raise an error on overflow), but maybe it would still be faster, in particular for the common "read a million integers between 1 and 1000" type of format.

[eldering]

[Funny, I was just looking into a few minor checktestdata issues, including this one.]

Yes, I think that would be a good avenue to explore, and would make sense if it improves performance significantly. I currently don't have the WF2018 problemset available. Is is (publicly) available somewhere? Otherwise, I'd have to wait a little before our backups are online.

[austrin]

I don't think so, but one set you could look at is NWERC 2017, in particular the problems ascendingphoto and factorfree. The validators look almost the same, except that one stores the values in an array (without using them for anything), and that one is about 3x slower than the other. But even the faster one is a bit sluggish -- on my machine it takes around 1.5s just to read a million numbers which with a lot of test files gets a bit annoying.

[TPolzer]

I have an experimental branch of checktestdata in antlr_rewrite that seems to be a lot better performance wise, on the other hand it is by far not as well tested and it currently doesn't really have helpful error messages for non conforming input.

[thijskh]

Well, the testsuite passes, so that's already quite something?