The most primitive and the fastest implementation of a fixed-size last-in-first-out stack on stack in Rust, for Copy-implementing types

Overview

cargo crates.io codecov Hits-of-Code Lines of code License docs.rs

This is the simplest and the fastest (faster than Vec!) implementation of a last-in-first-out stack data structure, on stack, when stack elements are Copy implementing primitives. This is basically a wrapper around an uninitialized array. When it is created on stack, its elements contain no specific data. Then, when you push_unchecked(x), the head of the stack is moved forward and x is placed into the element of the array. When you pop_unchecked(), the head is moved backward and the data is retrieved from the array. There are no boundary checks, that's why both push_unchecked() and pop_unchecked() may lead to undefined behavior. Use push() and pop(), which are safer, but slower. For even slower but even safer behavior, you can use try_push() and try_pop().

First, add this to Cargo.toml:

[dependencies]
microstack = "0.0.7"

Then, use it like this (mind the unsafe blocks, they give the fastest performance, but undefined behavior if you go over the stack boundaries):

use microstack::Stack;
let mut s : Stack<&str, 10> = Stack::new(); // allocation on stack
unsafe { s.push_unchecked("foo") }; // no boundary checks here
unsafe { s.push_unchecked("bar") }; // and here
assert_eq!("bar", unsafe { s.pop_unchecked() }); // and here again
assert_eq!(1, s.len());

Pay attention, here the stack is created with an extra const generic argument equal to 10. This is the total size of the stack data structure, which is allocated on stack when ::new() is called.

Read the API documentation.

How to Contribute

First, install Rust and then:

$ cargo test -vv

If everything goes well, fork repository, make changes, send us a pull request. We will review your changes and apply them to the master branch shortly, provided they don't violate our quality standards. To avoid frustration, before sending us your pull request please run cargo test again. Also, run cargo fmt and cargo clippy.

Also, before you start making changes, run benchmarks:

$ rustup run nightly cargo bench

Then, after the changes you make, run it again. Compare the results. If your changes degrade performance, think twice before submitting a pull request.

Comments
  • Update Rust crate serde to 1.0.163

    Update Rust crate serde to 1.0.163

    Mend Renovate

    This PR contains the following updates:

    | Package | Type | Update | Change | |---|---|---|---| | serde (source) | dependencies | patch | 1.0.160 -> 1.0.163 |


    Release Notes

    serde-rs/serde

    v1.0.163

    Compare Source

    • Eliminate build script from serde_derive crate to slightly reduce build time (#​2442, thanks @​taiki-e)

    v1.0.162

    Compare Source

    • Support deserializing flattened adjacently tagged enums from data formats which represent fields as bytes, such as the csv crate (#​2377, thanks @​mfro)

      #[derive(Deserialize)]
      pub struct Record {
          common: u64,
          #[serde(flatten)]
          kind: Kind,
      }
      
      #[derive(Deserialize)]
      #[serde(tag = "kind", content = "parameter", rename_all = "lowercase")]
      enum Kind {
          Foo(u64),
          Bar(bool),
      }
      
      common,kind,parameter
      1,foo,42
      2,bar,true
      

    v1.0.161

    Compare Source

    • Improve error messages produced by serde_test on test failure (#​2435, thanks @​Mingun)

    Configuration

    📅 Schedule: Branch creation - At any time (no schedule defined), Automerge - At any time (no schedule defined).

    🚦 Automerge: Disabled by config. Please merge this manually once you are satisfied.

    Rebasing: Whenever PR becomes conflicted, or you tick the rebase/retry checkbox.

    🔕 Ignore: Close this PR and you won't be reminded about this update again.


    • [ ] If you want to rebase/retry this PR, check this box

    This PR has been generated by Mend Renovate. View repository job log here.

    opened by renovate[bot] 6
  • `try_push`

    `try_push`

    In Rust methods named try_* return Option/Result.

    When https://github.com/yegor256/microstack/issues/17 is fixed and push is renamed to push_unchecked, I suggest to rename the current try_push method to just push and also introduce fn try_push(..) -> Result<(), V>.

    opened by VictorBulba 4
  • Update Rust crate serde to 1.0.164

    Update Rust crate serde to 1.0.164

    Mend Renovate

    This PR contains the following updates:

    | Package | Type | Update | Change | |---|---|---|---| | serde (source) | dependencies | patch | 1.0.163 -> 1.0.164 |


    Release Notes

    serde-rs/serde

    v1.0.164

    Compare Source


    Configuration

    📅 Schedule: Branch creation - At any time (no schedule defined), Automerge - At any time (no schedule defined).

    🚦 Automerge: Disabled by config. Please merge this manually once you are satisfied.

    Rebasing: Whenever PR becomes conflicted, or you tick the rebase/retry checkbox.

    🔕 Ignore: Close this PR and you won't be reminded about this update again.


    • [ ] If you want to rebase/retry this PR, check this box

    This PR has been generated by Mend Renovate. View repository job log here.

    opened by renovate[bot] 3
  • Configure Renovate

    Configure Renovate

    Mend Renovate

    Welcome to Renovate! This is an onboarding PR to help you understand and configure settings before regular Pull Requests begin.

    🚦 To activate Renovate, merge this Pull Request. To disable Renovate, simply close this Pull Request unmerged.


    Detected Package Files

    • Cargo.toml (cargo)
    • .github/workflows/cargo.yml (github-actions)
    • .github/workflows/pdd.yml (github-actions)
    • .github/workflows/tarpaulin.yml (github-actions)
    • .github/workflows/up.yml (github-actions)
    • .github/workflows/xcop.yml (github-actions)

    Configuration Summary

    Based on the default config's presets, Renovate will:

    • Start dependency updates only once this onboarding PR is merged
    • Enable Renovate Dependency Dashboard creation.
    • Use semantic commit type fix for dependencies and chore for all others if semantic commits are in use.
    • Ignore node_modules, bower_components, vendor and various test/tests directories.
    • Group known monorepo packages together.
    • Use curated list of recommended non-monorepo package groupings.
    • Apply crowd-sourced package replacement rules.
    • Apply crowd-sourced workarounds for known problems with packages.

    🔡 Would you like to change the way Renovate is upgrading your dependencies? Simply edit the renovate.json in this branch with your custom config and the list of Pull Requests in the "What to Expect" section below will be updated the next time Renovate runs.


    What to Expect

    With your current configuration, Renovate will create 1 Pull Request:

    Update Rust crate serde to 1.0.163
    • Schedule: ["at any time"]
    • Branch name: renovate/serde-1.x
    • Merge into: master
    • Upgrade serde to 1.0.163

    ❓ Got questions? Check out Renovate's Docs, particularly the Getting Started section. If you need any further assistance then you can also request help here.


    This PR has been generated by Mend Renovate. View repository job log here.

    opened by renovate[bot] 1
  • Dependency Dashboard

    Dependency Dashboard

    This issue lists Renovate updates and detected dependencies. Read the Dependency Dashboard docs to learn more.

    This repository currently has no open or pending branches.

    Detected dependencies

    cargo
    Cargo.toml
    • serde 1.0.164
    • bincode 1.3.3
    github-actions
    .github/workflows/cargo.yml
    • actions/checkout v3
    • actions/setup-java v3
    • actions-rs/toolchain v1
    .github/workflows/pdd.yml
    • actions/checkout v3
    .github/workflows/tarpaulin.yml
    • actions/checkout v3
    • actions-rs/toolchain v1
    • actions-rs/tarpaulin v0.1
    • codecov/codecov-action v3
    .github/workflows/up.yml
    • actions/checkout v3
    • peter-evans/create-pull-request v5
    .github/workflows/xcop.yml
    • actions/checkout v3

    • [ ] Check this box to trigger a request for Renovate to run again on this repository
    opened by renovate[bot] 0
  • Do not convert internal buffer from MaybeUninit<[V; N]> to [V; N]

    Do not convert internal buffer from MaybeUninit<[V; N]> to [V; N]

    I briefly looked at the code and it seems there is no reason to convert it.

    Even more, it violates Rust's safety rules, because the memory is not initialized.

    telegram-cloud-photo-size-2-5408890794368157446-y

    image

    So make items to be MaybeUninit

    image
    opened by VictorBulba 3
  • Stack::into_iter() is slower than Vec::into_iter()

    Stack::into_iter() is slower than Vec::into_iter()

    According to the results of vs_vec.rs bench, we are slower in iterating than Vec:

    $ rustup run nightly cargo bench
    ...
         Running benches/vs_vec.rs (target/release/deps/vs_vec-903d5e84934e313a)
    
    running 2 tests
    test stack_push_and_pop ... bench:       6,058 ns/iter (+/- 449)
    test vec_push_and_pop   ... bench:       3,425 ns/iter (+/- 138)
    

    The problem is in the into_iter() method. Let's figure out where is the lag and fix.

    bug help wanted 
    opened by yegor256 0
Releases(0.0.7)
  • 0.0.7(May 15, 2023)

    See #20, release log:

    • 6156a20a79ab94d4efc2aaca8b9507c963ec18b6 by @yegor256: #20 doc
    • 0b8face0cd370c5fc40c8f7a6688e98f11cebf56 by @yegor256: #20 pop_unchecked()

    Released by Rultor 1.74.7, see build log

    Source code(tar.gz)
    Source code(zip)
  • 0.0.6(May 15, 2023)

    See #18, release log:

    • a5fdc30141ef35c13dd143ef3dd1e6026a847993 by @yegor256: #18 try_push() introduced
    • 904667a924924e5374f2b64de25f9490a0de8b34 by @yegor256: #17 push() renamed to push_unc...
    • 11dd7793006f2d96aed053971b8d5075ce35bee1 by @yegor256: test
    • 5a470a0050d5c33d40decd7c1908d2633adfaa5d by @yegor256: test
    • 8b146110e350cb53d4784dc5445370b426dd864f by @yegor256: test
    • 1108421145c2ba1500f14902c408e4da11b82a30 by @yegor256: two tests
    • bc53df3303a3b7ce7bd75e23d3bb43b618ba7c96 by @yegor256: doc
    • 962cb616ac3a27046766106bffef0eabc0f10f52 by @yegor256: lifo
    • da7058a2275528d94a9991d42bb3c7142eb0ffb5 by @yegor256: doc
    • 2ece30511f02997dee526d24e2b2195d6eabf4e0 by @yegor256: vec
    • 0c2118613cf0a083c7b1610b8fd9add905613b9b by @yegor256: test for str
    • 4ef5a28caa2ce923565603bf9aa16ea7f1e704e9 by @yegor256: doc
    • 77a8c129faec18f191294172d2f5a1b7343f011e by @yegor256: Merge pull request #11 from ye...
    • 9c20f3fdd8b1702dfacea569f62e69f7c4f98e82 by @rultor: new version in README

    Released by Rultor 1.74.7, see build log

    Source code(tar.gz)
    Source code(zip)
  • 0.0.5(May 12, 2023)

    See #10, release log:

    • e4b101c6caded4793028ba94ad1a008449c2c123 by @yegor256: #10 iter() in bench
    • eaf9dbb3e36015e8634bc20aba0ca7b428ab10e7 by @yegor256: #10 less into_iter
    • 7e40ffd7982bbd18bbd2fcf29560a892112ee4b2 by @yegor256: #10 re
    • d46f5a20b2bb2811190f4cf62ffc007bce046629 by @yegor256: #10 iter()
    • c0201312a36114fd0675b744cfd88e58893ad600 by @yegor256: more checks
    • cb295ee2bb75a82ed808d13f7056abbcbb8c22b9 by @yegor256: doc
    • 6d88415138e5b9d64539402419780775e7f03d76 by @yegor256: Merge pull request #9 from yeg...

    Released by Rultor 1.74.7, see build log

    Source code(tar.gz)
    Source code(zip)
  • 0.0.4(May 12, 2023)

    See #8, release log:

    • 0e4b9772329a1179846bb95a6bde5ff14e274cef by @yegor256: Merge branch 'master' of githu...
    • c44db2a940998767752b3d22ab4cc6ad500ef6a0 by @yegor256: no Clone trait
    • 4e8771f46fe40696173a6f2803c64504cd703c50 by @yegor256: try_push() and try_pop()
    • 0e1b84749559305b221cc51d139ed77f06f435bf by @yegor256: faster clone()
    • c016bb2682a03d6b915d5d48be6c26954d79a525 by @yegor256: iterator
    • 1630b3b261d58b69e609a6be6c68ac5613370a93 by @yegor256: Copy works
    • 1c2eac73a65d40093728b1aff02c4bee7a607597 by @yegor256: Copy mandatory
    • 1ccee4d5b16adc49ccf5eb2988c22492eb466c31 by @yegor256: faster than vec on push and po...
    • 72bd3b038e914caa68cf4fc301ca8bb3fc7f2d57 by @yegor256: Merge pull request #7 from yeg...
    • f505bdabeb13dfe15f69ff656af740eb0ced1a1c by @rultor: new version in README

    Released by Rultor 1.74.7, see build log

    Source code(tar.gz)
    Source code(zip)
  • 0.0.3(May 6, 2023)

    See #6, release log:

    • 8c54fb4a5aa0daa3004fc454f3d7029aac777fa6 by @yegor256: #6 format
    • 1da6bd3e1673ef6475a58ec2a88f05c457bd0785 by @yegor256: #6 extra test
    • b4cf92684776da378a734d414ab08f555a1ae193 by @yegor256: #6 extra test
    • bd3ff4c90a3bf3832e70f0ea485fd824a480d4ab by @yegor256: #6 lifetime
    • 9c2678a022a54e5151c32e8107f21f609af2b339 by @yegor256: typo
    • 29a3e23b722d3809cd4dba507816a0cb995eb7a2 by @yegor256: doc
    • 74b5234a709d5d8d6ff4bb9b0d3da71ec5ea6fcd by @yegor256: Merge pull request #5 from yeg...
    • 1140f3d4710b3584319518112ce82398e2eafc06 by @rultor: new version in README

    Released by Rultor 1.74.7, see build log

    Source code(tar.gz)
    Source code(zip)
  • 0.0.2(May 6, 2023)

    See #4, release log:

    • 3a143f32e6dc38c96377b90dcddab7ccc63bd1d7 by @yegor256: #4 doc
    • 64b188df611488e54e471b835350cb3a4ed3902d by @yegor256: #4 typo
    • 5444ea242781ca557c1c39404ce79a451fd092be by @yegor256: #4 into_iter
    • 6500f1f09f778e1ac71014e6422803f4fa2543a2 by @yegor256: Merge pull request #2 from yeg...
    • 1463601b28a83be732ac3f941fb8b841821264e7 by @yegor256: bench fixed
    • 26f97d6c27f6e2aa2d9d64dbac83e994b5bcdb2b by @yegor256: new version in README
    • 2bdcf12e13488ea971b0dcb6ea5c41094e6f3779 by @yegor256: doc

    Released by Rultor 1.74.7, see build log

    Source code(tar.gz)
    Source code(zip)
  • 0.0.1(May 6, 2023)

    See #1, release log:

    • c30abb958d86df7674de4a0374675c4e61159ee3 by @yegor256: clean
    • 80d1e2cda3b9e96e397afb46b52f53acc2406361 by @yegor256: doc
    • 966c1da7bc6a8f9a31a51202003304baec6076b3 by @yegor256: first

    Released by Rultor 1.74.7, see build log

    Source code(tar.gz)
    Source code(zip)
Owner
Yegor Bugayenko
Author of "Elegant Objects" book series (buy them on Amazon); architect of @objectionary; founder of @zerocracy; creator of @zold-io
Yegor Bugayenko
Primitive Roblox Lua executor

rulx Primitive Roblox Lua executor Build cargo build --target i686-pc-windows-msvc --release License rulx is free and open source software licensed un

ORC Free and Open Source Software 5 Aug 16, 2022
Finding the shortest and fastest path in the graph to optimize traffic.

Finding the shortest and fastest path in the graph to optimize traffic. Because we don't want to spend unnecessary time searching for the optimal route back to home.

Tomáš Petržela 2 Oct 26, 2021
Rusty Reflective DLL Injection - A small reflective loader in Rust 4KB in size

Reflective Loader in Rust (4KB in size) A small reflective loader PoC in Rust. I remade this from my old project (https://github.com/memN0ps/arsenal-r

null 97 Apr 8, 2023
Adds size optimizations to any Perseus app automatically.

Perseus Size Optimization Plugin WARNING: Until Perseus #66 is fixed, this plugin can actually increase overall binary size! Once that issue is fixed

arctic_hen7 6 Aug 14, 2022
Abstract GPU Project - The easiest and most ergonomic GPU library

Abstract GPU Project - The easiest and most ergonomic GPU library

LyricWulf 9 Nov 30, 2022
Scan all IP nodes of CloudFlare to find the fastest IP node.

中文版 | English ?? Introduction Scan all IP nodes of CloudFlare to find the fastest IP node. ⚡️ Get Started ??️ Build git clone https://github.com/golan

golangboy 47 Mar 19, 2024
Attribute macro for implementing methods on both Foo and ArchivedFoo.

rkyv_impl Implement methods for Foo and ArchivedFoo in a single impl block. use rkyv::Archive; use rkyv_impl::*; use std::iter::Sum; #[derive(Archive

Duncan 5 Aug 6, 2023
A copypastable guide to implementing simple derive macros in Rust.

A copypastable guide to implementing simple derive macros in Rust. The goal Let's say we have a trait with a getter trait MyTrait {

Imbolc 131 Dec 27, 2022
Might have a go at implementing Pulumi for Rust 🤷‍♂️

Might have a go at implementing Pulumi for Rust ??‍♂️

Nick 11 Nov 1, 2022
A zero-copy parser for the contents of the __unwind_info section of a mach-O binary.

A parser for Apple's Compact Unwinding Format, which is used in the __unwind_info section of mach-O binaries.

Markus Stange 10 May 31, 2022
Provably optimal zero-copy parsers using nondeterministic finite automata.

inator: an evil parsing library You supply the evil plan; we supply the -inator! or, Provably Optimal Zero-Copy Parsers with Nondeterministic Finite A

Will Sturgeon 51 Oct 4, 2023
First Git on Rust is reimplementation with rust in order to learn about rust, c and git.

First Git on Rust First Git on Rust is reimplementation with rust in order to learn about rust, c and git. Reference project This project refer to the

Nobkz 1 Jan 28, 2022
Inverse kinematics plugin for Bevy implementing the FABRIK algorithm.

Inverse kinematics plugin for Bevy implementing the FABRIK algorithm.

Georg Friedrich Schuppe 11 Dec 31, 2022
Try to find the correct word with only first letter and unknown letter count

Try to find the correct word with only first letter and unknown letter count

Alexandre 6 Apr 11, 2022
Find out who is pretending to be offline

Dinkleberg Find out who is pretending to be offline Preview Disclaimer Dinkleberg was developed for educational, private and fair use. I am not respon

oSumAtrIX 40 Dec 28, 2022
The working code for my Safe Pay app - check out my tutorial!

Safe Pay Tutorial This repository contains the source code for my blog post Using PDAs and SPL Token in Anchor. The code contains the following: Solan

Daniel Pyrathon 39 Aug 28, 2022
An out-of-box ChatGPT bot for Telegram.

TeleGPT API Docs | Releases | Twitter An out-of-box ChatGPT bot for Telegram. TeleGPT is a Telegram bot based on teloxide framework and async_openai.

null 169 Apr 7, 2023
An out-of-box ChatGPT bot for Telegram.

TeleGPT API Docs | Releases | Twitter An out-of-box ChatGPT bot for Telegram. TeleGPT is a Telegram bot based on teloxide framework and async_openai.

null 173 Apr 16, 2023
Shows only the first page of rustc output

cargo-first-page Shows only the first page of rustc output. Installation cargo install cargo-firstpage Usage Prefix the cargo command by firstpage: T

Cecile Tonglet 11 Dec 19, 2021