5 ms·

Parallelizing the Naughty Dog Engine Using Fibers [video]

55 points by rgawdzik 12y ago

frik 12y ago
Fibers is a kind of lightweight thread, also known as coroutine. It's available in WinAPI since Win16 days and heavily used in MS Word. It's also heavily used in many AAA games that use Lua 5.1/LuaJIT, known as coroutine. And in the Go language its named Goroutine. http://en.wikipedia.org/wiki/Fiber_(computer_science) http://en.wikipedia.org/wiki/Fiber_(computer_science) , Lua Coroutines http://www.lua.org/pil/9.html http://www.lua.org/pil/9.html , Lua in video games http://en.wikipedia.org/wiki/Category:Lua-scripted_video_games http://en.wikipedia.org/wiki/Category:Lua-scripted_video_gam..., Go Goroutines http://www.golang-book.com/10/index.htm http://www.golang-book.com/10/index.htm Triva: Naughty Dog uses a Lisp/Scheme dialect for their scripting language: http://en.wikipedia.org/wiki/Game_Oriented_Assembly_Lisp http://en.wikipedia.org/wiki/Game_Oriented_Assembly_Lisp, http://www.quora.com/Does-Naughty-Dog-still-use-lisp-for-making-games http://www.quora.com/Does-Naughty-Dog-still-use-lisp-for-mak...
- beering 12y ago
  The different types of lightweight threads and thread-like things can differ quite a bit in their implementation and usage. E.g. some are explicitly cooperative and require the function to Yield() to other coroutines. Others, like goroutines (which are more like threads) automatically yield at certain points (e.g. I/O or function calls). I think generally coroutines imply that the programmer handles more of the logic of when to switch tasks, while lightweight threads (in Go, Haskell, etc.) imply that there's more stuff "behind the scenes" to manage the concurrency for you like real OS threads. You may have lightweight threads that are multiplexed onto multiple OS threads, but you wouldn't have coroutines that are multiplexed onto multiple OS threads because coroutines implies no parallelism.
- jeremiep 12y ago
  Naughty Dog switched to PLT Scheme during the Uncharted series, which is documented here: http://www.slideshare.net/naughty_dog/statebased-scripting-in-uncharted-2-among-thieves http://www.slideshare.net/naughty_dog/statebased-scripting-i...
angersock 12y ago
The talk about the tagged allocators and fibers kinda reminds me of Erlang. :) EDIT: The use of atoms and per-process stacks which are rapidly returned to the operating environment is kinda similar to how this presentation handles the allocation of the data for jobs/"frames".
NathanKP 12y ago
It is interesting to see that the techniques they used were in many cases quite similar to techniques that were in use decades ago by game devs who had to struggle with much worse hardware. For example they discussed how they achieved 60 FPS with a pipeline that essentially works on 3 frames in parallel: 1 frame of logic, the next frame of graphics, and the the next frame in GPU rendering phase. I remember reading a really interesting book by a dev who had worked on RTS games like Total Annihilation, and Age of Empires and this was a technique that he talked at length about as essential to the performance of those games on the hardware of that time. I learned a lot from that book, including how to make efficient path finding, AI, etc. It's nice to see that fundamental techniques like that are still useful to this day.
- Vekz 12y ago
  and that book was?
  - NathanKP 12y ago
    Sorry should have thought to include a link: http://www.amazon.com/Real-Time-Strategy-Programming-Wordware-Developers/dp/1556226446 http://www.amazon.com/Real-Time-Strategy-Programming-Wordwar... Most of the technical stuff about Direct X is obviously hopelessly outdated now, but it was pretty cool stuff back in 2000 or so when teenage me wanted to learn coding by playing around writing games. :P
- orbifold 12y ago
  Triple buffering is also advantageous to minimize graphics driver overhead, one part is updated by multiple cpu tasks, one is transferred to the gpu, one is used to render.
dragonfax 12y ago
I've been working with golang for too long. Everytime I watch stuff like this it just looks like they're re-inventing goroutines, channels, and the go scheduler.
- throwawayspeccy 12y ago
  Programmers were using cooperative threading for decades before Go made the concept popular with the web crowd.
nimish 12y ago
Very similar to how GHC parallelizes work items/sparks/threads onto native threads.

55 points by rgawdzik 12y ago

frik 12y ago

Fibers is a kind of lightweight thread, also known as coroutine. It's available in WinAPI since Win16 days and heavily used in MS Word. It's also heavily used in many AAA games that use Lua 5.1/LuaJIT, known as coroutine. And in the Go language its named Goroutine. http://en.wikipedia.org/wiki/Fiber_(computer_science) http://en.wikipedia.org/wiki/Fiber_(computer_science) , Lua Coroutines http://www.lua.org/pil/9.html http://www.lua.org/pil/9.html , Lua in video games http://en.wikipedia.org/wiki/Category:Lua-scripted_video_games http://en.wikipedia.org/wiki/Category:Lua-scripted_video_gam..., Go Goroutines http://www.golang-book.com/10/index.htm http://www.golang-book.com/10/index.htm Triva: Naughty Dog uses a Lisp/Scheme dialect for their scripting language: http://en.wikipedia.org/wiki/Game_Oriented_Assembly_Lisp http://en.wikipedia.org/wiki/Game_Oriented_Assembly_Lisp, http://www.quora.com/Does-Naughty-Dog-still-use-lisp-for-making-games http://www.quora.com/Does-Naughty-Dog-still-use-lisp-for-mak...

beering 12y ago
The different types of lightweight threads and thread-like things can differ quite a bit in their implementation and usage. E.g. some are explicitly cooperative and require the function to Yield() to other coroutines. Others, like goroutines (which are more like threads) automatically yield at certain points (e.g. I/O or function calls). I think generally coroutines imply that the programmer handles more of the logic of when to switch tasks, while lightweight threads (in Go, Haskell, etc.) imply that there's more stuff "behind the scenes" to manage the concurrency for you like real OS threads. You may have lightweight threads that are multiplexed onto multiple OS threads, but you wouldn't have coroutines that are multiplexed onto multiple OS threads because coroutines implies no parallelism.
jeremiep 12y ago
Naughty Dog switched to PLT Scheme during the Uncharted series, which is documented here: http://www.slideshare.net/naughty_dog/statebased-scripting-in-uncharted-2-among-thieves http://www.slideshare.net/naughty_dog/statebased-scripting-i...

angersock 12y ago

The talk about the tagged allocators and fibers kinda reminds me of Erlang. :) EDIT: The use of atoms and per-process stacks which are rapidly returned to the operating environment is kinda similar to how this presentation handles the allocation of the data for jobs/"frames".

NathanKP 12y ago

It is interesting to see that the techniques they used were in many cases quite similar to techniques that were in use decades ago by game devs who had to struggle with much worse hardware. For example they discussed how they achieved 60 FPS with a pipeline that essentially works on 3 frames in parallel: 1 frame of logic, the next frame of graphics, and the the next frame in GPU rendering phase. I remember reading a really interesting book by a dev who had worked on RTS games like Total Annihilation, and Age of Empires and this was a technique that he talked at length about as essential to the performance of those games on the hardware of that time. I learned a lot from that book, including how to make efficient path finding, AI, etc. It's nice to see that fundamental techniques like that are still useful to this day.

Vekz 12y ago
and that book was?
- NathanKP 12y ago
  Sorry should have thought to include a link: http://www.amazon.com/Real-Time-Strategy-Programming-Wordware-Developers/dp/1556226446 http://www.amazon.com/Real-Time-Strategy-Programming-Wordwar... Most of the technical stuff about Direct X is obviously hopelessly outdated now, but it was pretty cool stuff back in 2000 or so when teenage me wanted to learn coding by playing around writing games. :P
orbifold 12y ago
Triple buffering is also advantageous to minimize graphics driver overhead, one part is updated by multiple cpu tasks, one is transferred to the gpu, one is used to render.

dragonfax 12y ago

I've been working with golang for too long. Everytime I watch stuff like this it just looks like they're re-inventing goroutines, channels, and the go scheduler.

throwawayspeccy 12y ago
Programmers were using cooperative threading for decades before Go made the concept popular with the web crowd.

nimish 12y ago

Very similar to how GHC parallelizes work items/sparks/threads onto native threads.