Dwarlixir

Mistakes were made

The Big Elixir 2019's theme

[Talks that present] new ways of thinking [...] and talk deeply about lessons learned [...].

We want to hear about [...] the very strange.

Who you're listening to

Aldric Giacomoni

@trevoke

Director of Engineering at Stash

Why this talk? 1/2

You got to lose to know

How to win

― Dream On, Aerosmith

Why this talk? 2/2

With every mistake we must surely be learning

Still my guitar gently weeps

― While My Guitar Gently Weeps, The Beatles

Apparently obligatory

Why?!

Why this side project?

Establishing context

A mix of a MUD and Dwarf Fortress

What's a MUD?

What's Dwarf Fortress?

So what we're gonna aim for is…

  • A telnet connection for people
  • A world map
  • With time passing
  • Creatures that can move
  • Creatures that can die
  • Creatures that can reproduce
  • Balancing out the ecosystem

Disclaimer

I am not a game designer.

Nothing here constitutes good advice.

Seriously.

Roadmap

  • [0/6]
    • [ ] algorithm improvement
    • [ ] extreme local state
    • [ ] distributed state
    • [ ] schedulers and the "tick"
    • [ ] flooding processes
    • [ ] linux oom killer

Algorithm improvement

Misconception

A list is like an array

AKA "what's the deal with immutability anyway?"

Story

World: Graph → Edges and nodes

  1. "nodes" are just ids
  2. generate one edge to a random node from each node
  3. collect, breadth-first, edges into islands
  4. create single edges between islands

Key code

def traverse(node, _, visited) when node in visited, do: visited
def traverse(node, edge_list, visited) do
  visited = [node | visited]
  edges_from_node = direct_edges(node, edge_list)
  Enum.flat_map(
    edges_from_node,
    fn({_s, dest}) -> traverse(dest, edge_list, visited) end
  )
end

Impact

Lots of data structures initialized recursively

Lots of data being copied when flattening

VERY SLOW

Fix

def traverse(node, _, visited) when node in visited, do: visited
def traverse(node1, edge_list, visited) do
  visited = [node1 | visited]
  edges_from_node = direct_edges(node1, edge_list)
  Enum.reduce(
    edges_from_node,
    visited,
    fn({_a, b}, acc) -> traverse(b, edge_list, acc) end)
end

Lessons

  1. copying data structures is expensive

Roadmap

  • [1/6]
    • [X] algorithm improvement
    • [ ] extreme local state
    • [ ] distributed state
    • [ ] schedulers and the "tick"
    • [ ] flooding processes
    • [ ] linux oom killer

Extreme local state

Misconception

local state has got to be better than global state

Story

"Actor model?" Moar like extreme object-oriented, amirite?

Synchronous call

A → B

B → A

A → ☺

Impact

Alice asks Bob (and waits)

Bob asks Charlie (and waits)

Charlie asks Alice (and waits)

Dining philosophers

The classic concurrency problem.

Check it out.

Fix

Tell, don't ask.

Lessons

  1. copying data structures is expensive
  2. tell, don't ask

Roadmap

  • [2/6]
    • [X] algorithm improvement
    • [X] extreme local state
    • [ ] distributed state
    • [ ] schedulers and the "tick"
    • [ ] flooding processes
    • [ ] linux oom killer

Distributed state

Misconception

Fewer synchronous calls will reduce the opportunity of deadlocks

Story

Moar local state in moar local places

Spaghetti state

  • Dwarf has location exits, location id
  • locations have dwarf info

Impact

Accidentally multiple sources of truths

Fix

Some state is global

Lessons

  1. copying data structures is expensive
  2. tell, don't ask
  3. prefer a single source of truth

Roadmap

  • [3/6]
    • [X] algorithm improvement
    • [X] extreme local state
    • [X] distributed state
    • [ ] schedulers and the "tick"
    • [ ] flooding processes
    • [ ] linux oom killer

Schedulers and the "tick"

Game of Life

Misconception

There won't be a noticeable impact to sending all my creatures a message at the same time

Story

The tick (not the blue one)

Impact

All schedulers triggered at same time - literally a heartbeat of intense CPU usage on the box

Fix

More or less "any other way"

I opted for "all manage their own ticks"

Never mind how untestable that makes the system

Smarter fix is probably "bounded global ticks" so that some control can be exerted more easily

Lessons

  1. copying data structures is expensive
  2. tell, don't ask
  3. prefer a single source of truth
  4. understand your system's CPU needs

Roadmap

  • [4/6]
    • [X] algorithm improvement
    • [X] extreme local state
    • [X] distributed state
    • [X] schedulers and the "tick"
    • [ ] flooding processes
    • [ ] linux oom killer

flooding processes

Misconception

It's hard to send a single process too many messages

Story

Every action is an event

Dwarlixir is decentralized

Impact

  • The locations crashed
  • The mobs crashed
  • The process that printed stuff to the console crashed

Fix

  1. Cry
  2. Batch messages
  3. Research game design patterns

Lessons

  1. copying data structures is expensive
  2. tell, don't ask
  3. prefer a single source of truth
  4. understand your system's CPU needs
  5. actors are single-threaded

Roadmap

  • [5/6]
    • [X] algorithm improvement
    • [X] extreme local state
    • [X] distributed state
    • [X] schedulers and the "tick"
    • [X] flooding processes
    • [ ] linux oom killer

linux OOM killer

Misconception

My world simulation won't grow unbounded in RAM usage

Story

"Emergent Behavior"

Impact

The operating system does what it needs to do to stay up

Fix

Ecosystem

Lessons

  1. copying data structures is expensive
  2. tell, don't ask
  3. prefer a single source of truth
  4. understand your system's CPU needs
  5. actors are single-threaded
  6. understand your system's RAM needs

Roadmap

  • [6/6]
    • [X] algorithm improvement
    • [X] extreme local state
    • [X] distributed state
    • [X] schedulers and the "tick"
    • [X] flooding processes
    • [X] linux oom killer

BONUS

Yak shaving

It's yaks all the way down

Language Server Protocol

One server

One plugin per text editor

Editors matter

I use emacs

primary plugin: alchemist.el

Existing LSP projects

  • Marlus Saraiva's elixir_sense
  • Jake Becker's elixir-ls

Created an org on Github

https://github.com/elixir-lsp forked the projects, opened issues on original projects to explain why

Created channel on Elixir Slack

elixir-lang.slack.com

#language-server

Recruited folks

  • @jason_axelson
  • @asummers

Eventually the author of elixir_sense joined

Woot!

Community is active

WOOT!

Last open loop

Still haven't established communication with Jake Becker

Yaks

  • Dwarlixir
  • ECStatic
  • alchemist.el
  • elixir-ls
  • an actual community

Resources

Q&A

If I don't know the answer, I'll make up a good one