Aaron Hsu

You can't say C needs to add anything because C already has everything. But it gives you access to all sorts of algorithms, right? You can do a binary search to find that stuff. You can do a hash table lookup to find that stuff. You can do a quadratic lookup on that stuff. There's all sorts of ways of finding that data.

Conor

Welcome to ADSP The Podcast, episode 196, recorded on August 21st, 2024. My name is Connor, and today I interview Aaron Shu on site at the Eagle Pub on the campus of the University of Cambridge. We chat about algorithms in APL as well as their implementations. This is uh pretty epic. We are here in the historic Eagle Pub, thanks to the recommendation of both Ben Dean and Tristan Brindle to uh previous guests on ADSP. And I'm here with Aaron Shu, the first time guest on ADSP. I believe you were episode 18. I don't actually know what number guest you were on a ray cast. So we will link at the top of the show notes for folks that can't get enough of Aaron Shu after this conversation. I'll let you introduce yourself after a brief introduction from me, most famous for being the author or creator of the CodeDFunds compiler, which is a uh APL that is both run on the GPU and is, I believe, compiled on the GPU. Which is can't be said about many languages that can be compiled, both run and compiled on the GPU. Yeah, nope. Uh and uh yeah, designed to self-host itself is the idea. And you work at Dialogue Limited, you have for I think the last few years, um since basically your dissertation or completing your PhD. They fund the compiler research, so and I'm sure do you want to add anything? You're a uh man with uh strong opinions, strongly held of many hobbies and passions. We were just discussing that uh it's not so much passions that both of us have, but obsessions, you know.

Aaron Hsu

They don't overlap a lot. I I like to do a deep dive, and I am I'm quick to change an opinion, provided that you provide evidence that exceeds the evidence and research that I've done.

Conor

And uh like that's the problem there, folks, is that he has done an immense amount of research himself, so the the amount that you have to provide is is not trivial. What are the things that we and so I guess I should also mention we for those that don't know where the Eagle pub is and why it's historic, we are on uh the Cambridge, University of Cambridge campus. This is where I believe DNA. I think that's that's what the sign said. It'll be in the show notes, but also more interesting to me, this is a pub that Alan Turing, the father of computing, frequented uh as he went to King's College, one of the colleges associated with the University of Cambridge. Uh potentially were sitting at a table that Mr. Turing himself sat at. I mean, it's it's possible. It's possible. Yeah. I mean, it was over half a century ago.

Aaron Hsu

Inhabiting the overall same spatial geometry.

Conor

Yeah. If it wasn't the same table, you know, at least we are frequenting the space that he frequented in decades past. Uh we are here at Iverson College. Probably no one that's listening to this podcast that doesn't listen to a raycast as well knows what that is. It's a week-long get-together. You yourself have been to, I think, a couple before. I think two before, yeah. So this is your third one. And it's a collection of about 25, 30 folks. I'm not sure how many it was in years past. It's about that. Yeah about the same.

Aaron Hsu

20 to 30 is a, I think, a pretty typical number.

Conor

And some other folks, not attending this time, but attended in the past. The infamous Arthur Whitney behind the K's and Shackti. Uh who else has attended that um Roger Huey, I think, attended, who is the main implementer of the J language, for those that have heard of that. So it's a uh what would you say, an uh congregating of like-minded folks to share ideas while they're still working on their own personal work. And it I think it's uh I've heard it referred to as like an not this specifically, but this kind of meeting as like an unconference. It's a conference without a schedule.

Aaron Hsu

I think it's the it's in the tr the tradition of classic scholastic colleges of a meeting of shared minds to pursue the you know furtherment of ideas and knowledge and share experiences and things like that. I think I think that's sort of the the appeal in general.

Conor

How is this uh addition compared to years past? Because I think the last one was before the pandemic, so it's been a few years.

Aaron Hsu

Uh so uh without a doubt, the crowd is younger, but also way more eclectic. So there are many, many different backgrounds compared to in past colleges, where the past colleges had usually a stronger, more intense representation of senior uh people in the array programming field, whereas uh this college now has uh a much broader selection of people who have a lot of passion and varying uh degrees of experience in in the array programming field.

Conor

So has that changed the vibe or the conversations that have been happening? Sometimes, sometimes.

Aaron Hsu

Sometimes one thing we do is we can we we I think we are a lot more active and broad in our topics that we can cover right now. Uh you know, we have a lot more new things that are being discussed instead of like really precise refinements on things that we all know quite well. Yes, yeah. So there's a lot of new seeding of ideas to play with.

Conor

Yeah, I think probably in years past you didn't have creators of brand new, never heard about before array languages by some of the attendees.

Aaron Hsu

Brand new languages sweeping the nation.

Conor

Yeah, yeah. We're referring to the Weewa language uh created by Kai Schmidt. He's here, he gave a presentation on Monday. I think he there was a lot of I won't say dropped jaws, but uh definitely Admiration Yeah, burrowed frows and uh some interesting design design decisions made in that language. But that is a topic for another day.

Aaron Hsu

Yeah. Something I might want to mention, given that this is not necessarily an array community, other people outside of the array community might know my background as a scheme developer back in the day, and I was on uh I was one of the members of the small working group for the standardization of the R6RS. R7RS uh scheme standard. So like as far as laying out some more history, like if if you know, if they don't know array languages, they might know Lisps. They might know scheme or Lisps or something like that.

Conor

Yeah, that is uh I mean Alex Stepanov, the father of the standard template library and algorithms and C, was famously also a scheme developer for I think like uh I don't know if it was a decade, but he had some exploration of ideas uh that he explored in a couple different languages. Java was one of them, Ada was another, and I think he had a scheme as well, and actually he had like Notes on Programming, which was like an 88-page document where his first implementation of a reduction was in scheme, but he had a little comment that said reduce is taken from APL. And so there's actually a kind of a very faint dotted line between APL and C. Inner product, IOTA, I think adjacent difference even was taken from the name was taken from the kind of uh N-wise reduction in APL. So a couple a very faint line, but IOTA definitely comes from APL. And and zero and one Booleans also come from APL. Is that in C though? Oh, I guess the implicit conversions.

Aaron Hsu

Yeah, implicit conversions over.

Conor

Yes. There's many languages, to many people's chagrin, that have that.

Aaron Hsu

But it was famously Knuth's favorite feature from APL. So Really? Yeah. He he writes about it in his um uh Art of Computer Programming. His favorite, he calls them the Iverson Booleans or something like that. Really? And it was taken from APL and he he he likes to use them a lot.

Conor

I I love it's one of the things that I at times take for granted in APL. A lot of times I forget about the importance of rank polymorphism and Booleans as zero and one, a subset of the integer space, because it leads to like you can extend Boolean operations to work on the full integer range at a lot of times, which I believe APL does that, like in the case where you have and an or the extended integers is L CM and G C D.

Aaron Hsu

And it is also extended in a tolerant form to floating points as well. I have had uh nightmares trying to uh ensure compatible implementations of that. But yes.

Conor

You're telling me that there's a G C D implementation of those primitives for floating points. Yep.

Aaron Hsu

Uh how? What? Yes. Yes. It's um you have to you have to do it. Is it a different algorithm entirely? Or it's the same, it's the same basic algorithm. You do um the the the Chinese remainder theorem type stuff. It's the same basic G C D type things, but you have to you have to fac uh there's some kind of factorization on the floats to normalize them, or something that you have to do uh that gets into some kind of standard form that you then can.

Conor

I mean immediately you it's I would think there has to be some kind of discretization, otherwise you could have an infinite number of answers, no?

Aaron Hsu

Well, so that's where uh quad CT tolerant comparison comes in. So normally, for most cases, if you want a useful result on this, you you compare for equivalency across a range, not on exact bitwise equality over floats. So you have to do a soft equality uh checking, and then you execute the algorithm as you typically would, and it follows the same basic mathematical results, um the simple ones, and and you you just apply it to floats. It's a it's a contentious feature.

Conor

Yeah, interesting. I've never even in my life considered GCD on floating point. It's uh neither have many other people. Well, maybe maybe we should stay on the topic of I don't know, what do you call them, fancy? Maybe uh esoteric algorithms, seeing as this is the ADSP algorithms.

Aaron Hsu

What does ADSP stand for? Sorry.

Conor

It's the acronym taken from the Nicholas Verth book, algorithms plus data structures equals programs. Of course, of course. One time on an episode, uh someone mentioned, oh, like ADSP, it's a book, and I was like, no, it's a podcast. And then they were like, no, like you bait you took your name from the book, and I was like, oh yeah, how did I it was it was uh it was like 160 episodes in. I'd forgotten where we stole the name from.

Aaron Hsu

You've lost your roots. Yeah, you're no longer connected.

Conor

It is a part of the the new 2.0 version of this podcast, though. We're trying to bring back more algorithms and data structures conversation. So maybe maybe we'll record for an hour. We we have a topic lined up, but maybe we'll save that for the last 30 minutes of this conversation. Let's talk about algorithms. So, what are more algorithms either that you really like that exist in APL that you rely on all the time, or maybe staying in this like fancy space that I would have never guessed that GCD works on floating point. Are there other sort of esoteric things that are less useful or actually useful that you know you can reach for in APL that you don't have, you know, that C should consider adding to its you know, algorithm header?

Aaron Hsu

You know, I think I think you can't say C needs to add anything because C already has everything. And so like you can't not yet, we don't have reflection. I don't know. If I if I know some C programs, somebody's doing binary reflection on their own executables and getting data out like that. Like you can do it, you just have to be crazy.

Conor

You can do anything, that's true. It's it's not a language feature yet.

Aaron Hsu

When you work in these languages, the the just difference between a language feature and uh just some kind of hacker doing something on the bot bit level is it gets it gets pretty thin. You know? Uh you know, what's the difference between a C instruction and an assembly inline block with intrinsics? I you know, I don't know. Uh so the the but as far as algorithms, I think I actually I I I tend to have grown into preferring to avoid having to think about algorithms too much by shifting the abstraction just a little bit up at your base layer to worrying more about the overall type of uh engagement. So maybe a little bit higher level where you're specifying I want to do something that's within a family of algorithms, and then allowing your implementation of that to select the best algorithm out of that, and that maybe giving you more access to algorithms without having to be as aware of all the different varieties of algorithms that are out there as a usability case. I kind of like that, but but within the general computing sphere, uh C I think is less guilty of this than others, but still guilty. I think alternative algorithms that do not require pointer chasing. That would be the there are many ways in which you can work with flat data, encoded data, uh, you know, representations in a another a slightly richer mathematical domain like linear algebra or matrices or numerical spaces. Something in that space, instead of just building a set of abstract data types that operate over pointers, I I would encourage people to like play with not having to rely go to the pointer as your core way of connecting data together.

Conor

Well, so interestingly in C, the iterator abstraction that lives between your data structure and your algorithm actually means that like an iterator has an interface of the dot next, which for certain data structures, you know, the elements live contiguously in memory, so there is no pointer chasing. So because they have an abstraction in between, if you're using a linked list and you invoke some algorithm like find or whatever where you have to traverse, you're gonna pointer chase. But if you're use if your underlying data structure is a vector or a std array, there's actually no pointer chasing there. So really, the algorithm is in a way divorced from whether or not you are doing pointer chasing.

Aaron Hsu

Especially with the iterator patterns.

Conor

Yeah, so it's it's really based on the data structure that you're choosing underneath, which in this sense you're saying if you were gonna we don't have a graph data structure, but if we did have one, you would be advocating for representing that in some contiguous flat representations.

Aaron Hsu

Internal representations, implementations of your or of your complex structures, try to avoid having pointers all over the place. You know, that's that would be my first preference.

Conor

You know, I mean C in general, we do that quite well. C amongst everybody is not bad. Yeah, the vector is our go-to. And even some of the containers are not actually containers, they're container adapters. Like the stack and the queue and the deck are all just wrappers on top of vector. And and so like you could implement those as linked lists, but we avoid that because cache locality and portrait chasing is important.

Aaron Hsu

There's a lot of things that can be said about C, but you know, what things tell us a couple things. There is a culture, there is a culture of performance in C. So these things do matter. But you know, for instance, I think something that's come up in the the broader programming zeitgeist recently is is uh you know the the idea of larger object pools as a as a mechanism for managing your data as opposed to like RAII or other things like that. And I think modern C ⁇ tends to do a lot of selling to beginning C programmers, this this modern C uh uh C of RAII with these particular containers and single object focuses on things like that. And I think there's a there's a there's an extra level that I I agree with with some people on learning how to think maybe in terms of object pools at a top level instead of allocating these with smart pointers in the middle of your space for managing your your lifetimes. Stuff like that, I think, is uh an underappreciated technique outside of say the game programming world. And and C is really good at it. And yeah, I think you're kind of leaving a lot on the table if you don't take advantage of that if you're gonna force yourself to use a language like C.

Conor

Have you used these techniques in your code defense compiler?

Aaron Hsu

Yes.

Conor

Really? And so are you manually implementing that yourself?

Aaron Hsu

So one of my interesting failures was that uh I had I had a ref counted memory management system that uh allocated and deallocated based on stack lifetimes, very close to what you would think of as like smart pointers in C. The same basic concept as a shared pointer. And you know, that had some overhead, so I thought, you know what? I'm gonna do some object pooling, uh, you know, manage this memory myself, I'm gonna you know, use my own allocator instead of right uh doing a malloc, and I said, all right, you know what, I'm gonna do it, it's gonna be sort of like a bump stack allocator based a little bit like the the slab allocator in Linux's kernel and all that stuff. And so I implemented all that, came out, worked beautifully, and ran exactly the same performance-wise as when I didn't. And then I got to thinking, I was like, well, you know what? That was kind of stupid. Because the underlying operating system is basically doing exactly what I just re-implemented. And so I had just re-implemented a kernel malloc in for myself and got it. Exactly the same comment. Do you keep it or do you toss it? I tossed it. I tossed it. I I I got about 10 commits in of on that work, and then you'll see a giant revert of all that code. And I just, you know, goodbye. I don't I don't need that anymore. So I I do other things. But the the the the principle of of managing those objects in a way that avoids needing to manage ref counts throughout your program. So basically going even further than just smart pointers. Get rid of getting rid of smart pointers in your program and you know, having object pools at a higher level so you don't have to bump ref counts up and down all the time and stuff like that.

Conor

You know, that's that's a big I that's something I would Yeah, there's some uh I'm not sure if it's modern C guidelines, but there's a couple guidelines I think that consider smart pointers as just global variables. And depending on who you are, folks have strong feelings on whether or not those are a good thing or a bad thing.

Aaron Hsu

It's kind of the beauty of C, right? Is like you each person can be his own church. Because you kind of get to pick whatever, you know. Actually, maybe it's not the beauty, maybe it's the curse of C is that you're relegated to picking only the subset of C you like and then always being, you know.

Conor

This is what I've heard from uh a manager at Facebook that uh when they code on their own, they love to use C. But when they code and are managing a team, they never use C because everyone has a different style that they want to program in, and trying to mandate a consistent style is so much harder. And so they choose Rust, you get way more guarantees, there's way less code review needed. And you can just say we're using Rust format, and it gets rid of a lot of the arguments that you end up having if you're coding in a C code base.

Aaron Hsu

Yeah, well, if we want to get snarky and critical about things, you know, like I I have the same complaint about Rust and C, which is simply that the languages do not encourage uh like deep inherent memorization of the ecosystem. Like you tend to be doing a lot of lookups, a lot of references, a lot of autocompletes, a lot of, you know, which which library do I need to call for this thing. And I much prefer when I can think about a problem, have the language in my head and not have to go to an API reference, not have to look something up every hour or every 30 minutes to go have to do something. I just want all of that sitting in my head, and I just want to program. I don't want to have to deal with all that other stuff.

Conor

Well maybe maybe this is an opportunity. So of the stuff sitting in your head, you mentioned algorithms, you said you preferred sort of families of abstractions, but when it comes to primitives, a lot of these map to what we consider algorithms in C ⁇ . So what are, you know, your go-to favorite primitives that I mean, some of them, like I said, IOTA that exists in C, whether that's really an algorithm, you know, it lives in the actually it lives in the numeric header, which are a small set of numeric algorithms.

Aaron Hsu

Diodic iota, though. Dyadic iota and iota underbar in API, which those correspond to some really interesting cases. Dyadic iota. Walk people through what uh and actually walk people in case they happen to not know what iota is. So iota is the the primitive that would allow you to generate the the numbers uh or generate the discrete space in a n-dimensional discrete space. So so in in in the vector case, you would be generating the natural numbers. It's the index space of uh of a vector. In a matrix, you're generating the index space of a matrix, uh, which would be things like 0, 0, 0, 1, 0, 2, 1, 0, etc., uh as indices into a two-dimensional array of some sort. And you can go up to any number of dimensions with that and you generate sort of the entire index space that exists.

Conor

So the C iota is basically the one-dimensional subset of the APL iota. Right. Right, right. And so dyadic iota.

Aaron Hsu

And dyadic iota, this is this is one this is a cool design question you have, right? Because dyadic iota, when you express what you want, it's really just I want to find matching elements between two sets of things, right? I want to- I have uh an ordered set of one thing, and I want to find that the matching things in an ordered set of another thing, right? And it's that's a really simple specification, but it gives you access to all sorts of algorithms, right? There you can do a binary search to find that stuff. You can do a hash table lookup to find that stuff, you can do a quadratic lookup on that stuff. There's all sorts of ways of finding that data behind the scenes. And there's uh there's something I really like about not having to think whether I want a skip list or a hash table or a binary search or something else, and allowing that to be decided on later based on the actual data that you have, instead of a priori deciding we're gonna make this a hash table because we think this is what our data is going to look like.

Conor

We are saying the word dyadic uh to convert that to uh I mean I made the same mistake. To convert that to C speak, that just means a binary function. Not bitwise arithmetic, but just a function that takes two arguments, whereas iod iota is a monadic or unary function takes one argument. So for the case, let's give give them a short example. If you've got the lists 2, 3, and 1, 2, 3, 4, 5, and you place dyadic iota in between those two because binary functions are dyadic functions are infix in APL. What does that give you as a result?

Aaron Hsu

It's gonna look at those elements that are the left argument, that second set, and it's gonna try to find the matching element in the other set and give you, return you the index pointing into that space. Or into that set. So if two, three is your left argument.

Conor

One to five is your right argument.

Aaron Hsu

So you would get the well those some of those don't match. So there's an extra edge case where it says if you can't find it, just return the index one more than the unmatched. So if you did two, three and you're trying to find, you know, one, two, three, four, five or something through that, the two and the three in that one, two, three, four, five, are going to match on the two, three. Right. So you'll get uh zero for the two, because that's the first element, and three is the second element in that set. So you get uh one there, and everything else is just going to give you uh two because they can't find it in that set.

Conor

Right.

Aaron Hsu

So you'll get two for the one, uh, one, two, two, two.

Conor

So it basically returns you the indices of matched items, and for everything else that doesn't exist, you get a length plus one back. Yeah.

Aaron Hsu

Basically the index of the matching item or one more than the largest index in the largest valid index for the uh searching site. Right.

Conor

And so off the top of your head, do you know how one this is implemented, and I'm not even sure if you can say in uh dialogue APL, and two, how it's implemented in code defunds, the GPU version, because I'm sure they're very different, and it's interesting that you could use binary search, because binary search is not typically the top algorithm you think of when you're doing a GPU accelerated algorithm.

Aaron Hsu

Right. So so for an algorithm like this, the on a CPU, if you have enough data that you need to do this work, it it pays to build a hash table of this stuff and look it up. And so in the dialog interpreter, you would, in fact, often generate a hash table for the set of elements you're gonna look up, and then you just look up membership in that set and find the index that goes along with that. So the key is the value and the value. The value is the key. The value is the key, the index is the value.

Conor

The problem is that we were have to use the value multiple times there. But yes.

Aaron Hsu

But uh but the problem is there's a there's a computational cost to building the hash table. So very often it the interpreter will prefer to do that where you have an array that's stable. But if you have small amounts of data that you're gonna search, it's not worth it to build the hash table. So you can just use a you know a quadratic search or a binary search to find your data in that space, and that'll have lower overheads, and that's the faster way to go. And it's very common that you might use this pattern on small sets rather than large sets in APL. In other languages, this isn't as much of a primitive. It's sort of a special case for a lot of people. So they they tend not to want to have optimizations for small cases and large cases in the same primitive or same library call. In the code efense compiler, since we care about the GPU and the CPU, our CPU, we have two algorithms, uh two spaces we have to implement. The CPU case, we're assuming that it's small. We're assuming it's small. So we we use like a quadratic or a binary search algorithm on small arrays because we don't want more than like a thousand 1024 of them. So we don't if we don't have more than like two to the ten of these elements, we use something very naive because it's low overhead. But on the GPU side, we we can't really do a hash table. Like it's really complex to do a hash table and it's very expensive to do a hash table on a GPU. You can do it, but I don't want to have to maintain that kind of algorithm.

Conor

Well, I mean we do, not to interrupt, but I think it's been in the last one or two years, we have a lot of algorithms in different libraries, but we have started building in the namespace KUCO for coup collections. Yeah, we have a bunch of these different types of hash maps, because it's not just one hash map on a GPU, there's these static hash maps. So, anyways, if you're thinking out there, to roll your own, very difficult. If you don't want to roll your own, they are some hash map implementations that we are rolling out, so yeah, and and uh you know the problem then is well uh it's it's a lot of work to work on this.

Aaron Hsu

So what I what what I do is I just use the uh binary search, and that is very low overhead, and it's you know it requires logarithmic in general, the the logarithmic type critical paths, but in practice, especially for those intermediate variables where you want to maximize the amount of actual work you're doing on a on a problem like this, because on a GPU, you know, this might be a a very memory-bound sort of operation. And so when you're working with that, I I want to try to minimize the memory bandwidth on it for the types of intermediate spaces that we very often would work with in the data. So I I just use a binary search and that turns out to work remarkably well.

Conor

Yeah, I'm trying to think if there's because uh I was chatting with Kai the other day, and he was saying that he has certain optimizations built into like kind of what similar to what dialogue APL does, idiom recognition. Yeah. And he said one of those is a uh row reduction outer product, or or table as they call it. So like you can build up a table and do a reduction on each row, and that actually won't materialize. Anyways, I'm trying to think if there would be some GPU equivalent, uh probably the binary searches for each element would end up being more performant. But you could do something similar. Like fusing the results of the lookup with the with the next operation. Yeah, like so I'm trying to think if you did some outer like you could implement dyadic iota technically in terms of like a outer product.

Aaron Hsu

For for small arrays, I I I do have that just directly in there, and you can fuse that. Yeah. And uh this is just for outer product in general, you're saying. Because on the GPU we just tile it out. Right. And we do the operations. So if you've got fusion on your scalar operations, then you can fuse that outer product.

Conor

Yeah, that's super, super nice. Because it's a very common pattern that you blow th blow something up into a table and then you immediately want to shrink it back down on a row or column basis. Yeah.

Aaron Hsu

And then as long as the memory requirements for that are small enough, then yeah, it makes sense. And sometimes it actually may make more sense than you think. If you have too little data to s really saturate the GPU, sometimes it's worth it to do a little extra computation, saturate the GPU a little bit better, and make use of all that computation power, even though you're slightly less asymptotically efficient.

Conor

Yeah. That's becoming a problem that our GPUs, especially in the latest like Blackwell models, are getting so big that it's actually very difficult for small problems. I mean, the national labs in America don't have any problems saturating our GPUs, but like for a you know, a single node, you're just doing something at home, it is actually very hard to s put your GPU to full use. Yeah. And so now there's you know technologies coming up where they're actually you know built like partitioning your GPU uh virtually into like smaller GPUs because then you can just send multiple tasks as if you have like a multi-node system. I would take advantage of that if I could. Yeah. I mean most of us don't have black weld GPUs, so it's not not a problem for most of us. Uh I don't even have a blackwell GPU. I think I've got an Ampere in my workbook. I think I've only got like three or four. No, that's a joke.

Aaron Hsu

Of course I don't have any.

Conor

Alright, well, we're at the what time is it? We're at the 30-minute mark. Maybe we'll take a small break here. This is gonna be a week for the listener. It's gonna be like four minutes for us, and then we're gonna talk about tersity and the the pitch that I don't know how to make for why tersity matters. All this has been the warm-up to the I mean that was the initial that was the initial topic. Uh all right, we'll be back in a sec. Be sure to check these show notes either in your podcast app or at adspthepodcast.com for links to anything we mentioned in today's episode, as well as a link to a GitHub discussion where you can leave thoughts, comments, and questions. Thanks for listening. We hope you enjoyed, and have a great day.

Bryce (Outro)

Low quality, high quality. That is the tagline of our podcast.

Conor

It's not the tagline. Our tagline is chaos with sprinkles of information.