J'aime 0
Fork 0

Dernière activité 1784621034

ZZ's Avatar ZZ a révisé ce gist 1784621034. Aller à la révision

1 file changed, 1 insertion, 1 deletion

Gemma4-C++-to-rust-test.md

@@ -154,7 +154,7 @@ The `MASKS` and `SHIFTS` constants are used to isolate these 2-bit chunks. For e
154 154 #### 2. The Workflow
155 155 * **Producer (`produce`)**:
156 156 1. Scans the bitfield for any buffer marked as `FREE`.
157 - 2. Uses **CAS (Compare-And-Swap)** via `compare_exchange_weak` to atomically change `FREE` $\rightarrow$ `WRITING`.
157 + 2. Uses **CAS (Compare-And-Swap)** via `compare_exchange_weak` to atomically change `FREE` > `WRITING`.
158 158 3. Writes the data into that specific buffer index.
159 159 4. Uses CAS to change `WRITING` > `READABLE`.
160 160 * **Consumer (`consume`)**:

ZZ's Avatar ZZ a révisé ce gist 1784620993. Aller à la révision

1 file changed, 3 insertions, 3 deletions

Gemma4-C++-to-rust-test.md

@@ -156,12 +156,12 @@ The `MASKS` and `SHIFTS` constants are used to isolate these 2-bit chunks. For e
156 156 1. Scans the bitfield for any buffer marked as `FREE`.
157 157 2. Uses **CAS (Compare-And-Swap)** via `compare_exchange_weak` to atomically change `FREE` $\rightarrow$ `WRITING`.
158 158 3. Writes the data into that specific buffer index.
159 - 4. Uses CAS to change `WRITING` $\rightarrow$ `READABLE`.
159 + 4. Uses CAS to change `WRITING` > `READABLE`.
160 160 * **Consumer (`consume`)**:
161 161 1. Scans for any buffer marked as `READABLE`.
162 - 2. Uses CAS to atomically change `READABLE` $\rightarrow$ `READING`.
162 + 2. Uses CAS to atomically change `READABLE` > `READING`.
163 163 3. Copies the data out of that buffer index.
164 - 4. Uses CAS to change `READING` $\rightarrow$ `FREE`.
164 + 4. Uses CAS to change `READING` > `FREE`.
165 165
166 166 #### 3. Rust-Specific Details
167 167 * **`UnsafeCell<T>`**: In Rust, you cannot mutate a value inside a shared reference (`&self`) unless it is wrapped in a type that provides "interior mutability." Since we are handling synchronization ourselves via atomics, `UnsafeCell` is the most efficient way to tell the compiler: *"I know what I'm doing; allow me to mutate this memory."*

ZZ's Avatar ZZ a révisé ce gist 1784620559. Aller à la révision

Aucun changement

ZZ's Avatar ZZ a révisé ce gist 1784620484. Aller à la révision

1 file changed, 170 insertions

Gemma4-C++-to-rust-test.md(fichier créé)

@@ -0,0 +1,170 @@
1 + This is a lock-free **Triple Buffer** implementation. Its primary purpose is to allow one thread (the Producer) to write data and another thread (the Consumer) to read data without blocking each other, while ensuring the consumer always gets the most recent "complete" frame.
2 +
3 + Here is the translation into Rust.
4 +
5 + ### The Rust Implementation
6 +
7 + To implement this in Rust, we need `UnsafeCell` because we are mutating elements of an array across different threads based on a manual state machine rather than using a `Mutex`. We also use `repr(align(64))` to match the C++ `alignas(64)`, which prevents "false sharing" (where the CPU caches multiple buffers in one line, causing performance degradation).
8 +
9 + ```rust
10 + use std::cell::UnsafeCell;
11 + use std::sync::atomic::{AtomicU8, Ordering};
12 +
13 + #[repr(align(64))]
14 + pub struct TripleBuffer<T> {
15 + // UnsafeCell allows interior mutability for lock-free access
16 + buffers: [UnsafeCell<T>; 3],
17 + state: AtomicU8,
18 + }
19 +
20 + impl<T: Copy> TripleBuffer<T> {
21 + const FREE: u8 = 0;
22 + const WRITING: u8 = 1;
23 + const READABLE: u8 = 2;
24 + const READING: u8 = 3;
25 +
26 + const MASKS: [u8; 3] = [0x03, 0x0C, 0x30];
27 + const SHIFTS: [u8; 3] = [0, 2, 4];
28 +
29 + pub fn new(initial_value: T) -> Self {
30 + Self {
31 + buffers: [
32 + UnsafeCell::new(initial_value),
33 + UnsafeCell::new(initial_value),
34 + UnsafeCell::new(initial_value),
35 + ],
36 + state: AtomicU8::new(0),
37 + }
38 + }
39 +
40 + pub fn produce(&self, data: T) {
41 + let mut old_state: u8;
42 + let mut idx: usize;
43 +
44 + // Step 1: Find a FREE slot and mark it as WRITING
45 + loop {
46 + old_state = self.state.load(Ordering::Relaxed);
47 + idx = None;
48 + for i in 0..3 {
49 + if (old_state & Self::MASKS[i]) == Self::FREE {
50 + idx = Some(i);
51 + break;
52 + }
53 + }
54 +
55 + let idx = match idx {
56 + Some(i) => i,
57 + None => continue, // Spin until a slot is free
58 + };
59 +
60 + let new_state = old_state | (Self::WRITING << Self::SHIFTS[idx]);
61 + if self.state.compare_exchange_weak(
62 + old_state, new_state, Ordering::AcqRel, Ordering::Relaxed
63 + ).is_ok() {
64 + break;
65 + }
66 + }
67 +
68 + // Step 2: Write data to the buffer (Safe because we hold the WRITING state)
69 + unsafe {
70 + *self.buffers[idx].get() = data;
71 + }
72 +
73 + // Step 3: Mark the slot as READABLE
74 + loop {
75 + old_state = self.state.load(Ordering::Relaxed);
76 + if (old_state & Self::MASKS[idx]) != Self::WRITING {
77 + break;
78 + }
79 + let new_state = (old_state & !Self::MASKS[idx]) | (Self::READABLE << Self::SHIFTS[idx]);
80 + if self.state.compare_exchange_weak(
81 + old_state, new_state, Ordering::AcqRel, Ordering::Relaxed
82 + ).is_ok() {
83 + break;
84 + }
85 + }
86 + }
87 +
88 + pub fn consume(&self, out: &mut T) -> bool {
89 + let mut old_state: u8;
90 + let mut idx: usize;
91 +
92 + // Step 1: Find a READABLE slot and mark it as READING
93 + loop {
94 + old_state = self.state.load(Ordering::Relaxed);
95 + idx = None;
96 + for i in 0..3 {
97 + if (old_state & Self::MASKS[i]) == Self::READABLE {
98 + idx = Some(i);
99 + break;
100 + }
101 + }
102 +
103 + let idx = match idx {
104 + Some(i) => i,
105 + None => return false, // No complete frame available
106 + };
107 +
108 + let new_state = old_state | (Self::READING << Self::SHIFTS[idx]);
109 + if self.state.compare_exchange_weak(
110 + old_state, new_state, Ordering::AcqRel, Ordering::Relaxed
111 + ).is_ok() {
112 + break;
113 + }
114 + }
115 +
116 + // Step 2: Read data from the buffer (Safe because we hold the READING state)
117 + unsafe {
118 + *out = *self.buffers[idx].get();
119 + }
120 +
121 + // Step 3: Mark the slot as FREE
122 + loop {
123 + old_state = self.state.load(Ordering::Relaxed);
124 + if (old_state & Self::MASKS[idx]) != Self::READING {
125 + break;
126 + }
127 + let new_state = old_state & !Self::MASKS[idx]; // Set to FREE (0)
128 + if self.state.compare_exchange_weak(
129 + old_state, new_state, Ordering::AcqRel, Ordering::Relaxed
130 + ).is_ok() {
131 + break;
132 + }
133 + }
134 +
135 + true
136 + }
137 + }
138 +
139 + // Required to allow the buffer to be shared between threads
140 + unsafe impl<T: Sync> Sync for TripleBuffer<T> {}
141 + ```
142 +
143 + ### Explanation of the Logic
144 +
145 + #### 1. The State Machine (The "Bit-Packing" Trick)
146 + Instead of using three separate atomic variables, this code uses a single `u8` as a bitfield. Each buffer is allocated **2 bits** of space:
147 + * `00`: Free
148 + * `01`: Writing (Producer owns it)
149 + * `10`: Readable (Ready for Consumer)
150 + * `11`: Reading (Consumer owns it)
151 +
152 + The `MASKS` and `SHIFTS` constants are used to isolate these 2-bit chunks. For example, Buffer 1 is checked by shifting the state 2 bits to the right and masking with `0x03`.
153 +
154 + #### 2. The Workflow
155 + * **Producer (`produce`)**:
156 + 1. Scans the bitfield for any buffer marked as `FREE`.
157 + 2. Uses **CAS (Compare-And-Swap)** via `compare_exchange_weak` to atomically change `FREE` $\rightarrow$ `WRITING`.
158 + 3. Writes the data into that specific buffer index.
159 + 4. Uses CAS to change `WRITING` $\rightarrow$ `READABLE`.
160 + * **Consumer (`consume`)**:
161 + 1. Scans for any buffer marked as `READABLE`.
162 + 2. Uses CAS to atomically change `READABLE` $\rightarrow$ `READING`.
163 + 3. Copies the data out of that buffer index.
164 + 4. Uses CAS to change `READING` $\rightarrow$ `FREE`.
165 +
166 + #### 3. Rust-Specific Details
167 + * **`UnsafeCell<T>`**: In Rust, you cannot mutate a value inside a shared reference (`&self`) unless it is wrapped in a type that provides "interior mutability." Since we are handling synchronization ourselves via atomics, `UnsafeCell` is the most efficient way to tell the compiler: *"I know what I'm doing; allow me to mutate this memory."*
168 + * **`Ordering::AcqRel`**: This ensures that memory writes performed by the producer before the state change are visible to the consumer after they see the state change.
169 + * **`T: Copy`**: The C++ code uses `buffers[idx] = data`, which performs a copy. In Rust, I added the `Copy` trait bound for simplicity. If `T` is a large struct, you would use `std::ptr::copy_nonoverlapping` or wrap the data in `Box`.
170 + * **Alignment**: `#[repr(align(64))]` ensures the structure starts at a cache line boundary, reducing CPU pipeline stalls caused by multiple cores fighting over the same cache line.
Plus récent Plus ancien

Propulsé par Opengist ⋅ Load: 19ms⋅

Français