Two's Complement - The Compiler Explorer Problem

Episode Date: March 20, 2023

How do you solve a problem like Compiler Explorer sponsors? Matt digs into a surprisingly interesting algorithm problem that is in no way related to compilers. Ben explains how he nearly bankrupted himself by starting a bank.

I'm Matt Godbolt. And I'm Ben Rady. And this is Two's Compliment, a programming podcast. Hey Ben. Hey Matt. What's new? Uh... Well, I'm sick.

Oh yeah. You've been absent from work the last few days with a head cold right not not the dreaded lurgy yeah no i i have uh it's funny actually because yesterday i i woke up early because i couldn't sleep because i was all my brain was full of snot and uh i came down and i you know sat down on my desk here at my house and started working. And like 14 hours later, I was like, I should go to bed. Oh my gosh. That. And it was only because I was just super absorbed in work and kind of trying to distract myself

from the fact that I was sick. In a good way, I hope. Yeah, it was. I mean, it's like, it's one of those things where I really have to be cognizant of not getting too absorbed in what I'm doing, because I know that I will burn myself out if I do that every day. But yesterday, it was actually kind of like good therapy. And I sort of like was thinking about uh you know some of the folks at twitter that are doing that not of their own free will these days oh my gosh um yeah and uh going like you know i have to i have to be careful because i i don't want to talking of being careful now you and i usually go out of our way not to mention anything that's particularly contemporary because we like to reorder our episodes as we see fit and now we're exposed to

having to release this one sooner rather than later otherwise people will well that's assuming that by the time you're listening to this twitter even still exists yeah i do hope you know it survived a lot over the years that's true we i we are not that is not the topic for today that is not today's topic has occurred will not be a surprise to our listener. I would like to point out that I'm excited for you that you are as excited about what you're doing for your day job right now. That you can spend 14 hours straight and then ask the self-limit because you will otherwise burn yourself out in a good way because you choose to. Yeah. So that's great news. no that and it's it's been

fun they the day job these days has been quite good but anyway that's not what we're talking that's not what we're talking about today no in fact we as always have our carefully chosen 20 seconds before clicking record topic which is a surprising difficult issue that came up in my little open source project and i was surprised how difficult adding a particular feature was and i was thinking to myself this could be like one of those coding interview questions that you could give to somebody and then i don't really like those at the best of days but you know sometimes you have to come up with them and then i thought well let's talk about it on a podcast because it's kind of an interesting problem. So the problem is this. Let's suppose, hypothetically, you have a website. the amount of advertising or otherwise on your website you want to strictly limit the number of

little icons for your advertisers stroke sponsors to some number so I only want to show say three icons at the top right hand corner of my website because any more than that and it drives me mad and I'm sure it drives my users mad so that's the starting point then I suppose you've got multiple sponsors and you have agreements with those sponsors that say hey I need to show your icon at least one in every n page loads and you know those so far you have three sponsors and three slots and so the algorithm has been hard code the three icons into the top of the page and get on with your life so that's a pretty good algorithm so far but then imagine a fourth sponsor comes along and you realize suddenly you have to make a runtime determination about which sponsors to show when so that you can

hand on heart go to each sponsor and say hey your icon is being showed this many times and i have metrics to track that so i can actually show people this right and because the easy route would just be to randomly show them and then hope the law of large numbers comes along your side and just make sure manually that there is no uh there's no like it's not impossible for you to show the requisite number of time of sponsors per time um you know that that's not fun i'd like to come up with an algorithm which can provably show that i can get every single sponsor shown and that there will be no issue or it will throw an exception and say nope you've oversold everything you can't keep everybody happy now and you might have to go to

four icons so that was the problem i was facing and i sat down and i wrote something and it turned out to be substantially more difficult than i thought it should be So just to clarify here, this is the promise that you've made to your sponsors. That's correct. Is that you, you will show their little icon, their image, some percentage of the page loads.

That's correct. Yeah. So just sort of like thinking of this at first pass, like, and you sort of alluded to this, like, it is possible that for more sponsors than three, you've actually overcommitted, right? and three slots it's trivially well i can't satisfy that right there's no sequence of of shift shifting them around that that makes it fair to all my sponsors because they'll all be less than 100 right right but if i have four and each one is 30 of the time then obviously it's pretty trivial to just keep cycling them around and you know shifting literally shifting them along you know show one two three two three four three four one four one two blah there you are they'll get shown a lot more than one in three and that's great so that's a good solution and as a human you'd sit down and work that out

as a computer you could reasonably you know imagine you came up with an algorithm and all it has to do is say satisfy the constraints that i've agreed a solution to that problem where you have four sponsors and one in three is to have sponsors one and two and then show three and four on ultimate page loads in the third slot right that also you know that the first two sponsors are getting 100 coverage the other two are getting 50 coverage so that's also a solution and then that was the when i wrote the algorithm, finally got an algorithm which didn't immediately blow up, that's what it did.

It finally said like, this is perfect. And I realized I was missing a constraint. Yeah, yeah. You want to balance them. Exactly. So you also want to say for a given frequency, folks who are being shown one in three

should be shown around about the same amount. And that's what makes it even more difficult because you've gone from something which is trivially provable um and i was thinking about this in terms of you know complexity theory um if i if i set if the forgetting how complicated the the algorithm that generates the solution is and say let's say the solution is an array of N samples of sponsors, right? So let's say there's just 10 of them, and each of those 10 array has a choice, three sponsors at a time. And I could say that to you and say, like, if you were to just cycle through these iteratively,

then it would meet my commitments, right? That would be like something you could say. You can, in a very straightforward way, you can see if it is a solution, right? So the solution can be checked in polynomial time, if we're thinking about NP and non-np kind of problems right like so a solution where you're saying is this um does this meet the criteria of all of the sponsors individually you go well there are there's 10 slots sponsor one is shown four times sponsor two is shown four times the sponsor three is shown four times whatever then that's more than a third of the time so they're all fine okay this is definitely a correct solution and so that becomes one category of difficulty as soon as you say i want to minimize the amount of difference between the numbers of times a sponsor is shown it goes into a new category because to check that

answer you have to solve the problem yourself i could give you something which like meets the criteria of like it's definitely one in three or more than one in three but to prove that it's minimal is also np hard or np difficult or np whatever the categories are so it turned out to be more and more interesting than i than i thought um and there are definitely online algorithms for doing this kind of thing but what i wanted to do and this is the critical thing, and this is going to get it into one of your favorite subjects, is I wanted to write tests. Yeah, I was just going to say, anytime you're dealing with sort of randomness, that becomes tricky, right? Exactly right. to a friend down the pub the other night as you do um his solution was immediately like a dynamic programming algorithm which just uses essentially an error metric of like how often have i shown

each one and then each time you get to choose so every time the page loads up it effectively re-chooses another sample and that's kind of how i solved it as well that's that's my solution is like that but rather than doing a choice every time and or having randomness and or dealing with you know well there are lots of servers each one of the servers has its own idea about which solution is what i wanted to be able to write tests so i wanted to be able to say generate me a minimal set and then i can compare it against what a human would have chosen for a a set of a rotation like uh that would work and satisfy all those constraints now obviously like i said at the beginning if you just did a random thing you could definitely say well just pick them with one third probability you know scale the probabilities

and then just keep picking them and see and then you would you would get an answer i'm quite sure you get an answer but you would never be able to write a test that wasn't anything other than seed the random number generator with a known good seed run the test for 100 and going to go well empirically i meet the criteria after 100 iterations so that's probably fine and i don't like that because it doesn't i i can't tell if the algorithm is wrong or right or anything it just seems that right also those kinds of tests are super hard to read but yeah so let me make sure that I understand what you're trying to get at here. So you want to build an algorithm that's going to produce basically a script, a list of the configurations that are going to be shown. Correct. through that list over and over again. Okay, cool. And then your tests then,

are you expecting a stable output from the execution of that algorithm? So your tests could be like, yeah, solve this problem for these constraints, and then it will produce that script. And then in the most basic case, you could literally just assert that for this configuration with these constraints,

it produces this result and if i change the configuration i will get a different result that is exactly their summary exactly correct yes and so for the very simple cases yes you can sort of squint and say well what would i do as a human and then obviously modulo ordering that where it doesn't matter and in fact i enforce a sort ordering uh within the icons just to make it sort of stable like you said uh yeah i that's what most of my tests are they're like well i've got five sponsors and three slots and then these these two have this frequency these three two have this frequency this one has to be shown every time and then this is the only solution that i could think

of and maybe it comes up with a slightly different solution and then i just write convince myself the solution is equivalent and then say okay well that's the one i'm codifying here it's like my algorithm so it's a little bit uh uh black box testy or um or not the other thing the other type um you know it's it's definitely a little bit over sensitive to the nuances of the algorithm in that but it is at least human understandable right you can say this looks reasonable to me like one two three one two four one two three there you go all right now we've got all the ratios are right everyone's about equal that looks good to me i'm fine with it yeah and you could send that to all of your sponsors and be

like this is literally what we did exactly if if if they can and from that standpoint i should like the record to to to note that my sponsors have shown no indication that they give any kind of care at all about this other than like i have an agreement that says one in n and i'm sure they'll take my word for it but i would like them to know that i've really thought hard about it to make sure i'm giving everyone a it on a fair shot but yeah so it's um it's an it was an interesting problem and i i i i sent out a message in this sort of random channel at work and i'm afraid to say we paralyzed half of our math phds oh yeah it was a wonderful nerd snap when they all started citing n choose k papers and the choice problem and all this kind of stuff but um yeah it was it was fun to discover and as i say it makes for it might make for an interesting

interview question uh even if you know how to do it which i think i do now i you know there's still a lot to discuss in terms of like testability like we've just been doing here um i i should say that i did also write as well as all these little unit tests i did actually write an actual test that says just generate a call the the code that's going to use the pre-canned list um having created the pre-canned list and do it you know sample it a thousand times and let's just make sure that on aggregate it still actually does keep to all of those criteria that each sponsor is one and end so that's that's kind of my integration test there where not only is i'm like i'm just rendering the page effectively and then looking at the icons again like these come out right which tests both the does the icon thing do the right thing as well

as does it correctly call the underlying algorithm and then does it in fact choose a new and different one of the possible solutions each time round you know like round robin or whatever it's doing you know it strikes me that that actually might be a good application of a generative testing or property based oh that's interesting yeah um if you especially if you wanted to be able to sort of dial up or down the amount of time you were willing to spend verifying the algorithm. Yeah. Like, you're never going to be able to get 100% certainty with a generative test,

but you can be like, I ran this for 12 hours, testing all possible combinations that the generative testing framework could come up with, and all of them satisfied the constraints. Yeah. So, you know, I'm'm not 100 sure that this is correct but i'm like many many nines sure that's that's really valid i mean obviously this is overkill all this stuff's overkill because given the of course n will be three page slots and maybe four maybe five sponsors total ever um again a perfectly valid solution to this entire problem

is godbolt sits down and writes out the list and then types it into the code right literally hard codes the list in that's completely reasonable but it was a really fun exercise in in uh determining you know solving a problem that is actually quite computer sciencey uh-huh but so are you gonna i was gonna say about the generative the thing that strikes me about the generative is that it is easy to given a you know a generate generated set of constraints like n slots m sponsors with this many like uh constraints themselves to prove that the result that you got out of the algorithm is correct right that i think is what you're talking about here is like sort of essentially randomly choose the number of slots randomly choose a bunch of sponsors call the algorithm

and then you can using this simple algorithm of like just counting the number of occurrences and divided by how many times uh how many things you got back um you can say yeah this definitely hit the constraints that we cared about although again the balance between sponsors is a bit more subtle in terms of that right but ignoring that part for now you can say okay this is probably great what you can't do is check that if it turns around and says there's no solution you can't tell if it's right or not so if it picks uh interesting four slots and then 10 sponsors that have to be shown one in seven or whatever something like that you're like i don't know trivially if that's solvable or not without writing the algorithm myself again which defeats the point so you could

again but it certainly allows you to approach the um the the conclusion that it'll either blow up incorrectly and tell you that something doesn't fit that you think could fit but if it does give you a solution it is a it is a valid solution so that is probably okay because again if you're if you're if you're on the phone to the sponsor and you're saying okay one in one in two or three and seven okay three and seven we can do three and seven and then i just type the thing hit enter and gotta go oh yeah it can find a solution for you yes we're good we're good yeah yeah no i mean you could definitely have a a generative test that like if i was writing something like that i would first start writing it with um constraints that i knew couldn't be solved for, and then I would

run the generative test until it blew up having hit one of those constraints, just to make sure I'd written the generative test properly. Right, that's true. And then dial back the constraints until I sort of fit the very edges of what I thought could be solved, and then let it

run for a wrong time, and figure out if we agree, basically. Right, right, right. And then see, like, could be solved and then let it run for a wrong time and figure out if we agree basically right right right right and then see like okay yeah and then you know if you if it blows up and says oh i couldn't come up with a solution for this then you sort of look at that and go like oh yeah no you're right there is i i can't come up with a solution for that either does that mean there's not one no but between you know the the algorithm the tests and me we can't come up with one so um but yeah that's super interesting so i mean i gotta say though like are you gonna leave our listener hanging by not explaining what your solution was because i feel like i mean we've got code so it's it's

effectively the dynamic programming solution so uh i have my array of of uh sponsors to fill and the first thing i do is i sort all of the sponsors by how their current occurrence compares to their their hoped occurrence right how how you know like you know so you start out and nobody's been seen ever right so everyone So everyone's equally badly placed. Right. So at that point, you just pick three arbitrarily out of your list and you put them in. But now they've had now they were all at 100 percent. Right. Which is obviously higher than the target that they wanted. And that's fine. Higher is always better. Right.

So then on the next iteration, you say, OK okay who all else needs to be fitted in and then you sort the sort them still and you say well okay well those three are now at the bottom of the list and maybe the other sponsor gets the to the top of the list now because he you know that sponsor is out by 100 or out by 30 33 and the others are now like at potentially 50 because they would have been shown for half the time so okay he's more out than they are so we need to pick him first okay cool and then you just pick any of the other two again right now you've got those two in and now you update the counts again and say okay now we've got a better idea when we're sort of asymptotically approaching the the right numbers for them all as yeah okay but the other thing that i do and this is the second constraint so that will

immediately find a solution to the the problem of having four where they have to be shown one in three that will immediately follow this find the solution it goes one two three one two four we're done and you're like no no that's not fair on three and four they get shown half as often as one and two even though they all pay in the same amount of money right which effectively what this all amounts to so adding that constraint of like saying um i want to reduce the standard deviation of occurrences for sponsors that are at the same tier so if you're a one in three guy then i'm going to get all of the other sponsors that are one in three and i will say how many occurrences are there of each of those what is the standard deviation of those counts if they're all the same the standard deviation is zero it means like everyone's got perfectly fair but if it's like two and oh and oh the standard deviation

is you know huge huge i don't know two probably near a two and so that's too high and so we're going to keep going and then that also gets counted in like their score as to whether or not they should be picked or not it's like how behind they are their their uh uh their contemporaries and so you just keep going until you hit the hit assist a set where all of your constraints appear to be sorry all your constraints in terms of the number of times of that things are being shown have been met and there isn't a single standard deviation amongst all of the the sponsors at the same level where anyone's been put out by more than whatever threshold you've decided is like that's fine i think my threshold set to a quarter

or something like that so like everyone has to be pretty much on the same number maybe one higher than the other right and that means that the algorithm will keep going in in the case of you know like a um uh you know like a rounding error of like well it's 0.333333 it'll keep going and adding more and more and more and more until eventually it goes well i've they're close enough now they're within a quarter of a standard deviation over the number of of choices that i'm going to make now yeah you can see you looking and thinking now. So the first thing I'm kind of thinking about here is, so you're actually able in this algorithm to bucket the sponsors into the fixed frequency. Yes, it's not a continuum because I phrased it as one in N rather than 33% or whatever.

Now, I'm sure I could come up with an equivalent scoring that sort of says, how fair is this? Now, one thing that occurred to me is that the algorithm could, in fact, pick a sponsor that's paying less money to more often than the sponsor pays more money if there's like competition at one level. So you could imagine weird situations like that. And I haven't put that constraint in yet. But my instinct is that you could come up with a score that you want to either maximize or minimize, depending on which way you do, about how good this particular choice is. And then you keep going until either that score is as high as it could be or as low as you, like it's an error, as low as you want. Or maybe you go until it stops changing between iterations and you go well this is the best i got and then if it's not getting any better you're like well then no solution exists which is kind of where i ended up although i just got a hard-coded set of like if you get to 100

and you can't fit these constraints then probably that's not you know that's not good enough and so i'm certain and maybe somebody who's listening now is jumping up and down in their chair or is walking their dog shouting into the void about like this well of course you use you know brisdom's blah blah algorithm right uh-huh but and if so please let me know or send me a pr or whatever it's just it's one of those things that i enjoyed the intellectual challenge i enjoyed the intellectual challenge of uh of trying to think of a solution and probably somebody smarter than me is going to say oh there's just a closed form solution but as i say a bunch of math phds couldn't come up with an answer in an afternoon of work right right and i

mean it's in a lot of ways i mean this is kind of like a portfolio optimization problem that's the funny thing is it is very similar to our day job yeah yeah that's that's very interesting i actually i was going to say it's actually an interesting um problem that presumably every online advertiser kind of has to solve as well they're trying to maximize their profit given x y and z constraints like google can't show you a hundred ads it can show you three or four or debatably however many many of the actual results are in fact ads hiding as such but whatever the idea being is like i show you the three best and how do you determine those three best especially quickly right right and then there's the meta portfolio optimization problem where google has to decide how many slots for advertisers will make us the most money.

Right. Oh, gosh. So you've got to optimize that portfolio problem based on the greater constraints of like... How many will users tolerate? Yeah, exactly. I just plugged three out of thin air and thought, well, this looks like there's enough space on the page for three. Right, right, right. Hopefully. there's enough space on the page for three right right right hopefully did i tell you about uh the the change to uh have we ever talked about bank of dad we've talked about i don't know if

we talked about it on air but we've talked about i don't think we have talked about it which you know is a great way of bankrupting yourself as you're about to explain i mean you know for a greater cause so so so for our listener uh bank of Dad is this thing that I actually got from a coworker many, many years ago where his dad would pay him a ridiculous monthly interest rate for money that was, quote unquote, deposited in the Bank of Dad, like 5% a month. So long as he calculated the interest properly. And this is when he was like six, seven, eight, nine years old, right? And so I've done this with our kids for a long time. And what happens, what I've discovered is you got to make the problem harder and harder and harder.

Otherwise, you're really not getting a good return on your bank of debt interest payments. And these days, for my oldest, we have given them a portfolio optimization problem. Oh, my word. Because we went from simple monthly compounding interest to daily compounding interest to continuous compounding interest to continuous compounding interest uh we actually had a version of this where it was like i would give them the interest amount for the month assuming continuous compounding and they had to figure out the interest rate oh um so inverting the problem and now the latest version of this has been a portfolio optimization problem where i say something along the lines of like, okay, you can pick the interest rate and the number of days that that interest is applied,

but there's a fee calculation that is a function of those things. And so the fees will be deducted from your total interest. And so you have to figure out which combination of interest rate and days results in the highest actual payment to you oh my gosh um and this has been and and of course i now have i've set myself up now for the future of having like infinitely many dimensions to add to this portfolio optimization problem

where i say okay and here's another fee and here's another fee and here's another fee and here's another by the um by the time they graduate from Bank of Dad, they'll be running their own trading system against the world, right? They are having to solve the same problems that we do. Yeah. That's really cool. I mean, we've already kind of busted out a little bit of Python

to try to solve some of these things. Oh, gosh. So it's leading in a good dimension. But yeah, both my kids are... At least one of them is well-versed with this type of problem and the other one is sort of like looking over the the ones you're going oh is this is this how i'm gonna and you're gonna have to come up with something more complicated

yeah yeah yeah factorize this large prime number and correctly you know other people make their kids like mow the lawn and clear snow, rake leaves. In my household, I torture my children to do their music practices, right? That's how they get their allowance. But for you, they have to calculate portfolio optimization in order to get... I guess this is interest on their deposit of the allowance that they had. Yeah, yeah. So, gosh. Yes. We did have to put a cap on the total of the allowance that they had yeah so gosh yes

we we did have to put a cap on the total amount of money that it's in bank of dad because i started projecting out and i'm like uh we're not gonna be able to make the mortgage payments if i keep it's like continuing on this pattern donald knuth who stopped giving out um payments he was doubling the the reward for every bug you found wasn't he for a long time and then went you know now we're at to 1024 it's no joke if someone finds a typo and so uh i believe he gives out um like checks that are like not cashable like they're fake like donald canoes checks i had a friend at google who had one and proudly had it on his on his uh desk but you know it wasn't actual real money and

and for good reason really i mean that was maybe a mistake on canoes part but whatever yeah yeah all right my friend yeah well those those my those kinds of problems are are all over the place is sort of my point right and they are very interesting when you find them yeah they are there are more places than you might imagine and most of the time of course when people like we interview people and it's like we talk about potentially like problems that involve like what big o notation does this particular algorithm have and then you know most of the time the problem is why is this not compiling uh hang on a second have you got your environment set up right oh wait a second just yeah no put put put put another space between these two things over here please please, and all that.

Yes. And it's never actually a problem that's algorithmic in nature. But every now and then, you hit one. Yes. And you're very pleased. Yeah. Yeah, totally. Totally.

Cool. All right, my friend. Well, thank you for listening to my problem. No, no, this is a great episode. If folks have any better ideas, then let us know, and I'll see you the next time. Yep, bye.

You've been listening to Two's Compliment, a programming podcast by Ben rady and matt godbold find the show transcripts and notes at www.twoscomplement.org contact us on mastodon we are at twos compliment at hackyderm.io...................................................... . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . .