---
### [python - speed up]
- [[python - speed up]利用Concurrency加速 Python 程式執行效率](https://hackmd.io/@YungHuiHsu/SJ5EgB5eT)
#### process 與 thread
- [[python - speed up] process(程序/進程) 與 thread (執行緒/線程)](https://hackmd.io/@YungHuiHsu/SJCIdO5x6)
- [[python - speed up] 多執行緒(multi-threading)的基本概念](https://hackmd.io/@YungHuiHsu/r1C9Akpgp)
- [python - speed up] threading 模組的使用(待補)
- [[python - speed up] How to speed up multiple camera streams simultaneously with multithreading<br>如何使用多執行序加速視訊(相機/錄影)串流](https://hackmd.io/@YungHuiHsu/BJr5SyYQn)
- [python - speed up] multiprocessing模組的各種使用方法(待補)
- [[python - speed up] multiprocessing模組的Pool功能使用範例。multiprocessing.Pool Sample Notes](https://hackmd.io/@YungHuiHsu/BJiMZLKxp)

---
# [python - speed up] 利用Concurrency加速Python 程式執行效率
## 前言

在python中要進行加速運算時，可能對於process 、thread、Concurrency、Parallelism等概念感到混淆，以及對於python提供加速運算的內建模組，諸如`threading`、`asyncio`、`multiprocessing`、`concurrent`感到疑惑，本文旨在幫助使用者建立基本觀念，幫助工具選擇

---
## 電腦(Computers)的硬體限制與傳輸延遲(Latency)
[source: realpython.com/lessons/computers-latency/](https://realpython.com/lessons/computers-latency/)
現代電腦系統中，資料必須在不同的硬體層級進行運算與傳輸，但不同層級間的運算速度不等，而導致了延遲(latency)產生

延遲(latency)是指從發送請求到接收到相應的反應(response)所經過的時間。在電腦系統中，延遲可以出現在多個層面：
* 網路延遲：數據在網路中傳輸的時間。
* I/O延遲：數據讀取或寫入的時間。
* 處理延遲：CPU或其他處理單元處理數據的時間。
* 排隊延遲：數據在等待被處理的時間。

由於從CPU往外、經由Cashe、RAM(memory)、Disk、Network等層級的資料傳輸速度/延遲(Latency)呈現數量級的遞減，因此需要考量任務執行時，效能卡在哪個層級來選擇適合的對應處理方案

### I/O-Bound vs CPU-Bound

[source: A virtual machine scheduler based on CPU and I/O-bound features for energy-aware in high performance computing clouds](https://www.sciencedirect.com/science/article/pii/S0045790616302270)

[source](https://hackmd.io/@zsy/OS-midterm1)

- **I/O-Bound** 輸入/輸出密集型任務
- 指主要受到輸入/輸出速度限制的任務
- 程序的執行速度主要取決於**輸入/輸出操作的速度**，例如從硬碟讀取資料或從網路獲取資料
[source: realpython.com/lessons/computers-latency/](https://realpython.com/lessons/computers-latency/)
- **CPU-Bound** CPU密集型任務
- 指主要受到CPU處理速度限制的任務
- 程序的執行速度主要**取決於CPU的計算能力**，即CPU執行指令的速度

不同延遲原因的解決方案：
* 低延遲I/O：對於I/O密集型應用程序，降低I/O操作的延遲可以顯著提高性能
* 平行處理：通過並行處理(concurrency)和多線程，我們可以在等待一個任務（例如，I/O操作）完成時，讓CPU同時處理其他任務，從而減少總體延遲
* 緩存和預取：使用緩存和數據預取策略可以減少對高延遲操作（例如，網路請求或硬盤讀取）的依賴

## Concurrency（並行）和Parallelism(平行)
[source: wiki](https://en.wikipedia.org/wiki/File:Parallel-concurrent.png)

[source: Shivprasad koirala。codeproject.com。Concurrency vs Parallelism](https://www.codeproject.com/Articles/1267757/Concurrency-vs-Parallelism)

### Concurrency（並行，中國翻譯"並發"）
- 程式能夠**同時處理**多個任務的能力
這些任務並非在真實物理時間上同時進行，而是透過程式邏輯讓它看起來像是同時發生(透過在不同的時間片段輪流執行thread或task)
- 並行關注的是結構和設計

在python中，`threading` 和 `asyncio` 之間的最大區別是執行序(thread)/任務(task)輪流運行的方式

- `threading`模組
使用搶先式多任務處理(pre-emptive multitasking)，操作系統可以**搶佔thread**以進行**切換**。操作系統實際上瞭解並掌控每個線程，並可以隨時**中斷**它以開始運行其他thread。

搶先式多任務處理非常方便，因為thread中的程式碼不需要執行任何操作即可進行切換。 由於存在“隨時”一詞，這也可能導致實作上的複雜與困難。因為切換可能發生在很小的單位，例如單個 Python 語法的中間，例如 `x = x + 1` 之類的簡單語法(涉及多步原子操作atomic operation，詳見[深入 GIL](https://blog.louie.lu/2017/05/19/%E6%B7%B1%E5%85%A5-gil-%E5%A6%82%E4%BD%95%E5%AF%AB%E5%87%BA%E5%BF%AB%E9%80%9F%E4%B8%94-thread-safe-%E7%9A%84-python-grok-the-gil-how-to-write-fast-and-thread-safe-python/))

- `asyncio` 模組
使用協作式多任務處理(cooperative multitasking)。 這些任務必須通過明確宣告何時準備好退出來進行協作(程式碼必須稍作更改才能實現)

> wiki
> 在電腦科學中，並行性（Concurrency）指的是一個程式、演算法或問題的不同部分或單元能夠以非順序或部分順序的方式執行，而不影響最終結果。這允許並行單元的平行執行，這在多處理器和多核心系統中可以顯著提高執行的整體速度。用更技術性的術語來說，並行性指的是一個程式、演算法或問題能夠分解為無序或部分有序的組件或計算單元。

### Parallelism（平行，中國翻譯"並行"）
- **同時執行**多個任務的能力
這裡的同時是指物理上的同時，即同一時刻執行多個任務
- 並行關注的是提高執行效率
- 在python中使用`multiprocessing`模組實現
通過`multiprocessing`，Python 創建了新的process。 一個process可以視為幾乎完全不同的程式，儘管從技術上講，它們通常被定義為資源的集合，其中資源包括記憶體，文件(file handles )等。每個process都在自己的 Python 解釋器中運行

由於是不同的process，因此`multiprocessing`程式中的每個程式碼邏輯都可以在不同的核心上執行，亦即"平行"

## 並行的多工處理 Concurrency Multitasking

[source : 2019。travishen。Generator as Coroutines](https://super9.space/archives/1818)

| 特點 | Cooperative Multitasking | Pre-emptive Multitasking |
|------------------|--------------------------------------------------|----------------------------------------------------|
| **控制** |**process控制**CPU使用時間 | **作業系統控制**CPU使用時間 |
| **中斷** | process**自願釋放**控制 | 作業系統可以在任何時間**中斷**進程 |
| **資源管理** | 依賴process合作和正確釋放資源、資源分配可能不夠公平或高效 | 作業系統積極管理和分配資源 |
| **響應性** | 可能受到單一process占用CPU的影響、一個不合作的process可能導致系統中斷 | 通常提供更好的系統響應性和用戶交互性 |
| **開發複雜性** | 相對簡單；process有更多的控制權、開發者需要確保process正確釋放CPU | 開發者不需要擔心process，但需要處理同步和並行問題 |
| **應用場景** | 適用於較簡單或事件驅動的系統 | 適用於需要高度交互和平行處理的系統 |

| 並行類型<br>(Concurrency Type) | 切換決定 | 處理器(Processors)數量 |
|:------------------------------------------------------:|:------------------------------------:|:----------------------:|
| 搶占式多任務<br>Pre-emptive multitasking (`threading`) | 作業系統決定何時在Python外部切換任務 | 1 |
| 協作式多任務<br>Cooperative multitasking (`asyncio`) | 任務決定何時放棄控制(process自願釋放控制) | 1 |
| 多程序處理<br>Multiprocessing (`multiprocessing`) | 所有process在不同的處理器上同時運行 | Many |

[modified from: realpython.com/python-concurrency](https://realpython.com/python-concurrency/)

### 1. 協作式多任務處理　Cooperative Multitasking
Cooperative Multitasking 是一種多任務處理策略，其中每個程序**process自主管理**其對CPU的使用。在這種模式下，一個process一旦開始執行，它將繼續運行，直到它**主動選擇釋放**CPU。這通常發生在process等待外部輸入/輸出（例如，讀取文件或網路通信）或者process自願給其他process使用CPU的時候

### 2. 搶占式多任務處理　Pre-emptive Multitasking
相對的，Pre-emptive Multitasking 是由**作業系統控制**的，它分配給每個process一個固定的執行時間（稱為時間片Time slice）。當一個process的時間片用完時，作業系統會中斷該進程，保存其當前狀態，並將CPU控制權轉移給下一個process。

## 並行性的類型 Concurrency Type
並非所有演算法都能充分利用並行性
### 簡單並行 Trivial concurrency:
* 由相互獨立的活動組成
* 不共享資料
* 例如：同時處理多個用戶端的網路伺服器

### 共用資料並行 Shared data concurrency:
- 軟體通常有三個步驟：輸入、計算、輸出
- 拆分計算部分意味著需要在在輸入和輸出階段需要協調
- 可能需要計算節點之間的協調

## 並行性的組件 Concurrency Component

| 組件 | 功能 | 例子 | 挑戰 |
|-----------|----------------------------------------------|----------------------------------------------|----------------------------------------------|
| 生產者<br>Producer | 生產數據 | 接收來自客戶端的請求<br>並將其放入一個隊列中 | 確保數據的安全生產和傳遞，<br>避免競爭條件或數據不一致 |
| 工作者<br>Worker | 計算數據 | 從隊列中取出請求，處理它們<br>（例如查詢數據庫或執行計算） | 從生產者處有效地獲取數據，並可能需要與其他工作者協同工作 |
| 消費者<br>Consumer | 消耗數據 | 將工作者處理的結果<br>發送回客戶端 | 確保從工作者處安全且正確地獲取和使用數據，並可能需要處理來自多個工作者的數據 |

[source: 2021。Jakob Jenkov。jenkov.com。The Producer Consumer Pattern](https://jenkov.com/tutorials/java-concurrency/producer-consumer.html)

### Concurrency Patterns
#### 多個工作者 N-Workers
* 生產者-工作者-消費者模型 (Producer-Worker-Consumer Model)：生產者讀取數據，將其交給工作者進行計算，然後消費者將結果寫回。
* 應用 (Application)：常用於大型圖像處理，其中圖像可以被分割並分別處理。
* 平行性 (Parallelism)：**工作者獨立操作**，由於他們不需要經常通信，因此提供了高度的平行性。
#### 生產者廣播 Producer Broadcast
* 所有工作者都看到所有數據，但可能不會操作所有數據，而是在數據暴露給它們時繼續工作。
#### 混合和匹配模式 Mix and Match
- 生產者可以廣播給工作者
- **工作者可以彼此通信**，並為消費者整合信息。

### Concurrency 系統的挑戰
- **執行協同 (Execution Co-ordination)**
如何確保process能夠同步並協調他們的執行。
* 示例情境：在圖像處理中，儘管工作者大多可以獨立工作，但在達到他們工作部分的邊界時，他們可能需要通信以避免計算不一致。
- **記憶體分配 (Memory Allocation)**
如何在多個process之間分配記憶體，這在Concurrency Programming中變得複雜
- **排程 (Scheduling)**
決定哪些進程何時處於活動狀態。
- 作業系統參與 (OS Involvement)：在大多數Concurrency Programming中，作業系統管理排程，但放棄控制可能並非總是理想的。
- **吞吐量(Throughput)**
* 目標 (Goal)：實現更高的吞吐量（每單位時間完成的工作量更多）通常是編寫Concurrency應用程式的目的
* 影響因素 (Influence Factors)：執行協同、記憶體分配和排程可以影響系統的吞吐量
* 微調 (Fine-Tuning)：可能需要調整這些因素的行為以實現速度提升
- **分配 (Distribution)**
如何對thread、process與機器上進行分配，需要管理系統上的任務和資源分配
- **死鎖 (Deadlocks)**
當兩個或更多組件互相等待對方時發生死鎖。如果 A 在等待 B 做某事，而 B 在等待 A 做某事，則永遠不會發生任何事情。
- **資源飢餓 (Resource Starvation)**
程式的不同組件可能會爭奪記憶體、磁碟空間或 CPU 存取權。

更多補充見[[python - speed up] 多執行緒(multi-threading)的基本概念](https://hackmd.io/@YungHuiHsu/r1C9Akpgp)

## Python中的Concurrency
### Python中提供concurrency（並行）功能的模組:
* `threading`(I/O-Bound 類型任務適用)
* `asyncio`(I/O-Bound 類型任務適用)
* `multiprocessing`(CPU-Bound 類型任務適用)
### Python GIL(Global Interpreter Lock)
* 互斥鎖 Mutex(thread lock)，確保一次只有一個thread控制直譯器
* 限制：這限制了多個執行序(multi-threaded)在 Python 內的操作方式。當程式的兩個並行部分同時操作時，會導致競爭條件 (race conditions)。
* 記憶體分配：如果在記憶體分配內部有這種競爭條件，將導致記憶體洩漏 (memory leaks)。GIL 是為了解決這個問題而引入的。

推薦閱讀：[2017。louie_lu。深入 GIL: 如何寫出快速且 thread-safe 的 Python - Grok the GIL: How to write fast and thread-safe Python](https://blog.louie.lu/2017/05/19/%E6%B7%B1%E5%85%A5-gil-%E5%A6%82%E4%BD%95%E5%AF%AB%E5%87%BA%E5%BF%AB%E9%80%9F%E4%B8%94-thread-safe-%E7%9A%84-python-grok-the-gil-how-to-write-fast-and-thread-safe-python/)

#### Python的C擴展語言的互動 Python interacts with C-extensions
- C-extensions：可以用 C 編寫代碼並將其插入到下面，然後讓 Python 調用它。這使 Python 變得強大，但也使記憶體分配變得具有挑戰性。
- Guido：只有在新程式碼不會降低單執行序程式的前提下才能移除 GIL
- CPython 和 PyPy 使用 GIL！Jython 和 IronPython 不使用 GIL

#### GIL 的未來和 PEP 554
- CPython支援子直譯器(Subinterpreters)，而每個子直譯器(Subinterpreters)都有自己的 GIL，因此C-extensions層級的程式碼能夠促進python的並行性
- 每個interpreters間彼此獨立
- PEP 554中提議在 Python 標準庫中公開這些直譯器。這不會修正目前的 GIL，但會給程式設計師提供更多的工具，允許他們繞過 GIL 工作。

## 使用Concurrency的時機
- Concurrency總是帶來額外的複雜性，並且常常會導致難以發現的錯誤。
- 在遇到已知的性能問題之前，暫緩添加Concurrency，然後再確定需要哪種Concurrency
> 過早的優化是一切程式設計問題的根源 - Donald Knuth
> Premature optimization is the root of all evil (or at least most of it) in programming. - Donald Knuth

- 決定優化程式後，下一步是確定瓶頸是CPU-bound的還是I/O-bound的

對於 I/O 綁定問題，Python 社區有一個普遍的經驗法則： “**可以用`asyncio`時就用 ，必要用`threading`'時就用** ”。

`asyncio`可以為這類程式提供最好的速度，但有時你需要一些關鍵 libraries ，但這些 libraries 可能還沒有被完整移植。

:warning: 記住，任何不向事件迴圈交出控制權的任務都會阻塞所有其他任務:warning:

## 結語
Python中提供concurrency（並行）功能的模組:
* `threading`(I/O-Bound 類型任務適用)
* `asyncio`(I/O-Bound 類型任務適用)
* `multiprocessing`(CPU-Bound 類型任務適用)
* `concurrent`: 提供`threading`與`multiprocessing`的高階API封裝

根據python [Concurrent Execution官方文件](https://docs.python.org/zh-tw/3/library/concurrency.html)提到:
:::info
- multiprocessing — Process-based parallelism
- `concurrent.futures.ProcessPoolExecutor` 提供了一個更高層級的介面用來將任務推送到背景程序(background process)而**不會阻塞**調用方程序(calling process)的執行。 與直接使用Pool介面相比，concurrent.futures API 能更好地允許將工作單元發往無需等待結果的下層進程池

- threading — Thread-based parallelism
- `concurrent.futures.ThreadPoolExecutor` 提供了一個高層級介面用來向背景執行序(background thread)推送任務而**不會阻塞**調用方執行序(calling thread)的執行，同時仍然能夠在需要時獲取任務的結果。
- `queue` 提供了一個線程安全的介面用來在運行中的執行序(threads)之間交換數據。
- `asyncio` 提供了一個替代方式用來實現任務層級(task level)的並行而不要求使用多個操作系統的執行序(operating system threads)。

詳細操作見[concurrent.futures — Launching parallel tasks](https://docs.python.org/3/library/concurrent.futures.html)一節說明
:::

## Reference
#### [2013。Rob Pike。Concurrency is not parallelism](https://go.dev/blog/waza-talk)

Concurrency是獨立執行計算的組合，且並行性(concurrency)$=!$平行性(parallelism)：
- Concurrency
- 是同時處理很多事情
- 指結構面的設計

- Parallelism
- 是同時做很多事情
- 指執行面
Concurrency提供了一種結構化解決問題的方法，該問題可能（但不一定）是可平行化的
> Concurrency is the composition of independently executing computations, and concurrency is not parallelism: concurrency is about dealing with lots of things at once but parallelism is about doing lots of things at once. Concurrency is about structure, parallelism is about execution, concurrency provides a way to structure a solution to solve a problem that may (but not necessarily) be parallelizable.

#### [Toward Concurrency](https://www.dropbox.com/scl/fi/lbkqb4ojo79sdyjzi35rg/Toward-Concurrency.paper?rlkey=eq5yqcva5v7u0x808xvo55f7n&dl=0)
#### [2016。OPASS'S BLOG。OPASS'S BLOG。Concurrency系列(一): 理解Concurrency之路](http://opass.logdown.com/tags/concurrency)

#### [2017。louie_lu。深入 GIL: 如何寫出快速且 thread-safe 的 Python - Grok the GIL: How to write fast and thread-safe Python](https://blog.louie.lu/2017/05/19/%E6%B7%B1%E5%85%A5-gil-%E5%A6%82%E4%BD%95%E5%AF%AB%E5%87%BA%E5%BF%AB%E9%80%9F%E4%B8%94-thread-safe-%E7%9A%84-python-grok-the-gil-how-to-write-fast-and-thread-safe-python/)

#### [2018。Shivprasad koirala。codeproject.com。Concurrency vs Parallelism](https://www.codeproject.com/Articles/1267757/Concurrency-vs-Parallelism)

| 主題 | Concurrency | Parallelism |
| --- | --- | --- |
| 基本定義 | 在同一核心上使用重疊或時間分片執行多個任務。 | 在不同的核心上執行多個任務。 |
| 目標 | 在不過度使用資源的情況下感覺到平行處理。 | 為了性能實現實際的平行處理。 |
| 觀點 | 軟體設計：以合作的方式組成獨立執行的計算。 | 硬體：平行執行計算。 |
| 資源利用 | 輕 | 重 |

#### [2019。Jim Anderson。realpython.com。Speed Up Your Python Program With Concurrency](https://realpython.com/python-concurrency/)

- [2020。Jahongir Rahmonov。realpython.com。PyPy: Faster Python With Minimal Effort](https://realpython.com/pypy-faster-python/)

#### [2023。sysprog。concurrency並行程式設計: 概念](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts)
> - ==Concurrency 指程式架構==，將程式拆開成多個可獨立運作的工作，像是驅動程式都可獨立運作，但不需要平行化。
> - ==Parallelism 則指程式執行==，同時執行多個程式。
>
> Concurrency 可能會用到 Parallelism，但不一定要用 Parallelism 才能實現 Concurrency。在 Concurrent 中，工作可拆分成「獨立執行」的部份，於是「可以」讓很多事情一起做，但「不一定」要真的同時做。但 Parallelism 著重規劃， 將能夠並行的程式，分配給不同硬體單元，使其同時執行。

#### [2023。Max行銷誌。【爬蟲進階】Concurrency Programming](https://www.maxlist.xyz/2020/04/09/concurrency-programming/)

#### Coroutine與 Async IO

comparison in concurrency and parallelism

> [velotio.com。Implementing Async Features in Python - A Step-by-step Guide](https://www.velotio.com/engineering-blog/async-features-in-python)
> Fig:- A comparison in concurrency and parallelism