profiling.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "90994e34",
   "metadata": {},
   "outputs": [],
   "source": [
    "using BenchmarkTools\n",
    "using ProfileView"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "386f9c2a",
   "metadata": {},
   "source": [
    "# Julia Likes to Know Your Type"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d99f473d",
   "metadata": {},
   "source": [
    "### Suppose I want to make a container that will hold two arrays, then I want to make a function that operates on those two arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4bcbaca5",
   "metadata": {},
   "outputs": [],
   "source": [
    "# First define a basic container\n",
    "struct Holder\n",
    "    x\n",
    "    y\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "61b126f5",
   "metadata": {},
   "outputs": [],
   "source": [
    "# And now my function\n",
    "a = 7\n",
    "b = 3\n",
    "function f(H::Holder)\n",
    "    return a * H.x.^2 + b * H.y.^2\n",
    "end;\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a0fcb321",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Now make a container and call f\n",
    "H = Holder([1, 2], [2, 3])\n",
    "f(H)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb3c7da4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Looks good, except...\n",
    "@time f(H)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3b13e5dd",
   "metadata": {},
   "outputs": [],
   "source": [
    "# That a lot of memory allocations for a simple function\n",
    "# and if the containers get big...\n",
    "H = Holder(rand(10^7), rand(10^7))\n",
    "f(H)\n",
    "@time f(H);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "80a8a0cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's do better\n",
    "# First thing we can do is look at what the compiler sees\n",
    "H = Holder([1, 2], [2, 3])\n",
    "@code_warntype f(H);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "90720659",
   "metadata": {},
   "outputs": [],
   "source": [
    "# We should never use global variables inside a function, because Julia doesn't know if I'll change the type\n",
    "a = \"This was an Int but now it's a String...\"\n",
    "f(H)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "02eaea59",
   "metadata": {},
   "outputs": [],
   "source": [
    "# So we can make variables constants or we can make them function arguments\n",
    "const ca = 7\n",
    "function f(H, b)\n",
    "    return ca * H.x.^2 + b * H.y.^2\n",
    "end\n",
    "\n",
    "H = Holder([1, 2], [2, 3])\n",
    "f(H, 3) # compile\n",
    "@time f(H, 3);\n",
    "println()\n",
    "@code_warntype f(H, 3);\n",
    "\n",
    "# this didn't actually reduce allocations in this case, but the compiler looks better\n",
    "# it's a start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "519a2e20",
   "metadata": {},
   "outputs": [],
   "source": [
    "# So it knows what ca and b are, but not what H1.x and H1.y are\n",
    "Holder(\"Howdy\", (1.0, [1+2im, 1.0+3im]))\n",
    "\n",
    "#Let's be more specific"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa6b4c97",
   "metadata": {},
   "outputs": [],
   "source": [
    "# This container provides some type information\n",
    "struct TypedHolder\n",
    "    x::AbstractVector{<:Real}\n",
    "    y::AbstractVector{<:Real}\n",
    "end\n",
    "TH = TypedHolder([1, 2], [2, 3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7ca3ddaa",
   "metadata": {},
   "outputs": [],
   "source": [
    "f(TH, 3)\n",
    "@time f(TH, 3)\n",
    "println()\n",
    "@code_warntype f(TH, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5fd1ed73",
   "metadata": {},
   "outputs": [],
   "source": [
    "# The problem is that we've still used abstract types, so maybe it's a bit better, but the compiler still doesn't know what it's getting\n",
    "# We should use concrete types instead\n",
    "struct ConcreteHolder\n",
    "    x::Vector{Int}\n",
    "    y::Vector{Int}\n",
    "end\n",
    "CH = ConcreteHolder([1, 2], [2, 3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05bc7175",
   "metadata": {},
   "outputs": [],
   "source": [
    "f(CH, 3)\n",
    "@time f(CH, 3)\n",
    "println()\n",
    "@code_warntype f(CH, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d7698702",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Much better! But now we're pretty restricted\n",
    "CH = ConcreteHolder(rand(10^7), rand(10^7));"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1551b53",
   "metadata": {},
   "source": [
    "### The Power of Parametric Types"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "077e2830",
   "metadata": {},
   "outputs": [],
   "source": [
    "struct ParametricElementHolder{T<:Real}\n",
    "    x::Vector{T}\n",
    "    y::Vector{T}\n",
    "end\n",
    "ParametricElementHolder([1, 2], [2, 3])\n",
    "ParametricElementHolder(rand(10^7), rand(10^7));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "659bedfa",
   "metadata": {},
   "outputs": [],
   "source": [
    "PEH = ParametricElementHolder([1, 2], [2, 3])\n",
    "\n",
    "f(PEH, 3)\n",
    "@time f(PEH, 3)\n",
    "println()\n",
    "@code_warntype f(PEH, 3)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c8b01f43",
   "metadata": {},
   "outputs": [],
   "source": [
    "# This is still a bit restrictive\n",
    "println(typeof(1:2))\n",
    "ParametricElementHolder(1:2, 2:3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "934785e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# So we can be more general\n",
    "struct ParametricHolder{T<:AbstractVector{<:Real}, S<:AbstractVector{<:Real}}\n",
    "    x::T\n",
    "    y::S\n",
    "end\n",
    "\n",
    "# Now all of these work\n",
    "println(typeof(ParametricHolder([1, 2], [2, 3])))\n",
    "println(typeof(ParametricHolder(rand(10^7), rand(10^7))))\n",
    "println(typeof(ParametricHolder(1:2, 2:3)))\n",
    "println(typeof(ParametricHolder(1:2, [2.0, 3.0])))\n",
    "\n",
    "# And we've got better performance\n",
    "PH = ParametricHolder([1, 2], [2, 3])\n",
    "\n",
    "f(PH, 3)\n",
    "@time f(PH, 3)\n",
    "println()\n",
    "@code_warntype f(PH, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de568c97",
   "metadata": {},
   "source": [
    "## It's all about the dots"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b7926abb",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Here's the function we've been running\n",
    "function f(C, b)\n",
    "    return ca * C.x .^ 2 + b * C.y .^ 2\n",
    "end\n",
    "\n",
    "# Those dots say to operate element wise, but most of the operators don't have dots.\n",
    "# This is the same as\n",
    "function f2(C, b)\n",
    "    x2 = C.x .^ 2\n",
    "    ax2 = ca * x2\n",
    "    y2 = C.y .^ 2\n",
    "    by2 = b * y2\n",
    "    return ax2 + by2\n",
    "end\n",
    "\n",
    "f(PH, 3)\n",
    "f2(PH, 3)\n",
    "@time f(PH, 3)\n",
    "@time f2(PH, 3);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d6e7dd6a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Instead we should use dots so that all of it is vectorized\n",
    "function fdot(C, b)\n",
    "    return ca .* C.x .^ 2 .+ b .* C.y .^ 2\n",
    "end\n",
    "fdot(PH, 3)\n",
    "@time fdot(PH, 3);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e24b9a6b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# There's still some allocation because we're allocating the result\n",
    "# We could preallocate instead\n",
    "\n",
    "function fdot!(result, C, b)\n",
    "    result .= ca .* C.x .^ 2 .+ b .* C.y .^ 2\n",
    "end\n",
    "\n",
    "R = zero(PH.x)\n",
    "fdot!(R, PH, b)\n",
    "@time fdot!(R, PH, b);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e315040b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Success! We've eliminated all allocations\n",
    "# Let's see performance\n",
    "x = rand(10^7)\n",
    "y = rand(10^7)\n",
    "\n",
    "H = Holder(x, y)\n",
    "PH = ParametricHolder(x, y)\n",
    "\n",
    "R = zero(x)\n",
    "\n",
    "f(H, 3)\n",
    "f(PH, 3)\n",
    "fdot!(R, H, 3)\n",
    "fdot!(R, PH, 3)\n",
    "\n",
    "println(\"No Parametric Type, No dots\")\n",
    "@time f(H, 3)\n",
    "println(\"Parametric Type, No dots\")\n",
    "@time f(PH, 3)\n",
    "println(\"No Parametric Type, with dots\")\n",
    "@time fdot!(R, H, 3)\n",
    "println(\"Parametric Type, with dots\")\n",
    "@time fdot!(R, PH, 3);\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55fb4b4b",
   "metadata": {},
   "source": [
    "### We can see that the dots give the main performance increase, but to fully eliminate allocations, we needed to use parametric types. In this simple application, the parametric type didn't increase performance, but if this were inside a loop, an optimizer, or any performance critical part of the code, it can be a huge benefit."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44651af1",
   "metadata": {},
   "source": [
    "# Avoid allocation whenever possible in loops/optimization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6b1dabc7",
   "metadata": {},
   "outputs": [],
   "source": [
    "function xpm(x)\n",
    "    return [x-1, x, x+1]\n",
    "end;\n",
    "\n",
    "function g()\n",
    "    y = 0\n",
    "    for i = 1:10^7\n",
    "        ret = xpm(i)\n",
    "        y += ret[2]\n",
    "    end\n",
    "    return y\n",
    "end;\n",
    "g()\n",
    "@time g();\n",
    "# xpm allocates every time, so this is bad"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e4ad26a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Instead we could preallocate and then operate in-place\n",
    "function xpm!(ret, x)\n",
    "    return [x-1, x, x+1]\n",
    "end\n",
    "\n",
    "function g_inplace()\n",
    "    y = 0\n",
    "    ret = Vector{Int}(undef, 3)\n",
    "    for i = 1:10^7\n",
    "        xpm!(ret, i)\n",
    "        y += ret[2]\n",
    "    end\n",
    "    return y\n",
    "end;\n",
    "g_inplace\n",
    "@time g_inplace()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2accbfc0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Or use an SVector/MVector, which are small (length < ~100) statically sized arrays\n",
    "using StaticArrays\n",
    "function xpm_static(x)\n",
    "    return @SVector[x-1, x, x+1]\n",
    "end\n",
    "\n",
    "function g_static()\n",
    "    y = 0\n",
    "    for i = 1:10^7\n",
    "        ret = xpm_static(i)\n",
    "        y += ret[2]\n",
    "    end\n",
    "    return y\n",
    "end\n",
    "g_static()\n",
    "@time g_static();"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22c805c5",
   "metadata": {},
   "source": [
    "## Type Instability"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ab1c1a60",
   "metadata": {},
   "outputs": [],
   "source": [
    "function mymax(low, x)\n",
    "    s = low\n",
    "    for xi in x\n",
    "        s = (s < xi) ? xi : s\n",
    "    end\n",
    "    return s\n",
    "end;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b66bc30d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# works well for integers\n",
    "x = rand(Int, 1000)\n",
    "\n",
    "@btime mymax(-Inf, $x)\n",
    "@btime mymax(typemin(Int), $x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d97ef7d",
   "metadata": {},
   "source": [
    "## Slicing arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d18f4cea",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's make a Fourier series summer\n",
    "\n",
    "c_coeffs = rand(1000) # c[m] * cos(m * θ)\n",
    "s_coeffs = rand(1000) # s[m] * sin(m * θ)\n",
    "c0 = 1.0\n",
    "\n",
    "coeffs = vcat(c0, c_coeffs, s_coeffs);\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c3a48b4c",
   "metadata": {},
   "outputs": [],
   "source": [
    "function Fsum(θ, coeffs)\n",
    "    M = (length(coeffs) - 1) ÷ 2\n",
    "    c_coeffs = coeffs[2:(M+1)]\n",
    "    s_coeffs = coeffs[(M+2):end]\n",
    "\n",
    "    tot = coeffs[1]\n",
    "    tot += sum(c_coeffs .* cos.((1:M) .* θ) .+ s_coeffs .* sin.((1:M) .* θ))\n",
    "end\n",
    "@btime Fsum(1.0, $coeffs);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7bdbd4a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "θs = range(0, 2π, 1001)\n",
    "@time Fsum.(θs, Ref(coeffs));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9b11b260",
   "metadata": {},
   "outputs": [],
   "source": [
    "function Fsum(θ, coeffs)\n",
    "    M = (length(coeffs) - 1) ÷ 2\n",
    "    c_coeffs = @view(coeffs[2:(M+1)])\n",
    "    @views s_coeffs = coeffs[(M+2):end]\n",
    "\n",
    "    tot = coeffs[1]\n",
    "    tot += sum(c_coeffs .* cos.((1:M) .* θ) .+ s_coeffs .* sin.((1:M) .* θ))\n",
    "end;\n",
    "@btime Fsum(1.0, $coeffs);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c3829ee3",
   "metadata": {},
   "outputs": [],
   "source": [
    "function Fsum(θ, coeffs)\n",
    "    M = (length(coeffs) - 1) ÷ 2\n",
    "    c_coeffs = @view(coeffs[2:(M+1)])\n",
    "    @views s_coeffs = coeffs[(M+2):end]\n",
    "    tot = coeffs[1]\n",
    "    tot += sum(c_coeffs[m] * cos(m * θ) + s_coeffs[m] * sin(m * θ) for m in 1:M)\n",
    "    #tot += sum(s * sin(m * θ) for (m, s) in enumerate(s_coeffs))\n",
    "    return tot\n",
    "end;\n",
    "@btime Fsum(1.0, $coeffs);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4af13e45",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb569382",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.11.2",
   "language": "julia",
   "name": "julia-1.11"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.11.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}