In this post, we will implement a static search tree (S+ tree) for high-throughput searching of sorted data, as introduced on Algorithmica. We’ll mostly take the code presented there as a starting point, and optimize it to its limits. For a large part, I’m simply taking the ‘future work’ ideas of that post and implementing them. And then there will be a bunch of looking at assembly code to shave off all the instructions we can. Lastly, there will be one big addition to optimize throughput: batching.

https://en.algorithmica.org/hpc/data-structures/s-tree/

source: HN

This post isn’t a scientific evaluation or an A/B study. It’s my personal opinion after trying to make Rust gamedev work for us, a small indie developer (2 people), trying to make enough money to fund our development with it.

source: L

There is a joke that if there is tech debt, surely there must be derivatives to work with that debt? I’m happy to say that the Rust ecosystem has created an environment where it looks like one solution for tech debt is collateralization.

source: HN

This is the story of how I identified the bug. (TLDR: collect::<Vec<_>>() will sometimes reuse allocations, resulting in Vecs with large excess capacity, even when the length is exactly known in advance, so you need to call shrink_to_fit if you want to free the extra memory.)

Ordinarily, that wouldn’t have been a problem, since the into_iter().map().collect() line used to pack them into (u32, u32)s would allocate a new vector with only the exact amount of space required. However, thanks to the allocation reuse optimization added in Rust 1.76, the new vec shared the backing store of the input vec, and hence had a capacity of 16560, meaning it was using 132480 bytes of memory to store only 16 bytes of data.

source: HN

Polonius refers to a few things. It is a new formulation of the borrow checker. It is also a specific project that implemented that analysis, based on datalog. Our current plan does not make use of that datalog-based implementation, but uses what we learned implementing it to focus on reimplementing Polonius within rustc.

source: L

This post is best described as a technology demonstration; it melds together web servers, plugins, WebAssembly, Go, Rust and ABIs. Here’s what it shows:

How to load WASM code with WASI in a Go environment and hook it up to a web server.
How to implement web server plugins in any language that can be compiled to WASM.
How to translate Go programs into WASM that uses WASI.
How to translate Rust programs into WASM that uses WASI.
How to write WAT (WebAssembly Text) code that uses WASI to interact with a non-JS environment.

source: L

Of course you can leak memory, even in Rust. For even medium-sized long-running applications, lots of graphs from a good memory profiler can make life better. And they’ll probably help you find the memory leak too.

In my last post I introduced the Compiler performance roadmap for 2022. Let’s see how things are progressing.

Along the way I had to undo some optimizations I had added to this code a couple of years ago. Those optimizations turned out to be useful for one kind of expensive macro (with many rules but no metavariables) present in the html5ever benchmark. But such macros aren’t common in practice, and these optimizations were unhelpful for more typical expensive macros, which are recursive, have fewer rules, and use metavariables. This shows the value of a good benchmark suite.

source: L

In the rest of this post I’ll walk through a typical C mutex API, compare with a typical Rust mutex API, and look at what happens if we change the Rust API to resemble C in various ways.

source: HN

In this post, I will cover how we worked to ensure correctness in our register allocator, regalloc.rs, by developing a symbolic checker that uses abstract interpretation to prove correctness for a specific register allocation result. By using this checker as a fuzzing oracle, and driving just the register allocator with a focused fuzzing target, we have been able to uncover some very interesting and subtle bugs, and achieve a fairly high confidence in the allocator’s robustness.

source: HN

So Rust is going really well for us at Oxide, but for the moment I want to focus on more personal things — reasons that I personally have enjoyed implementing in Rust. These run the gamut: some are tiny but beautiful details that allow me to indulge in the pleasure of the craft; some are much more profound features that represent important advances in the state of the art; and some are bodies of software developed by the Rust community, notable as much for their reflection of who is attracted to Rust (and why) as for the artifacts themselves.

source: L

This section documents the exploit mitigations applicable to the Rust compiler when building programs for the Linux operating system on the AMD64 architecture and equivalent.

source: L

I show how to use heterogeneous lists and traits to implement a type-safe printf in Rust. These mechanisms can ensure that two variadic argument lists share important properties, like the number of format string holes matches the number of printf arguments.

source: HN

Or more exactly, why does this happen, and why do people perceive it as a problem?

source: L

I still believe it would be possible to build a high quality editor based on the original design. But I also believe that this would be quite a complex system, and require significantly more work than necessary.

A few good ideas and observations could be mined out of this post.

source: L

With all that’s going on in the world you’d be forgiven for forgetting that as of today, it has been five years since we released 1.0 in 2015! Rust has changed a lot these past five years, so we wanted reflect back on all of our contributors’ work since the stabilization of the language.

source: L

I’ve recently been writing a bit of parsing code in Rust, and I’ve been jumping back and forth between a few different parsing libraries - they all have different advantages and disadvantages, so I wanted to write up some notes here to help folks who are undecided choose what libraries and techniques to consider, and also to offer some suggestions for the future of the Rust parsing ecosystem.

source: L

Much of writing software revolves around checking if some data has some shape (“pattern“), extracting information from it, and then reacting if there was a match. To facilitate this, many modern languages, Rust included, support what is known as “pattern matching”.

source: L

In this post, I took the opportunity to re-summarise what I consider to be the essence of this ownership rules in Rust.

source: L

This post explains how to implement heap allocators from scratch. It presents and discusses different allocator designs, including bump allocation, linked list allocation, and fixed-size block allocation. For each of the three designs, we will create a basic implementation that can be used for our kernel.