Profiling a chess engine

[Algorhythm]

I want to investigate the efficiency of the code in various parts of my chess engine to see if there are any glaring performance bottlenecks that can be improved on. E.g. my engine calculates perft at ~20MNps, which is significantly lower than other numbers I see people reporting online, so I wonder how my move generation could be sped up.

In the past I have tried profiling alpha-beta search with a Connect-4 AI but ran into problems because the search is recursive: most of the search function's time is spent executing copies of itself, so it's difficult to get a sense of where things could be optimised using callstack-based profiling methods like flamegraphs, which are normally very useful.

Has anyone found a good method of profiling large, deeply recursive functions like this to see where the program is actually spending its time doing work? I would expect a tool that can collapse the call stack of certain functions would be available but I have had no luck finding something like that so far.

I am developing in Rust on Windows, but would be interested to hear any info people can give!

[ColonelPhantom]

Not sure about Windows, but on GNU/Linux, the

Code: Select all

perf

profiler I believe supports instruction-level profiling, which shows which instructions take the most time in your function.

Also, usually I would hope you use multiple functions. That would allow a profiler to see which of those takes the most time, so you know which sub-step takes the most time. (Although for perft you probably don't have a whole lot, since there's not a lot to do, since it's essentially all movegen and make-unmake).

[JohnWoe]

1. Implement a bench - command
2. gprof

I have a shell script which produces smt like this:
47% -> Evaluation (this is nonsense)
33% -> MoveGen
2.5% -> LazySort
etc ...

Code: Select all

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 46.59     20.40    20.40 102254368     0.00     0.00  mayhem::Evaluate(bool)
 17.21     27.93     7.54 121336797     0.00     0.00  mayhem::AddMovesB(int, unsigned long)
 15.65     34.78     6.85 128064335     0.00     0.00  mayhem::AddMovesW(int, unsigned long)
  3.67     36.39     1.61 12608965     0.00     0.00  mayhem::HashEntry::put_hash_value_2_moves(unsigned long, mayhem::Board*) const
  2.87     37.64     1.26 54117135     0.00     0.00  mayhem::SearchB(int, int, int, int)
  2.83     38.88     1.24 42120322     0.00     0.00  mayhem::SearchW(int, int, int, int)
  2.42     39.94     1.06 35318941     0.00     0.00  mayhem::SortOneMoveOnly(int, int, int)
  0.96     40.36     0.42 44087042     0.00     0.00  mayhem::QSearchW(int, int, int, int)
  0.88     40.75     0.39 322909661     0.00     0.00  mayhem::HandleCastlingRights()
  0.87     41.13     0.38        2     0.19     0.19  mayhem::SetHashtable(int)
  0.82     41.49     0.36 57000898     0.00     0.00  mayhem::QSearchB(int, int, int, int)
  0.48     41.70     0.21 12780889     0.00     0.00  mayhem::MgenRooksPlusQueensW()
  0.48     41.91     0.21        1     0.21     0.21  mayhem::SetNNUE(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&)
  0.41     42.09     0.18  7048929     0.00     0.00  mayhem::MgenW(mayhem::Board*)
  0.40     42.26     0.18 12698124     0.00     0.00  mayhem::MgenRooksPlusQueensB()
  0.38     42.43     0.17 114911364     0.00     0.00  mayhem::EasyDraw(bool)
  0.35     42.58     0.16  7602562     0.00     0.00  mayhem::MgenB(mayhem::Board*)
  0.33     42.73     0.15 12780889     0.00     0.00  mayhem::MgenSetupW()
  0.31     42.86     0.14 12698124     0.00     0.00  mayhem::MgenBishopsPlusQueensB()
  0.27     42.98     0.12 102254317     0.00     0.00  mayhem::FixFRC()
  0.23     43.08     0.10 12698124     0.00     0.00  mayhem::MgenSetupB()
  0.21     43.17     0.09 12780889     0.00     0.00  mayhem::MgenBishopsPlusQueensW()
  0.21     43.26     0.09 12698124     0.00     0.00  mayhem::MgenKingB()
  0.18     43.34     0.08 12698124     0.00     0.00  mayhem::MgenKnightsB()
  0.14     43.40     0.06                             nnue_evaluate
  0.11     43.45     0.05 12656996     0.00     0.00  mayhem::Draw(bool)
  0.10     43.50     0.05   804138     0.00     0.00  mayhem::AddPromotionB(int, int, int)
  0.09     43.54     0.04 12780889     0.00     0.00  mayhem::MgenKnightsW()
  0.09     43.58     0.04 12780889     0.00     0.00  mayhem::MgenKingW()
  0.07     43.61     0.03  1097312     0.00     0.00  mayhem::AddPromotionW(int, int, int)
  0.07     43.64     0.03   294912     0.00     0.00  mayhem::PermutateBb(unsigned long, int)
  0.06     43.66     0.03  8683655     0.00     0.00  mayhem::HashEntry::update(mayhem::MoveType, unsigned long, unsigned char)
  0.05     43.68     0.02    12838     0.00     0.00  mayhem::ChecksCastleB(unsigned long)
  0.03     43.70     0.02   823985     0.00     0.00  mayhem::CloseBonus(int, int)
  0.03     43.71     0.02    76216     0.00     0.00  mayhem::ChecksCastleW(unsigned long)
  0.03     43.73     0.02        1     0.02     0.02  mayhem::Save::Save()
  0.02     43.74     0.01   294912     0.00     0.00  mayhem::MakeSliderMagicMoves(int const*, int, unsigned long)
  0.02     43.75     0.01   168358     0.00     0.00  mayhem::UserStop()
  0.02     43.76     0.01    64792     0.00     0.00  mayhem::HandleCastlingB(int, int, int)
  0.02     43.77     0.01      226     0.00     0.00  mayhem::SortRoot(int)
  0.02     43.78     0.01                             main
  0.01     43.78     0.01       15     0.00     0.00  mayhem::MgenRoot()

[Carbec]

hi

I am also interested by that, but I develop under windows 10.
How do you do it ?

Philippe

[mvanthoor]

hi

I am also interested by that, but I develop under windows 10.
How do you do it ?

Philippe

There is an open source profiler called "Very Sleepy" which can profile Windows programs.