Clear, Simple, and Wrong

1. I didn’t know enough to follow it
2. I didn’t care enough to follow it
3. I was too drunk to follow it
4. It relied on unstated context that I didn’t have
5. It relied on unstated context that I had but didn’t realize was relevant
6. I was trying to understand it as an explanation of X but it was an explanation of Y
7. (6), because the person mistakenly thought it was an explanation of X
8. (7), because the person did not know X and Y were different
9. (6), because the person didn’t have an explanation of X and wanted to hoodwink me
10. It was actually a description, with no explanatory power
11. It looked like – but wasn’t – #10 because I was not able to tell the difference
12. It was an explanation of a thing that does not exist
13. It looked like – but wasn’t – #12 because I was not able to tell the difference

Author’s note: This was written years ago. I still think it’s mostly true, but I never published it because it didn’t feel like a full explication of why this is worth thinking about. I’ve since seen similar models gestured at, so this idea is by no means unique to me. Publishing it as part of a draft dump because why not?

[Epistemic status: works on my machine]

Note: for the purposes of this article, I am assuming that there are only two genders. I’m not sure I believe that in real life, and I suspect this concept could be extended to N genders, but it makes it way, way easier to talk about.

Inspired mostly, I think, by Ozy’s excellent concept of cis by default and in particular this examination of misuses of the idea, I’ve been interrogating my own internal gender identity a lot. I’ve come up with what I’m calling the “two-bucket” theory, which feels right to my own experience.

And now I’ve come up with a new mental model for this: the two buckets model. I think this resolves a bunch of issues, but I have no idea if it will resolve yours. The idea is that, rather than having a gender, you have two gender buckets that have orthogonal amounts of gender-phlogiston in them. I have also explained this has being like the speedometer on a car, or being like attribute points in an RPG.

This feels right to me! I have a very small amount of maleness, and a very small amount of femaleness. I don’t think I would feel wrong in a female body, because I don’t think I feel right in mine; I just… don’t care much? I don’t really think I’m completely agender, and I probably lean male slightly more than female, but it’s like 10-8 whereas, like, Arnold Schwarzenegger probably has 100 points of maleness (and I don’t want to speculate on how much femaleness he has).

So what are the advantages here, besides ‘it feels right to me, personally’? Well, I think it explains a few things pretty well.

Cis-By-Default

I think “cis-by-default” is defined by people who aren’t much of either gender. Like, if your maleness:femaleness ratio is close to 1 and low in absolute value, you probably don’t care much and being gendered in line with your body is not painful. Sure, I’m a cis man. If I had been born with my same self-ness* into a female body, I’d be a cis woman. I just don’t care much one way or the other.

Non-Binary

I have, I am somewhat ashamed to admit, never really understood what “non-binary” means, and, in particular, how it is distinct from being agender. Like, how is being “in-between” genders different from just being not a gender at all? There’s no way that I’m aware of to explain the existence of both non-binary-but-gendered and totally-non-gendered in a spectrum model. In the two buckets model, a non-binary person might be like 55 male and 56 female, while an agender person might be 0/0 or 1/1 or similar, extremely small values.

Trans

One of the difficulties people have with the existence of trans folks seems to me of the form “you were born in a male body, you got by just fine being male for 25 years, and now all of a sudden you’re saying it was always wrong? You were a normal man for 25 years! You can’t have just been faking it that whole time!” I think you could model this sort of trans person as being, like, 15 male/90 female. Enough male that they would get by as cis-by-default if there weren’t a burning femaleness inside them.

* I am aware that my self-ness would have grown and developed differently if I had been born female. Maybe it would make more sense if this was a freaky-friday type of thing than a counterfactual born-female Alexander thing. But I hope my point makes sense either way.

Note: I wrote this a few years ago and never published it because it’s super negative and probably nobody cares. But rereading it now is kind of fun so I’m putting it out there. I liked the game but god damn it was full of problems.

I just finished Dragon Quest XI, and have some thoughts about it. This post is largely negative, because mostly I noticed things that bothered me, so I will start by saying I put about a million hours into the game and actually liked it quite well. However, it has a number of really annoying flaws that seem frankly amateurish.

Text

The text is bad. It writes out slowly, playing a little sound as it prints the letters, which is annoying. If you press a button, it writes the rest of the current block fast. However, if the block was short, it moves it off screen and starts writing the next block instead, so if you want to just be able to read things at a normal pace, you end up occasionally missing lines. This is a constant low-level annoyance throughout the entire game. The text should have printed immediately and silently and to a larger area of the screen. This makes certain things, like shops and inns, much more annoying than they should be.

The Menus

The menus are horrible. Very nearly everything about very nearly every menu sucks. The worst offense is the item menus. Each character has an individual inventory. The idea, I suppose, is to add a level of strategic depth to combat – make sure your characters have the appropriate healing items, or that your healer has some stuff she can throw at enemies to do damage. In practice, you always have a healer, and the combat isn’t very hard, even if you’re not grinding at all. So there’s a lot of complexity, and a LOT of extra menus, and places to lose track of things, for very nearly zero benefit.

There are, for some reason, 11 item menus. One per character, the “item bag,” the “equipment bag,” and “important items.” Keeping equipment separate from items might not be crazy, but it’s not interesting either. Especially since some equipment can be used in battle, making it more item-like, so the distinction isn’t really clear. It also means that you have two places to look when you get an item and don’t know what it does; it could be at the back of the item bag or the equipment bag. And some items your characters will put directly into their own inventories (healing items, mostly), so good luck if you clicked through that text. Despite having, again, 11 item menus, the game somehow fails to separate crafting materials from everything else, leading to tremendous clutter.

Equipping your characters is handled separately from the item menus; there’s an explicit Equipment menu. It’s annoying that if I am in an item menu and I realize I want to move equipment around, I can’t, but this isn’t really a big deal.

This is probably at its worst when shopping. Shopping goes as follows: You approach a shopkeeper, who says something that you don’t care about. Because of the text issues above, you press a d-pad button, or perhaps X or O if you’re feeling reckless, to skip past it. They ask if you want to buy or sell; you probably want to buy. You go through their list of items, and when you select one you have to confirm that’s what you want, then select the character whose inventory it will go into, then confirm that, and then if it’s gear, the shopkeeper will ask you if you want to equip it immediately and require another confirmation and some number of further textboxes to skip. It’s so much clicking! Most of the text is meaningless, I mostly want to do the same small number of things, and I end up putting things in the wrong inventory, or clicking X one too many times and starting the process of buying another one of whatever I just bought because I was trying to get through the menu quickly. When shopping for gear, it displays that gear’s main stat (attack, defense, charm, whatever) and how the new piece of equipment will affect that stat if equipped to a character. You have to go into the more info to see its effect on other stats which might also be relevant, and cannot at this time see the stats of the equipped gear. This is not the only time info that obviously should have been cross-referenced was not.

The main in-game menu has six options: Items, Equipment, Misc., and three options I used so little I had to look up what they were (Attributes, Magic, and Party Talk). Misc has a number of useful things hiding in it, at least one of which should have been promoted to the main menu, perhaps at the expense of Magic, which is useless.

Side note: Magic is a useless menu option because DQXI has a truly wonderful feature called “handy heal-all,” which uses your magic to heal but not all the way. I don’t know its exact rules, but it won’t overspend mana to top off your last couple life points. It felt very good, it had an easy shortcut, and I used it constantly.

The misc menu has the quest catalogue, which is a very useful list of all the side quests you have accepted, their current state, and info about how to complete them. It also tells you where you can go to accept new quests, if they’re available. Promoting this to the top menu would be reasonable. Leaving it tucked away is also reasonable, but it should have been the top or second option, since you go to it a lot. It also has the Character Builder, which is how you grow your characters. That should have made it to the top menu.

The misc menu also has the info page, which has info on everything and somehow still manages to suck. It has lists of items you’ve gathered and enemies you’ve defeated. For some reason, these things are not hyperlinked. For example, an item will show you what enemies drop it; there is no way to go from the item’s info page to the enemy’s. Why not? Because it wouldn’t be right if anything about the menu was good, I guess. The game includes crafting, and crafting materials do not list what items they are used for, either.  From the starting point of wanting to craft an item, finding out what I need to do to be able to requires me to go to the forging info menu, find the item, leave that menu, go to the item menu, find the ingredient, leave that menu, go to the monster menu, and find the monster that drops it. This is way too many steps for what is obviously a common usecase.

The Maps

There are a bunch of maps, and with one exception they all have clear flaws. There is a mini-map, which is fine, although not especially valuable. There is an area map, which is quite good. Everything else is dumb.

You can only look at the area map of wherever you are right now, and anywhere you can get to by navigating to nearby areas. The map of where you are right now is better than the maps of nearby areas, because it has info overlaid on it that is not present on other maps. Namely, people who want to talk to you, and a couple kinds of locks. There are two points in the game where you get special keys that allow you to access areas (items, really) that you couldn’t before, but it is not possible to search the maps for this information.

There is also a world map, which for some reason has no information on it except a picture of the world and dots for the places you can warp to. You cannot see a map of the place you’re thinking about warping before doing the warp, so if you forget the name of the place you’re going, you get to just try things until you get it right.

The fast travel options are weird. You can travel to major locations, except the ones you can’t. Namely, there are some islands that can only be gotten to by boat, and you have to sail to them every time. More on this in the section about linearity.

Movement and Buttons

Your character has a few options for movement. Normal walking/running (you get slower in cramped areas, which is actually kind of nice for being able to navigate inside houses and whatnot), sprinting, and horse. I wanted to sprint basically every single time I was moving; walking around between interesting areas is not the fun part of a video game. This meant I had to hold down R2 constantly, which is stupid. Sprinting should be the default, or toggled, or something. The options button sets you to auto-run, which is at the normal running speed but you don’t have to hold the control stick forward. Sprinting also has that feature. It’s one of those things where they added a nice quality of life feature that has almost no use, while missing an adjacent, hugely valuable improvement.

You can ride a horse outdoors by summoning it at a bell, which are placed by campsites and outside of towns, mostly. The horse is significantly faster than sprinting, but you have to get on and off, sometimes you’ll be doing something unremarkable like crossing a bridge and the game will stop you, walk the horse backwards a step or two, and helpfully pop up a warning that you can’t go that way mounted. So riding the horse is faster than running, except when it’s randomly annoying, and you can’t really predict when that will happen. I mostly didn’t use the horse because of the surprises. When you’re riding the horse you also have to hold R2 to dash, even though the only reason you’d ever get on the horse is because you want to go fast. Galloping through monsters knocks them out of your way instead of engaging them in combat, which is actually pretty fun. Except sometimes it doesn’t and you get into combat anyway; which monsters you can knock away and which you’ll have to engage is surprising, so I ended up just avoiding them as if I were on foot when I was on the horse. Overall the horse implementation is unreliable in ways that seem crazy, and the experience is mostly frustrating and un-fun.

When engaging enemies, you want to get close to them and then hit X, in order to strike first in battle. This is a silly thing to make me do literally hundreds of times, and has its own stupid flaws that should have been obvious to the designers. X is the button you use for everything, and in particular does three main things in the overworld: pick up items from “sparkly spots” (materials and occasionally items, they regenerate after a while), engage enemies that you’re close to, and fire your crossbow at enemies you’re a little farther away from. It is very annoying to try to grab an item, not notice where the little indicator is on your screen, and accidentally shoot an enemy instead, which causes it to come fight you. It is also annoying to try to attack an enemy and accidentally shoot it instead. Nothing bad happens but it’s a dumb way to waste a few seconds. There are four buttons that are completely unused on the overworld, by the way.

The controls are set up so that you can sort-of play one handed. The movement is on the left analog stick, of course. And menus are navigated using the d-pad. L2 is an alias for X, meaning you can interact with things and select options with only your left hand. However, there’s no alias for O, so you can’t go into a menu and then get out of it. L1 is completely unused. This is another thing where they half-assed a quality of life improvement but missed a huge, obvious part of it. L3 is technically used, but all it does is bring you to first-person view, which is, as far as I can tell, entirely for aesthetic purposes. That’s fine, but it would also have been reasonable to use L3 as an alias, and perhaps move the first-person camera into a menu. Maybe I’m the weird one, though, and other people loved this feature.

We have known since, at the very latest, 1994 that selecting moves in combat should be a consistent experience, requiring the same number of confirmations regardless of number of targets. That is, moves that do not select targets (either they hit all enemies, or are randomly targeted, or are powerups to the caster or whatever) should require some token click of “yes, I mean it” to keep the same cadence as other moves. DQXI bucks this conventional wisdom, and thus you sometimes enter a move you were still considering because you forgot that it was going to happen after N clicks rather than the standard N+1. A minor mistake, to be sure, but an amateurish one.

There are several times when a cutscene ends, you regain control, and then you walk a few feet forward and into another cutscene trigger. It’s annoying every single time. Just one more bizarre quality of life failure.

Linearity

The game is relentlessly linear. Unfortunately, it is not upfront about this. You can explore off the beaten path, but you are not allowed to have any fun if you do. You get a boat not far into the game, which provides you access to maybe ten or so new places. You can collect some new crafting materials – I didn’t track if you can make use of any of them, but you can grab them anyway. You can also see a bunch of locked doors, and talk to people who will not give you new quests or anything until the story has advanced enough that they’ll be interesting. You can also sail to a couple of whirlpools, which will glow and let you know it’s not time to go to them yet.

Much later, you get access to a flying whale (seriously) and a similar thing happens: there are handful of new areas you can go to, but you’re not allowed to have any fun until you’ve found and accepted the appropriate side quests that tell you to go to those locations. You can also see locked doors, but you get the key that opens them after you get the whale.

Side note: summoning the whale can only be done from a few locations, and takes forever. It plays a (boring) cutscene every single time you summon it. If you’re on the ground and want to go to a location you can only reach by whale, you have to warp to a place you can summon the whale from, which plays a loading screen, then watch the cutscene and then watch another loading screen. You can warp directly to on-your-boat, but you can’t warp directly to on-your-whale for some reason.

One particularly egregious thing is that there are a handful of books – reading books is a minor game mechanic – that when you read them, your character opens it up, then says something like “…but he realized he’s not ready for it quite yet.” So that’s fun. You have to just remember where they were, or else just re-explore everywhere later.

You will, in general, have a better time playing the game if you never, ever, ever go anywhere the game hasn’t explicitly told you to until the end of the postgame. What you find is uniform: crafting materials you can’t take advantage of, large clearings that are obviously going to have events later, and locked doors that you have to remember manually.

Gender Politics

I’m going to keep this short, because this post is huge and not really about the world of the game so much as its mechanics. However, it bears pointing out that the game has a constant stream of minor comments about hot girls. There are a small number of townsperson character models that are reused throughout the various towns in the game; one of them is a dancer girl. There is basically always a man watching the dancer girl and mentioning that she’s hot. There is a side quest that is “dress Jade up like a bunny for a lecherous old man.” There’s also the whole “puff-puff” thing; you can talk to various women in the game to perform the “puff-puff,” which has no effect on the story and is usually the set up for some kind of gag, but is also obviously a sex joke.

I have no issue with video game characters being hot. Costume changes aren’t very important to me, but they are cool, and some of them being hot is totally fine. But the game shouldn’t casually throw a stream of misogyny at you.

Miscellany

There are moves where it is hard to tell what stat is used to calculate damage. In particular, Rab is a character who can be either a physical or a magical fighter. Some ways into the game, he learns a move that, it turns out, uses strength rather than magical might to calculate damage. The game doesn’t tell you that, though; I had to look it up. Jade, similarly, has a number of moves based on her charm stat. Sylvando might, too; I didn’t check.

The game has a day/night cycle and a weather system. These almost never affect anything, but when they do it’s uniformly annoying. The day/night cycle is very long, and mostly you are just in day because when you rest, sleeping until dawn is the default option, and you’ll probably be sleeping enough that you’ll reset to day before it becomes night in most cases. I must have been 10+ hours into the game before I saw the day/night transition animation. Your camera is temporarily taken over and you stare into the sky, which then darkens. I thought it was some sort of important story event starting unexpectedly at first. It’s not elegant. The weather system is even more boring: sometimes, it rains. There are some enemies that only appear when it is raining, so if you are interested in fighting one of those enemies, you find a campsite and sleep over and over again until it rains. There are cows that tell you the forecast, but they’re not immediately adjacent to campsites, so they are absolutely useless – sleeping over and over is faster than running back and forth to the cows. You can sleep until four times – dawn, noon, dusk, and night. The only differences are between day and night, and sleeping until dusk does nothing but get you the weird transition animation faster, so there are four choices but only two categories.

Speaking of sleeping, it does not restore your dead characters to life. This doesn’t actually matter, because you learn Zing (the life spell in the game) reasonably early, and restoring characters to life is one of the functions of the (again, wonderful) handy heal-all. You can also pay for resurrection, but spending mana and then sleeping is always better. Sometimes, though, you’ll forget that some characters are dead, sleep, assume you’re healed up, and then start a battle down one or more characters. This is a really stupid gotcha, and provides the opportunity to have a feel-bad moment with no upside, because it doesn’t actually add strategic depth.

Churches (and statues, which are like churches but they appear outside of towns) provide a number of functions, most of which are stupid. They do saving, which is good. And later in the game they allow you to reassign skill points, which is cool. They also provide divination, which prints out about five thousand lines of text telling you how much exp each character needs. This information is freely available at all times, in a way that’s easier to get to and faster to read, but the game doesn’t tell you that, so until you stumble across it, if you care about the answer, you have to use a terrible interface for it. Reviving dead characters, as above, is handled badly. They will also remove poison and curses, which are dumb for the exact same reason revival is.

Good Things

Just to balance out the negativity here, I’d like to include some good aspects of the game.

The music is quite good. Apparently a lot of people took issue with the music, but it was good for me. I generally have on a stream or TV or something while I’m playing, and it was inoffensive and catchy as low-level background music.

A huge fraction of names (of items, monsters, abilities, etc) are puns, which is first distracting, and then sort of groan inducing, but is so thorough that it’s eventually just sort of part of the game, and the jokes are often pretty good.

The combat system is mostly a traditional turn-based JRPG system, but with a compelling tweak: different attacks target either single enemies, all enemies, or groups of enemies. Target-all abilities are in short supply, and having to think about enemies in groups is an interesting way to do combat. I’ve never played a Dragon Quest game before, so it’s possible this is an ancient innovation, but it was new to me and I liked it.

The game is arranged in three acts. You retread a lot of ground in the second act, and to some extent again in the third, but the game handles it well. New treasures appear, of course, and enemies power up. The atmosphere changes dramatically, as well, which helps it feel fresh, and you’re allowed to go through things much more quickly the second and third times. I thought it was very well done.

I fucking love the slimes. Drake slimes are my favourite, I think.

The third act, when you have access to everywhere and everything, is good. It’s a pretty nice world to run around and explore in, once it starts letting you rather than punishing you for trying.

The crafting system is good. It requires a little care, but not too much. If you’re good at it – or overleveled for whatever you’re making – you can make your crafted items stronger. It feels like something real, whereas it easily could have felt like a speedbump in the way of getting your gear. But it didn’t feel like something I had to master, so I think it hit the sweetspot pretty well. It does have one truly bizarre misstep: late in the game, you get access to a second category of crafting actions, and you simultaneously get the first action in that category. But… it’s the only action in the new category. It’s like the developers just forgot they started this new thing, or perhaps they had more options in there but got rid of them and never reworked it. This doesn’t make the game worse, but it’s a totally unforced error.

Early on in the game, your revival spell has a 50% chance of failing, which is pretty interesting. It’s a neat way to add tension to some early boss fights.

Note: I wrote this a couple years ago, and abandoned it because it didn’t have a satisfying conclusion. It’s not a great story narratively but I still think it’s interesting, so here it is!

Some years ago, my coworker Zack wrote a a chess engine in Rust, to which I contributed a bit. Recently, my coworkers and I have started a new game of office chess against it, and it turns out that it runs too damn slow. On an early board position, it didnt come up with an answer after running on my macbook pro after about 8 hours when searching a 9-ply tree. And then the next day I ran it with an 8-ply search and 8 hours was once again insufficient.

I decided to try to make it fast, and then got sort of obsessed for a couple weeks and knocked out, depending on what task you’re running, 60-80% of the runtime. For the rest of this post, assume I’m running all timings against this position (sure hope it’s representative, lol).

An Extremely Brief Introduction To Chess Engines Using α-β Search

This isn’t what this post is about, so here’s the least you should need to know to read this post: Chess is a two-player perfect information game, so it permits an α-β search for finding moves. What you do is go through each move from a position (a ply), and then recurse; when you bottom out (however deep you wanted to search), you score the position based on some heuristics and go back up the tree. You use some algorithmic magic stuff to stop looking at trees when moves are really good or bad.

Chess games can reach the same position via multiple paths (transposition), so you want to cache positions that you’ve already scored, again to avoid looking through big trees of moves, which takes forever because of exponents.

What Not To Do

I don’t recommend taking this approach, but I had an idea for how to speed up the program before I bothered profiling anything, and it turned out I was really, really right. When we were caching the scores for various board states, we were caching the entire series of moves from the start state to the end of the recursion (the variation). That’s a ton of wasted space, and this is a very memory-hungry application in order to cache results as effectively as possible. I didn’t profile the exact mechanics of where things improved because of it, but I moved to only stashing the remaining part of the variation, so we can still stitch the full variation back together higher up in the stack, but save a ton of memory. This was worth a 30-50% speedup; you can see the implementation in this small patch.

In general, “have ideas” has been by far my least successful technique. Most of the things I’ve changed on a hunch have had non-noticeable or even negative impact on performance. Don’t be like me. Profile your application.

On The Right Track

Next up, I made a bunch of random changes and couldn’t tell if any of them helped or not. Eventually I got serious and started using tools. The first thing I tried was cargo-flamegraph, which doesn’t work very well on macs. (Foreshadowing: this story is about to come to the part where I have a second personal breakthrough). I spent a while doing horrible nonsense like booting in recovery mode to disable security settings, and ultimately found out that the tool just doesn’t follow threads on mac OS.

Next up, I found the tool cargo profiler, which installation tools start with “NOTE: This subcommand can only be used on Linux machines.” So I realized if I’m trying to profile code in an immature systems language, I need a Linux box. Fortunately, the cost of 1 Linux VM on EC2 is $0, so from here on out I was mostly developing on an Ubuntu instance.

Tools

I found that cargo flamegraph was extraordinarily valuable. Cargo profiler basically didn’t work for me, and I ended up just running valgrind myself, but the results were less useful than I had hoped. Probably this is a me problem. I mostly leaned on flamegraphs, which are wonderful.

Here’s an interesting portion of a flamegraph from this point.

(this isn’t the bottom of the flamegraph, but it’s a relevant part). The bottom row here, if you squint, says it’s in the α_β_negamax_search function. Everything above that is various function calls that the app spent time in while also inside the lower function; each column is sort of a cross-section of stack. So a wide column means we spent a lot of time in that function while it was also inside all the functions below it. Here you can see from the second row that while in this depth of the α_β_negamax_search call, we spent a little in a function (in orange) that I can hover over and see is called WorldState.reckless_lookahead; about 1/4 in order_movements_intuitively, and most of the rest in another recursion into α_β_negamax_search.

This is really valuable information! It was very surprising that we’re spending ~20% of our time in order_movements_intuitively, because it’s just a sort of a list with < 50 elements!

fn order_movements_intuitively(experience: &HashMap<Patch, u32>,
    commits: &mut Vec) {
    commits.sort_by(|a, b| {
        let a_feels = experience.get(&a.patch);
        let b_feels = experience.get(&b.patch);
        b_feels.cmp(&a_feels)
    });
}

The first thing I did was switch sort_by to sort_unstable_by, which the docs say is usually faster if you don’t care about stability. The docs are right! But it was still too slow. Next up, I — well, I combined a few functions together, because we were sorting and then immediately re-sorting with a different comparison function, so this part isn’t as narratively compelling — but then I pulled the cache lookups out of the comparison function. This was enough to plummet order_movements_intuitively down from 20% of the time spent in the negamax function to like 4%, which was great. And it’s the second time in a row that fixing the use of hashes was a big performance win, which it turns out is not a theme; there was just some serious low-hanging fruit there.

Rust Specific Insights

So far, all I’ve done is notice and correct what amount to a couple of significant design flaws. The tools helped me catch the second one, but as it turns out we’re out of this sort of problem. The rest is much harder.

The reason it’s hard is actually a good thing – Rust is really fast. It mostly doesn’t do stupid stuff, and just goes really fast and eats up as much CPU and memory as you’ve got lying around. This is, you’ll note, really fucking cool, and this is one of the reasons writing Rust is fun, especially for a filthy interpreted language pleb like myself. Unfortunately, for all that, it still does get harder.

The next big issue I saw was that some of our functions were spending up to half their time in Vec::extend and/or Vec::push, which themselves are spending a lot of time in low-level stuff like malloc, realloc, and free. This is the part where the project became really fun for me – I write Python in my day job, mostly, and writing python does not tend to lend itself to performance hunting on the level of “too many mallocs.” So the next step is to remove allocations.

This consisted of two main things. The first is using Vec::with_capacity to pre-allocate an appropriate amount of memory for my vectors. Sometimes I had known lengths (e.g. in the sorting of moves as seen above); sometimes I had known maximums (e.g. there will never be more than eight pawns owned by a particular player); sometimes I had good-enough guesses to feel pretty good about it (e.g. there will be more than 2 bishops in few enough positions that it doesn’t matter). Sometimes I had reasonable guesses – I’ve read that most chess positions have in the neighbourhood of 40 moves.*

The second thing is just not creating vectors in the first place. One of the main move-generation functions was delegating to a bunch of sub-functions to generate moves for each piece type and then pushing all those results onto one result vector. I changed it to pass a mutable, pre-allocated vector around and extend onto that.

These changes resulted in allocation-related time spent in the relevant function to drop from ~50% to like <5%, and some other allocations further down the stack to disappear from the perf tool’s sampling entirely.

At this point, from the starting point of right after I fixed the issue with storing full variations in the hashmap to right after I fix all these reallocs, I’m seeing time on a depth 6 search of the relevant position going from about 50-60s to about 30s.

The Bad News

The bad news is this is about where I ran out of ideas and/or energy. I had the temerity to make a couple more small changes by following basically the above pattern, but no more big wins. A couple things showed up that I thought were dumb, and I stamped them out – using a different hash algorithm for some data types was a big improvement on a micro-level but didn’t have a substantial impact on realistic workloads, for example. The program also uses immutable structs for various purposes, including the list of squares on the board and the list of pieces by team; moving those to static variables and returning them instead of re-allocating new ones when they’re needed, again, showed a pretty impressive improvement on the micro benchmark but minimal improvement on actual runs.

What’s left is that there’s just not much to strip out. The program’s threading model could be improved – we kick off one thread per move at the top level position, which frequently results in one expensive move’s calculation taking a long time after the other threads are done. I’m not sure how to make that better while still getting the α-β search benefits.

* I don’t know if this is true, or where I heard it. From unscientifically checking some positions, I’m seeing that 40 moves covers >= 90% of them.