Stream: roctoberfest

Topic: 2023 day 14

Fabian Schmalzried (Oct 18 2023 at 19:52):

I just did day 14 and my (probably not optimal) solution for part 2 took about a minute to run. With --optimize it was "only" about 20s. So it's probably good to know that there is --optimize.

Anton (Oct 20 2023 at 07:52):

Hi @Fabian Schmalzried,
Can you share your code? If it's some new patholigical performance case I'll make an issue for it

Fabian Schmalzried (Oct 21 2023 at 08:48):

Here it is, but I don't think it's rocs fault.
https://gist.github.com/FabHof/5b2ac84a1df7cb165da43231fb84c616

Anton (Oct 21 2023 at 09:02):

Uhu, yes, I expect that all the non-tail recursive calls cause the slowdown. Thanks for sharing anyway :)

Elias Mulhall (Oct 22 2023 at 23:05):

Here's a different take on day 14, I've actually had this one partially completed for a bit!
https://github.com/mulias/roctoberfest/blob/main/advent_2022/day_14/main.roc

Elias Mulhall (Oct 22 2023 at 23:06):

The output for this one is fun
Screenshot_2023-10-22_19-01-45.png
Screenshot_2023-10-22_19-01-26.png

Luke Boswell (Oct 22 2023 at 23:09):

I love how clean the solution reads in Roc. Thank you for sharing.

Brendan Hansknecht (Oct 22 2023 at 23:31):

that poor addSand function. I wonder if we can write in a different way to help with the nesting.

Elias Mulhall (Oct 23 2023 at 00:26):

Haha. This works, not sure if it's much better?

addSand : Cave, Array2D.Index -> Result Cave [SandFellIntoTheInfiniteAbyss, Blocked]
addSand = \cave, pos ->
    when Array2D.get cave pos is
        Err OutOfBounds -> Err SandFellIntoTheInfiniteAbyss
        Ok Sand | Ok Rock -> Err Blocked
        Ok Air ->
            addSand cave (down pos)
            |> Result.onErr \err ->
                if err == Blocked then
                    addSand cave (downLeft pos)
                else
                    Err err
            |> Result.onErr \err ->
                if err == Blocked then
                    addSand cave (downRight pos)
                else
                    Err err
            |> Result.onErr \err ->
                if err == Blocked then
                    Ok (Array2D.set cave pos Sand)
                else
                    Err err

Elias Mulhall (Oct 23 2023 at 00:47):

This isn't too bad

addSand : Cave, Array2D.Index -> Result Cave [SandFellIntoTheInfiniteAbyss, Blocked]
addSand = \cave, pos ->
    when Array2D.get cave pos is
        Err OutOfBounds -> Err SandFellIntoTheInfiniteAbyss
        Ok Sand | Ok Rock -> Err Blocked
        Ok Air ->
            addSand cave (down pos)
            |> elseIfBlocked \_ -> addSand cave (downLeft pos)
            |> elseIfBlocked \_ -> addSand cave (downRight pos)
            |> elseIfBlocked \_ -> Ok (Array2D.set cave pos Sand)

elseIfBlocked = \result, thunk ->
    when result is
        Err Blocked -> thunk {}
        _ -> result

Brendan Hansknecht (Oct 23 2023 at 01:28):

Oh wow :astonished:...yeah, much nicer

Luke Boswell (Oct 23 2023 at 01:33):

I like how clear this is to follow the logic. I wonder though how performant this is, like would you expect this to be significantly worse than an equivalent imperative implementation or roughly equivalent when using --optimize? This is probably not straightforward to verify realistically for performance, but if this kind of thing is as good as or better, then that is a very positive signal for Roc. It looks really easy to test and verify correctness, and is easy to read and follow the logic... almost as easy as reading the text of the problem description.

Brendan Hansknecht (Oct 23 2023 at 01:42):

I think llvm will inline elseIfBlocked and all of the thunks. Once those are inlined, I think it is tail recursive, so perf should be fine

Elias Mulhall (Oct 23 2023 at 01:46):

It runs in less than a second on my machine. --optimize maybe makes it very slightly snappier. We're manipulating a list of 68,000 elements so there's some work going on, but this still feels like a toy problem to me.

Having O(1) array element access is definitely nice, that's one of the things that kills me when I do AoC in list-based functional languages.

Brendan Hansknecht (Oct 23 2023 at 02:19):

This is what I see with hyperfine. --optimize does a lot.

Just run:

Benchmark 1: ./day14-dev
  Time (mean ± σ):     671.3 ms ±  11.5 ms    [User: 664.1 ms, System: 3.7 ms]
  Range (min … max):   664.6 ms … 716.0 ms    20 runs

Benchmark 2: ./day14-opt
  Time (mean ± σ):     137.7 ms ±   1.2 ms    [User: 135.9 ms, System: 1.2 ms]
  Range (min … max):   135.8 ms … 139.3 ms    20 runs

Summary
  './day14-opt' ran
    4.88 ± 0.09 times faster than './day14-dev'

Brendan Hansknecht (Oct 23 2023 at 02:20):

Of course from an end user perspective, the compile time is long enough that dev is probably faster if you are building and running.

Elias Mulhall (Oct 23 2023 at 02:25):

very cool!

Last updated: Jul 06 2025 at 12:14 UTC