場景：MD5 暴力破解
- 字符集：26 個小寫字母
- 長度：1~8 位
- 總組合數：Σ 26^i (i=1..8) ≈ 2171 億
- 目標：利用多核 CPU 縮短破解時間
四種方案對比
| 方案 | 描述 | 同步機制 | 優點 | 缺點 |
|---|
| 1. 共享單一生成器 | 多線程輪流取下一個候選串 | Mutex / Interlocked | 候選序列連續 | 鎖爭用極大，4 線程比單線程慢 8 倍 |
| 2. 靜態均分任務 | 啟動前將空間均分 N 份 | 無 | 無同步開銷 | 負載不均，代碼難復用 |
| 3. 固定大小任務包 | 預切分任務包，線程動態領取 | 領取時互斥 | 負載較均 | 需調優包大小，邏輯複雜 |
| 4. 動態任務竊取 (採用) | 線程按需從全局隊列取固定批次 | 原子隊列操作 | 負載自動均衡、邏輯簡潔、高復用 | 批次大小需調優 |
方案 4 核心設計
// 全局任務隊列 (環形緩衝區 + 原子索引)
typedef struct { uint64_t start, end; } Task;
Task task_queue[TASK_QUEUE_SIZE];
atomic_size_t head = 0, tail = 0;
// 生產者：主線程按批次切分總空間入隊
void producer(uint64_t total, uint64_t batch) {
for (uint64_t s = 0; s < total; s += batch) {
uint64_t e = min(s + batch, total);
size_t idx = atomic_fetch_add(&tail, 1) % TASK_QUEUE_SIZE;
task_queue[idx] = (Task){s, e};
}
}
// 消費者：工作線程循環取任務
void *worker(void *arg) {
Task t;
while (1) {
size_t h = atomic_load(&head);
size_t t_idx = atomic_load(&tail);
if (h == t_idx) break; // 隊列空
if (atomic_compare_exchange_weak(&head, &h, (h + 1) % TASK_QUEUE_SIZE)) {
t = task_queue[h];
crack_range(t.start, t.end); // 核心破解邏輯
}
}
return NULL;
}
關鍵優化點
- 批次大小：太小 → 原子操作開銷大；太大 → 負載不均。經驗值：
總空間 / (核心數 * 100)
- 無鎖隊列：C11
atomic_* 或 GCC 内建 __sync_*，避免 Mutex 內核切換
- 仿射變換生成候選：將線性索引
0..N-1 映射為字符串，無需字串操作，純整數運算
- 早期退出：找到密碼設置全局標誌，其他線程檢測後退出
- CPU 親和性：
pthread_setaffinity_np 綁核，減少緩存失效
實測數據 (4 核 3.4GHz)
