rigtorp/Seqlock là dự án Backend trên GitHub, viết chủ yếu bằng C++, với 246 sao. An implementation of Seqlock in C++11
Tóm tắt dựng từ metadata GitHub của chính dự án — chưa có bài review TopGit. Trang sẽ tự động cập nhật khi bài review đầy đủ được xuất bản.
VÌ SAO CHƯA CÓ REVIEW
TopGit viết bài đầy đủ cho repo có nhiều sao nhất và được yêu cầu nhiều nhất. Trang này là snapshot trong thời gian chờ — xem README gốc ở tab READ ME.
A seqlock can be used as an alternative to
a readers-writer lock. It
will never block the writer and doesn't require any memory bus locks.
Example
struct Data {
std::size_t a, b, c;
};
Seqlock<Data> sl;
sl.store({0, 0, 0});
auto t = std::thread([&] {
for (;;) {
auto d = sl.load();
if (d.a + 100 == d.b && d.c == d.a + d.b) {
return;
}
}
});
sl.store({100, 200, 300});
t.join();
Usage
Create a seqlock:
struct Data {
std::size_t a, b, c;
};
Seqlock<Data> sl;
Store a value (can only be called from a single thread):
sl.store({1, 2, 3});
Load a value (can be called from multiple threads):
auto v = sl.load();
Implementation
Implementing the seqlock in portable C++11 is quite tricky. The basic
seqlock implementation unconditionally loads the sequence number,
then unconditionally loads the protected data and finally
unconditionally loads the sequence number again. Since loading the
protected data is done unconditionally on the sequence number the
compiler is free to move these loads before or after the loads from
the sequence number.
T load() const noexcept {
T copy;
size_t seq0, seq1;
do {
seq0 = seq_.load(std::memory_order_acquire);
copy = value_;
seq1 = seq_.load(std::memory_order_acquire);
} while (seq0 != seq1 || seq0 & 1);
return copy;
}
Compiling this code specialized for int with g++-5.2 -std=c++11 -O3 yields
the following assembly:
We see that the compiler did indeed reorder the load of the protected
data outside the critical section and the data is no longer protected
from torn reads. Interestingly compiling using clang++-3.7 -std=c++11 -O3 produces the correct assembly:
Make the location of the protected data dependent on the sequence
number by storing multiple instances of the data and selecting which
one to read from based on the sequence number. This solution should
be portable to all CPU architectures, but requires extra space.
For x86 it's enough to insert a compiler barrier using
std::atomic_signal_fence(std::memory_order_acq_rel). This will
only work on the x86 memory model. On
ARM memory model you need to inserts a dmb memory
barrier instruction, which is not possible in C++11.
Since my target architecture is x86 I've implemented the second
option:
T load() const noexcept {
T copy;
size_t seq0, seq1;
do {
seq0 = seq_.load(std::memory_order_acquire);
std::atomic_signal_fence(std::memory_order_acq_rel);
copy = value_;
std::atomic_signal_fence(std::memory_order_acq_rel);
seq1 = seq_.load(std::memory_order_acquire);
} while (seq0 != seq1 || seq0 & 1);
return copy;
}
Compiled with g++-5.2 -std=c++11 -O3 it produces the
following correct assembly:
The store operation is implemented in a similar manner to the load
operation. Additionally the data and sequence counter is aligned and
padded to prevent false sharing with adjacent data.
References:
fast reader/writer lock for gettimeofday 2.5.30
Can Seqlocks Get Along With Programming Language Memory Models?
(slides)
x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors
A Tutorial Introduction to the ARM and POWER Relaxed Memory Models
Testing
Testing lock-free algorithms is hard. I'm using two approaches to test
the implementation:
A test that load() and store() publish results in the correct
order on a single thread.
A multithreaded fuzz test that load() never see a partial
store() (torn read).
Potential improvements
Allow partial updates and reads using a visitor pattern.
Support for multiple writers can be achieved by using a CAS loop to
acquire the odd sequence number in the store operation. This would
have the same effect as wrapping the seqlock in a spinlock.
Trade-off space for reduced readers-writer contention by striping
writes across multiple seqlocks.
Trang TopGit này là một snapshot — tab "Readme" hiển thị nguyên văn README của repo (đã bỏ link, giữ ảnh). Repo GitHub ở github.com/rigtorp/Seqlock là nguồn chính thức.
rigtorp/Seqlock có bao nhiêu sao?
rigtorp/Seqlock có 246 sao GitHub — tải lại trang để xem số mới nhất, hoặc xem trực tiếp github.com/rigtorp/Seqlock. TopGit phản chiếu số sao của GitHub nhưng không cam kết đến từng phút.
rigtorp/Seqlock có phải mã nguồn mở không?
Có — rigtorp/Seqlock phát hành theo license MIT, nghĩa là mã nguồn mở để đọc, fork và (tùy license) tái sử dụng. Mã: github.com/rigtorp/Seqlock.
rigtorp/Seqlock còn đang phát triển không?
Commit gần nhất trên rigtorp/Seqlock là 2.1 năm trước (theo timestamp GitHub). Repo có 38 fork — một chỉ báo về mức độ quan tâm của cộng đồng.
rigtorp/Seqlock là gì?
rigtorp/Seqlock (rigtorp/Seqlock) là dự án C++ trên GitHub. Theo mô tả gốc: An implementation of Seqlock in C++11
rigtorp/Seqlock so với các dự án Backend khác thế nào?
rigtorp/Seqlock được TopGit xếp vào nhóm Backend, với 246 sao GitHub và viết bằng C++. Xem trang chủ đề Backend trên TopGit để so sánh với các dự án tương tự theo số sao và mức độ hoạt động.
Đọc đầy đủ README ở tab phía trên.
Vẫn đang phân vân về Seqlock?
Một cú bấm sẽ gửi câu hỏi kèm trang này cho AI — xem AI nói gì về Seqlock.
/Seqlock
