Compile Time Crimes

Amos Wenger: Both of you say something?

Amanda Majorowicz: Something?

James Munns: Hello, I am James.

Amos Wenger: Yeah, we have you. I can see the levels in Cleanfeed, which makes me feel safe. I can even like hit the download button as many times as I want. Like, anxiety? Boom. Download. Now you have all the files on your disk.

Amanda Majorowicz: That sounds like too many... I don't like it. I get anxiety by that.

Amos Wenger: It's fine. I'm the one doing it.

Amanda Majorowicz: I'm like: wait. No, no, no. No, no, no. That's too many files.

Amos Wenger: Well, okay. I understand that. Yeah, but losing the audio is the higher anxiety. Surely. No?

Amanda Majorowicz: Maybe, I don't know. It's intermittent- it's anxiety either way, I guess.

Amos Wenger: Ok ok ok, we'll fight about it later.

James Munns: We can have our own special anxieties.

Amos Wenger: I understand.

Amanda Majorowicz: Do you want the little bits of anxiety or just the really big potential anxiety? One of the two.

Amos Wenger: All right. Well, James, what do you have for us today?

Postcard RPC and needed trickery

James Munns: Okay. I've been working on Postcard RPC because I got nerd sniped into how to fix some things that I didn't think needed to be fixed, but that required some trickery. So I've been working on doing tricky things at compile time. This is me documenting some of the silly tricks that I've done because I think you might appreciate them Amos.

Amos Wenger: I hope so.

James Munns: One of the things that I've been working on is preparing a list of schemas. So if I'm making a device and I want to say: these are all the types that the device can send or receive, sort of like an OpenAPI spec if you're familiar with those, but just a list of, "Hey, when you talk to me, these are all the different kinds of data you can send and receive." And in the past I hadn't been making them unique. I would just kind of do a macro expansion, and if you had 10 endpoints that all sent the same data, then you would just get 10 copies of that schema, but schemas aren't so big, so I wasn't too bothered by it.

It wasn't great, but it also wasn't practically a problem.

Amos Wenger: Right... do you have a unique identifier for them? Can you hash the schemas? How does that actually work? Because like, doing anything at compile time is complicated enough. But now I'm just thinking, even if you didn't have the compile time constraint, how do you...

James Munns: The answer is yes. Yeah, so as a reminder, Postcard RPC- we did an episode on it, and I can't remember how deep I went into this part of it, but- I do have a const function that hashes the schema and the URI together, and produces an 8 byte key at const time for that. So you will have a const schema for a type, so there's a trait Schema that gives you a const SCHEMA, which is a type that is like a recursive struct that describes the data.

And then I have a function that can take that type and produce an eight byte hash for that. And then that's usually what I use as my message identifiers on the wire. And that means you also don't need to calculate it at runtime. It just becomes this bag of eight bytes that you append to the front of every message.

Problem: de-duplicating lists

James Munns: So one of the things I would like to do is deduplicating both that set of key hashes, as well as the set of schemas, because if I am allowing you to download types, like reflection style, of what types are used for this, I need to deduplicate both the IDs. So these are all of my endpoints by ID, as well as these are all of the types that are used by all of those endpoints, and ideally deduplicating them, so that if I have five endpoints that all return the same struct, just in a different context, then I don't repeat that definition five times.

Amos Wenger: Question, is it a concern of like, your binaries need to be as tiny as possible because you're doing this on embedded? Is it a constraint of, like it's a bandwidth problem? You want the response to be as small as possible? Why are you even deduplicating them in the first place? Or just someone said, "Oh, that's messy, you should fix it."

James Munns: There's actually multiple parts to this here. The main answer is for bandwidth. So right now I use USB, and even though it's sort of the full speed, which is the lower USB 1.1 speeds.

Amos Wenger: Right.

James Munns: It's still fast enough, and the schemas aren't large enough, it isn't a problem. But I've talked to some people that want to use this over much lower bandwidth links- so either radios, or very old serial ports- saying: Oh, well, you're just gonna transfer five kilobytes of schemas is more problematic than crunching that all down to maybe a couple hundred bytes, ideally, particularly if we have very repetitive or very recursively nested types.

So on one hand, I didn't know how to do it before and I managed to figure out how. So it's not like there's a specific pressure on this, but in this case, reducing the amount of packets that I need to send when you say, "Tell me about yourself!" I want to describe myself as succinctly as possible usually for bandwidth reasons.

For some implementation reasons, a lot of these end up being statics or static references. So they actually do get kind of deduplicated by the linker already. So this is more about when I've been asked to describe myself, how many packets I need to send to describe myself and how large are those packets.

Amos Wenger: For the past two minutes, I've been picturing... there's a short by I want to say Pixar, about a letter that goes through the air. Cause I've been thinking about Postcard over radio frequency. I have that short in mind. I think you should make that part of your branding. I was totally listening to your explanation. Please, please continue James.

James Munns: I've kind of crunched out a very basic example of this so it's a little easier to follow if you don't know how all the guts of Postcard RPC work. But let's say I have a list of u32s, so just integers unsigned. The list is 1, 5, 10, 5, 20, 1. So we notice that there are some duplicates on that list, and if I wanted to get rid of those duplicates,

I want to end up with an array that is 1, 5, 10, or 20. I don't particularly care about the order, but I don't want there to be any duplicates in this list. So I've removed one of the fives and one of the ones.

Amos Wenger: Luckily, HashSet is const, right? Please tell me HashSet is const. Cause that's what I would do at runtime.

James Munns: Well, there is an issue with that and we will get to that.

Amos Wenger: Okay, okay.

Proc/decl macros only work with tokens

James Munns: So if I wanted to do this with a procedural or a declarative macro, the issue is that this only works with tokens. So procedural and declarative macros can do some really cool things and if you throw syn at the problem, you can write a proc macro that probably could do all the things you just described and take all those tokens in, convert them into integers, do the hash set of them, and produce a new token tree or whatever of the unique integers, and that would work.

And it would work if I gave you the input of this array 1, 5, 10, 5, 20, 1.

Amos Wenger: Yes.

James Munns: But if I give you another const or a static or something like that, these macros only work with tokens. They can't see the value behind them, which means that it won't work if I just say I have a const LIST_WITH_DUPES because they can't understand that.

Amos Wenger: Yeah, all they would see is the identifier. They wouldn't actually see the value that's behind that. And I don't think you can even fake your way around that. Cause syn, S Y N is a parser for Rust. It's an entirely separate parser from rustc's parser which have different functionality. Can we say bitched on the podcast? I bitched about it on X. You can bleep that if you want. I don't care.

Anyway, uh, I've bitched about that before: that like, oh, rustc has its own parser and then syn is also a parser, and it's messy my head. In my perfect view of the world, there's only one parser that can do it all. But I was explained that actually, the rustc parser is better at recovering from parse errors and emitting very detailed diagnostics, error messages, yeah. Whereas syn is better at keeping the exact structure of the AST exactly the way written, even when it wouldn't matter for rustc, like new lines and the exact formatting of comments and everything.

So it actually has a function, but then even if you have that instead of having a stream of tokens, like you said, like identifiers, numbers, then you still have just this tree of AST and it doesn't do any of the name lookup for you.

James Munns: Yeah, and that's the problem, is that that is a token. That is an identifier, whatever you want to qualify it as, and in proc macro or declarative macro world, they work with tokens, they do not work with source code. They don't understand that it is an array, or that it has some length or anything like that.

It is just an identifier that it has parsed as an identifier. And like I said, it can't do anything with this because macro world doesn't think about Rust code. It thinks about Rust source, if that makes sense. It's not tied to the semantics.

What about const fn?

James Munns: The other tool that we have here- and like I mentioned with that is const fn, which is Rust code, does think about Rust code, does have access to Rust code, but it has some restrictions to it. So you mentioned: oh, I would just throw it in a HashSet. Well, at least currently, you can't use heap allocations in const. And even if you could, there's no way to then turn it into a static that would work on my no standard embedded system or anything like that.

And I think there is some interest, and I've talked to the const fn folks like Oli, and there is interest in the future of being able to make like a vec in a const fn and then turn it into a slice or a fixed size array, and then use that as just a plain const. I think, some other languages, like maybe Zig, have the ability to do that.

Amos Wenger: I was gonna make that parallel. Zig has comptime- evaluation, compile time- and I think you can run any arbitrary Zig code in there because they don't care. But in Rust, const is actually run through Miri? Is that, yeah? And so, you have very limited capabilities. And I think like over time we've unlocked new abilities in const piecemeal. It's been very slow and very frustrating for people who are used to Zig where you can just like fucking run whatever code you want.

James Munns: Yeah. I think it is something that will get better, but I'm working with stable Rust today. I'm sort of limited because we either start with a fixed size array, so like a [u32; 6] or a slice of u32 of variable size. So we start with that.

And based on my answer, I said we want to end up with either a [u32; 4], so shrunk to just the uniques, or another slice of u32.

Problem: there's no alloc in const (yet)

James Munns: And there's this problem is that there's no alloc and const, which means I can't just put it in a vec, collect them all, and then dump it out. I need to figure out what type they are, because when you declare a const fn, like any other function in Rust, you have to say the signature of the inputs and the signature of the outputs when you define the function, which means different instances of this sort of need to take and return different pieces, but I found sort of a way to navigate this.

Amos Wenger: I'm very curious about that. I have no idea how you got out of this one. Usually it's just like, "Well, const can't do it yet, so fuck it, too bad."

James Munns: Yeah, yeah.

So, step one: we take our [u32; 6]. It is a const value that we've, let's say, expanded in a macro, where I say: okay, you gave me the six things that you care about, I've done some other things in const world, and I end up with this list of six integers. And I know that it is an array of six integers.

So my first step is: we can get the length of a constant array in const. .len() is a const fn, and so if I take a const value and call .len() on it, I can get the size of it. My first step is going to be to convert this [u32; 6] into an option [u32; 6] and a usize.

Time for a code example

James Munns: I have this const fn, which I'm pretty sure works. I kind of wrote it in pseudocode. So if it doesn't perfectly compile, I'll point you towards the real thing. We can say: we have a function called uniques, which takes a generic argument N, which is a usize, and a slice of u32s.

Amos Wenger: Okay. Okay. I have to stop you, James. You know I have to. First of all, are you using a bitmap font?

James Munns: Yes! Departure Mono, it's beautiful.

Amos Wenger: Okay, I'm glad we clarified that. Second all: I think we need to tell the people,in Rust, they can make functions generic, so they can accept type parameters. A compare function can take two things that implement Ord, then you can compare them, they can be ints or strings or whatever.

So you have this idea of type parameters, and like in Java, like in other languages with that kind of influence, it takes type parameters between chevrons? Do you have another name for them?

James Munns: I'd say angle brackets, but...

Amos Wenger: Angle brackets, exactly. But then in const code, you can also accept not just types, but also values. And so, if you haven't written const code before, and you're looking at the same slide_ I_ am, it will at first look a little weird, because between the angle brackets, there's something const N: usize. like, the function can be parameterized by any of the 4- no, that's 32 bits...

James Munns: Yeah. These are const generics. This is just another flavor of generics. You can use them on const fns, you can use them on non const fns. You can have types, like a struct that is generic over const n usize. For example, if you wanted a struct that was generic over the size of a buffer, you could have that buffer be u8; N, where N is the const N usize thing like that.

We use this a lot in embedded because we have to right size our buffers because we don't have an allocator very often. So yeah, this is const generics. We're parameterizing over a value rather than a type.

We'll just take that as a given right now. So we have this N, which is a length. It's actually the length, that number six that we had before. And we take in a slice of u32s and we return an array of option u32 of length N and a usize. So the first thing we check is that the generic parameter N matches the length of our slice. That's just a little robustness of making sure that we handed the right thing in.

And then we create a new output array that is just an array of None; N. And because iterator is a trait and we can't use trait methods in const fns, we get to hand roll our own while loops for iteration, which means I start my output index, which is going to track how many things we've placed in that out buffer, and i, which is where I'm kind of scanning my input from. It's back to the lovely C style- actually not even C style because we don't have for loops, we just have while loops at this point of manually managing our iteration.

While we're iterating over the input slice, we're going to then iterate over anything in that out that has turned into a Some.

So basically I'm just walking through the list. And if I find a new unique value, I kind of push it into this out. But instead of it being like a vec, it's an array of options and I just turn the nones into some as my push primitive here.

Amos Wenger: I have so many notes on this, but I'm going to- I'm going to let you finish.

This is the compiler's problem, not my runtime code's problem

James Munns: Yeah, it's horrifically O(N^2), but again, this is the compiler's problem and not my runtime code's problem, so I'm not going to worry about it. I walk through the input list, pushing items that I find that are unique. If I find that they are not unique, I don't push them into the list because they're already there.

And then at the end of this list, I'm left with my full array of six items. I will have pushed four items into it, and because of my outindex variable is 4, I return that whole option list and the number 4.

Amos Wenger: Believe it or not, the fact that you're doing a linear lookup every time instead of hashing was not even one of my notes. This is not even the level I'm operating on right now. I'm looking at option u32 and I'm thinking there's no niche for u32. So you're essentially, you're allocating too much, but again, it's all in const, so who cares?

James Munns: We'll get there.

Amos Wenger: Okay. I like the trick that you don't know the size of the output, so you just fuck it, like every element is an option.You know the maximum number of them, so you just allocate a little too much and then you return, what, the actual size?

No, I'm looking at this and going this is maybe uninit- sorry, maybe uninit?

James Munns: Yeah, there's some tricks and I tried using this. The answer is that uninit arrays are hard to do with stable const today because at the end you would want to then turn it into an init array. So I did try that, but the answer is: not quite enough things are stable in const with maybe uninit, specifically, maybe uninit arrays.

Amos Wenger: Right.

James Munns: There might be a way to do it. I just didn't figure it out.

Amos Wenger: Those are weird. They don't fit in my need do an episode about them just so that I can refer back to it and then understand them properly.

James Munns: Cool. So this is a neat function. It takes some values.

const LIST_WITH_DUPES

James Munns: Let's look at what it might look like. So I have this array const LIST_WITH_DUPES. It is a slice. It's got six items. I can make another const just called len that is a usize that just takes that first constant and calls .len() on it because len is a const fn. You can take the input of another const, call a const function on it and get a value. So we can then get len. And then I can make this third const called intermediate, which is that tuple of an array of options of len with a usize, and then I can call my const fn, uniques::<LEN>, and then pass it the slice, list with dupes. So then I end up with this array and the length of unique items in it.

Amos Wenger: Why can't you just do all of that inside of a const fn? Is what I'm not understanding. If you pass it a u32 slice, can't you just then call len inside of there?

James Munns: Sure, and what's your return type?

Amos Wenger: That's... okay.

James Munns: So ideally you would have a slice, but then you have to return something, and you can't allocate the array inside of the function and then return a slice of it, because then you haven't bound that to anything.

Amos Wenger: Sure. Okay.

James Munns: So that's the answer is: because we need to figure out the types in each step.

Amos Wenger: Makes sense. Gotcha.

That's not quite what we want

James Munns: That's not quite what we want. We now have all of our uniques, but that's not how we would want to use them where we have to like iterate through this array. And like you said, options are probably going to double the size of a u32 array because there's no niche and with alignment, it needs to work out.

We're essentially doubling our size, actually more than that: we want to have four items in the end, and we now have like, 12 words worth of stuff because we have an option u32 or something like that.

Amos Wenger: Yeah, we have identified the uniques, but we haven't shrunken anything. We're actually using more memory. Maybe we should explain what a niche is? It's like for some types, like if you have non zero u32, for example, you know that zero is not a legal value for that. So you can use that to signify none. If you have an option non zero u32, then it's just like a u32, but zero means none and all the other values are some, something. Rust does that a lot. You can do that with like non null pointers. You can do that with enums. An option of an enum is not necessarily larger than the enum.

James Munns: The real code for this definitely does that because I have an option reference to the schema when I'm deduplicating it. And because references can never be zero,

Amos Wenger: Cannot be null yes.

James Munns: So they also get niche'd. So even my option reference is still just the size of a reference. I do take advantage of that there, but not here because this is a simplified example.

Write a function that extracts the uniques from the option array

James Munns: That's not quite what we want. Let's write that function that extracts the uniques from that option array. Now I have a const fn that is const M: usize. So it's generic over const M usize. And we take a slice in, which is our slice of option u32, and we return an array of u32 of length M. We start by creating our output, which is that array of u32 M. We're going to start iterating where we know M is the size of our output. That's how many unique items we expect to have. So we start iterating from zero until we hit that number, and we unwrap each of the items. And this is another one of those cool things that const is if you unwrap and panic in a const fn, the compile just fails. It is a compile time error rather than a run time error.

So we go through and we fill in every value of the output array with Some. And then just as a reasonable check, a robustness check, we then keep iterating to the end of the input array and make sure that all of those are none. So we're kind of verifying that: yes, we got in a slice of six items, you told me there were going to be four unique items in there, I was able to extract all four unique items, and then that additional space was just nothing.

Now we have a whole list of consts

James Munns: When we put that all together, now we have a whole list of consts. The first one is our input array, the second one is the length of that input array, then we do that intermediate step where we turn it into option, array, and the unique size. We then get the deduplicated length, which is just that usize from the intermediate. And then we can call our extract function with the deduplicated length and the input array of options. And then finally, we can turn that fixed sized array of four items into a slice of u32s. Because, again, in const, you can take a reference to a const value as a const, and the compiler will sort it out for you.

Amos Wenger: James, you know how some people have prank shows where they take turns pranking each other? Is that- am I on one of those shows right now? Because I'm looking at the thing and I don't know whether to be impressed or disgusted which if I recall correctly is how you felt about my, "Oh we can cast that lifetime to static because it's just for the duration of a call and it's blocking so within that thread it stays valid," and you were like, "I don't know if that's true..."

James Munns: Yeah, I mean, that's what I go for. I love solutions that are just: how could you, but I couldn't think of a different, better way to do that.

Amos Wenger: Please tell me that you actually have a declarative macro that actually puts all that in module and hides it away from you. Please tell me that.

Declarative macro: input as an ident

James Munns: I'm so glad you asked. So here is that, uh, declarative macro, because you can take the input as an ident, and this is a really interesting technique. It makes sense, but you can kind of smash together macros with const fns, and actually sort of bounce between the two, because you can use macros inside of const fns, and you can use const fns inside of macros. And even though it seems unreasonable, because you think, "Oh well, what are the stages of compilation?"

You can actually sort of bounce back and forth between the two of them and have all of these intermediate consts, which very often then get used as the input to the next stage of something that a macro generates, or have a macro generate multiple const fn's or multiple constant values and sort of bounce between the two until you end up with this.

So this is really only sort of one layer where I'm using a declarative macro just because you have to do this multi step process and the user doesn't want any of those intermediate values. They just want the final value out. Now I have my const LIST_WITH_DUPES, which is an array of u32s, and then I have my const LIST_DEDUPED, which is also a slice of u32s, and I just call that dedupe macro, which expands inside of a const block, which means none of those intermediate values are going to end up in my final program, only the calculated subset.

We might not even end up with the list with dupes in our program if we don't reference it anywhere. Only the consts that we reference are going to be used in our program. Which means we might just have all of this intermediate garbage at compile time. But, we end up with the perfectly sized array of unique integers at runtime that our microcontroller or whatever can use with no allocations or anything.

Amos Wenger: You will not remove from my head the thought... and I know I did rubicon. I presented rubicon on this very podcast! So who am I to say anything? But: if people looked at that, they would be like, "You know what? There's something wrong with Rust and the Rust people and I don't want to touch it." I would understand. It would make sense to me. I couldn't blame them, because it shouldn't exist!

Limitations and room for improvement

James Munns: I think there's room for improvement, don't get me wrong. I talked to Oli about this, and Oli's first response was, "Oh wow." Which made me feel good, because Oli's the one that wrote a lot of the const pieces, or one of the original architect of a lot of the const stuff. But also said: hey, you know. I'm going to have some time in the near future. And these are exactly the pain points we want to get rid of. Not having to have these intermediate steps... no roadmap on this, but like I said, being able to do allocations in const functions and then returning the array because that would make all of these tricks pointless. You would just have one const fn -

Amos Wenger: Of course.

James Munns: - that has the signature we want here, which is just slice to slice.

Amos Wenger: Just like rubicon should not exist because it's working around limitations of the Rust compiler and you could, you should just really go into the Rust compiler and add the flags that you need. It's so interesting because if you didn't know why it is that way- really, I'm trying to approach this from the perspective of someone who's not using Rust on a daily basis and looking all this and going like, "Dear God, why?"

But it's because Rust is doing all this in like super hardcore difficulty because it's not just compiling something to a binary and running it. That's proc macros. Rust does do that in some context. But for const, it's none of that. It's interpreting things and it's not interpreting things the easy way either. It is like doing tracking memory allocations and tagging pointers and doing this weird CHERI like thing because Miri is actually supposed to help you detect undefined behavior and unsafe code. That's where the limitations come from. I'm actually not exactly sure... why do we need all the might of Miri to just do const fns, but I dunno. Do you?

James Munns: Well, I mean,you're going to need to run the code at compile time. And especially if you're cross compiling, you need to work essentially within the Rust abstract machine. So the neat thing about Miri is that it is essentially a Rust abstract machine interpreter, which is why we use it as essentially a sanitizer a lot of the time, because the VM can introspect the world that's going on there. I don't know exactly the decisions that got made there, but it was: well, if you have to abstractly interpret code at compile time, because it might be for a different architecture anyway, then why not have one really good one that can also -

Amos Wenger: Yeah.

James Munns: -enforce all the invariants of the abstract model at the same time?

Amos Wenger: I think it's a case of like: can do more, so it can also do less. In that context, we don't need all the- although I guess it could detect memory unsafety in your const fn code. Like can you have unsafe const fn code?

James Munns: It does. You can.

Amos Wenger: That's terrible.

James Munns: And if you ever do something that would be undefined behavior, your code won't compile.

Amos Wenger: I'm revolted. I'm leaving Rust.

James Munns: So const fn can have pointers and can have unsafe code and that's why maybe uninit could be possible here. It's just that not all the methods have been made const yet.

Amos Wenger: Sure.

Can we take this further?

James Munns: So... can we take this further?

Amos Wenger: No! Enough!

James Munns: The answer is yes, because what if we had a list of lists?

So we have a slice of slices, and all of my slices can be different sizes, and what I'd like to end up is with one slice that contains all of the items that are used here. So where this maps back to reality is when you have these endpoints-

Amos Wenger: I'm sorry. Time out. Where this maps back to reality? 30 minutes into this episode? It was just a great line.

James Munns: So where this maps back to reality is because if you have an endpoint that contains multiple types, so it might have the input type and the output type and the input type might be a composite type of a- like a struct or things like that, it might have its own list of types that are involved in the request and response.

If I have this array of four endpoints, I'm going to end up with this list of each of their types. And like I said, if I'm trying to figure out the list of unique types in the entire system, then I want one array of all the inputs and all the outputs, because there might be duplicates between my different endpoints.

Amos Wenger: So you're also doing flattening...

James Munns: I don't have the code written up for this because I wrote these slides about five minutes before we gave the talk, but I'll walk you through the process.

Amos Wenger: James...

The process on how to get a list of lists

James Munns: So first, we write a const fn that gets the total size. It just walks through the arrays and counts the length of each subarray. So we would say the first one's five, the second one's one, the third one's whatever the number it was. And we just get a sum of what is the upper bound of potential unique values that we could have. And then we turn around and use that as our option u32 allocator basically because we go: if there was absolutely no duplication, this list could be at most this many elements large. And then we repeat the same process that we did for a single one.

We fill all of the sublists into our allocated chunk, and then we get the total number out of how many uniques there were. Then we're back to the same tricks. We then crunch it back down, we end up with one slice, and we can end up with this same sort of behavior. And again, we can write a little procedural macro that hides all of these intermediate steps that are horrific and necessary. But we can end up from an array of array of u32s to a single array of deduplicated u32s.

And like I said, even though it is very wasteful, I'll tell you the algorithm in Postcard RPC also does what's called perfect hashing. When I have all of those keys, I say, "Well, they're all eight byte keys. Could I smash them all down to one byte keys? And would there be any collisions? If yes, could I smash them down to 2 byte keys and not have any collisions?" and if so, then I go, "Ah, I don't need 8 byte keys, I need 2 byte keys," which, when I was talking about what I send over the wire, now I've just shrunk the header of every message from containing an 8 byte key to a 2 byte key, and I can calculate that with no misses at compile time. Which means that you can never screw it up because it's using all the types you're actually using. And it can always get exactly the right number. So this technique is generally called perfect hashing, but this is also something we can do at const time.

Nerd snipe: Huffman coding

Amos Wenger: So, James, I've already been very annoying to you this episode,I want to thank you for your patience, but I have another nerd snipe, for the next episode, of course, which is you should do Huffman, because-

James Munns: Ooh...

Amos Wenger: Right? Maybe you have more than 256 different message types or schemas to deduplicate. But some of them come up more often than not.

James Munns: That's fair.

Amos Wenger: I think the best explanation... Let's put it in terms of UTF-8, they thought. Because that's what people know, instead of Huffman. Okay in UTF-8 uh, if you send "a, b, c" a, b, and c all each take only one byte. But then you have this seventh bit? Eighth bit? What, what am I thinking of?

James Munns: Eighth bit. That's the extension bit.

Amos Wenger: Eighth bit. Yeah, it's the extension bit. So you can have characters, or whatever you want to call them. Okay, this is not the episode about UTF-8. You can have multi byte sequence. So you can have more than 256 or more than 128 different letters. And you could do the same with the schemas. Like maybe some schemas are used very rarely, and you can afford to have like a two, three, four bytes prefix for those messages. But then the ones you use the most often, and you can actually do that because you know how often they show up in schemas. So let's see you that in const code, James!

James Munns: You know how often they show up on schemas, but not how often they are sent over the wire.

Amos Wenger: That's true.

James Munns: You could have a very common type that is very, very rarely actually sent.

Amos Wenger: Exactly. So, you'd have a likely annotation? You do profile guided optimization of schema prefixes?

Make sure it can never be misunderstood

James Munns: This is more about making sure that it can never be misunderstood. Cause that's one of the big things about Postcard RPC is you could do all of these tricks, manually assign message IDs, manually bump them to go, "Oh, we just rolled over 255 items. Now we need 256 items. So now all of my keys need to bump up to two bytes."

You could do that, but I've seen those bugs in production before where you have one system that thinks it's talking one byte keys and another system that's talking two byte keys. And this is also a reason why I chose varints for Postcard RPC you can never misunderstand the length of an integer because they're all varints all the time, which means there's never any room for confusion even if you're compiling on different days.

And this is the same thing is I have a deterministic way of hashing and a deterministic way of crunching from 8 to 4 to 2 to 1, which means that also if you have a system that natively is thinking in 1 byte IDs but someone sends it an 8 byte ID, It can crunch that 8 down to 1 and go, "Oh, I know what you're talking about."

And because you know that the set of messages that it can accept is representable in one byte, that's always acceptable to do that crunching. And if I'm natively thinking in two bytes and you send me one byte, I go: No, I won't crunch that down because I already proved that I need at least two bytes

Amos Wenger: Right, yeah.

James Munns: I don't know if this could collide or not. So I'll refuse to expand it or crunch my numbers down to match it.

Amos Wenger: Well, I'm just glad I got to name drop Huffman, to be completely honest with you.

James Munns: It's very cool. And I think if I wasn't on embedded, I would just do compression because Flate or LZ4 use Huffman encoding as part of the encoding process. And so it is absolutely the right tool to use here, if you're willing to pay for compression.

Amos Wenger: You know, I'm glad that we have embedded. You have the internet of things, and people complain about that, call it the internet of something else, that I'm not gonna say on the podcast, even though I could...

Amanda Majorowicz: But what?

Amos Wenger: It's the internet of shit.

James Munns: You'll drop "fuck" about 10 times and not shit?

Amos Wenger: You made me say it!

Amanda Majorowicz: I'm just curious.

James Munns: We're going to have to check the explicit check box on this episode.

Internet of things & chips in everything

Amos Wenger: Yeah. You have chips in everything. I have chips in my light bulbs at home. But I'm glad, because we have to think about these tricks again. We have to think in terms of constrained resources because there was a gap, like after computers became ridiculously big and powerful and before we started putting chips in light bulbs, where we suddenly didn't have to care anymore, we could be wasteful with everything. And now, sure, we have the Macbook M4... that's like infinitely powerful, and nobody knows what to do with that much compute- yes they do, it's running inference on LLMs- and then we have those tiny chips.

James Munns: This is one of my favorite things because we're getting to the point where microcontrollers are as powerful as the computers from the late 80s and early 90s like desktop computers. There's still this mindset and a lot of embedded is that microcontrollers are very tiny. You can't do anything fancy with them. They need to be bare bones. And this is where a lot of that internet of shit stuff has come from in that people were like, "Oh, I can't afford encryption or authentication because I'm just a little guy." And that's not great.

A lot of what I've been doing with my network protocol stuff is looking at things like AppleTalk which was done on computers in the early 90s and going: well, if the Mac from 1990 could afford to do it, our microcontrollers can probably afford to do that. And they had networking and printer sharing and file systems and things like that.

Sometimes you don't want all those things because you're saving power or whatever, but if you're thinking of "I have to be miserable because I have to shave every byte off of everything," that's not necessarily true. And particularly when we have better compilers like Rust and we can cheat and do a lot of those things at compile time to leverage our ridiculously powerful MacBooks and do all the work ahead of time so that our tiny little 16 kilobyte firmware device doesn't have to worry its pretty little head about it then: yeah, that's exactly the kind of tricks I like doing.

Amos Wenger: Yeah, well, you got my vote.