Amanda Majorowicz: This is Self-Directed Research.
Our hosts, James and Amos, get hyped about different topics and take turns each week
presenting their ideas to each other.
You can check out the website, YouTube or Spotify to watch this
episode's presentation and visit sdr-podcast.com/episodes for
previous episodes with presentations, videos, show notes and transcripts.
New episodes are published every Wednesday.
This episode is brought to you by CodeCrafters.
Check out the link in our show notes or listen at the end for
more information after James elaborates on "Compile Time Crimes."
Hope you enjoy!
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.
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?
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.
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.
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.
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.
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.
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 fn`s, you can use them on non `const fn`s.
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.
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
Amos Wenger: out.
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.
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::`, 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.
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.
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.
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.
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 fn`s, and you can use `const fn`s 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!
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 fn`s, 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.
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...
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.
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?
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.
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.
James Munns: This episode is sponsored by CodeCrafters.
CodeCrafters is a service for learning programming skills by doing.
CodeCrafters offers a curated list of exercises for learning programming
languages like Rust or learning skills like building an interpreter.
Instead of just following a tutorial, you can instead clone a repo that contains
all of the boilerplate already, and make progress by running tests and pushing
commits that are checked by the server, allowing you to move on to the next step.
If you enjoy learning by doing, sign up today using the link at
sdr-podcast.com/codecrafters, or use the link in the show
notes to start your free trial.
If you decide to upgrade, you'll get a discount and a portion of
the sale will support this podcast.
That's sdr-podcast.com/codecrafters.
Thanks to CodeCrafters for sponsoring this episode.