mrjace / standup5x5 Goto Github PK

My solutions to the problem posed by Matt Parker of Stand Up Maths

See: https://www.youtube.com/watch?v=_-AfhLQfb6w

Just run make and execute ./a25 -v, ./s25 -v, ./v25 -v or ./525 -v

NB: Omit the -v option if planning to use the time shell call

I've set the default compiler to clang-12 in the Makefile, as this produces the fastest executables in my testing, but edit the Makefile and switch to gcc if that's what you have

a25, s25, v25, and 525 all support the -v option which will emit run-time metrics If measuring with the time shell call, be aware that it typically takes about 1ms for an executable to get up and running, the times reported by time will be slightly higher than the internally measured times. Also, the time taken to print the metrics can become a non-neglible factor at these low execution times.

For speed, all solutions are written to a file named solutions.txt in the current directory

[a25|s25|v25|525] [-v] [-t num_threads] [-f word-file]

• -v : Normally no console output is produced. -v allows the executable to emit metrics
• -t : Allows the user to specify the number of threads to use. By default the executables will use 1 or 2 less threads than there are CPUs on the system
• -f : Allows the user to specify an input word file to use. By default the executables will use the words-alpha.txt file

My development systems are a desktop AMD 5950x based PC, and an Intel i7-1165G7 based laptop. On my AMD system, which runs at a fixed at 4.7GHz CPU clock with hyper-threading disabled, the following (internal) times are seen, which include the loading of the full 4MB words_alpha.txt file:

a25 takes around 18ms to complete, using 16 threads

s25 takes around 0.98ms to complete using 16 threads

v25 takes around 0.82ms to complete using 16 threads

525 won't run on my AMD system. On my Intel laptop it takes 1.35ms to complete using 8 threads. I estimate that on a full desktop runtimes of 0.80ms should be achievable

All algorithms use a bit-wise representation of the words for efficiency of comparing

All algorithms also implement lockless thread co-ordination for speed.

My first attempt at a solution (source not included) focused on the New York Times wordle list, for which there is 10 valid solutions. It split the word set into 2-vowel and 1-vowel sub-sets, and utilised the fact that all actual words must have one vowel in them (vowel being a, e, i, o , u, y). This meant that there could be either 5 words with 1-vowel, or 4 x 1-vowel words and a single 2-vowel word as valid solutions. That code just did a straight reduction search on the 1-vowel set, which for the NYT Wordle List, only meant a little over 1-thousand 1-vowel words. The single 2-vowel set was then run over all 4 x 1-vowel sets to find solutions. This ran extremely quickly, being able to find all 10 solutions in around 1.5ms

After commenting on the Youtube video, I then discovered that most people were using the full words-alpha.txt file as a starting set, and even crazier to me, people were using the full ~4MB word set, instead of at least using just a set of only the 5 letter words. Okay, I guess?

My first solution did not work properly on the words-alpha input set as that set contains many words with no-vowels in it, thereby breaking my assumption that all valid words should have at least 1 vowel.

So I needed to redesign

This was my 2nd attempt at a full solution. It implements a more generic version of my first attempt. Instead of using 2-vowel and 1-vowel words, it split the input set into one set containing the most frequently character, which also handily happens to be a, and everything else. Using my first approach, this generates a set of 4-word partial solutions from the non-a words. For completeness it also tries to find 5-word solutions using all letters but a, but none exist.

Once all 4-word partial solutions are found, the a set is combined with the 4-word solutions to find all 5-word solutions.

This approach works very well and is very fast, but the idea of splitting the input into multiple sets grew into my third solution attempt.

I've included combos.c which is non-functional pseudo-code that formed the basis of s25. I wrote a frequency implementation that originally ordered all words from most the frequently occurring letter to the least. This approach produced just 9 word sets to represent all words and was easy to combinate over.

After putting it all together, it worked, but quite slowly. Taking about 50s to run. I then remembered some of the comments in the Youtube video about trying from least-frequent to most-frequent, so I reversed the sort order, and the solution now completed in about 15s. This was still disappointing.

I then realised that we only need to use 25 letters out of 26, and so I tried stopping the combination sequence 1 set short of the full combination set. Doing this got the execution time down to under 1s while still finding all 538 solutions.

After this, I starting looking at other solutions online, and came across Sylvester Hesp's solution, and to my surprise, we had both essentially developed the same solution. Where I was focusing on combinating over sets, Sylvester was combinating over letters, but the actual implementation was extremely similar in a remarkable example of convergent design.

Sylvester's work is here: https://github.com/oisyn/parkerwords

I then saw how Sylvester had solved the 25 instead of 26 approach with his clever skipping implementation that skips at the start of the combinator, instead of my approach that skipped at the end. His approach actually applied perfectly to my code (I owe a huge debt of gratitude to his solution to this issue), and with that the initial implementation of s25 was running in around 4-5ms for the actual main algorithm loop, and ~5-7ms to load in the the words-alpha file, with overall run-times ranging from 9-14ms depending on what the system is doing. Run times were signiciantly less if using the words-alpha-five.txt or NYT files as input.

v25.c is just s25.c but with AVX2 instructions added for processing the key sets. The use of AVX-2 saw the main algorithm loop be sped up by almost 3x. This is my first time ever playing around with AVX instructions, so it was a fun learning experience.

525.c is v25.c with AVX-512 instructions, instead of AVX2. This will not compile successfully on any platform that does not support AVX-512.

AVX-512 will run the main algorithm in around 65% of the time of the AVX2 version. Of course, file load times are still a significant factor, and so I'd expect to see overall run-times at ~75-80% of v25 run times. Sadly I do not have a high-end AVX-512 capable desktop to verify this claim, although these ratios were true on the AVX-512 laptop.

A large problem I dealt with was how to quickly read in and process the 4MB word file. My first attempt just processed the file with a straight mmap() and that saw the file get read in and processed in around 7ms. My second attempt used multiple threads, which each thread working on their own portion of the input file. This worked fairly well, but hash table building was a large source of contention. Additionally, the system doesn't really like many threads jumping about all over a single file.

My final solution was to set the readers to incrementing an atomic integer to gain access to the next 8KB block of the file. This improved locality and also ensured a (mostly) sequential step through the file, which boosted file reading times dramatically. I then had the readers focus on finding 5 letter words and inserting them into an array, with an atomic integer defining where in the array any particular reader would insert their word.

I then had the main thread process the word array that was being built by the reader threads to build the hash table concurrently. Doing all this together managed to get file load and hash table build times to under 0.7ms on my AMD system.

About mid-way through the frequency set build, we rescan the frequencies and re-order the remaining sets from most-frequent to least. The works because the bulk of the benefit from the least to most frequent ordering has already been gained by this stage, and reducing the length of the combinatorial "tail" has an amortizing effect of more than making up for the increased set sizes mid-algorithm

I moved all the file reading and other utility functions to a common utilities.h file that is included by the main algorithms. In this way, any future tweaks should be consistent across all implementations

I received an email from Landon Kryger about his solution here: https://github.com/GuiltyBystander/5words

Landon had come up with the most efficient implementation of the search problem I'd ever seen. Truly fantastic work! Landon says that he arrived at his solution also fairly independently, but at its core it uses the same basic algorithm that Sylvester and myself had found.

Where Landon went one step further is that he had added a further breakdown of the search space, where the presence (or not) of the most common letters is used to divide each set further, such that when progressing through the sets, characters that are already seen are used to eliminate sub-sets of the sets from being considered. This comes at a cost of a somewhat high amount of set up overhead, but for a single-threaded solution, his was simply the fastest around.

Landon was looking for someone to collaborate with to help make his solution faster. I spent some time analysing how his algorithm works, and while it is extremely clever and elegant, it is somewhat difficult to parallelise the setup steps, and the bit-mask remapping he implements which is essential to the speed of his approach consumes a significant amount of CPU time, and also forces a point of linearity to derive the mapping. The remapping of the bitmaps can be parallelised, as can the set building, but spatial locality issues arise from the data being scattered across many different arrays/vectors.

As a direct comparison, even though Landon's solution makes 30x less comparisons during the search phase, his algorithm is just 3x faster when using a single thread. I think we can implement a solution true to his original vision in a highly parallelised manner, but it would be a fair amount of work.

So instead I worked with Landon to arrive at a hybrid solution that isn't as elegant or as flexible as Landon's core solution, but preserves the strong spatial locality inherent in the "pointers within a single set" approach that my solution implements.

With that, I updated s25.c, v25.c and 525.c to implement this hybrid approach, and huge speedups were seen in low thread numbers, but smaller speedups as threads are increased.

v25.c is now capable of finding all 538 solutions on my system in under 1ms including loading the 4MB words-alpha.txt file, solving, and writing the results out. Even using just a single thread takes under 6ms.

Where Landon's approach uses the 6 most frequently occurring characters to create subsets from, the hybrid solution only uses 2, and it is still slightly slower than Landon's solution for a single thread scenario for non-AVX mode.

Update: The master branch has 6 tier code now

I was able to parallelise the tier setup paths. This has resulted in the setup for 6 tiers taking only 10us more than the setup for 3 tiers. As a result, the 6 tier path is now the fastest in all scenarios.

Update 2: I discovered a low-CPU-cost way to calculate the best characteres to use to split subsets for each character set. Main algorithm compares were reduced by 33%.

I'm including the words-alpha file, plus a version of words-alpha that only has the 5-letter words in it, as well as the NYT Wordle sets. It seems silly to me for us to be spending time finding ~80KB of 5 letter words from a ~4MB file but since that's what people seem to be doing, so I included the full set here.

Thank you to Matt Parker for making the problem public, and all the intelligent and robust discussion of solutions in the Youtube comments, and a big thank you to Sylvester Hesp for his approach to the set skipping issue, and to Landon Kryger for his insightful algorithm improvements!