Conor

Well, I mean I'm like a APL programmer at heart, not a Right, right.

Bryce

I think it's like like you you're approaching it like top down, whereas I'm approaching it like bottom up.

SPEAKER_03

Yeah.

SPEAKER_00

That's what makes us such a such a such an awesome pair.

SPEAKER_02

Make that the cold open.

Conor

And the last part of this episode. Welcome to AD SP The Podcast, episode 294, recorded on July 9th, 2026. My name is Connor, and today with my co-host Bryce, we chat about the histogram algorithm, histocache, and more.

Bryce

It's gonna be fun. It's gonna be so much fun. I am gonna get to give you a quiz.

Conor

A quiz? A quiz. About what?

Bryce

Uh I don't think the quiz is gonna go well for you.

Conor

That's fine.

Bryce

Alright. Alright. Here's the quiz. You are given a graph. And the answer is or the question is, not the answer. I'll give you the answer eventually. But this is a graph that on the x-axis shows different bin counts, and on the y-axis shows speed up. And this is for a histogram algorithm. In particular, a multi-channel histogram algorithm. Multi-channel means a histogram where it outputs uh to multiple different places, like uh if you're doing a histogram over an image, over the pixels in an image, and you want to output uh you know different red, green, blue, alpha uh counts. And uh the question is for this diagram, why is performance regressing for some of the large bin counts, but not other of the large bin counts? And all of the information that you need to answer this is on the graph. You don't need to see the code, the answer is very simple. And we will see whether you can get there. So the in particular, this graph shows uh uh the the perf from from bin counts starting at 16 to uh 124k bins. Uh but but the wording of my question is we're we only we're only interested in the performance of the 32k bins up to the 1024k bins.

Conor

Well, first of all, let's uh let's take a step back and understand multi-channel histogram. So all it means is you're just you're binning multiple things instead of a single thing. That's all it means.

Bryce

You are taking one for for like like when you take your value in for a histogram, in this case here, your value is something that you're decomposing into multiple constituent parts. The example I gave was like a pixel where uh you know it has an R a red, a green, a blue, and an alpha component. So you have some composite thing that is your value, and the output is going to multiple different output locations. So you're splitting it up into its components. Or like if you had like a uh a 3D uh point uh value, like a 3D point struct that had an x, y, and z coordinate. Your histogram algorithm in this case would have a separate output histogram for the x's, a separate for the y's, and a separate for the z's.

Conor

Okay, that makes sense. And yeah, you've got speed up on the y-axis, and then on the x-axis you have zero all the way up to a million, because it's a thousand thousand. Yeah. And at the thirty-two thousand mark, there's a degradation right there, and then it pops back up, and then at sixty-four thousand, it degrades again.

SPEAKER_03

So obviously, those are both powers of two.

Bryce

Ah, interesting, interesting. Those are both powers of two.

Conor

Well, I mean and everything I guess technically on the x-axis is a power of two. It's not like I'm Sherlock Holmes here.

Bryce

Is it?

Conor

Is it? Oh, yeah, that's true, it's not. A lot of them are. Well, it goes 16, 32, 64, 128, 256, 512, 1000. And I'm assuming that's 1024. Uh, but then in between 32 and 64 is 48 and 56, which is rather odd. Because other than those two.

Bryce

I I will I will I will give you uh information here that is not applicable to the solution of the problem, but explains why 56k is on this graph. The reason that 56k is on this graph is because that is the number of 32-bit bins that you can fit into shared memory on an NVIDIA B200 GPU. And so that bin count was important to include on here for the single channel case. And this is the multi-channel case. It just happened to be that when I did the benchmark sweep that it included that point here. And 48K I think was put on here because uh we were interested in more granular information about the performance between 32k and 64k. So 56k was like a specific interesting like case that we wanted to look at. It's not applicable here because in the case of the multi-channel histogram, uh you need like if the if for the single channel you can fit 56 bins, then for the multi-channel you can only fit 56k divided by however many channels you have. In this case, we always have four channels. But it is it is beneficial that we did include the 56k bin count on here because it helped us learn something.

Conor

Oh, and the in the I didn't read the tweet. The tweet says that the correct answer is one word, right?

Bryce

Yes. That's that's I think me being a little bit cheeky, but the answer is not complicated. Or or the answer I will accept is not complicated. Well, that's not true. The answer is complicated, however, you really only have to name the general area that the problem is in to get the answer correct here. So Yeah, I don't know. I don't know. I'm I'm No, no, no, no, you you you're gonna get there. You you've already identified one of the key pieces of this, which is at so from 32k to 1024k, look at all of the ones that regress. What do all the ones that are regress have in common?

SPEAKER_03

That they're a power of two.

Conor

Right, and all the ones that don't regress are where it's just the 48 and 56, so yes.

Bryce

Uh but but I tell you, if it if you did any other non-power of two, it would not regress. What do you know about the histogram algorithm? Or what do you know about histogram in general?

Conor

And what do I know what do I know about your algorithm and uh the implementation?

Bryce

What do you know about the nature of solving a histogram?

Conor

The nature?

Bryce

Like, what are the bottlenecks in computing a histogram? Does it do a lot of compute?

Conor

Uh depends on the implementation.

Bryce

You believe that there's an implementation of histogram that does a lot of compute?

Conor

Of course you can construct uh compute intensive.

Bryce

What what what what is the what is the compute what is the compute by compute I mean, you know, arithmetic.

Conor

Uh I mean the easiest way to implement this in a array language, well is it the easiest? Um, is to do uh well, it depends on uh yeah, the bins and whatnot, but if you if you have like a you know every value gets its own bin. You just do an outer product and then a reduction on every row.

Bryce

Okay. So an outer product and reduction. What is the arithmetic intensity of those operations?

Conor

Arithmetic intensity?

Bryce

Is it is histogram more like a matmall or a mem copy?

Conor

Is histogram more like matmall or more like memcopy? Uh it's definitely not like memcopy. Would I say it's like matmol? Um not really, but I guess if I have to choose, uh I'll choose mat mole. But I I feel like I'm getting you're you're trying to lead me, you're trying to lead a horse to water and you're failing.

Bryce

How many in in in matmol, what are the what is what are the operations that you're doing?

Conor

You're doing multiplication and addition.

Bryce

And also, and also addition. Multiplications and additions. Uh roughly order of magnitude, how many multiplications and additions are you doing? Is it is it a linear number?

SPEAKER_03

No.

Bryce

No. It's like it's n cubed or n squared, depending on you whether you're doing mat batched or or or whatnot. Um but like let's, you know, it's nonlinear, right? Okay, you're doing a lot of flops. Depends on the size of your matrix, right? And depends on whether you're doing it, you know, whether it's a sparse map mole, structure like structured sparse, etc. But like a dense map mall, nonlinear. Okay. So you said it's doing multiplications and additions. On on the values. Are you doing multiplications and additions in a histogram?

SPEAKER_03

You're doing additions.

Bryce

Okay, you're doing additions. That's correct. What type of additions are you doing?

SPEAKER_03

Uh you're adding ones and zeros.

Bryce

Um well, you're always adding ones and zeros, technically. Are you adding let's assume let's pretend here that our let's let's pretend here that our our our histogram input type is floating point numbers. Okay? So assume that it's fp64. When you're doing your histogram, are you adding those fp64 values together?

SPEAKER_03

No.

Bryce

What are you adding? Ones and zeros. Okay, you're adding ones and zeros. What data type are you adding?

Conor

Whatever integer you decide to represent your bin counts.

Bryce

You so you are adding integers.

SPEAKER_03

Mm-hmm.

Bryce

Okay. In mapmul, are you adding integers?

SPEAKER_03

Not all the time.

Bryce

Let's assume we're doing let's assume we're doing an fp64. Floating point. Okay.

unknown

Okay.

Bryce

So in your histogram, you're in your in your map mall, you're doing floating point multiplications and additions in a non and it's O nonlinear. Right?

Conor

Sure.

Bryce

In histogram, you are only doing integer additions. What how many are you doing?

SPEAKER_03

Uh the ti uh the count of uh the number of values you have.

Conor

You're also doing comparisons too, potentially.

Bryce

What is the big O complexity?

Conor

Linear. And also, too, the the reason the reason I zoned out for a sec was because uh like this is all dependent on your implementation. Like I said, if you're doing an outer product It's not it's it is, it is if you're doing an outer product and then summing each of those rows, that's a quadratic amount of work. It's not linear. Like the implementation that we're talking about, where you just go one by one, sure, that's linear, but like an outer product, you're gonna do a quadratic or not a quadratic amount of work. Uh yeah, it is quadratic. Because you're gonna Yeah. Yeah, I'm correct. Uh and it all yeah, so it's it's it depends on the implementation.

Bryce

You wanna talk me through how it's quadratic?

Conor

Yeah. Say you've got ten elements, an outer product, an equality outer product on a ten uh element array is gonna give you a ten by ten matrix, which is a hundred values. And then you're gonna do a linear reduction on each row of that matrix, which is uh a square. So you're doing a quadratic uh amount of work. Um like each reduction is linear, but if you're doing a reduction on a Boolean mask that was the result of an equality with each element with the rest. Anyways, that's why when you were talking about the bytes thing, which kind of is uh I don't understand the point of this thought exercise, but I was thinking like, wait a second, like depending on the implementation, you could be doing more than a linear amount of work. Anyways, that's why that's why I was I didn't actually zone out. I started thinking that, like, what are we talking about here? We're we're talking in the in the abstract about uh an algorithm that we haven't actually described. And uh it the the things we were saying may or may not be true dependent on what the algorithm actually is.

Bryce

Okay, let's let's do some let's do some quick math. Um there are 148 SM cores on a B200.

Conor

This is like gonna be uh is this episode even gonna air? We're gonna have to record for an hour because we're gonna toss this episode.

Bryce

This episode is gonna air. This episode's gonna air.

Conor

I mean, I feel like didn't we have a disagreement at one point on uh some algorithm that was like uh you were arguing. I've gotta go figure it out. Oh yeah, it was which is it more similar to a transform or something? And I still like even describing all this stuff, like a memcopy is just copying, it's just moving.

Bryce

What what what is the dominant operation in a mem copy? Maybe a transform. How about how about a transform? A transform is a better example. Is it more like a transform or a um or a map mole? Or is it how about this? Is it more like a vector add or a map mole?

Conor

I don't know. I I still I still think it's more similar to a map mole than anything you've mentioned. We I mean this is the thing. This is why I bring up that previous example, because like I refuse to agree that something was more similar to something, but it's just because like my categories my the way that I categorize things is different than the way you you think about like the things that it's doing under the hood. I look at like the shape. Like if you look at what mapmall does, it takes something in one shape and turns it into a different shape. If you look what memcopy does, or if you look what transform does, or if you look what vector add does, it takes something in one shape, the shape doesn't change, and it's just the values that change. Histogram does this does uh something that's more similar to the Matmol in that like you have data and then you get something with a different shape that's just based on the values of those data.

Bryce

You're thinking you're thinking about this in terms of what the algorithm does. I'm thinking about this in terms of what are the per what are the bottlenecks limiting the performance of the of the algorithm. I don't care what the algorithm does. I'm just thinking about what are the limiting factors of the algorithm.

Conor

Well then you have to f then you have to phrase your question differently. Like you can't say, like, oh, which one is more similar if like to me the implied statement there is based on like what the algorithm does, and you're saying, oh, it's based on some other characteristic.

Bryce

That's fair, but that this is why I think this is an interesting problem, because you and I look at an algorithm in a completely different way. I look at it from the bottom up from the performance side, you look at it from the top down from the the algorithmic side. So that whatever weird performance effect we're seeing has something to do with the memory subsystem.

Conor

Well, that was a very boring 28 minutes to get to that single statement.

Bryce

Alright, so in a histogram, when you're when you're doing the store, the store is generally the expensive part because you have to somehow synchronize updates from different threads, right? So it would typically go through atomics. So the the bottleneck here is not actually the compute or the loading for the most part, except in some cases where you have low contention. The bottleneck primarily is the speed at which you can store the data into the result, because you have to ensure that you store it in a data-safe way, which means you need to use atomics. So I'll tell you the other thing. This this this weird performance effect does not happen for uh the single channel version. So most cache subsystems are banked, which means that when routing requests through the cache, based on the address, the memory address where the request is going to, it gets routed to a different part of the cache subsystem. Now, in our case here, this is a multi-channel histogram. So when we load one value, like a pixel, we then split it into its four constituent parts, and then we have to issue four stores into the memory subsystem that are going to hit four separate memory addresses to store the increment of the count for those four constituent parts. In this case, where we have these power of two bins, the last bits of the address, the bit for all of these, all of these four addresses, all four of these bins are a power of two size, and they all have the same alignment, and they're all gonna have the same last set of bits. And so when they go through the cache subsystem, all four of these store requests are gonna get sent to the same part of the cache, to the same bank in the cache, when they're power of two size, because the cache happens to be power of two sized, or rather, the the the way that the cache routes requests happens to be based on you know uh uh some of the low bits of the address. When we have a non power of two bin count, then the last bits of the address of each of the channels is different. And so they get routed to different L2 banks. And that is why if we do 64k, we see substantially worse performance than if we do 64k plus one bins. Now, the interesting thing is how you solve a problem like this, is a couple ways. One, you can change your data structure. So the data structure that we're using here is uh a struct of arrays. So each individual channel has its own arrays. So we have one block of memory for all of the red components, all the green components, all the blue components, all the alpha components. You could change your data structure to a data structure where you instead, you know, just have one, you know, you have the RGBA right next to each other, but in that case you've just got a single channel histogram. Like the person who chooses this multi channel histogram algorithm has intentionally decided that they want to have all of the individual components segregated into their own array where they're densely packed. The other way that you can solve this problem is by padding. So when you allocate the storage for these channels. You make sure that you put some space in between each of those allocations. Usually the best way to do it is to do one big allocation and put the padding in yourself manually. Because if you do four separate allocations of a power of two-sized chunk, you're likely to get addresses that are right after each other and that have this unfortunate alignment where they're all going to end up hashing into the same L2 bank. And so what you instead do is you allocate one big chunk of memory, and then you put a little bit of padding space in between each channel's storage, such that their addresses will hash differently. And of course, I probably would have gotten to the bottom of this if I hadn't added the 48K and 56K uh bin counts here. But many years ago, like 10 years ago, when I was working at Berkeley Lab on writing high-performance tridiagonal solvers for the Intel Xeon Phi chips of the time, uh I ran into a very similar effect like this. Um and uh and had to do a similar trick with adding padding to it. And actually, that is what motivated me to go to the C committee because I wanted to make sure that we added a proper multidimensional array abstraction to C. And in particular, that we added one that would support arbitrary layouts so that you could express a layout that has padding in between the dimensions. Because one way that you can add this padding is conceptually if you think about, if you think about uh the the big block of allocation for the channels as being a multidimensional array, where one dimension is what channel am I on, and the other dimension is uh how many bins are in that channel. One way you can add the padding is by adding a dimension in between those two that adds the uh the stride that you want. Anyways, I looked at this graph and it took me like three minutes, and I was immediately like, ah, this is this is some sort of L2 cash, you know, bank conflict effect.

Conor

So what's the single word? Memory?

Bryce

Cash.

Conor

Oh man. And just after having had a great episode where we had lots of great feedback on the GitHub discussion, and uh, you know, one person DM'd me. Um, and then we go and do this. This was maybe one of the worst episodes.

Bryce

I think the people are gonna love it. I think you're gonna get great feedback on this.

Conor

Uh and like also, too, like they're not what they're not looking at this graph. Like, did we even describe the graph well enough? And we never even actually described the algorithm. And that's my that's my problem, is that like technically you know, you you say, oh, there's only really one all all algorithms, and they're not really. Like, I was thinking like if you have a low enough number of bins, which clearly you don't based on this graph, but like if you only are got, you know, I don't know what the right threshold is, but like you could just have every um you know, if you if you're chunking this up, every you know, set of threads could just have their own array. And uh and then basically you just you just add those together. And uh then then you avoid all your atomics issues, you know?

Bryce

We call that privatization. Um, but you still like you can do you can have every thread have their own bins, um, but you can also have every group of threads have their own bins. And that's what the lower bin count algorithms do. Is that every group of threads has their own bin, their own set of bins that live in shared memory, in the the fast GP of memory. And then at the end, they merge their local privatized bins together.

Conor

So, anyways, I I I think that I think the the problem with this is uh with this episode is that you went in assuming a ton of stuff, and you just said, oh, all algorithm implementations are the same, and yet already here, now you now this is the interesting part is that like you're actually dispatching to a different algorithm based on the size of the bin. And you just we you just like kind of blanketly said, like, oh, there's only one algorithm, they're all the same, and uh that's like just demonstrably false.

Bryce

For the points we're looking at at the graph, it's all one algorithm. So the problem with you with the approach you just described um is what do you do when you have a larger number of bins?

Conor

I mean it's just not gonna work, right?

Bryce

Well, when you just have too many bins to store a local copy of the whole histogram.

Conor

You're just not I mean that that would be uh a terrible idea.

Bryce

To have that many b just to have that many bins?

Conor

No, no, no. To store a local copy. Like I said, you need to have like a uh uh a number of bins that's below some threshold. I don't know what it is, but like, you know.

Bryce

But then what's what's the thing that you should do when you have a larger number of bins?

Conor

Uh the algorithm that you've alluded to that we haven't talked about, where you know you're protecting uh a single one with atomics so that you can do updates and whatnot.

Bryce

Yeah, but the problem is that if you have a lot of contention, if you have if you if it ends up you you had a lot of bins, but most values go into just a few bins, then you have a lot of contention. And then that becomes very slow because you have a ton of atomics going to a couple of bins and your performance tanks because all the atomics on uh any individual bin get serialized. Um so there's a couple different things you can do. You can you can still do a privatized histogram, but you just you can't have it be local to the thread. You have to allocate dynamic storage for it. And that's what Cub currently does today, which is a little bit slower. The uh this algorithm, which is entirely something that an LLM came up with during auto research, is uh is one where you uh I call it histocache, where you build a small cache, like a small hash table basically, um for some of the bins in shared memory. And and so it for bins that are more frequently used, or in this case just a lucky set of bins, because there's no eviction, uh, they get to use the local uh storage. And then for other bins, they get to they have to go up directly to the global memory. But one of the advantages of having the cache is if you own if most of your values are only going to a small number of bins, then the cache will absorb it. And if your values are evenly distributed with a large number of bins, then it doesn't matter if the cache misses because you don't have a lot of contention. So the atomics going to the global memory are mostly cheap because they're not contended. And the interesting thing about the caching algorithm is it's the only way, like you don't if you knew about the in the structure of your input, if you knew, oh, most of my values are concentrated ahead of time, then you could pick a better algorithm. But the problem is you don't have a way of knowing that. And having a little cache lets you have one behavior when your values are concentrated, and a different behavior when your values are not concentrated.

Conor

How am I gonna edit this? I mean, that last part was interesting. Um histocash.

Bryce

Histoca.

Conor

Maybe that's the name of the episode. At least it'll have a good title.

Bryce

Yeah. It's uh it's interesting because the cache that I use, it uh it does not evict because it would be too expensive to do an eviction. Um so the cache is it's directly probed. So what you do is you get a value, you go and you find your bin, and then you look up where your bin should be in the cache. And if somebody else has already claimed that spot, then you you just you've missed in the cache and you go to global memory. But uh if nobody's claimed that spot, then you get to claim that spot. And so it's nice because it's a very cheap cache. It like the cost of a miss and the cost of a hit are very, very cheap. Uh the downside is that you know, if somebody's claimed your slot, you're just screwed.

Conor

Interesting.

Bryce

And so there are some adversarial, there are some adversarial inputs.

unknown

I'll share.

Conor

Is there a public implementation of this?

Bryce

Uh people I'm I'm in the process of upstreaming it to Cub. Um so by the time this airs, there should be a PR open, maybe? Oh, I guess this is airing tomorrow. I was gonna say it's aaron too. Maybe maybe not quite. There's a bunch of different input structures that you have to look at. Which one of the interesting things with this problem? Like if you just have like if if all of your values are in one bin, then this works very well because you're always gonna hit in the cache. Um and if they're sort of like randomly distributed, you're gonna have a pretty good cache hit rate. But you have to like kind of work hard to construct uh uh uh an algorithm like this. This here is a specific construction where uh like you can construct an adversarial input where you you calculate like what two bins will collide, and then you first poison the cache by filling the bin with by filling the slot in the cache that you're gonna then fill the rest of your input sequence with values that would go to that slot and then miss. And if you do that, then yeah, the performance is pretty atrocious. But a lot of the like reasonable inputs that would represent real data, it does pretty good on. I mean this one's like kind of meh. But anyways, yeah, histocache. I think it's pretty clever. I will tell you, Bradley, Bradley got this quiz right in like, I don't know, three or four minutes. That's uh Bradley Dice, our co-worker. Have we had Bradley on this podcast? I think we might have.

Conor

We have not.

Bryce

We have not had Bradley on the podcast? Really?

Conor

No. Unless if I'm forgetting, but I don't really forget that kind of thing yet, at least.

Bryce

So it's interesting. You my first instinct when I look at an algorithm is to think about the the bottlenecks.

Conor

Well, I mean, I'm like a APL programmer at heart, not a Right, right.

Bryce

I I think it's like like you you're approaching it like top down.

SPEAKER_00

Whereas I'm approaching it like bottom up.

SPEAKER_03

Yeah.

SPEAKER_00

That's what makes us such a such a such an awesome pair.

SPEAKER_02

Make that the cold open.

Conor

And the last part of this episode. 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

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

Conor

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