I've been on a bit of a side-quest recently to make my GADDAG implementation more efficient.  It started when my wife was testing Mark My Words on her phone and iOS killed the game because of memory pressure.

I did a bit of profiling (honestly, I should have before now), and yeah, the GADDAG nodes were by far the biggest chunk of memory in use.  And I had smartly anticipated that I could avoid re-initializing the dictionary from the word list if I kept it in memory during each session.  So when she loaded a second game, using a different dictionary... kaboom.

The GADDAG was doing its job, enabling the computer opponent to find moves.  But it was big and slow.  Slow to initialize (about 9 seconds to load and minimize from word list).  And it was BIG (about 200MB of GaddagNode in memory)

Gaddag is very helpful, he will get the job done. But he is big and slow.
Gaddag helpful. But Gaddag big. Gaddag slow to load.

Now, here's where I usually try AI and it falls on its face and then I write about how I can't trust it and I'll continue doing everything myself.  Well, that's all still mostly true, but I was able to get some actual value out of it this time.  I did my own web research and read about GADDAGs and DAWGs and realized that I wasn't minimizing my prefix-trie GADDAG into a true DAWG.  I asked Gemini's help in writing the minimize method and it pretty much knocked it out.  Of course, it rewrote the entire GADDAG too and I hadn't asked for that.

In the course of rewriting the GADDAG, it took it upon itself to change how the entirely-reversed paths are stored.  It put a path-reversal delimiter at the end and put the "isTerminal" flag on THAT node instead of on the node pointed to by the last (first) letter.  That is: "tac+" instead of "tac" for the entirely-reversed path corresponding to "cat".  I had a long, and unproductive conversation with Gemini about whether this was necessary where it consistently tried to gaslight me about this and made up nonsense test cases that didn't actually prove its point.  Because it was wrong.

I fixed the implementation in the new GADDAG, which meant that I didn't have to change my game board evaluation logic in my actual game repo.  

Now that it was minimized, it was only about 10% of its original size.  But it still took the same 9 seconds to initialize.  In my research I had read of a technique to bake the whole GADDAG/DAWG structure into a flat array of ints.  Not only would this eliminate the object overhead of all those nodes, an array of ints can be written and read from file very easily.

It works like this:  You take your minimized GADDAG DAWG, in which all functionally identical nodes have been canonicalized, and you traverse it in post-order.  Since you're doing leaves first, they'll already have been done when you do the parent nodes.  For each node, there's a header: 1 bit for isTerminal or not, and the rest for how many children there are.  For each child, you write 2 ints: 1 for the transition label (letter), and 1 for the address (index) of the node it points to.  This means your root is the last node written, at the end of the structure, so I reserved the first int to be a pointer to the root.

Gemini was able to write the baking function, and the binary search "getChild" function necessary to navigate the flat dawg.  But it failed to note that binary search requires sorted children until I saw that potential bug.

I wrote a new DAWG class backed by the int array, and because it's hot loadable and requires no parsing, I called it a HotDawg.  And because I wanted a convenience interface to query it as if it had actual node objects, I wrote a DawgWalker.

Now, the .hotdawg files I created which distill the GADDAG DAWG down to a flat int array are smaller than the minimized GADDAG in memory, but still about 4 times larger than the input word lists.  On a hunch, I tried to zip the file.  The result is only a little less than 2 times larger than the input word list.  Since my largest word list is 2.7MB, and the compressed .hotdawg is 4.8MB, I'm quite happy with that. Not only that, when accessing from Firebase Storage, the binary file actually downloaded quicker than the smaller text file.  I don't know what's up with that.  Maybe just network fluctuations.  Maybe the difference between application/octet-stream and text/plain.

Hotdawgs are much faster and leaner than Gaddag

Before:

Time to download the wordlist: 2.3sec

Time to parse/create the GADDAG: 9sec (mostly hidden from the user)

Memory Occupied: 200MB -> 18MB after minimization

After:

Time to download the .hotdawg: 1.3sec

Time to load the HotDawg from compressed data: 49ms

Memory occupied: 13MB

Since I cache the binary file, that 1.3sec is a one-time per-dictionary download, and the Dictionary is ready in-game pretty much instantly.

Did AI help me get this done?  For the first time, I can say unreservedly yes.  Did AI still have a shit-ton of gotchas and footguns, and strangely obstinate hallucinations?  Also yes.  I absolutely still do not trust Agentic AI that codes end-to-end.  But with a firm hand of someone that actually understands the code on the reins, it's not entirely useless.  That's progress.