append-only-vec - cargo Package Compare versions

Comparing version 0.1.0 to 0.1.1

.cargo_vcs_info.json

 {
   "git": {
-    "sha1": "8b69eac3ac81c26c42eb83e727d7c18453c7c46e"
+    "sha1": "db026671fe6f1436a713430f1f36336acc1c918d"
   },
   "path_in_vcs": ""
 }

.github/workflows/rust.yml

@@ -14,2 +14,6 @@ on: [push, pull_request]
           - 1.57
+        target:
+          - x86_64-unknown-linux-gnu
+          - i686-unknown-linux-gnu
+          - aarch64-unknown-linux-gnu
     steps:
@@ -21,2 +25,3 @@ - uses: actions/checkout@v2
           toolchain: ${{ matrix.rust }}
+          target: ${{ matrix.target }}
           override: true
@@ -35,2 +40,5 @@ - uses: actions-rs/cargo@v1
           - stable
+        target:
+          - x86_64-unknown-linux-gnu
+          - i686-unknown-linux-gnu
     steps:
@@ -42,2 +50,3 @@ - uses: actions/checkout@v2
           toolchain: ${{ matrix.rust }}
+          target: ${{ matrix.target }}
           override: true
@@ -44,0 +53,0 @@ - uses: actions-rs/cargo@v1

Cargo.toml

@@ -15,4 +15,4 @@ # THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
 name = "append-only-vec"
-version = "0.1.0"
-authors = ["David Roundy <[e-mail]>"]
+version = "0.1.1"
+authors = ["David Roundy <[e-mail]>"]
 description = "Append-only, concurrent vector"
@@ -19,0 +19,0 @@ readme = "README.md"

README.md

@@ -5,2 +5,4 @@ # Append-only-vec
 
+**Note:  currently there are frequent CI failures above, which are simply due to failure to install miri to run the test.  The tests do pass when run locally.**
+
 This crate defines a single data simple structure, which is a vector to which you can only append data.  It allows you to push new data values even when there are outstanding references to elements of the `AppendOnlyVec`.  Reading from a `AppendOnlyVec` is much faster than if it had been protected by a `std::sync::RwLock`.

src/lib.rs

@@ -43,10 +43,17 @@ //! AppendOnlyVec
     reserved: AtomicUsize,
-    data: [AtomicPtr<T>; BITS - 1 - 3],
+    data: [AtomicPtr<T>; BITS_USED - 1 - 3],
 }
 
 unsafe impl<T: Send> Send for AppendOnlyVec<T> {}
-unsafe impl<T: Sync> Sync for AppendOnlyVec<T> {}
+unsafe impl<T: Sync + Send> Sync for AppendOnlyVec<T> {}
 
 const BITS: usize = std::mem::size_of::<usize>() * 8;
 
+#[cfg(target_arch = "x86_64")]
+const BITS_USED: usize = 48;
+#[cfg(all(not(target_arch = "x86_64"), target_pointer_width = "64"))]
+const BITS_USED: usize = 64;
+#[cfg(target_pointer_width = "32")]
+const BITS_USED: usize = 32;
+
 // This takes an index into a vec, and determines which data array will hold it
@@ -88,2 +95,143 @@ // (the first return value), and what the index will be into that data array
 impl<T> AppendOnlyVec<T> {
+    #[cfg(target_arch = "x86_64")]
+    const EMPTY_POINTERS: [AtomicPtr<T>; BITS_USED - 1 - 3] = [
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+    ];
+    #[cfg(target_pointer_width = "32")]
+    const EMPTY_POINTERS: [AtomicPtr<T>; BITS_USED - 1 - 3] = [
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+    ];
+    #[cfg(all(not(target_arch = "x86_64"), target_pointer_width = "64"))]
+    const EMPTY_POINTERS: [AtomicPtr<T>; BITS_USED - 1 - 3] = [
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+        AtomicPtr::new(std::ptr::null_mut()),
+    ];
     pub fn iter(&self) -> impl Iterator<Item = &T> {
@@ -168,64 +316,3 @@ (0..self.len()).map(|i| unsafe { self.get_unchecked(i) })
             reserved: AtomicUsize::new(0),
-            data: [
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-                AtomicPtr::new(std::ptr::null_mut()),
-            ],
+            data: Self::EMPTY_POINTERS,
         }
@@ -314,1 +401,24 @@ }
 }
+
+#[test]
+fn test_parallel_pushing() {
+    use std::sync::Arc;
+    let v = Arc::new(AppendOnlyVec::<u64>::new());
+    let mut threads = Vec::new();
+    const N: u64 = 100;
+    for thread_num in 0..N {
+        let v = v.clone();
+        threads.push(std::thread::spawn(move || {
+            let which1 = v.push(thread_num);
+            let which2 = v.push(thread_num);
+            assert_eq!(v[which1 as usize], thread_num);
+            assert_eq!(v[which2 as usize], thread_num);
+        }));
+    }
+    for t in threads {
+        t.join().ok();
+    }
+    for thread_num in 0..N {
+        assert_eq!(2, v.iter().copied().filter(|&x| x == thread_num).count());
+    }
+}

No alert changes

No metric changes