diff options
| author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 14:29:10 +0000 |
|---|---|---|
| committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 14:29:10 +0000 |
| commit | 2aa4a82499d4becd2284cdb482213d541b8804dd (patch) | |
| tree | b80bf8bf13c3766139fbacc530efd0dd9d54394c /third_party/rust/inplace_it | |
| parent | Initial commit. (diff) | |
| download | firefox-2aa4a82499d4becd2284cdb482213d541b8804dd.tar.xz firefox-2aa4a82499d4becd2284cdb482213d541b8804dd.zip | |
Adding upstream version 86.0.1.upstream/86.0.1upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'third_party/rust/inplace_it')
| -rw-r--r-- | third_party/rust/inplace_it/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | third_party/rust/inplace_it/Cargo.toml | 23 | ||||
| -rw-r--r-- | third_party/rust/inplace_it/LICENSE.txt | 21 | ||||
| -rw-r--r-- | third_party/rust/inplace_it/README.md | 73 | ||||
| -rw-r--r-- | third_party/rust/inplace_it/src/alloc_array.rs | 63 | ||||
| -rw-r--r-- | third_party/rust/inplace_it/src/fixed_array.rs | 325 | ||||
| -rw-r--r-- | third_party/rust/inplace_it/src/guards/mod.rs | 5 | ||||
| -rw-r--r-- | third_party/rust/inplace_it/src/guards/slice_memory_guard.rs | 78 | ||||
| -rw-r--r-- | third_party/rust/inplace_it/src/guards/uninitialized_slice_memory_guard.rs | 148 | ||||
| -rw-r--r-- | third_party/rust/inplace_it/src/lib.rs | 57 | ||||
| -rw-r--r-- | third_party/rust/inplace_it/tests/drop_correctness.rs | 100 | ||||
| -rw-r--r-- | third_party/rust/inplace_it/tests/stackalloc_correctness.rs | 103 |
12 files changed, 997 insertions, 0 deletions
diff --git a/third_party/rust/inplace_it/.cargo-checksum.json b/third_party/rust/inplace_it/.cargo-checksum.json new file mode 100644 index 0000000000..f92ca4684d --- /dev/null +++ b/third_party/rust/inplace_it/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"4431a6b354414c3dcfeb818ece8789ea5523b351b5d158b88a066282728eb423","LICENSE.txt":"2d1e28cf922abfa9466d56d6858a81c57c80a8b669d86b8e57d281e633653654","README.md":"d69d531dd6ee20a7389751ab2a6f5ec1bb218c7bf60a9141139b5ea4edb347fb","src/alloc_array.rs":"dc53579073ac783cdf7c8756df455590d7507fbee62adcfdbb90802fe2cdcc95","src/fixed_array.rs":"c5a7b2f1b75fe503424a7246022cffe1dca5a92d25e47ff0b08c6dd193d361d8","src/guards/mod.rs":"30273efe8708fe8799eead390924ee4c36266e5d1827ac175e292dc3dda048ca","src/guards/slice_memory_guard.rs":"3c1c71674a28a88db3642e297d556d564feef7dbd5cad0f369e397f338817a08","src/guards/uninitialized_slice_memory_guard.rs":"980d70a1b2dcd007ee79bec5b4959feb0e3ed0adef49b12103efba0cb37fb627","src/lib.rs":"510960832a5fb447f1e4f255cc793cda73416c39a53b9c647b9bb3af78eb23e0","tests/drop_correctness.rs":"2016ed153f30a8b70e5697114b0bf90395627a4b65ea6e3f0f21a8e78e17e8d5","tests/stackalloc_correctness.rs":"41418e59d77fffb2ada793bb33a15281fa61e4b3a9f8241f80bef63a012133a6"},"package":"dd01a2a73f2f399df96b22dc88ea687ef4d76226284e7531ae3c7ee1dc5cb534"}
\ No newline at end of file diff --git a/third_party/rust/inplace_it/Cargo.toml b/third_party/rust/inplace_it/Cargo.toml new file mode 100644 index 0000000000..36f0502c1a --- /dev/null +++ b/third_party/rust/inplace_it/Cargo.toml @@ -0,0 +1,23 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies +# +# If you believe there's an error in this file please file an +# issue against the rust-lang/cargo repository. If you're +# editing this file be aware that the upstream Cargo.toml +# will likely look very different (and much more reasonable) + +[package] +edition = "2018" +name = "inplace_it" +version = "0.3.2" +authors = ["Dmitry Demin <shepardiwe@gmail.com>"] +description = "Place small arrays on the stack with a low-cost!" +readme = "README.md" +license = "MIT" +repository = "https://github.com/NotIntMan/inplace_it" + +[dependencies] diff --git a/third_party/rust/inplace_it/LICENSE.txt b/third_party/rust/inplace_it/LICENSE.txt new file mode 100644 index 0000000000..7b11e7f504 --- /dev/null +++ b/third_party/rust/inplace_it/LICENSE.txt @@ -0,0 +1,21 @@ +MIT License
+
+Copyright (c) 2018 Dmitry Demin <shepardiwe@gmail.com>
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
\ No newline at end of file diff --git a/third_party/rust/inplace_it/README.md b/third_party/rust/inplace_it/README.md new file mode 100644 index 0000000000..56a0f6b285 --- /dev/null +++ b/third_party/rust/inplace_it/README.md @@ -0,0 +1,73 @@ +# Inplace it!
+
+[](https://crates.io/crates/inplace_it)
+[](https://github.com/NotIntMan/inplace_it/blob/master/LICENSE.txt)
+[](https://github.com/NotIntMan/inplace_it/actions)
+
+Place small arrays on the stack with a low cost!
+
+The only price you should pay for this is the price of choosing
+a type based on the size of the requested array! This is just one `match` and `call`!
+
+## What?
+
+This crate is created for one purpose: allocating small arrays on the stack.
+The simplest way to use it is:
+
+```rust
+use inplace_it::{inplace_or_alloc_array, UninitializedSliceMemoryGuard};
+
+inplace_or_alloc_array(
+ 150, // size of needed array to allocate
+ |mut uninit_guard: UninitializedSliceMemoryGuard<u16>| { // and this is consumer of uninitialized memory
+ assert_eq!(160, uninit_guard.len());
+
+ {
+ // You can borrow guard to reuse memory
+ let borrowed_uninit_guard = uninit_guard.borrow();
+ // Let's initialize memory
+ // Note that borrowed_uninit_guard will be consumed (destroyed to produce initialized memory guard)
+ let init_guard = borrowed_uninit_guard.init(|index| index as u16 + 1);
+ // Memory not contains elements [1, 2, ..., 160]
+ // Lets check it. Sum of [1, 2, ..., 160] = 12880
+ let sum: u16 = init_guard.iter().sum();
+ assert_eq!(sum, 12880);
+ }
+
+ {
+ // If you don't want to reuse memory, you can init new guard directly
+ let init_guard = uninit_guard.init(|index| index as u16 * 2);
+ // Memory not contains elements [0, 2, 4, ..., 318]
+ // Lets check it. Sum of [0, 2, 4, ..., 318] = 25440
+ let sum: u16 = init_guard.iter().sum();
+ assert_eq!(sum, 25440);
+ }
+ }
+)
+```
+
+## Why?
+
+Because allocation on the stack (i.e. placing variables) is **MUCH FASTER** then usual
+allocating in the heap.
+
+## Moar!
+
+You can read the [API reference](https://docs.rs/inplace_it) for more details
+or create an [new issue](https://github.com/NotIntMan/inplace_it/issues/new)
+to submit a bug, feature request or just ask a question.
+
+## Release notes
+
+### 0.3.2
+* Placing of uninit memory moved out from `try_inplace_array` to disallow compiler to optimize it.
+
+### 0.3.1
+* Initialize with an exact-size iterator.
+
+### 0.3.0
+* API safety. No more unsafe external functions.
+* Drop correctness. No more dropping of uninitialized memory.
+
+### 0.2.2
+* Fixed drop-correctness for safe functions. Now unsafe function do not drop your data but safe function do it correctly.
diff --git a/third_party/rust/inplace_it/src/alloc_array.rs b/third_party/rust/inplace_it/src/alloc_array.rs new file mode 100644 index 0000000000..5f41ff97de --- /dev/null +++ b/third_party/rust/inplace_it/src/alloc_array.rs @@ -0,0 +1,63 @@ +use crate::guards::UninitializedSliceMemoryGuard;
+use std::mem::MaybeUninit;
+use crate::try_inplace_array;
+
+/// `alloc_array` is used when `inplace_or_alloc_array` realize that the size of requested array of `T`
+/// is too large and should be replaced in the heap.
+///
+/// It allocates a vector with `size` elements and fills it up with help of `init` closure
+/// and then pass a reference to a slice of the vector into the `consumer` closure.
+/// `consumer`'s result will be returned.
+pub fn alloc_array<T, R, Consumer: FnOnce(UninitializedSliceMemoryGuard<T>) -> R>(size: usize, consumer: Consumer) -> R {
+ unsafe {
+ let mut memory_holder = Vec::<MaybeUninit<T>>::with_capacity(size);
+ memory_holder.set_len(size);
+ let result = consumer(UninitializedSliceMemoryGuard::new(&mut *memory_holder));
+ memory_holder.set_len(0);
+ result
+ }
+}
+
+/// `inplace_or_alloc_array` is a central function of this crate.
+/// It's trying to place an array of `T` on the stack and pass the guard of memory into the
+/// `consumer` closure. `consumer`'s result will be returned.
+///
+/// If the result of array of `T` is more than 4096 then the vector will be allocated
+/// in the heap and will be used instead of stack-based fixed-size array.
+///
+/// Sometimes size of allocated array might be more than requested. For sizes larger than 32,
+/// the following formula is used: `roundUp(size/32)*32`. This is a simplification that used
+/// for keeping code short, simple and able to optimize.
+/// For example, for requested 50 item `[T; 64]` will be allocated.
+/// For 120 items - `[T; 128]` and so on.
+///
+/// Note that rounding size up is working for fixed-sized arrays only. If function decides to
+/// allocate a vector then its size will be equal to requested.
+///
+/// # Examples
+///
+/// ```rust
+/// use inplace_it::{
+/// inplace_or_alloc_array,
+/// UninitializedSliceMemoryGuard,
+/// };
+///
+/// let sum: u16 = inplace_or_alloc_array(100, |uninit_guard: UninitializedSliceMemoryGuard<u16>| {
+/// assert_eq!(uninit_guard.len(), 128);
+/// // For now, our memory is placed/allocated but uninitialized.
+/// // Let's initialize it!
+/// let guard = uninit_guard.init(|index| index as u16 * 2);
+/// // For now, memory contains content like [0, 2, 4, 6, ..., 252, 254]
+/// guard.iter().sum()
+/// });
+/// // Sum of [0, 2, 4, 6, ..., 252, 254] = sum of [0, 1, 2, 3, ..., 126, 127] * 2 = ( 127 * (127+1) ) / 2 * 2
+/// assert_eq!(sum, 127 * 128);
+/// ```
+pub fn inplace_or_alloc_array<T, R, Consumer>(size: usize, consumer: Consumer) -> R
+ where Consumer: FnOnce(UninitializedSliceMemoryGuard<T>) -> R
+{
+ match try_inplace_array(size, consumer) {
+ Ok(result) => result,
+ Err(consumer) => alloc_array(size, consumer),
+ }
+}
diff --git a/third_party/rust/inplace_it/src/fixed_array.rs b/third_party/rust/inplace_it/src/fixed_array.rs new file mode 100644 index 0000000000..918ce8b205 --- /dev/null +++ b/third_party/rust/inplace_it/src/fixed_array.rs @@ -0,0 +1,325 @@ +use crate::guards::UninitializedSliceMemoryGuard;
+use core::mem::MaybeUninit;
+
+/// This trait is a extended copy of unstable
+/// [core::array::FixedSizeArray](core::array::FixedSizeArray).
+///
+/// This is not a perfect solution. Inheritance from `AsRef<[T]> + AsMut<[T]>` would be preferable.
+/// But until we cannot implement `std` traits for `std` types so that inheritance limits us
+/// and we cannot use `[T; n]` where `n > 32`.
+pub trait FixedArray {
+ type Item;
+ const LEN: usize;
+ fn as_slice(&self) -> &[Self::Item];
+ fn as_slice_mut(&mut self) -> &mut [Self::Item];
+}
+
+macro_rules! impl_fixed_array_for_array {
+ ($($length: expr),+) => {
+ $(
+ impl<T> FixedArray for [T; $length] {
+ type Item = T;
+ const LEN: usize = $length;
+ #[inline]
+ fn as_slice(&self) -> &[Self::Item] {
+ self
+ }
+ #[inline]
+ fn as_slice_mut(&mut self) -> &mut [Self::Item] {
+ self
+ }
+ }
+ )+
+ };
+}
+
+macro_rules! impl_fixed_array_for_array_group_32 {
+ ($($length: expr),+) => {
+ $(
+ impl_fixed_array_for_array!(
+ $length, $length + 1, $length + 2, $length + 3,
+ $length + 4, $length + 5, $length + 6, $length + 7,
+ $length + 8, $length + 9, $length + 10, $length + 11,
+ $length + 12, $length + 13, $length + 14, $length + 15,
+ $length + 16, $length + 17, $length + 18, $length + 19,
+ $length + 20, $length + 21, $length + 22, $length + 23,
+ $length + 24, $length + 25, $length + 26, $length + 27,
+ $length + 28, $length + 29, $length + 30, $length + 31
+ );
+ )+
+ };
+}
+
+impl_fixed_array_for_array_group_32!(0, 32, 64, 96);
+
+#[cfg(not(target_pointer_width = "8"))]
+impl_fixed_array_for_array!(
+ 128, 160, 192, 224, 256, 288, 320, 352, 384, 416, 448, 480, 512, 544, 576, 608, 640, 672, 704,
+ 736, 768, 800, 832, 864, 896, 928, 960, 992, 1024, 1056, 1088, 1120, 1152, 1184, 1216, 1248,
+ 1280, 1312, 1344, 1376, 1408, 1440, 1472, 1504, 1536, 1568, 1600, 1632, 1664, 1696, 1728, 1760,
+ 1792, 1824, 1856, 1888, 1920, 1952, 1984, 2016, 2048, 2080, 2112, 2144, 2176, 2208, 2240, 2272,
+ 2304, 2336, 2368, 2400, 2432, 2464, 2496, 2528, 2560, 2592, 2624, 2656, 2688, 2720, 2752, 2784,
+ 2816, 2848, 2880, 2912, 2944, 2976, 3008, 3040, 3072, 3104, 3136, 3168, 3200, 3232, 3264, 3296,
+ 3328, 3360, 3392, 3424, 3456, 3488, 3520, 3552, 3584, 3616, 3648, 3680, 3712, 3744, 3776, 3808,
+ 3840, 3872, 3904, 3936, 3968, 4000, 4032, 4064, 4096
+);
+
+/// `try_inplace_array` trying to place an array of `T` on the stack and pass the guard of memory into the
+/// `consumer` closure. `consumer`'s result will be returned as `Ok(result)`.
+///
+/// If the result of array of `T` is more than 4096 then `Err(consumer)` will be returned.
+///
+/// Sometimes size of allocated array might be more than requested. For sizes larger than 32,
+/// the following formula is used: `roundUp(size/32)*32`. This is a simplification that used
+/// for keeping code short, simple and able to optimize.
+/// For example, for requested 50 item `[T; 64]` will be allocated.
+/// For 120 items - `[T; 128]` and so on.
+///
+/// Note that rounding size up is working for fixed-sized arrays only. If function decides to
+/// allocate a vector then its size will be equal to requested.
+///
+/// # Examples
+///
+/// ```rust
+/// use inplace_it::{
+/// try_inplace_array,
+/// UninitializedSliceMemoryGuard,
+/// };
+///
+/// let sum = try_inplace_array(100, |uninit_guard: UninitializedSliceMemoryGuard<u16>| {
+/// assert_eq!(uninit_guard.len(), 128);
+/// // For now, our memory is placed/allocated but uninitialized.
+/// // Let's initialize it!
+/// let guard = uninit_guard.init(|index| index as u16 * 2);
+/// // For now, memory contains content like [0, 2, 4, 6, ..., 252, 254]
+/// let sum: u16 = guard.iter().sum();
+/// sum
+/// });
+/// // Sum of [0, 2, 4, 6, ..., 252, 254] = sum of [0, 1, 2, 3, ..., 126, 127] * 2 = ( 127 * (127+1) ) / 2 * 2
+/// match sum {
+/// Ok(sum) => assert_eq!(sum, 127 * 128),
+/// Err(_) => unreachable!("Placing fails"),
+/// };
+/// ```
+pub fn try_inplace_array<T, R, Consumer>(size: usize, consumer: Consumer) -> Result<R, Consumer>
+ where Consumer: FnOnce(UninitializedSliceMemoryGuard<T>) -> R
+{
+ macro_rules! inplace {
+ ($size: expr) => {unsafe {
+ indirect(move || {
+ let mut memory: [MaybeUninit<T>; $size] = MaybeUninit::uninit().assume_init();
+ consumer(UninitializedSliceMemoryGuard::new(&mut memory))
+ })
+ }};
+ }
+ #[cfg(target_pointer_width = "8")]
+ let result = match size {
+ 0 => inplace!(0),
+ 1 => inplace!(1),
+ 2 => inplace!(2),
+ 3 => inplace!(3),
+ 4 => inplace!(4),
+ 5 => inplace!(5),
+ 6 => inplace!(6),
+ 7 => inplace!(7),
+ 8 => inplace!(8),
+ 9 => inplace!(9),
+ 10 => inplace!(10),
+ 11 => inplace!(11),
+ 12 => inplace!(12),
+ 13 => inplace!(13),
+ 14 => inplace!(14),
+ 15 => inplace!(15),
+ 16 => inplace!(16),
+ 17 => inplace!(17),
+ 18 => inplace!(18),
+ 19 => inplace!(19),
+ 20 => inplace!(20),
+ 21 => inplace!(21),
+ 22 => inplace!(22),
+ 23 => inplace!(23),
+ 24 => inplace!(24),
+ 25 => inplace!(25),
+ 26 => inplace!(26),
+ 27 => inplace!(27),
+ 28 => inplace!(28),
+ 29 => inplace!(29),
+ 30 => inplace!(30),
+ 31 => inplace!(31),
+ 32 => inplace!(32),
+ 33..=64 => inplace!(64),
+ 65..=96 => inplace!(96),
+ 97..=127 => inplace!(127),
+ _ => return Err(consumer),
+ };
+ #[cfg(not(target_pointer_width = "8"))]
+ let result = match size {
+ 0 => inplace!(0),
+ 1 => inplace!(1),
+ 2 => inplace!(2),
+ 3 => inplace!(3),
+ 4 => inplace!(4),
+ 5 => inplace!(5),
+ 6 => inplace!(6),
+ 7 => inplace!(7),
+ 8 => inplace!(8),
+ 9 => inplace!(9),
+ 10 => inplace!(10),
+ 11 => inplace!(11),
+ 12 => inplace!(12),
+ 13 => inplace!(13),
+ 14 => inplace!(14),
+ 15 => inplace!(15),
+ 16 => inplace!(16),
+ 17 => inplace!(17),
+ 18 => inplace!(18),
+ 19 => inplace!(19),
+ 20 => inplace!(20),
+ 21 => inplace!(21),
+ 22 => inplace!(22),
+ 23 => inplace!(23),
+ 24 => inplace!(24),
+ 25 => inplace!(25),
+ 26 => inplace!(26),
+ 27 => inplace!(27),
+ 28 => inplace!(28),
+ 29 => inplace!(29),
+ 30 => inplace!(30),
+ 31 => inplace!(31),
+ 32 => inplace!(32),
+ 33..=64 => inplace!(64),
+ 65..=96 => inplace!(96),
+ 97..=128 => inplace!(128),
+ 129..=160 => inplace!(160),
+ 161..=192 => inplace!(192),
+ 193..=224 => inplace!(224),
+ 225..=256 => inplace!(256),
+ 257..=288 => inplace!(288),
+ 289..=320 => inplace!(320),
+ 321..=352 => inplace!(352),
+ 353..=384 => inplace!(384),
+ 385..=416 => inplace!(416),
+ 417..=448 => inplace!(448),
+ 449..=480 => inplace!(480),
+ 481..=512 => inplace!(512),
+ 513..=544 => inplace!(544),
+ 545..=576 => inplace!(576),
+ 577..=608 => inplace!(608),
+ 609..=640 => inplace!(640),
+ 641..=672 => inplace!(672),
+ 673..=704 => inplace!(704),
+ 705..=736 => inplace!(736),
+ 737..=768 => inplace!(768),
+ 769..=800 => inplace!(800),
+ 801..=832 => inplace!(832),
+ 833..=864 => inplace!(864),
+ 865..=896 => inplace!(896),
+ 897..=928 => inplace!(928),
+ 929..=960 => inplace!(960),
+ 961..=992 => inplace!(992),
+ 993..=1024 => inplace!(1024),
+ 1025..=1056 => inplace!(1056),
+ 1057..=1088 => inplace!(1088),
+ 1089..=1120 => inplace!(1120),
+ 1121..=1152 => inplace!(1152),
+ 1153..=1184 => inplace!(1184),
+ 1185..=1216 => inplace!(1216),
+ 1217..=1248 => inplace!(1248),
+ 1249..=1280 => inplace!(1280),
+ 1281..=1312 => inplace!(1312),
+ 1313..=1344 => inplace!(1344),
+ 1345..=1376 => inplace!(1376),
+ 1377..=1408 => inplace!(1408),
+ 1409..=1440 => inplace!(1440),
+ 1441..=1472 => inplace!(1472),
+ 1473..=1504 => inplace!(1504),
+ 1505..=1536 => inplace!(1536),
+ 1537..=1568 => inplace!(1568),
+ 1569..=1600 => inplace!(1600),
+ 1601..=1632 => inplace!(1632),
+ 1633..=1664 => inplace!(1664),
+ 1665..=1696 => inplace!(1696),
+ 1697..=1728 => inplace!(1728),
+ 1729..=1760 => inplace!(1760),
+ 1761..=1792 => inplace!(1792),
+ 1793..=1824 => inplace!(1824),
+ 1825..=1856 => inplace!(1856),
+ 1857..=1888 => inplace!(1888),
+ 1889..=1920 => inplace!(1920),
+ 1921..=1952 => inplace!(1952),
+ 1953..=1984 => inplace!(1984),
+ 1985..=2016 => inplace!(2016),
+ 2017..=2048 => inplace!(2048),
+ 2049..=2080 => inplace!(2080),
+ 2081..=2112 => inplace!(2112),
+ 2113..=2144 => inplace!(2144),
+ 2145..=2176 => inplace!(2176),
+ 2177..=2208 => inplace!(2208),
+ 2209..=2240 => inplace!(2240),
+ 2241..=2272 => inplace!(2272),
+ 2273..=2304 => inplace!(2304),
+ 2305..=2336 => inplace!(2336),
+ 2337..=2368 => inplace!(2368),
+ 2369..=2400 => inplace!(2400),
+ 2401..=2432 => inplace!(2432),
+ 2433..=2464 => inplace!(2464),
+ 2465..=2496 => inplace!(2496),
+ 2497..=2528 => inplace!(2528),
+ 2529..=2560 => inplace!(2560),
+ 2561..=2592 => inplace!(2592),
+ 2593..=2624 => inplace!(2624),
+ 2625..=2656 => inplace!(2656),
+ 2657..=2688 => inplace!(2688),
+ 2689..=2720 => inplace!(2720),
+ 2721..=2752 => inplace!(2752),
+ 2753..=2784 => inplace!(2784),
+ 2785..=2816 => inplace!(2816),
+ 2817..=2848 => inplace!(2848),
+ 2849..=2880 => inplace!(2880),
+ 2881..=2912 => inplace!(2912),
+ 2913..=2944 => inplace!(2944),
+ 2945..=2976 => inplace!(2976),
+ 2977..=3008 => inplace!(3008),
+ 3009..=3040 => inplace!(3040),
+ 3041..=3072 => inplace!(3072),
+ 3073..=3104 => inplace!(3104),
+ 3105..=3136 => inplace!(3136),
+ 3137..=3168 => inplace!(3168),
+ 3169..=3200 => inplace!(3200),
+ 3201..=3232 => inplace!(3232),
+ 3233..=3264 => inplace!(3264),
+ 3265..=3296 => inplace!(3296),
+ 3297..=3328 => inplace!(3328),
+ 3329..=3360 => inplace!(3360),
+ 3361..=3392 => inplace!(3392),
+ 3393..=3424 => inplace!(3424),
+ 3425..=3456 => inplace!(3456),
+ 3457..=3488 => inplace!(3488),
+ 3489..=3520 => inplace!(3520),
+ 3521..=3552 => inplace!(3552),
+ 3553..=3584 => inplace!(3584),
+ 3585..=3616 => inplace!(3616),
+ 3617..=3648 => inplace!(3648),
+ 3649..=3680 => inplace!(3680),
+ 3681..=3712 => inplace!(3712),
+ 3713..=3744 => inplace!(3744),
+ 3745..=3776 => inplace!(3776),
+ 3777..=3808 => inplace!(3808),
+ 3809..=3840 => inplace!(3840),
+ 3841..=3872 => inplace!(3872),
+ 3873..=3904 => inplace!(3904),
+ 3905..=3936 => inplace!(3936),
+ 3937..=3968 => inplace!(3968),
+ 3969..=4000 => inplace!(4000),
+ 4001..=4032 => inplace!(4032),
+ 4033..=4064 => inplace!(4064),
+ 4065..=4096 => inplace!(4096),
+ _ => return Err(consumer),
+ };
+ Ok(result)
+}
+
+#[inline(never)]
+fn indirect<R>(fun: impl FnOnce() -> R) -> R {
+ fun()
+}
diff --git a/third_party/rust/inplace_it/src/guards/mod.rs b/third_party/rust/inplace_it/src/guards/mod.rs new file mode 100644 index 0000000000..e4fcf53fbd --- /dev/null +++ b/third_party/rust/inplace_it/src/guards/mod.rs @@ -0,0 +1,5 @@ +mod uninitialized_slice_memory_guard;
+mod slice_memory_guard;
+
+pub use uninitialized_slice_memory_guard::*;
+pub use slice_memory_guard::*;
diff --git a/third_party/rust/inplace_it/src/guards/slice_memory_guard.rs b/third_party/rust/inplace_it/src/guards/slice_memory_guard.rs new file mode 100644 index 0000000000..80b73136a8 --- /dev/null +++ b/third_party/rust/inplace_it/src/guards/slice_memory_guard.rs @@ -0,0 +1,78 @@ +use core::{
+ ops::{Deref, DerefMut},
+ mem::{MaybeUninit, transmute},
+ ptr::{drop_in_place, write},
+};
+
+/// Guard-struct used for correctly initialize uninitialized memory and `drop` it when guard goes out of scope.
+/// Usually, you *should not* use this struct to handle your memory.
+///
+/// ### Safety
+///
+/// If you use this struct manually, remember: `&mut [MaybeUninit<T>]`'s content will be overwriten while initialization.
+/// So it is *not safe* to apply this struct to already initialized data and it can lead to *memory leaks*.
+///
+/// ### Example
+/// ```rust
+/// use inplace_it::SliceMemoryGuard;
+/// use std::mem::MaybeUninit;
+///
+/// // Placing uninitialized memory
+/// let mut memory: [MaybeUninit<usize>; 100] = unsafe { MaybeUninit::uninit().assume_init() };
+/// // Initializing guard
+/// let mut memory_guard = unsafe {
+/// SliceMemoryGuard::new(
+/// // Borrowing memory
+/// &mut memory,
+/// // Forwarding initializer
+/// |index| index * 2
+/// )
+/// };
+///
+/// // For now, memory contains content like [0, 2, 4, 6, ..., 196, 198]
+///
+/// // Using memory
+/// // Sum of [0, 2, 4, 6, ..., 196, 198] = sum of [0, 1, 2, 3, ..., 98, 99] * 2 = ( 99 * (99+1) ) / 2 * 2
+/// let sum: usize = memory_guard.iter().sum();
+/// assert_eq!(sum, 99 * 100);
+///
+/// ```
+pub struct SliceMemoryGuard<'a, T> {
+ memory: &'a mut [MaybeUninit<T>],
+}
+
+impl<'a, T> SliceMemoryGuard<'a, T> {
+ /// Initialize memory guard
+ #[inline]
+ pub unsafe fn new(memory: &'a mut [MaybeUninit<T>], mut init: impl FnMut(usize) -> T) -> Self {
+ for (index, item) in memory.into_iter().enumerate() {
+ write(item.as_mut_ptr(), init(index));
+ }
+ SliceMemoryGuard { memory }
+ }
+}
+
+impl<'a, T> Deref for SliceMemoryGuard<'a, T> {
+ type Target = [T];
+
+ #[inline]
+ fn deref(&self) -> &Self::Target {
+ unsafe { transmute::<&[MaybeUninit<T>], &[T]>(&self.memory) }
+ }
+}
+
+impl<'a, T> DerefMut for SliceMemoryGuard<'a, T> {
+ #[inline]
+ fn deref_mut(&mut self) -> &mut Self::Target {
+ unsafe { transmute::<&mut [MaybeUninit<T>], &mut [T]>(&mut self.memory) }
+ }
+}
+
+impl<'a, T> Drop for SliceMemoryGuard<'a, T> {
+ #[inline]
+ fn drop(&mut self) {
+ for item in self.memory.into_iter() {
+ unsafe { drop_in_place(item.as_mut_ptr()); }
+ }
+ }
+}
diff --git a/third_party/rust/inplace_it/src/guards/uninitialized_slice_memory_guard.rs b/third_party/rust/inplace_it/src/guards/uninitialized_slice_memory_guard.rs new file mode 100644 index 0000000000..ae125051e0 --- /dev/null +++ b/third_party/rust/inplace_it/src/guards/uninitialized_slice_memory_guard.rs @@ -0,0 +1,148 @@ +use core::{
+ mem::MaybeUninit,
+ ops::{
+ RangeBounds,
+ Bound,
+ },
+};
+use crate::guards::SliceMemoryGuard;
+
+/// Guard-struct used to own uninitialized memory and provide functions for initializing it.
+/// Usually, you *should not* use this struct to handle your memory.
+///
+/// Initializing functions spawns [SliceMemoryGuard] which will provide access to initialized memory.
+/// It also means memory can be used again after [SliceMemoryGuard] is dropped.
+///
+/// ### Safety
+///
+/// If you use this struct manually, remember: `&mut [MaybeUninit<T>]`'s content will be overwriten while initialization.
+/// So it is *not safe* to apply this struct to already initialized data and it can lead to *memory leaks*.
+///
+/// ### Example
+/// ```rust
+/// use inplace_it::UninitializedSliceMemoryGuard;
+/// use std::mem::MaybeUninit;
+///
+/// // Placing uninitialized memory
+/// let mut memory: [MaybeUninit<usize>; 100] = unsafe { MaybeUninit::uninit().assume_init() };
+/// // Initializing guard
+/// let mut uninit_memory_guard = unsafe { UninitializedSliceMemoryGuard::new(&mut memory) };
+///
+/// {
+/// // Initializing memory
+/// let mut memory_guard = uninit_memory_guard
+/// // we need to call .borrow() because out init-API consumes uninit-guard
+/// .borrow()
+/// // then passing initialize closure and the guard is ok
+/// .init(|index| index * 2);
+/// // For now, memory contains content like [0, 2, 4, 6, ..., 196, 198]
+///
+/// // Using memory
+/// // Sum of [0, 2, 4, 6, ..., 196, 198] = sum of [0, 1, 2, 3, ..., 98, 99] * 2 = ( 99 * (99+1) ) / 2 * 2
+/// let sum: usize = memory_guard.iter().sum();
+/// assert_eq!(sum, 99 * 100);
+/// // memory_guard dropped here
+/// }
+///
+/// // uninit_memory_guard is available again now
+///
+/// {
+/// // Initializing memory
+/// let mut memory_guard = uninit_memory_guard.init(|index| index * index);
+/// // For now, memory contains content like [0, 1, 4, 9, ..., 9604, 9801]
+///
+/// // Using memory
+/// // Sum of [0, 1, 4, 9, ..., 9604, 9801] = 99 * (99 + 1) * (2 * 99 + 1) / 6
+/// let sum: usize = memory_guard.iter().sum();
+/// assert_eq!(sum, 99 * (99 + 1) * (2 * 99 + 1) / 6);
+/// // memory_guard dropped here
+/// }
+///
+/// ```
+///
+/// [SliceMemoryGuard]: struct.SliceMemoryGuard.html
+pub struct UninitializedSliceMemoryGuard<'a, T> {
+ memory: &'a mut [MaybeUninit<T>],
+}
+
+impl<'a, T> UninitializedSliceMemoryGuard<'a, T> {
+ /// Initialize memory guard
+ #[inline]
+ pub unsafe fn new(memory: &'a mut [MaybeUninit<T>]) -> Self {
+ Self { memory }
+ }
+
+ /// Get the length of memory slice
+ #[inline]
+ pub fn len(&self) -> usize {
+ self.memory.len()
+ }
+
+ /// Construct new memory guard with new bounds.
+ ///
+ /// Can be used to shrink memory.
+ ///
+ /// ### Panics
+ ///
+ /// Panic can be reached when given `range` is out of memory's range.
+ #[inline]
+ pub fn slice(self, range: impl RangeBounds<usize>) -> Self {
+ let start = match range.start_bound() {
+ Bound::Excluded(n) => n.saturating_add(1),
+ Bound::Included(n) => *n,
+ Bound::Unbounded => 0,
+ };
+ let end = match range.end_bound() {
+ Bound::Excluded(n) => *n,
+ Bound::Included(n) => n.saturating_add(1),
+ Bound::Unbounded => self.memory.len(),
+ };
+ Self {
+ memory: &mut self.memory[start..end],
+ }
+ }
+
+ /// Initialize memory and make new guard of initialized memory.
+ /// Given `init` closure will be used to initialize elements of memory slice.
+ #[inline]
+ pub fn init(self, init: impl FnMut(usize) -> T) -> SliceMemoryGuard<'a, T> {
+ unsafe {
+ SliceMemoryGuard::new(self.memory, init)
+ }
+ }
+
+ /// Initialize memory and make new guard of initialized memory.
+ /// Given `source` slice will be used to initialize elements of memory slice.
+ /// Returned guard will contain sliced memory to `source`'s length.
+ ///
+ /// ### Panics
+ ///
+ /// Panic can be reached when given `source`'s range is out of memory's range.
+ #[inline]
+ pub fn init_copy_of(self, source: &[T]) -> SliceMemoryGuard<'a, T>
+ where T: Clone
+ {
+ self.slice(..source.len()).init(|index| { source[index].clone() })
+ }
+
+ /// Initialize memory and make new guard of initialized memory.
+ /// Given `iter` exact-size iterator will be used to initialize elements of memory slice.
+ /// Returned guard will contain sliced memory to `iter`'s length.
+ ///
+ /// ### Panics
+ ///
+ /// Panic can be reached when given `iter`'s length is out of memory's range.
+ #[inline]
+ pub fn init_with_iter(self, mut iter: impl ExactSizeIterator<Item = T>) -> SliceMemoryGuard<'a, T> {
+ self.slice(..iter.len()).init(|_index| { iter.next().unwrap() })
+ }
+
+ /// Create new uninit memory guard with less or equal lifetime to original guard's lifetime.
+ /// This function should be used to reuse memory because init-API consumes the guard.
+ #[inline]
+ pub fn borrow(&mut self) -> UninitializedSliceMemoryGuard<T> {
+ unsafe {
+ UninitializedSliceMemoryGuard::new(self.memory)
+ }
+ }
+}
diff --git a/third_party/rust/inplace_it/src/lib.rs b/third_party/rust/inplace_it/src/lib.rs new file mode 100644 index 0000000000..7c13bd2c16 --- /dev/null +++ b/third_party/rust/inplace_it/src/lib.rs @@ -0,0 +1,57 @@ +//! # Inplace it!
+//!
+//! Place small arrays on the stack with a low cost!
+//!
+//! The only price you should pay for this is the price of choosing
+//! a type based on the size of the requested array! This is just one `match`!
+//!
+//! ## What?
+//!
+//! This crate is created for one purpose: allocating small arrays on the stack.
+//! The simplest way to use it is:
+//!
+//! ```rust
+//! use inplace_it::{inplace_or_alloc_array, UninitializedSliceMemoryGuard};
+//!
+//! inplace_or_alloc_array(
+//! 150, // size of needed array to allocate
+//! |mut uninit_guard: UninitializedSliceMemoryGuard<u16>| { // and this is consumer of uninitialized memory
+//! assert_eq!(160, uninit_guard.len());
+//!
+//! {
+//! // You can borrow guard to reuse memory
+//! let borrowed_uninit_guard = uninit_guard.borrow();
+//! // Let's initialize memory
+//! // Note that borrowed_uninit_guard will be consumed (destroyed to produce initialized memory guard)
+//! let init_guard = borrowed_uninit_guard.init(|index| index as u16 + 1);
+//! // Memory not contains elements [1, 2, ..., 160]
+//! // Lets check it. Sum of [1, 2, ..., 160] = 12880
+//! let sum: u16 = init_guard.iter().sum();
+//! assert_eq!(sum, 12880);
+//! }
+//!
+//! {
+//! // If you don't want to reuse memory, you can init new guard directly
+//! let init_guard = uninit_guard.init(|index| index as u16 * 2);
+//! // Memory not contains elements [0, 2, 4, ..., 318]
+//! // Lets check it. Sum of [0, 2, 4, ..., 318] = 25440
+//! let sum: u16 = init_guard.iter().sum();
+//! assert_eq!(sum, 25440);
+//! }
+//! }
+//! )
+//! ```
+//!
+//! ## Why?
+//!
+//! Because allocation on the stack (i.e. placing variables) is **MUCH FASTER** then usual
+//! allocating in the heap.
+//!
+
+mod guards;
+mod fixed_array;
+mod alloc_array;
+
+pub use guards::*;
+pub use fixed_array::*;
+pub use alloc_array::*;
diff --git a/third_party/rust/inplace_it/tests/drop_correctness.rs b/third_party/rust/inplace_it/tests/drop_correctness.rs new file mode 100644 index 0000000000..4913bb48cc --- /dev/null +++ b/third_party/rust/inplace_it/tests/drop_correctness.rs @@ -0,0 +1,100 @@ +use std::cell::Cell;
+use inplace_it::*;
+use std::mem::MaybeUninit;
+
+struct DropCounter {
+ count: Cell<usize>,
+}
+
+impl DropCounter {
+ fn with_current<F: FnOnce(&DropCounter) -> R, R>(f: F) -> R {
+ thread_local!(
+ static COUNTER: DropCounter = DropCounter {count: Cell::new(0)};
+ );
+ COUNTER.with(f)
+ }
+
+ #[inline]
+ fn get() -> usize {
+ DropCounter::with_current(|c| c.count.get())
+ }
+
+ #[inline]
+ fn inc() {
+ DropCounter::with_current(|c| c.count.set(c.count.get() + 1));
+ }
+
+ #[inline]
+ fn clear() {
+ DropCounter::with_current(|c| c.count.set(0));
+ }
+}
+
+struct DropCounterTrigger(u8 /* One byte to avoid zero-sized types optimizations */);
+
+impl DropCounterTrigger {
+ fn new() -> Self {
+ Self(228)
+ }
+}
+
+impl Drop for DropCounterTrigger {
+ #[inline]
+ fn drop(&mut self) {
+ DropCounter::inc();
+ }
+}
+
+#[test]
+fn maybe_uninit_works_as_expected() {
+ DropCounter::clear();
+ drop(MaybeUninit::<DropCounterTrigger>::uninit());
+ assert_eq!(DropCounter::get(), 0);
+ DropCounter::clear();
+ drop(MaybeUninit::<DropCounterTrigger>::new(DropCounterTrigger::new()));
+ assert_eq!(DropCounter::get(), 0);
+ DropCounter::clear();
+ let mut memory = MaybeUninit::<DropCounterTrigger>::new(DropCounterTrigger::new());
+ unsafe { core::ptr::drop_in_place(memory.as_mut_ptr()); }
+ drop(memory);
+ assert_eq!(DropCounter::get(), 1);
+}
+
+#[test]
+fn inplace_array_should_correctly_drop_values() {
+ for i in (0..4096).step_by(8) {
+ DropCounter::clear();
+ try_inplace_array(i, |guard: UninitializedSliceMemoryGuard<DropCounterTrigger>| {
+ assert!(guard.len() >= i);
+ }).map_err(|_| format!("Cannot inplace array of {} size", i)).unwrap();
+ assert_eq!(DropCounter::get(), 0);
+ DropCounter::clear();
+ let len = try_inplace_array(i, |guard| {
+ let len = guard.len();
+ guard.init(|_| DropCounterTrigger::new());
+ len
+ }).map_err(|_| format!("Cannot inplace array of {} size", i)).unwrap();
+ assert_eq!(DropCounter::get(), len);
+ DropCounter::clear();
+ try_inplace_array(i, |guard| {
+ let guard = guard.slice(..i);
+ assert_eq!(guard.len(), i);
+ guard.init(|_| DropCounterTrigger::new());
+ }).map_err(|_| format!("Cannot inplace array of {} size", i)).unwrap();
+ assert_eq!(DropCounter::get(), i);
+ }
+}
+
+#[test]
+fn alloc_array_should_correctly_drop_values() {
+ for i in (0..4096).step_by(8) {
+ DropCounter::clear();
+ alloc_array(i, |_guard: UninitializedSliceMemoryGuard<DropCounterTrigger>| {});
+ assert_eq!(DropCounter::get(), 0);
+ DropCounter::clear();
+ alloc_array(i, |guard| {
+ guard.init(|_| DropCounterTrigger::new());
+ });
+ assert_eq!(DropCounter::get(), i);
+ }
+}
diff --git a/third_party/rust/inplace_it/tests/stackalloc_correctness.rs b/third_party/rust/inplace_it/tests/stackalloc_correctness.rs new file mode 100644 index 0000000000..d87e95e04a --- /dev/null +++ b/third_party/rust/inplace_it/tests/stackalloc_correctness.rs @@ -0,0 +1,103 @@ +use inplace_it::*;
+use std::cmp::Ordering;
+
+#[inline(never)]
+fn get_stack_pointer_value() -> usize {
+ use std::mem::transmute;
+
+ let begin_of_function_stack: usize = 0;
+ unsafe {
+ transmute::<&usize, usize>(&begin_of_function_stack)
+ }
+}
+
+fn calculate_stack_consumption(begin: usize, end: usize) -> usize {
+ if begin >= end {
+ begin - end
+ } else {
+ end - begin
+ }
+}
+
+/// This test measures stack memory consumption from 0 to 4096 items by step 32
+/// Then, it calculates "tangent of an angle" (y/x) from "point of zero" (0 items and it's stack size).
+///
+/// It bad cases, when compiler optimizes `try_inplace_array` function so that it doesn't make sense,
+/// difference between lowest and highest borders is huge.
+///
+/// In good cases, all "points" are form almost a line so all "tangents of an angle" do not have much difference among themselves.
+/// And the difference of the borders is small. It's about 0 <= D <= 2.
+/// Also, "tangents of an angle" about 0 < T <= 3. In bad cases tangents are VERY HUGE.
+///
+/// This is what that test checks.
+#[test]
+fn stack_memory_should_allocate_no_more_than_needed() {
+ #[inline(never)]
+ fn inplace_and_sum(size: usize) -> usize {
+ let begin = get_stack_pointer_value();
+ let result = try_inplace_array(size, |mem: UninitializedSliceMemoryGuard<usize>| {
+ let end = get_stack_pointer_value();
+ let mem = mem.init(|i| i);
+ let mut sum = 0usize;
+ for i in mem.iter() {
+ sum += *i as usize;
+ }
+ // To sure sum operation was not optimized to no-op
+ let len = mem.len();
+ assert_eq!(sum, if len > 0 {
+ len * (len - 1) / 2
+ } else {
+ 0
+ });
+ let stack_consumption = calculate_stack_consumption(begin, end);
+ stack_consumption
+ });
+ match result {
+ Ok(result) => result,
+ Err(_) => panic!("Inplace should never fail is this test"),
+ }
+ }
+
+ fn calc_differential_coefficients(mut data: impl Iterator<Item = (usize, usize)>) -> impl Iterator<Item = f64> {
+ let (zero_x, zero_y) = data.next()
+ .expect("Input iterator should not be empty");
+
+ data.map(move |(x, y)| {
+ let dx = (x - zero_x) as f64;
+ let dy = (y - zero_y) as f64;
+ dy / dx
+ })
+ }
+
+ fn calc_differentials_borders_dispersion(data: &[f64]) -> f64 {
+ let min = data.iter().min_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal))
+ .expect("Input dataset should not be empty");
+ let max = data.iter().max_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Equal))
+ .expect("Input dataset should not be empty");
+ max - min
+ }
+
+ let stack_sizes = (0..=4096).step_by(32)
+ .map(|length| {
+ let stack_size = inplace_and_sum(length);
+ const USIZE_LAYOUT: usize = std::mem::size_of::<usize>() + std::mem::align_of::<usize>(); // usize layout coefficient
+ let stack_size = stack_size / USIZE_LAYOUT;
+ (length, stack_size)
+ })
+ .collect::<Vec<_>>();
+
+ // dbg!(&stack_sizes);
+
+ let stack_sizes_differentials = calc_differential_coefficients(stack_sizes.into_iter())
+ .collect::<Vec<_>>();
+
+ for differential in &stack_sizes_differentials {
+ assert!(*differential <= 3.0);
+ }
+
+ let differentials_borders_dispersion = calc_differentials_borders_dispersion(&stack_sizes_differentials);
+
+ // dbg!(stack_sizes_differentials, differentials_borders_dispersion);
+
+ assert!(differentials_borders_dispersion <= 2.0);
+}
|