# i-h95QIGchY transcript
# Source: https://www.youtube.com/watch?v=i-h95QIGchY
# Title: Assuming as Much as Possible
# Speaker: Andrew Reece
# Conference: BSC 2025 (Better Software Conference)
# Fetched: 2026-06-08
# Segments: 3719

---

[00:00] Now I get to introduce Andrew Reese who
[00:02] I'm very lucky to work with at my day
[00:05] job where I work on Zcash. Andrew works
[00:07] on Zcash as well with me. Um Andrew is
[00:11] the only person well okay so I'm going
[00:15] to do an analogy that I heard John say
[00:16] once which is there's some kind of zen
[00:19] thing where you're pointing at the moon
[00:21] and you're trying to point at the moon
[00:23] but the guy is like yeah you're showing
[00:27] me your finger. I've seen your finger
[00:28] before. and you're like, "No, no, but
[00:30] like it's the moon." Like the thing, you
[00:32] know, it's the thing like over there.
[00:35] Um, so I have lots of conversations with
[00:37] Andrew where like there are these
[00:40] extremely like meta insightful
[00:42] conversations about programming and the
[00:44] nature of programming and patterns that
[00:46] show up and all these kinds of things.
[00:48] And um although he told me that he
[00:51] doesn't feel very smart about these
[00:53] things, I always find that these
[00:54] conversations for me are extremely
[00:56] stimulating. Uh, and I have all kinds of
[00:59] new ideas talking to Andrew. And so he's
[01:01] going to be talking about, see, I
[01:04] thought this was going to be like
[01:05] patterns in software, but it says
[01:07] assuming as much as possible. So, you
[01:10] know, I could have been informed earlier
[01:12] about that, but anyway. So, give it up
[01:14] for the very, very wise and insightful
[01:17] Andrew Ree.
[01:27] Hello everyone and thank you Sam for
[01:29] that far too kind introduction. Um yeah
[01:32] for those who don't know me I'm Andrew
[01:33] Reese. I am uh mostly known around these
[01:36] circles as the creator and lead dev on
[01:39] WhiteBox. Uh if you're unfamiliar it the
[01:42] very short version is it's a debugger
[01:44] with the timeline so you can track how
[01:46] data changes across time. The slightly
[01:48] longer version is that it's uh exploring
[01:52] what happens if you can generalize the
[01:54] features of a debugger and a profiler
[01:57] and a logger and a ripple. Um but we're
[02:00] not going to be talking too much about
[02:01] whitebox itself. Um I'll be pulling a
[02:05] few examples from the codebase just as
[02:07] jumping off points.
[02:10] My role in whitebox other than coding a
[02:15] large amount of it myself has been
[02:17] managing kind of one to five contractors
[02:20] at different times and as part of that
[02:24] it's very useful if you can understand
[02:27] the entire codebase and the basic
[02:31] premise of this talk is
[02:34] finding the
[02:37] patterns there you Go Sam. There are
[02:39] there are patterns in here.
[02:42] Finding the patterns uh in
[02:46] uh ways that you can write code that are
[02:48] friendly to both the developer and to
[02:51] the machine. So
[02:55] here we have two very exciting circles.
[02:58] Uh we have CPUs with all of their things
[03:02] that they're amazing at. Well, they can
[03:04] be they're very stupid, but they're very
[03:05] stupid very quickly, which is really
[03:07] helpful.
[03:09] um they aren't so good when it comes to
[03:14] indirection comes when it comes to
[03:16] branching when it comes to looking at
[03:18] memory they haven't seen before very
[03:19] quickly and then humans have their own
[03:22] set of features uh and there's actually
[03:25] a surprising amount of crossover here
[03:27] we're also not great at context
[03:30] switching into new places or jumping
[03:33] around and remembering the entire stack
[03:35] of things that we've been looking at and
[03:36] so it seems Like there should be some
[03:38] intersection between these for
[03:41] um
[03:43] making sure that we do things that are
[03:46] sympathetic to the machine and also are
[03:49] easy for humans as developers to
[03:51] understand your code. Now I mean so far
[03:55] science has not quite been able to
[03:57] determine whether developers are
[03:58] actually human. Um but it's it's close
[04:01] enough for the moment. Uh the
[04:09] Yeah, we'll be looking for the places on
[04:12] in this overlap where both humans and
[04:15] computers are able to understand and
[04:18] operate on these things quickly. We're
[04:20] not so much looking for complete
[04:22] optimization, but a default path that is
[04:26] straightforward, concrete, and then the
[04:30] CPU will by default be pretty good,
[04:33] although you can always optimize
[04:34] further.
[04:36] I want to take a brief moment to
[04:38] separate generalization from abstraction
[04:41] here. Uh in the there's a lot of
[04:43] crossover uh but I think they're
[04:44] different. And so I see generalization
[04:48] as um describing the
[04:54] describing the problem space with a
[04:57] slightly expanded vocabulary so that you
[04:59] can talk about more things but you can
[05:01] still talk about the same thing in
[05:03] exactly as much detail as you could
[05:04] before. And so my example here would be
[05:06] if you had a minimum function and you
[05:09] can do minimum of a and b you can
[05:11] generalize that to a minimum of anything
[05:14] in an array. You can still do two a two
[05:16] element array but you can do this larger
[05:19] domain as well. Now there are costs
[05:22] associated with generalizations but
[05:24] typically they don't have this same
[05:26] indirection that abstractions do. So
[05:29] abstractions as I tend to think about
[05:31] them are kind of a layer on top of the
[05:34] thing that you're actually doing. Uh
[05:36] where only certain variables only
[05:39] certain features are allowed to bubble
[05:40] through. It's kind of a semi-permeable
[05:42] membrane between the implementation and
[05:45] the um the interface that is presented
[05:48] to the presented above.
[05:51] Okay, let's get into it.
[05:54] Um,
[05:56] for me, lifetimes and stable pointers
[05:59] are a an incredibly useful architectural
[06:03] tool. So, fortunately, most of you have
[06:06] been to the Echoslavs talk the other
[06:08] day, and you'll know how he uses arenas.
[06:12] My use is very similar. Uh, but I'm just
[06:14] going to very briefly um walk through
[06:17] what arenas are for anyone unfamiliar.
[06:20] Uh the basic version of this is that you
[06:25] using some virtual alert tricks have
[06:28] what seems like an infinitely long block
[06:30] of bytes. Uh and then as you want to
[06:33] allocate things, you allocate the first
[06:36] bit and you bump the amount that you've
[06:39] used. Uh you push some other thing on.
[06:42] So maybe you push an array, then you
[06:43] push a strct, then you push a string. Uh
[06:45] and then at some point you are done with
[06:48] those things and you can either pop back
[06:50] to a previous point like that you've
[06:52] seen recently. Maybe you no longer need
[06:54] that string anymore.
[06:56] Uh you could have generated it for print
[06:59] f and then you're done with it for now.
[07:01] Or uh very usefully you can just wipe
[07:05] the entire thing and your arena is now
[07:08] empty and ready to be used for something
[07:09] else.
[07:10] Now in practice uh in my codebase and I
[07:13] think most others who use arenas uh we
[07:15] tend to use multiple of them and so we
[07:18] have many of these stacks that are
[07:21] operating in parallel. Um you can think
[07:24] of these stacks somewhat like a call
[07:26] stack in that after you're finished with
[07:28] things you can you can pop back. Um but
[07:32] the
[07:34] so so what this means is if you're if
[07:35] you're pushing onto one arena
[07:38] and you have your your data at the end
[07:41] um then once you've popped back
[07:45] everything after that point is
[07:47] invalidated effectively. Uh and so this
[07:50] presents our first problem which is uh
[07:53] we quite often want to interle things
[07:57] that happen on different lifetime things
[07:59] that are conceptually nested but which
[08:03] happen um yeah in interled.
[08:07] So
[08:09] as well as having the hierarchy of the
[08:12] the stack itself, there's also a
[08:15] conceptual hierarchy of uh the arenas
[08:19] themselves.
[08:21] So here we have kind of permanent app
[08:23] lifetime arena and pretty much
[08:25] everything is conceptually underneath
[08:28] that. Um,
[08:31] now one of the nice things if you have
[08:33] this conceptualization is that if an
[08:37] inner arena gets a pointer to something
[08:41] in an outer arena,
[08:43] it knows that its lifetime is going to
[08:45] outlive the lifetime is going to extend
[08:47] past its own. And so if we can make sure
[08:51] those pointers are stable, then we can
[08:53] keep that pointer indefinitely until say
[08:56] our run closes. um it it can keep
[08:59] pointers into the app.
[09:03] The interle for instance an example of
[09:05] that happens inside runs. Um as a
[09:08] debugger we get uh all sorts of debug
[09:11] info from the OS and that includes a
[09:15] breakpoint. So when a breakpoint
[09:18] happens, the process stops, we get
[09:20] control and we want to do some caching
[09:22] to make sure that we're only reading the
[09:25] same memory uh once within within that
[09:28] break, for instance. And
[09:32] we do that caching interled with
[09:35] recording stuff that is going to be true
[09:37] for the entire run. So we want to save
[09:40] some data, save some recording uh and so
[09:43] that will go in the run while the stuff
[09:45] that only wants to stay in the uh that
[09:48] only extends for the entire event stay
[09:50] in the event cache. Okay, I think I've
[09:53] done that to death. Let's move on to
[09:55] some more interesting topics. Type
[09:58] mappings. Now you're going to see some
[10:00] familiar things here if you were at
[10:02] Ryan's talk.
[10:05] Whenever you're designing a system, you
[10:09] have a large amount of choice in terms
[10:13] of where what you determine statically
[10:17] at compile time in your type system and
[10:19] what gets determined dynamically at
[10:22] runtime.
[10:24] in a an initial incarnation of whitebox
[10:27] where the primary focus was around JIT
[10:30] compiling small chunks of code and then
[10:33] uh debugging those. We had control over
[10:35] the full um
[10:38] uh the full pipeline of compilation and
[10:40] we we happened to be using clang
[10:43] um which generated dwarf information.
[10:46] The so the first version of this we we
[10:49] were using this dwarf debug information
[10:52] and that is every type of debug
[10:54] information excepting line information
[10:56] but that's beside the point. So types
[10:59] compilation units uh functions variables
[11:02] all of that is a debug information
[11:03] entry.
[11:05] Uh and basically all of the interesting
[11:08] stuff interesting stuff happens inside
[11:11] this dwarf attributes list.
[11:15] So that's fully generic, all determined
[11:17] at runtime. Sorry, fully dynamic, all
[11:19] determined at runtime. And then on the
[11:22] opposite side of the spectrum, uh let's
[11:24] have a look at Clang's version of types.
[11:29] Um yeah, so these are all subasses of
[11:32] type. And what you're not seeing here is
[11:36] all of their subasses.
[11:38] Um and also all of the things that they
[11:41] multiply inherit from.
[11:45] Right.
[11:46] So
[11:49] given the our experience with dwarf
[11:51] debug information um
[11:55] as we moved into doing full executable
[11:58] debug in full executable debugging
[12:02] um we needed to handle PTBs and so we
[12:04] needed our own format that could handle
[12:07] both dwarf and pdb and we decided to go
[12:11] with kind of somewhere in the middle in
[12:13] that static dynamic uh split it.
[12:19] Um, so whereas
[12:22] you have this many types in clang, we
[12:24] have one. Uh, but then we also have one
[12:26] of these these other main types. Uh, I'm
[12:28] going to focus on types mostly uh later
[12:31] on.
[12:33] So this will be familiar if you were
[12:36] here yesterday.
[12:38] uh each type entry uh sorry each kind of
[12:42] conceptual type gets an entry uh in our
[12:45] type arena.
[12:47] Um so that can be strcts or base types.
[12:52] We got enums that have an underlying
[12:55] type of that base type. aliases, type
[12:58] defafs of those uh arrays, pointers,
[13:02] pointers to type defs, uh qualified
[13:06] types, pointers to qualified types,
[13:09] double pointers,
[13:11] qualified pointers.
[13:14] Yeah. Um
[13:18] yeah, as as I said, if you were here at
[13:20] Ryan's talk, uh you would have seen
[13:22] something very similar to this. Now,
[13:25] unfortunately, as some of you may be
[13:27] aware, um Ryan is no longer with us.
[13:34] >> Maybe it sound like something happened.
[13:37] >> But he would want us to go on in his
[13:39] absence.
[13:42] >> He's fine. He's just had to leave early.
[13:45] So, you you'll notice that all of these
[13:49] uh all of these pointers are going in
[13:51] one direction. They're all kind of
[13:52] pointing downwards in this graph and
[13:55] that is kind of towards this notion of
[13:58] an inner type and that'll come up in a
[14:01] sec.
[14:03] So this is a slightly a bridged version
[14:06] of our types. Um you can see there's
[14:09] kind of a general tag uh name size this
[14:12] inner type thing I mentioned and then
[14:14] some uh per type information. You'll
[14:17] note that the inner type is always
[14:19] available. Uh, and
[14:23] one of the things that
[14:25] having been through the whole make a
[14:27] debugger process before, uh, you realize
[14:29] is that
[14:32] you really want be able to get these
[14:34] inner types. Uh, it's a really useful
[14:36] thing to be able to do. Um, as I
[14:39] mentioned, we have these qualified types
[14:41] and enums and aliases. And sometimes,
[14:43] you know, if you're if you're presenting
[14:45] this to the user as a type, that's
[14:47] information that you want to know and
[14:48] you want to be able to show that. But
[14:52] quite often, you know, if you're reading
[14:55] data, you don't really care whether it's
[14:57] an S4 or an int. You just want to know
[14:59] how many bytes to read and how to
[15:00] interpret them. Uh, so we have this
[15:04] inner type for finding that, finding
[15:06] that out.
[15:08] You'll notice that we have this nil type
[15:11] at the bottom.
[15:13] And that is an entry into our type array
[15:18] that basically does nothing but is a
[15:20] place for things that don't actually
[15:22] have an inner type to legally point. And
[15:24] you can see that this points back to
[15:26] itself, which means if you aren't sure
[15:29] whether something has an inner type, you
[15:30] can safely just read it and you can do
[15:32] inner type of inner type of inner type
[15:34] of inner type and you can safely access
[15:37] this. um which just makes
[15:41] it makes the code that is using all of
[15:43] this type information so much easier to
[15:45] read without having to qualify
[15:48] everything in conditions about whether
[15:49] or not there isn't is an inner type.
[15:53] Now normally I'm I'm on the zero is
[15:56] initialization train. Um but this of
[15:59] course uh doesn't apply here because
[16:02] this is a pointer not an index. uh we
[16:04] need to actually initialize this.
[16:08] So I was thinking about this and I was
[16:11] wondering like why is this an
[16:13] appropriate time to be doing something
[16:16] other than zero zero is initialization?
[16:18] What am I what am I giving up here? And
[16:22] the the conclusion I came to was that
[16:27] our our type concept is kind of an outer
[16:30] level strct within our program. there's
[16:33] an array of these effectively
[16:36] um and nothing else things will point to
[16:40] types but nothing else actually contains
[16:42] them.
[16:44] Nothing else actually contains them.
[16:47] Now this means that when you're
[16:48] initializing if you're initializing a
[16:51] strct uh if it's a if it's a type you're
[16:55] basically doing it because you care
[16:57] about the type. You're only doing it for
[16:59] the for the sake of initializing a type.
[17:01] And so it's really not very much extra
[17:03] extra cost to do this nil type thing. Uh
[17:07] it's also
[17:09] uh it's also the case that because we
[17:11] have this as an array uh the array
[17:13] itself is zero initialized. Uh so you
[17:16] have you know n elements equals zero.
[17:21] Um but then as we saw
[17:26] the the types of strcts that are
[17:28] contained like strings kinds uh those
[17:30] are all zero initializable. So yeah I
[17:34] think this kind of containment idea is
[17:35] at least a partial heristic for that zi
[17:38] or nil type uh dichotomy.
[17:43] Okay. So
[17:46] we've got this typekind tag at the top.
[17:51] Um the normal way of doing this default
[17:54] I think is you have an enum and it just
[17:56] increments from zero and you know
[18:00] doesn't really mean anything. It's just
[18:02] an arbitrary identifier so you can
[18:04] distinguish between different things. Um
[18:06] the kind of the most semantic use of
[18:09] this is as an index into lookup a lookup
[18:13] table. So you might have some metadata
[18:15] like strings or sizes or something else.
[18:18] Uh and you would read that with you know
[18:22] enum strings enum b and get b out.
[18:26] Uh if you're feeling slightly spicy, you
[18:29] can order these in a particular pattern
[18:31] so that you can do uh simplifi like
[18:35] pretty small evaluations to do more than
[18:37] one check more than one thing at once
[18:39] and group them into some uh some
[18:42] pattern.
[18:45] The other common use for enums is as
[18:48] flags. So you have each bit uh is either
[18:52] you you have each flag is typically one
[18:55] bit set uh at some position in the
[18:58] number and you can it's a bit more
[19:01] flexible because you can have
[19:02] non-ontiguous elements all grouped
[19:04] together in this kind of flag CDE and
[19:06] that's pretty much entirely what it's
[19:08] used for is allowing you to have all of
[19:10] these booleans uh and switch switch them
[19:13] all on and off independently.
[19:17] So our outer types um the pointers, the
[19:21] qualifiers, the strcts, enums, all of
[19:24] that,
[19:25] we don't really have a huge number of
[19:27] them. And you know, we're doing debug
[19:31] information. It's it's stayed pretty
[19:33] much the same for a long time. And I
[19:35] think we can assume here that it's going
[19:37] to remain the same for at least a while
[19:39] longer. I think we have about 19
[19:41] different types here. And you you may
[19:43] see where this is going. Um, one of the
[19:46] things we can do is we can just turn
[19:49] each of those into a flag.
[19:52] Now, we're ignoring base types for the
[19:54] moment.
[19:56] This may look a little wasteful.
[20:00] Uh, you know, we're using one to the 26.
[20:03] That's uh that's a very large number.
[20:06] Um, you don't really want to be indexing
[20:07] with that. But we buy some stuff with it
[20:11] and I think it's worth it. This this
[20:14] only really works because we know this
[20:15] max bound that we've we've got of
[20:18] there's only a fairly limited number of
[20:20] things that we we want to represent.
[20:24] And because we we're treating these
[20:27] things as flags, we can group them
[20:28] because it's it's actually quite common
[20:30] in debug code to be uh to segregate
[20:34] different code paths by various
[20:36] different groups of type information. So
[20:38] often you want to treat pointers and
[20:39] arrays quite similarly. sometimes
[20:41] arrays, pointers. Uh we can see we've
[20:44] got arl and nonar valvel refs. U strrus,
[20:47] unions, and classes are all types of
[20:49] records that you want to often but not
[20:51] always want to treat the same.
[20:55] Welcome to our separate bplot
[21:00] bits are high level.
[21:05] In this case, we are continuing on where
[21:08] we left off with
[21:11] and and or operators.
[21:14] Now, you are hopefully familiar with
[21:17] these. Uh we saw before
[21:20] uh you know, we had these these flags
[21:22] and we get to set them. Now the cool
[21:25] thing here is that we basically get to
[21:26] treat our um the kind of the thing we're
[21:29] querying against as a set and we get to
[21:33] um we get to query that with our kind.
[21:38] Now because of the way that uh these
[21:42] work where we only ever have kind of one
[21:45] additional qualifier or pointer per
[21:47] thing, we only ever have one bit set in
[21:51] this kind if in the outer types.
[21:56] Um so we get to do a multiple lookup
[21:58] with a single operation.
[22:01] The computer is fantastic at ends. It
[22:04] has no problem with them at all. And
[22:06] this um oring these things together I
[22:10] mean ores are cheap enough as it is but
[22:13] um this will just get evaluated at
[22:15] compile time and treated as a single
[22:16] value.
[22:19] Okay. And then we have this ability to
[22:22] uh to invert the bits and we can check
[22:25] whether or not check that our thing is
[22:27] not one of these things.
[22:29] Now
[22:31] this is simple right? But if you don't
[22:35] approach this through the lens of what
[22:38] can I achieve using flags, what can I
[22:40] how can I how can I make do this in a
[22:43] sympathetic way, it's very easy to end
[22:45] up with, you know, a completely abstract
[22:47] set type or uh you know just a loop over
[22:52] an array which is it's not the end of
[22:54] the world. But if we can do that in a
[22:56] way that is incredibly concrete,
[22:58] incredibly simple, and easy for the
[23:01] computer, that seems like a a complete
[23:04] no-brainer.
[23:12] All right, so
[23:18] we have this inner type. we have this
[23:20] primitive way of determining whether um
[23:27] whether a type is of a particular kind.
[23:30] What's quite common is that we actually
[23:33] we want to get through all the way as I
[23:34] mentioned before we don't care about
[23:37] many of these steps uh on the on the
[23:40] path. We just care about the innermost
[23:43] thing. And so a useful thing to be able
[23:46] to do is just we can loop over our um
[23:51] our anquery.
[23:53] And so you end up with a very simple
[23:55] way. Uh once you're familiar with this,
[23:57] this is about as simple a loop as it
[23:59] gets um and we
[24:03] can skip through enums and qualifiers
[24:05] and whatnot. Uh and get our type out.
[24:08] And then you can do the inverse and find
[24:10] the first instance of something. Again,
[24:12] very simple loop.
[24:14] Okay, so I was I was looking through my
[24:17] notes and I got to this point. I was
[24:19] like,
[24:20] "Okay, who who cares?
[24:23] How is this how is this helpful?" Um,
[24:26] and
[24:29] the important thing here is what's not
[24:32] here, right? So, I look back at the
[24:35] dwarf code and the equivalent of this is
[24:40] this.
[24:42] Now,
[24:44] that's not a totally impenetrable amount
[24:46] of code. You you could read through this
[24:48] and understand it. Um,
[24:52] but this is basically a primitive in all
[24:54] of your debug operations. And so when
[24:56] something goes wrong, you have to now
[24:59] question whether this is correct.
[25:03] Would you prefer to be using this as the
[25:05] primitive or this?
[25:10] Okay.
[25:12] Now
[25:15] we've done this by looping over the
[25:17] different pointers.
[25:19] An alternative we could have taken was
[25:21] would be to
[25:23] basically cache these uh these mappings
[25:26] early on and have this pass through
[25:30] alias pass through qualifiers pass
[25:32] through qualifiers except not atomic
[25:34] types because those needed for separate
[25:35] things. Um, but that gets
[25:39] it's unnecessarily expensive and we can
[25:41] do it fairly easily with this functional
[25:42] mapping.
[25:48] Okay, we've gone we've gone inwards as
[25:52] it were. Um, but sometimes we want to go
[25:54] outwards. We've started with a pointer.
[25:57] We've got our int. Uh, but in many cases
[26:00] we want to do the opposite. What is the
[26:02] pointer type for this value? Do we have
[26:04] one? If not, we can create one. But
[26:06] let's at least try and get the canonical
[26:08] version first.
[26:11] So
[26:15] we could have done the same as here
[26:18] effectively and tried to added the
[26:21] pointer to the equivalent pointer type,
[26:24] the equivalent reference type, the
[26:25] equivalent um volatile, all of those
[26:28] things. Again, it's it's pretty sparse.
[26:31] Like most of these things don't actually
[26:33] have outer types.
[26:35] Now I was thinking of this in those
[26:38] terms. Think of this as a reference to
[26:40] the outer type and
[26:45] at some point
[26:47] kind of a an audible click happened in
[26:49] my head as well first of all I slapped
[26:53] my forehead that might have been part of
[26:54] it. Um,
[26:56] but if you reframe from
[26:59] references to mappings,
[27:02] it's very it's obvious like what is the
[27:05] canonical map? A map, a hashmap.
[27:09] You can just map from type to type. And
[27:13] because we have stable pointers, um, you
[27:16] can easily treat those as keys and
[27:18] values.
[27:20] Again, we have another choice to make
[27:22] here. Um, do we want to
[27:26] have a very simple map but one of them
[27:29] per kind of um per kind of mapping that
[27:33] we want? Uh, or do we want to include
[27:36] that outer type kind uh the kind of
[27:39] thing that we're looking for with a
[27:41] qualifier or a pointer in the key to our
[27:43] map itself.
[27:45] And
[27:47] this kind of trade-off often comes up
[27:49] where you want you you can choose
[27:51] between many simple things or one
[27:54] slightly more complicated thing. And in
[27:56] this case, I chose the slightly more
[27:58] complicated thing as it's only a little
[28:00] only a little bit more complexity.
[28:05] More choices appear. Um how do we want
[28:09] to hash this thing? So uh you will note
[28:12] the explicit padding in here because
[28:14] otherwise you might not get those as a
[28:16] value that you expect. The compiler
[28:19] might do anything with them. Um but this
[28:21] way with the uh with all of the bytes
[28:24] filled we could just hash variably.
[28:26] That's the kind of most most generalized
[28:28] version. But we know the type of thing
[28:31] that we're doing. We know it's fixed
[28:32] size. Let's make assumptions about that
[28:35] and benefit from it. we can do a two
[28:38] element hash and turn that into
[28:42] um the thing that we use as the key in
[28:44] our app.
[28:47] But we know more about the platform that
[28:50] we're operating on.
[28:53] So
[28:55] on 64-bit systems, specifically x8664,
[29:01] what do we know about pointers?
[29:06] They're not actually 64-bit.
[29:09] Uh at typically they are 48 bit
[29:13] occasionally 52 and uh I think Arch 64
[29:18] um ARM 64 has some 56 bit uh address
[29:23] bases.
[29:25] This basically means we have 8 bits
[29:27] guaranteed at the top of our uh pointer
[29:30] given that we know our platform. And
[29:32] I'll point out that uh as a debugger,
[29:34] you have to know your platform. Uh and
[29:36] so portability is already uh it's not
[29:39] it's not a cause that we can go for. Uh
[29:41] so let's let's take advantage of this
[29:43] and use those top eight bits.
[29:47] Ah
[29:49] uh it seems like we may have hosed
[29:52] ourselves here because we've got massive
[29:54] values, right? We can't just put those
[29:56] into eight bits. Um,
[30:00] but let me introduce you to your new
[30:02] best friend. Okay, we've got left
[30:05] shifting. These are one left shifted by
[30:08] 20, one left by 8, all of that kind of
[30:10] thing. And that takes us from 8 to 256.
[30:14] There's an operation that goes in the
[30:15] other way and that is most significant
[30:18] bit.
[30:21] You will find this incredibly useful.
[30:25] You can you have to do this slightly
[30:27] differently on clang and MSVC. Clang has
[30:29] the benefit that it will happen. It will
[30:31] do it at compile time. Uh you have to do
[30:34] some nasty hacky tricks on MSVC to make
[30:37] that happen.
[30:40] Okay,
[30:42] let's see if we can
[30:46] learn by testing. Anyone in the
[30:48] audience, what is the most significant
[30:50] bit here?
[30:53] >> One. Yes.
[30:54] here.
[30:56] >> Yes. Here.
[30:59] >> Yes. Okay. So, we're we're counting from
[31:01] the right from the least significant bit
[31:02] and the furthest thing is the most
[31:04] significant bit. Great. Uh most sign
[31:07] most significant bit here.
[31:10] >> None.
[31:11] >> No. Yeah. It's failure
[31:13] >> undefined. Yes.
[31:17] So, this is just something to be aware
[31:19] of. Okay. Well, we can look back at our
[31:22] flags and um the way we've described it,
[31:26] each of these is going to be the most
[31:27] significant bit. Is it 8 9 10 11 12?
[31:31] Great. And that's part of the reason
[31:32] that I write it that way rather than the
[31:35] zero xf whatever.
[31:38] Cool. So, uh we have 26 is our max value
[31:43] now. Uh and any any guesses for number
[31:47] of bits that you can represent 26 in?
[31:51] >> Five.
[31:53] >> Correct.
[31:55] Um we're doing one to the 32
[31:57] effectively.
[32:00] Uh and so we can
[32:04] we can get our pointer, we can get our
[32:07] uh kind and we can put these together.
[32:09] And I think I have written those. Oh no,
[32:13] there's the correct way around. Great.
[32:15] Cool. So
[32:17] we are in this case shifting the pointer
[32:21] up and putting the kind at the bottom.
[32:25] And this is the machine code that uh
[32:28] corresponds to that.
[32:30] Um this BSR is basically the most
[32:33] significant bit that we saw earlier. uh
[32:37] the compiler gets to make an extra
[32:39] optimization here because uh it knows
[32:42] that the value is never above um it
[32:45] never uses more than five bits. So it
[32:46] doesn't even have to end here.
[32:49] Okay, we we did it that way around. Um
[32:52] we had a choice though. We we could have
[32:54] done it the other way around. Uh what
[32:56] happens there? Yeah, it's, you know,
[33:00] it's fine, but
[33:04] unless you have a reason to choose
[33:05] otherwise, you may as well go with the
[33:07] uh the nice smaller one. U less
[33:11] instruction pressure, I catch pressure.
[33:14] Um, and it also uses fewer registers.
[33:18] Um, the other nice benefit of using the
[33:21] small value at the bottom with a pointer
[33:22] at the top, uh, is that if you're really
[33:24] pressed for bits, you may be able to
[33:26] take some from the alignment bits of the
[33:29] type of the pointer. Um, but yeah. Okay.
[33:33] Is is this useful? Is this um like how
[33:38] much of an impact is this really going
[33:39] to have? And to be honest, probably not
[33:42] that much.
[33:44] um choosing one over the other. But once
[33:48] you know this, there is just zero effort
[33:51] to choose the the one that's better.
[33:55] So you have no excuse now. Okay,
[34:00] welcome back to bits a high level.
[34:03] We've been our main thread has been
[34:05] preempted
[34:06] and we're going to talk about
[34:10] bits.
[34:12] Okay, so
[34:14] you get some some bitwise number and the
[34:18] normal interpretation of this is to just
[34:20] treat it treat them all as one value. So
[34:22] this is 233.
[34:25] But there's no reason that you can't
[34:27] split out different fields from this
[34:29] value and treat those as their own
[34:32] separate values. So here because they're
[34:35] four bit they each fit into a nibble or
[34:37] a 16 bit um digit
[34:43] um yeah 14 and nine in this case.
[34:47] Okay. So what can we do with that if we
[34:50] if we split these numbers into multiple
[34:52] parts?
[34:53] All right. Let's start off simple. So we
[34:55] we take our take a couple of bits at the
[34:57] bottom and we can have four values with
[35:00] those. uh we might then add an uh a
[35:07] three length axis on top of that using
[35:10] another two bits. So we have 4x3 and
[35:13] then we we have this kind of rectangular
[35:15] array of uh of different values.
[35:19] Uh you can you can think of that as an x
[35:21] and a y axis.
[35:24] uh and then we can add a uh two length
[35:28] or yeah one bit dimension on on our Z
[35:31] axis and now we have effectively a
[35:33] little 3D mapping within a single number
[35:39] and that's where the uh the value at the
[35:42] top exists.
[35:44] So
[35:45] yeah our our friends in the array
[35:48] programming language world would call
[35:49] this kind of a rectangular mapping. It's
[35:51] basically what they their entire data
[35:53] structure everything is in this format.
[35:56] Uh our our friends in the functional
[35:58] world would call this a product type. Uh
[36:00] and you can you can kind of see why here
[36:02] because you're tsing four by 3x two as
[36:05] the number of different possibilities
[36:06] that you have. Um and another another
[36:09] way of thinking about this is
[36:10] effectively each of these different
[36:12] color dimensions is a strct member.
[36:18] So,
[36:22] I like this rectangular view. Um, but
[36:26] there's there's a more general one,
[36:27] which is this tree. And each time you
[36:30] hit a bit or each time you hit a new
[36:32] dimension, you can split off into
[36:35] however many different options that
[36:36] dimension has.
[36:39] Um, this is occasionally useful for
[36:42] coming up with the shape of things, but
[36:44] probably not great to think about once
[36:46] it's in there. And you'll see why in a
[36:47] sec.
[36:50] Uh, yeah, same same position, but now in
[36:53] this different interpretation.
[36:56] And I I'll say here, and I'll probably
[36:57] say it again, that one of the great
[36:58] things about
[37:01] uh bitwise numbers is that you can
[37:03] interpret them in multiple different
[37:05] ways at different times. and being able
[37:07] to switch between them uh for for the
[37:10] same bit pattern, being able to switch
[37:13] between different interpretations of
[37:14] that um from one moment to the next can
[37:17] actually give you quite a lot of power.
[37:21] So this tree version is even more
[37:23] general. Uh you don't actually have to
[37:25] have even dimensions the whole way. You
[37:27] can uh once you've decided on your first
[37:30] split, you could completely reinterpret
[37:31] the bits differently. So here we have um
[37:35] on the left two by 3x4 and on the right
[37:39] is 2x two by two by two by two. I think
[37:43] I said too many twos.
[37:46] Um again
[37:49] this can encode potentially more
[37:52] different things. You'll see in a sec.
[37:55] But if you can avoid it I would
[38:01] Yeah.
[38:03] Right. Then let's bring it back to
[38:05] types. So we'll start with this tree uh
[38:09] tree view on this this type question. Um
[38:12] there's different ways we could break up
[38:13] our space of types of base types
[38:16] specifically. Um you know we're dealing
[38:18] with floats, dealing with unsigned and
[38:20] signed integers, booleans, chars, that
[38:22] kind of thing. Uh, and each of each type
[38:28] has kind of a a general type kind like
[38:31] signed or unsignedable whatever. Um, and
[38:34] also a size.
[38:37] Now
[38:39] um you know this this float and scaler
[38:42] thing I happen to know is useful in some
[38:44] circumstances when you're um you're
[38:47] interpreting the base type and you maybe
[38:50] you want to encode that in there so you
[38:52] get this information for free um but you
[38:54] end up with this kind of slightly
[38:55] lopsided tree where um
[39:00] doesn't all really it doesn't fit into
[39:02] this
[39:03] this neat multiple dimensions thing that
[39:05] we mentioned earlier.
[39:07] Another thing I'll point out here is
[39:09] that we have these
[39:11] we have we have an outlier case um that
[39:14] is F10 an 80 bit x87 fpu float um and
[39:21] whenever you whenever you try and map a
[39:24] space whenever you try and generalize a
[39:26] model well you often you will often come
[39:29] across situations where ah there's an
[39:31] exception
[39:34] and again at that point you have a
[39:35] choice
[39:36] Do you want to generalize your model so
[39:40] that you can account for this or do you
[39:43] want to um keep the model nice and
[39:46] simple and then
[39:48] keep an keep the exception for the
[39:51] unusual case and you can keep that in
[39:54] the um the interpretation of the data
[39:56] kind of with the the tree style thing we
[39:58] saw before. um you can treat that you
[40:02] can use that do that in the code with
[40:04] whenever you're dealing with stuff you
[40:05] just have an extra if it's uh if it's an
[40:07] 80- bit float um
[40:11] yeah you have that choice now I guess I
[40:13] probably should have mentioned before
[40:15] the convention we have in the codebase
[40:16] is that unless bits are specifically
[40:21] otherwise required uh types normally
[40:23] specified in terms of their bite size
[40:24] not their bit size um
[40:28] yeah and again We've we've got this nil
[40:30] type
[40:32] uh and there's only really one nil type
[40:36] and each of these kind of bottom layers
[40:39] on the tree has four values and that
[40:43] means we're we're oversp specifying nil.
[40:46] Well, you can you can ether interpret as
[40:47] there's a a one bite nil, a two byt nil,
[40:49] a four by nil, and an 8 by nil. Or you
[40:51] can interpret that as there's a one bite
[40:54] nil and then there are three holes in
[40:56] our space.
[40:58] Um
[41:01] now
[41:04] for a certain interpretation that's a
[41:06] problem. Um but if you are willing to
[41:09] ignore it then you get a lot of utility
[41:11] from that.
[41:14] This is another breakdown of that of
[41:17] that tree. Um I know I'm missing
[41:19] unsigned char and v various other things
[41:21] here. Um but let's go with this as a
[41:24] simple version for the sake of the talk.
[41:27] um we're we're just kind of accepting
[41:28] that we have holes where all of our nils
[41:30] are. Uh and in practical use, we don't
[41:34] really have um 8 bit or 16 bit floats
[41:37] that we have to deal with. Uh although
[41:40] just by having this type system, we now
[41:43] handle that um even if unintentionally.
[41:50] Okay, so I mentioned you want to it's
[41:53] useful to be able to think of this as a
[41:55] uh as a as a clean separation of
[41:58] dimensions uh and rather than as the
[42:02] tree. If if you're thinking it as the
[42:03] tree, what typically happens is you have
[42:06] to do each decision point in the tree as
[42:09] a separate conditional. Um, so not only
[42:12] are you nesting bunch more, you're kind
[42:14] of adding this this layer of indirection
[42:16] in your code, you
[42:19] just end up with n * m different um for
[42:24] however many dimensions you have
[42:27] uh different cases you have to handle.
[42:29] And quite often if you have neat
[42:31] dimensions, you can take the value on
[42:33] one dimension, handle that, take the
[42:34] value on the other dimension and handle
[42:36] that as separate cases and end up with n
[42:38] plus m cases instead.
[42:42] Okay,
[42:44] right back to how this works in the
[42:47] codebase. So, we have our types arena uh
[42:50] as a as a top level debug information or
[42:54] debug information type. Uh it ends up
[42:57] being useful basically having an entire
[42:58] array just for types. Um
[43:03] so we have our base types at the bottom.
[43:06] Uh we've got I should have mentioned we
[43:09] have basically end up with four bits for
[43:12] the um the kind and then four bits for
[43:14] the size. Um
[43:19] so we yeah we have 256
[43:22] uh different locations here. We then
[43:24] have some other built-in types um which
[43:27] we know we're going to need but don't
[43:28] really fit neatly into this. So that
[43:29] includes things like the XMM type uh and
[43:33] you know the Windows thread exe
[43:35] execution block type that kind of thing.
[43:38] Uh and then we just have everything
[43:40] after that. It's pretty much completely
[43:41] arbitrary. Um we have
[43:46] our pointers, our qualifiers, all of
[43:48] that in there.
[43:52] Okay. So we have our different
[43:56] components of our our values. We have
[43:58] our kind and we have our size. Um
[44:02] the fact that we have these as separate
[44:04] components mean not only can we given a
[44:06] type determine both of these we can then
[44:08] re recombine them uh after having done
[44:11] some calculation uh and then find the
[44:14] new computed type. We don't have to
[44:16] indirect this through multiple lookup
[44:19] tables. It's just oring two small
[44:21] numbers together. Uh and this this case
[44:24] is for integer promotion. This is a
[44:26] small snippet as part of that uh where
[44:28] you have to take both kind and size into
[44:29] account.
[44:33] Okay, let's
[44:35] we have both this base type and the
[44:38] other outer types the the qualifiers the
[44:41] pointers and so on. Those are both
[44:42] within our type kind. And this is where
[44:45] I think it gets really cool. Um we do
[44:49] our pass through. We we get the kind of
[44:51] base type as part of that. Sorry, the
[44:53] the the innermost type that we care
[44:56] about as part of that. And then we can
[45:00] switch on this and filter our switch to
[45:02] the level of detail that we care about.
[45:05] So we can mask off we we can basically
[45:08] treat all base numbers and enums the
[45:12] same thing and then they only have have
[45:14] to deal with a single case in our switch
[45:15] statement rather than dealing with what
[45:18] would that be? you know 256 I guess from
[45:21] the previous thing different options
[45:22] from in our lookup table. Um
[45:27] we can then deal with the different out
[45:30] types as as separate things. Another
[45:33] case um in this one we are looking at
[45:39] return values on windows. So that has a
[45:41] particular um particular API particular
[45:44] calling convention. Uh, and in this
[45:47] case, we don't care about the size of
[45:49] the type, but we do care what kind it is
[45:51] because floats get treated differently
[45:53] from basically everything else. Uh, and
[45:56] you can see again there's there's, you
[45:58] know, it's not no entries here, not no
[46:00] cases, but we don't have to deal with
[46:02] the entire type spectrum if it as if it
[46:05] were just a uh a flat undifferiated
[46:09] arbit arbitrary number.
[46:13] And the last case
[46:15] um we can look at just the inner type
[46:17] and then um basically ignore all um
[46:23] ignore all of the outer types, ignore
[46:24] all the qualifiers. And there's another
[46:26] case I didn't add here which is uh where
[46:28] you want to read data. It's useful to
[46:30] know uh what it is so that you can if
[46:32] it's a signed variable and it's smaller
[46:34] than eight bytes um you want to read it
[46:37] and make sure you sign extend it. Uh,
[46:39] and so that's a case where the full base
[46:41] type rather than just one of these
[46:43] components is helpful.
[46:46] Okay,
[46:48] end of part one.
[46:51] Welcome to part two, stacks and
[46:53] stackability, where we're going to talk
[46:55] about white box, the the workings of
[46:57] white box that help it work more like a
[46:59] profiler.
[47:01] Uh so
[47:04] again, white box collects things over
[47:07] time and it can collect things in
[47:09] multiple threads at once.
[47:12] Uh this breaks down for um
[47:18] both both gooey purposes and the
[47:21] internal structure happen to mirror
[47:24] quite nicely here. Uh so hopefully this
[47:26] this will make sense. we have our kind
[47:28] of general run recording and inside that
[47:33] we have um run threads and inside of
[47:36] that we have multiple levels on a call
[47:38] stack. Inside that we have all of our
[47:42] many calls that have happened within
[47:44] that call stack. Uh and then in inside
[47:46] that we have an individual call to a
[47:49] particular function.
[47:52] Now couple of things to note here.
[47:58] Firstly, um, all of these things are
[48:03] on,
[48:05] you know, we have many levels of nesting
[48:07] here and and while I said we have a few
[48:09] arenas, we don't want an unbounded
[48:11] number of arenas.
[48:13] Um if we had an arena per thread, you
[48:16] know, most people many people in here
[48:18] will be sane with their use of threads.
[48:20] But uh in in the general case, there's
[48:23] really not much of a uh not much of a
[48:26] bound there. And that goes for each each
[48:29] entry in this dimension.
[48:32] So we we don't want to just have an
[48:34] arena per array. We want some other some
[48:36] other notion some other method of
[48:38] storing this information.
[48:42] The other thing I'll note here is I
[48:45] still want my stable pointers. They're
[48:46] really useful. Okay, I'm going to keep
[48:49] them. Nothing will stop me.
[48:54] Right. So, an alternative view on this
[48:57] is this. This is with the kind of tree
[48:59] that we're forming. There are other
[49:01] things at each of these levels, but
[49:02] they're not important.
[49:05] Um, I want my stable pointers to calls.
[49:08] Okay. or each individual call instance.
[49:12] What are the options we've got? Okay,
[49:14] I'll start basic. You know, we just
[49:17] pre-allocate some array and it's big
[49:20] enough and we just use as much as we
[49:22] need and we know that we're not going to
[49:24] need more. Um, works in some cases. It's
[49:28] not going to work here. There's too many
[49:30] each of the things is both too big and
[49:32] too volatile in uh too dynamic in how
[49:35] large they end up being. Um and that is
[49:38] true at each level of the stack whether
[49:39] or not it was kind of directly there or
[49:41] indirected via pointer.
[49:44] Probably the default solution here would
[49:46] be a kind of realoclock array where you
[49:48] start with something fairly small and
[49:50] then you double it uh and you move the
[49:53] pointer to the new thing and then you
[49:55] keep a reference to each of these things
[49:56] by index. You may see where I'm going
[49:58] here. It's not stable.
[50:01] Uh and this isn't an entirely small
[50:05] point. So if you if you want to actually
[50:08] reference one of these things and you're
[50:10] using indices at each of these levels,
[50:12] what are you going to end up with? Four
[50:14] indices and a base pointer to start
[50:15] with.
[50:17] It's both it's both starting to get to a
[50:20] reasonable amount of memory if you're
[50:21] holding a lot of these and also it's
[50:23] really inconvenient to write the code
[50:25] around.
[50:27] Okay, another option uh we could we
[50:31] could indirect
[50:33] we could have we could have a a meta
[50:35] block that points into individual chunks
[50:38] and then the individual chunks can
[50:40] remain stable and then we kind of
[50:42] reallocate this meta block structure.
[50:46] Um
[50:48] I think this would work. Uh there's no
[50:50] kind of
[50:52] inherent problem with this. you end up
[50:54] still doing the leaking although now the
[50:57] some fixed size some some constant size
[50:59] smaller than the the full problem. Um
[51:03] and then you you either leak this or you
[51:07] have some pool structure that ends up
[51:10] dealing all this and if you do that then
[51:12] you end up having to free things because
[51:13] they're not in the right place in the uh
[51:16] in the arena stack. I can go on about
[51:19] that but
[51:21] I don't know it's not great. There's
[51:23] also two jumps. So if we could avoid
[51:25] that, that would be nice.
[51:27] Um, common solution for
[51:32] variable length data where you want
[51:33] things to be static where you can grow
[51:35] them is this kind of chunked link list
[51:38] approach. Um, so you have an four items
[51:43] on this particular case have four items
[51:45] in each list list node have a pointer to
[51:48] the start and to the end. And this is
[51:51] great. We use this uh for strings things
[51:53] where you string lists where basically
[51:57] all of the the only thing you need to do
[51:59] with them is iterate through them from
[52:02] beginning to end.
[52:04] Um but in our particular case a
[52:07] constraint that I haven't mentioned yet
[52:09] is that we want random access and
[52:13] that is slow here. Uh now you may be
[52:16] thinking that we can just walk through
[52:21] and find it and it'll be fine. Computers
[52:23] are fast, memory is fast, whatever.
[52:25] Caching has improved so much. All of
[52:27] that fun stuff. Um maybe that would be
[52:30] okay with moderately sized data um that
[52:34] you do relatively infrequently.
[52:37] But uh I don't know if you've ever seen
[52:39] a profiler. Uh if you've ever seen a
[52:42] profiler trace, they end up being many
[52:43] gigabytes. And this is we do this all
[52:46] the time, so it's completely prohibitive
[52:48] for us.
[52:50] Another option could break things down
[52:52] in some sort of tree structure. Um, but
[52:55] we said we're trying to remove
[52:56] interaction here as well. So if we can
[52:58] avoid that, that would be really nice.
[53:00] There's also just like so many things
[53:02] happening all over the place for a
[53:05] structure that is that maybe end up
[53:06] being used quite a lot. We'd like to
[53:09] avoid that if possible.
[53:11] So So this is where I've ended up. um we
[53:15] take the the doubling size that we saw
[53:18] in the the real case and we took the um
[53:22] the metab block or chunk pointers
[53:24] approach of the the case after that um
[53:28] and rather than
[53:32] um rather than doubling in place this in
[53:36] this particular case we double the size
[53:37] of the array uh each each time we add a
[53:40] new chunk.
[53:42] Now, there's a nuance here. I said
[53:44] double the size of the array and not
[53:46] double the size of the previous chunk.
[53:49] Um I I think both can probably work. Uh
[53:53] but the maths well for one thing, you
[53:57] end up with a power of two size if you
[53:58] do it this way for the total total
[54:00] array. And that that's quite nice for
[54:02] various things. Uh and I think the maths
[54:04] work out maths works out nicely when you
[54:06] do it this way. Um so you'll see that
[54:08] the first two blocks are the same size.
[54:11] uh and then we double and then we double
[54:12] again.
[54:14] And you may also notice that the the
[54:17] pointers are just immediately next to
[54:19] the the the size of the array, the
[54:21] number of elements in the array. Uh and
[54:23] that is intentional um because
[54:29] we're on a 64-bit system. There's only
[54:32] 64 times that you can double the number,
[54:35] including the first one, and still be
[54:37] representable in address space, you
[54:39] know. So worst case, you end up with 64
[54:41] pointers here.
[54:44] Okay, but what have we already said? Uh
[54:47] that we're not actually in a 64-bit
[54:50] address space. We could this that you
[54:52] can you can chunk that down to 48 or 52
[54:55] or something around there.
[54:57] Okay. And then uh in in reality, you're
[55:01] on an actual physical system and you are
[55:04] very unlikely to have that many actual
[55:07] elements in RAM.
[55:09] Uh next step down. You have a real
[55:14] problem that you're trying to solve. And
[55:16] while in our first example
[55:19] uh we pooed the idea of having some
[55:22] known size of things that we can um that
[55:26] we can definitely fit all of our
[55:27] elements into. when you don't have to
[55:30] pay the actual full cost of that uh in
[55:33] term you only have to pay the log two of
[55:35] the cost of that uh that actually
[55:37] becomes a lot more feasible
[55:41] and then of course
[55:43] each individual element has a size. It's
[55:46] not just one bite typically. Um and then
[55:50] beyond that you shrink the number of
[55:53] pointers you need further by the fact
[55:55] that uh your initial chunk is not just
[55:58] one element but many
[56:01] um possibly you decided by cache size or
[56:04] page size or some other reasonable
[56:07] default for your problem. There's
[56:08] there's a little bit of nuance in how
[56:10] you decide that. Um,
[56:12] but but you end up with this. It's not a
[56:17] completely tiny header structure, but
[56:19] it's it's completely tractable.
[56:27] Right. So,
[56:30] this I I looked around for this. Um I
[56:34] couldn't see anyone talking about it
[56:36] although I'm sure that other people have
[56:37] done it. Uh given that I couldn't find a
[56:40] name I've come up with the name
[56:42] exponential array um or XAR for short.
[56:50] So we have this kind of array idea idea
[56:54] for storing a a virtual array and um but
[57:00] we we have to actually you know we have
[57:02] we need the code for this we need to
[57:04] implement it. It's no longer just a
[57:06] single lookup. There needs to be some
[57:08] kind of operations to find each element.
[57:10] And I guess this is this is where um I'm
[57:14] going to say that abstraction and
[57:17] generalization are not always a bad
[57:18] thing. They have a cost, but sometimes
[57:20] that cost is worthwhile.
[57:22] Uh and
[57:25] the way that we're going to generalize
[57:26] this is by treating bytes as first class
[57:29] citizens.
[57:31] Okay. So parameters that we're we're
[57:33] looking at are the size of each element.
[57:37] Uh the number of elements in the first
[57:38] chunk and from that you can infer the
[57:41] rest of them
[57:43] and the number of pointers that you're
[57:44] going to store to these chunks. And
[57:46] given that you can basically describe
[57:48] this entire structure.
[57:52] Okay, we're going to take advantage here
[57:54] of another thing that we know about the
[57:57] platforms that we're on. Um on
[58:02] um on in the typical Windows and Linux
[58:05] calling convention if you pass a 1 2 4
[58:08] or 8 byt uh strct and it's there are
[58:11] more options for that on Linux uh if you
[58:14] pass a strct that is ex exactly eight
[58:17] bytes it will get passed as a register
[58:19] and so given that we know this it's
[58:22] actually not that difficult to compress
[58:25] all the information that we need to know
[58:27] into eight bytes
[58:29] um So maybe it sounds like a micro
[58:32] optimization. Um but again it's actually
[58:36] very the the mental overhead on doing
[58:38] this is pretty small once you're aware
[58:40] of it.
[58:44] The other point to do with calling
[58:46] conventions or APIs is
[58:49] you know we we want one version of an
[58:53] array function is to get to the element
[58:55] at index i. Uh and that's that's all
[58:58] well and good. Um, but there are other
[59:00] things you want to do with them. And as
[59:01] soon as you have multiple
[59:03] um multiple different parameters that
[59:06] you're passing, then being able to chunk
[59:08] all of that meta information into one uh
[59:11] one element is convenient both from a
[59:13] calling convention and from a developer
[59:16] perspective. Do you see that
[59:18] intersection happening? Yeah. Um
[59:22] so we
[59:24] um have this incredibly complicated
[59:28] header strct which just contains the
[59:31] size because we've we've said that our
[59:34] the number of chunks number of pointers
[59:36] that we store um may want to differ in
[59:38] different cases. Uh and then um given
[59:41] this
[59:43] we can uh we know that our chunk is
[59:47] going to be immediately following this
[59:48] and we know that they're going to align
[59:49] because of the size of this thing. Um
[59:52] given this we can find the which chunk
[59:56] uh an element is in and then where
[59:58] inside that chunk it is.
[1:00:01] Um I'm very happy to talk people through
[1:00:04] what this is all doing. um we don't
[1:00:07] really it's I don't think we have time
[1:00:08] to do it currently but you can observe
[1:00:11] that all of the operations are just
[1:00:14] shifts and addition and subtraction it's
[1:00:18] all stuff that the computer can do very
[1:00:21] very handily uh and
[1:00:25] I think this is mostly possible because
[1:00:26] of the the
[1:00:29] um the structure that we ended up with
[1:00:30] here with everything being a power of
[1:00:32] two now you could have gone maybe I want
[1:00:35] Fibonacci structure.
[1:00:38] Um and maybe you could have but if you
[1:00:42] do that then
[1:00:45] um finding the doing this inverse of the
[1:00:49] you know maybe going from
[1:00:52] um doing doing the multiplication out
[1:00:53] isn't too bad but then going in the
[1:00:55] opposite opposite direction becomes a
[1:00:56] lot more prohibitive. Whereas we have
[1:00:58] our best friend most significant bit and
[1:01:01] that does it.
[1:01:10] that does our log base 2
[1:01:13] uh in um with about the latency of an
[1:01:16] integer multiplication and depending on
[1:01:18] the platform it's sometimes more like an
[1:01:20] addition. So it's between very good and
[1:01:22] the best it can possibly be.
[1:01:26] Okay, let's let's look at getting a real
[1:01:29] type that we can find. And we've
[1:01:32] introduced this with um wanting to find
[1:01:34] a um a particular call in this tree of
[1:01:38] calls. But we'll just look at the the
[1:01:40] last array in that.
[1:01:43] Okay. So I'll point out that this is not
[1:01:46] actually how I do it in my codebase
[1:01:48] because uh we have some some macro
[1:01:51] hackery to get around having to
[1:01:53] implement this everywhere or to rewrite
[1:01:55] this everywhere. Uh I don't didn't want
[1:01:57] this talk to be too Csp specific and so
[1:02:00] I'm not going to go into that but feel
[1:02:01] free to ask me about it later.
[1:02:03] Um so anyway we can specify the metadata
[1:02:07] and then call so we have our outer
[1:02:10] function is it's fully typed uh and then
[1:02:13] our inner function um it calls the
[1:02:16] generic byte-wise oper operator and
[1:02:19] returns a pointer to the thing it found.
[1:02:22] Uh if this were an external function um
[1:02:26] like I said the
[1:02:28] uh an eight byt strct will just get
[1:02:30] pushed into a register or moved into a
[1:02:32] register and then passed as one of the
[1:02:34] parameters like that. Uh and you can
[1:02:36] actually see um here we have a shift of
[1:02:40] eight. Um we have 30 chunks and we have
[1:02:45] a you can't see here but it's a 24 byt
[1:02:47] element. Uh and so at the very right we
[1:02:51] have eight uh and then 30 and then at
[1:02:54] the very end this 0x18 that's 24 in hex.
[1:02:59] Um, okay. This is this is an external
[1:03:01] call and in reality um particularly if
[1:03:05] you're a Unity G Unity build team then
[1:03:09] um you're actually going to call you're
[1:03:13] going to get your code
[1:03:15] your compiler and your linker are going
[1:03:17] to know uh what the function is going to
[1:03:19] call and it's going to inline them and
[1:03:21] it's going to be hack times where you
[1:03:23] don't have to do this extra call
[1:03:24] overhead
[1:03:25] before we get there. I mean we just have
[1:03:29] an awareness. We're not going to go
[1:03:30] through this in detail of the the
[1:03:33] machine code that gets generated.
[1:03:36] And um
[1:03:39] hopefully you're all familiar with
[1:03:40] Godbolt at this point. You whenever you
[1:03:42] have a a query about what things get
[1:03:44] turned into, Godbolt is a a lovely go-to
[1:03:47] for quickly checking what things are
[1:03:48] going to look like. Um but this is a a
[1:03:51] general case. There's nothing
[1:03:53] particularly objectionable in there.
[1:03:54] There's like there's a jump. Maybe we
[1:03:56] could have made this branchless. Um
[1:03:58] there's an IMOLE which is not quite as
[1:04:00] fast as some of the other bitwise
[1:04:02] arithmetic but I mean like this is
[1:04:05] pretty much this is this is really very
[1:04:08] good for uh generic code u for kind of
[1:04:12] generic operations dynamic dynamically
[1:04:14] typed operation. Um and then at the end
[1:04:18] we
[1:04:20] um
[1:04:22] we we find out what the pointer ends up
[1:04:24] being to our thing. And so the
[1:04:28] the gold standard here, which would be
[1:04:30] finding the address of an element in an
[1:04:32] array, uh would basically just be a
[1:04:35] single LEA maybe with a a couple of mobs
[1:04:37] before it. Um and while we're not quite
[1:04:40] there, like if you've seen the size of
[1:04:42] some of the disassembly and in many
[1:04:44] other functions, we're not too far off.
[1:04:48] Okay, so if we specialize to a the
[1:04:50] specific types that we're interested in,
[1:04:52] it's actually all very similar. um
[1:04:55] except the there's some early outs at
[1:04:57] the top and um a little trick to compute
[1:05:01] uh 24 times for the size slightly faster
[1:05:04] than a generic multiply.
[1:05:06] Um okay, so so two things jump out at me
[1:05:09] here. One is um this got inlined the
[1:05:13] inner type didn't end up being the fact
[1:05:15] that we did this dynamically initially
[1:05:16] didn't really matter for the resulting
[1:05:18] machine code. Um, and the other thing
[1:05:21] that jumps out is that the dynamic
[1:05:24] version is actually not that bad. Uh,
[1:05:26] and so given that we're a debugger and
[1:05:30] we do many things dynamically, um, it's
[1:05:34] actually occasionally useful to use the
[1:05:36] dynamic version. And the fact that we've
[1:05:37] done it this way rather than through
[1:05:39] templates or something means that we
[1:05:41] have this option to basically have this
[1:05:44] monomorphization on the right or the uh
[1:05:48] or a runtime version on dynamically
[1:05:51] typed version on the left.
[1:05:54] Uh and thinking of this is basically
[1:05:57] bite first thinking wins over type first
[1:05:59] thinking.
[1:06:03] Okay. So why do we need this random
[1:06:08] access? Um
[1:06:10] well, one of the things we need to be
[1:06:12] able to do is
[1:06:16] um bind elements in our calls. And here
[1:06:20] we get to make another awesome
[1:06:22] assumption.
[1:06:23] Uh one of the great things that happens
[1:06:25] when things happen across time
[1:06:28] is they're sorted by time.
[1:06:31] And that is incredibly useful because it
[1:06:33] means that we can binary search them.
[1:06:37] And there's many reasons you need to do
[1:06:38] this uh in profilers in general and in
[1:06:41] white box in particular. Um but let's
[1:06:45] just say we need binary search
[1:06:48] and we can take advantage of this bite
[1:06:50] first thinking. Um so first of all the
[1:06:54] the default if you were treating this in
[1:06:57] a type first way it would be okay. We we
[1:06:59] have our call um let's just say we have
[1:07:02] a simple array rather than this slightly
[1:07:03] more complicated z we have an we have
[1:07:06] our array of calls and oh we need
[1:07:09] because we're in C we need this we need
[1:07:12] this separate uh we need a separate
[1:07:14] function for each type of strct that we
[1:07:17] are going over we need one for calls and
[1:07:19] we need one for stack levels and we need
[1:07:21] one for all these other things that
[1:07:22] we've we've mentioned we have arrays of
[1:07:24] and that is that's that gets unwieldy
[1:07:27] um But like if you're doing a search
[1:07:32] over things, are you actually comparing
[1:07:34] the whole strct? Uh I would say in
[1:07:38] almost all cases, no. You're you're just
[1:07:40] comparing some in 99% of cases you're
[1:07:44] comparing some simple member of that
[1:07:47] strct.
[1:07:49] There's the occasional one where you
[1:07:50] need to compute uh compute something
[1:07:52] given multiple members, but the typical
[1:07:55] case is this.
[1:07:57] And so if you're happy to you have this
[1:08:00] this strct that you're looking through
[1:08:01] and you can identify a search key, you
[1:08:03] really only need one version of this
[1:08:06] function per search key type, not outer
[1:08:08] key type.
[1:08:12] Once you've gone through this and worked
[1:08:14] it out, uh it's it's not much more
[1:08:16] complicated to do it for the for the ZAR
[1:08:18] version. Um and this is the the code for
[1:08:22] that. I'm not going to claim it's the
[1:08:23] best binary search. In fact, I know it's
[1:08:24] not because there are better branch
[1:08:26] versions. But uh I'll just point out two
[1:08:28] things. One, uh we're getting the Z meta
[1:08:32] and you can actually see here the case
[1:08:33] that I was referencing earlier where you
[1:08:36] end up with multiple different um
[1:08:39] parameters and it's quite nice having
[1:08:41] your Z meta constrained to one thing
[1:08:42] rather than is split out into all of its
[1:08:44] members.
[1:08:46] Um
[1:08:47] and the other is you just end up doing
[1:08:51] the typed get
[1:08:54] uh and then get the offset into that
[1:08:56] strct and then you know the thing that
[1:08:59] you test against and you test we're
[1:09:01] doing a slightly
[1:09:03] this is a binary search where uh rather
[1:09:06] than just finding an exact element you
[1:09:08] find the thing that is less than or
[1:09:11] equal to that element. So it's slightly
[1:09:13] unusual.
[1:09:17] And here is where you may have seen a
[1:09:20] hole in the z before. Here's where we
[1:09:22] get to fill that in. Um, and if you're
[1:09:25] thinking that this is a very pure a very
[1:09:28] pure structure, maybe you're making a
[1:09:30] library for this, then um I don't know
[1:09:33] this this is a member that may not make
[1:09:35] sense. But this is for our codebase.
[1:09:38] This is for a spec specific purpose that
[1:09:41] we know. Uh, and so we can put in the
[1:09:44] things that are helpful even if they're
[1:09:45] not pure. Uh and so
[1:09:48] we have all of these parameters current
[1:09:50] uh as as an option. There's like the
[1:09:53] most explicit layer possible. Uh but
[1:09:55] most of the time we don't need all of
[1:09:57] that. That's more complicated than we
[1:09:58] need and we just binary search an array
[1:10:01] kind of as expected.
[1:10:04] General point here is I often find it
[1:10:07] helpful to have um the explicit function
[1:10:10] with everything specified and then all
[1:10:13] helper functions call that with
[1:10:16] different things. So you have you have
[1:10:17] this extra one layer. You don't end up
[1:10:20] then doing like
[1:10:23] this this tree of specializations adding
[1:10:26] one more specialization each for each
[1:10:28] call in that call stack. Uh so side
[1:10:31] point though,
[1:10:34] okay, we're gonna
[1:10:39] jump slightly to a different topic or a
[1:10:42] different aspect of this topic. Uh and
[1:10:45] that is mappings. Back to mappings.
[1:10:50] Now,
[1:10:51] I wanted to include in this talk a kind
[1:10:54] of full section on using um the
[1:10:58] locations of things as a source of
[1:11:00] information. Uh but it turned out
[1:11:03] there's uh far too much to say there
[1:11:05] that um and it would completely blow out
[1:11:08] the rest of this talk and it's it's far
[1:11:11] too long as it is. So, we've got some
[1:11:14] mappings. Um, and what what you're
[1:11:17] probably familiar with is doing you're
[1:11:19] probably familiar with doing parallel
[1:11:20] arrays in the context of um, SOA style
[1:11:24] structures where you know thing at index
[1:11:28] zero in one array maps to thing at index
[1:11:31] zero in some other array and they're
[1:11:33] kind of conceptually part of the same
[1:11:34] thing but stored separately. And the
[1:11:37] wins you get from this are u maybe it's
[1:11:40] cache in that they're um or the access
[1:11:44] pattern means that you're accessing all
[1:11:46] of one array and not the other one.
[1:11:47] Maybe it's a size thing where um one of
[1:11:50] them only has to be bit flags and the
[1:11:52] other one is some large str member and
[1:11:54] the bit flag would throw off the
[1:11:56] alignment so you end up with a bunch of
[1:11:57] wasted space. Um maybe it's just you
[1:12:00] know uh you get this mapping
[1:12:04] and you don't have to record any data.
[1:12:07] You just it's it exists in the ether for
[1:12:10] free. And well you you're just getting
[1:12:13] this from the fact that you have this
[1:12:14] structure.
[1:12:16] And then another case um that is
[1:12:20] particularly helpful is
[1:12:23] you have two different arrays that live
[1:12:27] on different lifetimes
[1:12:29] and they get to know about each other.
[1:12:33] Um but you never have to keep an
[1:12:34] explicit pointer or handle a reference
[1:12:36] or anything from one to the other or
[1:12:38] generic map whatever. Uh, and what that
[1:12:41] means is that the thing that you're
[1:12:43] pointing to, if that disappears, you
[1:12:46] don't have to go and fix up any
[1:12:47] pointers. You don't have to say, "Oh,
[1:12:48] wait, no, this is no longer this no
[1:12:50] longer exists. I need to make sure that
[1:12:52] I've uh I've handled that case." It just
[1:12:55] poof, it's gone.
[1:12:58] And this shows up for us in the call
[1:13:01] stack case. Now I mentioned near the
[1:13:02] beginning that we have this kind of
[1:13:04] event cache um where we look up
[1:13:07] information at the um when we have a
[1:13:10] debug event. Uh and we one of the things
[1:13:15] that we store is like an unwound call
[1:13:17] stack.
[1:13:23] And you've also seen from the timeline
[1:13:25] view that we have this kind of profiler
[1:13:28] like view of calls across time.
[1:13:32] And
[1:13:34] what's quite nice here is we have some
[1:13:36] parallel mapping, but there's a nuance.
[1:13:39] Um,
[1:13:43] call stacks when you unwind them, you
[1:13:45] start at the current um the current
[1:13:47] instruction pointer, the current level
[1:13:50] of the call stack, and then you do a
[1:13:52] little bit of jiggory pokery and you
[1:13:53] find the pointer back to the previous
[1:13:55] level of the call stack, and you end up
[1:13:57] with a kind of gnarly linked list. um
[1:14:01] going from the leaf to the root.
[1:14:03] And then in our profiler leg view, we
[1:14:06] want to store that with the root at the
[1:14:10] bottom because it means that as the as
[1:14:12] the size of the call type changes, it
[1:14:15] stays in the same place.
[1:14:18] Uh so this means that we're we're
[1:14:20] counting in opposite directions. And
[1:14:24] what what this basically means is that
[1:14:26] we have kind of this this inverse
[1:14:28] parallel case which is it's a slight
[1:14:30] extension to the parallel case and it's
[1:14:33] you know big deal I guess. Um but
[1:14:37] there's a there's something else that
[1:14:38] comes out of this which is
[1:14:41] we're thinking about our um profiler
[1:14:44] call levels. Uh I I keep saying
[1:14:47] profiler. you're getting data across
[1:14:48] this as well as calls, but uh I'm sure
[1:14:51] profile is more familiar.
[1:14:55] Um when we're accessing data at these
[1:14:58] different levels, sometimes you're going
[1:14:59] to be okay at at level two,
[1:15:04] we have some data
[1:15:07] and
[1:15:09] maybe um I pass a pointer to that data
[1:15:11] into these lower functions. Maybe they
[1:15:13] modify that data. I want to keep looking
[1:15:15] at that data referenced in in corite
[1:15:18] level two uh and see how it changes
[1:15:20] across time. What you also might want to
[1:15:22] do is say whatever's at the top of the
[1:15:25] stack what is currently happening there.
[1:15:27] And so we need to be able to reference
[1:15:29] uh from both these sides.
[1:15:32] Okay, cool. This this seems like a uh a
[1:15:37] solved issue. You know, you've used
[1:15:39] Python. You've seen many things that do
[1:15:41] this. Um,
[1:15:44] if you're kind of indexing into an
[1:15:46] array, you can use zero to or positive
[1:15:48] numbers to access from from the left or
[1:15:50] negative numbers to access from the
[1:15:52] right and you get this zero one zero and
[1:15:55] minus one kind of the opposite sides and
[1:15:57] then one minus two opposite sides and so
[1:15:59] on. Um, and that's kind of the in the
[1:16:04] general case you're doing this minus x +
[1:16:06] one with the brackets in the right place
[1:16:08] to to convert from level to depth.
[1:16:13] I don't know if anyone can see where
[1:16:14] this is going.
[1:16:18] Welcome to bits of high level part
[1:16:20] three.
[1:16:26] If you're happy to happy to assume that
[1:16:28] you live on a two's complement machine,
[1:16:30] which
[1:16:32] well I know I do. Um
[1:16:35] you can you can make that choice for
[1:16:36] yourself. uh then you you know that this
[1:16:40] minus x + one is the same as a not x.
[1:16:43] Now okay is is this swap going to make
[1:16:47] the difference between a completely
[1:16:49] amazing feature and
[1:16:52] uh something that doesn't work at all?
[1:16:54] Probably not. But you will notice
[1:16:58] uh there's there's many of these things
[1:17:01] there's many operations happening on the
[1:17:02] left. And you know you might do minus x
[1:17:05] plus one and you're like ah I forgot the
[1:17:06] parenthesis. H sorts of bugs. Is it x
[1:17:09] minus one? H what was it? What was it
[1:17:11] again? Um you got to take this extra
[1:17:13] thinking step to make sure you've got
[1:17:15] that right. And it's another place that
[1:17:18] you might get things wrong. Uh and if
[1:17:20] you know that you can do this this not
[1:17:22] operation and do this flip, then that's
[1:17:25] makes things so nice.
[1:17:28] It's small. It's a it's a creature
[1:17:30] comfort. let's say
[1:17:33] um if you're thinking of negation
[1:17:36] uh if you look at it on a on a number
[1:17:37] line we're kind of flipping around the
[1:17:40] middle of zero so negative 0 maps back
[1:17:42] to zero um the negative of the minimum
[1:17:45] number I think is technically undefined
[1:17:47] but in practice often maps back to
[1:17:49] itself uh and then everything else you
[1:17:52] know does it what you expect one goes to
[1:17:54] minus one and so on and then it's worth
[1:17:56] seeing that the the not version of this
[1:17:58] it effectively mirrors around uh you can
[1:18:02] you can think of this either as minus0.5
[1:18:05] or the left edge of zero depending on
[1:18:08] what makes more sense to you in the
[1:18:11] integer case the the second feel
[1:18:13] somewhat more appropriate. Um
[1:18:16] uh and that means that we can do level
[1:18:19] equals not depth and depth equals not
[1:18:20] level. Uh and everyone's happy and you
[1:18:25] know ah squiggly,
[1:18:32] right?
[1:18:34] Uh let's
[1:18:37] have a have a roundup of where we've got
[1:18:38] to with this call situation. You may
[1:18:41] remember the tree that had run which had
[1:18:45] members of run thread which have levels
[1:18:47] in a call stack uh which have a number
[1:18:49] of calls and then each individual call.
[1:18:53] Uh and this is the a potential layout of
[1:18:56] that within a single arena uh with these
[1:18:59] zars. Um so our red run thread at the
[1:19:04] left points sorry our red run at the
[1:19:06] left points to these blue run threads.
[1:19:10] Um
[1:19:12] the run thread, you can see that these
[1:19:16] uh the run threads are pointing to these
[1:19:18] green call stack levels. And you can see
[1:19:20] we've got three of them. The first two
[1:19:22] are the same size and the uh third one
[1:19:24] is double the size. Um and then
[1:19:28] the
[1:19:30] uh the the stack levels,
[1:19:33] what did I get to? It calls the next one
[1:19:36] down. Um sorry, not calls. it references
[1:19:39] the next level down the with the chunks.
[1:19:42] Um, and then once we're done with this,
[1:19:45] so you can see that we've interled
[1:19:47] pushing onto these different um
[1:19:49] different arrays. And the if it's not
[1:19:51] obvious, the the hashed bits are just
[1:19:53] memory we don't care about. Something
[1:19:55] else is there for for this purpose.
[1:19:57] Um, but yeah, we've we've interled all
[1:20:00] these things. We've done all our stuff.
[1:20:02] We've shown everything to the user. The
[1:20:04] user's so grateful to us for showing us
[1:20:06] all this information. They fixed their
[1:20:07] bugs and yes.
[1:20:10] Um, but now it's time for another run.
[1:20:13] Let's go.
[1:20:16] Clear.
[1:20:18] Just pop back.
[1:20:20] You can zero the um the one array left
[1:20:25] of pointers. And so zeroing it means you
[1:20:28] have um no members and then all of your
[1:20:30] pointers are null and doesn't point to
[1:20:33] anything. And we're reset. And it's one
[1:20:36] operation. You don't have to walk all
[1:20:37] the way up the stack. You don't have to
[1:20:39] keep all of these arrays around in some
[1:20:42] real tree.
[1:20:44] There we go.
[1:20:50] Part three, pipelining dependencies. Um,
[1:20:54] we're going to take a jump back to the
[1:20:56] debugger world here in a sec, but we're
[1:20:58] going to start with a a simple example.
[1:21:03] So, we're building up some case.
[1:21:05] something has happened. Uh we want to
[1:21:07] switch and we we have our case ename a
[1:21:12] we do the thing that happens with that
[1:21:14] and we do some other other code and we
[1:21:16] have another case and we get some stuff
[1:21:18] that's specific to that and then we also
[1:21:21] get some stuff that's the same as the
[1:21:22] the first one. Uh and then we get a
[1:21:24] third case and we we've copied it again
[1:21:26] but we're starting to think this this is
[1:21:29] going to be a little bit hard to
[1:21:30] maintain. Maybe we need to do something
[1:21:32] with this. And then we get a fourth
[1:21:35] case. We're like, yeah, we we probably
[1:21:36] should do something about this. These
[1:21:38] are meaningfully the same. And
[1:21:42] this this is going to be a nightmare.
[1:21:43] Like assume this is not just two lines
[1:21:45] of code, but some considerable amount.
[1:21:49] So
[1:21:51] default response I'd say is pull this
[1:21:55] out into a function.
[1:21:58] And you know it it kind of works. uh
[1:22:02] there's nothing completely nothing wrong
[1:22:04] with that and in many ca in many cases
[1:22:06] that is uh probably the best approach
[1:22:09] but you will often find that a better
[1:22:12] approach is in my particular view uh is
[1:22:16] to do this pipelining thing where you do
[1:22:19] each individual case uh and then you
[1:22:22] move the the common code down so that
[1:22:24] all of them end up going through that
[1:22:26] that code path.
[1:22:28] uh and there's this extra step for setup
[1:22:30] common because there's often something
[1:22:31] that has to be done before that.
[1:22:35] So this is the case with calls. We end
[1:22:38] up with these kind of multiple different
[1:22:40] paths. Uh kind of ends up as a tree. And
[1:22:45] here we have everyone's favorite data
[1:22:47] structure, the DAG. Yes. Yeah.
[1:22:52] Okay. You you might be thinking like
[1:22:54] this is this is an unfair example.
[1:22:56] You've explicitly said that all of these
[1:22:58] things are completely the same and
[1:22:59] there's one of them and they're they're
[1:23:01] all matching. Okay, fair point. Fair
[1:23:03] point. Let's do a slightly more hard
[1:23:06] example.
[1:23:08] So
[1:23:10] now we have five different things that
[1:23:12] might get done as a result of our four
[1:23:14] different enums. Uh and then each of our
[1:23:17] enums does a different but overlapping
[1:23:20] subset of those things.
[1:23:22] Okay. So again kind of first version of
[1:23:26] this pulling out in the in the default
[1:23:28] way to functions. Um
[1:23:32] you can do this but now each of your
[1:23:35] call sites has some different context
[1:23:37] from within that enum specific case. And
[1:23:41] also you now have a function in your
[1:23:43] codebase that might get called from
[1:23:46] somewhere else. And
[1:23:50] you know either you take the approach
[1:23:55] this might get called from somewhere
[1:23:56] else and you handle that in which case
[1:23:59] you have to do all of this work to make
[1:24:01] sure that you're not assuming too much
[1:24:02] context or you don't do that and then
[1:24:06] you later come back to this you're like
[1:24:07] oh that looks like it does the thing I
[1:24:08] want it to do and you use it and you
[1:24:10] forget about all of the assumptions that
[1:24:12] you made as part of making it. uh and
[1:24:14] then you have a bad time debugging
[1:24:16] because there's some subtle case that
[1:24:18] you've forgotten about. So the the
[1:24:22] alternative that I would propose in not
[1:24:25] all but but some cases uh is to do this
[1:24:28] pipelining approach.
[1:24:32] Okay. So in in the kind of abstract we
[1:24:36] have each individual case uh and then we
[1:24:39] work out what we want to do and then we
[1:24:42] do the things that we want to do
[1:24:45] that kind of ends up in in this
[1:24:47] situation. Um except there's a you know
[1:24:51] there's often a wrinkle between with
[1:24:53] with this which is that these have inner
[1:24:56] dependencies between them and in this
[1:24:59] case that's trivial. You've just you can
[1:25:02] just order these if statements in the
[1:25:04] right way.
[1:25:07] Trivial is maybe an overstatement there.
[1:25:10] Sometimes there are complexities there,
[1:25:12] but in many cases once you've worked out
[1:25:15] what the different jobs to be done are,
[1:25:17] ordering them is straightforward.
[1:25:20] Okay, let's have a look a look at a
[1:25:22] couple of ways that we could do this.
[1:25:24] Um, one is I I kind of think of as um a
[1:25:29] bit like a it's you're framing what
[1:25:32] needs doing in terms of the input in
[1:25:35] terms of the problem statement. Um, and
[1:25:38] so using our best friend bits. Yes. Can
[1:25:41] we get another round of applause?
[1:25:47] We can use our linearly incrementing
[1:25:50] enum and turn that into a flag.
[1:25:54] um and then compare that flag with uh
[1:25:56] different combinations of other flags.
[1:25:58] Uh and again, we're doing a few
[1:26:00] operations here, but again, this is
[1:26:01] these are constant things that will get
[1:26:03] uh turned into a single value at compile
[1:26:06] time. Um and if you
[1:26:10] um blur your eyes a little bit, this is
[1:26:12] quite similar to what we were doing with
[1:26:14] our types case, except those were
[1:26:16] already kind of pre-shifted
[1:26:19] um where we were checking against
[1:26:20] pointer and reference and array, that
[1:26:21] kind of thing all at once.
[1:26:23] Um, an alternative is
[1:26:27] we frame the problem in terms of what we
[1:26:29] want to do as a as a result kind of the
[1:26:32] output of this um of this event this
[1:26:36] thing that's happened and um again using
[1:26:41] bits but just slightly differently we
[1:26:43] are just specifying I want to do job job
[1:26:46] one job two job three whatever uh and
[1:26:48] then we do them and you know each of
[1:26:50] these operations bitwise s trivial. Um,
[1:26:54] computer's not going to complain about
[1:26:55] them once you're familiar with them.
[1:26:57] Incredibly concrete, kind of easy to
[1:27:00] understand what's going on.
[1:27:03] Okay, let's let's go one step harder.
[1:27:06] Um,
[1:27:08] it's possible that it's the enum is not
[1:27:11] the only thing that determines what
[1:27:12] needs to be done. Uh, and in that case,
[1:27:15] uh, you, you know, have this if
[1:27:16] statement at the top. Uh, and if that is
[1:27:19] true, then you kind of need to be in
[1:27:22] this um output oriented thing as far as
[1:27:25] I'm aware, unless you start making your
[1:27:27] conditions really complex. Uh, but
[1:27:29] you're probably already doing that
[1:27:32] analysis earlier on when you're trying
[1:27:34] to understand the problem input. Uh, and
[1:27:37] it often ends up being easier to specify
[1:27:38] in this way. Uh, and then another thing
[1:27:41] that might happen is that while doing
[1:27:44] your jobs, you realize that something
[1:27:45] else needs doing afterwards.
[1:27:48] And
[1:27:50] uh I've written this in a slightly
[1:27:51] different way here. Um this is kind of
[1:27:53] doing a branch free branch free version
[1:27:57] of the if statement above. Uh where
[1:28:00] you're converting some condition to zero
[1:28:02] or one and then multiplying it by a
[1:28:04] flag. So that is either zero or the flag
[1:28:07] uh and then you're um oring it which is
[1:28:10] like item potently set including uh into
[1:28:14] your flags.
[1:28:16] Um now
[1:28:21] my gen I tend to tend to have the
[1:28:25] opinion that
[1:28:27] um
[1:28:29] you can go you can definitely go too far
[1:28:31] with branch free code if readability is
[1:28:33] your goal. Um but a little bit of branch
[1:28:36] free code will actually end up being
[1:28:38] easier easier to read once you're used
[1:28:40] to it. Uh because it means you're doing
[1:28:42] this thing than this thing than this
[1:28:43] thing than this thing. There's no
[1:28:44] there's no indirection. and there's no
[1:28:46] kind of extra layer of looking out into
[1:28:48] different different places and trying to
[1:28:49] keep that stack of like what's happened.
[1:28:52] Um,
[1:28:55] your mileage may vary.
[1:28:58] Okay, we can we can expand this a little
[1:29:00] bit more. Sometimes uh just do the thing
[1:29:03] is not enough information. Sometimes you
[1:29:04] need to know like what am I doing with
[1:29:06] this thing? There's some parameter
[1:29:08] effectively that needs to be passed to
[1:29:09] the operation. And so we just add some
[1:29:12] data that's available for that.
[1:29:16] um you you might get to the point where
[1:29:17] you package these together into a strct.
[1:29:20] Uh you might end up that do the thing or
[1:29:23] not do the thing is not quite the right
[1:29:25] framing. A better framing is don't do
[1:29:27] anything or do version one or do version
[1:29:30] two uh or three or four or five. And if
[1:29:35] you have just three options then kind of
[1:29:38] uh from a bit perspective the
[1:29:43] the the flags version two bits and the
[1:29:48] um sorry the flags version which is two
[1:29:51] bits and the kind of enum small enum
[1:29:54] version which is two bits for three
[1:29:56] values uh are the same. Uh
[1:30:00] but from a kind of mental modeling
[1:30:04] perspective, it may make sense to to
[1:30:06] break it down this way anyway. Um or you
[1:30:09] may find that the you know keeping with
[1:30:12] just bits and having a very simple uh a
[1:30:15] simple protocol there is is the e easier
[1:30:18] thing to understand. Once you get kind
[1:30:20] of to higher numbers, um
[1:30:25] the number of values that you can
[1:30:27] represent with a few bits compared to
[1:30:29] the number of uh individual bit flags
[1:30:32] you can represent with the new bits
[1:30:34] grows astronomically. And so uh you can
[1:30:37] you can fit more kinds if they are
[1:30:40] mutually exclusive into a single value.
[1:30:43] Uh and that and that's kind of the big
[1:30:44] one of the big distinctions between kind
[1:30:47] of using um separate dimensions versus
[1:30:52] growing a dimension uh comes down to
[1:30:55] which is kind of are can these things
[1:30:57] happen at the same time or uh can only
[1:31:00] one of these things be true at once. And
[1:31:01] so in this case our job can only be
[1:31:04] beginning or ending or it can be
[1:31:06] neither.
[1:31:09] And so this is modulo some detail pretty
[1:31:12] much what we're doing with debug events.
[1:31:15] Um this is roughly you know again
[1:31:19] skimming some stuff what we get from um
[1:31:22] from the Windows operating system. Uh we
[1:31:24] get uh process has been created a thread
[1:31:26] has been created uh module has been
[1:31:28] loaded. Um and you'll you'll notice that
[1:31:33] uh in create process event at the top we
[1:31:35] have this this thread begins and we have
[1:31:37] some data for the thread. what handle it
[1:31:39] is. And then al the same thing happens
[1:31:41] in create thread. Uh and then the same
[1:31:43] thing that happens in sorry a module
[1:31:47] begins in load DL and a module begins in
[1:31:50] create process debug event. Um as Ryan
[1:31:54] mentioned uh a module you can kind of
[1:31:57] think of as a term that encompasses both
[1:32:00] loaded exes and loaded DLS.
[1:32:04] Uh and then we have the other side of
[1:32:05] this thing which is uh handling our
[1:32:07] debug event. And um we get to handle the
[1:32:12] um
[1:32:14] uh the the thread beginning from the
[1:32:17] create process event and the thread
[1:32:18] beginning from the debug event in one
[1:32:21] place. And I mean just it's one place in
[1:32:24] the code. And that's not just like one
[1:32:26] function where it gets run although that
[1:32:28] is true. It is also one call stack in
[1:32:30] the there is no call stack where this
[1:32:32] gets hit other than the one where it
[1:32:34] gets hit. So you know exactly what is
[1:32:37] happening. You know exactly the context
[1:32:39] when this is run.
[1:32:42] Um again you know we're handling modules
[1:32:46] getting loaded and unloaded. Uh and then
[1:32:48] sometimes you know things happen. Um
[1:32:50] maybe some exception got hit and we need
[1:32:52] to break the user's process. Uh that's
[1:32:54] kind of a a job flag that we we have.
[1:33:00] Okay. So we've
[1:33:03] I think a thing to notice here is that
[1:33:06] the left stuff is framed in the context
[1:33:10] of the problem. And so in this case it's
[1:33:14] platform dependent uh and it's using the
[1:33:19] granularity of states that Windows
[1:33:22] specifies.
[1:33:23] um and also the the way that they've
[1:33:26] split it out and then we get to
[1:33:28] reinterpret that into a way that is
[1:33:30] convenient for us and handle that in our
[1:33:33] own code and we can make it platform
[1:33:35] independent and I I find that there's
[1:33:37] quite often this split of like the
[1:33:40] framing that makes sense from the input
[1:33:41] and the framing that makes sense from
[1:33:42] the output and they're they're not
[1:33:44] always the same thing. um you you get
[1:33:45] this kind of in uh slightly semantically
[1:33:49] compressed
[1:33:51] um
[1:33:53] uh data formats where they represent the
[1:33:55] same information in multiple ways
[1:33:56] depending on you know the size of the
[1:33:58] integer although that that and then that
[1:34:00] doesn't actually change the way that you
[1:34:02] handle that integer after the fact.
[1:34:06] Anyh who,
[1:34:09] we've got this way of
[1:34:14] dealing with
[1:34:16] dependencies.
[1:34:17] We can we can pipeline these things into
[1:34:19] kind of we work out what the jobs to be
[1:34:21] done and then we do the jobs. Great. Um
[1:34:25] if you look for it depend the the issue
[1:34:28] of dependencies appears everywhere.
[1:34:31] It's a really really useful lens to
[1:34:33] have. If if you've been following
[1:34:34] computer enhance Casey, then you'll know
[1:34:37] about the issues with dependencies at
[1:34:40] the machine code instruction level. Um
[1:34:42] you can think of them in this level. You
[1:34:44] can think of them as like build system
[1:34:46] dependencies. Um and then you can you
[1:34:49] have have this completely generic
[1:34:52] version, the most generalized version
[1:34:54] possible that you can think of. And then
[1:34:56] we have all of these specializations
[1:34:58] that we can apply to our actual problems
[1:35:00] that assume the things that we know
[1:35:01] about the problem space. Um so in our
[1:35:05] case we only ever do the thing once or
[1:35:07] we don't do it. You you often end up in
[1:35:10] a situation where there's a you might
[1:35:12] want to do a thing multiple times and
[1:35:14] that's often where cues can get
[1:35:16] involved. Um you can have a a DAG that
[1:35:20] is statically defined and then adds this
[1:35:23] element of um caching or um we we keep
[1:35:29] some data around from from previous
[1:35:31] times. So that we not only does this
[1:35:36] thing
[1:35:37] uh do we depend on the state from like
[1:35:40] just earlier in the function, we depend
[1:35:42] on previous loops of this this whole
[1:35:44] iteration. Uh and then you can get all
[1:35:47] the way to the most generic possible uh
[1:35:49] DAG. Uh but you know who would do that?
[1:35:53] Uh
[1:35:54] okay, admittedly so this is from this is
[1:35:57] from uh this is whitebox.
[1:36:00] This is the the legit ver world of white
[1:36:03] box where
[1:36:06] um you know we basically are operating a
[1:36:10] build system and
[1:36:13] you can see that this is not the
[1:36:15] simplest of dependency graphs. You can
[1:36:18] get more complicated of course um but
[1:36:21] this particular dependency chain was not
[1:36:24] completely obvious a priority. we we had
[1:36:27] to work this out as we went. And so
[1:36:29] having this as a more general data
[1:36:31] structure helped us to both pipe it into
[1:36:34] dots so we could actually see what the
[1:36:36] data data structure was um and then also
[1:36:40] um we could attach state to each of
[1:36:41] these nodes and add some more extra
[1:36:43] debug information which is helpful.
[1:36:46] Thinking back on it I think we probably
[1:36:47] could have gone kind of half a step
[1:36:50] um more specialized more concrete. Um
[1:36:56] I think that the actual operations could
[1:36:58] have been uh done in this
[1:37:03] you know inline way where you just work
[1:37:05] out what what it's doing and your linear
[1:37:07] linearization is kind of statically
[1:37:09] baked in uh and then you add on top of
[1:37:11] this um
[1:37:14] uh a kind of immediate mode API for
[1:37:17] adding the debug information so that you
[1:37:19] can work out what's going on. Um but
[1:37:21] then and then that way your the
[1:37:24] complexities of traverse you know
[1:37:27] modeling and traversing a DAG uh are not
[1:37:30] in your real code. They're only in your
[1:37:31] debug code.
[1:37:33] Um the you've you've simplified that
[1:37:36] into the linearized or pipeline version
[1:37:38] in the actual code.
[1:37:41] Okay. So
[1:37:44] the point about assumptions here is
[1:37:49] that you can if you know the case you're
[1:37:52] working with, if you know the code that
[1:37:55] is running around this, if you know the
[1:37:57] problem domain, you can make so many
[1:38:00] assumptions that make it easier to
[1:38:01] understand and much faster to run.
[1:38:05] Um,
[1:38:06] but
[1:38:08] you know, designs change. You might be
[1:38:10] thinking like, okay, this is good as
[1:38:13] long as my my code stays exactly the
[1:38:15] same forever, but uh
[1:38:19] you know, things change and that is
[1:38:22] true. Um I would like to go more into
[1:38:24] this at some point, but I will touch in
[1:38:26] it now because I feel like I I should.
[1:38:29] Um,
[1:38:33] the first thing to say is
[1:38:38] you probably have some notion of what
[1:38:41] your design is going to be while you're
[1:38:42] writing it. Uh, and many programs are
[1:38:46] big and so you write them step by step,
[1:38:48] but you you have at least some notion of
[1:38:50] where you're going. Um
[1:38:53] there's there's a temptation to
[1:38:57] uh overly concret overly concretize kind
[1:39:01] of wherever you are. Um but you've got
[1:39:04] to there's you just have to have that
[1:39:07] self-awareness to like no this this is
[1:39:09] going to be this is this is going to
[1:39:11] change that don't optimize this. I don't
[1:39:14] want to tie myself into this specific
[1:39:15] limitation. And the example that jumps
[1:39:18] to mind for for me on that is um
[1:39:22] processes. Uh many debuggers will uh
[1:39:26] allow you to run multiple processes uh
[1:39:29] and analyze all of them at once. Ybox
[1:39:31] doesn't. And so I I would like to at
[1:39:34] some point so I don't make the
[1:39:35] assumption that I have a single process
[1:39:37] despite the fact that it's true across
[1:39:38] my entire codebase.
[1:39:43] Uh other friends that you have are
[1:39:46] static assert sizes, ranges, all that
[1:39:48] kind of thing. Um if you're assuming
[1:39:50] that uh your enums are in a particular
[1:39:53] range, uh you can check that at compile
[1:39:55] time. You don't have to um pay any
[1:39:58] runtime cost for that.
[1:40:00] A a fun one that um I haven't seen many
[1:40:04] people do is you can just add kind of
[1:40:07] garbage tokens that are meaningful to
[1:40:10] you. um make them exist somewhere and
[1:40:12] then use them around the code where you
[1:40:15] rely on the assumption that you're
[1:40:17] talking about and then if that if that
[1:40:19] assumption ever disappears you can get
[1:40:21] rid of the in this case define assume fu
[1:40:23] or you could have a constant or you know
[1:40:25] there's a few different ways you could
[1:40:26] do this and then your compiler will say
[1:40:30] basically this assumption is broken here
[1:40:32] and here and here and here go and check
[1:40:34] those
[1:40:37] [Applause]
[1:40:44] Uh, I'm a fan of asserts. Um, I'm sure
[1:40:47] you're all familiar with those. Um,
[1:40:51] there's nothing that requires you to
[1:40:53] requires you to make those be um just
[1:40:56] like simple expressions. If in de if
[1:40:58] you're in debug mode, uh you can do some
[1:41:01] arbitrarily complex check that
[1:41:03] structures are all like in the right
[1:41:05] order. the things that reference each
[1:41:07] other should reference each other,
[1:41:08] things that don't don't or shouldn't
[1:41:11] don't and so on. Um I think you saw
[1:41:15] earlier I have like unreachable and
[1:41:17] switch statements all the time. Um or
[1:41:19] like the end of an if else if else chain
[1:41:21] if you expect it to be handled above. Um
[1:41:24] this is another one that I quite like
[1:41:26] which is um
[1:41:29] in debug mode it will assert if the
[1:41:33] condition is true. Uh but in release
[1:41:37] mode it'll just evaluate to the
[1:41:38] expression itself.
[1:41:41] Um and then that means that you can like
[1:41:45] do the check for like this this just
[1:41:48] shouldn't happen. I I'm pretty sure that
[1:41:49] this doesn't happen. I'm not going to
[1:41:50] deal with that. Uh
[1:41:53] sorry. You are going to deal with that
[1:41:55] though because you're checking. So you
[1:41:57] can be like if this case happens that
[1:42:00] that is unexpected
[1:42:03] um tell me as a developer about it but I
[1:42:06] can do some kind of safe no op or exit
[1:42:08] the function or pass some error code
[1:42:10] back or however you're dealing with that
[1:42:12] um regardless and so that it's not going
[1:42:14] to affect the the end user.
[1:42:17] Okay,
[1:42:22] we have been, ladies and gentlemen,
[1:42:24] preempted again by bits of high level.
[1:42:29] Okay. Um, I'm not going to go over all
[1:42:31] of this. I'm not going to read a table
[1:42:32] off to you. I I just wanted to
[1:42:37] to bring up the idea that
[1:42:41] um you have a bunch of these bitwise
[1:42:43] operations, right?
[1:42:44] They're as concrete as it gets on a on a
[1:42:46] CPU. They're they're pretty fundamental.
[1:42:49] They're like mathematically understood
[1:42:51] concepts and all that. Um but
[1:42:56] once there's there's often a kind of oh,
[1:42:58] I've learned how they manipulate the
[1:43:00] bits now. I'm done with them. Um but I
[1:43:03] think if you can
[1:43:07] if you can see the other interpretations
[1:43:09] of these values
[1:43:12] see the other interpretations of these
[1:43:14] operations uh then you will find that
[1:43:16] they will apply in many cases in your
[1:43:19] codebase and ju just to
[1:43:22] to bring one up which I didn't really
[1:43:24] explicitly go over before um if we
[1:43:28] recall back to the
[1:43:32] this is on on the topic of
[1:43:35] reinterpreting things in multiple
[1:43:36] different ways. Our our base types, I
[1:43:40] know it's it's a long time ago now.
[1:43:42] Sorry for keeping you here so long, but
[1:43:44] if you recall back, we have our base
[1:43:46] type was our kind and our size, and we
[1:43:50] had those like jammed together. And we
[1:43:52] can interpret each of those things as
[1:43:54] separate values. Um, what I didn't say
[1:43:57] earlier, which I should have, is okay,
[1:44:00] we've put those together, we can
[1:44:01] reinterpret those as because we only
[1:44:05] have four bits for each of them. We
[1:44:07] reinterpret that as an 8 bit number,
[1:44:09] it's 256
[1:44:12] different possible values. That is 256
[1:44:14] different entries into our uh type
[1:44:16] array. And it means that we can
[1:44:21] we can we do this mapping back from um
[1:44:25] the the two
[1:44:27] twopart type kind into a location. So
[1:44:32] like it's not just it's sometimes one
[1:44:34] number and it's sometimes two numbers
[1:44:36] and the ability to switch between them
[1:44:37] lets you do extra things. And and the
[1:44:40] same goes for for these operations. Um
[1:44:44] yeah, I'm not going to go over them. you
[1:44:45] can get the slides afterwards and look
[1:44:47] over them if you want. Uh or you can
[1:44:48] find many other places that we'll we'll
[1:44:50] talk about them.
[1:44:53] Okay, it's been it's been a while. Thank
[1:44:56] you for bearing with me. Uh just going
[1:44:59] to sum up some of the things. Um I like
[1:45:03] stable pointers. Okay, if you can keep
[1:45:07] stable pointers, things become so much
[1:45:09] easier. I know that there are cases
[1:45:10] where handles are needed and that's
[1:45:12] fine. But there are many many sub cases
[1:45:15] where stable pointers are the best way
[1:45:17] to go.
[1:45:19] Uh if you can break your problems down
[1:45:24] into of separable dimensions
[1:45:27] um then you will find that uh you need
[1:45:33] much less code to handle all of the
[1:45:36] cases. And like you're a limited human
[1:45:38] being. There's only so much code you can
[1:45:40] understand. If you can if you can fit
[1:45:42] all the things that you have going on
[1:45:44] into a smaller space, it's often going
[1:45:47] to be easier.
[1:45:49] Um, now
[1:45:52] if if it's not obvious with the like a
[1:45:53] strct type and the product type um
[1:45:56] mentions, this rectangular dimensions
[1:45:59] thing is is kind of the same as a Plex.
[1:46:02] It's kind of the same as a mega. So we
[1:46:04] are team Plex team mega here.
[1:46:12] Um so what's happening is that with with
[1:46:16] your with your mega strruct you have all
[1:46:18] of these different members you think of
[1:46:20] all of these as a different dimension
[1:46:22] and at a certain point it gets hard to
[1:46:24] visualize but you can kind of abstractly
[1:46:26] think of it that way and then you know
[1:46:29] you don't all don't use all of these
[1:46:31] members in every case and those are just
[1:46:33] effectively holes in that space uh as I
[1:46:36] mentioned for
[1:46:40] hopefully I have convinced you that um
[1:46:42] you can think of bits as high level and
[1:46:45] um you can do these operations that are
[1:46:49] kind of semantically meaningful um that
[1:46:52] are incredibly concrete and the CPU is
[1:46:55] very happy doing them. Um I like
[1:46:59] pipelines. I'm going to keep it nice and
[1:47:02] simple.
[1:47:04] Try it out. see if it works for you. Um,
[1:47:09] again, I think that it you will find
[1:47:11] that it reduces the amount of context
[1:47:13] you need to keep in your head and
[1:47:15] reduces the amount of context that needs
[1:47:17] to be um,
[1:47:21] it reduces the amount that you have to
[1:47:23] add kind of uh, wrapping of stuff to
[1:47:26] make sure that certain assumptions
[1:47:28] aren't broken because if it's only used
[1:47:30] in one place, then you know how it's
[1:47:32] being used.
[1:47:34] Um
[1:47:37] many of these cases are about kind of
[1:47:39] removing indirection in one form or
[1:47:40] another. Whether that's extra calls,
[1:47:42] extra memory accesses, um doing thing
[1:47:46] doing doing things with complicated
[1:47:49] operations where we could do them with
[1:47:50] just a a simple bitwise. And
[1:47:55] [Music]
[1:47:57] the final point on generalization
[1:48:00] um
[1:48:02] I guess I guess my take on this is
[1:48:07] you want to know we've we've gone
[1:48:09] through these different topics. We've
[1:48:10] gone through kind of mappings and
[1:48:12] pipeline or dependencies
[1:48:14] uh and and uh understanding the
[1:48:17] different dimensions of things whether
[1:48:18] that's like tree structures or whatnot
[1:48:21] um tree structures or dimens or uh
[1:48:24] separable dimensions and I think that it
[1:48:28] is useful to know what the
[1:48:30] generalization of the thing you're doing
[1:48:32] is. I think the the map is the really
[1:48:34] obvious example to me there where like
[1:48:36] I'm doing a mapping I can map
[1:48:39] or I can use an array index or I can use
[1:48:42] any of these other things. Um so
[1:48:45] knowing what the generalization is will
[1:48:48] help you know will provide you a way of
[1:48:52] shortcutting to what the possible
[1:48:54] options to your solutions are. And then
[1:48:56] given your different assumptions, you
[1:48:58] can make a different specialization
[1:49:00] um to to do the simple thing, but the
[1:49:04] the simplest thing that is required that
[1:49:06] is not going to lock you in.
[1:49:10] I would tend to lean towards
[1:49:14] generalization over abstraction. uh as a
[1:49:16] rule um you end up with uh many fewer
[1:49:22] code paths and less indirection and a
[1:49:25] much better understanding of of what
[1:49:26] you're doing. Uh and if you actually
[1:49:28] need to understand the codebase, which
[1:49:31] you do because things are going to go
[1:49:32] wrong and you need the bug fix and you
[1:49:35] if there are bugs then your model of the
[1:49:37] world is wrong and you don't know why.
[1:49:40] So you're going to have to assume that
[1:49:42] everything is not working and if there's
[1:49:45] more code and more indirection that is
[1:49:47] going to be so much harder.
[1:49:52] Thank you very much for listening. I
[1:49:54] appreciate you sticking through with me
[1:49:57] there. Uh if you want to follow me on on
[1:50:00] Twitter or follow Whitebox, uh there's
[1:50:02] the the links. Uh feel free to message
[1:50:05] me about this or Whitebox or anything
[1:50:06] else. Uh and you can have a look at
[1:50:08] webbox on the website. Thank you very
[1:50:11] much.
[1:50:21] Thank you so much. That was such a good
[1:50:22] talk. Uh if you haven't already, uh you
[1:50:25] should go to whitebox.systems and try
[1:50:26] out whitebox. It is truly amazing what
[1:50:29] this program can do. It is unlike
[1:50:30] anything I have ever seen before and
[1:50:32] it's it's totally worth a try. Um so
[1:50:34] definitely go there. Um, I did want to
[1:50:36] ask you,
[1:50:36] >> that's very kind. I will just warn you
[1:50:38] that there are still sharp edges. So,
[1:50:39] uh, mind your fingers.
[1:50:42] >> I wanted to ask you, uh, I think it says
[1:50:44] it's on version 0.122.
[1:50:47] I wanted to know what the current state
[1:50:49] of white box is. What's the future?
[1:50:51] >> Um, yeah, that's actually a kind of
[1:50:54] that's an old version. It's actually uh
[1:50:56] we we just stopped doing that numbering
[1:50:59] system at some point and started saying
[1:51:00] the the date that things came out
[1:51:01] because it it felt somewhat ridiculous.
[1:51:03] Um, so we're currently releasing
[1:51:07] whenever there's there's something
[1:51:08] something new. Uh, and you know, if you
[1:51:12] if you've bought it, you access until at
[1:51:14] least the end of version version 1.0
[1:51:16] reel, which we're not at yet.
[1:51:18] >> Is there something that'll mark the 1.0
[1:51:20] release?
[1:51:23] >> Uh, that's a good question. There's
[1:51:26] there's a number of things that we
[1:51:27] definitely need. Um, and then there's a,
[1:51:30] you know, a list a list of nice to
[1:51:31] haves. Um, but I think it would take too
[1:51:34] long to to iterate through that now.
[1:51:38] >> So, I'm in the fortunate place of having
[1:51:40] seen this talk twice now. Uh, and I
[1:51:42] think I understand it about maybe 60 to
[1:51:44] 70%. I'm getting there. Um, so if you
[1:51:47] haven't or you know in the future once
[1:51:48] this is able to be watched as a VOD, you
[1:51:50] should definitely watch it again if you
[1:51:51] didn't understand everything, which I
[1:51:53] suspect is most the people here in the
[1:51:54] audience. Um, but you have an amazing
[1:51:56] amount of insight. There's so many
[1:51:58] interesting concrete details here that
[1:52:00] you've pointed out. Um, one of the
[1:52:02] things I find very interesting is, uh,
[1:52:04] you you have this sort of like empathy
[1:52:06] for the computer that helps you see the
[1:52:08] like combination between you and the
[1:52:10] computer and what is capable between you
[1:52:12] two. Um, specifically like operator the
[1:52:15] operands for instructions uh can be
[1:52:17] encoded smaller if you use numbers that
[1:52:19] are not shifted up like 32 bits or
[1:52:21] whatever. Um and and also like the whole
[1:52:24] uh structures that you have basically
[1:52:25] generics in C uh where with the calling
[1:52:29] conventions and knowing that you only
[1:52:30] have so many registers to pass um that
[1:52:32] sort of like three-way connection blows
[1:52:34] my mind. Um how did you how did you get
[1:52:37] to the state you were able to make those
[1:52:38] kinds of connections?
[1:52:40] So I think as a debugger you get a a
[1:52:44] head start on insight into those because
[1:52:46] you have to deal with calling
[1:52:47] conventions and you have to deal with
[1:52:49] you know what what registers are being
[1:52:51] passed and so on. Um
[1:52:53] uh more recently we're we're trying some
[1:52:57] uh some JIT stuff in the user process
[1:52:59] and as part of that we've been making um
[1:53:02] kind of a an assembler API. Uh so it's
[1:53:06] just just function calls rather than
[1:53:07] interpreting some text but basically
[1:53:09] doing the same thing that an assembler
[1:53:10] would for the subset that we of x86 that
[1:53:13] we need. Um, and that like really drives
[1:53:17] home the uh the encoding issues like
[1:53:21] this this is an immediate I have a
[1:53:24] deleted scene that um where the encoding
[1:53:29] of an LEA kind of changes between um you
[1:53:33] know you can you can encode you use LEA
[1:53:36] to do these little tricks where you
[1:53:39] multiply by one two three four five
[1:53:43] eight or nine
[1:53:44] Um, and kind of surprisingly a multiply
[1:53:48] by five, three, five or nine is encoded
[1:53:54] smaller than the powers of two. Um,
[1:53:58] and and that's like a quirk of the x86.
[1:54:01] Um, there are reasons behind that, but
[1:54:04] like it's it catches you out when you
[1:54:06] when you look at it. Um,
[1:54:09] so having done that really reinforced
[1:54:11] it. I think as I mentioned earlier,
[1:54:13] Godbolt is just like a wonderful
[1:54:15] resource. Everyone, if you haven't used
[1:54:16] Godbolt, what are you first of all, what
[1:54:18] are you doing? And second of all, go
[1:54:19] there now and put some code in and see
[1:54:21] what happens. Uh see what the machine is
[1:54:23] actually doing with with your
[1:54:24] instructions.
[1:54:26] >> Um so, uh if you haven't noticed, I've
[1:54:29] gotten more than my fair share of
[1:54:30] questions, uh in this conference. Um and
[1:54:33] I have around 20 questions written down
[1:54:36] here, so I'm not going to ask all of
[1:54:37] those.
[1:54:37] >> You can't ask all of them. We we there's
[1:54:40] no way we can fit Demetri. So we have to
[1:54:42] move into tomorrow. So you actually have
[1:54:43] >> Wait, hold on.
[1:54:44] >> Yes.
[1:54:45] >> How many is too many?
[1:54:48] >> All right. Well, for now I I will ask
[1:54:49] one more question. We'll do some
[1:54:50] audience questions. When we run out,
[1:54:52] we'll do more questions. Uh so buckle
[1:54:54] in. Um so one of the things I find
[1:54:57] really interesting uh and uh is that uh
[1:55:01] I often do I think Casemitori does this
[1:55:03] for bitwise operators. you'll often do
[1:55:05] like is flag set or all flag set or
[1:55:07] things like this where you kind of wrap
[1:55:08] up the bitwise operators and you kind of
[1:55:09] push them away a little bit with a
[1:55:10] define. Um, and I think at one point you
[1:55:13] called the unary not operator a squiggly
[1:55:15] kind of like endearingly. Um, I'm
[1:55:17] curious like do you think there's a
[1:55:19] benefit to keeping those operators in in
[1:55:21] the front there like being able to see
[1:55:23] those?
[1:55:24] >> Yeah. So,
[1:55:27] I think
[1:55:30] this doesn't really help when you're
[1:55:31] first writing it, but the the benefit of
[1:55:37] choosing one of these paths, whether you
[1:55:38] have kind of a meaningful name or the
[1:55:41] the operator just bare. Um the the value
[1:55:45] you get from having one of those
[1:55:47] consistently within a location is the
[1:55:49] ability to uh compare and contrast
[1:55:51] between them. So
[1:55:54] the problem is you don't know this
[1:55:55] beforehand which of those you don't
[1:55:57] necessarily know you might have a
[1:55:58] heristic which of those is going to be
[1:56:00] useful but you might end up with a
[1:56:02] situation where you want to contrast
[1:56:04] like is any bit of this set in one case
[1:56:06] and is all are all bits set in the other
[1:56:08] case and I know in the white box
[1:56:11] codebase we do that in a in a checkbox
[1:56:14] for like is a is it a tick or is it a
[1:56:16] the um you know half filled in square uh
[1:56:20] and in that case your your diff The
[1:56:22] point of having these things next to
[1:56:24] each other is to juxtapose those two
[1:56:26] different versions. Um, but then I think
[1:56:28] the the raw version is useful where
[1:56:33] um
[1:56:35] you end up with a bunch of these these
[1:56:37] operations next to each other and
[1:56:41] particularly if you're doing it in a
[1:56:42] branch way, you're just doing kind of
[1:56:44] simple maths at each point. Um, and I
[1:56:47] mean you saw what happened with the the
[1:56:49] minus x plus one and you can you find
[1:56:54] that many of these bitwise operators
[1:56:56] have a mathematical identity with some
[1:56:58] other things. So if you have some
[1:57:00] complex combination of operators, it may
[1:57:02] actually just collapse down to one or
[1:57:04] two. And
[1:57:08] um I guess that's interesting from a
[1:57:10] micro optimization point or if it's in a
[1:57:13] hot loop. Um but sometimes that's also
[1:57:15] interesting from like oh there's some
[1:57:18] kind of more fundamental thing that is
[1:57:19] happening. I'm I'm doing all this
[1:57:21] garbage as a way of describing this
[1:57:22] operation. Uh or you know this this
[1:57:25] straightforward way of describing this
[1:57:27] operation that happens to have multi
[1:57:28] multiple steps but actually there's
[1:57:30] there's only one thing that's happening.
[1:57:32] Well there's only a couple of things
[1:57:33] that are happening. Um,
[1:57:37] I wish I could give a prescription to
[1:57:39] when when to choose which, but it's a
[1:57:42] kind of gut feel, I guess.
[1:57:44] >> You said you work with contractors. Do
[1:57:46] you feel like you ever get push back
[1:57:47] from them being like, "Oh, this is
[1:57:49] scary. This is an operator. I don't
[1:57:50] know. I don't use the squiggly that
[1:57:51] often. What does that do again?"
[1:57:54] Um
[1:57:57] uh
[1:57:59] I mean I don't think we've had any
[1:58:03] issues with that because
[1:58:06] uh they're all intelligent and well
[1:58:09] practiced programmers. Uh so um
[1:58:14] you know I I kind of think that
[1:58:19] the these bitwise operators are pretty
[1:58:22] fundamental things in computing and
[1:58:26] unless architectures change
[1:58:27] dramatically. They're going to be around
[1:58:29] for a for a long time. um
[1:58:34] if you if you don't know them now then
[1:58:36] then you can learn and you know that
[1:58:39] they're a little bit unfamiliar at first
[1:58:40] but I think the familiarity is the the
[1:58:42] main barrier to get over once once you
[1:58:44] understand what they do that they're
[1:58:45] fairly straightforward.
[1:58:47] >> I used to have a co-orker I would talk
[1:58:49] to a lot about JavaScript. He loved
[1:58:51] JavaScript and he would often tell me
[1:58:53] that like oh yeah this this oneliner map
[1:58:56] like map thing that you can do in
[1:58:57] JavaScript it's amazing. And I was like
[1:58:59] well you know it's a little bit hard to
[1:59:00] understand. And he was like, "No, no,
[1:59:01] you should understand map for free.
[1:59:03] That's like a thing you should know as a
[1:59:04] JavaScript developer." And the rest of
[1:59:06] like all these like standard library
[1:59:07] things come for free assuming you're a
[1:59:09] good developer in this space. And I
[1:59:11] always kind of hated that idea of like
[1:59:12] uh just like the standard libraries,
[1:59:15] your atomic units that you should like
[1:59:16] take for granted, right? But I feel like
[1:59:18] the binary operators as you as you point
[1:59:20] out here, they are more fundamentally
[1:59:22] atomic units that like if you understand
[1:59:23] them, you understand them and those
[1:59:25] those help you out, you know, in the
[1:59:27] long term.
[1:59:27] >> Yes, definitely. Um, and not not only
[1:59:32] are they fundamental,
[1:59:35] um,
[1:59:38] I've kind of said this a few times, but
[1:59:39] they're very concrete. Like if you have
[1:59:41] a map over something with, I don't know,
[1:59:46] you you don't know what the
[1:59:48] implementations of that are. Um, there's
[1:59:50] maybe some side effect in terms of
[1:59:52] memory that you weren't expecting or
[1:59:54] maybe there's some edge case that it
[1:59:55] doesn't handle depending on what it is.
[1:59:57] Um
[2:00:00] and in the in the JavaScript case there
[2:00:03] are a million of them. There are like
[2:00:06] depending on how you count them like
[2:00:07] seven seven eight nine um bitwise
[2:00:11] operators, you know, it's something you
[2:00:13] can learn.
[2:00:15] >> All right, I'm going to go ahead and
[2:00:16] open it up uh for audience questions. Um
[2:00:18] let's go here. Yakas. Uh okay regarding
[2:00:22] your exponential array type um like have
[2:00:26] you ever tried comparing uh sorting
[2:00:29] sorting performance on let's say
[2:00:31] millions of items versus just regular
[2:00:34] array because I I do those a lot. So
[2:00:38] >> uh no I haven't tried comparing um we
[2:00:41] don't actually end up having to do any
[2:00:42] sorting because we're lucky enough that
[2:00:45] our input is already sorted by time.
[2:00:48] That's an important distinction.
[2:00:50] >> Yeah.
[2:00:51] >> Yeah. Yeah. Okay.
[2:00:52] >> I mean,
[2:00:54] there's maybe an edge case where like
[2:00:56] profiler style events come in that may
[2:00:58] be slightly out of order, but you're
[2:00:59] sorting like six elements rather than a
[2:01:02] million. You're just sorting at the very
[2:01:04] end. they're usually just iterating or
[2:01:06] or fetching one item or
[2:01:08] >> uh so what happen a relatively frequent
[2:01:11] case in the the timeline for instance is
[2:01:14] like um we we don't want to show all of
[2:01:18] the things that happened before the
[2:01:19] timeline. Uh so we will binary search at
[2:01:23] the the known start of the timeline find
[2:01:26] the first value at that point and then
[2:01:28] iterate from there there on uh that's
[2:01:30] quite common. um or there are places
[2:01:33] where we have multiple different bin
[2:01:35] multiple binary searches happening
[2:01:36] sequentially.
[2:01:42] No question, just admiration. You
[2:01:44] casually dropped a full Andrews hacker
[2:01:47] delight and the contents of a data
[2:01:49] structure white paper and just
[2:01:51] completely cool. No emotions, not even
[2:01:53] time for people to applause. Just like
[2:01:56] take this.
[2:01:57] >> Thank Thank you very much. That's very
[2:01:59] kind.
[2:02:05] You need to get uh better at pausing for
[2:02:07] applause. Like after every slide, you
[2:02:09] should just
[2:02:12] >> Any more questions?
[2:02:14] >> Will you be offended if I call them res?
[2:02:18] >> I mean, no, but it's more characters. So
[2:02:20] like, do you really want that?
[2:02:24] >> Oh, just the RA even shorter. daughter
[2:02:27] of Andrew. Now,
[2:02:29] >> CZ A R.
[2:02:34] >> Um, so you made a point of evangelizing
[2:02:36] for stable pointers at one point. Um, is
[2:02:39] there ever a time where you care about
[2:02:40] like keeping a pointer stable across
[2:02:44] multiple lifetimes like when it's
[2:02:45] deallocated and reallocated or does that
[2:02:48] basically always mean that you should
[2:02:50] expand the lifetime to to merge both?
[2:02:53] Um, do you have any particular examples
[2:02:56] in mind of when that
[2:02:58] >> I don't. asking if there's any any case
[2:03:00] where that would be something you'd care
[2:03:02] about or whether you
[2:03:04] >> I guess the the closest thing
[2:03:08] I I think we we have
[2:03:11] memory that persists across lifetimes
[2:03:17] um or across multiple lifetimes but not
[2:03:22] not stable pointers
[2:03:26] to them. Uh
[2:03:28] let's think. I think the the place where
[2:03:30] this might come up is to do with
[2:03:33] handling um our run arena because we
[2:03:38] don't want to give the memory back to
[2:03:40] Windows and then immediately ask for it
[2:03:41] again. So we we want we want to keep
[2:03:43] that around and
[2:03:46] um
[2:03:52] I mean so the the
[2:03:55] pointer to that is from like a parent
[2:03:59] strct. So I I guess in some in some
[2:04:02] abstract sense there's like a a run that
[2:04:04] hasn't happened yet. It's kind we're
[2:04:06] kind of between runs um and this pointer
[2:04:10] still exists.
[2:04:12] Uh, but
[2:04:15] I didn't I didn't really go into this,
[2:04:16] but you can kind of break down lifetime
[2:04:18] in multiple ways of like a value
[2:04:21] lifetime and a um a location lifetime
[2:04:24] and a memory lifetime. Um, and like so
[2:04:28] the memory is still is still there and
[2:04:31] the base strct is still there even if
[2:04:33] the thing that is conceptually
[2:04:35] referencing doesn't exist anymore. Um,
[2:04:42] yeah, I think that's where I come from
[2:04:44] with that.
[2:04:47] >> Other questions? Yeah.
[2:04:48] >> So, I find the exponential array like
[2:04:51] super cool. I I've never seen it.
[2:04:55] >> Like a mix between a slab allocator and
[2:04:59] um a binary tree in a
[2:05:02] >> array.
[2:05:03] So, I just want to know like has anyone
[2:05:05] seen it before?
[2:05:08] I think I have seen this.
[2:05:13] >> Can we uh
[2:05:14] >> It reminds me of like array mapped hash
[2:05:16] tries, right? Stuff like that.
[2:05:17] >> Yeah. But those are now called zars.
[2:05:19] >> No, those end up on trees.
[2:05:22] >> Those end up as a tree of nodes.
[2:05:23] >> Yeah. Yeah. Like it's arrays of arrays
[2:05:25] and they're exploited in the fact that
[2:05:26] we have power too where we do logarithms
[2:05:28] and stuff like that.
[2:05:30] >> Yes. But they're like log based on path
[2:05:32] link path.
[2:05:33] >> Yeah.
[2:05:35] You go wider, right?
[2:05:37] So I think
[2:05:40] I think there's like a
[2:05:42] log structured merge tree is a thing in
[2:05:44] databases
[2:05:46] um that uses a kind of similar concept
[2:05:49] of doubling sizes but for the for an
[2:05:52] entire tree at a time uh and that I
[2:05:55] forget the exact sequence but that may
[2:05:57] have been an inspiration as part of
[2:05:58] this. Um,
[2:06:01] but yeah, I'd be interested to see if
[2:06:02] anyone's seen them kind of used as
[2:06:06] intermediate data structures in code
[2:06:07] before. I will have to come and chat to
[2:06:10] you afterwards.
[2:06:11] >> I think it's worth mentioning. There was
[2:06:12] like probably six different messages in
[2:06:14] the chat and the Twitch chat being like,
[2:06:15] "Oh my gosh, this is amazing. This is
[2:06:17] our thing. Oh, what is this? This is
[2:06:18] really interesting." Um, so it's
[2:06:20] definitely a very interesting data
[2:06:21] structure people are excited for. What
[2:06:22] do you think is the applicability for
[2:06:24] your own programs after white box or
[2:06:26] other people's programs? Do you think it
[2:06:28] is a generally purpose or general
[2:06:29] purpose data structure for a large set
[2:06:32] or is it like where's the boundaries
[2:06:33] there
[2:06:34] >> uh of zars that
[2:06:35] >> yeah like what kind of things would make
[2:06:37] it not useful or where's the boundary
[2:06:39] >> so um I obviously showed that within um
[2:06:41] a single a single tree of uh types but
[2:06:46] having introduced the idea to the
[2:06:48] codebase they've they've popped up
[2:06:50] everywhere um because there's just this
[2:06:55] uh this this uh effectively static
[2:07:00] header size and then um all of the
[2:07:05] blocks being pushed later into an arena.
[2:07:08] Uh they're very easy to um
[2:07:13] you can you can have the header on the
[2:07:15] stack uh and then have some scratch
[2:07:18] point to an arena push types push uh
[2:07:22] push strings push um arrays. it's ours
[2:07:27] of any length. Uh and then once you're
[2:07:30] done with the and you can in the the
[2:07:33] important thing here is that you can
[2:07:34] interle pushing onto multiple virtual
[2:07:36] arrays at once uh and then just pop back
[2:07:39] at the end. Um and they're
[2:07:42] uh you know it's as if they never
[2:07:44] existed.
[2:07:46] So keep keeping that that main advantage
[2:07:48] of arenas and
[2:07:51] um yeah I'll I'll the pitfalls of them
[2:07:56] one of them is the same as any other
[2:08:02] actually before that so one way of
[2:08:04] thinking about them is as a
[2:08:05] generalization of regular slices where a
[2:08:08] slice would be um number and pointer and
[2:08:10] this is just number and pointer pointer
[2:08:12] pointer pointer pointer um but the the
[2:08:15] pitfall
[2:08:16] is um true with kind of any chunked
[2:08:21] um
[2:08:23] chunked data structure where you can
[2:08:28] if you if you interle
[2:08:31] uh pushing some stuff and then you take
[2:08:32] another
[2:08:34] um another scratch point on your arena
[2:08:38] push more things you may add another
[2:08:42] chunk onto your ZAR or other chunk
[2:08:45] chunked um array like thing. Um and then
[2:08:48] when you pop back, you now have a ZAR in
[2:08:53] a partially valid state. So you've got
[2:08:55] your first chunks and your last chunks
[2:08:57] and and so accessing this will happen
[2:09:00] will will occur legally and accessing
[2:09:02] that um might not occur every time. And
[2:09:04] so you can you can hit that. So that
[2:09:06] that is a case to be careful of. But I
[2:09:08] think that is as far as I can see just
[2:09:11] um unavoidable in the case of trying to
[2:09:15] have stable chunk arrays of any sort. Um
[2:09:20] and and once you know to watch out for
[2:09:22] it, you can you can do things like I
[2:09:25] mean asan is an obvious example. You can
[2:09:27] poison the end of your arena and so
[2:09:29] accessing it is is immediately
[2:09:31] immediately shows up loudly. Um and then
[2:09:35] the the other cost to them is
[2:09:40] you have you know 20 pointers or however
[2:09:43] many pointers. Uh
[2:09:46] now you can the nice thing about that is
[2:09:49] that you can you know you only have to
[2:09:51] add if you add three more pointers
[2:09:53] you've octupled the size of your array.
[2:09:57] And you know like it's it's pretty easy
[2:09:58] to convince yourself that that is
[2:10:00] sufficient for uses. Um but if you end
[2:10:04] up with um a really large number of
[2:10:08] otherwise small data structures
[2:10:11] that refer to a typically small number
[2:10:14] of things but occasionally it's large
[2:10:16] then um you end up with like quite a
[2:10:19] large overhead of um this these pointers
[2:10:23] and
[2:10:25] yeah I mean you can use one of the other
[2:10:27] options in those cases you could like
[2:10:29] move back to the general case. I I think
[2:10:31] the most general thing is possibly the
[2:10:33] tree case. Um
[2:10:36] but you know there's various options
[2:10:38] that we went over that you could think
[2:10:40] through for your problem.
[2:10:43] >> Yes.
[2:10:44] >> So they kind of exist in reference in a
[2:10:48] blog post from like the the machinery
[2:10:51] guys. Rest in peace. Uh
[2:10:53] >> well they're gone now. So
[2:10:55] >> yeah, but I they don't end up going with
[2:10:58] them. like they kind of think about them
[2:10:59] and say, "Nah, we'll do something else."
[2:11:01] >> Yeah, I think I know the the article
[2:11:03] you're you're referencing there. Yeah,
[2:11:04] >> I don't think they realized that the
[2:11:06] number of pointers you need to keep is
[2:11:08] bounded.
[2:11:09] >> Yeah, I I think that was was an
[2:11:11] important thing. Yeah, the like what
[2:11:13] what made it worth like moving because
[2:11:16] if you have to have that extra pointer
[2:11:18] in direction, it's like I don't know is
[2:11:20] that really worth it? But the fact that
[2:11:22] it's it's that relatively small bound
[2:11:25] makes it quite convenient to keep you
[2:11:27] know you have this single array
[2:11:29] structure all at once.
[2:11:30] >> Yeah, they suggest keeping the pointers
[2:11:32] in a dynamic array and I don't think you
[2:11:34] would suggest that if you realize, oh
[2:11:35] wait, I only need this many.
[2:11:36] >> Yeah.
[2:11:36] >> Yeah. The thing I I was thinking of is
[2:11:39] doing that.
[2:11:40] >> Cool.
[2:11:41] >> So it is normal.
[2:11:48] >> Sam, how are we doing on time? Do we
[2:11:49] want to cut off at a specific time?
[2:11:51] >> All right. All right. Um, so one of the
[2:11:54] things I learned a lot from your talk or
[2:11:56] when I originally saw it especially was
[2:11:58] uh
[2:11:58] >> keep asking.
[2:11:59] >> Yeah. This idea of of parameter space
[2:12:01] and especially how you deal with holes,
[2:12:03] right? So often times when I'm trying to
[2:12:05] make a system uh I really want that
[2:12:07] system to be clean and and like kind of
[2:12:08] perfect in a way, right? So when I come
[2:12:10] across a hole where it's like this
[2:12:11] combination of parameters that's not
[2:12:13] defined, that seems weird. I must be
[2:12:14] doing something wrong. Um
[2:12:17] yeah I guess how did you come across
[2:12:19] that concept? How did so you you
[2:12:21] essentially advocate for like the holes
[2:12:23] can be fine actually right so you do
[2:12:24] this with your your 10 byt or yeah 10
[2:12:27] byt float uh and even though it
[2:12:29] technically is a slightly unbalanced
[2:12:31] parameter tree uh it's more useful to
[2:12:34] have a consistent parameter space that
[2:12:36] you can talk about stuff with with a
[2:12:38] hole or an extra thing on top.
[2:12:40] >> Yes. Um,
[2:12:46] now I guess the reason
[2:12:50] that I think that
[2:12:52] um is because I was already on team
[2:12:54] mega.
[2:12:56] Um, and then
[2:12:59] like I listened to some array
[2:13:01] programming people talk about what
[2:13:02] they're doing with their their different
[2:13:04] dimensions and um the fact that all of
[2:13:07] their arrays are rectangular and they
[2:13:08] talk about having holes but how it
[2:13:10] doesn't matter. um like the the the the
[2:13:12] the real benefit comes from having this
[2:13:15] simple and consistent um
[2:13:18] this simple and consistent mapping for
[2:13:20] things and simple and consistent
[2:13:21] identity. Uh and then
[2:13:24] the connection between those I I know I
[2:13:27] I mentioned all these different things
[2:13:28] and it may have seem seemed somewhat
[2:13:31] random to bring up array programming and
[2:13:32] functional programming. Um but the the
[2:13:36] notion of the product type on once
[2:13:37] you're familiar with the fact that a
[2:13:39] product type or construct is a product
[2:13:41] type and that's just the fact that it's
[2:13:43] referencing effectively these different
[2:13:44] dimensions then that kind of clicked in
[2:13:47] make making the link between these two
[2:13:49] things
[2:13:52] take another audience question
[2:13:55] >> how important is the rule that the first
[2:13:57] element of your has to be two like
[2:14:00] because I know that that means like it's
[2:14:02] going to be a power of two yes So what h
[2:14:04] if you have a power of two minus one as
[2:14:06] like your size, how bad is that? Like
[2:14:07] does that mess up like your entire like
[2:14:09] get function or something?
[2:14:11] >> So how important is it that it's a power
[2:14:13] of two or how important is it that it's
[2:14:15] exactly two?
[2:14:15] >> Size of the entire array is always um
[2:14:18] because I I saw like your first element
[2:14:20] is always going to be two elements
[2:14:21] instead of being one two four you have
[2:14:23] two two four. I know that results into a
[2:14:25] side an array size of like power of two
[2:14:27] instead of like power two minus one.
[2:14:29] >> And how important is that? Okay. So, um
[2:14:32] they don't have to be just two. That
[2:14:35] that was just for the um to keep it
[2:14:37] small on the slide. Uh it
[2:14:40] the way I have my implementation is the
[2:14:44] the first is always a power of two. Um
[2:14:48] so
[2:14:50] commonly
[2:14:52] like a shift of six or a shift of eight.
[2:14:54] So 64 or 256 elements. Um now on the
[2:14:59] context of or the the on the question of
[2:15:02] um nonp power of two base sizes
[2:15:06] um so so I part of the answer to that is
[2:15:09] like that's um
[2:15:13] is
[2:15:16] uh you you get some of the benefit of
[2:15:18] this uh non-power to thing by
[2:15:21] distinguishing between
[2:15:24] the size of the element as just
[2:15:26] an any size that doesn't have to be a
[2:15:28] power of two, anything. Um, and the um
[2:15:31] number of elements being a power of two
[2:15:33] because it means that you can treat
[2:15:35] indices as powers of two um but not um
[2:15:41] like it doesn't have to be a power of
[2:15:42] two offset into the into the array. The
[2:15:48] um question no
[2:15:51] there's a
[2:15:56] the the problem is um I think
[2:15:59] determining which trunk things are in
[2:16:02] and if you have nonpowers of two it
[2:16:04] becomes you have to do like a log
[2:16:06] operator or or some other trick that
[2:16:09] probably I'm actually I'm pretty sure
[2:16:11] there's there are tricks that exist in
[2:16:12] hacker light for like integer logs um so
[2:16:16] you can probably you could probably use
[2:16:17] one of those if you can find one um
[2:16:20] computers that like doing things with
[2:16:22] powers of you. So, uh,
[2:16:27] >> because I had like some I was thinking
[2:16:30] about like binary search and stuff and I
[2:16:31] was
[2:16:35] >> um
[2:16:37] I So I
[2:16:39] Okay, another downside with with these
[2:16:42] uh data structures is that they're
[2:16:43] slightly awkward to take sub slices of.
[2:16:46] Um,
[2:16:48] and so the the kind of naive option
[2:16:52] there is to do just like a pointer to
[2:16:54] the to the thing or just copy all of the
[2:16:57] the size and the um and the pointers and
[2:17:00] then have a begin and end offset. Uh I I
[2:17:04] did
[2:17:05] um I did work out the implementation
[2:17:09] of a
[2:17:12] kind of general sliced version of this
[2:17:14] where the the the first chunk is
[2:17:18] variably sized. Um and as far as I can
[2:17:22] tell that would work and it it works in
[2:17:24] part because um you have to treat zero
[2:17:28] as a special case anyway. Um
[2:17:33] but in practice I haven't used them once
[2:17:35] in since implementing it. Um
[2:17:39] your mileage may vary.
[2:17:42] >> Um one of the quotes in the talk that I
[2:17:44] felt like you should pause and wait for
[2:17:46] applause. Um you said something to the
[2:17:48] effect of bite first thinking wins over
[2:17:49] type based thinking. Um, and I believe
[2:17:51] this is in the context of uh what I
[2:17:53] would try to describe as like C style
[2:17:55] generics, but then you also do this
[2:17:57] parameter space packing and then that
[2:18:00] makes the calling convention much better
[2:18:01] and and like all these things come
[2:18:03] together, right? Um, do you mind
[2:18:04] explaining like that quote a little bit
[2:18:06] more?
[2:18:10] Uh
[2:18:13] I guess I guess one one avenue you can
[2:18:16] go down with that is
[2:18:22] barring some complexities of the C
[2:18:24] memory model. Um
[2:18:28] the the bytes are an actual base
[2:18:30] reality. They're there and they have
[2:18:34] some bit pattern in them and you can
[2:18:36] interpret that bit bit pattern. uh in
[2:18:39] whatever way you'd like. Um the types
[2:18:43] are an artificial construct on top of
[2:18:46] that that helps us think about them and
[2:18:49] helps us catch silly mistakes. Um and
[2:18:52] while they're useful, they're not
[2:18:57] they're not the concrete thing that are
[2:18:58] there. And so if you can think about
[2:19:00] things like if you can think about
[2:19:01] what's actually there, then you have a a
[2:19:04] good chance of being able to work out
[2:19:05] something you can do with that.
[2:19:08] Do we have any more questions from the
[2:19:09] audience?
[2:19:11] I have a Yeah. Uh, let's go. Masha,
[2:19:14] >> it's not a real question. I'm sorry. So,
[2:19:17] the last the very last slide you had was
[2:19:19] marked as the third one,
[2:19:22] >> but it was also written that you had
[2:19:23] like 111. Is there a secret? And can we
[2:19:26] unlock that?
[2:19:31] >> Would you like to see the deleted
[2:19:32] scenes?
[2:19:33] >> We would like to see the deleted scenes.
[2:19:34] >> Okay.
[2:19:42] the these are slightly less structured.
[2:19:45] Um
[2:19:47] uh but I guess welcome to part five of
[2:19:49] bits of high level.
[2:19:51] Uh okay, first is
[2:19:57] thank you.
[2:20:00] Uh I actually lost count. however many
[2:20:02] parts this is. Um,
[2:20:06] again I mentioned before common thing
[2:20:07] you want to do bind some value in a
[2:20:11] lookup table. As a debugger we have to
[2:20:12] deal with fast fail codes. Um, and some
[2:20:16] of these are considered fatal, some of
[2:20:18] them are not. And um,
[2:20:22] the straightforward thing would just be
[2:20:24] to pack these in an array of bulls. And
[2:20:27] that would work. That would be fine. Um
[2:20:30] I in fact it's completely non-issue. Um
[2:20:34] however it's wasting 78 of the space and
[2:20:38] it hurts my soul and it's
[2:20:41] yeah um and there are like 76 of them or
[2:20:46] something depending on which Windows
[2:20:47] platform you run. Uh and
[2:20:50] the trick is realizing that all of the
[2:20:52] interesting ones happen under 63 and
[2:20:55] then you can pack rather than It's
[2:20:58] common to think of lookup tables as
[2:21:00] memory that you look at. Uh but you can
[2:21:02] also think of those as just values that
[2:21:05] you look at and you can kind of pack the
[2:21:07] value into uh a uh a 64-bit integer or
[2:21:12] however many bits you need. And then
[2:21:14] okay, so you've probably seen like
[2:21:16] single bit um bit packing.
[2:21:21] Um
[2:21:22] but there's no reason you have to stop
[2:21:25] at one. you can it's possible to pack uh
[2:21:29] you know any number of you know you have
[2:21:32] a fixed number of bits to play with. Um
[2:21:35] and given that you can scale how many
[2:21:38] different elements you have and how big
[2:21:39] each of those elements are within your
[2:21:41] like literal immediate value array
[2:21:45] thing. Um so if if we look at basic
[2:21:48] version we have um bool array of all of
[2:21:52] these different values you can um index
[2:21:55] into them and get the value out. That's
[2:21:57] it's pretty common. Uh and then we have
[2:22:00] the same but kind of shifted into this
[2:22:02] immediate mode world. Um and like this
[2:22:08] is if you haven't seen this before this
[2:22:09] probably looks unfamiliar. Um, but if
[2:22:12] you blur your eyes a little bit, it's
[2:22:14] quite similar to the array definition.
[2:22:17] Uh, you're shifting by the index into
[2:22:20] the array um multiplied by the number of
[2:22:23] bits each value in the array takes up.
[2:22:26] Uh, and then on the um on so that's
[2:22:29] that's creating the value, you're left
[2:22:31] shifting, and then on accessing the
[2:22:33] value, you right shift it so that those
[2:22:35] bits are the ones at the the bottom and
[2:22:37] then uh mask them off. Um and you can
[2:22:40] see that there's a relationship between
[2:22:42] the shift the number of bits uh and how
[2:22:45] you shift and how you mask.
[2:22:47] Um and then you can look at the
[2:22:51] um the disassembly for that. And
[2:22:55] like I said uh LA depending on exactly
[2:22:58] how how it's being used uh has slightly
[2:23:01] different encodings and so you end up
[2:23:03] with a slightly differently sized thing.
[2:23:04] Uh but you end up with four instructions
[2:23:07] that don't touch data memory. They're
[2:23:10] only touching instruction memory. Um and
[2:23:13] if you're thinking in terms of total
[2:23:14] memory, you end up with slightly less.
[2:23:17] Now again, it's one of those cases where
[2:23:19] it's like who cares?
[2:23:23] When am I going to use this? Um
[2:23:27] you end up with a similar total memory
[2:23:29] footprint. the the case that I've found
[2:23:35] is and and maybe it's just my own like
[2:23:39] personal mental disorder is um with
[2:23:44] um when you have a small array that gets
[2:23:49] you have lots of these small arrays and
[2:23:52] each individual one gets touched
[2:23:54] infrequently. So it won't be in cache
[2:23:56] but you end up touching a lot of them
[2:23:58] total. Um then it kind of becomes
[2:24:03] worth I don't know it if I do it this
[2:24:08] way it gives me peace of mind and it the
[2:24:10] it won't be the memory cache issue won't
[2:24:12] be an issue and I don't have to think
[2:24:14] about it. Um that way I you know it
[2:24:16] haunts my dreams even though it's seven
[2:24:19] bytes whatever.
[2:24:22] Um, and then the other use for this is
[2:24:27] um,
[2:24:30] uh, it's kind of a I think it's a John
[2:24:33] Blow something John Blow said at
[2:24:36] Handmade Con. Oh, sorry. Yeah, one of
[2:24:38] one of the early Handmade Cons um, about
[2:24:42] uh, one generally preferring
[2:24:45] arithmetic based code to like if
[2:24:48] condition based code.
[2:24:51] Uh, and if you have the ability to think
[2:24:54] of your data in terms of these little
[2:24:57] um, mini arrays, then you can you get to
[2:25:00] do this. And the the kind of
[2:25:03] furthest point that I think uh my my use
[2:25:07] of this has got to is um I have like
[2:25:12] these little teeny strcts with two two
[2:25:15] bit members and then I can pack two
[2:25:19] uh two of these strcts into an array of
[2:25:23] of eight bits and then I have an array
[2:25:25] of those like array of those bytes and
[2:25:28] then I have another array of those uh
[2:25:30] bytes. So this is accessing like the
[2:25:33] um it's using because it's a two element
[2:25:36] array it uses a bool as an index um and
[2:25:39] then you shift it by the index times
[2:25:43] whether or not you shift it by four and
[2:25:45] then um you add on the shift of whether
[2:25:47] you want the first element in the strct
[2:25:49] or the second element in the strct. Um
[2:25:51] and then um
[2:25:54] shift it by that much and mask off the
[2:25:57] couple of values. I guess it helps in
[2:26:00] this case that both elements of the
[2:26:02] struct are the same size.
[2:26:05] Uh
[2:26:07] what was this? Yeah, there was some kind
[2:26:10] of general
[2:26:12] recommendations around the little
[2:26:18] thinking about bit packing like does
[2:26:21] does it already if you just put the
[2:26:23] value in some bits does it already fit
[2:26:25] in those bits? If so, you're done. um
[2:26:28] does the minimum the maximum value minus
[2:26:30] the minimum value does that range fit in
[2:26:33] your bits? If so, you can shift it by
[2:26:34] the minimum value and then reintroduce
[2:26:36] the minimum value on the way out. Um you
[2:26:39] can think of it in term rather than
[2:26:40] think of it as a range you think of it
[2:26:42] as discrete values because it might be
[2:26:44] sparse. And then you can um
[2:26:48] you know if you have 255 different
[2:26:51] values regardless of how different those
[2:26:53] values are, regardless of what type they
[2:26:55] are, you can refer to any of them uni
[2:26:58] uniquely with eight bits. Um
[2:27:04] and if
[2:27:07] you know so the then the simple version
[2:27:09] is you'd put that in array but there
[2:27:11] might be some pattern that you can
[2:27:12] exploit so that you just get the value
[2:27:13] out immediately without having to touch
[2:27:14] memory or you do the somewhat
[2:27:20] uh
[2:27:21] yeah you do you do the the bitwise
[2:27:24] immediate array version thing or you do
[2:27:26] some more like real compression style
[2:27:28] thing with
[2:27:30] um
[2:27:31] what is it
[2:27:34] arithmetic trees I forget the precise
[2:27:36] terminology
[2:27:37] if you want to know more about these
[2:27:39] things uh hackers alike is quite well
[2:27:41] known hackme is a PDF that goes around
[2:27:44] occasionally from like
[2:27:48] at least 50 years ago but I forget
[2:27:50] exactly when um it's a little bit more
[2:27:52] kind of sign it's about solving the
[2:27:54] scientific problems rather than the
[2:27:56] direct
[2:27:58] um kind
[2:28:00] more immediate use of of bitwise
[2:28:02] arithmetic that hacker light has and
[2:28:04] then there's an HTML with the URL with a
[2:28:08] couple more uh things that uh probably
[2:28:11] also within one of the other ones.
[2:28:16] Uh
[2:28:19] we Okay. Um this this is like one of the
[2:28:24] earlier slides, but this was blacked out
[2:28:27] before.
[2:28:29] Um
[2:28:31] it's just a a nice simplification that
[2:28:34] if you have flags, you can um you don't
[2:28:38] have to have a separate array, sorry, a
[2:28:40] separate enum for the non like
[2:28:42] non-shifted version of that flag to
[2:28:44] index into them. And then you can um get
[2:28:48] the value both set and get the value
[2:28:51] like directly in a in a way that is
[2:28:55] obvious how it relates to the the
[2:28:56] original flag. And like I said, the
[2:29:00] Clang
[2:29:01] compiler will let you do this at compile
[2:29:04] time. The
[2:29:06] um MSVC compiler will not, which is a
[2:29:10] shame. Um but this is an option if if
[2:29:16] you want to do it on MSBC. Um another
[2:29:19] option is just to have the the
[2:29:21] non-shifted values uh beforehand for the
[2:29:24] for when you're setting the compile time
[2:29:26] uh sorry when you're setting the uh
[2:29:30] the
[2:29:32] flag string index. And then like hidden
[2:29:36] in here is another use of this
[2:29:40] um otherwise ridiculous array access. Um
[2:29:44] so each nibble in that each digit is
[2:29:50] um
[2:29:52] uh is the bit the highest bit within a
[2:29:57] nibble. And then you can uh it's it's
[2:30:00] it's
[2:30:03] the other case where you would use this
[2:30:05] slightly ridiculous array indexing uh is
[2:30:08] in compile time stuff where you can't
[2:30:10] access arrays like actual arrays.
[2:30:13] Uh and if you if you want to walk
[2:30:15] through that I'm I'm happy to go through
[2:30:17] that.
[2:30:19] And then a little trick is um like I
[2:30:25] said and as you knew most significant
[2:30:28] bit is undefined when when you get a
[2:30:32] value of zero um it's there are
[2:30:35] reasonable ways that you can wrap that
[2:30:37] so that you get minus one I think
[2:30:38] someone mentioned uh as the end result
[2:30:41] um but typically I just have it as the
[2:30:45] the bare version um
[2:30:49] the
[2:30:51] what you quite often end up in a
[2:30:53] situation like in my earlier code where
[2:30:58] the first thing and the second thing
[2:30:59] like the zero thing and the first thing
[2:31:03] are handled in the same way. Uh and if
[2:31:06] that is the case then you can do this
[2:31:08] like x or one trick and so if if it was
[2:31:11] zero uh then it becomes one and then the
[2:31:15] most significant bit is zero. If it was
[2:31:18] one already, then it stays the same. Um,
[2:31:20] and if it was a higher bit was set, then
[2:31:24] this is a no-up and you just still get
[2:31:25] the higher bit set.
[2:31:28] I think that is all of the deleted
[2:31:31] scenes.
[2:31:33] Yeah, there you go. Another random.
[2:31:40] Do you have a limit of how many
[2:31:41] questions you want?
[2:31:45] Um, this is an easy one actually. Uh do
[2:31:47] you think using something like Arc would
[2:31:49] go a long way or help you uh in any way?
[2:31:51] I know I believe that uh Whitebox is
[2:31:53] currently using deMue. Uh but I'm
[2:31:57] curious.
[2:31:59] >> Um I specifically the immediate mode UI
[2:32:03] arc arc UI
[2:32:05] >> that arc of the many arcs. Yeah. So, I
[2:32:08] caught some of that uh on stream, but I
[2:32:10] was not here because um uh I have a
[2:32:14] problem with my cash eviction strategy
[2:32:16] in my head. And so, if I'd come to the
[2:32:18] talks earlier, then I wouldn't have been
[2:32:20] able to remember anything for these uh
[2:32:21] for my own. So, I I have glimpsed it but
[2:32:25] not seen seen the details. Um
[2:32:29] it's it's very possible. I'm I'm kind of
[2:32:31] using Darham Guey in a way that it's not
[2:32:33] really intended to be used. Uh and it
[2:32:35] causes some friction. uh and it at some
[2:32:38] point does need a U new UI.
[2:32:40] >> Are there particular like wish list
[2:32:42] things you want from DMUI or if you know
[2:32:44] if you were to use another framework you
[2:32:45] would like something that does X?
[2:32:48] >> Um
[2:32:51] part of the problem is that it's not set
[2:32:57] up directly for exactly how I want to do
[2:33:00] profiler and debugger like views. um
[2:33:03] which you know would be unreasonable to
[2:33:05] ask of someone's UI uh which kind of
[2:33:08] implies that we should probably build
[2:33:10] our own but that's a that's a sort of
[2:33:12] rabbit hole. Um
[2:33:20] yeah I think I think a lot of the issues
[2:33:21] come around with
[2:33:23] when we want to build custom UI
[2:33:25] features.
[2:33:28] >> Are there any more audience questions?
[2:33:32] This might be a bit of a big question,
[2:33:34] but we were talking earlier about hashts
[2:33:37] and how you had a sort of new way of
[2:33:40] doing that on top of arenas. Uh would
[2:33:44] you want to expand a bit on that?
[2:33:48] >> This was a discussion we're having
[2:33:49] outside of the outside of this talk.
[2:33:51] Yeah.
[2:33:54] Um
[2:33:57] so
[2:34:01] okay hashts
[2:34:04] you have
[2:34:06] by the way if anyone hasn't implement a
[2:34:07] hasht I would recommend going and doing
[2:34:09] it not necessarily for use just but to
[2:34:11] understand the different things that are
[2:34:13] going on there it really helps um take
[2:34:15] something that is consider you would
[2:34:17] normally consider magic because of a lot
[2:34:20] of the hash magic that's going on and
[2:34:21] turning that into something that's
[2:34:22] concrete
[2:34:23] Um but specifically to the question
[2:34:26] um
[2:34:29] okay so first thought is many of our
[2:34:33] uses of
[2:34:35] um hashmaps are as acceleration
[2:34:38] structures kind of pointing into already
[2:34:42] stable places and so the
[2:34:45] um I'm far I'm far less concerned with
[2:34:49] having acceleration structures be stable
[2:34:50] than having the kind of quotequote real
[2:34:52] data uh be stable,
[2:34:56] but that's not all cases. Uh and you do
[2:34:59] want,
[2:35:00] as I said, it's nice having stable
[2:35:02] things. So, you have you have a few
[2:35:05] options. Um,
[2:35:08] and as I mentioned to you before, to my
[2:35:10] shame, many of the hash or the h the
[2:35:13] general hash table that we use within
[2:35:15] whitebox is is still uh using reallock
[2:35:18] because
[2:35:20] um I did it ages ago. Um long before
[2:35:24] coming
[2:35:26] coming to the aesthetic sensibilities
[2:35:27] that I have now. Uh and
[2:35:31] um basically it's just never been a
[2:35:33] priority to change.
[2:35:35] Okay, I'll I'll stop deferring and
[2:35:36] answer the actual question. The um
[2:35:42] so we have the
[2:35:46] when when you implement a hash table,
[2:35:48] you have your
[2:35:50] um
[2:35:53] you hash your key and then you end up
[2:35:55] with a thing that you turn into an index
[2:35:57] into some other array. Uh and then from
[2:36:00] that you either directly have the keys
[2:36:02] and values in there or you have a way of
[2:36:04] determining what the keys and values
[2:36:05] are. Um,
[2:36:08] and
[2:36:10] I guess I guess the first way of
[2:36:14] explaining how you could keep that
[2:36:16] stable would just be to slap it onto a
[2:36:18] ZAR. And um, rather than the index being
[2:36:22] a direct kind of um, modulo offset into
[2:36:27] that, it's a it's kind of like a
[2:36:30] virtualized, it's just the regular
[2:36:31] index, but into the ZAR. Um
[2:36:36] the
[2:36:40] uh the the difficulty then comes from
[2:36:44] when you grow the array, you need to
[2:36:45] rehash things.
[2:36:47] Um
[2:36:49] and but okay, as we've all learned,
[2:36:54] right,
[2:36:56] powers of two are loved by computers and
[2:36:59] so they're loved by you. Yes.
[2:37:02] Um so we have our our all of our hash
[2:37:06] blocks are powers of two. Um which means
[2:37:10] that an index into into that is using an
[2:37:13] exact number of bits. And so when when
[2:37:17] we grow our
[2:37:19] hash table and by what power do we grow
[2:37:21] our hash table? We double it. Yes. Um
[2:37:25] excuse me.
[2:37:27] uh when we double the size of our hash
[2:37:29] table, we now have effectively one extra
[2:37:32] bit at the beginning of our index. And
[2:37:35] so the possible solution that we were
[2:37:39] discussing for a linear probing hasht is
[2:37:43] that you can scan from the beginning of
[2:37:45] your block. Um and then each time you
[2:37:47] hit something, you know whether or not
[2:37:50] it there's only two options. It's either
[2:37:52] going to stay stay where it is asterisk
[2:37:56] or go to the um the equivalent like the
[2:38:01] same offset but in the other second
[2:38:02] chunk of the the next chunk across. Um
[2:38:07] okay that asterisk
[2:38:09] is to do with collisions as it always is
[2:38:11] with hash tables. Um, and
[2:38:16] yeah, I mean there's there's some
[2:38:17] implementation of details you work out
[2:38:19] there that if having not implemented it,
[2:38:22] it seems like you could um effectively
[2:38:26] remove an element each time you move it
[2:38:28] and then everything else would shift
[2:38:30] back into place. And if you removed it,
[2:38:31] you don't move forward. You just look at
[2:38:33] the same place again until you've gone
[2:38:34] all the way through. Um
[2:38:37] there might be a slightly smarter way of
[2:38:40] doing it that skips some of that work
[2:38:42] but um I don't have any confident
[2:38:45] statements on that.
[2:38:47] Uh
[2:38:53] and then the other way is to do you
[2:38:57] mentioned with the like hash array map
[2:38:58] tree where then all of the nodes are you
[2:39:03] have a bunch of nodes but where where
[2:39:04] your base data is stable and then
[2:39:06] actually your intermediate nodes are
[2:39:08] stable as well um but you
[2:39:11] um you have your login accesses into
[2:39:13] into the various endpoints and I think
[2:39:15] that's how like C++ ++ is
[2:39:19] ordered map or un unordered map works.
[2:39:22] Um,
[2:39:23] which I don't know why I know because
[2:39:26] well I I don't have to deal with it. So
[2:39:29] yeah um
[2:39:50] Yeah. Um the other the other thing you
[2:39:53] could do is
[2:39:56] um
[2:39:59] yeah so you have more options that you
[2:40:01] can if you keep your you don't have to
[2:40:04] have the same structure for your uh your
[2:40:08] slots your bucket pointers as your
[2:40:10] actual key value data.
[2:40:12] Um, so you could have your key value
[2:40:15] data in what whatever
[2:40:18] uh storage you like. Like if you don't
[2:40:21] need to iterate it, you can just put it
[2:40:22] wherever in the arena. Um, or you can do
[2:40:25] like trunking lists or one of those
[2:40:27] other um
[2:40:31] one of those other collection
[2:40:33] structures. Uh, and then your slots can
[2:40:37] go
[2:40:39] uh you can either just leak the old ones
[2:40:41] each time and double or you can have
[2:40:43] like power of two pools within your
[2:40:45] arena and free it from one that goes on
[2:40:48] the free list for like size eight and
[2:40:50] then you have a new one of size 16.
[2:40:53] Well, you do that after copying the
[2:40:55] things over after rehashing the things
[2:40:57] over. Um,
[2:41:03] >> yeah, I think there were some other
[2:41:04] options, but they have slipped my mind.
[2:41:08] All right, this will be my last
[2:41:09] question. Um, how much of this talk do
[2:41:12] you think applies to C or C++ and how
[2:41:15] much of it applies to all languages? In
[2:41:17] other words, can I tell my JavaScript
[2:41:18] friend that he should watch this talk
[2:41:20] and follow the the advice?
[2:41:24] So, first of all, um
[2:41:31] I mean the the slightly glib answer is
[2:41:33] that
[2:41:35] if you're doing things like the
[2:41:38] um
[2:41:40] treating your value as a very small like
[2:41:44] 32 element set or other things like
[2:41:48] that, then you you do still get that win
[2:41:50] of it becoming one operation.
[2:41:53] rather than a loop of operations or some
[2:41:56] other more complex system of operations.
[2:41:58] Um
[2:42:00] and
[2:42:05] but but yeah, so the other side of it is
[2:42:07] like
[2:42:09] C, C++, other systems programming
[2:42:11] languages.
[2:42:13] um you're running on an actual computer
[2:42:16] and they have this these instructions
[2:42:18] baked in as like fundamental operations.
[2:42:23] Um, and while
[2:42:26] I think most scripting languages have
[2:42:29] them, um, you're kind of still going
[2:42:33] through all of the indirection of any
[2:42:35] other operator and a lot of the
[2:42:39] you know,
[2:42:40] like previously we kind of compared the
[2:42:43] latency of a an imole to an AD and I'm
[2:42:48] pretty sure that the the speed
[2:42:50] difference between those two
[2:42:51] instructions is completely dominated by
[2:42:53] the the VM on other languages. Although
[2:42:56] I guess having said that like V8 is
[2:42:59] pretty impressive at turning turning
[2:43:01] things into machine code if you can
[2:43:03] structure your data in a way that it can
[2:43:06] know to jip the machine code and not do
[2:43:08] the generic VM thing.
[2:43:10] >> Yeah, I imagine there's still quite a
[2:43:11] bit of compile time uh analysis and
[2:43:14] optimizations what can that can apply.
[2:43:16] But there's I don't know, maybe this is
[2:43:19] just because I don't really live in that
[2:43:21] world, but there's a lot of
[2:43:24] blackbox magic in the V8 compiler. Um,
[2:43:28] and I don't know I know there's magic in
[2:43:30] regular compilers kind of. Uh, but
[2:43:34] the kinds of changes that you're going
[2:43:37] to get are are kind of
[2:43:41] Oh, no. I'm I'm going to say they're
[2:43:42] more predictable, but that's like that's
[2:43:43] going to open up a whole can of worms.
[2:43:45] Listen, that's a bad idea.
[2:43:49] >> I think that will we'll call it there.
[2:43:51] Thank you so much. Another round of
[2:43:52] applause for Andrew Reese.