Ko'p oqimlilik - Zamonaviy C++

Ikki oqim bir xil xotiraga bir vaqtda yozsa - natija aniqlanmagan. Bu bo'limda poygani ko'rsatamiz, keyin uni to'rt xil usulda yo'q qilamiz.

Birinchi oqim #

C++

#include <print>
#include <string>
#include <vector>
#include <thread>
#include <mutex>
#include <atomic>
#include <future>
#include <numeric>
#include <algorithm>
#include <chrono>

C++

long long qismYigindi(int boshi, int oxiri)
{
    long long jami = 0;
    for (int i = boshi; i <= oxiri; ++i) jami += i;
    return jami;
}

int main()
{
    std::println("Apparat qo'llab-quvvatlaydigan oqimlar:");
    unsigned yadro = std::thread::hardware_concurrency();
    std::println("  hardware_concurrency() > 0: {}", yadro > 0);

    std::println("");
    std::println("Bitta oqimda:");
    long long ketmaKet = qismYigindi(1, 1'000'000);
    std::println("  1..1000000 yig'indisi = {}", ketmaKet);

    std::println("");
    std::println("To'rt oqimda:");
    std::vector<long long> natijalar(4, 0);
    {
        std::vector<std::jthread> oqimlar;
        for (int i = 0; i < 4; ++i) {
            int boshi = i * 250'000 + 1;
            int oxiri = (i + 1) * 250'000;
            oqimlar.emplace_back([&natijalar, i, boshi, oxiri] {
                natijalar[static_cast<std::size_t>(i)] = qismYigindi(boshi, oxiri);
            });
        }
        // jthread destruktori join() ni O'ZI chaqiradi
    }

    long long parallel = std::accumulate(natijalar.begin(), natijalar.end(), 0LL);
    std::println("  yig'indi = {}", parallel);
    std::println("  bir xilmi: {}", parallel == ketmaKet);

    std::println("");
    std::println("Har bir bo'lak:");
    for (std::size_t i = 0; i < natijalar.size(); ++i) {
        std::println("  {}-oqim: {}", i, natijalar[i]);
    }

    return 0;
}

Natija

Apparat qo'llab-quvvatlaydigan oqimlar:
  hardware_concurrency() > 0: true

Bitta oqimda:
  1..1000000 yig'indisi = 500000500000

To'rt oqimda:
  yig'indi = 500000500000
  bir xilmi: true

Har bir bo'lak:
  0-oqim: 31250125000
  1-oqim: 93750125000
  2-oqim: 156250125000
  3-oqim: 218750125000

std::jthread - std::thread o'rniga

C++11 dagi std::thread da xavfli xususiyat bor: uni join() yoki detach() qilmasdan yo'q qilsangiz, destruktor std::terminate() chaqiradi - dastur darhol o'ladi.

KOD

{
    std::thread t{ish};
}                       // BOOM - terminate

C++20 dagi std::jthread esa destruktorida o'zi join() qiladi:

KOD

{
    std::jthread t{ish};
}                       // avtomatik join

Bu RAII ning yana bir namunasi (9-bo'lim).

jthread yana to'xtatish belgisini ham beradi:

KOD

std::jthread t{[](std::stop_token belgi) {
    while (!belgi.stop_requested()) { ... }
}};
t.request_stop();

Yangi kodda std::thread ni ishlatmang - jthread har jihatdan yaxshiroq.

Yuqoridagi misolda har bir oqim natijalar ning o'z katakchasiga yozdi - shuning uchun poyga yo'q.

Ma'lumotlar poygasi #

C++

int main()
{
    constexpr int OQIM = 8;
    constexpr int TAKROR = 100'000;
    constexpr long long KUTILGAN = OQIM * TAKROR;

    std::println("Himoyasiz hisoblagich:");
    std::println("  {} oqim, har biri {} marta oshiradi", OQIM, TAKROR);
    std::println("  kutilgan natija: {}", KUTILGAN);
    std::println("");

    int yoqotishBorUrinishlar = 0;
    long long engKattaYoqotish = 0;

    for (int urinish = 0; urinish < 20; ++urinish) {
        long long hisoblagich = 0;          // HIMOYASIZ
        {
            std::vector<std::jthread> oqimlar;
            for (int i = 0; i < OQIM; ++i) {
                oqimlar.emplace_back([&hisoblagich] {
                    for (int k = 0; k < TAKROR; ++k) ++hisoblagich;
                });
            }
        }
        long long yoqotish = KUTILGAN - hisoblagich;
        if (yoqotish > 0) ++yoqotishBorUrinishlar;
        engKattaYoqotish = std::max(engKattaYoqotish, yoqotish);
    }

    std::println("20 urinishdan:");
    std::println("  yo'qotish bo'lgan urinishlar bormi: {}",
                 yoqotishBorUrinishlar > 0);
    std::println("  yo'qotish sezilarli edimi: {}",
                 engKattaYoqotish > TAKROR);

    std::println("");
    std::println("Natija HAR SAFAR boshqacha - va u hech qachon");
    std::println("kutilgandan katta bo'lmaydi, faqat kichik.");

    return 0;
}

Natija

Himoyasiz hisoblagich:
  8 oqim, har biri 100000 marta oshiradi
  kutilgan natija: 800000

20 urinishdan:
  yo'qotish bo'lgan urinishlar bormi: true
  yo'qotish sezilarli edimi: true

Natija HAR SAFAR boshqacha - va u hech qachon
kutilgandan katta bo'lmaydi, faqat kichik.

++hisoblagich - bu bitta amal emas

Mashina darajasida ++x uch qadamdan iborat:

Qadam	Amal
1	Xotiradan registrga o'qish
2	Registrni oshirish
3	Registrni xotiraga yozish

Ikki oqim bir vaqtda bajarsa:

KOD

Oqim A: o'qidi 100
Oqim B: o'qidi 100
Oqim A: oshirdi -> 101, yozdi
Oqim B: oshirdi -> 101, yozdi

Ikki oshirish qilindi, lekin qiymat faqat bir marta oshdi. Bitta oshirish yo'qoldi.

Bu C++ standarti bo'yicha shunchaki noto'g'ri natija emas - bu aniqlanmagan xatti-harakat. Kompilyator bunday kodni ko'rganda ixtiyoriy narsa qilishi mumkin, jumladan tsiklni butunlay optimallashtirib tashlash.

Ma'lumotlar poygasining ta'rifi:

Shart	Izoh
Ikki oqim bir xotiraga kiradi	Ha
Kamida bittasi yozadi	Ha
Sinxronizatsiya yo'q	Ha

Uchchalasi bir vaqtda bo'lsa - poyga. Faqat o'qish xavfsiz.

`std::mutex` #

C++

int main()
{
    constexpr int OQIM = 8;
    constexpr int TAKROR = 100'000;
    constexpr long long KUTILGAN = OQIM * TAKROR;

    long long hisoblagich = 0;
    std::mutex qulf;

    {
        std::vector<std::jthread> oqimlar;
        for (int i = 0; i < OQIM; ++i) {
            oqimlar.emplace_back([&hisoblagich, &qulf] {
                for (int k = 0; k < TAKROR; ++k) {
                    std::lock_guard himoya{qulf};
                    ++hisoblagich;
                }
            });
        }
    }

    std::println("mutex bilan:");
    std::println("  natija:   {}", hisoblagich);
    std::println("  kutilgan: {}", KUTILGAN);
    std::println("  to'g'rimi: {}", hisoblagich == KUTILGAN);

    std::println("");
    std::println("Yaxshiroq: qulflashni tsikldan CHIQARISH");

    long long ikkinchi = 0;
    {
        std::vector<std::jthread> oqimlar;
        for (int i = 0; i < OQIM; ++i) {
            oqimlar.emplace_back([&ikkinchi, &qulf] {
                long long mahalliy = 0;              // qulfsiz ishlaymiz
                for (int k = 0; k < TAKROR; ++k) ++mahalliy;

                std::lock_guard himoya{qulf};        // faqat bir marta qulf
                ikkinchi += mahalliy;
            });
        }
    }

    std::println("  natija:   {}", ikkinchi);
    std::println("  to'g'rimi: {}", ikkinchi == KUTILGAN);
    std::println("");
    std::println("Birinchi variant {} marta qulfladi.", KUTILGAN);
    std::println("Ikkinchisi atigi {} marta.", OQIM);

    return 0;
}

Natija

mutex bilan:
  natija:   800000
  kutilgan: 800000
  to'g'rimi: true

Yaxshiroq: qulflashni tsikldan CHIQARISH
  natija:   800000
  to'g'rimi: true

Birinchi variant 800000 marta qulfladi.
Ikkinchisi atigi 8 marta.

Mutexni hech qachon qo'lda qulflamang

KOD

qulf.lock();
ishla();               // istisno tashlasa - QULF OCHILMAYDI
qulf.unlock();

Bu boshi berk ko'chaga olib keladi: keyingi oqim abadiy kutadi.

RAII o'ramlaridan foydalaning:

O'ram	Qachon
`std::lock_guard`	Oddiy holat, eng tez
`std::unique_lock`	Ochish/qulflash kerak, `condition_variable`
`std::scoped_lock`	Bir nechta mutex birga
`std::shared_lock`	O'qish uchun (`shared_mutex` bilan)

std::scoped_lock ikki mutexni boshi berk ko'chasiz qulflaydi:

KOD

std::scoped_lock ikkalasi{qulf1, qulf2};

Qo'lda qulf1.lock(); qulf2.lock(); yozsangiz va boshqa oqim teskari tartibda qulflasa - ikkalasi ham abadiy kutadi.

Poygani yo'q qilishning to'rt yo'li - eng yaxshisi umumiy holatdan qochish

`std::atomic` #

C++

int main()
{
    constexpr int OQIM = 8;
    constexpr int TAKROR = 100'000;
    constexpr long long KUTILGAN = OQIM * TAKROR;

    std::atomic<long long> hisoblagich{0};

    {
        std::vector<std::jthread> oqimlar;
        for (int i = 0; i < OQIM; ++i) {
            oqimlar.emplace_back([&hisoblagich] {
                for (int k = 0; k < TAKROR; ++k) ++hisoblagich;
            });
        }
    }

    std::println("atomic bilan:");
    std::println("  natija:    {}", hisoblagich.load());
    std::println("  to'g'rimi: {}", hisoblagich.load() == KUTILGAN);

    std::println("");
    std::println("Qulfsizmi (lock-free):");
    std::println("  atomic<int>       {}", std::atomic<int>{}.is_lock_free());
    std::println("  atomic<long long> {}", std::atomic<long long>{}.is_lock_free());
    std::println("  atomic<double>    {}", std::atomic<double>{}.is_lock_free());

    std::println("");
    std::println("Atom amallar:");
    std::atomic<int> q{10};
    std::println("  boshlang'ich:        {}", q.load());
    std::println("  fetch_add(5) qaytdi: {}", q.fetch_add(5));
    std::println("  endi:                {}", q.load());
    std::println("  exchange(100) qaytdi:{}", q.exchange(100));
    std::println("  endi:                {}", q.load());

    int kutilgan = 100;
    bool almashdi = q.compare_exchange_strong(kutilgan, 200);
    std::println("  compare_exchange:    almashdi={}, endi={}", almashdi, q.load());

    kutilgan = 100;                      // endi 200, mos kelmaydi
    almashdi = q.compare_exchange_strong(kutilgan, 300);
    std::println("  ikkinchi urinish:    almashdi={}, kutilgan endi={}",
                 almashdi, kutilgan);

    return 0;
}

Natija

atomic bilan:
  natija:    800000
  to'g'rimi: true

Qulfsizmi (lock-free):
  atomic<int>       true
  atomic<long long> true
  atomic<double>    true

Atom amallar:
  boshlang'ich:        10
  fetch_add(5) qaytdi: 10
  endi:                15
  exchange(100) qaytdi:15
  endi:                100
  compare_exchange:    almashdi=true, endi=200
  ikkinchi urinish:    almashdi=false, kutilgan endi=200

compare_exchange - qulfsiz algoritmlarning asosi

q.compare_exchange_strong(kutilgan, yangi) bitta bo'linmas amalda quyidagini bajaradi:

KOD

if (q == kutilgan) { q = yangi; return true; }
else               { kutilgan = q; return false; }

Muvaffaqiyatsiz bo'lganda kutilgan ga haqiqiy qiymat yoziladi - shuning uchun qayta urinish oson:

KOD

int eski = hisoblagich.load();
while (!hisoblagich.compare_exchange_weak(eski, eski * 2)) {
    // eski avtomatik yangilandi, qayta urinamiz
}

_weak versiya ba'zi platformalarda sababsiz ham muvaffaqiyatsiz bo'lishi mumkin, lekin tsiklda tezroq. Tsikl ichida _weak, tsiklsiz _strong ishlating.

atomic faqat kichik va trivial turlar uchun qulfsiz bo'ladi. std::atomic<std::string> yozish mumkin, lekin u ichida mutex ishlatadi.

`std::async` va `std::future` #

C++

long long ogirHisob(int n, int koeffitsient)
{
    long long jami = 0;
    for (int i = 1; i <= n; ++i) jami += static_cast<long long>(i) * koeffitsient;
    return jami;
}

int bolish(int a, int b)
{
    if (b == 0) throw std::runtime_error{"nolga bo'lish"};
    return a / b;
}

int main()
{
    std::println("Parallel vazifalar:");

    auto v1 = std::async(std::launch::async, ogirHisob, 1'000'000, 1);
    auto v2 = std::async(std::launch::async, ogirHisob, 1'000'000, 2);
    auto v3 = std::async(std::launch::async, ogirHisob, 1'000'000, 3);

    // get() natija tayyor bo'lgunicha kutadi
    std::println("  1-vazifa: {}", v1.get());
    std::println("  2-vazifa: {}", v2.get());
    std::println("  3-vazifa: {}", v3.get());

    std::println("");
    std::println("Istisno OQIM ORQALI uzatiladi:");

    auto yaxshi = std::async(std::launch::async, bolish, 100, 4);
    auto yomon  = std::async(std::launch::async, bolish, 100, 0);

    std::println("  100/4 = {}", yaxshi.get());

    try {
        std::println("  100/0 = {}", yomon.get());
    } catch (const std::runtime_error& x) {
        std::println("  100/0 -> tutildi: {}", x.what());
    }

    std::println("");
    std::println("Ko'p vazifani birga kutish:");
    std::vector<std::future<long long>> vazifalar;
    for (int k = 1; k <= 5; ++k) {
        vazifalar.push_back(std::async(std::launch::async, ogirHisob, 100'000, k));
    }

    long long jami = 0;
    for (auto& v : vazifalar) jami += v.get();
    std::println("  beshta vazifa yig'indisi: {}", jami);

    return 0;
}

Natija

Parallel vazifalar:
  1-vazifa: 500000500000
  2-vazifa: 1000001000000
  3-vazifa: 1500001500000

Istisno OQIM ORQALI uzatiladi:
  100/4 = 25
  100/0 -> tutildi: nolga bo'lish

Ko'p vazifani birga kutish:
  beshta vazifa yig'indisi: 75000750000

std::async - eng xavfsiz boshlanish nuqtasi

async uch narsani birdan hal qiladi:

Muammo	Yechim
Natijani qaytarish	`future::get()`
Istisnoni uzatish	`get()` uni qayta tashlaydi
Oqim hayoti	`future` destruktori kutadi

Umumiy o'zgaruvchi umuman kerak emas - shuning uchun poyga ham yo'q.

Muhim tuzoq: std::launch::async ni oshkora yozing:

KOD

auto v = std::async(ish);                        // ishga tushmasligi mumkin
auto v = std::async(std::launch::async, ish);    // ALBATTA yangi oqimda

Birinchi shaklda amalga oshirish std::launch::deferred ni tanlashi mumkin - vazifa get() chaqirilgunicha umuman bajarilmaydi va hech qanday parallellik bo'lmaydi.

Ikkinchi tuzoq:

KOD

std::async(std::launch::async, ish);      // future darhol yo'q qilinadi

Natijani o'zgaruvchiga saqlamasangiz, vaqtinchalik future shu qatorda yo'q qilinadi va destruktori vazifa tugashini kutadi - ya'ni kod ketma-ket bajariladi.

Amaliy misol: parallel qidiruv #

C++

std::vector<int> katta;

std::size_t sanoq(std::size_t boshi, std::size_t oxiri, int qidirilayotgan)
{
    std::size_t topildi = 0;
    for (std::size_t i = boshi; i < oxiri; ++i) {
        if (katta[i] == qidirilayotgan) ++topildi;
    }
    return topildi;
}

int main()
{
    // Aniq ma'lumot - takrorlanadigan natija uchun
    katta.resize(4'000'000);
    for (std::size_t i = 0; i < katta.size(); ++i) {
        katta[i] = static_cast<int>(i % 100);
    }

    std::println("massiv: {} element, qiymatlar 0..99", katta.size());
    std::println("");

    constexpr int OQIM = 4;
    const int qidirilayotgan = 42;

    std::vector<std::future<std::size_t>> vazifalar;
    std::size_t bolak = katta.size() / OQIM;

    for (int i = 0; i < OQIM; ++i) {
        std::size_t boshi = static_cast<std::size_t>(i) * bolak;
        std::size_t oxiri = (i == OQIM - 1) ? katta.size() : boshi + bolak;
        vazifalar.push_back(
            std::async(std::launch::async, sanoq, boshi, oxiri, qidirilayotgan));
    }

    std::size_t jami = 0;
    for (std::size_t i = 0; i < vazifalar.size(); ++i) {
        std::size_t n = vazifalar[i].get();
        std::println("  {}-bo'lak: {} ta", i, n);
        jami += n;
    }

    std::println("");
    std::println("parallel natija:   {}", jami);

    std::size_t ketmaKet = sanoq(0, katta.size(), qidirilayotgan);
    std::println("ketma-ket natija:  {}", ketmaKet);
    std::println("bir xilmi:         {}", jami == ketmaKet);

    std::println("");
    std::println("Bu yerda umumiy YOZUV yo'q - faqat o'qish.");
    std::println("Shuning uchun mutex ham, atomic ham kerak emas.");

    return 0;
}

Natija

massiv: 4000000 element, qiymatlar 0..99

  0-bo'lak: 10000 ta
  1-bo'lak: 10000 ta
  2-bo'lak: 10000 ta
  3-bo'lak: 10000 ta

parallel natija:   40000
ketma-ket natija:  40000
bir xilmi:         true

Bu yerda umumiy YOZUV yo'q - faqat o'qish.
Shuning uchun mutex ham, atomic ham kerak emas.

Parallellik har doim tezlatmaydi

Parallel kod uch xarajat keltiradi:

Xarajat	Izoh
Oqim yaratish	Mikrosoniyalar, lekin nolga teng emas
Sinxronizatsiya	Har qulf - kutish
Kesh nizosi	Bir kesh qatoriga yozish - "false sharing"

Kichik vazifada bu xarajatlar foydadan katta bo'ladi. Amaliy chegara: vazifa kamida bir necha yuz mikrosoniya davom etsin.

Amdal qonuni ham eslatib turadi: agar dasturning 20% i ketma-ket bo'lsa, cheksiz yadro bilan ham eng ko'pi bilan 5 barobar tezlashadi.

Va eng muhimi: avval to'g'ri ishlasin, keyin tez. Poygali tez kod - foydasiz kod.

Sinov vositalari:

KOD

g++ -fsanitize=thread -g dastur.cpp
g++ -fsanitize=address -g dastur.cpp

ThreadSanitizer poygani u sodir bo'lmagan bo'lsa ham topa oladi - chunki u kirish naqshini tahlil qiladi, natijani emas.

Amaliy topshiriq

std::jthread bilan oqim yarating va destruktori join qilishini tekshiring.
Himoyasiz hisoblagichni 8 oqimda oshiring - natija to'g'rimi?
Xuddi shu kodni bir necha marta ishga tushiring - natija bir xilmi?
std::lock_guard bilan himoyalang.
Qulflashni tsikldan chiqarib mahalliy yig'indi ishlating.
std::atomic<long long> bilan qayta yozing.
is_lock_free() ni turli turlar uchun tekshiring.
fetch_add va exchange nima qaytarishini kuzating.
std::async bilan istisno tashlaydigan vazifa yarating va get() da tuting.
std::launch::async ni olib tashlang - parallellik saqlanib qoldimi?

Xulosa #

std::jthread destruktorida o'zi join() qiladi - std::thread esa terminate chaqiradi.
++x uch qadamdan iborat - shuning uchun himoyasiz oshirish poyga.
Poyga uchta shart bilan aniqlanadi: bir xotira, kamida bitta yozuv, sinxronizatsiya yo'q.
Poyga - noto'g'ri natija emas, aniqlanmagan xatti-harakat.
Mutexni qo'lda qulflamang - lock_guard, unique_lock yoki scoped_lock ishlating.
Bir necha mutexni birga qulflash uchun scoped_lock - boshi berk ko'chasiz.
Qulflashni tsikldan chiqaring: mahalliy yig'indi, oxirida bitta qulf.
std::atomic bitta o'zgaruvchi uchun mutexdan ancha tez.
compare_exchange qulfsiz algoritmlarning asosi; tsiklda _weak ishlating.
std::async natija, istisno va oqim hayotini birdan hal qiladi.
std::launch::async ni oshkora yozing, aks holda parallellik bo'lmasligi mumkin.
Eng yaxshi yechim - umumiy holatdan butunlay qochish.

Keyingi bo'limda aniqlanmagan xatti-harakat va sanitayzerlar bilan tanishamiz.

Birinchi oqim #

Ma'lumotlar poygasi #

std::mutex #

std::atomic #

std::async va std::future #

Amaliy misol: parallel qidiruv #

Xulosa #

Xatolik topdingizmi?

`std::mutex` #

`std::atomic` #

`std::async` va `std::future` #