Avoiding Work (on the main thread)

I'm working on a CPU opponent for Mark My Words because I believe it's a very fun game that a lot of people will like, but it can be difficult to find an opponent.

Since the game is similar to Scrabble in many ways, I did some research on algorithmic strategies for Scrabble, hoping to adapt them to my game.  One of the interesting things I learned about is a GADDAG, which is a specialized Trie that makes it easy to look up words starting anywhere in the word.  I already was using a Trie for an experimental feature, so I figured I'd replace it on my way to a CPU opponent.

While GADDAGs enable quick lookup during the game, this comes at the cost of significantly more precomputing.  When I did a naive replacement, I noticed that the game became unresponsive for a few seconds while initializing the dictionary.  Immediately, I thought "This is a perfect time to bust out an Isolate and do this work on another thread."  And it was!  But, when I went to test in the web build, I discovered that Isolates are not supported on web!

I looked into it and discovered that compute addresses this.  Sort of.  It runs stuff in an Isolate in supported platforms, but still on the main thread on web.  I'm back to functional, but unresponsive.

I've got PLENTY of javascript/typescript experience, so this immediately made me think of somehow turning this initialization process into an async process.  But it's not like a http request where there's a lot of waiting around doing nothing.  All this work still has to be done locally.  But, it doesn't have to be done all at once.  All we're really doing in the initialization is adding every word in the wordlist to the GADDAG.  The order doesn't matter, it's even idempotent.  This is completely parallelizable!  But the event loop is still single-threaded, so not really.

So I built a poor-man's multithreading for this task.  Chunk the wordlist (I arbitrarily chose 500 word chunks), then for each chunk create a Future.delayed which adds all those words to the GADDAG.  Use Future.wait to gather all these (even though they are Future<void>) so we don't exit early and Bob's-your-uncle.

This seems to work very well in practice.  I did not notice any unresponsiveness even when I know that the dictionary loading process is ongoing.

While I was at it, I refactored the dictionary population to go through a Riverpod provider, and used cross_cache to cache the raw Uint8List I get from the Firebase Storage bucket I keep my dictionary wordlists in.  So now I keep a local disk/indexeddb cache, as well as an in-memory cache of each of the dictionaries loaded during the app session.  This means I can avoid:

1. The expensive dictionary initialization - if I've already done that this session
2. The Firebase read and download - if the user has already done that once for the dictionary in question.
3. A lot of work searching for words that fit the board, using the GADDAG.

Wonderful, but there's still a lot of work to get to a functioning CPU opponent.