C ++ 26: Bloksız bir yığının basitleştirilmiş uygulanması
Son yazımda bloklar olmadan programlama teorisine göre, şimdi pratik bir uygulama.
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.
Genel düşünceler
Dışarıdan, çağrı (uygulama) veri korumasından sorumludur. İçeriden, veri yapısı korumadan sorumludur. Hiçbir veri ihale oluşamayacak şekilde kendini koruyan bir veri yapısı, iplik geçirmez.
Her şeyden önce, bir yarışma veri yapısının tasarımında nasıl ilerleyeceğine dair soru ortaya çıkıyor.
Her şeyden önce: Bir yığın için ne beklerim?
Bir yığın
std::stack LIFO prensibini takip edin (önce şarj edin). Bir yığın staBaşlık Kimdirstack> Gerekli, üç üye işlevi vardır: sta.push(e)Yeni bir unsurunuz olabilir e Yığının üst kısmını ekleyin sta.pop() Yukarıdan ve ile kaldır sta.top() Buna bakın. Yığın karşılaştırma operatörlerini destekler ve boyutunu bilir.
#include <stack>
...
std::stack<int> myStack;
std::cout << myStack.empty() << 'n'; // true
std::cout << myStack.size() << 'n'; // 0
myStack.push(1);
myStack.push(2);
myStack.push(3);
std::cout << myStack.top() << 'n'; // 3
while (!myStack.empty()){
std::cout << myStack.top() << " ";
myStack.pop();
} // 3 2 1
std::cout << myStack.empty() << 'n'; // true
std::cout << myStack.size() << 'n'; // 0
Şimdi bloksuz bir yığın uygulamaya başlayalım.
Basitleştirilmiş bir uygulama
Basitleştirilmiş uygulamamda push-Üye işlevi. Her şeyden önce, sadece zincirlenmiş bir listeye nasıl yeni bir düğüm eklendiğini göstermek istiyorum. head Basitçe zincirli listedeki ilk düğümün işaretçisidir.
Basitçe zincirlenmiş listedeki her düğümün iki özelliği vardır: değeri T Ve işaretçi next. next Basitçe zincirlenmiş listedeki bir sonraki öğeyi ifade eder. Yalnızca düğüm anlamına gelir nullptr. Yeni bir veri düğümünün eklenmesi basittir. Yeni bir düğüm oluşturun ve next-Bu önerileri önceki kafaya çevirin. Şimdiye kadar, yeni düğüm erişilemez. Sonunda yeni düğüm yeni kafa olur ve onu kapatır push-Prox.
Aşağıdaki örnek, eşzamanlı bir yığın blokları olmadan uygulamayı göstermektedir:
// lockFreeStackPush.cpp
#include <atomic>
#include <iostream>
template<typename T>
class LockFreeStackPush {
private:
struct Node {
T data;
Node* next;
Node(T d): data(d), next(nullptr) {}
};
std::atomic<Node*> head;
public:
LockFreeStackPush() = default;
LockFreeStackPush(const LockFreeStackPush&) = delete;
LockFreeStackPush& operator= (const LockFreeStackPush&)
= delete;
void push(T val) {
Node* const newNode = new Node(val); // 1
newNode->next = head.load(); // 2
while( !head.compare_exchange_strong(newNode->next,
newNode) ); // 3
}
};
int main(){
LockFreeStackPush<int> lockFreeStack;
lockFreeStack.push(5);
LockFreeStackPush<double> lockFreeStack2;
lockFreeStack2.push(5.5);
LockFreeStackPush<std::string> lockFreeStack3;
lockFreeStack3.push("hello");
}
Kararlı üyelerin işlevini istiyorum push analiz. Yeni düğümü (1) oluşturun, bir sonraki işaretçisini eski kafaya uyarlar ve yeni düğümü yeni bir kafaya SO -CAAL CAS işlemine dönüştürür (3). CAS Operasyonu, bir atom geçişinde bir karşılaştırma ve değişim işlemi sunar.
Arama newNode->next = head.load() eski değerini şarj etmek head. Davet edilen değer ne zaman newNode->next Aynı head (3) 'de head AÇIK newNode Güncellendi ve çağrı head.compare_exchange_strong itibaren true Geriye doğru. Aksi takdirde, çağrı verir false Geri ve while-Chip çağrıya kadar gerçekleştirilir true geri gelmek. head.compare_exchange_strong itibaren false Başka bir iş parçacığı yığına yeni bir düğüm eklediğinde.
Kod örneğinde (2) ve (3) satırları bir tür nükleer işlem oluşturur. Önce veri yapısının bir anlık görüntüsü oluşturulur (2), daha sonra işlemi yayınlama girişimi yapılır (3). Anlık görüntü artık geçerli değilse, bir geri dönüş gerçekleştirilir ve denemeler tekrar yapılır.
Sırada ne var?
Bugünün basitleştirilmiş yığını uyguluyorum, gelecekteki yığınlar için bir temel olarak ihtiyacım var.
(RME)
C ++ 26: Bloksız bir yığının basitleştirilmiş uygulanması
Son yazımda bloklar olmadan programlama teorisine göre, şimdi pratik bir uygulama.
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.
Genel düşünceler
Dışarıdan, çağrı (uygulama) veri korumasından sorumludur. İçeriden, veri yapısı korumadan sorumludur. Hiçbir veri ihale oluşamayacak şekilde kendini koruyan bir veri yapısı, iplik geçirmez.
Her şeyden önce, bir yarışma veri yapısının tasarımında nasıl ilerleyeceğine dair soru ortaya çıkıyor.
- Kilitleme stratejisi: Verilerin yapısı kaba kilidi veya ince taneyi destekliyor veya bloklar içermiyor mu? Kaba kaba bloğun uygulanması daha kolaydır, ancak çatışmalara yol açar. İnce tahıl uygulaması veya bloklar olmadan çok daha zorludur. Her şeyden önce: kaba tahıl kilitlemesini nasıl anlayabilirsiniz? Kaba tane bloğu, veri yapısının yalnızca belirli bir anda bir iş parçacığı tarafından kullanıldığı anlamına gelir.
- Arayüzün ayrıntıtüsü: İplik güvenli veri yapısının arayüzü ne kadar güçlü olursa, eşzamanlı kullanımınızı düşünmek o kadar zor olur.
- Tipik kullanım modelleri: Okuyucular esas olarak verilerin yapısını kullanıyorsa, bunları yazarlar için optimize etmemelisiniz.
- Boşluklardan kaçının: Veri yapınızın dahili müşterilerini iletmeyin.
- yarışma: Veri yapısında genellikle müşteri eşzamanlı istekleri meydana gelir mi?
- Ölçeklenebilirlik: Eşzamanlı istemcilerin sayısı artarsa veya verilerin yapısı sınırlıysa veri yapısının performansı nedir?
- Değişmez: Kullanırken veri yapısına hangi değişmez uygulanmalıdır?
- İstisnalar: Bir istisna meydana gelirse ne olmalı?
Her şeyden önce: Bir yığın için ne beklerim?
Bir yığın
std::stack LIFO prensibini takip edin (önce şarj edin). Bir yığın staBaşlık Kimdirstack> Gerekli, üç üye işlevi vardır: sta.push(e)Yeni bir unsurunuz olabilir e Yığının üst kısmını ekleyin sta.pop() Yukarıdan ve ile kaldır sta.top() Buna bakın. Yığın karşılaştırma operatörlerini destekler ve boyutunu bilir.
#include <stack>
...
std::stack<int> myStack;
std::cout << myStack.empty() << 'n'; // true
std::cout << myStack.size() << 'n'; // 0
myStack.push(1);
myStack.push(2);
myStack.push(3);
std::cout << myStack.top() << 'n'; // 3
while (!myStack.empty()){
std::cout << myStack.top() << " ";
myStack.pop();
} // 3 2 1
std::cout << myStack.empty() << 'n'; // true
std::cout << myStack.size() << 'n'; // 0
Şimdi bloksuz bir yığın uygulamaya başlayalım.
Basitleştirilmiş bir uygulama
Basitleştirilmiş uygulamamda push-Üye işlevi. Her şeyden önce, sadece zincirlenmiş bir listeye nasıl yeni bir düğüm eklendiğini göstermek istiyorum. head Basitçe zincirli listedeki ilk düğümün işaretçisidir.
Basitçe zincirlenmiş listedeki her düğümün iki özelliği vardır: değeri T Ve işaretçi next. next Basitçe zincirlenmiş listedeki bir sonraki öğeyi ifade eder. Yalnızca düğüm anlamına gelir nullptr. Yeni bir veri düğümünün eklenmesi basittir. Yeni bir düğüm oluşturun ve next-Bu önerileri önceki kafaya çevirin. Şimdiye kadar, yeni düğüm erişilemez. Sonunda yeni düğüm yeni kafa olur ve onu kapatır push-Prox.
Aşağıdaki örnek, eşzamanlı bir yığın blokları olmadan uygulamayı göstermektedir:
// lockFreeStackPush.cpp
#include <atomic>
#include <iostream>
template<typename T>
class LockFreeStackPush {
private:
struct Node {
T data;
Node* next;
Node(T d): data(d), next(nullptr) {}
};
std::atomic<Node*> head;
public:
LockFreeStackPush() = default;
LockFreeStackPush(const LockFreeStackPush&) = delete;
LockFreeStackPush& operator= (const LockFreeStackPush&)
= delete;
void push(T val) {
Node* const newNode = new Node(val); // 1
newNode->next = head.load(); // 2
while( !head.compare_exchange_strong(newNode->next,
newNode) ); // 3
}
};
int main(){
LockFreeStackPush<int> lockFreeStack;
lockFreeStack.push(5);
LockFreeStackPush<double> lockFreeStack2;
lockFreeStack2.push(5.5);
LockFreeStackPush<std::string> lockFreeStack3;
lockFreeStack3.push("hello");
}
Kararlı üyelerin işlevini istiyorum push analiz. Yeni düğümü (1) oluşturun, bir sonraki işaretçisini eski kafaya uyarlar ve yeni düğümü yeni bir kafaya SO -CAAL CAS işlemine dönüştürür (3). CAS Operasyonu, bir atom geçişinde bir karşılaştırma ve değişim işlemi sunar.
Arama newNode->next = head.load() eski değerini şarj etmek head. Davet edilen değer ne zaman newNode->next Aynı head (3) 'de head AÇIK newNode Güncellendi ve çağrı head.compare_exchange_strong itibaren true Geriye doğru. Aksi takdirde, çağrı verir false Geri ve while-Chip çağrıya kadar gerçekleştirilir true geri gelmek. head.compare_exchange_strong itibaren false Başka bir iş parçacığı yığına yeni bir düğüm eklediğinde.
Kod örneğinde (2) ve (3) satırları bir tür nükleer işlem oluşturur. Önce veri yapısının bir anlık görüntüsü oluşturulur (2), daha sonra işlemi yayınlama girişimi yapılır (3). Anlık görüntü artık geçerli değilse, bir geri dönüş gerçekleştirilir ve denemeler tekrar yapılır.
Sırada ne var?
Bugünün basitleştirilmiş yığını uyguluyorum, gelecekteki yığınlar için bir temel olarak ihtiyacım var.
(RME)