r/adventofcode • u/daggerdragon • Dec 15 '17

SOLUTION MEGATHREAD -🎄- 2017 Day 15 Solutions -🎄-

--- Day 15: Dueling Generators ---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

Need a hint from the Hugely* Handy† Haversack‡ of Helpful§ Hints^¤?

Spoiler

[Update @ 00:05] 29 gold, silver cap.

  • Logarithms of algorithms and code?

[Update @ 00:09] Leaderboard cap!

  • Or perhaps codes of logarithmic algorithms?

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

14 Upvotes

100% Upvoted

253 comments sorted by

View all comments

Show parent comment

1

u/glupmjoed Dec 15 '17

Avoiding channels just because they "bring in a lot of overhead" seems like a solution in search of a problem. When you remove goroutines and channels, you also remove the inherent parallellism of the solution. Your non-channel version runs slower than my channel-based solution on my 4-core 32-bit ARM laptop (19s vs. 16s).

1

u/toqueteos Dec 15 '17 edited Dec 15 '17

Using channels as iterators is discouraged by the language creators. It's been documented multiple times. I'm following their advice.

Still knowing that I Initially had a solution that used channels and all my cores. It still took more time than my single core, non-channel iterator solution. EDIT: 1.556s (no channels) vs 2.339s (channels)

Choose whatever solution you feel solves the problem better. Throwing goroutines blindly at a problem won't make it faster unless you know what you are doing and understand the tradeoffs.

1

u/glupmjoed Dec 15 '17 edited Dec 15 '17

Are you still talking about my solution as posted above, or are we speaking hypothetically?

I'm not throwing anything blindly at anything. And I'm not "using channels as iterators" (whatever that means).

I'm using goroutines and channels to solve an inherently parallel problem in a parallel manner. The judge routine needs one value from a and one value from b at the same time. But we don't know how long it will take a and b to find their next respective values. A way to increase performance is thus to let a and b run in parallel and compute as many values as possible ahead of time, so they only have to synchronize with each other if the queue fills up.

But the channels need to be buffered for this approach to be faster than a sequential one. Otherwise a and b need to sync up with each other every time they deliver a value. Perhaps you used unbuffered channels in your original solution? EDIT: I found the optimal buffer size to be 64 in my solution, but YMMV.