Poor performance results in a seamingly simple algorithm (Advent of Code 2023, Day 16). Help please! 🙏

[jasagredo]

I solved Day 16 (link to the problem) in Scryer-Prolog with what I thought was a very straight-forward implementation (link to the code). However processing an input of 110x110 characters results in almost 60 seconds of running time for part 1, people do similar algorithms in orders of milliseconds in other languages.

This discussion is more of a call for guidance. What is going wrong here? Am I not choosing the right data structures, i.e. should I use for example assocs for whenever I want to check membership on seen states? Will that make such a big difference? Is Prolog not suitable for this kind of matrix manipulations? Am I writing faulty predicates that compute too much?

Part 2 even consumes the full 64gbs of RAM of my machine without finishing.

Quoting the Power of Prolog:

Nevertheless, Prolog is sometimes associated with being slow. In our experience, the main reasons for this are:

1. Exponential-time algorithms can be conveniently encoded in Prolog.
2. Beginners sometimes accidentally write Prolog programs that do not even terminate, then call them "slow".

Maybe I'm falling in both categories? So perhaps this ticket can be seen as a call for review and critique on the code I wrote.

If you take some minutes to read through the code, thanks in advance!

[triska]

One thing I noticed in the code you posted is:

matrix_nth0(X-Y, Mat, E) :-
    nth0(Y, Mat, L),
    nth0(X, L, E).

So, access to any element has linear expected time in the size of the matrix. If you instead, using library(assoc), represent the matrix as an AVL tree with keys of the form X-Y, then you reduce this to logarithmic worst-case overhead for accessing any element X-Y in the matrix. That's not the O(1) worst-case access time we get from programming languages with fast array operations as built-ins (such as APL or J), but can improve the running time by many orders of magnitude, if this matrix access is the bottleneck in your use case.

May I suggest that you please post a program that compiles, with a description of what you did to run it, so that others can reproduce the issue? Thank you a lot!

[UWN]

On the other hand, nth0/3 is quite fast. So the break even point from which the logarithmic access time is better might be more remote.

[jasagredo]

Thanks both, I'm going to try to tweak the nth0. I have also been thinking that probably I don't need the other matrix so I might halve the time (by only accessing one of them).

I thought the program did compile, it compiled when I left it yesterday but maybe I committed a slightly different version, will check.

Many thanks to both!

PS: have you considered solving these problems and publishing your solutions? I think a "good optimal version" of these kind of processing problems could help the Prolog community in the long run on understanding what to do in specific cases. I would certainly love to compare my solutions with the solutions of the people that really know prolog 😄

[jasagredo]

Diff of the change: jasagredo/advent-of-prolog-2023@668525e?diff=unified&w=1

By:

• using an assoc for the matrix (in which I consult elements at random positions on each step)
• using an assoc for the list of seen states (in which I check membership quite often)
• deleting the second matrix that was not needed

and despite:

• converting the assoc of seen states to a list
• sorting it to remove duplicates

I was able to lower the execution time of a single input from 60 seconds to 0.7 seconds:

?- time(part1('inputs/16.txt', Sol)).
   % CPU time: 0.781s, 6_233_332 inferences

So it seems the problem was that the complexity of my code was linear in many places where it could be logarithmic.

The file should now be self-contained and should compile just fine. At least it does on my machine (scryer-prolog 0.9.3).

Many thanks to both!

[triska]

Nice to hear, thank you a lot for posting your code and this update! You are doing great work with your solutions, very elegant and general! Please keep up the great work, it is very interesting to see!

[jasagredo]

It is such a compliment to hear that.

I feel like I think too much "imperatively" and most of the stuff I do is done by "intuition" on how something works by reading the scryer docs and prolog source, having read The Power of Prolog (huge thanks for it, btw) and having had a 3 months course on Prolog at university many years ago! 😄

Many times I don't fully realize the implications of what I wrote until I try to run it.

I have many relations that work only one way, or are wrong when backtracking so not everything is elegant there 😁