This is kind of part 13 of the series about: How to build a Constraint Programming solver?
But it is also interesting for you if you don’t care about constraint programming.
It’s just about: How to make your code faster.

Anyway these are the other posts so far in the ongoing series:

• Part One: Setup and backtracking
• Part Two: Pruning
• Part Three: Pruning+Benchmarking
• Part Four: Alldifferent constraint
• Part Five: Better data structure
• Part Six: Sum constraint first part
• Part Seven: Sum constraint speed-up
• Part Eight: UI Refactoring
• Part Nine: Recap video
• Part Ten: First part of graph coloring
• Part Eleven: MIP graph coloring and optimization
• Part Twelve: Documentation and latest benchmarking

In the last post the benchmark looked good for classic sudokus but not so much for killer sudokus and okayish for graph coloring I would say. As always one can try to improve the performance by rethinking the code but today I mostly want to share how one can check which parts of the code are slow and maybe improve on that i.e by reducing the memory consumption.

First step in improving the performance is always to know what is slow at the moment. We don’t want to take hours in improving one line of code which is only responsible for 1% of the code run time.

An important step is to reduce the memory used.

Memory usage

Let’s find out how much memory we use in the the normal sudoku case at first because we call less functions there:

> julia
julia> using Revise
julia> include("benchmark/sudoku/cs.jl")
julia> main()
julia> @time main(;benchmark=true)

quite a normal setup.
The first main() call is for compiling and checking that we solve every sudoku. The @time macro gives us the time but also the memory usage.

1.009810 seconds (3.69 M allocations: 478.797 MiB, 18.51% gc time)

Attention: This includes all kind of timing not just the solve and is run on my Laptop so don’t compare that to the benchmark results from last time.

We use ~500MiB of memory for solving 95 sudokus. Aha and now?
Yeah that doesn’t give us much detail. Therefore we make memory measurements per line now. Close the current session first.

> julia --track-allocation=user
julia> include("benchmark/sudoku/cs.jl")
julia> main(;benchmark=true)

Close the session.

In the file explorer of your IDE you can now see a couple of *.mem files.
I suppose the most memory is used in the constraint all_different.jl

i.e at the bottom of the file you see:

           - function all_different(com::CoM, constraint::Constraint, value::Int, index::Int)
 12140913     indices = filter(i->i!=index, constraint.indices)
  7885120     return !any(v->issetto(v,value), com.search_space[indices])
           - end

7885120 means that ~7.5MiB are used in that line. (This is a cumulative measurement).

The function itself checks whether we can set value at index or whether that isn’t possible (violates the constraint).

We do a filtering step first here which is creates a new array in the first line and for the second line we again create an array and fill it with true or false and then iterate over it to check…