Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Blowing up my compile times for dubious benefits

claytonwramsey.github.io

Post reply on HN
Print view View original

21–28 of 28 posts

Re: Blowing up my compile times for dubious benefits

#21

Post by vlovich123 »

JonChesterfield wrote: post #18
evmar wrote: post #3

> to make all the constants known at compile time, everything has to be written in a const function. This means: No allocations [...] No for loops These constants are relatively unchanging relative to the rest of your program. Why not write a code generator (without the above weird restrictions) to compute them once and save the result?

It is better to write obscure compile time code in the metalanguage than to write a separate program which generates the same result, even if the separate program would generate something than can then be spliced in at compile time anyway. Well, "better". "Industry practice" might be more accurate. Also "necessary" if your build system is garbage and/or your team is frighted of code generators but not meta-programmin…

You can write the compile time generation as a separate Rust program. It has the added advantage that you only need to run it if the program itself changes and otherwise check in the generated code.

The main advantage is that you don’t have to generate Rust code as a string. You’re just generating Rust data structures in Rust and that is convenient. Not sure if there’s any tricks for that.

Re: Blowing up my compile times for dubious benefits

#22

Post by mcdonje »

evmar wrote: post #3

> to make all the constants known at compile time, everything has to be written in a const function. This means: No allocations [...] No for loops These constants are relatively unchanging relative to the rest of your program. Why not write a code generator (without the above weird restrictions) to compute them once and save the result?

My first thought would be to store the magic numbers in either a db or a config file.

Re: Blowing up my compile times for dubious benefits

#23

Post by afdbcreid »

littlestymaar wrote: post #14

> I suspect that the constant evaluator in Rust is just plain slow. IIRC, it's using the miri interpreter, which is indeed very slow.

Not exactly: IIRC it is part of Miri somehow, but it doesn't do all the fancy checks for UB (only part of them).

Re: Blowing up my compile times for dubious benefits

#24

Post by claytonwramsey »

harerazer wrote: post #4

While this post has a good amount of substance, I found it rather hard to understand due to small mistakes (or hidden assumptions, or something else?). All of which seem easily fixed/clarified, but these sorts of things are unnecessary friction for readers. Edit: Thanks to Jasper for stating the big hidden assumption made by the author - that he is only considering the case of being blocked by enemy pieces, not one's…

Hi, I'm the original author! This is my first post. I might talk more about chess engines in my blog in the future...

Some background: I taught a class on chess engines this spring (at some point, I'll write up a postmortem on it, maybe). This post was originally derived from my lecture notes for the class, and was (if I remember correctly) the 5th lecture, so I could make more assumptions about the students being steeped in chess-engine lingo.

Josh Triplett is entirely correct here on the masking technique. There are two steps to sliding-piece move generation: first, creating the set of squares a piece can "see," and then the set that it can attack. Magic bitboards are used for generating the set of squares a piece can see.

In terms of where magic bitboards come from: there's not that much in terms of logical derivation. You just have to kind of squint and say, "yeah, I believe that'll work." Magic numbers are found by brute force trial-and-error.

Collisions are caused when the magic multiply doesn't actually yield a perfect bit extraction. Imagine if O * M >> 59 was instead some gross expression of all five bits. The magic number for B1 here is actually an exception - things are not usually so easy. However, if two different positions have the same attack set, and they get sent to the same index by a magic multiply, it doesn't matter that they collided because they map to the same value.

Re: Blowing up my compile times for dubious benefits

#25

Post by claytonwramsey »

evmar wrote: post #3

> to make all the constants known at compile time, everything has to be written in a const function. This means: No allocations [...] No for loops These constants are relatively unchanging relative to the rest of your program. Why not write a code generator (without the above weird restrictions) to compute them once and save the result?

I thought about that. The big benefit of using `const` here is that I can lean on my existing abstractions (e.g. Bitboard, Square, Direction) which I was already using in the engine. In order to use those abstractions in `build.rs`, I would have to split out those base data structures into a separate crate. I found empirically that splitting out code into a separate crate resulted in an observable Elo reduction (though this was about a year ago, so I forget how much), even with `lto=true`.

Re: Blowing up my compile times for dubious benefits

#27

Post by claytonwramsey »

the8472 wrote: post #16

I wonder whether using `const` over `static` was intentional here. The first gets instantiated at each use site while the latter exists (approximately) once in the binary.

It is! I tried using `static` as a test, and benchmarked the engines against each other.

The final result was that a `const` lookup table yielded +19 Elo over dynamic magic generation, while a `static` one yielded only +10 in a tournament between all three. Elo is non-linear and dependent on the set of competitors, so that's why it has no relation to the +6.6 from the end of my post.

My suspicion is that moving to `static` removes the ability to optimize against the magic table when the query is known at compile time, since I often use magic lookups from fixed squares and occupancies in places other than move generation.

I also found that it yielded no change in compile time or binary size, so it was basically all disadvantages to use `static`.

Re: Blowing up my compile times for dubious benefits

#28

Post by carltg »

Wow, this is a really cool project. Just one thing that I was curious about... At the end there was talk about elo rating and their uncertainties, but I wasn't sure how those were computed and if those were determined to be statistically significant. The dubious benefits of the compile times seem independent from an ELO rating and so I think a statistical test to ensure the significance of the results would be good to further drive the point home.

Apart from the ELO claim, the runtime speedup is sure beneficial at the very least! Cheers to the author

Post reply on HN