C ++ 26: Bloksız bir yığının tamamen uygulanması
Önceki makalede sondan bir önceki katkı ve eksik uygulamada bloklar olmadan programlama teorisine göre, blok olmayan bir bloğun tam olarak uygulanması şimdi takip edilmektedir.
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.
Sıralı tutarlılık
Bu paragraf isteğe bağlıdır. Örneklerimde standart bellek kuralları kullanıyorum: sıralı tutarlılık. Bunun nedeni basit. Sıralı tutarlılık, tüm bellek düzenlemelerinin en güçlü garantilerini sunar ve bu nedenle kullanımı diğer depolama düzenlemelerinden daha kolaydır. Sıralı tutarlılık, blokları olmayan veri yapılarının tasarımı için ideal bir başlangıç noktasıdır. Ek optimizasyon adımlarında, bellek düzenlemeleri zayıflatılabilir ve rahat bir anlambilim veya semantik kullanılabilir.
Mimariye bağlı olarak, bellek sözleşmesinin zayıflaması ödemiyor olabilir. Örneğin, X86 bellek modeli, en modern mimarilerin en güçlü bellek modellerinden biridir. Bu nedenle, sıralı tutarlılığın iptali ve daha zayıf bir bellek emrinin kullanılması, istenen performansın iyileştirilmesini getirmeyebilir. Aksine, Armv8, PowerPC, Itanium ve özellikle DEC alfa sıralı tutarlılık iptal edilirse geri ödeme yapabilir.
Son makalenin basitleştirilmiş yığınının versiyonunun iki sorunu vardır: her şeyden önce, bir çekme işlemi yok ve ikincisi, herhangi bir bellek yayınlamıyor.
Tam bir uygulama
Genellikle bir yığın üyenin işlevlerini destekler push,, pop VE top. Üyelerin uygulanması pop VE top İplik geçirmez bir şekilde, çağrının topardından popKonu -Safe. Bir iş parçacığı olabilir t1 stack.top() Ara ve başka bir iş parçacığından t2 üst üste biniyor, stack.top() Daha sonra stack.pop() çağrılar. Şimdi son çağrı pop Yanlış yığın büyüklüğünde.
Dosyalama iadesi yok
Sonuç olarak, iki öğe işlevi aşağıdaki uygulamada top VE pop Tek bir işlevde özetlenmiştir: topAndPop.
// lockFreeStackWithLeaks.cpp
#include <atomic>
#include <future>
#include <iostream>
#include <stdexcept>
template<typename T>
class LockFreeStack {
private:
struct Node {
T data;
Node* next;
Node(T d): data(d), next(nullptr){ }
};
std::atomic<Node*> head;
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() {
Node* oldHead = head.load(); // 1
while( oldHead && !head.compare_exchange_strong(oldHead, oldHead->next) ) { // 2
if ( !oldHead ) throw std:
ut_of_range("The stack is empty!"); // 3
}
return oldHead->data; // 4
}
};
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(); // 5
std::cout << fut3.get() << 'n';
std::cout << fut4.get() << 'n';
std::cout << fut5.get() << 'n';
}
Üye işlevi topAndPop Yığının üst öğesini döndürür. Yığının ana öğesini (satır 1) okur ve bir sonraki düğümü yeni bir kafa yapar oldHead HAYIR nullptr (satır 2). oldhead bir nullptrYığın boşken. Yığın boşken bir istisna koydum (satır 3). Özel olmayan bir değerin geri dönüşü veya bir std:ptional Aynı zamanda geçerli bir seçenektir. Değerin kopyasının bir dezavantajı var: Kopyalar üreticisi gibi bir istisnaysa std::bad_alloc Tetik, değer kaybolur. Son olarak, üye işlevi ana öğeyi döndürür (satır 4).
Çağrı fut.get(),, fut1.get(),, fut2.get() (Satır 5) İlişkili sözün gerçekleştirildiğinden emin olun. Başlatma politikası sağlanmazsa, söz verimi arayanın iş parçacığında ertelenebilir. Tembel, sözün sadece gelecekse gerçekleştirildiği anlamına gelir get VEYA wait Sonucunu ister. Söz ayrıca ayrı bir iş parçacığında başlayabilir:
auto fut = std::async(std::launch::asnyc, [&conStack]{ conStack.push(2011); });
auto fut1 = std::async(std::launch::asnyc, [&conStack]{ conStack.push(2014); });
auto fut2 = std::async(std::launch::asnyc, [&conStack]{ conStack.push(2017); });
Program çıktısı nihayet:
Yığın bloklar olmadan piyasaya sürülmesine rağmen push VE topAndPop Desteklenen, ciddi bir sorunu var: hafızayı kaybeder. Çünkü yapabilirsin oldHead Sadece aradıktan sonra değil head.compare_exchange_strong(oldHead, oldHead->next) (2) üye işlevinde topAndPop kaldırılacak mı? Cevap, başka bir konu oldHead kullanabilir. Üyelerin işlevlerini analiz edelim push VE topAndPop. Eşzamanlı olarak yürütülmesi push Bu bir sorun değil çünkü çağrı !head.compare_exchange_strong(newNode->next, newNode) newNode->next Atomik yeni kafaya güncellendi. Bu, yalnızca bir çağrı olsa bile geçerlidir topAndPop Olur. Sorun, farklı görüşler topAndPop Çağrı ile veya çağrı olmadan push iç içe. Eliminasyon oldHeadBaşka bir iş parçacığı kullanırken, felaket olur çünkü yok olma oldHead Güncellemesinden önce veya sonra her zaman yeni kafada yapılmalıdır: oldHead->next (2).
Sırada ne var?
RCU ve Hazard'ın işaretçileri sayesinde bir sonraki makalemdeki hafıza kayıplarını kaldırabilirim.
(RME)
C ++ 26: Bloksız bir yığının tamamen uygulanması
Önceki makalede sondan bir önceki katkı ve eksik uygulamada bloklar olmadan programlama teorisine göre, blok olmayan bir bloğun tam olarak uygulanması şimdi takip edilmektedir.
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.
Sıralı tutarlılık
Bu paragraf isteğe bağlıdır. Örneklerimde standart bellek kuralları kullanıyorum: sıralı tutarlılık. Bunun nedeni basit. Sıralı tutarlılık, tüm bellek düzenlemelerinin en güçlü garantilerini sunar ve bu nedenle kullanımı diğer depolama düzenlemelerinden daha kolaydır. Sıralı tutarlılık, blokları olmayan veri yapılarının tasarımı için ideal bir başlangıç noktasıdır. Ek optimizasyon adımlarında, bellek düzenlemeleri zayıflatılabilir ve rahat bir anlambilim veya semantik kullanılabilir.
Mimariye bağlı olarak, bellek sözleşmesinin zayıflaması ödemiyor olabilir. Örneğin, X86 bellek modeli, en modern mimarilerin en güçlü bellek modellerinden biridir. Bu nedenle, sıralı tutarlılığın iptali ve daha zayıf bir bellek emrinin kullanılması, istenen performansın iyileştirilmesini getirmeyebilir. Aksine, Armv8, PowerPC, Itanium ve özellikle DEC alfa sıralı tutarlılık iptal edilirse geri ödeme yapabilir.
Son makalenin basitleştirilmiş yığınının versiyonunun iki sorunu vardır: her şeyden önce, bir çekme işlemi yok ve ikincisi, herhangi bir bellek yayınlamıyor.
Tam bir uygulama
Genellikle bir yığın üyenin işlevlerini destekler push,, pop VE top. Üyelerin uygulanması pop VE top İplik geçirmez bir şekilde, çağrının topardından popKonu -Safe. Bir iş parçacığı olabilir t1 stack.top() Ara ve başka bir iş parçacığından t2 üst üste biniyor, stack.top() Daha sonra stack.pop() çağrılar. Şimdi son çağrı pop Yanlış yığın büyüklüğünde.
Dosyalama iadesi yok
Sonuç olarak, iki öğe işlevi aşağıdaki uygulamada top VE pop Tek bir işlevde özetlenmiştir: topAndPop.
// lockFreeStackWithLeaks.cpp
#include <atomic>
#include <future>
#include <iostream>
#include <stdexcept>
template<typename T>
class LockFreeStack {
private:
struct Node {
T data;
Node* next;
Node(T d): data(d), next(nullptr){ }
};
std::atomic<Node*> head;
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() {
Node* oldHead = head.load(); // 1
while( oldHead && !head.compare_exchange_strong(oldHead, oldHead->next) ) { // 2
if ( !oldHead ) throw std:
ut_of_range("The stack is empty!"); // 3}
return oldHead->data; // 4
}
};
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(); // 5
std::cout << fut3.get() << 'n';
std::cout << fut4.get() << 'n';
std::cout << fut5.get() << 'n';
}
Üye işlevi topAndPop Yığının üst öğesini döndürür. Yığının ana öğesini (satır 1) okur ve bir sonraki düğümü yeni bir kafa yapar oldHead HAYIR nullptr (satır 2). oldhead bir nullptrYığın boşken. Yığın boşken bir istisna koydum (satır 3). Özel olmayan bir değerin geri dönüşü veya bir std:
ptional Aynı zamanda geçerli bir seçenektir. Değerin kopyasının bir dezavantajı var: Kopyalar üreticisi gibi bir istisnaysa std::bad_alloc Tetik, değer kaybolur. Son olarak, üye işlevi ana öğeyi döndürür (satır 4).Çağrı fut.get(),, fut1.get(),, fut2.get() (Satır 5) İlişkili sözün gerçekleştirildiğinden emin olun. Başlatma politikası sağlanmazsa, söz verimi arayanın iş parçacığında ertelenebilir. Tembel, sözün sadece gelecekse gerçekleştirildiği anlamına gelir get VEYA wait Sonucunu ister. Söz ayrıca ayrı bir iş parçacığında başlayabilir:
auto fut = std::async(std::launch::asnyc, [&conStack]{ conStack.push(2011); });
auto fut1 = std::async(std::launch::asnyc, [&conStack]{ conStack.push(2014); });
auto fut2 = std::async(std::launch::asnyc, [&conStack]{ conStack.push(2017); });
Program çıktısı nihayet:
Yığın bloklar olmadan piyasaya sürülmesine rağmen push VE topAndPop Desteklenen, ciddi bir sorunu var: hafızayı kaybeder. Çünkü yapabilirsin oldHead Sadece aradıktan sonra değil head.compare_exchange_strong(oldHead, oldHead->next) (2) üye işlevinde topAndPop kaldırılacak mı? Cevap, başka bir konu oldHead kullanabilir. Üyelerin işlevlerini analiz edelim push VE topAndPop. Eşzamanlı olarak yürütülmesi push Bu bir sorun değil çünkü çağrı !head.compare_exchange_strong(newNode->next, newNode) newNode->next Atomik yeni kafaya güncellendi. Bu, yalnızca bir çağrı olsa bile geçerlidir topAndPop Olur. Sorun, farklı görüşler topAndPop Çağrı ile veya çağrı olmadan push iç içe. Eliminasyon oldHeadBaşka bir iş parçacığı kullanırken, felaket olur çünkü yok olma oldHead Güncellemesinden önce veya sonra her zaman yeni kafada yapılmalıdır: oldHead->next (2).
Sırada ne var?
RCU ve Hazard'ın işaretçileri sayesinde bir sonraki makalemdeki hafıza kayıplarını kaldırabilirim.
(RME)