I created benchmarks for measuring creating new vectors/dynstacks. The standard Vec type outperformed DynStack with 2 ns vs 43 ns. Ouch.

Vec::new() promises it does not perform any allocation. Instead that is done when the first element is pushed (or if constructed with Vec::with_capacity(x)). So I thought we should do the same here.

With this PR the new_speed_dynstack benchmark goes from 43 to 4.5 ns on my machine. 89% less time. All other benchmarks remain unchanged for me.

DynStack does not auto-implement Send and Sync because it has a *mut u8 pointer. I’m like 80% sure it is Send and Sync after quickly perusing the code and have added a wrapper in my codebase that unsafely implements Send and Sync.

Is it safe to implement Send and Sync for DynStack?

fn access_native(b: &mut Bencher) {
    let mut stack = Vec::<Box<dyn Display>>::new();
    for _ in 0..1000 {
        stack.push(Box::new(black_box(0xF00BAAusize)));
    }
    b.iter(|| {
        let stack = black_box(&stack);
        for i in stack {
            black_box(i);
        }
    });
}

fn access_dynstack(b: &mut Bencher) {
    let mut stack = DynStack::<dyn Display>::new();
    for _ in 0..1000 {
        dyn_push!(stack, black_box(0xF00BAAusize));
    }
    b.iter(|| {
        let stack = black_box(&stack);
        for i in stack {
            black_box(i);
        }
    });
}

Result:

access_native           time:   [315.01 ns 317.38 ns 320.12 ns]                               
Found 3 outliers among 100 measurements (3.00%)
  2 (2.00%) high mild
  1 (1.00%) high severe

access_dynstack         time:   [1.1576 us 1.1643 us 1.1717 us]                                
Found 7 outliers among 100 measurements (7.00%)
  7 (7.00%) high mild

I think this crate is a prime example of when the dyn keyword shines. DynStack<T> is quite unclear what T is and that it has to be a trait for it to not panic. However DynStack<dyn T> makes that so much clearer.

An attempt to fix #1. Sadly it does not fix it at compile time, but rather introduce a panic at runtime. However, it still solves the memory unsoundness of possibly reading past the pointer.

I'm not able to measure any conclusive performance penalty for this. I have also tried inspecting the generated assembler, and it looks like the entire assert is being completely optimized away. So I don't see any reason not to include this safety check.

This test compiles and runs just fine:

#[test]
fn test_non_dyn() {
    let mut stack: DynStack<u8> = DynStack::new();
    for _ in 0..15 { dyn_push!(stack, 5u8); }
    let x = stack[14];
    println!("{:?}", x);
}

...but I'm quite sure it does dumb things internally, by composing and decomposing fat pointers for things where there are no fat pointers?

I use DynStack with some code that expects an ExactSizeIterator. I’ve added a wrapper in my codebase to implement that trait, but it would be cool if an ExactSizeIterator implementation were upstreamed.

struct DynStackIter<'a, T: 'a + ?Sized> {
    len: usize,
    n: usize,
    iter: dynstack::DynStackIter<'a, T>,
}

impl<'a, T: 'a + ?Sized> DynStackIter<'a, T> {
    #[inline]
    fn new(dynstack: &'a DynStack<T>) -> Self {
        DynStackIter {
            len: dynstack.len(),
            n: 0,
            iter: dynstack.iter(),
        }
    }
}

impl<'a, T: 'a + ?Sized> Iterator for DynStackIter<'a, T> {
    type Item = &'a T;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        let item = self.iter.next();
        if item.is_some() {
            self.n += 1;
        }
        item
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.len - self.n, Some(self.len - self.n))
    }
}

impl<'a, T: 'a + ?Sized> ExactSizeIterator for DynStackIter<'a, T> {
    #[inline]
    fn len(&self) -> usize {
        self.len - self.n
    }
}

I included this project as a submodule into another project, but cargo fmt annoyed me because it made the submodule path dirty. Thus I'm fixing this.

• cargo fmt

Maybe I find some cargo clippy issues, that could be trivially fixed, too.

I realize it would be very easy to reuse the same decomp_fat and recomp_fat implementations, instead of duplicating them. Reduces the risk of them becoming out of sync and one being wrong. As well as less code to understand for the confused reader.

I got rid of recomp and renamed recomp_mut to recomp. Since a *mut pointer automatically coerce to a *const if needed, only the version returning *mut T was really needed.

I pushed git tags to the commits that matched what's published to crates.io. Makes comparing git history and released versions much simpler.

And now this PR adds a change log, describing what has changed between versions. Really good practice to have IMO, since it makes understanding the project and how it has evolved way simpler. Mostly for people using the crate, and want to know how, if and why they should upgrade which version they depend on.

Thanks for this awesome crate. I really enjoyed reading the blog post you wrote on this topic as well!

This PR adds build time checks that tries its best to validate that the memory layout of a fat pointer is what we expect it to be. So hopefully this will result in the crate failing to compile on any hypothetical toolchain where the fat pointers change in any way.

I feel the main problem of relying on memory layout that has not been stabilized is that as the developer of software, I have very little control over who will compile it and with what toolchain. So even if I were to make everything using dynstack inside my crate unsafe and explain the requirements in the docs. It's very unlikely that whoever compiles a program later will check these requirements. They might very well just do cargo install very-fast-app and run it and have no idea it even uses dynstack inside :)

It's currently possible to misuse the dyn_push! macro in various ways. This PR tries to prevent the ones I found:

• $stack:expr metavariable is expanded in unsafe block. This allows the user to write unsafe code without an unsafe block because of the hidden unsafe block in the macro:

dyn_push!(&mut (*std::ptr::null_mut::<DynStack<dyn Debug>>()), 1);

• There are no checks in place that $stack is actually a DynStack. A user can pass their own struct with an unsafe push method and the macro will call it.

struct Foo;
impl Foo {
  pub unsafe fn push(&mut self, _: *mut ()) {
    std::hint::unreachable_unchecked()
  }
}
let mut t = Foo;
dyn_push!(t, ());

I've tried to add comments for most of the changes I've made. I don't know if this is the best way, let me know if you have any ideas for improving it.

The call to identify() from the newly introduced sealed MustBeDynStack trait returns &mut DynStack. Even if the user creates a struct with an identity method, they still have to return a &mut DynStack and that means the call to s.push in the macro is guaranteed to be DynStack::push. The reason why it doesn't just do something like let s: &mut DynStack = $stack; (without the trait) is because that would break if you call it as dyn_push!(stack);, and similarily let s: &mut DynStack = &mut $stack breaks if called as dyn_push!(&mut stack). Calling identity as a method will let autoref figure out whether to insert &mut or not and will allow both as before.

Would you be open to a PR adding support for a heapless version behind an alloc feature flag, using heapless::Vec?

If this is even possible, but i can't see why not.