Fabian Schmalzried (Dec 23 2023 at 21:04): Fabian Schmalzried (Dec 23 2023 at 21:04):After beeing sick in bed for a few days, I had some time to continue. Day 17 was something that was not so nice to do in Roc, but at least here is my part 1 : https://github.com/FabHof/aoc-2023/blob/main/day17/main.roc
It took 10 minutes to run on my laptop (with --optimize). For part 2 I think I implemented something that should maybe work, but I get a memory access violation after about 1 minute.
Oskar Hahn (Dec 26 2023 at 13:33):I had a solution for Part 1 that run in around 7 Seconds, but I think it only worked by accident: https://github.com/ostcar/aoc2023/blob/37f02c7e4f4b49d5ce3630af29c7ad4e7159183a/days/day17.roc
So I rewrote it for Part 2. It works, but it is very slow. For part 1, a build with --optimize takes more then a minute. I forgot to write down the number for Part 2, but it was around 10 Minutes.
https://github.com/ostcar/aoc2023/blob/main/days/day17.roc
I don't understand, why it is so slow. I tried different things, but nothing helped.
Could someone explain to me, what I am doing wrong?
Brendan Hansknecht (Dec 26 2023 at 14:27):I think you are just hitting the recursive refcounting perf issue
Brendan Hansknecht (Dec 26 2023 at 14:27):So, not really doing anything wrong. Just a roc issue that still needs fixing.
Brendan Hansknecht (Dec 26 2023 at 14:30):Hmm...might be wrong...hard to follow all the types without annotations
Brendan Hansknecht (Dec 26 2023 at 14:47):Oh, nvm. The issue here is the seen list. List.contains is linearly scanning it and that is a huge part of the execution time. Using a Set instead, it still isn't super fast, but part2 takes about a minute for me.
Brendan Hansknecht (Dec 26 2023 at 14:53):After that, List.dropAt queue minIndex uses about half of the exection time with the List.walkWithIndex in getShortest using the other half.
Brendan Hansknecht (Dec 26 2023 at 14:54):So some sort of priority queue or heap there that makes it trivial to get the lowest element would be a huge gain probably.
Brendan Hansknecht (Dec 26 2023 at 14:54):especially if it is a heap that stores the lowest element as the last index in the list to make it free to remove
Brendan Hansknecht (Dec 26 2023 at 14:57):So I have tested this twice and it makes no sense to me. After switching this app to use a Set for tracking seen elements. I ran it to measure the full execution time uninstrumented. Both times results looked approximately like this for execution time:
$ /tmp/aoc2023/days/day17
Part1 in 6.339s:
722
Part2 in 54.736s:
894
I then measure it with perf (which pauses and dumps the stack of the binary many times). Somehow running with perf is faster than running without perf by about 2x:
$ perf record -F97 --call-graph dwarf -- /tmp/aoc2023/days/day17
Part1 in 3.607s:
722
Part2 in 30.281s:
894
[ perf record: Woken up 106 times to write data ]
[ perf record: Captured and wrote 26.434 MB perf.data (3276 samples) ]
what's surprising about that? perf should give better perf, it's right there in the name! :stuck_out_tongue:
Richard Feldman (Dec 26 2023 at 15:10):...but yeah I have no idea why that could be happening :sweat_smile:
Brendan Hansknecht (Dec 26 2023 at 15:21):Yeah, it is super strange. Even stranger, time perf record -F97 --call-graph dwarf -- /tmp/aoc2023/days/day17 slows back down, but date && perf record -F97 --call-graph dwarf -- /tmp/aoc2023/days/day17 && date still runs at the fast speed.
Brendan Hansknecht (Dec 26 2023 at 15:21):So the fast speed can be measured with external programs
Last updated: Jul 06 2025 at 12:14 UTC