51–59 of 59 posts
Very often if you have text, which this does, you can make huge savings by being intelligent with the text. Rust intentionally provides the simplest possible growable string buffer String, which is literally (under the hood, you can't poke this legitimately) Vec plus the promise that this is UTF-8 text. But you might find your needs better served by one (or several) of: Box -- you don't need capacity, so, don't store…
What does Box give you that &str doesn’t?
Earlier quoted context omitted.
Box used to be ~T early on in rust… (then it became a `box` keyword, before being removed entirely.) They got rid of it because they wanted to move more things into libraries and have a less opinionated compiler. I think I agree though, especially with Option. Swift’s option syntax (and kotlin’s which is similar) is so much better, a simple question mark in the type. Options are important enough that dedicated syntax…
The Try trait (representing the ? the operation) is super cool though! I wish it was marked stable so you could implement it for types without using the nightly compiler. Note that both Option and Result implement that same trait. Perhaps if try blocks ever become a thing... we can finally use it for our own types ;) https://doc.rust-lang.org/std/ops/trait.Try.html
AIUI a key innovation is ControlFlow, reifying the Break/ Continue choice as a sum type in the type system. This is already stable and is a useful piece of vocabulary even without its contribution to understanding the Try trait.
Knowing that Bob's CircusPerformance trait and Sarah's SeaLion type both use ControlFlow to decide whether we should keep going or halt ASAP means you don't have to write fraught adaptor code because Bob thought obviously the boolean "true" means keep going while Sarah's understanding was that it's a signal about being finished, so "true" means stop.
For Try what ControlFlow did was unlock the difference between "Success / Failure" as encoded by Result::Ok and Result::Err and the "Halt / Carry on" distinction ControlFlow::Break and ControlFlow::Continue. Often we want to stop when there's an error, but sometimes we mean the exact opposite, carry on trying things until one of them succeeds.
Earlier quoted context omitted.
There's really an endless list of these optimizations. A few I've used (though not necessarily in rust): Atoms: Each string can be referenced with a single u32 or even u16, and they're inherently deduplicated. Bump allocator: your strings are &str, allocation is super fast with limited fragmentation. Single pointer strings (this has a name, I can't think of it right now): you store the length inside the allocation in…
Atoms: is this similar to interned strings?
Very often if you have text, which this does, you can make huge savings by being intelligent with the text. Rust intentionally provides the simplest possible growable string buffer String, which is literally (under the hood, you can't poke this legitimately) Vec plus the promise that this is UTF-8 text. But you might find your needs better served by one (or several) of: Box -- you don't need capacity, so, don't store…
There's really an endless list of these optimizations. A few I've used (though not necessarily in rust): Atoms: Each string can be referenced with a single u32 or even u16, and they're inherently deduplicated. Bump allocator: your strings are &str, allocation is super fast with limited fragmentation. Single pointer strings (this has a name, I can't think of it right now): you store the length inside the allocation in…
First, on the heap we have a self-indicating length prefix, basically we use the bottom 7 bits of each byte to indicate 7 bits of length and the top bit indicates there are more bits in the next byte. So "ben-schaaf" would be 0x0A then the ASCII for "ben-schaaf"
But, we avoid even having a heap allocation if we have 8 or fewer UTF-8 bytes to encode the text, that's our Small String Optimisation.
To pull this off we specify that our heap allocations will have 4 byte alignment even though they don't need it. This shouldn't be a problem, in fact many allocators never actually deliver smaller alignments anyway.
This means our pointer now has two spare bits, the least significant bits are now always zero for a valid heap pointer. We rotate these bits to the top of the first byte (this varies depending on whether the target is big-endian or little-endian) and we mask them so that for these valid pointers they are 0b10xxxxxx
So, now we can look at the "single pointer" and figure out
If it begins 0b10xxxxxx it really will be a valid pointer, rotate it, mask out that flag bit and dereference the pointer to find the length-prefixed text.
If it begins 0b11111AAA there's a short string here but it didn't need all 8 bytes, the next AAA bytes of the "pointer" are just UTF-8 and conveniently AAA is enough binary for 0 through 7 to be signalled, the exact length we have
If it has any other value the entire 8 bytes of "pointer" is a UTF-8 encoded string
Earlier quoted context omitted.
There's really an endless list of these optimizations. A few I've used (though not necessarily in rust): Atoms: Each string can be referenced with a single u32 or even u16, and they're inherently deduplicated. Bump allocator: your strings are &str, allocation is super fast with limited fragmentation. Single pointer strings (this has a name, I can't think of it right now): you store the length inside the allocation in…
ColdString is both your "Single pointer string" and a Small String Optimisation on top. First, on the heap we have a self-indicating length prefix, basically we use the bottom 7 bits of each byte to indicate 7 bits of length and the top bit indicates there are more bits in the next byte. So "ben-schaaf" would be 0x0A then the ASCII for "ben-schaaf" But, we avoid even having a heap allocation if we have 8 or fewer UTF…
But it also means the CPU has to follow the pointer (and potentially get a cache miss or pipeline stall) to find the length. Having a fat pointer of ptr+length makes a lot of sense for string views, and for owned string buffers with capacity it can mean avoiding a cache miss when appending to the buffer.
It's complicated in other words.
Very often if you have text, which this does, you can make huge savings by being intelligent with the text. Rust intentionally provides the simplest possible growable string buffer String, which is literally (under the hood, you can't poke this legitimately) Vec plus the promise that this is UTF-8 text. But you might find your needs better served by one (or several) of: Box -- you don't need capacity, so, don't store…
There's really an endless list of these optimizations. A few I've used (though not necessarily in rust): Atoms: Each string can be referenced with a single u32 or even u16, and they're inherently deduplicated. Bump allocator: your strings are &str, allocation is super fast with limited fragmentation. Single pointer strings (this has a name, I can't think of it right now): you store the length inside the allocation in…
You can build an ad-hoc bump allocator by using a String and indexing into it. You can't use &str references though, as a growing String may reallocate elsewhere and invalidate your references (Rust won't even let you try this), so you have to use your own indices. This is the same thing that bump allocator libraries usually do, too. It can be tricky but have great performance gains.
I recently 100x-d the speed of an XML/HTML builder I use internally by rewriting it to only have one thing on the heap, a single String. Every push happens right at the call site linearly, and by passing data through closures the formatting (indentation, etc.) is controllable. My first iteration was written in the least efficient way possible and had thousands of tiny allocations in nested heap objects, it was painfully slow.
Earlier quoted context omitted.
"You have 400 megabytes of zeros in " is probably a pretty easy heuristic to add.
That may be surprisingly difficult in Rust. We generally think of Option using O to represent None. However, it can actually use any invalid value of T
But if a debugger can show you all values of type X, and the compiler defines null-y values of X, surely there's some way? That still doesn't seem complicated, just not as overwhelmingly-trivial as some languages.
tbh "trait" feels like a very problematic name for that type, for this kind of educational purpose - `trait` is already an established concept and keyword: https://doc.rust-lang.org/book/ch10-02-traits.html It's especially problematic because traits don't have memory behaviors like this article in most cases - by default they're unsized, because it's a description of behavior, not data, and you can't even use them as…