Forem: Phoebe Goldman

Eliminating CLOS for a 4.5x speedup

Phoebe Goldman — Sat, 24 Dec 2022 02:25:19 +0000

My friend Nathan pinged me today asking me for help optimizing the lexer for some weird language he's building. Well, actually, our conversation started,

Nathan Ringo

Sigh, rly wish CL had &mut references other than using macros instead of functions

phoebe Goldman

i do not wish that
but they’re easy to emulate using clojures or conses as something like Cell

Nathan Ringo

I mean I don't wish they were as pervasive as in rust
But in eg my parser I've got a bunch of state I'd like to be stack allocated, but shared between things

I brainstormed some ways he could accomplish that (the options I proposed were either putting the state in a struct and dynamic-extent allocating an instance, or putting it in a let and writing all the functions that operate on it in an inner labels). But eventually he let slip that he actually wanted to get his lexer to run at 1MiB/s or faster, and stack-allocating its state was one of his thoughts of how he might do it.

Now, not to sound too full of myself, but I consider myself an expert in optimizing Common Lisp code. The first thing I told him to do was to compile with (optimize (speed 3) (safety 1) (debug 0)). Oddly, the effects were very platform-dependent; on an Intel i7, that saw a speedup of a few percent, but on an Arm A72, it was a few percent slower, because somehow it garbage collected more. Keep in mind that we weren't particularly collecting rigorous data; we were looking for low-hanging fruit, not micro-optimizations.

I asked him to send me the source, and it turned out that all of his data was in CLOS classes. (More specifically, he'd worked out some whacky arcana with the metaobject protocol to make CLOS classes with read-only slots. I've always said "just don't mutate them," but hey, to each their own, I guess.) Now I love CLOS. But it's slow as hell. And it gets way slower as soon as you start messing with the MOP. The strategy I advocate for is, develop your prototype using CLOS, and then, if you need it to be faster, convert it to using defstruct. So that's what I did.

Conveniently, defstruct already supports defining structures with read-only slots, so we didn't even have to resort to my laissez-faire "just don't mutate it" attitude. I grepped for defclass in his project, replaced every instance with a similar defstruct, and then replaced all the make-instance calls with structure constructors for good measure. He wasn't using multiple inheritance (or any inheritance at all, actually), so the changes were trivial, and purely syntactic. No changes to logic required.

So I ran his benchmark on my m1 MacBook Air, and the speedup was absurd. For the old version, SBCL's time reported:

Evaluation took:
  3.155 seconds of real time
  3.112716 seconds of total run time (2.781656 user, 0.331060 system)
  [ Run times consist of 0.358 seconds GC time, and 2.755 seconds non-GC time. ]
  98.67% CPU
  66 lambdas converted
  1,614,459,488 bytes consed

The new version, just replacing CLOS classes with defstruct structs, showed:

Evaluation took:
  0.680 seconds of real time
  0.664909 seconds of total run time (0.543139 user, 0.121770 system)
  [ Run times consist of 0.125 seconds GC time, and 0.540 seconds non-GC time. ]
  97.79% CPU
  15 lambdas converted
  405,298,304 bytes consed

So obviously, 3.155s is like 4.5x as long as 0.680s. But also, the CLOS version is consing roughly 4x as much to produce the same number of objects (or at least, objects visible to his code). This doesn't particularly surprise me, but I think it may be unexpected to people less familiar with the internals of Common Lisp. The short version is that CLOS is the most powerful object system on the market, and implementing it efficiently is really hard. In particular, supporting dynamic (re-)definition of classes and methods means there's a lot of state, a lot of lookups, and a lot of caching.

I'd like to point out, just in case: the lesson here is not "don't use CLOS because it's slow." CLOS is a fantastic tool, especially for interactive development. The lesson is, write your code with CLOS, and if you're concerned about needing it to be fast, stick to the subset of CLOS that corresponds to defstruct. Then, once you get to a place of actually caring about performance, try replacing your classes with structs. Start with the classes that you construct many instances of and access a lot; rarely-used classes won't matter.

Now go forth and impress your friends with your ability to make their code run several times faster in 10 minutes of editing!

rustc frustrations: trait coherence edition

Phoebe Goldman — Sat, 25 Sep 2021 17:56:53 +0000

Problem: for some hobby-hacking OS dev I’m doing, I need (want) to implement drivers for a few different UART consoles. The first part of these drivers I build is for writing output from my little baby OS over the UART, which I can read from a real computer. This allows me to do some basic printf debugging for the rest of my system.

A naive good-enough implementation of writing a byte to a UART is: wait in a busy-loop until the UART is ready for a byte, then push the byte into it. To write a string, just do that for every byte in the string. To do this, you need to implement two operations which are specific to the UART chip you’re using:

can_write: test if it’s ready to receive a byte
unchecked_write_byte: push the byte into it

Then, you plug those two implementations into a generic write_byte, which in turn you plug into a generic write_str, and now you can write to your UART!

To that effect, the code I wrote was:

pub trait Console {
  /// write `byte` to `self` without first verifying that `self` is ready to recieve a
  /// byte.
  unsafe fn unchecked_write_byte(&mut self, byte: u8);
  fn can_write(&mut self) -> bool;
  fn blocking_write_byte(&mut self, byte: u8) {
    block_until(|| self.can_write(), 1);
    unsafe { self.unchecked_write_byte(byte); }
  }
}

impl<T> core::fmt::Write for T
where T: Console,
{
  fn write_str(&mut self, s: &str) -> fmt::Result {
    for b in s.bytes() {
      self.blocking_write_byte(b);
    }
    Ok(())
  }
}

Which, of course, doesn't compile. Can you spot the error? If you've written any serious amount of Rust, I'm sure you can, but for non-Rustaceans, the problem is:

error[E0119]: conflicting implementations of trait `core::fmt::Write` for type `&mut _`
  --> src/console.rs:18:1
   |
18 | / impl<T> core::fmt::Write for T
19 | | where T: Console,
20 | | {
21 | |     fn write_str(&mut self, s: &str) -> fmt::Result {
...  |
26 | |     }
27 | | }
   | |_^
   |
   = note: conflicting implementation in crate `core`:
           - impl<W> Write for &mut W
             where W: Write, W: ?Sized;
   = note: downstream crates may implement trait `console::Console` for type `&mut _`

For more information about this error, try `rustc --explain E0119`

The rule at play here is called "trait coherence," so if you want to read more, that's your search term. The short version is that the compiler requires that there must be at most one implementation of a trait for each type; not type can have two or more competing implementations of the same trait. This saves the compiler developers from having to answer some hard questions about which implementation they should choose when offered alternatives, and mostly seems like a reasonable requirement.

The problem, from where I'm standing, is that the rules which prevent you from defining multiple conflicting trait implementations are a bit overzealous. In my case, no type ever will have conflicting implementations of Write, since none of the handful of types for which I've implemented Console are mutable references and therefore none of them get the implementation from Core for &mut W: Write + ?Sized.

But, as the error message points out, "downstream crates may implement trait console::Console for type &mut _." I'm compiling a binary, not a library, so "downstream crates" is not a meaningful concept, but whatever. Let's try making Console pub(crate), so that we know for sure that no "downstream crate" will ever implement Console for &mut W: Write + ?Sized.

Of couese, changing pub trait Console to pub(crate) trait Console doesn't change anything. Same error, same meaningless note about downstream crates.

I asked in the Rust Discord about what I should do, and the responses I got basically just made me more frustrated. To be clear, the people who responded were very helpful, and offered what I believe to be the best advice possible. It's just that rustc doesn't permit a good solution to my problem.

As is, I got two plausible suggestions, which look to me like these two implementations:

Candidate 1: write an `impl Write` for each implementor of `Console`.

This would essentially look like:

pub trait Console {
  /// write `byte` to `self` without first verifying that `self` is ready to recieve a
  /// byte.
  unsafe fn unchecked_write_byte(&mut self, byte: u8);
  fn can_write(&mut self) -> bool;
  fn blocking_write_byte(&mut self, byte: u8) {
    block_until(|| self.can_write(), 1);
    unsafe { self.unchecked_write_byte(byte); }
  }
  fn write_str(&mut self, s: &str) -> fmt::Result {
    for b in s.bytes() {
      self.blocking_write_byte(b);
    }
    Ok(())
  }
}

impl Console for Pl011 {
  unsafe fn unchecked_write_byte(&mut self, byte: u8) {
    // this part is boring & irrelevant
  }
  fn can_write(&mut self) -> bool {
    // same with this
  }
}

impl fmt::Write for Pl011 {
  fn write_str(&mut self, s: &str) -> fmt::Result {
    Console::write_str(self, s)
  }
}

impl Console for Pc16550d {
  unsafe fn unchecked_write_byte(&mut self, byte: u8) {
    // this part is boring & irrelevant
  }
  fn can_write(&mut self) -> bool {
    // same with this
  }
}

impl fmt::Write for Pc16550d {
  fn write_str(&mut self, s: &str) -> fmt::Result {
    Console::write_str(self, s)
  }
}

Notice that the two fmt::Write implementations have the same text other than the name of the implementing type. Not my favorite...

Candidate 2: use a generic wrapper struct to implement `Write`.

pub trait Console {
  /// write `byte` to `self` without first verifying that `self` is ready to recieve a
  /// byte.
  unsafe fn unchecked_write_byte(&mut self, byte: u8);
  fn can_write(&mut self) -> bool;
  fn blocking_write_byte(&mut self, byte: u8) {
    block_until(|| self.can_write(), 1);
    unsafe { self.unchecked_write_byte(byte); }
  }
}

pub struct ConsoleWriter<T>(T);

impl<T> fmt::Write for ConsoleWriter<T>
where T: Console,
{
  fn write_str(&mut self, s: &str) -> fmt::Result {
    let c = &mut self.0;
    for b in s.bytes() {
      c.blocking_write_byte(b);
    }
    Ok(())
  }
}

That part alone isn't so bad, but now I also have to wrap my Console instances in a ConsoleWriter struct, so

use spin::Mutex;
use crate::driver::uart::Pl011;

pub static CONSOLE: Mutex<Pl011> = Mutex::new(
  unsafe { Pl011::new(0x3F20_1000usize as *mut u8) }
);

becomes

use spin::Mutex;
use crate::driver::uart::Pl011;
use crate::console::ConsoleWriter;

pub static CONSOLE: Mutex<ConsoleWriter<Pl011>> = Mutex::new(
  ConsoleWriter(unsafe { Pl011::new(0x3F20_1000usize as *mut u8) })
);

Again, I don't love this.

My solution: just don't implement `Write`.

After writing each of these solutions and considering their merits and flaws, I realized that, hey, who the hell even needs core traits? If interacting with the standard library (or the little part of it I can use on a bare-metal target) is going to make me miserable, I just won't do it.

Will this make my code more brittle? Yes. Will it be harder to read, since people joining the project will have to familiarize themselves with my own custom set of traits instead of the standard traits they already know? Probably. Will I lose the ability to interoperate with libraries that use Write to implement generic functionality, and end up reinventing the wheel instead? Almost certainly. Do I care? Not at all.

why i (sometimes) prefer dynamic typing

Phoebe Goldman — Wed, 22 Jan 2020 06:24:19 +0000

this is a response to Alexis King's blog post "No, dynamic type systems are not inherently more open."

i've written a fair amount of Rust in my day. (starting my post like this is my way of defending myself against angry static typers). i know the value of a strong type system which proves the assumptions you make in your code, and i know that static typing is an elegant way to annotate a program with compile-time invariants. i know the joy of catching bugs in the compiler and fixing them before they ever have to run, of ci time saved by catching a mistake in a local compile rather than a remote test suite, and i know how much a consistent and versatile type language improves generated documentation and library interfaces. but sometimes, dynamic typing is still the right choice, and y'all need to shut up and get over it.

i also don't want this to seem like an ad-hominem attack. i'm responding to this blog post because i think Alexis King did a good job of concisely
articulating some arguments that i've seen in weaker and less well-considered forms elsewhere, and i think she gives me a good opportunity to explain why i feel differently.

as their first argument, the author of that blog post presents an elegant and intuitive Javascript program which concisely does the correct thing (namely, ignoring events of unknown event_type when it falls through the switch):

const handleEvent = ({ event_type, data }) => {
  switch (event_type) {
    case 'login':
      /* ... */
      break
    case 'signup':
      sendEmail(data.user.email, `Welcome to Blockchain Emporium, ${data.user.name}!`)
      break
  }
}

here's King's strongly-typed Haskell alternative:

data Event = Login LoginPayload | Signup SignupPayload
data LoginPayload = LoginPayload { userId :: Int }
data SignupPayload = SignupPayload
  { userId :: Int
  , userName :: Text
  , userEmail :: Text }

instance FromJSON Event where
  parseJSON = withObject "Event" \obj -> do
    eventType <- obj .: "event_type"
    case eventType of
      "login" -> Login <$> (obj .: "data")
      "signup" -> Signup <$> (obj .: "signup")
      _ -> fail $ "unknown event_type: " <> eventType

instance FromJSON LoginPayload where { ... }
instance FromJSON SignupPayload where { ... }

handleEvent :: JSON.Value -> IO ()
handleEvent payload = case fromJSON payload of
  Success (Login LoginPayload { userId }) -> {- ... -}
  Success (Signup SignupPayload { userName, userEmail }) ->
    sendEmail userEmail $ "Welcome to Blockchain Emporium, " <> userName <> "!"
  Error message -> fail $ "could not parse event: " <> message

which this is a considerably longer, but still quite intuitive, block of
Haskell which does the wrong thing (namely, error when a message's event_type falls through the case statement). this version is more lines of code and makes more information explicit which would be assumed in the Javascript version. King considers the latter an advantage, and describes how it's possible, at the cost of some additional thought, to do the wrong thing in Javascript or the right thing in Haskell.

in case i haven't been clear enough, i think this is a pretty bad
argument. it's trivially true that it's possible to translate a program from any one Turing-complete language to another, which is pretty much the only real point unambiguously in Haskell's favor in this case. King touts it as a feature that Haskell requires the programmer to compute the most general types of their terms in their heads, but i see that as a huge point in Javascript's favor. in programs that perform trivial transformations on complex objects, i find that this effort is rarely worthwhile. King, though, is happy to dismiss the overhead during an apparent response to a Reddit comment in favor of dynamic typing,

It’s definitely more boilerplate, but some extra overhead for type definitions is to be expected (and is greatly exaggerated in such tiny examples), and the arguments we’re discussing aren’t about boilerplate, anyway.

i contest the claim, actually, that this is a case where the overhead is
exaggerated by the size of the example, as i have frequently written and read interchangeable or equivalent Javascript in the wild. i believe it's useful, valuable and a huge strength of Javascript that it's easier to conceptualize and write this exact function and that it takes fewer lines of code. this may not have been the subject of the comment in question, but i think it's actually worth discussing, whereas i frankly think the actual comment is inane and could have been chosen as a strawman (though it seems unlikely to me that it was). the actual point of dynamic typing is that it makes doing "the obvious thing" easier to think of, easier to write and easier to read, provided you and the language agree what is "the obvious thing". explicit static typing and type-based formalism are valuable in complex problem spaces, but actually, not all problem spaces are that complex. sometimes "the obvious thing" really is obvious, and i just want to write it and move on with my life.

King writes somewhere just past the introduction of her premise,

...programs are not capable of processing data of a truly unknown shape regardless of typing discipline, and static type systems only make already-present assumptions explicit.

if this is a surprise to you (which, sadly, it may be to some of my coworkers and classmates...), you need to deepen or reconsider your understanding of dynamic type systems. this is true, and you should know it. but i fear that, all too frequently, newer programmers who have just discovered this fact lose sight of the fact that, in simpler problem spaces, leaving assumptions implicit can save valuable mental overhead, which means work, which means time, which means money.

also, in cases where the assumptions are obvious but programmatically complex, it may not be worth the time to design a type system which accurately encodes the language's behavior. King refuses to refute this point; she responds to a HackerNews comment which is short and somewhat ambiguous, and interprets it in a way that leaves me unsatisfied. the comment reads:

What would be the type signature of, say, Python’s ~pickle.load()~?
from [https://news.ycombinator.com/item?id=21479933]

King responds with (a longer and clearer version of) the obvious answer, which is that pickle.load() (pickle is apparently a library that serializes and deserializes arbitrary Python objects) returns an Any, and that you'll have to do type-checks before you use it. while this is an accurate type, it's not particularly useful. in fact, i'll make the bold claim that it's never useful to describe a value as an Any, because that just means you know nothing about it. the dynamically-typed code is just a shorthand that inserts implicit type-assertions wherever necessary to make the program well-typed, and frankly, i prefer not to write them myself. it would be useful if a type system could predict and verify the return-type of pickle.load(file) by combining its argument with information about when the program calls pickle.dump(T, dump), but i think in this case, building the type-checker would be more trouble than stomping all the bugs it would catch.

A simple Haskell program

Phoebe Goldman — Thu, 06 Dec 2018 04:26:52 +0000

Today, I'd like to share a short Haskell program which helped improve my understanding of the language, in the hopes that you all might learn a bit about it.

module Main where

data EndlessList a = Cons a (EndlessList a)

repeatForever :: a -> EndlessList a
repeatForever x = Cons x (repeatForever x)

genSequence :: a -> (a -> a) -> EndlessList a
genSequence init trans = Cons init (genSequence next trans)
    where next = trans init

naturalNumbers :: EndlessList Integer
naturalNumbers = genSequence 0 succ

printAllOf :: Show a => EndlessList a -> IO b
printAllOf (Cons a b) = putStrLn (show a) >> printAllOf b

main :: IO ()
main = printAllOf naturalNumbers

I know Haskell is pretty crazy, so I'll do my best to break this down in maximum detail. You can see how it compiles on Godbolt.

If you have ghc installed, you should be able to copy that source into a file named Main.hs, compile it with ghc Main.hs, and run it with ./Main. If you do, you'll see that it prints the natural numbers, starting from 0, and that it doesn't stop until you close the process with <ctrl>-c.

module Main where

Haskell's modules are pretty similar to Javascript's. The important thing is that any program that wants to build into an executable that we can run must define a module named Main which contains a value main :: IO (). I'll get to that down at the bottom of the source file.

data EndlessList a = Cons a (EndlessList a)

This line does several things. Reading from right to left:

data statements define new types
EndlessList will be the name of our new "type constructor"
a will be an argument to EndlessList --- think of EndlessList as a function from one argument which returns a type
= separates the type constructor (EndlessList a) from the "value constructor" Cons a (EndlessList a)
Cons is the name of the "value constructor". It's common to give your type constructor and value constructor the same name, like data EndlessList a = EndlessList a (EndlessList a), but I felt that using different names added clarity to this example. The name "cons" comes from Lisp, and is used in functional programming to mean a pair
a and (EndlessList a) denote two arguments to the value constructor Cons of the respective type. All in all we are left with two things: a type EndlessList a and a function named Cons of a -> EndlessList a -> EndlessList a (that's how Haskell writes function types. For example, a function that adds two numbers together might have type Int -> Int -> Int. The last type, not followed by an arrow, is the return type; all the others are arguments).

Right away you might notice something a little strange --- there's no way obvious way to construct, store, or operate on a value which must by definition be of infinite length. Despite this, ghc is able to run this code and it does immediately start printing numbers and not stop.

repeatForever :: a -> EndlessList a
repeatForever x = Cons x (repeatForever x)

This block defines a function repeatForever. The first line describes its type: for any type a, takes a value of type a and returns an EndlessList a. The second line tells how to compute it: call the constructor Cons first with x and then with the result of recursively calling repeatForever x.
This function is infinitely recursive, and if you tried to write it in Javascript/C/C++/Java, it would either crash or never terminate. In Haskell, though, where lazy evaluation is king, repeatForever x does exactly what you want it to: repeats x forever.

genSequence :: a -> (a -> a) -> EndlessList a
genSequence init trans = Cons init (genSequence next trans)
    where next = trans init

This function is like repeatForever, but way cooler. If you can read that type, good for you. init and next will each be of type a, and trans will be a function that takes an a and returns an a. This function creates a list whose first element is init and whose nth element is the result of applying trans to its (n - 1)st element.

Let's test it out with:

naturalNumbers :: EndlessList Integer
naturalNumbers = genSequence 0 succ

Here, naturalNumbers is an EndlessList of Integers. As we all know, the natural numbers start with 0, and the successor function succ will calculate the next natural number. We could replace succ with the anonymous function \n -> n + 1 for no change, but I think writing succ in my code is funny.

Haskell's hard-to-grok separation of concerns relegates input/output to a Monad called IO. Wiser people than I have tried and failed to describe what monads are and their implications, so I will not try.

Instead, I will tell you only that the type IO b means an input/output action which will result in a value of type b.

printAllOf :: Show a => EndlessList a -> IO b
printAllOf (Cons x y) = putStrLn (show x) >> printAllOf y

printAllOf will, for any type a that can be shown, take an EndlessList a and perform some IO action resulting in any arbitrary type b. Now, because our EndlessList will be infinite, this I/O action will never terminate, which is why it can claim to result in a value of any type b.

Instead of a recursive function, here we have a recursive IO action. The >> infix operator, like foo >> bar, denotes a sequence of operations. I read foo >> bar as "do foo and discard the result, then do bar". putStrLn is an IO action which prints a String to standard output, followed by a newline, similar to Javascript's console.log. show formats a value as a String, so putStrLn $ show x converts x into a String and then prints it to standard output.

main :: IO ()
main = printAllOf naturalNumbers

main, like in C/C++/Rust/Java/etc., is the "entry point" of a program. In Haskell, main is an IO action with no result, which means its type is IO (). We define ours as printing all of the natural numbers, which is what our program does.

Edit

The original code of this post used

printAllOf (Cons x y) = (putStrLn $ show x) >> printAllOf y

As per alirun's advice, I replaced that line with:

printAllOf (Cons x y) = putStrLn (show x) >> printAllOf y

On `union` in C

Phoebe Goldman — Sat, 01 Dec 2018 06:32:48 +0000

This is a response I wrote several months ago on /r/C_Programming that I wrote to the question "Can someone explain unions?" No one ever read it, as far as I can tell, because /r/C_Programming is basically abandoned and most people ignore that kind of "I didn't know what I was getting into when I signed up for a college course that uses C!" cry for help.

I thought the question was pretty interesting, though, because in an age where constructs like Rust's enum; Haskell's sum types; and object-oriented subclassing in Java, C# and C++ are available as higher-level and relatively narrow constructs for polymorphism, it's not always immediately obvious how unions are (ab)used in C.

There are two common use cases for unions. One is for when you want to store a value that might be one of several different types, which is called a tagged union. For a common example, consider a type Number which can represent either an int or a float:

#include <stdio.h>

enum NumberKind { FLOAT, INT };
struct Number {
  enum NumberKind kind;
  union {
    int i;
    float f;
  };
};

void output_number(struct Number * n) {
  switch (n->kind) {
  case INT:
     printf("The integer %d\n", n->i);
     break;
  case FLOAT:
    printf("The float %f\n", n->f);
    break;
  }
}

int main() {
  struct Number three = { .kind = INT, { .i = 3 } };
  struct Number two_point_five = { .kind = FLOAT, { .f = 2.5 } };

  output_number(&three);
  output_number(&two_point_five);

  return 0;
}

The union section of struct Number will hold either an int i or a float f, and the enum NumberKind kind field tells the programmer which it is. The implementations of many interpreted languages use tagged unions (often with fascinating optimizations, but that's a story for another time) to represent values --- that's why you don't have to write types like int, float, or struct Number in Javascript.

As with most things in C, there's a lot of room for mistakes; there's nothing stopping me from reading n->i regardless of what n->kind is, and believe me when I say that I and every other C programmer have spent more hours than we'd like debugging exactly that.

That ability, though, is vital to the other use of unions, type punning. Wikipedia has a great article on type punning, which it defines as "any programming technique that subverts or circumvents the type system of a programming language in order to achieve an effect that would be difficult or impossible to achieve within the bounds of the formal language."

That's kind of a mouthful, but the point is that, at a certain point, you and the type system are going to agree, and type punning is the way you cheat. Rust has it in the standard library, but in C we're limited to either pointer-casts or unions.

Consider code for pointer-tagging.

#include <stdint.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>

union TaggedPointer {
  void * p;
  uintptr_t i;
};

// set the least significant bit of `ptr`
void * tag_a_pointer(void * ptr) {
  union TaggedPointer tagged = { .p = ptr };
  tagged.i |= 1;
  return tagged.p;
}

// true iff the least significant bit of `ptr` is set
bool has_low_bit_set(void * ptr) {
  union TaggedPointer tagged = { .p = ptr };
  return (tagged.i & 1) == 1;
}

int main() {
  void * some_pointer = malloc(16);

  assert(!has_low_bit_set(some_pointer));

  void * tagged = tag_a_pointer(some_pointer);
  assert(has_low_bit_set(tagged));

  return 0;
}

If you're not familiar, the idea behind pointer tagging is that the low few bits of a pointer go unused because of some weird crap, and so they can be used the same way as the tag in a tagged union.

To do that, though, you need to be able to operate on the bits of the pointer as if they were an integer. Because TaggedPointer.i and TaggedPointer.p occupy the same block of memory, altering one (as in tag_a_pointer) changes the other. Many people thing this looks cleaner than a pointer-cast, which might look like:

void * tag_a_pointer_but_with_pointer_casts(void * ptr) {
  uintptr_t i = *((uintptr_t *)(&ptr));
  i |= 1;
  return *((void **)(&i));
}

Aside: The reason my two examples in this post are similar is not because unions are limited to use in tagging for interpreted languages, but just because my hobbyist work is limited to that field. Both patterns pervade the language --- I first encountered tagged unions while digging through the C source for the Xen hypervisor (a pretty brutal first exposure to C, but I was just an intern, so it didn't really matter). The first example I ever saw of type punning was FastInverseSquareRoot, which is an adventure in low-level programming unto itself.