concorrencia/primes/n_primes_proc.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e165c356-ad3d-420b-9826-b08ee6ee9612",
   "metadata": {},
   "source": [
    "# Demonstração: processos cooperando através de filas\n",
    "\n",
    "### Conceitos: número primo e menor fator primo\n",
    "\n",
    "Número primo `n` só pode ser representados por `1` fileira de itens.\n",
    "\n",
    "Números compostos podem ser representados por `f` fileiras de itens.\n",
    "\n",
    "O '''menor fator primo''' é a menor dimensão que é um número primo.\n",
    "\n",
    "<img src=\"prime-cookies.png\" width=\"50%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9290715-6774-40e7-85c1-64fc3e94c8da",
   "metadata": {},
   "source": [
    "### Importar o que vamos usar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "35f9d950-3868-4ac3-ab1c-30d0cee56977",
   "metadata": {},
   "outputs": [],
   "source": [
    "import os, math, sys\n",
    "from time import perf_counter\n",
    "from typing import NamedTuple, TypeAlias\n",
    "import multiprocessing as mp\n",
    "import multiprocessing.queues as mpq\n",
    "\n",
    "from primes import least_prime_factor, make_sample\n",
    "\n",
    "from table import Table"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d7d9d31-4764-4529-bdaf-c4b923563b61",
   "metadata": {},
   "source": [
    "### Selecionar a magnitude dos números para trabalhar\n",
    "\n",
    "Escolha uma magnitute apropriada para que a demonstração não fique lenta demais ou rápida demais na sua máquina."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "01bdf2f4-6473-4937-b053-d7fd6fe18d1c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "144_115_188_075_855_872\n"
     ]
    }
   ],
   "source": [
    "# may be needed on MacOS 13\n",
    "# see: https://superfastpython.com/filenotfounderror-multiprocessing-python/\n",
    "mp.set_start_method('fork')\n",
    "\n",
    "# Magnitude of primes that take a few seconds to check\n",
    "#\n",
    "# machine  magnitude\n",
    "# RPI4     2 ** 49\n",
    "# X250     2 ** 53\n",
    "# YOGA9    2 ** 57\n",
    "# M2MAX    2 ** 57\n",
    "# VIVO     2 ** 63\n",
    "\n",
    "MAGNITUDE = 2**57\n",
    "\n",
    "print(f'{MAGNITUDE:_}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "51612d06-3dd4-4a02-9bb8-36c824451171",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "≈ 2↑54   18_014_398_509_481_951\n",
      "≈ 2↑54   18_014_398_509_481_984\n",
      "≈ 2↑54   18_014_399_314_786_597\n",
      "≈ 2↑55   27_021_597_764_222_939\n",
      "≈ 2↑55   27_021_597_764_222_976\n",
      "≈ 2↑55   27_021_598_744_655_129\n",
      "≈ 2↑55   36_028_797_018_963_913\n",
      "≈ 2↑55   36_028_797_018_963_968\n",
      "≈ 2↑55   36_028_803_757_875_637\n",
      "≈ 2↑56   54_043_195_528_445_869\n",
      "≈ 2↑56   54_043_195_528_445_952\n",
      "≈ 2↑56   54_043_196_378_148_947\n",
      "≈ 2↑56   72_057_594_037_927_931\n",
      "≈ 2↑56   72_057_594_037_927_936\n",
      "≈ 2↑56   72_057_596_722_278_677\n",
      "≈ 2↑57  108_086_391_056_891_903\n",
      "≈ 2↑57  108_086_391_056_891_904\n",
      "≈ 2↑57  108_086_392_348_502_419\n",
      "≈ 2↑57  144_115_188_075_855_859\n",
      "≈ 2↑57  144_115_188_075_855_872\n",
      "≈ 2↑57  144_115_189_976_253_901\n"
     ]
    }
   ],
   "source": [
    "sample = sorted(make_sample(MAGNITUDE))\n",
    "\n",
    "from math import log2\n",
    "\n",
    "for n in sample:\n",
    "    print(f'≈ 2↑{log2(n):.0f} {n:24_}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b10d9eac-62a7-412d-962f-6061c551cc6b",
   "metadata": {},
   "source": [
    "### Classe que representa um exemplo de fatoração\n",
    "\n",
    "`n`: inteiro a ser fatorado\n",
    "`lpf`: Least Prime Factor (menor fator primo)\n",
    "`elapsed`: tempo transcorrido para fatorar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "9bbe5088-97ce-4bd4-af8b-cfb79922f7dd",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Experiment(NamedTuple):  # <3>\n",
    "    n: int\n",
    "    lpf: int\n",
    "    elapsed: float\n",
    "\n",
    "    @property\n",
    "    def prime(self):\n",
    "        return self.n == self.lpf"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "939c83b1-c3ec-4f11-9319-e008e0c8f4cb",
   "metadata": {},
   "source": [
    "### Fazer um experimento"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "8afbb12c-eb1e-456a-8aa8-11a855bb2e20",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Experiment(n=7, lpf=7, elapsed=2.582994056865573e-06)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def check(n: int) -> Experiment:  # <6>\n",
    "    t0 = perf_counter()\n",
    "    res = least_prime_factor(n)\n",
    "    return Experiment(n, res, perf_counter() - t0)\n",
    "\n",
    "check(7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "7f06fe8b-cefe-4f38-b018-6c68f2a1d21a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Experiment(n=9, lpf=3, elapsed=7.499911589547992e-07)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "check(9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "02087ea4-9fcc-4cee-9a0f-697c260c6938",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Experiment(n=72057596722278677, lpf=268435399, elapsed=2.7066562920081196)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "check(72057596722278677)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a24a3431-d3ef-4fcc-bf75-70d0647874a0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "268435523"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "72057596722278677 // 268435399"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "000797be-6356-423c-84da-a83b20b449c6",
   "metadata": {},
   "source": [
    "### Fluxo de trabalho\n",
    "\n",
    "<img src=\"process-workflow.png\" width=\"50%\">"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d4bde5b5-b28d-49e0-bdcb-9b475d6c55c5",
   "metadata": {},
   "source": [
    "### Criar um worker\n",
    "\n",
    "Cada worker é uma função que fica em loop consumindo tarefas da fila: `jobs.get()`.\n",
    "\n",
    "O resultado de cada `check(n)` processado é um `Experiment`, colocado na fila `results`.\n",
    "\n",
    "Quando `jobs.get()` devolve `0`, é uma \"poison pill\" (cápsula de veneno).\n",
    "\n",
    "Então saímos do laço e colocamos um `Experiment` com `n=0` para sinalizar que terminamos."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "29695231-1636-4e49-b016-741dfbcb2f7d",
   "metadata": {},
   "outputs": [],
   "source": [
    "JobQueue = mpq.SimpleQueue[int]  # <4>\n",
    "ResultQueue = mpq.SimpleQueue[Experiment]  # <5>\n",
    "\n",
    "def worker(jobs: JobQueue, results: ResultQueue) -> None:  # <7>\n",
    "    while n := jobs.get():  # <8>\n",
    "        results.put(check(n))  # <9>\n",
    "    results.put(Experiment(0, False, 0.0))  # <10>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "743ed639-c0cf-4a96-9de4-2d0696061640",
   "metadata": {},
   "source": [
    "### Enfileirar tarefas\n",
    "\n",
    "Colocamos cada `n` da amostra na fila `jobs`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "f3e4d318-0542-4e87-9f24-f475bbeeb962",
   "metadata": {},
   "outputs": [],
   "source": [
    "def queue_jobs() -> JobQueue:\n",
    "    jobs: JobQueue = mp.SimpleQueue()  # <2>\n",
    "    for n in make_sample(MAGNITUDE):\n",
    "        jobs.put(n)  # <12>\n",
    "    return jobs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e399180c-b32f-49dc-b99f-b8dbb7eb6fe3",
   "metadata": {},
   "source": [
    "### Iniciar tarefas\n",
    "\n",
    "Para cada processo worker criado:\n",
    "\n",
    "* `proc.start()` inicia o worker;\n",
    "* `jobs.put(0)` coloca um 0 como sinal para o worker terminar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "485f72e7-abae-49bb-8f49-4184ea6a6c02",
   "metadata": {},
   "outputs": [],
   "source": [
    "def start_jobs(qtd_procs: int, jobs: JobQueue, results: ResultQueue):    \n",
    "    for _ in range(qtd_procs):\n",
    "        proc = mp.Process(target=worker, args=(jobs, results))  # <13>\n",
    "        proc.start()  # <14>\n",
    "        jobs.put(0)  # <15> \"poison pill\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d573fde1-befd-4c23-9789-e4cdf88942d4",
   "metadata": {},
   "source": [
    "### Exibir resultados\n",
    "\n",
    "Enquanto ainda há processos executando:\n",
    "\n",
    "* obtemos um `Experiment` da fila `results`;\n",
    "* se `exp.n` é zero, o processo terminou;\n",
    "* do contrário, atualizamos a tabela com o resultado."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "0474191a-7650-4488-8853-be66d9cd1c61",
   "metadata": {},
   "outputs": [],
   "source": [
    "def report(qtd_procs: int, results: ResultQueue, table: Table) -> int:  # <6>\n",
    "    checked = 0\n",
    "    procs_done = 0\n",
    "    while procs_done < qtd_procs:  # <7>\n",
    "        exp = results.get()  # <8>\n",
    "        if exp.n == 0:  # <9>\n",
    "            procs_done += 1\n",
    "        else:\n",
    "            checked += 1  # <10>\n",
    "            table.update(exp.n, exp.lpf, exp.elapsed)\n",
    "            \n",
    "    return checked"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8933826-39af-459a-bccb-326b3ec028b2",
   "metadata": {},
   "source": [
    "### Orquestração dos componentes\n",
    "\n",
    "* criar e exibir a tabela de resultados com os números da amostra;\n",
    "* reportar quantidade de processos worker a serem usados;\n",
    "* registrar momento inicial em `t0`;\n",
    "* enfileirar tarefas (isso é praticamente imediato);\n",
    "* criar fila de resultados;\n",
    "* iniciar tarefas;\n",
    "* exibir resultados à medida que ficam prontos;\n",
    "* exibir número de verificações feitas e o tempo transcorrido.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "b59187a7-d984-45c0-aba9-f69ff2393091",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "06b4e544871041329d04047f0b87c7a9",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "VBox(children=(Valid(value=False, description='18_014_398_509_481_951', layout=Layout(width='90%'), readout='⏳…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Using 12 worker processes.\n",
      "21 checks in 6.5s\n"
     ]
    }
   ],
   "source": [
    "def supervisor(qtd_procs: int) -> None:\n",
    "    table = Table(sample)\n",
    "    table.display()\n",
    "    print(f'Using {qtd_procs} worker processes.')\n",
    "    t0 = perf_counter()\n",
    "    jobs = queue_jobs()\n",
    "    results: ResultQueue = mp.SimpleQueue()\n",
    "    start_jobs(qtd_procs, jobs, results)  # <3>\n",
    "    checked = report(qtd_procs, results, table)  # <4>\n",
    "    elapsed = perf_counter() - t0\n",
    "    print(f'{checked} checks in {elapsed:.1f}s')\n",
    "\n",
    "supervisor(os.cpu_count())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ca3feb71-c37b-4fdb-bd36-87f0b2fe06f1",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}