GopherCon Europe 2020: Egon Elbre - A Tale of Breadth-First Search

30:31 389 views 100% Published 6 months ago

About the talk:
One of my passions is optimizing different algorithms. It might seem that those fancy fast algorithms you see are a spark of imagination and “just happen”. In practice, the way you get to them is much more incremental. For every good idea, there are at least five that failed.

One fundamental way of optimizing algorithms is:
- Measure
- Make a few hypotheses why those things in the profile are slow
- Formulate few solutions to each of the hypotheses
- Try all promising solutions (and observe for more hypotheses)
- Keep the best solution (if there is one)
- Keep the second-best solution around, just in case
- goto 1

In this talk, we’ll demonstrate and explain the principles. We’ll take a basic “Breadth-First Search” implementation and incrementally make it 2x faster on a single core. Then we’ll take these principles to multi-core and squeeze out further 2x. These improvements are accompanied by failures along the way.

The attendees will end up with a clearer understanding of how algorithms are developed and optimized.

About the speaker:
Egon Elbre (@egonelbre) is a software engineer with over 10 years of experience. He started playing with Go just after the first public announcement and has hung around since then. He loves finding new ways of looking at code such that it would be easier to maintain, understand and, most of all, ensure that it delivers value. He strongly believes that there are explanations that help people learn and be productive faster. When he’s not neck deep in code he’s either drawing or playing the piano.


Link Original video