pierce/lib.rs
1/*! Avoid double indirection in nested smart pointers.
2
3The [`Pierce`] stuct allows you to cache the deref result of doubly-nested smart pointers.
4
5# Quick Example
6
7```
8# use std::sync::Arc;
9# use pierce::Pierce;
10let vec: Vec<i32> = vec![1, 2, 3];
11let arc_vec = Arc::new(vec);
12let pierce = Pierce::new(arc_vec);
13
14// Here, the execution jumps directly to the slice to call `.get(...)`.
15// Without Pierce it would have to jump to the Vec first,
16// than from the Vec to the slice.
17pierce.get(0).unwrap();
18```
19
20# Nested Smart Pointers
21
22Smart Pointers can be nested to - in a way - combine their functionalities.
23For example, with `Arc<Vec<i32>>`, a slice of i32 is managed by the wrapping [`Vec`] that is wrapped again by the [`Arc`][std::sync::Arc].
24
25However, nesting comes at the cost of **double indirection**:
26when we want to access the underlying data,
27we must first follow the outer pointer to where the inner pointer lies,
28then follow the inner pointer to where the underlying data is. Two [Deref]-ings. Two jumps.
29
30```
31# use std::sync::Arc;
32let vec: Vec<i32> = vec![1, 2, 3];
33let arc_vec = Arc::new(vec);
34
35// Here, the `Arc<Vec<i32>>` is first dereferenced to the `Vec<i32>`,
36// then the Vec is dereferenced to the underlying i32 slice,
37// on which `.get(...)` is called.
38arc_vec.get(0).unwrap();
39```
40
41# Pierce
42
43The [`Pierce`] struct, provided by this crate,
44can help reduce the performance cost of nesting smart pointers by **caching the deref result**.
45We double-deref the nested smart pointer at the start, storing the address where the inner pointer points to.
46We can then access the underlying data by just jumping to the stored address. One jump.
47
48Here's a diagram of what it *might* look like.
49
50```text
51 ┌───────────────────────────┬───────────────────────────────┬──────────────────────────────────────────┐
52 │ Stack │ Heap │ Heap │
53┌────────────┼───────────────────────────┼───────────────────────────────┼──────────────────────────────────────────┤
54│ T │ │ │ │
55│ │ ┌──────────────────┐ │ ┌───────────────────┐ │ ┌──────────────────────────────────┐ │
56│ │ │Outer Pointer │ │ │Inner Pointer │ │ │Target │ │
57│ │ │ │ │ │ │ │ │ │ │
58│ │ │ T ────────────────────────► T::Target ─────────────────► <T::Target as Deref>::Target │ │
59│ │ │ │ │ │ │ │ │ │ │
60│ │ └──────────────────┘ │ └───────────────────┘ │ └──────────────────────────────────┘ │
61│ │ │ │ │
62├────────────┼───────────────────────────┼───────────────────────────────┼──────────────────────────────────────────┤
63│ Pierce<T> │ │ │ │
64│ │ ┌──────────────────┐ │ ┌───────────────────┐ │ ┌──────────────────────────────────┐ │
65│ │ │Outer Pointer │ │ │Inner Pointer │ │ │Target │ │
66│ │ │ │ │ │ │ │ │ │ │
67│ │ │ T ────────────────────────► T::Target ─────────────────► <T::Target as Deref>::Target │ │
68│ │ │ │ │ │ │ │ │ ▲ │ │
69│ │ ├──────────────────┤ │ └───────────────────┘ │ └────────────────│─────────────────┘ │
70│ │ │Cache │ │ │ │ │
71│ │ │ │ │ │ │ │
72│ │ │ ptr ───────────────────────────────────────────────────────────────────┘ │
73│ │ │ │ │ │ │
74│ │ └──────────────────┘ │ │ │
75│ │ │ │ │
76└────────────┴───────────────────────────┴───────────────────────────────┴──────────────────────────────────────────┘
77```
78
79# Usage
80
81`Pierce<T>` can be created with `Pierce::new(...)`. `T` should be a doubly-nested pointer (e.g. `Arc<Vec<_>>`, `Box<Box<_>>`).
82
83[deref][Deref::deref]-ing a `Pierce<T>` returns `&<T::Target as Deref>::Target`,
84i.e. the deref target of the deref target of `T` (the outer pointer that is wrapped by Pierce),
85i.e. the deref target of the inner pointer.
86
87You can also obtain a borrow of just `T` (the outer pointer) using `.borrow_inner()`.
88
89See the docs at [`Pierce`] for more details.
90
91## Deeper Nesting
92
93A `Pierce` reduces two jumps to one.
94If you have deeper nestings, you can wrap it multiple times.
95
96```
97# use pierce::Pierce;
98let triply_nested: Box<Box<Box<i32>>> = Box::new(Box::new(Box::new(42)));
99assert_eq!(***triply_nested, 42); // <- Three jumps!
100let pierce_twice = Pierce::new(Pierce::new(triply_nested));
101assert_eq!(*pierce_twice, 42); // <- Just one jump!
102```
103
104# Benchmarks
105
106These benchmarks probably won't represent your use case at all because:
107* They are engineered to make Pierce look good.
108* Compiler optimizations are hard to control.
109* CPU caches and predictions are hard to control. (I bet the figures will be very different on your CPU.)
110* Countless other reasons why you shouldn't trust synthetic benchmarks.
111
112*Do your own benchmarks on real-world uses*.
113
114That said, here are my results:
115
116**Benchmark 1**: Read items from a `Box<Vec<usize>>`, with simulated memory fragmentation.
117
118**Benchmark 2**: Read items from a `SlowBox<Vec<usize>>`. `SlowBox` deliberately slow down `deref()` call greatly.
119
120**Benchmark 3**: Read several `Box<Box<i64>>`.
121
122Time taken by `Pierce<T>` version compared to `T` version.
123
124| Run | Benchmark 1 | Benchmark 2 | Benchmark 3 |
125|-----------|-------------------|-------------------|-------------------|
126| 1 | -40.23% | -99.69% | -5.68% |
127| 2 | -40.59% | -99.69% | -5.16% |
128| 3 | -40.70% | -99.68% | +2.69% |
129| 4 | -39.85% | -99.68% | -5.35% |
130| 5 | -38.90% | -99.71% | -5.02% |
131| 6 | -39.12% | -99.69% | -5.53% |
132| 7 | -40.51% | -99.69% | -6.09% |
133| 8 | -26.99% | -99.71% | -6.43% |
134
135See the benchmarks' code [here](https://github.com/wishawa/pierce/tree/main/src/bin/benchmark/main.rs).
136
137# Limitations
138
139## Immutable Only
140
141Pierce only work with immutable data.
142**Mutability is not supported at all** because I'm pretty sure it would be impossible to implement soundly.
143(If you have an idea please share.)
144
145## Requires `StableDeref`
146
147Pointer wrapped by Pierce must be [`StableDeref`].
148If your pointer type meets the conditions required, you can `unsafe impl StableDeref for T {}` on it.
149The trait is re-exported at `pierce::StableDeref`.
150
151The vast majority of pointers are `StableDeref`,
152including [Box], [Vec], [String], [Rc][std::rc::Rc], [Arc][std::sync::Arc].
153*/
154
155use std::{ops::Deref, ptr::NonNull};
156
157pub use stable_deref_trait::StableDeref;
158
159/** Cache doubly-nested pointers.
160
161A `Pierce<T>` stores `T` along with a cached pointer to `<T::Target as Deref>::Target`.
162*/
163pub struct Pierce<T>
164where
165 T: StableDeref,
166 T::Target: StableDeref,
167{
168 outer: T,
169 target: NonNull<<T::Target as Deref>::Target>,
170}
171
172impl<T> Pierce<T>
173where
174 T: StableDeref,
175 T::Target: StableDeref,
176{
177 /** Create a new Pierce.
178
179 Create a Pierce out of the given nested pointer.
180 This method derefs `T` twice and cache the address where the inner pointer points to.
181
182 Deref-ing the created Pierce returns the cached reference directly. `deref` is not called on `T`.
183 */
184 #[inline]
185 pub fn new(outer: T) -> Self {
186 let inner: &T::Target = outer.deref();
187 let target: &<T::Target as Deref>::Target = inner.deref();
188 let target = NonNull::from(target);
189 Self { outer, target }
190 }
191
192 /** Borrow the outer pointer `T`.
193
194 You can then call the methods on `&T`.
195
196 You can even call `deref` twice on `&T` yourself to bypass Pierce's cache:
197 ```
198 # use pierce::Pierce;
199 use std::ops::Deref;
200 let pierce = Pierce::new(Box::new(Box::new(5)));
201 let outer: &Box<Box<i32>> = pierce.borrow_outer();
202 let inner: &Box<i32> = outer.deref();
203 let target: &i32 = inner.deref();
204 assert_eq!(*target, 5);
205 ```
206
207 */
208 #[inline]
209 pub fn borrow_outer(&self) -> &T {
210 &self.outer
211 }
212
213 /** Get the outer pointer `T` out.
214
215 Like `into_inner()` elsewhere, this consumes the Pierce and return the wrapped pointer.
216 */
217 #[inline]
218 pub fn into_outer(self) -> T {
219 self.outer
220 }
221}
222
223unsafe impl<T> Send for Pierce<T>
224where
225 T: StableDeref + Send,
226 T::Target: StableDeref,
227 <T::Target as Deref>::Target: Sync,
228{
229}
230
231unsafe impl<T> Sync for Pierce<T>
232where
233 T: StableDeref + Sync,
234 T::Target: StableDeref,
235 <T::Target as Deref>::Target: Sync,
236{
237}
238
239unsafe impl<T> StableDeref for Pierce<T>
240where
241 T: StableDeref,
242 T::Target: StableDeref,
243{
244}
245
246impl<T> Clone for Pierce<T>
247where
248 T: StableDeref + Clone,
249 T::Target: StableDeref,
250{
251 #[inline]
252 fn clone(&self) -> Self {
253 Self::new(self.outer.clone())
254 }
255}
256
257impl<T> Deref for Pierce<T>
258where
259 T: StableDeref,
260 T::Target: StableDeref,
261{
262 type Target = <T::Target as Deref>::Target;
263 #[inline]
264 fn deref(&self) -> &Self::Target {
265 unsafe { self.target.as_ref() }
266 /* SAFETY:
267 The Pierce must still be alive (not dropped) when this is called,
268 and thus the outer pointer must still be alive.
269
270 The Pierce might be moved, but it must be StableDeref so moving is ok.
271
272 The inner pointer (which is the deref result of the outer pointer) must last as long as the outer pointer,
273 so it must still be alive too.
274
275 The target (which is the deref result of the inner pointer) must last as long as the inner pointer,
276 so it must still be alive too.
277
278 It might seem that interior mutability can cause an issue,
279 but it actually is impossible to get long-living reference out of a RefCell or Mutex,
280 so you can't deref to anything inside an interior-mutable cell anyway.
281 */
282 }
283}
284
285impl<T> AsRef<<T::Target as Deref>::Target> for Pierce<T>
286where
287 T: StableDeref,
288 T::Target: StableDeref,
289{
290 #[inline]
291 fn as_ref(&self) -> &<T::Target as Deref>::Target {
292 &**self
293 }
294}
295
296impl<T> Default for Pierce<T>
297where
298 T: StableDeref + Default,
299 T::Target: StableDeref,
300{
301 fn default() -> Self {
302 Self::new(T::default())
303 }
304}
305
306#[cfg(test)]
307mod tests {
308 use super::*;
309
310 #[test]
311 fn test_arc_vec() {
312 use std::cell::RefCell;
313 use std::ops::AddAssign;
314 use std::sync::Arc;
315
316 let v = vec![RefCell::new(1), RefCell::new(2)];
317 let a = Arc::new(v);
318 let p1 = Pierce::new(a);
319 let p2 = p1.clone();
320 p1.get(0).unwrap().borrow_mut().add_assign(5);
321 assert_eq!(*p2.get(0).unwrap().borrow(), 6);
322 }
323
324 #[test]
325 fn test_rc_string() {
326 use std::rc::Rc;
327
328 let v = String::from("hello world");
329 let a = Rc::new(v);
330 let pierce = Pierce::new(a);
331 assert_eq!(&*pierce, "hello world");
332 }
333
334 #[test]
335 fn test_box_vec() {
336 let v = vec![1, 2, 3];
337 let a = Box::new(v);
338 let pierce = Pierce::new(a);
339 assert_eq!(*pierce.get(2).unwrap(), 3);
340 }
341
342 #[test]
343 fn test_triply_nested() {
344 let b: Box<Box<Box<i32>>> = Box::new(Box::new(Box::new(42)));
345 let pierce_once = Pierce::new(b);
346 assert_eq!(*Box::deref(Pierce::deref(&pierce_once)), 42);
347 let pierce_twice = Pierce::new(pierce_once);
348 assert_eq!(*Pierce::deref(&pierce_twice), 42);
349 }
350
351 #[test]
352 fn test_send() {
353 use std::sync::Arc;
354 let p1 = Pierce::new(Arc::new(String::from("asdf")));
355 let p2 = p1.clone();
356 let h1 = std::thread::spawn(move || {
357 assert_eq!(&*p1, "asdf");
358 });
359 let h2 = std::thread::spawn(move || {
360 assert_eq!(&*p2, "asdf");
361 });
362 h1.join().unwrap();
363 h2.join().unwrap();
364 }
365 #[test]
366 fn test_sync() {
367 let p: Pierce<Box<String>> = Pierce::new(Box::new(String::from("hello world")));
368 let p1: &'static Pierce<Box<String>> = Box::leak(Box::new(p));
369 let p2: &'static Pierce<Box<String>> = p1;
370 let h1 = std::thread::spawn(move || {
371 assert_eq!(&**p1, "hello world");
372 });
373 let h2 = std::thread::spawn(move || {
374 assert_eq!(&**p2, "hello world");
375 });
376 h1.join().unwrap();
377 h2.join().unwrap();
378 }
379
380 #[test]
381 fn test_size_of() {
382 use std::mem::size_of;
383 use std::sync::Arc;
384 fn inner_test<T>()
385 where
386 T: StableDeref,
387 T::Target: StableDeref,
388 {
389 assert_eq!(
390 size_of::<T>() + size_of::<&<T::Target as Deref>::Target>(),
391 size_of::<Pierce<T>>()
392 );
393 }
394 inner_test::<Box<Vec<i32>>>();
395 inner_test::<Box<Box<i32>>>();
396 inner_test::<Arc<Vec<i32>>>();
397 inner_test::<Box<Arc<i32>>>();
398 }
399}