Ayaz Hafiz (Oct 03 2022 at 22:23): Ayaz Hafiz (Oct 03 2022 at 22:23):Day 5, part 1 and 2: https://github.com/ayazhafiz/roc-advent-of-code/blob/main/2021/day5.roc
Ayaz Hafiz (Oct 03 2022 at 22:25):I feel like this problem hit the limit of what the associativity-list implementation of Dict in the standard library can do. I used @Brendan Hansknecht 's implementation here instead. I know there are more efficient ways to solve this problem, but this is probably a sign we should implement Hash and a faster Dict implementation :sweat_smile:
Brendan Hansknecht (Oct 03 2022 at 22:28):I probably have a similar implementation, but I used our list based set in a way that it still worked for the problem....though it definitely took a bit on part 2: https://github.com/bhansconnect/roc-aoc-2021/tree/trunk/day5
Brendan Hansknecht (Oct 03 2022 at 22:28):Super inefficient, but I really like the solution after parsing: https://github.com/bhansconnect/roc-aoc-2021/blob/trunk/day5/part2.roc#L96
Ayaz Hafiz (Oct 03 2022 at 22:29):otherwise, wow, Roc makes parsing into ad-hoc representations so painless. Only define the type annotations you want, compose things easily without ceremony - the startup ergonomics are at least as nice as they are in Haskell, and definitely feel better in most cases
Brendan Hansknecht (Oct 03 2022 at 22:29):I definitely have to learn your parser stuff at some point. Until then...the world of Str.split and hacks continues.
Ayaz Hafiz (Oct 03 2022 at 22:31):Set is smarter, I used Dict which ends up touching a lot more probably
Brendan Hansknecht (Oct 03 2022 at 22:31):Ah, that's definitely true.
Ayaz Hafiz (Oct 03 2022 at 22:34):hopefully your U64FlatHashDict can carry us, as long as we need it, until we implement one for the stdlib
Brendan Hansknecht (Oct 03 2022 at 22:37):If you help me add Hash, I should be able to upgrade the standard library dict and set. Though we do want to change a few things about my version to avoid ordering problems (should be done before merging) and hash flooding attacks (can be done after merging).
Brendan Hansknecht (Oct 03 2022 at 22:37):I really just don't know much about abilities, but once I see a dummy implementation and just need to fill in the bodies, I should be good.
Ayaz Hafiz (Oct 03 2022 at 22:47):opened #ideas > Hash ability to discuss. Happy to pair on the ability implementation once we get the base API sorted out, now that we have Encode/Decode in place you'll see that it's relatively straightforward
Shritesh Bhattarai (Oct 04 2022 at 04:34):My day 5 part 1 is an abomination: https://github.com/shritesh/advent/blob/main/2021/5.roc
I couldn't figure out how to use the aforementioned parser in the stdlib (including two packages crashes the compiler?) so I hand rolled my own state-machine based one. Also, I couldn't figure out an ergonomic way to essentially do List.update so I've got a hackjob of List.replace, List.set and custom tag types to make it work, which is probably why the code runs dead slow.
Brendan Hansknecht (Oct 04 2022 at 05:11):The issue is likely not truely your fault. Roc has some shape edges around uniqueness and copying. I am betting that you are copying your 1ish MB list many many times.
Brendan Hansknecht (Oct 04 2022 at 05:20):I am gonna test an try to figure if uniqueness is the issue.
Brendan Hansknecht (Oct 04 2022 at 05:28):Yeah, this is 100% roc uniqueness sharp edge leading to tons of copying.
Brendan Hansknecht (Oct 04 2022 at 05:30):Try changing cover to this:
cover = \{width, height, data}, x, y ->
index = width * x + y
when List.replace data index One is
{ value: None, list } -> { width, height, data: list }
{ value: One, list } -> { width, height, data: List.set list index TwoOrMore }
{ value: TwoOrMore, list } -> { width, height, data: List.set list index TwoOrMore }
The problem is that you were keep a reference to the grid because it was used after the List.replace statement in the when clause. This meant that every call to List.replace had to completely clone the list. This allocated about 1MB for every point in every line.
Shritesh Bhattarai (Oct 04 2022 at 05:35):Yup. Much faster. Thanks
Shritesh Bhattarai (Oct 04 2022 at 06:02):Part 2 is done: https://github.com/shritesh/advent/blob/main/2021/5.roc
List.range is broken in Roc. List.range 1 1 == List.range 1 2 == [1].
@Brendan Hansknecht 's solution helped in figuring that out.
Shritesh Bhattarai (Oct 04 2022 at 15:00):Filed an issue about it: https://github.com/roc-lang/roc/issues/4196
Anton (Oct 04 2022 at 17:19)::+1: thanks @Shritesh Bhattarai :)
Ghislain (Oct 07 2022 at 10:43):Hi, here's my solution for part2 https://github.com/ghigt/advent-of-code/blob/main/roc/day-5/part2.roc
My algorithm is SOO slow, 4min on my M1 :(
99% of it is spent on this function to look for the duplications:
seeDuplicate : List Coord -> Set Coord
seeDuplicate = \list ->
List.walk list { s: Set.empty, d: Set.empty } (\{s, d}, c ->
if Set.contains s c then
{ d: Set.insert d c, s }
else
{ s: Set.insert s c, d }
)
|> .d
Tried several other implementations with only one Set and Tag but it was even worse
Brendan Hansknecht (Oct 07 2022 at 13:49):Currently sets are list based instead of hash set based. So contains and insert both scan the entire list doing comparisons.
Brendan Hansknecht (Oct 07 2022 at 13:50):We just added the Hash ability. Soon, i will port over a Hash based dictionary (and set). That should greatly help here.
Brendan Hansknecht (Oct 07 2022 at 13:57):Also, i think lists currently grow by 1 element instead of 1.5 to 2x. So every time you insert, the list has to be reallocated and all bytes copied.
Brendan Hansknecht (Oct 07 2022 at 13:58):In other words, probably more a Roc maturity problem than a real problem with your code.
Ghislain (Oct 07 2022 at 14:05):Ok, a strategy like in Go which grows the slice capacity by 2x if append needs it
Ghislain (Oct 07 2022 at 14:08):I should look at the implementation of List, I naively thought it was a rust Vec which then grew its capacity with the rust strategy
Brendan Hansknecht (Oct 07 2022 at 14:19):I think we would prefer 1.5x more than 2x. The issue with 2x is that it can never reuse memory. Your new list is always large enough that it can't fit in the sum of all previous memory locations it occupied even if they are continuous. As such, the number at most can be the golden ratio.
Brendan Hansknecht (Oct 07 2022 at 14:19):But yeah, should be a simple addition if you want to try and fix it. (assuming it hasn't already been done)
Brendan Hansknecht (Oct 07 2022 at 14:25):Yeah, looks like this still needs to be done. Might require changes in a few different functions (probably funneling them all through list a single growth function)
Ghislain (Oct 07 2022 at 14:25):oh, I'm a "read-only" source code developer on Roc for now, hope to be able to help in a near future when I will have a better understanding of what happens under the hood! :sweat_smile:
Ghislain (Oct 07 2022 at 14:27):But having a look at all PR/docs since a couple of weeks now, it's a real pleasure to learn!
Brendan Hansknecht (Oct 07 2022 at 14:31):Ah, that's fine.
Brendan Hansknecht (Oct 07 2022 at 14:58):I'll add this and we can see if/how much it helps your example
Brendan Hansknecht (Oct 08 2022 at 00:36):Oh, actually in this case, I think you just needed the --optimize flag. I just ran it on an M1 and it ran in 13s.
Ghislain (Oct 08 2022 at 07:55):What does this flag do?
Anton (Oct 08 2022 at 08:41):I think it requests LLVM to optimize for execution speed.
Richard Feldman (Oct 08 2022 at 08:54):in general it tells the Roc compiler "spend time optimizing this program so that it will run faster (but take longer to build compared to normal)"
Last updated: Jul 06 2025 at 12:14 UTC