A stack for rust trait objects that minimizes allocations

Overview

dynstack

A stack for trait objects that minimizes allocations

COMPATIBILITY NOTE: dynstack relies on an underspecified fat pointer representation. Though it isn't expected to change in the foreseeable future, this crate expects Rust 1.34's representation.

Usage

dynstack can mostly replace anywhere you'd use a stack, or a vector that doesn't require removal from its center.

let mut stack = DynStack::<dyn Debug>::new();
dyn_push!(stack, "hello, world!");
dyn_push!(stack, 0usize);
dyn_push!(stack, [1, 2, 3, 4, 5, 6]);

for item in stack.iter() {
    println!("{:?}", item);
}

// prints:
//  "hello, world!"
//  0
//  [1, 2, 3, 4, 5, 6]
Comments
  • Dont allocate on new

    Dont allocate on new

    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.

    opened by faern 5
  • Is DynStack Send + Sync?

    Is DynStack Send + Sync?

    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?

    opened by calebmer 3
  • Pure access is 4x slow than native

    Pure access is 4x slow than native

    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
    
    opened by breezewish 3
  • Upgrade crate to Rust 2018 edition

    Upgrade crate to Rust 2018 edition

    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.

    opened by faern 2
  • Assert at runtime that DynTrait is used on only trait objects

    Assert at runtime that DynTrait is used on only trait objects

    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.

    opened by faern 2
  • Can use dynstack for non-dyn data

    Can use dynstack for non-dyn data

    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?

    opened by diwic 2
  • Implement ExactSizeIterator and size_hint for DynStackIter

    Implement ExactSizeIterator and size_hint for DynStackIter

    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
        }
    }
    
    opened by calebmer 1
  • Misc improvements

    Misc improvements

    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.

    opened by zseri 1
  • Reuse one implementation of compose/decompose fat ptrs

    Reuse one implementation of compose/decompose fat ptrs

    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.

    opened by faern 1
  • Add a changelog

    Add a changelog

    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.

    opened by faern 1
  • Check fat pointer memory layout at build time

    Check fat pointer memory layout at build time

    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 :)

    opened by faern 1
  • Guard macro against unsafe misuse

    Guard macro against unsafe misuse

    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.

    opened by y21 0
  • Alloc free behind feature flag?

    Alloc free behind feature flag?

    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.

    opened by MathiasKoch 2
Owner
Gui Andrade
Interested in emulation, compilers, RISC-V, and other random fun things.
Gui Andrade
A lending iterator trait based on generic associated types and higher-rank trait bounds

A lending iterator trait based on higher-rank trait bounds (HRTBs) A lending iterator is an iterator which lends mutable borrows to the items it retur

Sebastiano Vigna 6 Oct 23, 2023
async-alloc-counter measures max allocations in a future invocation

async-alloc-counter measures max allocations in a future invocation see examples/ for usage This allocator can be used as follows: use async_alloc_cou

Geoffroy Couprie 2 Dec 3, 2021
Stack buffer provides alternatives to Buf{Reader,Writer} allocated on the stack instead of the heap.

StackBuf{Reader,Writer} Stack buffer provides alternatives to BufReader and BufWriter allocated on the stack instead of the heap. Its implementation i

Alex Saveau 14 Nov 20, 2022
Remoc 🦑 — Remote multiplexed objects and channels for Rust

Remoc ?? — remote multiplexed objects and channels Remoc makes remote interaction between Rust programs seamless and smooth. Over a single underlying

ENQT GmbH 98 Dec 21, 2022
A framework for iterating over collections of types implementing a trait without virtual dispatch

zero_v Zero_V is an experiment in defining behavior over collections of objects implementing some trait without dynamic polymorphism.

null 13 Jul 28, 2022
Generate enum from a trait, with converters between them

Derive macro for Rust that turns traits into enums, providing tools for calling funtions over channels

Vitaly Shukela 16 Nov 3, 2022
A lending version of the `Stream` trait

lending-stream A lending version of Stream API Docs | Releases | Contributing Installation $ cargo add lending-stream Safety This crate uses #![deny(u

Yosh 5 Aug 14, 2023
Rust + Yew + Axum + Tauri, full-stack Rust development for Desktop apps.

rust-yew-axum-tauri-desktop template Rust + Yew + Axum + Tauri, full-stack Rust development for Desktop apps. Crates frontend: Yew frontend app for de

Jet Li 54 Dec 23, 2022
Stack unwinding library in Rust

Unwinding library in Rust and for Rust This library serves two purposes: Provide a pure Rust alternative to libgcc_eh or libunwind. Provide easier unw

Gary Guo 51 Nov 4, 2022
A Bancho implementation made in Rust for the *cursed* stack.

cu.rs A Bancho implementation made in Rust for the cursed stack. THIS PROJECT IS REALLY UNFINISHED AND IN ITS EARLY STAGES A drag and drop replacement

RealistikOsu! 5 Feb 1, 2022
Rust macro to make recursive function run on the heap (i.e. no stack overflow).

Decurse Example #[decurse::decurse] // ?? Slap this on your recursive function and stop worrying about stack overflow! fn factorial(x: u32) -> u32 {

Wisha W. 18 Dec 28, 2022
Awesome full-stack template using Yew and Rust

Docker + Actix + Yew Full Stack Template ??‍?? YouTube videos Full Stack Rust App Template using Yew + Actix! https://youtu.be/oCiGjrpGk4A Add Docker

Security Union 143 Jun 22, 2023
A memory efficient immutable string type that can store up to 24* bytes on the stack

compact_str A memory efficient immutable string type that can store up to 24* bytes on the stack. * 12 bytes for 32-bit architectures About A CompactS

Parker Timmerman 342 Jan 2, 2023
k-mer counter in Rust using the rust-bio and rayon crates

krust is a k-mer counter written in Rust and run from the command line that will output canonical k-mers and their frequency across the records in a f

null 14 Jan 7, 2023
Experimental Rust tool for generating FFI definitions allowing many other languages to call Rust code

Diplomat is an experimental Rust tool for generating FFI definitions allowing many other languages to call Rust code. With Diplomat, you can simply define Rust APIs to be exposed over FFI and get high-level C, C++, and JavaScript bindings automatically!

null 255 Dec 30, 2022
Aws-sdk-rust - AWS SDK for the Rust Programming Language

The AWS SDK for Rust This repo contains the new AWS SDK for Rust (the SDK) and its public roadmap. Please Note: The SDK is currently released as a dev

Amazon Web Services - Labs 2k Jan 3, 2023
A lightning fast version of tmux-fingers written in Rust, copy/pasting tmux like vimium/vimperator

tmux-thumbs A lightning fast version of tmux-fingers written in Rust for copy pasting with vimium/vimperator like hints. Usage Press ( prefix + Space

Ferran Basora 598 Jan 2, 2023
A command-line tool collection to assist development written in RUST

dtool dtool is a command-line tool collection to assist development Table of Contents Description Usage Tips Installation Description Now dtool suppor

GB 314 Dec 18, 2022
Rust mid-level IR Abstract Interpreter

MIRAI MIRAI is an abstract interpreter for the Rust compiler's mid-level intermediate representation (MIR). It is intended to become a widely used sta

Facebook Experimental 793 Jan 2, 2023