C ++ 26: Bloklar olmadan yığın için basit bir çöp manifoldu
Son üç makalede, yığın konusunu bloklar olmadan ele aldım:
Duyuru
Rainer Grimm yıllardır yazılım mimarı, ekip ve eğitim müdürü olarak çalıştı. C ++ programlama dilleri, Python ve Haskell hakkında makaleler yazmayı seviyor, ancak uzman konferanslarla konuşmayı da seviyor. Modern C ++ blogunda, C ++ tutkusuyla yoğun bir şekilde ilgileniyor.
Bu yazı için basit bir çöp koleksiyoncusu ile genişletiyorum.
Birden fazla eşzamanlı olarak yürütüldüğünü tartıştım topAndPush-Call bir yarış koşuludur. Birden fazla değilse bir düğümü güvenle ortadan kaldırabilirim topAndPush-Call eşzamanlı olarak gerçekleştirilir. Bu gözlem, bellek kaybı problemini çözmek için çok önemlidir: Bir listedeki uzak düğümler hariç, birden fazla olmasa da, bu listedeki düğümleri silecek ve silinecek topAndPush-Chiamare aktif. Tek bir meydan okuma var: başka hiçbir şeyin olmadığından nasıl emin olabilirim topAndPush-Bling aktif mi? Başında bir atom sayacı kullanıyorum topAndPush Sonunda arttı ve azaldı. Sayaç sıfır veya değilse bir topAndPush-Chiamare aktif.
Aşağıdaki program sunulan stratejiyi uygular. Dosyayı kullanıyorum lockFreeStackWithLeaks.cpp Başlangıç noktası olarak “C ++ 26: Bloklar Olmayan Bir Yığının Tamamen Uygulanması” makalesinden.
// lockFreeStackWithGarbageCollection.cpp
#include <atomic>
#include <future>
#include <iostream>
#include <stdexcept>
#include <thread>
template<typename T>
class LockFreeStack {
private:
struct Node {
T data;
Node* next;
Node(T d): data(d), next(nullptr){ }
};
std::atomic<Node*> head{nullptr};
std::atomic<int> topAndPopCounter{}; // 1
std::atomic<Node*> toBeDeletedNodes{nullptr}; // 2
void tryToDelete(Node* oldHead) { // 3
if (topAndPopCounter == 1) { // 6
Node* copyOfToBeDeletedNodes = toBeDeletedNodes.exchange(nullptr); // 8
if (topAndPopCounter == 1) deleteAllNodes(copyOfToBeDeletedNodes); // 9
else addNodeToBeDeletedNodes(copyOfToBeDeletedNodes);
delete oldHead;
}
else addNodeToBeDeletedNodes(oldHead); // 7
}
void addNodeToBeDeletedNodes(Node* oldHead) {
oldHead->next = toBeDeletedNodes;
while( !toBeDeletedNodes.compare_exchange_strong(oldHead->next, oldHead) ); // 10
}
void deleteAllNodes(Node* currentNode) { // 4
while (currentNode) {
Node* nextNode = currentNode->next;
delete currentNode;
currentNode = nextNode;
}
}
public:
LockFreeStack() = default;
LockFreeStack(const LockFreeStack&) = delete;
LockFreeStack& operator= (const LockFreeStack&) = delete;
void push(T val) {
Node* const newNode = new Node(val);
newNode->next = head.load();
while( !head.compare_exchange_strong(newNode->next, newNode) );
}
T topAndPop() {
++topAndPopCounter;
Node* oldHead = head.load();
while( oldHead && !head.compare_exchange_strong(oldHead, oldHead->next) ) {
if ( !oldHead ) throw std:
ut_of_range("The stack is empty!");
}
auto topElement = oldHead->data;
tryToDelete(oldHead); // 5
--topAndPopCounter;
return topElement;
}
};
int main(){
LockFreeStack<int> lockFreeStack;
auto fut = std::async([&lockFreeStack]{ lockFreeStack.push(2011); });
auto fut1 = std::async([&lockFreeStack]{ lockFreeStack.push(2014); });
auto fut2 = std::async([&lockFreeStack]{ lockFreeStack.push(2017); });
auto fut3 = std::async([&lockFreeStack]{ return lockFreeStack.topAndPop(); });
auto fut4 = std::async([&lockFreeStack]{ return lockFreeStack.topAndPop(); });
auto fut5 = std::async([&lockFreeStack]{ return lockFreeStack.topAndPop(); });
fut.get(), fut1.get(), fut2.get();
std::cout << fut3.get() << 'n';
std::cout << fut4.get() << 'n';
std::cout << fut5.get() << 'n';
}
Blokların olmayan yığın iki yeni özelliği ve üç yeni üyesi vardır. Atom sayacı topAndPopCounter Sayım (1) Aktif bileşenlerin sayısı topAndPop-Crepfen ve atom işaretçisi toBeDeletedNodes (2) Elimine edilecek düğümler listesindeki bir işaretçidir. Üye işlevi de dener tryToDelete (3), düğümleri çıkarın. Üye işlevi addNodeToBeDeletedNodes Silinecek düğüm listesine bir düğüm ve üyenin işlevi ekler deleteAllNodes (4) tüm düğümleri ortadan kaldırır.
Şimdi üyenin işlevini analiz edelim topAndPop. Başında ve sonunda topAndPop hale gelmek topAndPopCounter Artmış ve azaltılmış. oldHead Yığıntan çıkarılır ve bu nedenle nihayet hatırlanabilir Trytodelete (5) ortadan kaldırılacak. Üye işlevi tryToDelete Önce bir veya daha fazla topAndPop-Hias aktiftir. Eğer topAndPop-Aşetme aktif (6), oldHead silindi. Aksi takdirde olur oldHead Elimine edilecek öğelerin listesine eklendi (7). Sanırım sadece bir tane topAndPop-Chiamare aktif. Bu durumda yerel bir işaretçi oluşturuyorum copyOfToBeDeletedNodes Düğümlerde ortadan kaldırılacak ve toBeDeletedNodes-Birde nullptr (8). Düğümleri ortadan kaldırmadan önce, bu arada başka bir şey olup olmadığını kontrol edin topAndPop-Chiamare aktif. Mevcut olan topAndPop Yerel işaretçiyi kullanıyorum copyOfToBeDeletedNodesSilinecek tüm düğümlerin listesini silmek için (9). Başka bir topAndPop-Caccification ortada itilir, yerel işaretçiyi kullanıyorum copyOfToBeDeletedNodesetrafında toBeDeletedNodes-işaretçileri güncellemek için.
İki yardımcı işlev addNodeToBeDeletedNodes VE deleteAllNodes listede sarılık. deleteAllNodes Sadece bir topAndPop-Chiamare aktif. Sonuç olarak, senkronizasyon gerekmez. Bu ifade üye işlevi için geçerli değildir addNodeToBeDeletedNodes (9) ve (7). Senkronize edilmelidir çünkü birden fazla topAndPop-Call aktif olabilir. . while-Ve Loop bunu yapar oldHead Düğümdeki ilk düğüme elenecek ve bir tane kullanacak compare_exchange_strongbunun olduğunu hesaba katmak topAndPop-Bu örtüşebilir. Örtüşmek topAndPop-Hias, bunun oldHead->next != toBeDeletedNodes (Satır 10) e oldHead->next üzerinde toBeDeletedNodes güncellenmelidir.
Şimdiye kadar, yığının bloklar olmadan uygulanması beklendiği gibi çalışıyor, ancak bazı zayıflıkları var. Çok topAndPop-Crepf'in çağrıları, sayacı olabilir topAndPopCounter Asla bir olmaz. Bu, ortadan kaldırılacak düğümler listesindeki düğümlerin ortadan kaldırılmadığı ve hafıza kaybımız olduğu anlamına gelir. Ayrıca, silinecek düğüm sayısı bir kaynak sorunu haline gelebilir.
Sırada ne var?
RCU ve tehlike işaretçisi ile problemler C ++ 26'da çözülebilir.
(RME)
Son üç makalede, yığın konusunu bloklar olmadan ele aldım:
Duyuru
Rainer Grimm yıllardır yazılım mimarı, ekip ve eğitim müdürü olarak çalıştı. C ++ programlama dilleri, Python ve Haskell hakkında makaleler yazmayı seviyor, ancak uzman konferanslarla konuşmayı da seviyor. Modern C ++ blogunda, C ++ tutkusuyla yoğun bir şekilde ilgileniyor.
Bu yazı için basit bir çöp koleksiyoncusu ile genişletiyorum.
Birden fazla eşzamanlı olarak yürütüldüğünü tartıştım topAndPush-Call bir yarış koşuludur. Birden fazla değilse bir düğümü güvenle ortadan kaldırabilirim topAndPush-Call eşzamanlı olarak gerçekleştirilir. Bu gözlem, bellek kaybı problemini çözmek için çok önemlidir: Bir listedeki uzak düğümler hariç, birden fazla olmasa da, bu listedeki düğümleri silecek ve silinecek topAndPush-Chiamare aktif. Tek bir meydan okuma var: başka hiçbir şeyin olmadığından nasıl emin olabilirim topAndPush-Bling aktif mi? Başında bir atom sayacı kullanıyorum topAndPush Sonunda arttı ve azaldı. Sayaç sıfır veya değilse bir topAndPush-Chiamare aktif.
Aşağıdaki program sunulan stratejiyi uygular. Dosyayı kullanıyorum lockFreeStackWithLeaks.cpp Başlangıç noktası olarak “C ++ 26: Bloklar Olmayan Bir Yığının Tamamen Uygulanması” makalesinden.
// lockFreeStackWithGarbageCollection.cpp
#include <atomic>
#include <future>
#include <iostream>
#include <stdexcept>
#include <thread>
template<typename T>
class LockFreeStack {
private:
struct Node {
T data;
Node* next;
Node(T d): data(d), next(nullptr){ }
};
std::atomic<Node*> head{nullptr};
std::atomic<int> topAndPopCounter{}; // 1
std::atomic<Node*> toBeDeletedNodes{nullptr}; // 2
void tryToDelete(Node* oldHead) { // 3
if (topAndPopCounter == 1) { // 6
Node* copyOfToBeDeletedNodes = toBeDeletedNodes.exchange(nullptr); // 8
if (topAndPopCounter == 1) deleteAllNodes(copyOfToBeDeletedNodes); // 9
else addNodeToBeDeletedNodes(copyOfToBeDeletedNodes);
delete oldHead;
}
else addNodeToBeDeletedNodes(oldHead); // 7
}
void addNodeToBeDeletedNodes(Node* oldHead) {
oldHead->next = toBeDeletedNodes;
while( !toBeDeletedNodes.compare_exchange_strong(oldHead->next, oldHead) ); // 10
}
void deleteAllNodes(Node* currentNode) { // 4
while (currentNode) {
Node* nextNode = currentNode->next;
delete currentNode;
currentNode = nextNode;
}
}
public:
LockFreeStack() = default;
LockFreeStack(const LockFreeStack&) = delete;
LockFreeStack& operator= (const LockFreeStack&) = delete;
void push(T val) {
Node* const newNode = new Node(val);
newNode->next = head.load();
while( !head.compare_exchange_strong(newNode->next, newNode) );
}
T topAndPop() {
++topAndPopCounter;
Node* oldHead = head.load();
while( oldHead && !head.compare_exchange_strong(oldHead, oldHead->next) ) {
if ( !oldHead ) throw std:
ut_of_range("The stack is empty!");}
auto topElement = oldHead->data;
tryToDelete(oldHead); // 5
--topAndPopCounter;
return topElement;
}
};
int main(){
LockFreeStack<int> lockFreeStack;
auto fut = std::async([&lockFreeStack]{ lockFreeStack.push(2011); });
auto fut1 = std::async([&lockFreeStack]{ lockFreeStack.push(2014); });
auto fut2 = std::async([&lockFreeStack]{ lockFreeStack.push(2017); });
auto fut3 = std::async([&lockFreeStack]{ return lockFreeStack.topAndPop(); });
auto fut4 = std::async([&lockFreeStack]{ return lockFreeStack.topAndPop(); });
auto fut5 = std::async([&lockFreeStack]{ return lockFreeStack.topAndPop(); });
fut.get(), fut1.get(), fut2.get();
std::cout << fut3.get() << 'n';
std::cout << fut4.get() << 'n';
std::cout << fut5.get() << 'n';
}
Blokların olmayan yığın iki yeni özelliği ve üç yeni üyesi vardır. Atom sayacı topAndPopCounter Sayım (1) Aktif bileşenlerin sayısı topAndPop-Crepfen ve atom işaretçisi toBeDeletedNodes (2) Elimine edilecek düğümler listesindeki bir işaretçidir. Üye işlevi de dener tryToDelete (3), düğümleri çıkarın. Üye işlevi addNodeToBeDeletedNodes Silinecek düğüm listesine bir düğüm ve üyenin işlevi ekler deleteAllNodes (4) tüm düğümleri ortadan kaldırır.
Şimdi üyenin işlevini analiz edelim topAndPop. Başında ve sonunda topAndPop hale gelmek topAndPopCounter Artmış ve azaltılmış. oldHead Yığıntan çıkarılır ve bu nedenle nihayet hatırlanabilir Trytodelete (5) ortadan kaldırılacak. Üye işlevi tryToDelete Önce bir veya daha fazla topAndPop-Hias aktiftir. Eğer topAndPop-Aşetme aktif (6), oldHead silindi. Aksi takdirde olur oldHead Elimine edilecek öğelerin listesine eklendi (7). Sanırım sadece bir tane topAndPop-Chiamare aktif. Bu durumda yerel bir işaretçi oluşturuyorum copyOfToBeDeletedNodes Düğümlerde ortadan kaldırılacak ve toBeDeletedNodes-Birde nullptr (8). Düğümleri ortadan kaldırmadan önce, bu arada başka bir şey olup olmadığını kontrol edin topAndPop-Chiamare aktif. Mevcut olan topAndPop Yerel işaretçiyi kullanıyorum copyOfToBeDeletedNodesSilinecek tüm düğümlerin listesini silmek için (9). Başka bir topAndPop-Caccification ortada itilir, yerel işaretçiyi kullanıyorum copyOfToBeDeletedNodesetrafında toBeDeletedNodes-işaretçileri güncellemek için.
İki yardımcı işlev addNodeToBeDeletedNodes VE deleteAllNodes listede sarılık. deleteAllNodes Sadece bir topAndPop-Chiamare aktif. Sonuç olarak, senkronizasyon gerekmez. Bu ifade üye işlevi için geçerli değildir addNodeToBeDeletedNodes (9) ve (7). Senkronize edilmelidir çünkü birden fazla topAndPop-Call aktif olabilir. . while-Ve Loop bunu yapar oldHead Düğümdeki ilk düğüme elenecek ve bir tane kullanacak compare_exchange_strongbunun olduğunu hesaba katmak topAndPop-Bu örtüşebilir. Örtüşmek topAndPop-Hias, bunun oldHead->next != toBeDeletedNodes (Satır 10) e oldHead->next üzerinde toBeDeletedNodes güncellenmelidir.
Şimdiye kadar, yığının bloklar olmadan uygulanması beklendiği gibi çalışıyor, ancak bazı zayıflıkları var. Çok topAndPop-Crepf'in çağrıları, sayacı olabilir topAndPopCounter Asla bir olmaz. Bu, ortadan kaldırılacak düğümler listesindeki düğümlerin ortadan kaldırılmadığı ve hafıza kaybımız olduğu anlamına gelir. Ayrıca, silinecek düğüm sayısı bir kaynak sorunu haline gelebilir.
Sırada ne var?
RCU ve tehlike işaretçisi ile problemler C ++ 26'da çözülebilir.
(RME)