C++ Programlama Dili: C++26 Kapsayıcı Tarama Uzantısı

Duyuru

Kapsayıcı tarama, bir dizideki bir dizi öğenin toplamını hesaplamak gibi aralık sorgularıyla ilgili sorunları çözer. Ayrıca minimum aralık sorgularında ve diğer çeşitli algoritmalarda da kullanılır.

Noel özel

Fark yarat

Birlikte harika bir şey yaratalım: 1-24 Aralık tarihleri ​​arasında mentorluk programlarımdan birine kayıt yaptırırsanız paranın yarısını ALS araştırmasına bağışlayacağım.

Şu ana kadar neler başardığımızı görebilmemiz için her hafta bir güncelleme yayınlayacağım.

Burada benimle ilgili daha fazla bilgiyi, mentorluk programlarımın yapısını ve bireysel programları bulabilirsiniz:

Siz veya ekibiniz mentorluk programımdan özel bir seçim yapmak istiyorsanız lütfen benimle [email protected] adresinden iletişime geçin. Bir çözüm bulacağız.

Neden?

İşte ALS kliniğinden yapılan açıklama:

ALS, toplumun ilgi odağı olmayan nadir hastalıklardan biri olan “tıbbın yetimlerinden” biridir. Tedavi önemli ölçüde yetersiz finanse ediliyor ve şu anda ALS araştırması için yeterli finansman yok. Bağışlar ve diğer üçüncü taraf fonları kritik öneme sahiptir.

Bu yetersiz finansman Buz Kovası Mücadelesi ile açıkça ortaya çıktı.

Araştırmanın daha fazla paraya ihtiyacı var.

Ön ekin toplamı

Asenkron kapsayıcı taramadan bahsetmeden önce önek toplamı olarak da bilinen kapsayıcı taramayı tanıtmak istiyorum.

İngilizce Vikipedi'de şu tanım bulunur: “Bilgisayar biliminde, önek toplamı, kümülatif toplam, kapsayıcı tarama veya basitçe bir dizi x'in taranması₀X₁X₂… y sayılarının ikinci dizisidir₀Evet₁Evet₂…, giriş sırasının öneklerinin (alt toplamları) toplamları:”

    y0 = x0
    y1 = x0 + x1
    y2 = x0 + x1+ x2
    ...

Önerilen P2300R10, Kapsamlı Taramanın uygulanmasını sunar.

using namespace std::execution;

sender auto async_inclusive_scan(scheduler auto sch,                          // 2
                                 std::span<const double> input,               // 1
                                 std::span<double> output,                    // 1
                                 double init,                                 // 1
                                 std::size_t tile_count)                      // 3
{
  std::size_t const tile_size = (input.size() + tile_count - 1) / tile_count;

  std::vector<double> partials(tile_count + 1);                               // 4
  partials[0] = init;                                                         // 4

  return just(std::move(partials))                                            // 5
       | continues_on(sch)
       | bulk(tile_count,                                                     // 6
           [ = ](std::size_t i, std::vector<double>& partials) {              // 7
             auto start = i * tile_size;                                      // 8
             auto end   = std::min(input.size(), (i + 1) * tile_size);        // 8
             partials[i + 1] = *--std::inclusive_scan(begin(input) + start,   // 9
                                                      begin(input) + end,     // 9
                                                      begin(output) + start); // 9
           })                                                                 // 10
       | then(                                                                // 11
           [](std::vector<double>&& partials) {
             std::inclusive_scan(begin(partials), end(partials),              // 12
                                 begin(partials));                            // 12
             return std::move(partials);                                      // 13
           })
       | bulk(tile_count,                                                     // 14
           [ = ](std::size_t i, std::vector<double>& partials) {              // 14
             auto start = i * tile_size;                                      // 14
             auto end   = std::min(input.size(), (i + 1) * tile_size);        // 14
             std::for_each(begin(output) + start, begin(output) + end,        // 14
               [&] (double& e) { e = partials[i] + e; }                       // 14
             );
           })
       | then(                                                                // 15
           [ = ](std::vector<double>&& partials) {                            // 15
             return output;                                                   // 15
           });                                                                // 15
}

P2300R10 teklifinin Almancaya çevrilmiş açıklaması burada.

1. İşlev bir diziyi tarar doubles (olarak temsil edilir) std::span<const double> input) ve sonucu başka bir diziye kaydedin doubles (olarak temsil edilir) std::span<double> output).
2. Taramanın hangi yürütme kaynağında başlatılacağını belirten bir zamanlayıcı kullanılır.
3. Ayrıca bir tane olacak tile_count-Oluşturulan yürütülebilir aracıların sayısını kontrol eden parametre kullanılır.
4. Öncelikle algoritma için gereken geçici belleği ayırmamız gerekiyor, bunu bir std::vector, partials tamamlamak. Oluşturduğumuz her yürütme aracısı için çift geçici depolamaya ihtiyacımız var.
5. Daha sonra ilk vericimizi oluşturacağız. execution::just VE execution::continues_on. Bu vericiler, vericiye taşıdığımız geçici hafızayı iletir. Vericinin bir tamamlanma programı vardır: schyani zincirdeki bir sonraki eleman sch kullanılmış.
6. Verici ve verici adaptörü aramayı destekler operator|C++ alanlarına benzer. hadi kullanalım operator |bir sonraki işi eklemek için, bu işi tile_count-İcra aracılarının kullanılması execution::bulkoluşturulur.
7. Her temsilci birini arar std::invocable ve ona iki argüman sunuyor. Birincisi aracı endeksidir (i) içinde execution::bulkişlem, bu durumda benzersiz bir tamsayı [0, tile_count). Das zweite Argument ist, wie der Eingabesender gesendet hat – der temporäre Speicher.
8. Wir beginnen mit der Berechnung von Anfang und Ende des Bereichs der Eingabe- und Ausgabeelemente, für die dieser Agent verantwortlich ist, basierend auf unserem Agentenindex.
9. Dann führen wir einen sequenziellen std::inclusive_scan über unsere Elemente durch. Wir speichern das Scan-Ergebnis für unser letztes Element, das die Summe aller unserer Elemente ist, in unserem temporären Speicher “partials“.
10. Nachdem alle Berechnungen in diesem ersten Durchlauf in großen Mengen abgeschlossen sind, hat jeder der erzeugten Ausführungsagenten die Summe seiner Elemente in seinen Slot in Teilmengen geschrieben.
11. Jetzt müssen wir alle Werte in Teilmengen scannen. Das machen wir mit einem einzelnen Ausführungsagenten, der nach Abschluss von execution::bulk ausgeführt wird. Wir erstellen diesen Ausführungsagenten mit execution::then.
12. execution::then nimmt einen Eingabesender und ein std::invocable und ruft das std::invocable mit dem vom Eingabesender gesendeten Wert auf. Innerhalb unseres std::invocable rufen wir std::inclusive_scan für Teilmengen auf, die die Eingabesender an uns senden werden.
13. Dann geben wir Teilmengen zurück, die in der nächsten Phase benötigt werden.
14. Schließlich führen wir eine weitere execution::bulk in der gleichen Form wie zuvor durch. In dieser execution::bulk verwenden wir die gescannten Werte in Teilbereichen, um die Summen aus anderen Kacheln in unsere Elemente zu integrieren und den inklusiven Scan abzuschließen.
15. async_inclusive_scan gibt einen Sender zurück, der die Ausgabe std::span<double> sendet. Ein Verbraucher des Algorithmus kann zusätzliche Arbeit verketten, die das Scan-Ergebnis verwendet. Zu dem Zeitpunkt, an dem async_inclusive_scan zurückgegeben wird, ist die Berechnung möglicherweise noch nicht abgeschlossen. Tatsächlich hat sie möglicherweise noch nicht einmal begonnen.

Sender

• just(values): Gibt einen Sender ohne Abschlussplaner zurück, der die bereitgestellten Werte sendet. just ist eine Senderfabrik.
• bulk(input, shape, call): Gibt einen Sender zurück, der den aufrufbaren call beschreibt, der auf input gemäß shape aufgerufen wird.
• continues_on(input, scheduler): Gibt einen Sender zurück, der den Übergang vom Ausführungsagenten des Senders für die Eingabe zum Ausführungsagenten des Ziel-schedulers beschreibt.
• then(input, call): then gibt einen Sender zurück, der die Fortsetzung der Task des Senders für die Eingabe auf einem hinzugefügten Knoten des Aufrufs der bereitgestellten Funktion call beschreibt.

Wäre es nicht schön, dieses Programm in Aktion zu sehen? Derzeit (Dezember 2024) unterstützt kein Compiler std::execution oder die Concepts sender und scheduler.

Hier hilft die Referenzimplementierung stdexec, wobei ich den Datentyp der verarbeiteten Elemente von double in int geändert habe:

// inclusiveScanExecution.cpp

#include <algorithm>
#include <exec/static_thread_pool.hpp>
#include <iostream>
#include <numeric>
#include <span>
#include <stdexec/execution.hpp>
#include <vector>

auto async_inclusive_scan(auto sch,                   // 2
                          std::span<const int> input, // 1
                          std::span<int> output,      // 1
                          int init,                   // 1
                          std::size_t tile_count)     // 3
{
  std::size_t const tile_size = (input.size() + tile_count - 1) / tile_count;

  std::vector<int> partials(tile_count + 1); // 4
  partials[0] = başlangıç; // 4 dönüş stdexec::just(std::move(partials)) // 5 | stdexec::continues_on(sch) | stdexec::bulk(tile_count, // 6
                       [=](std::size_t i, std::vector &kısmi) { // 7 otomatik başlatma = i *tile_size; // 8 otomatik bitiş = std::min(input.size(), (i + 1) *tile_size); // 8 kısmi[i + 1] = *--std::clusive_scan(başlangıç(giriş) + başlangıç, // 9 başlangıç(giriş) + bitiş, // 9 başlangıç(çıkış) + başlangıç); // 9 }) // 10 | stdexec::sonra( // 11
               [](std::vektör &&partials) { std::clusive_scan(begin(partials), end(partials), // 12 Begin(partials)); // 12 return std::move(partials); // 13 }) | stdexec::bulk(tile_count, // 14
             [=](std::size_t i, std::vector &kısmi) { // 14 otomatik başlatma = i *tile_size; // 14 otomatik bitiş = std::min(input.size(), (i + 1) *tile_size); // 14 std::her_için(başlangıç(çıkış) + başlangıç, başlangıç(çıkış) + bitiş, // 14
                             [&](int &e) { e = kısmi[i] +e; } // 14); }) | stdexec::sonra( // 15
             [=](std::vektör &&partials) { // 15 çıktıyı döndürür; // 15}); // 15 } int main() { std::cout << 'n'; std::vektör girdi(30); std::iota(başlangıç(giriş), bitiş(giriş), 0); for (auto e: giriş) { std::cout << e << ' '; } std::cout << 'n'; std::vektör çıktı(input.size()); exec::static_thread_pool(8); autosch = havuz.get_scheduler(); araba [out] = stdexec::sync_wait(async_clude_scan(sch, giriş, çıkış, 0, 4)) .value(); for (auto e: out) { std::cout << e << ' '; } std::cout << 'n'; }

İçinde main bir tane olacak std::vector<int> 30 öğeyle oluşturulan giriş. THE std::iota-Fonksiyon şunu doldurur: input- ile başlayan ardışık tam sayıları içeren vektör 0. Program daha sonra vektörün içeriğini konsola yazdırır.

Bir sonraki şu saatte olacak: std::vector<int> output bununla aynı boyutta input-Kapsayıcı tarama işleminin sonuçlarını depolamak için oluşturulan vektör. THE exec::static_thread_pool pool görevleri aynı anda yürütmek için kullanılan iş parçacıklarına sahiptir. THE get_scheduler-İş parçacığı havuzu üye işlevi bir zamanlayıcı nesnesi oluşturur sch.

fonksiyon async_inclusive_scan zamanlayıcıyı kullan schvektör inputvektör outputbaşlangıç ​​değeri 0 ve bir karo sayısı 4. Bu işlev, belirtilen zamanlayıcıyı kullanarak kapsayıcı tarama işlemini eşzamansız olarak gerçekleştirir ve Gelecek türünde bir nesne döndürür. fonksiyon stdexec::sync_wait eşzamanlı olarak işlemin tamamlanmasını bekler async_inclusive_scanişlem yapılır ve sonuç değişkene eklenir out ambalajından çıkarıldı.

Son olarak program vektörün içeriğini döndürür out konsolda:

Bir sonraki adım nedir?

Bir sonraki blog yazımda bir adım geriye giderek operatörü kullanan istasyonların yapısına bakacağım. | açıklamak.

(Ben)