Creation date: 2022-02-16
Hey everyone, welcome back on a kind of ConstraintSolver post. It has been over a year since I wrote the last blog post about it which you can find here. Feel free to go to the very beginning of this series in which I code a constraint solver from more or less nothing in Julia.
In this post I want to touch on some things I have implemented in the last year which aren't too many as well as the general things I have learned while working on this project. It's definitely the biggest code base I work on alone. The Javis project I work on is structured in quite a different way and also several people are working on it. My ConstraintSolver code base provides a good view back into the past two and a half years. It has about 8,500 lines of code, some of it a bit on the math side. In this post I want to take a look back and reflect a bit on that project.
I've started in September of 2019 with the goal of writing a constraint solver from scratch in Julia. Don't really know what I thought: It's a hell of a goal. Well it still is 😉 Though as a software engineer now instead of a master student I unfortunately have less time to dive into those personal projects.
Let me list some things I still do whenever I start a new Julia project here and explain why I do them. In the first post I started with creating a
test/current.jl file which is in my
.gitignore and provides some kind of playground to work with the package. Testing out new functionality in a file that doesn't get public. I revised that approach a bit by having a
test/current folder with several files and sometimes sub folders which have their own Julia environment.
Besides that I of course use the wonderful package PkgTemplates whenever I create a new Julia package. Whether you want to store it on GitHub or GitLab it got you covered with all the configs you need for tests and documentation.
I also try to do test driven development whenever it feels reasonable and probably should do that even more. Test cases are definitely something I've learned a ton about with this project. Can't imagine programming this solver without tests. Realized a lot of times that when I don't have a test case for some function or part of a function there is probably a bug in it. Using Codecov is also very helpful to see those untested lines of code. Sometimes they can also be removed as dead code. The test driven development is especially helpful for thinking about what the inputs and outputs should be and they bring a little break from idea to code. It happened too often that I had an idea and immediately wanted to write it down into some code without thinking too much about other options and whether that approach is actually the best way forward. Writing down the test cases first forces you to think a little more about it. Another strategy is to go out for a walk which is also the best debugger.
One more thing on the tooling side is to use BenchmarkTools and create some benchmark reports for each pull request I make, see the bugs and benchmarks post. Apropos pull requests, I highly recommend to anyone working alone on a project: Do pull requests! It doesn't matter whether someone else looks at them or not but it's good practice, you can run your test cases there and keep track of the ideas, features and bug requests you work on. Additionally reviewing your code yourself there in a structured way is very helpful. Especially if you have longer breaks due to work or other projects you work on and come back to that PR a week, a month or sometimes even a year later.
Another good idea was to get in contact with people who know more about the stuff than I do. This was mainly the case because I blog about it and I met wonderful people along the way who give ideas, test my code or provide other helpful feedback. I would like to mention two of them here: Håkan Kjellerstrand and Mathieu Besançon. Thanks a lot!
That's not the only thing that makes blogging about such a project reasonable though. I caught a lot of bugs and figured out better ways to solve my problems while I read my code and wanted to explain it to you guys. In those moments you realize what you didn't understand yourself and what kind of ugly code you wrote just to get it done.
I think my approach of using multiple dispatch in a similar way of how MOI uses it for this project was a great idea which Mathieu gave me. Basically every constraint can implement some function like
prune and then it gets dispatched on the constraint type.
Let's continue with some things I should improve on in the next years on several projects but I'm already getting better at, hopefully...
I think in the department of documentation there is some progress to be made. These blog posts are great and I check them from time to time when I don't remember anymore why I did what I did. Having that documentation not on the blog but inside the code or at least in the official docs would be more helpful though. For this project I would also love to have kind of a map of how it's structured as it's sometimes hard to have an overview of all the different components.
This project is also a bit doomed as without proper documentation I don't expect anyone else to work on it but I guess it's also not very likely as it's a hobby project and not really made for a reasonable use it mind. Though I would love to use it for something bigger than solving sudokus for fun or some other puzzles like the eternity game.
Another one is that I should write more unit tests and not just end to end tests. Those are harder for me as often the input depends on some objects which are hard to create. Like in this case the overall
ConstraintSolverModel which contains all the information. Often I think it would be a good idea to break up some functions into smaller ones and change the input in such a way that they only get what they need. That makes them easier to unit test later on (or early in test driven development).
One that I feel now quite a bit is that I should probably do some small refactoring from time to time instead of a huge refactoring like this one PR 271 which is too big to get merged soon.
This is the section of things I do sometimes and some are just really fun to do but make life harder in the long run.
The first thing that comes to mind here is premature optimization. For those few of you who actually read most of my constraint solver posts know that I like to reduce the running time as much as I can and sometimes reimplement things that are done by other packages just to make them a little faster for my use case. You can see one of those examples in the maximum cardinality matching post.
I guess as long as it's fun I shouldn't really stop doing it but maybe don't do it too often. At least reimplementing things that are already quite good in other packages only increases the amount of code that is on your shoulders now. Though I think learning about the optimization and profiling along the way is a very valuable skill and sometimes things like a hungarian method post can have a nice impact on the other package. In that case the author of the Hungarian.jl package @gnimuc improved the package a lot after I wrote about it and now (or at least back then after my second post) our algorithms are quite fast now.
I wrote the last constraint solver post about a year ago and there are some smaller and some bigger changes I made since then. Unfortunately I didn't find the time in between to write about them which I guess means I failed at my early goal of documenting all the things I implemented for that solver on this blog.
Last year did my first and also second JuliaCon presentation one of them was about this project. If you haven't seen it please check it out on YouTube.
I rewrote the way I keep track of changes in each variable in PR 260. Then I implemented the xor and xnor constraints and had a hard time working with bridges. One thing that I think was very helpful was an issue by Hakan #235 in which he suggested that it would be nice to have a constraint like
[x[i] + i for i in 1:4] in CS.AllDifferentSet() for which internally new variables and constraints are generated for the vector and then those new variables are used in an all different constraint.
Then one big thing that happened due to Juliacon 2021 was that I heard more about others who work on constraint programming in Julia. I now use ConstraintProgrammingExtensions.jl for some of my constraints to provide a better experience to users who want to work with different solvers in the future and still want to use the same language. This meant that I switched from the above
AllDifferentSet for example to
This year I changed the logging of incumbent, time and others to a separate Julia package namely TableLogger.jl which I'll hopefully use for Bonobo.jl as well as for Juniper.jl in the future. In general I hope to maybe take some parts of this solver and make more general packages out of it like Bonobo which shall be a general branch and bound solver in Julia.
This will make it easier for others to work on some parts and also for me to focus on specifics and provide a greater good to the community as I don't expect anyone to use this solver for some actual hard work. Nevertheless I would love to bring some more constraints to it to have one package that I can use for constraint programming tasks that I have full control over.
That's all I have for this one 😉
Thanks everyone for reading and hope to see you soon. If you don't wanna miss a post please add your email address to the newsletter (end of this site).
Please checkout some other posts if you enjoyed this one. You can see the categories in the navbar on the left.
I think you might enjoy:
Special thanks to my 11 patrons!
Special special thanks to my >4$ patrons. The ones I thought couldn't be found 😄
For a donation of a single dollar per month you get early access to these posts. Your support will increase the time I can spend on working on this blog.
There is also a special tier if you want to get some help for your own project. You can checkout my mentoring post if you're interested in that and feel free to write me an E-mail if you have questions: o.kroeger <at> opensourc.es
I'll keep you updated on Twitter opensourcesblog.