[JAVA] CodinGame Tips

[wala]

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…).

[wala]

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.

[chouch]

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 !

[wala]

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.

[BrunoFelthes]

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!

[LoganWlv]

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.

[Zylo]

@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

[wala]

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

[wala]

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.

[skyyker]

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?

[wala]

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.