Introduction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Presenter: restart kernel and clear output!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Package development: improving engineering quality & latency\n",
    "\n",
    "Tim Holy\n",
    "\n",
    "Shuhei Kadowaki\n",
    "\n",
    "JuliaCon 2021"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Part 1: background (a tutorial on Julia's inner workings)\n",
    "\n",
    "In the first ~25min we'll introduce/review core features of Julia's design:\n",
    "\n",
    "- methods, types, & dispatch\n",
    "- specialization and type inference\n",
    "- runtime vs compiletime dispatch\n",
    "- MethodInstances\n",
    "- invalidation, backedges, & recompilation\n",
    "- precompilation\n",
    "\n",
    "Knowing something about these points is genuinely useful, but you do not have to master all to start improving packages.\n",
    "\n",
    "We'll also introduce the [MethodAnalysis](https://github.com/timholy/MethodAnalysis.jl) package, which allows you to see a lot of this directly."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Methods, types, & dispatch\n",
    "\n",
    "```julia\n",
    "myround(x::Integer) = x\n",
    "myround(x::AbstractFloat) = round(x)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Key points:\n",
    "\n",
    "- each definition is a separate method (use `methods(myround)` to see them all)\n",
    "- methods differ in their type signatures and implementations (*implementation specialization*)\n",
    "- Julia dispatches to the \"most specific\" matching method"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Compiler specialization and type inference\n",
    "\n",
    "Many methods are written with abstract signatures:\n",
    "\n",
    "```julia\n",
    "myround(x::AbstractFloat) = round(x)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The actual bit-level implementation differs for `Float32` and `Float64`: Julia *must* generate different code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Consequently, Julia also (automatically) performs *compiler specialization* whenever the method is invoked with a new concrete type:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "```julia\n",
    "myround(x::Float32)    # a `MethodInstance`, not a `Method`\n",
    "myround(x::Float64)    # another `MethodInstance` generated from the same `Method`\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "To support this need without requiring programmers to declare the type of each internal variable, Julia performs *type inference*. Effectively, Julia turns this:\n",
    "\n",
    "```julia\n",
    "function mysum(list)\n",
    "    s = zero(eltype(list))\n",
    "    for val in list\n",
    "        s = s + val\n",
    "    end\n",
    "    return s\n",
    "end\n",
    "```\n",
    "\n",
    "into this (when `list` is a `Vector{Float32}`):\n",
    "\n",
    "```julia\n",
    "function mysum(list::Vector{Float32})\n",
    "    s = zero(eltype(list::Vector{Float32})::Type{Float32})::Float32\n",
    "    for val::Float32 in list::Vector{Float32}\n",
    "        s = (s::Float32 + val::Float32)::Float32\n",
    "    end\n",
    "    return s::Float32\n",
    "end\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Julia calculates the types of all the intermediates from the types of the input arguments."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Runtime vs compiletime dispatch\n",
    "\n",
    "A compiled function is a \"blob\" of native code living in a particular memory location."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Calling a function involves:\n",
    "- preparing the arguments\n",
    "- deciding *which* specific compiled blob to use. This is like looking up someone's phone number in the phone book. Julia literally scans through the method tables."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "This decision can be made during *runtime* (when code is executing) or during *compiletime* (when Julia is compiling the function)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Schematic of a compiletime call in pseudo-Julia:\n",
    "```julia\n",
    "push!(execution_stack, args)\n",
    "@goto compiled_blob_52383\n",
    "```\n",
    "(The blob will retrieve the argument values by [popping the execution stack](https://en.wikipedia.org/wiki/Call_stack).)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Schematic of a runtime call in pseudo-Julia:\n",
    "```julia\n",
    "# scan the method tables and their lists of compiled blobs for a match\n",
    "# if the right blob hasn't been compiled yet, compile it now\n",
    "blob = get_blob_for_argtypes(f, typesof(args))\n",
    "# The rest looks the same as a compiletime call:\n",
    "push!(execution_stack, args)\n",
    "goto(blob)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "An intermediate case is [Union-splitting](https://julialang.org/blog/2018/08/union-splitting/), where Julia can determine that there are only a few possible argument types:\n",
    "```julia\n",
    "argtypes = typesof(args)\n",
    "push!(execution_stack, args)\n",
    "if argtypes === Tuple{Int64,Bool}\n",
    "    @goto compiled_blob_52383\n",
    "else # the only other option is Tuple{Float64,Bool}\n",
    "    @goto compiled_blob_52951\n",
    "end\n",
    "```\n",
    "Note the absence of the need to call `get_blob_for_argtypes`. Union-splitting generalizes compiletime dispatch."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# \"World-splitting\"\n",
    "\n",
    "*Note: this term is not in common use. It is intended to be reminiscent of Union-splitting.*\n",
    "\n",
    "Julia will exploit the \"state of the world\" when evaluating the possibility for compiletime dispatch."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Suppose: \n",
    "- you have an internal variable `x` but Julia can't infer a concrete type for it\n",
    "- Julia's next compilation task is to call `f(x)`\n",
    "- you have one or a few methods with concrete signature (e.g., `f(x::Int)`)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Then Julia will hazard a guess that it will end up calling `f(x::Int)`:\n",
    "```julia\n",
    "push!(execution_stack, args)\n",
    "if typesof(args) === Tuple{Int}\n",
    "    @goto compiled_blob_39412\n",
    "else\n",
    "    # do the call by runtime dispatch\n",
    "    ...\n",
    "end\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Julia tries to resolve as many dispatches as possible at compiletime using type information, otherwise the dispatch is delayed to runtime."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Looking up the proper blob at compiletime takes burden away from runtime, improving runtime performance.\n",
    "\n",
    "Ballpark costs of runtime dispatch (depends on size of `f`'s method tables):\n",
    "- single argument: 15-35ns\n",
    "- two arguments: ~100ns\n",
    "- ...\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# MethodInstances\n",
    "\n",
    "Compilation is *expensive*. You do not want to recompile the same method repeatedly for exactly the same types."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "To eliminate recompilation (within a single Julia session), Julia *caches* the compiled code. These are `Core.MethodInstance`s (type-inferred code, mentioned above) and `Core.CodeInstance`s (native code). You can think of these caches as, e.g., `Dict(signature => methodinstance)`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Julia makes it easy to see methods:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "methods(searchsorted)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Using MethodAnalysis.jl, you can introspect further:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "using MethodAnalysis\n",
    "methodinstances(searchsorted)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "searchsorted(1:8, 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "methodinstances(searchsorted)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Backedges\n",
    "\n",
    "Julia allows you to redefine a method. When this happens, previously-compiled code needs to be modified to call the new blob instead of the old one.\n",
    "\n",
    "To keep track of what needs to be changed, each `MethodInstance` keeps track of all *compiletime* callers. These are *backedges*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "mi = methodinstances(@which issorted([1, 3, 2]))[1]\n",
    "println(mi)\n",
    "direct_backedges(mi)               # also loaded from MethodAnalysis.jl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "all_backedges(mi)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "using AbstractTrees     # MethodAnalysis.jl defines AbstractTree.jl methods for tree representation of backedges\n",
    "print_tree(mi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "It can get complicated quickly!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Invalidation and recompilation\n",
    "\n",
    "If you redefine a `Method`, Julia will iterate through the `MethodInstance`s of the old method *invalidate* them all. It will also invalidate all backedges (direct and indirect).\n",
    "\n",
    "(For the experts: it does this by capping their *world age* at one less than the current age, making them uncallable in the future.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The next time you call one of these methods, it must be recompiled:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "f(x) = x^2\n",
    "t = ntuple(identity, 15)\n",
    "tstart = time(); map(f, t); time() - tstart"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(When you're measuring compile times, `@time` is dangerous because its arguments typically get compiled before the timer starts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "tstart = time(); map(f, t); time() - tstart   # fast on the second call!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "f(x) = x^2            # redefinition\n",
    "tstart = time(); map(f, t); time() - tstart   # slow again"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Invalidation in \"world-splitting\"\n",
    "\n",
    "Recall the case where we called `f` with an unknown type, but we had just `f(x::Int)`. When compiled, Julia did the method lookup at compile time.\n",
    "\n",
    "Now suppose you define a new method `f(x::String)`. Suddenly the world is different, but the old compiled code doesn't acknowledge this."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Outcome: invalidation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Loading new code can invalidate old code. In egregious cases, it can invalidate *its own code for loading the next package* and needs to recompile the core loading machinery."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    " Fixing most such cases was one of several contributions to reducing latency in Julia 1.6."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Precompilation\n",
    "\n",
    "Backedges have a second role: *precompilation*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Compilation is slow, so we cache the results. Why not make them available to the next session too? => cache to disk"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "But most `MethodInstance`s depend on a lot of other `MethodInstance`s, and it would be pretty useless if we only saved the top-level calls. Solution: cache the things you depend on too! "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "When you \"precompile\" a package, Julia stores:\n",
    "- lowered code\n",
    "- type-inferred code\n",
    "for all `Method`s defined in the package, and any needed `MethodInstance` that weren't already available."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Loading cached `MethodInstance`s takes some time. We can't cache every possible `MethodInstance`, so the package developer has to specify which ones should be cached.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "\n",
    "Julia has a `precompile(f, argtypes)` function. But it forces type-inference, and does not directly save anything to disk."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Implication: execution during package build has similar consequences to calling `precompile`, as far as what ends up in the cache."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Main takeaways\n",
    "\n",
    "- method lookup is slow\n",
    "- knowing all types allows Julia to move lookup to compiletime\n",
    "- Julia exploits this by specializing methods for specific argument types (many compiled blobs for a single method)\n",
    "- compilation is slow, so caching is desirable\n",
    "- Julia's dynamism necessitates cache invalidation and recompilation\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Looking ahead\n",
    "\n",
    "Compilation presents an opportunity for detailed introspection and analysis.\n",
    "\n",
    "A recent development are packages that exploit this to analyze \"code quality\" and contributions to latency.\n",
    "\n",
    "The rest of this workshop will teach you how to take advantage of this opportunity."
   ]
  }
 ],
 "metadata": {
  "@webio": {
   "lastCommId": null,
   "lastKernelId": null
  },
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Julia 1.7.0-pre3-ns 1.7.0-beta3",
   "language": "julia",
   "name": "julia-1.7.0-pre3-ns-1.7"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}