Home
Creators
Search Recent Missing Random
Posts
Search DMs Popular Hash Lookup Tags Random
Importer
Import FAQ
Register Favorites Keys Review DMs Logout
Community
Telegram ThePornDude
Home Creators Posts Import Register Favorites Logout

Can you time-trial some code? (Patreon)

Published:
2022-08-07 11:35:44
Edited:
2022-08-07 16:53:30
Imported:
2022-08

Content

UPDATE: Now with ≈20 bits of code.

As you may have noticed: the 15 minute runtime for five-letter-word code in my latest video has since been beaten. From 32 days for my original code, to 15 minutes from Benjamin Paaßen the record now seems to be 0.077 seconds (C++ code on a AMD Ryzen 5800X by Sylvester Hesp @oisyn).

Much of the chat happened under this tweet: https://twitter.com/standupmaths/status/1549343218407456769

I think a follow-up video is in order and I'd like to make it fairly soon. But as part of that it would be great to compare the different bits of code all running on similar hardware. I've collected up I-think-all of the bits of code people have sent in. I've listed them on the form page (not all will make the video). You can click through if you just want to have a look at them: https://forms.gle/o6DmDBdrvRsBuTEC7

If you have a chance to run some of them yourself (languages used: Python, C++, Rust, C, Java, Julia, Go) please do log your times (in seconds) in the form.

Do also make any comments below about what you'd like to see in the follow-up video! Here is my current reading list:

https://medium.com/@encody/how-to-speed-up-your-code-224-444-739-using-graphs-cc37dc395c0chttps://github.com/holmesrichards/ncliquehttps://arxiv.org/abs/cs/0011047https://digitalcommons.butler.edu/cgi/viewcontent.cgi?article=4100&context=wordwayshttps://digitalcommons.butler.edu/cgi/viewcontent.cgi?article=1275&context=wordways

PS There are a bunch of words in the Wordle list which were not in my original "words_alpha.txt" list which allow for more 'Wordle approved' solutions: bling, brung, grypt, gymps, pling, treck, vozhd, waqfs

Files

Patreon code time results

Thanks for taking the various five-letter-words problem bits of code out for a spin! Please use consistent hardware across all runs and enter the fastest times below. Enter times in number of seconds. Leave any you didn't test blank and just fill in whatever times you have.

Comments

Nathan Baulch

I emailed you (matt@aproblemsquared.com) with my Go (aka Golang) solution 2 weeks ago but I guess you didn't see it. 🤷

e38383

I submitted some times from a MacBook Air M2. oisyn was so fast it was barely measurable, somewhere between 0.3 and 0.5 seconds. I gave up my own try after realizing it would run for days ;)

Gianna J

Seeing that the first one is only using about 7% of my CPU, you've got me thinking about how I would parallelise such a problem 🤔

Tim

oisyn writes out the time so you don't need to measure just read the output

e38383

That's what I meant … it is between 0.3 and 0.5, most of the time it's just short of 0.41.

standupmaths

Sorry I missed that. I only double-checked for code that came in recently. Your Go entry is now in the list!

standupmaths

That ridiculous! I've added your code to the list.

e38383

WOW! That's just epic. I can confirm that it runs in <0.1s and is 3-4× faster than oisyn's.

Frank Gevaerts

Benchmarks are running while I'm cooking. So far it looks like there's three of them that I can't get to run with trivial effort (one c++, one rust and one julia). I might have another look at those later. (edit: I got them all to run. Nearly ready to submit results) (edit 2: delayed by more code to run)

Alex

If I want to run on 2 different machines, how would you like that submitted? I have a 5900x desktop as well as a M1pro macbook.

epinardscaramel

Done! Could only test the python code though.

Alex

I can't seem to get yours to run. Looks like there's lots of extra setup that is needed to get go files to run... I installed golang and tried to run the file, but there's required modules that need setup...

Nathan Baulch

Go should take care of dependencies automatically, you just have to `go run . words.txt` in the folder. Nevermind, I've removed the progress bar and other dependencies so it's completely standalone now (though not as pretty). 👍

Andrew Weir

I submitted results on the original form, didn't get to add results for the extra repositories. Do I need to resubmit everything, or can I make a second submission for the new repos?

Alex

Ran this in powershell: PS C:\Users\Alex\Python\Five Words\nathanbaulch> go run . "words_alpha.txt" result: go: go.mod file not found in current directory or any parent directory; see 'go help modules' In windows subsystem for linux got: ./main.go:20:23: undefined: io.ReadAll Edit: Got it working in linux, had to revert your change on line 20 back to "ioutil" instead of just "io" If you're on the discord, I can work with you in chat.

Nathan Baulch

I'm not much of a Powershell user but can you try: `$env:GO111MODULE='off'; go run . words_alpha.txt`

Alex

Yep, that worked for powershell! Gave the same io error, but with the reverting change I made back to ioutil, it gave me the output.

Jake McLeman

Done! Thanks for cluttering up my hard drive :D

Nathan Baulch

I'm a bit late to the party, however... I've managed to get 16 of the submissions working in Ubuntu 22 and have created a script that automatically downloads, configures, compiles, runs (x5) and compares the results using the nifty "hyperfine" benchmarking tool. Script: https://gist.github.com/NathanBaulch/8668695a19ac9fbfc78fa3cc24b83b0b Results summary: https://imgur.com/a/BUVnMpQ This should help anyone else who wants to run a (near) comprehensive comparison on their hardware.

Frank Gevaerts

I have three extra running ones in my set. bpaassen and holmesrichards are both python, not sure why you had issues with those. The other one is pyaggi, which needs -std=c++20 to compile (works with both clang++ and g++ for me) (so you need a new enough toolchain, presumably, but as far as I can tell ubuntu 22.04 has the same or newer versions compared to my laptop).

Leonardo Taglialegne

Me and oisyn have been out-optimizing each other a couple times now, both our versions are faster, to the point where we are trying to optimize _reading the file_ :D

Nathan Baulch

Cheers for the sanity check Frank, I actually did have those extra ones originally but removed them since they were a little slow and my old-ish laptop was getting tired after a long day crunching hyperfine tests (it runs each submission 5 times plus a warmup). I've add them back in (plus the new dotnet one below) and introduced a 2 minute timeout to keep the overall run time reasonable.

Frank Gevaerts

It's very annoying, I'm having to re-run my benchmarks again! :)

Frank Gevaerts

For those working to get the last millisecond out of the code, I'm noticing that the oisyn program is 30% to 50% slower when compiled with gcc than when compiled with clang, on both amd (31ms vs 22ms on my laptop) and arm (104ms vs 71ms on a raspberry pi 400). Both oisyn and miniBill allocate around 5MB of RAM, which with code and runtime overhead seems to add up to around 7MB of total RAM use. These things could easily run on a higher end 486 system! (edit: I looked up some CPU benchmarks, and the numbers say that oisyn's code should take between 1 and 10 minutes on a 486 DX2/66, i.e. 1992 tech)

Frank Gevaerts

My quest is complete (enough). I managed to get oisyn's code to run on MS-DOS 6.22 on a 486 DX2 133MHz. I only have a C++14 compiler for that (not C++20 as used in the original code), so I started with a slightly older (and slower, sorry!) revision and adjusted things until it compiled. The hardware is an industrial PC from the early 2000s, with a chip in it that has a Cyrix 486 DX2 core, running at 133MHz, with 64MB RAM. It runs in 159 seconds. Assuming a 133MHz 486 is twice as fast as a 66MHz 486, that means a high-end early-to-mid 90s PC would run this in just a bit over five minutes. (edit:) I forgot to turn on compiler optimisation for that! I tried again, this time doing it correctly, and it runs in 22 seconds, so an estimated 45 seconds on our high-end early 90s PC.

Leonardo Taglialegne

Thank you for overdoing this, I am enjoying your experiments

Landon Kryger

Hey Matt, hope it's not too late to update the video, but I think what I found counts as a breakthrough. The fastest algorithm most people settle on does about 95M comparisons of trying to add a word to a word set. My algorithm with Stew's help only does about 1.8M comparisons and lets us finish in under 1 ms, or 0.3 nanoparkers (1 parker = the time it took your code to run). TL;DR explanation is that we sort words into buckets so we can sweep and reject huge chunks of the wordlist instead of testing them one by one. Let me know if you need more details on how it works.