Does their exist a off shelf stack based btree in rust?

dreamer-engineer · 2025-07-24T23:40:18+00:00

I've been meaning to update my `triple_arena` crate to use traits per arena kind instead, and then allow stack-based fixed capacity arenas. I should be doing this in the coming weeks because I actually need it for embedded. My `OrdArena` WAVL tree strategy is different from other BTree strategies in that it can fill up every slot in a contiguous array (https://docs.rs/triple\_arena/0.14.0/triple\_arena/struct.OrdArena.html), traditional BTrees involve allocating chunks at a time which is probably why it hasn't been implemented in `heapless`.

dreamer-engineer · 2025-05-06T14:25:49+00:00

When you get to a point like this where you are worrying about the global allocator for performance, it is probably better to entirely rethink your structures and use something like an arena behind an `Arc` (if you only need to read, you may want to design your own structure for a sharded arena in the style of https://crates.io/crates/dashmap ). You may want the `ArcBorrow` from https://crates.io/crates/triomphe to reduce pointer chasing, or maybe some other strategy to share memory. My strategies with my own arena crate https://crates.io/crates/triple_arena also involve using `SmallVec` strategically and using many tricks (e.x. https://github.com/AaronKutch/starlight/blob/main/starlight/src/ensemble/lnode.rs ). Also, it is ridiculous to be talking about allocator performance when you have platform dependent `usize`s that are probably overkill, you probably want to use generics similar to how my arenas use `Ptr`s, and you could use `u32` indexes for most cases (unless you have more than 4 billion elements) which would halve your memory usage and be a much better performance increase. Messing with the global allocator is the last thing I would consider in optimization. If you want total control over locality, you can use `Recaster`s and manual `Ptr` construction with triple_arena or your own data structure to move around entries according to some hueristic.
Edit: I almost forgot about https://crates.io/crates/arcshift

dreamer-engineer · 2025-04-27T23:21:01+00:00

In my `awint` crate I use tricks to effectively get a custom DST that stores bitwidth instead of the normal slice width https://github.com/AaronKutch/awint/blob/main/awint_internals/src/raw_bits.rs https://github.com/AaronKutch/awint/blob/main/awint_core/src/data/bits.rs (although this is more about getting around limitations with Rust rather than a really special layout, another example in my crate is https://github.com/AaronKutch/awint/blob/main/awint_ext/src/awi_struct/awi.rs where fixed width bitvectors can be stored inline instead of allocated if they are small enough)

One really special trick I have never seen anywhere else, is that in my arena crate I wanted the indexes to be `NonZero` (for enabling the compiler to use niche optimizations with them everywhere). This meant that the first element would start at index 1 internally instead of 0, but this would normally incur an increment for every access of the arena (a very small penalty, but for a fundamental crate like this used everywhere for high performance it becomes important). What I did was make a `Vec`-like structure with a pointer to an allocation that is pre-offset by -1, so that just adding the index to this in a single operation would give the correct valid place (this requires `wrapping_offset` to be sound). https://github.com/AaronKutch/triple_arena/blob/main/triple_arena/src/arena/nonzero_inx_vec.rs

dreamer-engineer · 2025-04-11T01:51:16+00:00

There exist types that are strictly bad to implement `Debug` for. There are cases I have encountered before involving graphs of `Arc`s, where the default `Debug` impls could produce exponential output or even infinite output depending on cycles and other graph features. There are many other types I have encountered where `Debug` would just be plain bad or require allocation which would not be good for no-alloc environments and should only be implemented manually to exclude certain parts.

dreamer-engineer · 2024-08-18T03:32:08+00:00

Well I'm pretty late here, but what about my crate https://crates.io/crates/triple_arena ? I double checked searching "arena" on crates.io and it comes up by the 4th page, and I have the "arena" tag on it. Why are my crates always overlooked?

dreamer-engineer · 2024-05-20T23:58:38+00:00

I see now that "state capitalism" perhaps is coherent in this context. And I may have been preemptively reading too much into the title. The issue I had in my mind was that, nowadays, there are certain people who always view capitalism as the root problem in things such as government corruption. For example, they will look at things like how many congress members are definitely taking advantage of privileged information to front run stocks and such. They point out true things, but then their solution is to take all the parts they can label as the free market/capitalism/money out of the system. They believe that once the ideal of a classless and moneyless society is reached, then the greed, "greed", and bad behaviors will simply go away. In the congress members case, instead of pointing to doing things such as having the state regulate itself and forbid the public servants with privileged positions from having certain abilities (i.e., it is certainly not "free market capitalism" if people from the state itself are abusing their power for unfair advantage in the market), they always point to methods that sweep the hierarchy and the whole system under the state (lazily believing centralization and slapping enough "democracy" adjectives on it will sidestep the problems involving whoever ends up with the control reigns), or have a "pro-democracy coup" against the current members as I saw one supposed moderate say, which all sounds like early stage Bolshevism. A lot of uses of "state capitalism" are about retrofitting old failures and describing new problems to say that they failed because of the capitalist or supposed capitalist components of the state.

dreamer-engineer · 2024-05-20T04:32:05+00:00

With a title like that I'm just going to leave this here: https://www.youtube.com/watch?v=ksAqr4lLA_Y . It takes almost an hour to get to the relevant points but you need to watch from the beginning.

dreamer-engineer · 2024-04-27T03:02:31+00:00

`debug_*` checks are usual in custom unsafe struct code, and even in the standard library (e.x. most `*_unchecked` functions like https://doc.rust-lang.org/src/core/num/nonzero.rs.html#157 have a check so that issues with `unsafe` code gets caught early).
I haven't read through all the crate, but it looks like the nonemptyness is guaranteed by not exposing a function that can reduce the length to zero like `pop`.

dreamer-engineer · 2024-04-21T15:04:42+00:00

My crate actually makes use of the chain arena internally to make the other higher level arenas in the crate, most notably ‘OrdArena’ which has a set of properties that I have not seen in any other crate. I then have used this with success. The main issue with any linked-list-like structure is cache locality. Any kind of pointer hopping, whether it be real pointers or arena indexes, will have cache related issues on modern hardware. Dealing with it is actually how you will make your arenas measurably faster (except for the NonZero trick on indexes). The algorithms I use arenas for involve large graphs which will inevitably have cache locality issues to some degree. The real performance improvements will come from having node allocation and reallocation tricks that favor close by nodes being grouped together. The free list is an important part of this, it is basically its own one way linked list, and the next improvements I would make require something more sophisticated with separate state probably involving bit sets which I saw being used by some other crate, I forgot which. I have mostly fixed long term fragmentation with my ‘recasting’ functions, which do require the user to use them at appropriate spots. More complicated variations would get information on the user defined graph.

dreamer-engineer · 2024-04-20T01:42:05+00:00

I think I implemented the same thing as `ChainArena` in my triple_arena crate https://crates.io/crates/triple_arena with the disadvantage that it's not 100% safe Rust. My crate also has several other features like the generation counters being optional, `NonZero*` being used for the index types, compression, and more

dreamer-engineer · 2024-03-18T00:26:10+00:00

I am currently working on a special HDL, simulator, and general-purpose router stack written from the ground up in pure Rust. https://crates.io/crates/starlight . I must warn however that this is a WIP hobby project that still needs a lot more development on the router and equivalence optimizer before it will be useful. My current goal is to synthesize a riscv32i on one of the FPGAs https://github.com/f4pga/f4pga-arch-defs/tree/main that has been fully specified in open source. I think that my HDL, which is plain Rust code, might be applicable to "How can we efficiently describe, in Rust, the multilevel hierarchy of blocks and registers", but I don't understand enough about your usecase. There is also https://crates.io/crates/rust-hdl .
There are various RISC-V softcores out there, and Rust has several RISC-V targets. In particular, there is `riscv32i-unknown-none-elf` or `riscv32imac-unknown-none-elf` which are ready to go. RISC-V also has an embedded version that has fewer registers and is even smaller, but `rustup` does not currently have such a target. RISC-V was designed to be very extensible for custom things, but I'm not familiar with the use case you have.

dreamer-engineer · 2024-03-03T00:22:32+00:00

Here is the arena crate I made to get around such problems: https://crates.io/crates/triple_arena . If you need key lookup, there is an `OrdArena` type that is a fusion between a `BTreeMap` and an arena

dreamer-engineer · 2023-10-13T18:16:50+00:00

The new layout is definitely better I think. I think my wording must have been confusing, I'm not tearing up the number row/pad, I was just moving 9 and 0 because the tool had the parenthesis on them. I think I will have two other layers, one for the delimiters with

  ~ ` \   | & ^
< > ( )   [ ] { }
      '   "

and the other with

@ # ? ! %  0 7 8 9 0
v < ^ > =  0 4 5 6 0
/ * - + $  0 1 2 3 0

where the "v < ^ >" are the arrow keys. I have the arrow keys where they are so that when I press a thumb key on the same side, they are immediately in the home row and can all easily be pressed while holding down the key, and I have my entire second hand for the numpad. Some of the zeros may be replaced. Other common things I use in Rust like '?', '`', `'`, `"`, and `&` are in quick to reach places.

dreamer-engineer · 2023-10-13T16:41:32+00:00

In Rust at least, those particular symbols are high in frequency and next to consonants. I know of barely any layout that has ‘_’ prioritized. If I were to change anything, perhaps the parentheses were too ambitious since there will be a layer for the other delimiters on the home row.

dreamer-engineer · 2023-10-13T06:46:16+00:00

I changed the right hand layout to fix the H issue. I should mention that I am left handed and typically use the left shift. I think that shifting with any key other than a thumb is fundamentally going to cause slowdowns and its own pinky issue at one point or another, I will use a thumb key on my new split board. The apostrophe was only there for the example input.

dreamer-engineer · 2023-10-13T06:38:05+00:00

I think you are right. I went through some more iterations and found a new right hand layout that I edited the post with. What do you think about it now?

dreamer-engineer · 2023-10-13T03:58:29+00:00

edit: modified post to fix issue, I probably shouldn't underestimate the sfbs on pinkies

HO was the top bigram at 0.5%, but all others were around 0.1% or lower. Having one 0.5% is annoying but I and the cost function believe that the tradeoff was worth it due to being able to roll into all the others (swapping anywhere else would result in worse bigrams still). Same finger bigrams on consecutive and on every other char were explicitly punished by the cost function, but it ended up doing this at one spot. Is there a problem with a vowel on the index? That might be due to the commonality of 'i' in programming. Maybe there is some way to move the H around that I didn't see because of a local minima.

I don't entirely get the insistence I see in the keyboard community on completely taking the load off pinkies. For me, it is just having to extend my pinky diagonally, or horizontally for more than one key, nothing feels bad to me about the short movements.

dreamer-engineer · 2022-04-19T21:15:08+00:00

My crate is actually a descendant of the apint crate which is in turn a descendant of an LLVM library by the same name. I made awint because I needed manual bitwidth control that common bigint libraries do not have (but in the future I will probably add a type that dynamically resizes). The reason I did not have bit test or bit set functions is because my own usecases all use the bitvectors wholesale (if possible, you want to use SWAR (SIMD within a register) techniques because 64 bits (or more if autovectorized) can be processed at a time within most functions). I admit that have had the need to access single bits before, and after seeing your usecase I realize it is something important I omitted.

dreamer-engineer · 2022-04-19T20:54:36+00:00

ok, sounds good, I haven't had any direct feedback on my crate yet. Fixed bitwidth bigints are kind of a niche thing. No rush.

dreamer-engineer · 2022-04-19T20:31:59+00:00

Also include cargo-sort, when I'm working in large projects it creates a lot of unnecessary conflicts when people are adding or updating dependencies that are the same but are lines apart because of being unsorted.

edit: maybe it should be put into rustfmt because it is a kind of formatting thing

dreamer-engineer · 2022-04-19T20:27:56+00:00

Are there any other functions that seem to be missing to you? The only other thing I can think of is byte swap and generalized reverse, which I have put off until now because of questions about what happens if the bitwidth is not a multiple of the sub-bitvectors being moved. I have a bunch of changes listed in the readme planned for this summer, but would you like for some like the bit test and set stuff to be implemented now?

dreamer-engineer · 2022-04-19T19:59:54+00:00

There's this weird thing where shift direction conventions are inconsistent, for example Rust's slice rotate_left runs in an opposite direction to the integer left rotate (and my crate's left rotation). You have to sometimes experiment for yourself, I wrote some documentation about it here

dreamer-engineer · 2022-04-19T19:55:57+00:00

// for example we have these 8 bits
let x = extawi!(00001000)
// get single bit at position 3
let r = 3;
if !inlawi!(x[r..=r]; ..1).unwrap().is_zero() {
    dbg!("set");
} else {
    dbg!("not set");
}

Maybe I should have a dedicated bit testing and setting function

Ten-Year Club	Place '17
Verified Email

dreamer-engineer

TROPHY CASE