Building an LRU Cache via @mysteriouspants


Chris made a Least Recently Used (LRU) Cache: a hash map of fixed size that we can add nodes to until we reach its limit, after which the oldest node will be kicked out when we add another node. For Chris's implementation, he wraps a HashMap and a queue of nodes that he wants to evict.

The queue is a linked list. When we get an node, it goes to the front of the queue. Unfortunately this creates memory and borrowing issues when removing an node from the list and moving it to the front. Chris tried to contain the nodes in an Rc<Node> and have a link to the next node and a weak link backwards. However in this case he was hitting the heap a lot and he wanted a solution that pushes more of the logic into the struct and avoids the heap.

So instead he made the funniest linked list. It has a single contiguous Vec which are addressed by their position in the Vec. It freelists elements that are removed. It does this by using a NodeHandle which is just a newtype for a usize pointing to the node's place in storage. He could have shifted everything off the Vec, but NodeHandle is essentially free and it performs in O(1) for removing nodes.

One problem with the LRU Cache is that reading from it is technically writing to it. This occurs because you are moving stuff around in the eviction queue. So it is not thread-safe by default. He solved that by creating a wrapper around LruCache that is shareable across thread boundaries using Arc<RwLock<LruCache<K, V>>>.

One final feature of the project is an expiring cache. LruCaches are often used to proxy data sources and adding an expiry is an easy way of saying that you want the data to be "at least as fresh as" some duration.

Hopefully we can see this project packaged up in a crate in the near future.

Const Generics via @DanielPBank


Daniel was playing with const generics, mostly by reviewing examples he found online. He did attempt to make an image processing example using const generics but didn't finish in time for the meetup.

Basic Example from the Shipping Const Generics blog post

let data = [1, 2, 3, 4, 5, 6];

let sum1 = data.array_chunks().map(|&[x, y]| x * y).sum::<i32>();
assert_eq!(sum1, (1 * 2) + (3 * 4) + (5 * 6));

let sum2 = data.array_chunks().map(|&[x, y, z]| x * y * z).sum::<i32>();
assert_eq!(sum2, (1 * 2 * 3) + (4 * 5 * 6));

Rectangle Example from the Rust RFC Book

A struct specifying a rectangular array using const generic type parameters. If you attempt to create a rectangular array that does not fit the dimensions, you will get a compile-time error instead of a runtime error.

struct RectangularArray<T, const WIDTH: usize, const HEIGHT: usize> {
    array: [[T; WIDTH]; HEIGHT],

State Machine Example from /r/rust

See playground here. This example is interesting because we have a type parameter that manages internal state and what functions are available for that state.

This example still needs the #![feature(const_generics)] feature flag and fails with the following error otherwise. Currently, the supported types are signed and unsigned integer types, booleans, and chars. Other types coming in the future:

error: `&'static str` is forbidden as the type of a const generic parameter

Float Stuff Also Const Generics via @PeterKehl


As we were talking about const generics, Peter shared some code he is working that uses const generics. His project provides arbitrary precision floats backed by f32, f64, TwoFloat, and MPFR.

Debugging on AMG8833 Grid-EYE with Rust via @jacobrosenthal


Finally, still in the vein of const generics, Jacob shared an embedded project he was working on where he used const generics to solve a problem:

Adafruit AMG8833 Grid-EYE Breakout is a sensor from Panasonic featuring an 8x8 array of IR thermal sensors. Jacob had found a Rust driver for the Grid-EYE, but it was not as efficient as he wanted so he did some cleanup on the code.

One of the clean-up items was in an example where he needed to get the raw pixel data from the camera (as u8s) and group them into u16s so that he could convert the u16 value to a f32 temperature. (Actually there was another layer of nuance, only 12 bits from the u16 were being used so he had to use u16::from_le_bytes).

Here he used const generics to group two u8s into one u16:

loop {
    grideye.get_pixels_temperature_raw(&mut pixels).unwrap();

    //group by 2 u8s, turn into u16, then call temperature_u12_to_f32_celsius-> f32
    let out = pixels
        .map(|chunk| u16::from_le_bytes(*chunk))
        .map(|raw| temperature_u12_to_f32_celsius(raw, 0.25))
        .collect::<heapless::Vec<f32, N>>();

    rprintln!("{:?}", &out);

Previously we would have had to manually create an array, get the two u8, put them in the array, and pass it on. So using const generics makes this easier to read and work with.

Jacob also shared tools he uses for debugging on embedded, the probe-run and rtt-target crates.

VSCode Rust-analyzer Tips via @craig_jbishop

A couple of tips and tricks for rust-analyzer in VSCode came up.

Toggle On and Off Inlay Hints

The inlay hints in VSCode are a nice way to quickly inspect the types of things, but they can make the code look more verbose than it is. There is a setting to Display Inlay Hints which works but it is still a little inconvenient to open settings every time you want to show / hide the inlay hints. So here is a cool trick: you can add a keyboard shortcut to toggle the setting on and off. The shortcut uses the Settings Cycler extension, so you will need to have that installed. Afterwards, you can simply add a new entry in your Keyboard Shortcuts:

// Place your key bindings in this file to override the defaults
    "key": "alt+f", // key to press to activate command
    "command": "settings.cycle", // `settings.cycle` is the command that's actually being run, from the extension `hoovercj.vscode-settings-cycler`
    "when": "editorTextFocus && editorLangId == 'rust'", // this keybinding is only active when (editor is in focus) and (the language is `rust`)
    "args": { // these are the arguments passed to `settings.cycle`
      "id": "rust-toggle-inlay-hints", // must be unique
      "overrideWorkspaceSettings": true,
      "values": [ // Note: use the same settings in each values object
          "rust-analyzer.inlayHints.enable": false // sets the inlay hints off
          "rust-analyzer.inlayHints.enable": true // sets the inlay hints on

Insert Concrete Type Definitions

You might see an inlay hint for a variable and want to have the concrete type definition in the actual code. You can do this with Cmd . when the mouse is over the variable.

Crates You Should Know

  • ndarray-image: Allows conversion between ndarray's types and image's types
  • probe-run: Runs embedded programs just like native ones
  • rtt-target: Target side implementation of the RTT (Real-Time Transfer) I/O protocol
  • grideye: Rust driver for Grid-EYE / Panasonic AMG88(33)