Java: white ? repeat : repeat;

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

Pio
Posts: 334
Joined: Sat Feb 25, 2012 10:42 pm
Location: Stockholm

Re: Java: white ? repeat : repeat;

Post by Pio »

AxolotlFever wrote: Mon Nov 26, 2018 9:36 pm Hi all,

I am steadily making my Java engine Axolotl less horrible, and there is one particular bit of code that bloats my engine a heck of a lot.

Code: Select all

if (white){
            knights = board.WHITE_KNIGHTS;
        }
        else {
            knights = board.BLACK_KNIGHTS;
        }

Code: Select all

long myPieces = white ? board.WHITE_BISHOPS : board.BLACK_BISHOPS;
And similar. While this might not slow me down a lot (I am not sure about though) it is ugly and I would like to get rid of it.

In your (Java) engine, how do you get around this kind of checking?

Kind regards,
Louis
Hi Louis!

I have been able to remove that ugly code by rotating and mirroring the board. I use the trick both in evaluation (extremely simple for now) and in move generation so that I can remove the ugly special code for pawns. I write my engine in C# but it is neither object oriented nor efficient but I guess it could be a little bit better if I used popcount and some bmi2-instructions because then lots of my bithandling would become branch less such as rotating and mirroring the board. I use a Tri-board representation in a way that rotating and mirroring the board is very cheap and is almost just a mirroring of bits. The nice thing with my very compact representation is that I save the entire board as key in the hash table so that I do not have to worry about hash collisions and that saves me the time to validate that the hash move is legal. Right now I just use the built in dictionary in C# but it would be fun to write cuckoo hashing.

/Pio
DustyMonkey
Posts: 61
Joined: Wed Feb 19, 2014 10:11 pm

Re: Java: white ? repeat : repeat;

Post by DustyMonkey »

mar wrote: Tue Nov 27, 2018 3:20 pm If what you say was true, then these languages (I mean C# and Java) would run as fast as native code. Except for some synthetic benchmarks, this is clearly not the case.
Your logic isnt very sound. The optimizer isnt as good, so the programmer has to make up for it, which does not lead to the conclusion "would run as fast" - leads to the conclusion "might have to do it differently" .. but obviously zero benchmarks accept "doing it differently."

There have been studies (by the ACM) that actually tackle programmers being allowed to do it differently. The one I had read years ago, the result of that study was that the #1 factor in code performance was the programmers level of experience, not the language or compiler. Fit perfectly with what I already figured.

I wholly embarrassed a language bigot once after he showed me a VC98 vs VB98 comparison, a simple file processor that read one byte at a time, by typing 10 contiguous characters into his VB6 code, removing none, and then it was actually just barely beating the C code he was trying to prove a point with.

He was both very disappointed and amazed. Knowledge. I knew that VB6 defaulted to no i/o buffering, and that his C standard library always had a generous buffer of at least 512 bytes (a common disk sector size at the time.)

You can imagine how slow that VB6 code was without any i/o buffering. The 10 characters I added were "len = 4096", an addition that simply added a buffer size to the Open statement in VB6. He then played with optimization levels for the C version, and the C code then was ahead again, but this time by not very much at all.

You get the drift, yes? He was speculating that because his C code was well optimized, that his simple/direct translation would lead to "also well optimized" but... his speculation was wrong. In this case, "doing it differently" wasnt very much different, but I could have also manually added a buffer implementation that didnt use VB6's built in support for buffering and the effect would have been exactly the same, while the code being very much different.
mar wrote: Tue Nov 27, 2018 3:20 pm I also doubt that you get more than a couple of % by using whole program optimization (you can always put stuff in the headers, this is implied by using templates anyway so the compiler knows about what these functions).
Surely you have functions where a parameter, given as a constant (from an enum of piece types for example), decides the functions code path. With whole program optimization, the conditional on that function parameter is eliminated at compile time, and the now heavily reduced function is either inlined or multiple versions of the function are thus generated in the linked object modules.

If you are worried about bounds checking then surely you should be at least as worried about all the unnecessary conditionals in your program that arent optimized away across function boundaries.

This lack of whole program optimization absolutely REQUIRES you to "do it differently" to get the same performance as when aggressively taking advantage of it. The key is that taking advantage of it is exactly "working with the compiler" instead of against it. Doesnt matter what language or compiler you are using, the *only* way to get good efficiency is to work *with* the compiler.
mar wrote: Tue Nov 27, 2018 3:20 pm The problem is that arrays in C# or Java are objects, this is both for safety and it simplifies languages design, but the compiler no matter how good can't do much about it
You say objects but I hope you mean reference types.... The inaccuracies in your word usage is very hard to get over. Not going to draw any conclusions from it yet, but its leading to the conclusion that you dont really know much about any c# implementation (and I guess OOP in general) at all.

Integers are objects but you express no worries about integer performance. The fact that integers are objects only creates performance issues when boxing and unboxing them.

What matters is that you know that integers can be used just as efficiently as in other languages in spite of them being objects, and that you know boxing and unboxing are the expensive bits, and thus you can avoid them, yes?

The word you were looking for was 'references'

You didnt answer this question:

WHAT DID YOU DO BEFORE YOUR C COMPILER WAS ANY GOOD?

Like, 1998 compiler terrible? What did you do?

Did you throw up your hands and was the proud producer of terribly performing programs, or did you learn to work with the compiler and eventually managed to coerce efficient binaries out of the compiler in spite of it being far worse at optimizing than any C# compiler ever was?

Seriously, before C compilers optimized so well for you, WHAT DID YOU DO?
DustyMonkey
Posts: 61
Joined: Wed Feb 19, 2014 10:11 pm

Re: Java: white ? repeat : repeat;

Post by DustyMonkey »

Pio wrote: Tue Nov 27, 2018 8:37 pmif I used popcount and some bmi2-instructions
If you plan on doing so, then you need to know some what I learned today.

1) the intrinsics are not on the nuget server
2) they are on the myget server (still considered experimental)
3) you need to upgrade visual studio to the latest preview build if you want IDE support
4) you still may have to play with your projects configuration files (json) in order to target core 2.2, as the IDE seems to stop a bit short in its search for frameworks due to the path environment variable possibly containing characters that somehow prevent it from searching all of your paths.
Right now I just use the built in dictionary in C# but it would be fun to write cuckoo hashing.
A pitfall here is that the built in .NET hash tables (at least the ones in the main framework, not standard/core) use the keys default hash function. For value types like UInt64, the default hash just returns the value unhashed. Seriously.

No joke. This can lead to absolutely abysmal performance behavior on any of the frameworks hash table classes in some cases. The documentation for the hash table classes does not make this obvious at all.
Pio
Posts: 334
Joined: Sat Feb 25, 2012 10:42 pm
Location: Stockholm

Re: Java: white ? repeat : repeat;

Post by Pio »

DustyMonkey wrote: Tue Nov 27, 2018 10:18 pm
Pio wrote: Tue Nov 27, 2018 8:37 pmif I used popcount and some bmi2-instructions
If you plan on doing so, then you need to know some what I learned today.

1) the intrinsics are not on the nuget server
2) they are on the myget server (still considered experimental)
3) you need to upgrade visual studio to the latest preview build if you want IDE support
4) you still may have to play with your projects configuration files (json) in order to target core 2.2, as the IDE seems to stop a bit short in its search for frameworks due to the path environment variable possibly containing characters that somehow prevent it from searching all of your paths.
Right now I just use the built in dictionary in C# but it would be fun to write cuckoo hashing.
A pitfall here is that the built in .NET hash tables (at least the ones in the main framework, not standard/core) use the keys default hash function. For value types like UInt64, the default hash just returns the value unhashed. Seriously.

No joke. This can lead to absolutely abysmal performance behavior on any of the frameworks hash table classes in some cases. The documentation for the hash table classes does not make this obvious at all.
I did not think it was possible in C# to do it. If my engine will become better (I am currently setting up cutechess client with openings and my testing procedures) I will probably port it to another language which will be easy. Do not worry, I know how data structures work and have overridden the hash function and some other functions/operators, although not with zobrist hashing. My aim is not to do a fast or really good engine but just to try out some really nice things.

If I would try to do a good engine I think I would do a Monte Carlo type of engine with just end evaluation (win/draw/loss) together with endgame support (wdl tables) that would learn by using a type of pieceToSq table that would be merged between the grand children in a lazy way so that information will be shared more wit close relatives. Doing that together with favouring captures a lot (that could be merged in a similar fashion maybe) will lead to much better play where the engine will learn by itself. One nice property will be that generating an opening database will be very easy and you would actually more or less steal the opening databases from the opponents you play against.
Sesse
Posts: 300
Joined: Mon Apr 30, 2018 11:51 pm

Re: Java: white ? repeat : repeat;

Post by Sesse »

DustyMonkey wrote: Tue Nov 27, 2018 9:52 pm WHAT DID YOU DO BEFORE YOUR C COMPILER WAS ANY GOOD?

Like, 1998 compiler terrible? What did you do?
Wrote assembler.
User avatar
emadsen
Posts: 434
Joined: Thu Apr 26, 2012 1:51 am
Location: Oak Park, IL, USA
Full name: Erik Madsen

Re: Java: white ? repeat : repeat;

Post by emadsen »

Either way, I don't believe that bounds checking is the whole story why these managed languages perform so badly on chess engines, most likely their JIT compiler is not as good as fanboys claim... Long story short: if you want maximum performance for your chess program, you don't want to use Java or C#.
Come on Martin, you know better. Just check the CCRL rankings:
Image

Chess22k is written in Java. OK, that's cheap of me to cite someone else's efforts to make my point. My C# mailbox chess engine is rated 2500. I intend to make it stronger using bitboards, but it's on me to deliver.

I'm not disputing your citations of why managed languages are slower than native languages. You're correct about array bounds-checking. It's elided in many cases (when the compiler can prove the bounds won't be exceeded such as in a for loop) but if calculations are done to retrieve an index (like in magic bitboard move generation) array bounds are checked. But none of this is relevant unless the engine author is competing for a spot among the top 50 chess engines. C# and Java are fast enough. There are 1.3x more engines weaker than my C# engine than stronger. There are 8.4x more engines weaker than Sander's Java engine than stronger.

Your argument reminds me of the "You must have the lobster!" proselytizing mocked by Larry David. Why are you pushing C/C++? This thread began as a discussion about how to simplify color-specific code.
The result of that study was that the #1 factor in code performance was the programmers level of experience, not the language or compiler.
This. Totally this ^^^
My C# chess engine: https://www.madchess.net
mar
Posts: 2554
Joined: Fri Nov 26, 2010 2:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Java: white ? repeat : repeat;

Post by mar »

DustyMonkey wrote: Tue Nov 27, 2018 9:52 pm Your logic isnt very sound. The optimizer isnt as good, so the programmer has to make up for it, which does not lead to the conclusion "would run as fast" - leads to the conclusion "might have to do it differently" .. but obviously zero benchmarks accept "doing it differently."

There have been studies (by the ACM) that actually tackle programmers being allowed to do it differently. The one I had read years ago, the result of that study was that the #1 factor in code performance was the programmers level of experience, not the language or compiler. Fit perfectly with what I already figured.

I wholly embarrassed a language bigot once after he showed me a VC98 vs VB98 comparison, a simple file processor that read one byte at a time, by typing 10 contiguous characters into his VB6 code, removing none, and then it was actually just barely beating the C code he was trying to prove a point with.
Go on an embarass me by making Portfish run as fast in C# as SF3 in C++. Dream on.
Surely you have functions where a parameter, given as a constant (from an enum of piece types for example), decides the functions code path. With whole program optimization, the conditional on that function parameter is eliminated at compile time, and the now heavily reduced function is either inlined or multiple versions of the function are thus generated in the linked object modules.

If you are worried about bounds checking then surely you should be at least as worried about all the unnecessary conditionals in your program that arent optimized away across function boundaries.
You seem to overrate IPO/whole program optimization. How many conditionals in performance-critical loops will be optimized away? None. All constants are in headers in C++ so the compiler sees them.
As for your piece enum, the C# compiler actually does a good job in this case.
You say objects but I hope you mean reference types.... The inaccuracies in your word usage is very hard to get over. Not going to draw any conclusions from it yet, but its leading to the conclusion that you dont really know much about any c# implementation (and I guess OOP in general) at all.

Integers are objects but you express no worries about integer performance. The fact that integers are objects only creates performance issues when boxing and unboxing them.

What matters is that you know that integers can be used just as efficiently as in other languages in spite of them being objects, and that you know boxing and unboxing are the expensive bits, and thus you can avoid them, yes?

The word you were looking for was 'references'
Academic nonsense. Elementary types can "behave like objects" at language level, but you'll find no object-related opcodes in CIL for integers of course.
You didnt answer this question:

WHAT DID YOU DO BEFORE YOUR C COMPILER WAS ANY GOOD?

Like, 1998 compiler terrible? What did you do?

Did you throw up your hands and was the proud producer of terribly performing programs, or did you learn to work with the compiler and eventually managed to coerce efficient binaries out of the compiler in spite of it being far worse at optimizing than any C# compiler ever was?

Seriously, before C compilers optimized so well for you, WHAT DID YOU DO?
Sesse already answered this. And don't use caps-lock in a discussion.
Martin Sedlak
mar
Posts: 2554
Joined: Fri Nov 26, 2010 2:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Java: white ? repeat : repeat;

Post by mar »

emadsen wrote: Wed Nov 28, 2018 4:27 am
Either way, I don't believe that bounds checking is the whole story why these managed languages perform so badly on chess engines, most likely their JIT compiler is not as good as fanboys claim... Long story short: if you want maximum performance for your chess program, you don't want to use Java or C#.
Come on Martin, you know better. Just check the CCRL rankings:
Image

Chess22k is written in Java. OK, that's cheap of me to cite someone else's efforts to make my point. My C# mailbox chess engine is rated 2500. I intend to make it stronger using bitboards, but it's on me to deliver.

I'm not disputing your citations of why managed languages are slower than native languages. You're correct about array bounds-checking. It's elided in many cases (when the compiler can prove the bounds won't be exceeded such as in a for loop) but if calculations are done to retrieve an index (like in magic bitboard move generation) array bounds are checked. But none of this is relevant unless the engine author is competing for a spot among the top 50 chess engines. C# and Java are fast enough. There are 1.3x more engines weaker than my C# engine than stronger. There are 8.4x more engines weaker than Sander's Java engine than stronger.

Your argument reminds me of the "You must have the lobster!" proselytizing mocked by Larry David. Why are you pushing C/C++? This thread began as a discussion about how to simplify color-specific code.
The result of that study was that the #1 factor in code performance was the programmers level of experience, not the language or compiler.
This. Totally this ^^^
That's a logical fallacy. Obviously because chess22k has better search (and maybe eval?) than Cheng,
but if you want to compare performance, you have to compare apples to apples.

Even ChessBrain in Visual Basic is stronger than Cheng (why? CB VB is a SF clone)
Rewrite SF in Java and it will be #1 Java engine, much stronger than many other C/C++ engines below.
Rewrite chess22k in a compiled language of your choice with a good optimizer and it will make a very nice jump in the rating lists.

Where I'm pushing C/C++? Use whichever language you like, I don't care.
I simply pointed out that C#/Java are significantly slower (not just a couple of percent like fanboys say) than good compiled languages, replace C with D/Rust/you name it.
So if you want to attack the top engines, with C#/Java you are already losing some 100 elo. Improving 100 elo is hard. It gets much harder as the engine gets stronger.
Martin Sedlak
User avatar
emadsen
Posts: 434
Joined: Thu Apr 26, 2012 1:51 am
Location: Oak Park, IL, USA
Full name: Erik Madsen

Re: Java: white ? repeat : repeat;

Post by emadsen »

Use whichever language you like, I don't care
You seem to care deeply. Enough to hijack a beginning programmer's thread.

Gotta love Internet forums. Here are gathered chess programmers and computer chess enthusiasts, and as Freud observed, the "narcissism of small differences" rules.

I'll leave it at that. I can be of more use helping Louis in the new Engine, Axolotl thread.
My C# chess engine: https://www.madchess.net
mar
Posts: 2554
Joined: Fri Nov 26, 2010 2:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Java: white ? repeat : repeat;

Post by mar »

emadsen wrote: Wed Nov 28, 2018 6:58 am
Use whichever language you like, I don't care
You seem to care deeply. Enough to hijack a beginning programmer's thread.

Gotta love Internet forums. Here are gathered chess programmers and computer chess enthusiasts, and as Freud observed, the "narcissism of small differences" rules.

I'll leave it at that. I can be of more use helping Louis in the new Engine, Axolotl thread.
You seem offended by the fact that C# produces significantly slower code than compiled languages, but that's not my problem. Quoting rating lists or whoever you want won't change that a bit.
Martin Sedlak