Cthulhu.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# Cthulhu.jl Workshop\n",
    "\n",
    "Shuhei Kadowaki"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "<h2>Workshop Outline<span class=\"tocSkip\"></span></h2>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#Overview-of-Cthulhu.jl\" data-toc-modified-id=\"Overview-of-Cthulhu.jl-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Overview of Cthulhu.jl</a></span><ul class=\"toc-item\"><li><span><a href=\"#Walk-through-static-call-graph\" data-toc-modified-id=\"Walk-through-static-call-graph-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Walk-through static call graph</a></span></li><li><span><a href=\"#Walk-through-program-representations\" data-toc-modified-id=\"Walk-through-program-representations-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Walk-through program representations</a></span></li></ul></li><li><span><a href=\"#Get-familiar-with-Julia-compiler-with-Cthulhu\" data-toc-modified-id=\"Get-familiar-with-Julia-compiler-with-Cthulhu-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Get familiar with Julia compiler with Cthulhu</a></span><ul class=\"toc-item\"><li><span><a href=\"#Dynamic/static-dispatch\" data-toc-modified-id=\"Dynamic/static-dispatch-2.1\"><span class=\"toc-item-num\">2.1&nbsp;&nbsp;</span>Dynamic/static dispatch</a></span></li><li><span><a href=\"#Multiple-matching-methods-and-union-split\" data-toc-modified-id=\"Multiple-matching-methods-and-union-split-2.2\"><span class=\"toc-item-num\">2.2&nbsp;&nbsp;</span>Multiple matching methods and union-split</a></span></li><li><span><a href=\"#Multithreading-code\" data-toc-modified-id=\"Multithreading-code-2.3\"><span class=\"toc-item-num\">2.3&nbsp;&nbsp;</span>Multithreading code</a></span></li></ul></li></ul></div>"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "source": [
    "using BenchmarkTools, Cthulhu, JETTest"
   ],
   "outputs": [],
   "metadata": {
    "scrolled": false
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Overview of Cthulhu.jl"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Walk-through static call graph\n",
    "\n",
    "Cthulhu is a lens into a static call graph, and it's very similar to `code_typed`. \n",
    "They _never_ execute an input program as opposed to ordinal debuggers that interact with runtime.\n",
    "\n",
    "To illustrate how Cthulhu is different from `code_typed`, consider the following example"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "source": [
    "function inner(T, somes)\n",
    "    r::T = zero(T)\n",
    "    for s in somes\n",
    "        if isa(s.value, T)\n",
    "            r += s.value\n",
    "        end\n",
    "    end\n",
    "    return r\n",
    "end\n",
    "outer(somes) = inner(Int, somes)\n",
    "\n",
    "somes = [Some(rand(Bool) ? nothing : i) for i in 1:100000]\n",
    "@benchmark outer($somes)"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "BenchmarkTools.Trial: 458 samples with 1 evaluation.\n",
       " Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m):  \u001b[39m\u001b[36m\u001b[1m 9.241 ms\u001b[22m\u001b[39m … \u001b[35m 15.169 ms\u001b[39m  \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 0.00%\n",
       " Time  \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m):     \u001b[39m\u001b[34m\u001b[1m10.915 ms               \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m):    \u001b[39m0.00%\n",
       " Time  \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m):   \u001b[39m\u001b[32m\u001b[1m10.907 ms\u001b[22m\u001b[39m ± \u001b[32m885.843 μs\u001b[39m  \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m):  \u001b[39m0.43% ± 1.70%\n",
       "\n",
       "  \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▆\u001b[39m▅\u001b[39m█\u001b[34m▆\u001b[39m\u001b[39m▄\u001b[39m▁\u001b[39m▄\u001b[39m▃\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▂\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \n",
       "  \u001b[39m▄\u001b[39m▄\u001b[39m▄\u001b[39m▄\u001b[39m▇\u001b[39m█\u001b[39m▆\u001b[39m█\u001b[39m▆\u001b[39m▆\u001b[39m▇\u001b[39m▆\u001b[39m▆\u001b[39m█\u001b[39m▄\u001b[39m▅\u001b[39m▄\u001b[39m▄\u001b[39m▃\u001b[39m▅\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[34m█\u001b[39m\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m▇\u001b[39m▆\u001b[39m▆\u001b[39m█\u001b[39m▆\u001b[39m▆\u001b[39m█\u001b[39m▆\u001b[39m▆\u001b[39m▄\u001b[39m█\u001b[39m▄\u001b[39m▄\u001b[39m▃\u001b[39m▄\u001b[39m▄\u001b[39m▂\u001b[39m▃\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▃\u001b[39m▃\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▂\u001b[39m \u001b[39m▄\n",
       "  9.24 ms\u001b[90m         Histogram: frequency by time\u001b[39m         13.4 ms \u001b[0m\u001b[1m<\u001b[22m\n",
       "\n",
       " Memory estimate\u001b[90m: \u001b[39m\u001b[33m2.28 MiB\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m149332\u001b[39m."
      ]
     },
     "metadata": {},
     "execution_count": 2
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Suppose we want to improve the performance of `outer`. \n",
    "\n",
    "As [the performance tips suggest](https://docs.julialang.org/en/v1/manual/performance-tips/#tools), we first take a look at `@code_warntype`:"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "source": [
    "@code_warntype outer(somes)"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "MethodInstance for outer(::\u001b[0mVector{Some})\n",
      "  from outer(somes) in Main at In[2]:10\n",
      "Arguments\n",
      "  #self#\u001b[36m::Core.Const(outer)\u001b[39m\n",
      "  somes\u001b[36m::Vector{Some}\u001b[39m\n",
      "Body\u001b[36m::Int64\u001b[39m\n",
      "\u001b[90m1 ─\u001b[39m %1 = Main.inner(Main.Int, somes)\u001b[36m::Int64\u001b[39m\n",
      "\u001b[90m└──\u001b[39m      return %1\n",
      "\n"
     ]
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Looks all good ?\n",
    "\n",
    "Now we give a try to [JETTest.jl](https://github.com/aviatesk/JETTest.jl):"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "source": [
    "@report_dispatch outer(somes)"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "\u001b[7m═════ 2 possible errors found ═════\u001b[27m\n",
      "\u001b[35m┌ @ In[2]:10 \u001b[39m\u001b[0mMain.inner\u001b[0m(\u001b[0mMain.Int\u001b[0m, \u001b[0msomes\u001b[0m)\n",
      "\u001b[35m│\u001b[39m\u001b[91m┌ @ In[2]:5 \u001b[39m\u001b[0mMain.+\u001b[0m(\u001b[0m%22\u001b[0m, \u001b[0m%26\u001b[0m)\n",
      "\u001b[35m│\u001b[39m\u001b[91m│ runtime dispatch detected: \u001b[39m\u001b[0m\u001b[1mMain.+\u001b[22m\u001b[0m\u001b[1m(\u001b[22m\u001b[0m\u001b[1m%22\u001b[22m\u001b[96m\u001b[1m::Int64\u001b[22m\u001b[39m\u001b[0m\u001b[1m, \u001b[22m\u001b[0m\u001b[1m%26\u001b[22m\u001b[96m\u001b[1m::Any\u001b[22m\u001b[39m\u001b[0m\u001b[1m)\u001b[22m\n",
      "\u001b[35m│\u001b[39m\u001b[91m└───────────\u001b[39m\n",
      "\u001b[35m│\u001b[39m\u001b[91m┌ @ In[2]:5 \u001b[39m\u001b[0mBase.convert\u001b[0m(\u001b[0mT\u001b[0m, \u001b[0m%27\u001b[0m)\n",
      "\u001b[35m│\u001b[39m\u001b[91m│ runtime dispatch detected: \u001b[39m\u001b[0m\u001b[1mBase.convert\u001b[22m\u001b[0m\u001b[1m(\u001b[22m\u001b[0m\u001b[1mT\u001b[22m\u001b[96m\u001b[1m::Type{Int64}\u001b[22m\u001b[39m\u001b[0m\u001b[1m, \u001b[22m\u001b[0m\u001b[1m%27\u001b[22m\u001b[96m\u001b[1m::Any\u001b[22m\u001b[39m\u001b[0m\u001b[1m)\u001b[22m\n",
      "\u001b[35m│\u001b[39m\u001b[91m└───────────\u001b[39m\n"
     ]
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "(Int64, 2)"
      ]
     },
     "metadata": {},
     "execution_count": 4
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "There _are_ type-instabilities ! What's wrong with `code_warntype` ?\n",
    "\n",
    "Now let's use Cthulhu and see what really happened:\n",
    "```julia\n",
    "@descend_code_warntype optimize=false outer(somes)\n",
    "```\n",
    "\n",
    "_Go to terminal_"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "source": [
    "function inner(T, somes)\n",
    "    r::T = zero(T)\n",
    "    for s in somes\n",
    "        val = s.value\n",
    "        if isa(val, T)\n",
    "            r += val::T\n",
    "        end\n",
    "    end\n",
    "    return r\n",
    "end\n",
    "\n",
    "@benchmark outer($somes) # 3x faster !"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "BenchmarkTools.Trial: 1844 samples with 1 evaluation.\n",
       " Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m):  \u001b[39m\u001b[36m\u001b[1m2.158 ms\u001b[22m\u001b[39m … \u001b[35m  6.349 ms\u001b[39m  \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 52.38%\n",
       " Time  \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m):     \u001b[39m\u001b[34m\u001b[1m2.593 ms               \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m):    \u001b[39m0.00%\n",
       " Time  \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m):   \u001b[39m\u001b[32m\u001b[1m2.690 ms\u001b[22m\u001b[39m ± \u001b[32m406.191 μs\u001b[39m  \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m):  \u001b[39m1.21% ±  5.36%\n",
       "\n",
       "  \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▅\u001b[39m█\u001b[39m█\u001b[39m▆\u001b[39m▆\u001b[39m█\u001b[34m▇\u001b[39m\u001b[39m▅\u001b[39m▄\u001b[32m▁\u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \n",
       "  \u001b[39m▃\u001b[39m▂\u001b[39m▂\u001b[39m▄\u001b[39m▆\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[34m█\u001b[39m\u001b[39m█\u001b[39m█\u001b[32m█\u001b[39m\u001b[39m█\u001b[39m█\u001b[39m▇\u001b[39m▇\u001b[39m▆\u001b[39m▅\u001b[39m▅\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▃\u001b[39m▂\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m \u001b[39m▄\n",
       "  2.16 ms\u001b[90m         Histogram: frequency by time\u001b[39m        4.45 ms \u001b[0m\u001b[1m<\u001b[22m\n",
       "\n",
       " Memory estimate\u001b[90m: \u001b[39m\u001b[33m776.64 KiB\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m49705\u001b[39m."
      ]
     },
     "metadata": {},
     "execution_count": 5
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Yay, now it runs 3x faster !\n",
    "\n",
    "(For expert: <https://github.com/JuliaLang/julia/pull/41199> will eliminate the need for this kind of variable extraction in the future :))"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Recap:\n",
    "- `code_typed` and its family only presents the final output of inference and optimization\n",
    "- with Cthulhu, we can walk-through a static call graph by descending into each intermediate state\n",
    "- Cthulhu doesn't suggest anything, _it's up to you how to interpret them_\n",
    "  - in this view, we can think of JET as, an automated and opinionated version of a workflow using Cthulhu"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Walk-through program representations\n",
    "\n",
    "Julia's compilation process consists of:\n",
    "1. _lowering_: AST -> lowered code\n",
    "2. _type inference_: lowered code -> unoptimized typed code\n",
    "3. _Julia-level optimization_: unoptimized typed code -> optimized typed code\n",
    "4. _LLVM optimization_: optimized typed code -> LLVM IR\n",
    "5. _LLVM code generation_: LLVM IR -> native code\n",
    "\n",
    "So there are various different program representations:\n",
    "- AST (`Core.Expr`)\n",
    "- lowered code (`Core.CodeInfo`)\n",
    "- unoptimized typed code (`Core.CodeInfo`)\n",
    "- optimized typed code (`Core.CodeInfo`, `Core.Compiler.IRCode`)\n",
    "- LLVM IR\n",
    "- native code\n",
    "\n",
    "Cthulhu lets us to traverse these forms quite easily (except AST) !\n",
    "- unoptimized typed code: to see how type inference goes\n",
    "- optimized typed code: to see Julia-level optimizations\n",
    "- LLVM IR: to enjoy all the tricks LLVM does for us\n",
    "- native code: if you doubt all the beauty of abstractions"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "As an example, let's take a deeper look into this function call.\n",
    "\n",
    "```julia\n",
    "descend(; optimize=false) do\n",
    "    ary = [1,2,3]\n",
    "    @inbounds ary[1] + ary[3]\n",
    "end\n",
    "```\n",
    "\n",
    "Note that:\n",
    "- inference annotates types for this function call\n",
    "- Julia-level optimization inlines typed function calls\n",
    "- LLVM further gets rid of the array indexing and folds the final output (still it's not smart enough to eliminate the allocation of `ary`)\n",
    "\n",
    "_Go to terminal_"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Get familiar with Julia compiler with Cthulhu\n",
    "\n",
    "We need some knowledge of and familiarity with some concepts of Julia compilation to understand what Cthulhu shows us.\n",
    "\n",
    "Here I'm going to show a selection of most important concepts with examples."
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Dynamic/static dispatch\n",
    "\n",
    "When looking at an optimized code, there are two different representation of function calls: `:invoke` and  `:call`.\n",
    "Here are their meanings:\n",
    "- `:invoke` is a statically-resolved generic function call (i.e. \"static dispatch\")\n",
    "- `:call` is a dynamic generic function call (i.e. \"dynamic dispatch\"), or a builtin function call"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Note that it depends on how type inference goes successfully if Julia compiler can resolve function calls at compiletime or just delays the resolution to runtime.\n",
    "\n",
    "```julia\n",
    "@noinline invokecall(a) = sum(sincos(a))\n",
    "v = 42.0 # type-inference barrier here !\n",
    "\n",
    "# how these `f` calls are resolved\n",
    "descend((Int,)) do a\n",
    "    good = invokecall(a)\n",
    "    bad  = invokecall(v)\n",
    "    return (good, bad)\n",
    "end\n",
    "```\n",
    "\n",
    "_Go to terminal_"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "And now we just understood the idea of how JETTest works – it just hunts for `:call`s appearing in optimized typed code."
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Multiple matching methods and union-split\n",
    "\n",
    "When there are multiple matching methods, Julia's type inference recurses into each method match, so does Cthulhu (caveat: not always, think of e.g. what can happen for `show(::IO, ::Any)`).\n",
    "\n",
    "```julia\n",
    "multiplem(::Int)     = :int\n",
    "multiplem(::Integer) = \"integer\"\n",
    "\n",
    "descend((Integer,); optimize=false) do i\n",
    "    multiplem(i)\n",
    "end\n",
    "```\n",
    "\n",
    "_Go to terminal_"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "Note that the return type was `Union{String,Symbol}`.\n",
    "\n",
    "`Union` is basically \"a enumeration of possible types\".\n",
    "Julia compiler will form `Union` when it can't narrow down the type into one.\n",
    "\n",
    "Julia compiler will \"split\" `Union` type when a call signature includes `Union`, and this often lead to multiple matching methods:\n",
    "```\n",
    "descend((Integer,); optimize=false) do i\n",
    "    r = multiplem(i)\n",
    "    string(r)\n",
    "end\n",
    "```\n",
    "\n",
    "_Go to terminal_"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "More interesting thing happens when looking at optimized code.\n",
    "\n",
    "```julia\n",
    "verytyped(a::Int) = sin_for_int(a)\n",
    "verytyped(a::Float64) = sin_for_general(a)\n",
    "\n",
    "# see unoptimized code, then look at optimized code\n",
    "descend((Any,); optimize=false) do a\n",
    "    verytyped(a)\n",
    "end\n",
    "```\n",
    "_Go to terminal_\n",
    "\n",
    "Julia automatically forms `isa` branches and it _expands_ the union-split, so that the `verytyped` call can be resolved statically.\n",
    "\n",
    "Exercise:\n",
    "```julia\n",
    "verytyped2(a::Int) = sin_for_int(a)\n",
    "verytyped2(a) = sin_for_general(a)\n",
    "\n",
    "# see unoptimized code, then look at optimized code\n",
    "descend((Any,); optimize=false) do a\n",
    "    verytyped2(a)\n",
    "end\n",
    "```\n",
    "\n",
    "(it might be interesting if you consider this example together with the fact that our manual says [\"In general, you should use the most general applicable abstract types for arguments, and when in doubt, omit the argument types.\"](\"https://docs.julialang.org/en/v1.8-dev/manual/functions/#Argument-type-declarations\"))"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Multithreading code\n",
    "\n",
    "Reasoning about multithreading code is hard even with Cthulhu (this implies that Julia compiler is also having hard time inferring and optimizing multithreading code).\n",
    "\n",
    "Let's consider optimizing this code:"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "source": [
    "function compute_sins(i)\n",
    "    n = 1000000\n",
    "    out = Vector{Float64}(undef, n)\n",
    "    Threads.@threads for itr in 1:n\n",
    "        i = itr\n",
    "        out[i] = sin(i)\n",
    "    end\n",
    "    return out\n",
    "end\n",
    "\n",
    "@benchmark compute_sins(1000000)"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "BenchmarkTools.Trial: 111 samples with 1 evaluation.\n",
       " Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m):  \u001b[39m\u001b[36m\u001b[1m39.952 ms\u001b[22m\u001b[39m … \u001b[35m56.223 ms\u001b[39m  \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 4.94%\n",
       " Time  \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m):     \u001b[39m\u001b[34m\u001b[1m44.851 ms              \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m):    \u001b[39m4.36%\n",
       " Time  \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m):   \u001b[39m\u001b[32m\u001b[1m45.349 ms\u001b[22m\u001b[39m ± \u001b[32m 3.016 ms\u001b[39m  \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m):  \u001b[39m3.98% ± 1.74%\n",
       "\n",
       "  \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m█\u001b[39m▂\u001b[39m \u001b[39m \u001b[39m▂\u001b[39m▂\u001b[39m▅\u001b[39m▂\u001b[34m \u001b[39m\u001b[39m \u001b[39m \u001b[32m \u001b[39m\u001b[39m \u001b[39m \u001b[39m▃\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▂\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \n",
       "  \u001b[39m▅\u001b[39m▄\u001b[39m▅\u001b[39m▁\u001b[39m▄\u001b[39m▅\u001b[39m▄\u001b[39m▅\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m▁\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[34m▇\u001b[39m\u001b[39m▅\u001b[39m▄\u001b[32m▇\u001b[39m\u001b[39m▅\u001b[39m▅\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m▅\u001b[39m▅\u001b[39m▇\u001b[39m▇\u001b[39m▅\u001b[39m▅\u001b[39m▇\u001b[39m▄\u001b[39m█\u001b[39m▁\u001b[39m▄\u001b[39m▄\u001b[39m▄\u001b[39m▄\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▄\u001b[39m \u001b[39m▄\n",
       "  40 ms\u001b[90m           Histogram: frequency by time\u001b[39m        56.2 ms \u001b[0m\u001b[1m<\u001b[22m\n",
       "\n",
       " Memory estimate\u001b[90m: \u001b[39m\u001b[33m38.14 MiB\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m1999499\u001b[39m."
      ]
     },
     "metadata": {},
     "execution_count": 6
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "source": [
    "@code_warntype compute_sins(1000000)"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "MethodInstance for compute_sins(::\u001b[0mInt64)\n",
      "  from compute_sins(i) in Main at In[6]:1\n",
      "Arguments\n",
      "  #self#\u001b[36m::Core.Const(compute_sins)\u001b[39m\n",
      "  i@_2\u001b[36m::Int64\u001b[39m\n",
      "Locals\n",
      "  threadsfor_fun\u001b[36m::var\"#208#threadsfor_fun#5\"{Vector{Float64}, UnitRange{Int64}}\u001b[39m\n",
      "  out\u001b[36m::Vector{Float64}\u001b[39m\n",
      "  n\u001b[36m::Int64\u001b[39m\n",
      "  range\u001b[36m::UnitRange{Int64}\u001b[39m\n",
      "  i@_7\u001b[91m\u001b[1m::Union{Int64, Core.Box}\u001b[22m\u001b[39m\n",
      "Body\u001b[36m::Vector{Float64}\u001b[39m\n",
      "\u001b[90m1 ─\u001b[39m       (i@_7 = i@_2)\n",
      "\u001b[90m│  \u001b[39m       (i@_7 = Core.Box(i@_7::Int64))\n",
      "\u001b[90m│  \u001b[39m       (n = 1000000)\n",
      "\u001b[90m│  \u001b[39m %4  = Core.apply_type(Main.Vector, Main.Float64)\u001b[36m::Core.Const(Vector{Float64})\u001b[39m\n",
      "\u001b[90m│  \u001b[39m       (out = (%4)(Main.undef, n::Core.Const(1000000)))\n",
      "\u001b[90m│  \u001b[39m %6  = (1:n::Core.Const(1000000))\u001b[36m::Core.Const(1:1000000)\u001b[39m\n",
      "\u001b[90m│  \u001b[39m       (range = %6)\n",
      "\u001b[90m│  \u001b[39m %8  = Main.:(var\"#208#threadsfor_fun#5\")\u001b[36m::Core.Const(var\"#208#threadsfor_fun#5\")\u001b[39m\n",
      "\u001b[90m│  \u001b[39m %9  = Core.typeof(out)\u001b[36m::Core.Const(Vector{Float64})\u001b[39m\n",
      "\u001b[90m│  \u001b[39m %10 = Core.typeof(range::Core.Const(1:1000000))\u001b[36m::Core.Const(UnitRange{Int64})\u001b[39m\n",
      "\u001b[90m│  \u001b[39m %11 = Core.apply_type(%8, %9, %10)\u001b[36m::Core.Const(var\"#208#threadsfor_fun#5\"{Vector{Float64}, UnitRange{Int64}})\u001b[39m\n",
      "\u001b[90m│  \u001b[39m %12 = i@_7\u001b[91m\u001b[1m::Core.Box\u001b[22m\u001b[39m\n",
      "\u001b[90m│  \u001b[39m %13 = out\u001b[36m::Vector{Float64}\u001b[39m\n",
      "\u001b[90m│  \u001b[39m       (threadsfor_fun = %new(%11, %12, %13, range::Core.Const(1:1000000)))\n",
      "\u001b[90m│  \u001b[39m %15 = Base.Threads.threadid()\u001b[36m::Int64\u001b[39m\n",
      "\u001b[90m│  \u001b[39m %16 = (%15 != 1)\u001b[36m::Bool\u001b[39m\n",
      "\u001b[90m└──\u001b[39m       goto #3 if not %16\n",
      "\u001b[90m2 ─\u001b[39m       goto #4\n",
      "\u001b[90m3 ─\u001b[39m %19 = $(Expr(:foreigncall, :(:jl_in_threaded_region), Int32, svec(), 0, :(:ccall)))\u001b[36m::Int32\u001b[39m\n",
      "\u001b[90m│  \u001b[39m %20 = (%19 != 0)\u001b[36m::Bool\u001b[39m\n",
      "\u001b[90m└──\u001b[39m       goto #5 if not %20\n",
      "\u001b[90m4 ┄\u001b[39m %22 = Base.invokelatest\u001b[36m::Core.Const(Base.invokelatest)\u001b[39m\n",
      "\u001b[90m│  \u001b[39m %23 = threadsfor_fun\u001b[36m::Core.PartialStruct(var\"#208#threadsfor_fun#5\"{Vector{Float64}, UnitRange{Int64}}, Any[Core.Box, Vector{Float64}, Core.Const(1:1000000)])\u001b[39m\n",
      "\u001b[90m│  \u001b[39m       (%22)(%23, true)\n",
      "\u001b[90m└──\u001b[39m       goto #6\n",
      "\u001b[90m5 ─\u001b[39m       Base.Threads.threading_run(threadsfor_fun::Core.PartialStruct(var\"#208#threadsfor_fun#5\"{Vector{Float64}, UnitRange{Int64}}, Any[Core.Box, Vector{Float64}, Core.Const(1:1000000)]))\n",
      "\u001b[90m6 ┄\u001b[39m       Base.Threads.nothing\n",
      "\u001b[90m└──\u001b[39m       return out\n",
      "\n"
     ]
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "There is `Core.Box`, which indicates something got captured by closure and it generally tends to be a source of bad performance. But it's not clear where it actually impacts the performance from the output of `@code_warntype`.\n",
    "\n",
    "Seemingly a problem lives in a `Base.Threads.threading_run` call ? Let's run Cthulhu and descend into there:\n",
    "```julia\n",
    "@descend compute_sins(1000000)\n",
    "```\n",
    "\n",
    "_Go to terminal_\n",
    "\n",
    "So the problem stemmed from the fact that the dead argument `i` is captured within a loop.\n",
    "We can just eliminate it and now it runs 3x faster."
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "source": [
    "function compute_sins()\n",
    "    n = 1000000\n",
    "    out = Vector{Float64}(undef, n)\n",
    "    Threads.@threads for itr in 1:n\n",
    "        i = itr\n",
    "        out[i] = sin(i)\n",
    "    end\n",
    "    return out\n",
    "end\n",
    "\n",
    "@benchmark compute_sins()"
   ],
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "BenchmarkTools.Trial: 306 samples with 1 evaluation.\n",
       " Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m):  \u001b[39m\u001b[36m\u001b[1m14.424 ms\u001b[22m\u001b[39m … \u001b[35m24.539 ms\u001b[39m  \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 14.86%\n",
       " Time  \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m):     \u001b[39m\u001b[34m\u001b[1m15.564 ms              \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m):    \u001b[39m0.00%\n",
       " Time  \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m):   \u001b[39m\u001b[32m\u001b[1m16.343 ms\u001b[22m\u001b[39m ± \u001b[32m 1.831 ms\u001b[39m  \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m):  \u001b[39m3.70% ±  7.04%\n",
       "\n",
       "  \u001b[39m \u001b[39m▄\u001b[39m█\u001b[39m▅\u001b[39m▅\u001b[39m▄\u001b[39m▄\u001b[39m \u001b[39m \u001b[39m \u001b[34m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[32m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m▅\u001b[39m \u001b[39m▁\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \n",
       "  \u001b[39m▆\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m█\u001b[39m▆\u001b[39m▇\u001b[39m▅\u001b[34m▅\u001b[39m\u001b[39m▆\u001b[39m▄\u001b[39m▃\u001b[39m▄\u001b[39m▃\u001b[32m▃\u001b[39m\u001b[39m▁\u001b[39m▆\u001b[39m█\u001b[39m█\u001b[39m▄\u001b[39m█\u001b[39m▅\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▃\u001b[39m▁\u001b[39m▃\u001b[39m▃\u001b[39m▅\u001b[39m▃\u001b[39m▄\u001b[39m▄\u001b[39m▄\u001b[39m▄\u001b[39m▃\u001b[39m▄\u001b[39m▃\u001b[39m▃\u001b[39m▄\u001b[39m▃\u001b[39m▃\u001b[39m▁\u001b[39m▃\u001b[39m▄\u001b[39m▃\u001b[39m▄\u001b[39m▃\u001b[39m▄\u001b[39m▃\u001b[39m▁\u001b[39m▃\u001b[39m▁\u001b[39m▁\u001b[39m▃\u001b[39m▁\u001b[39m▃\u001b[39m \u001b[39m▄\n",
       "  14.4 ms\u001b[90m         Histogram: frequency by time\u001b[39m        21.4 ms \u001b[0m\u001b[1m<\u001b[22m\n",
       "\n",
       " Memory estimate\u001b[90m: \u001b[39m\u001b[33m7.63 MiB\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m8\u001b[39m."
      ]
     },
     "metadata": {},
     "execution_count": 8
    }
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "source": [
    "# if you're interested, JETTest.jl can also tell the performance pitfall\n",
    "# but with some other reports that stem from multithread constructions\n",
    "@report_dispatch compute_sins(1000)"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "\u001b[7m═════ 6 possible errors found ═════\u001b[27m\n",
      "\u001b[35m┌ @ threadingconstructs.jl:97 \u001b[39m\u001b[0mBase.Threads.threading_run\u001b[0m(\u001b[0mthreadsfor_fun\u001b[0m)\n",
      "\u001b[35m│\u001b[39m\u001b[34m┌ @ threadingconstructs.jl:30 \u001b[39m\u001b[0mBase.Threads.Task\u001b[0m(\u001b[0mfunc\u001b[0m)\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m┌ @ threadingconstructs.jl:52 \u001b[39m\u001b[0m#self#\u001b[0m(\u001b[0mfalse\u001b[0m)\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m┌ @ In[6]:6 \u001b[39m\u001b[0mBase.setindex!\u001b[0m(\u001b[0m%88\u001b[0m, \u001b[0m%87\u001b[0m, \u001b[0m%94\u001b[0m)\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m│ runtime dispatch detected: \u001b[39m\u001b[0m\u001b[1mBase.setindex!\u001b[22m\u001b[0m\u001b[1m(\u001b[22m\u001b[0m\u001b[1m%88\u001b[22m\u001b[96m\u001b[1m::Vector{Float64}\u001b[22m\u001b[39m\u001b[0m\u001b[1m, \u001b[22m\u001b[0m\u001b[1m%87\u001b[22m\u001b[96m\u001b[1m::Any\u001b[22m\u001b[39m\u001b[0m\u001b[1m, \u001b[22m\u001b[0m\u001b[1m%94\u001b[22m\u001b[96m\u001b[1m::Any\u001b[22m\u001b[39m\u001b[0m\u001b[1m)\u001b[22m\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m└───────────\u001b[39m\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m┌ @ In[6]:6 \u001b[39m\u001b[0mMain.sin\u001b[0m(\u001b[0m%86\u001b[0m)\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m│ runtime dispatch detected: \u001b[39m\u001b[0m\u001b[1mMain.sin\u001b[22m\u001b[0m\u001b[1m(\u001b[22m\u001b[0m\u001b[1m%86\u001b[22m\u001b[96m\u001b[1m::Any\u001b[22m\u001b[39m\u001b[0m\u001b[1m)\u001b[22m\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m└───────────\u001b[39m\n",
      "\u001b[35m│\u001b[39m\u001b[34m┌ @ threadingconstructs.jl:38 \u001b[39m\u001b[0mBase.Threads.wait\u001b[0m(\u001b[0mBase.getindex\u001b[0m(\u001b[0mtasks\u001b[0m, \u001b[0mi\u001b[0m)\u001b[0m)\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m┌ @ task.jl:320 \u001b[39m\u001b[0mBase._wait\u001b[0m(\u001b[0mt\u001b[0m)\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m┌ @ task.jl:293 \u001b[39m\u001b[0mBase.wait\u001b[0m(\u001b[0m%30\u001b[0m)\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m│ runtime dispatch detected: \u001b[39m\u001b[0m\u001b[1mBase.wait\u001b[22m\u001b[0m\u001b[1m(\u001b[22m\u001b[0m\u001b[1m%30\u001b[22m\u001b[96m\u001b[1m::Any\u001b[22m\u001b[39m\u001b[0m\u001b[1m)\u001b[22m\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m└───────────────\u001b[39m\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m┌ @ task.jl:290 \u001b[39m\u001b[0mBase.lock\u001b[0m(\u001b[0m%13\u001b[0m)\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m│ runtime dispatch detected: \u001b[39m\u001b[0m\u001b[1mBase.lock\u001b[22m\u001b[0m\u001b[1m(\u001b[22m\u001b[0m\u001b[1m%13\u001b[22m\u001b[96m\u001b[1m::Any\u001b[22m\u001b[39m\u001b[0m\u001b[1m)\u001b[22m\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m└───────────────\u001b[39m\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m┌ @ task.jl:296 \u001b[39m\u001b[0mBase.unlock\u001b[0m(\u001b[0m%40\u001b[0m)\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m│ runtime dispatch detected: \u001b[39m\u001b[0m\u001b[1mBase.unlock\u001b[22m\u001b[0m\u001b[1m(\u001b[22m\u001b[0m\u001b[1m%40\u001b[22m\u001b[96m\u001b[1m::Any\u001b[22m\u001b[39m\u001b[0m\u001b[1m)\u001b[22m\n",
      "\u001b[35m│\u001b[39m\u001b[34m│\u001b[39m\u001b[33m│\u001b[39m\u001b[91m└───────────────\u001b[39m\n",
      "\u001b[35m│\u001b[39m\u001b[91m┌ @ task.jl:322 \u001b[39m\u001b[0mBase.TaskFailedException\u001b[0m(\u001b[0m%68\u001b[0m)\n",
      "\u001b[35m│\u001b[39m\u001b[91m│ runtime dispatch detected: \u001b[39m\u001b[0m\u001b[1mBase.TaskFailedException\u001b[22m\u001b[0m\u001b[1m(\u001b[22m\u001b[0m\u001b[1m%68\u001b[22m\u001b[96m\u001b[1m::Task\u001b[22m\u001b[39m\u001b[0m\u001b[1m)\u001b[22m\n",
      "\u001b[35m│\u001b[39m\u001b[91m└───────────────\u001b[39m\n"
     ]
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "(Vector{Float64}, 6)"
      ]
     },
     "metadata": {},
     "execution_count": 9
    }
   ],
   "metadata": {}
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "juliacon2021-workshop-pkgdev 1.8.0-DEV",
   "language": "julia",
   "name": "juliacon2021-workshop-pkgdev-1.8"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.8.0"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}