Hello
Some codingamers @nmahoude, @Zylo contacted me to share java tips. And I know that some others (@skyyker, @Nerchio, @BrunoFelthes, @LoganWlv, @Jahz…) should also be interested.
So I created a CodingameFramework on github. This is the kind of code I use to start some multis. Most of my common java codingame tricks are used in it.
Some of the utilities should also be interesting for java codingame beginners (there’s a Logger, a file merger, a beam searcher, a flood fill implementation).
I hope this post helps sharing/discussing java experiences on codingame (tips, problems, code…).
I’ve encountered a problem during Spring Challenge 2021 :
I tried to use objects instead of arrays in my Beam Search (it’s easier to use and allows to use different types for the fields). But even with a time limit of 60ms I had a lot of timeouts in the arena. So I switched to array (like WayUtils). And I could set a time limit to 90-95 ms with almost no timeout.
I’m almost sure I didn’t change anything else.
If someone has a clue of the reason why i’m interested.
Hey,
Looks very interesting. I like to play java too and timeout are indeed quite annoying.
Me i’ve encountered problems in Fall Challenge 2020 (cause of 50ms/turn) and the game turn in an java optimization problem… which was actually very rewarding and quite fun !
I will take a closer look later but for what i see i could suggest :
-
Do not use Scanner class (it was my biggest problem on Fall Challenge 2020) because the buffer size is 1024 and force sometimes 2 round trip in 1 turn (i could observe some delay of ~15ms just to read input). I used the last option of this article.
-
Reverse the loop to avoid reading at each turn the size or keep it in a variable :
for (int i = 0; i < TMP_LISTS.length; i++) { ==> for (int i = TMP_LISTS.length - 1; i>= 0; i–) {
It does not apply to constants ! -
Need to benchmark but i am not sure about the efficiency of using byte. It use indeed less memory but every manipulation convert to an int and need to be cast back into a byte. And for what i know and test i’ve done, looping over an int is faster than a byte for example. Also for my small experience i never get an out of memory on CodinGame.
-
“Direction.values()”. This is bad ! Enum values return a copy every time it is called !
-
(k - 1) / 2 ==> k - 1 >> 1
-
2 * k + 1 ==> k << 1 | 1
-
Concerning GC i do not forbid myself of using Object but i allocate them at initialization time in a pool. Because i keep reference the entire game i never notice any latency due to GC.
I never felt the need of using it but i keep it mind for the d-day ! The use of unsafe… I think that GC does not manage what is allocated by it… so technically no more GC problem. I know that it is not to hard to get it in java 8 but could read that it is not the same in java 11 !
Thanks for your feedback and your tips :
-
I didn’t know about enum.values(). I’ve updated the project and will be careful from now on.
-
I’ve never noticed problems while reading the inputs (the time taken doesn’t vary a lot). But I’ll try your tip (maybe it’ll solve some of the mysterious timeouts i’ve been having in some games).
-
About the use of byte : even if you don’t have OutOfMemoryError your bot might be slower. At least that what I noticed when I increased too much the cache sizes.
Nice work @wala, I was trying to do something like it for a while.
I know that it is not easy to organize things…
I will take a look and I will try to contribute!
Thanks for the huge work @wala
Since we’re on JAVA CodingGame Tips, may I ask if you guys found a way to generate random numbers faster than ThreadLocalRandom.current().nextInt(int max)
?
I tried to implement Xoshiro256++, but it seems good only in C/C++.
I was also thinking of some kind of random bytes buffer which you will query and refill when empty.
@LoganWlv
In some cases it will be enough to have 2 big coprime integers and generate big cycle with non repeating ints.
private static long P1 = BIG_PRIME_1;
private static long P2 = BIG_PRIME_2;
private static long current = INITIAL_RANDOM_NUMBER_IN (1..P2-1);
private static long getNextRandom(long max) {
current = (current * P1) % P2;
return (current % max);
}
Small example: (5, 7)
1
(1 * 5) % 7 = 5
(5 * 5) % 7 = 4
(4 * 5) % 7 = 6
(6 * 5) % 7 = 2
(2 * 5) % 7 = 3
(3 * 5) % 7 = 1 => (1, 5, 4, 6, 2, 3): you have (7 - 1) non repeating ints
Thanks for your feedbacks.
I’ve added a package random. There are two additional “doc” links in the XORShiftRandom Javadoc.
That’s what i’m using in UTTT.
Edit : see below
While trying to find an answer to my question about arrays vs objects, I ran into the problem of pointer chasing. which might be a lead…
And I watched this video Java Performance Puzzlers by Douglas Hawkins where he said :
“hardware doesn’t like things being jumbled in memory it wants nice contiguous compact things”
The whole video is worth watching.
Just tried some performance on random generator.
My current best is java.util.SplittableRandom which seems to be 4 times faster than your XORShiftRandom. You have the same results?
When I chose XORShiftRandom for my MCTSs (over SplittableRandom…) it was based only on internet searchs and submits in the arena.
I did several benchmarks using Java Microbenchmark Harness :
Benchmark | Mode | Cnt | Score | Error | Units |
---|---|---|---|---|---|
SplittableRandom | avgt | 25 | 246045,663 | ±27970,447 | ns/op |
XORShiftRandom | avgt | 25 | 357386,862 | ±46990,309 | ns/op |
SplittableRandom performs better (but not 4 times better).
There a Stack Oveflow’s post where @LoganWlv give a link to benchmark results and an explanation.
So yes SplittableRandom seems to be a better choice.