My 3-Line Diff

2026-03-27

About 10 years ago, in 2016, I wrote a cellular automaton simulator called Reasoning Realm, which was not very good. I was an inexperienced programmer at the time and ended up implementing an algorithm (referred to in the programme as "Ignore Non Changing Cells") which simulates only cells in a pattern that have changed, or whose neighbours have changed, in the previous generation.

I implemented it in an O(N²) fashion, where N is the number of cells that are being simulated. For large patterns with only a small number of cells changing, it's still an improvement, but when larger amounts of change happen it slows to a crawl.

I last updated Reasoning Realm in 2018, but decided to revisit it specifically to patch this massive performance issue. It took barely a few minutes to figure out how to do it, and I made the following 3-line change (and if you're not aware, the proverbial "3-line diff" is apparently an in-joke in the OpenBSD community):

--- RR0.3.1.html        2018-12-19 04:15:43.000000000 +0000
+++ RR-dev.html 2026-03-27 08:28:47.257789917 +0000
@@ -448,12 +448,9 @@
 }
 
 function inSparse(x,y){
-  for(ib=0;ib<nextSparse.length;ib+=2){
-    if(nextSparse[ib] == y && nextSparse[ib+1] == x){
-      return true;
-    }
-  }
-  return false;
+  var ret = nextSparse['x' + x + 'y' + y];
+  nextSparse['x' + x + 'y' + y] = true;
+  return ret;
 }
 
 function fillSparse(){

This was one of those morale-boosting moments where I realise how much I've improved as a programmer in the last ~8 years. This used to feel like some huge insurmountable problem with the code and now it's trivial for me.

It's not actually 3 lines if you count the deletions, but never mind. And it's not really a very good solution, since it requires making a string and using it as a key. It's definitely not what I'd do if I were programming in C or assembly, but it's still much faster than O(N²). Also, you may have noticed that the old code used a global variable as an iterator; that particular mistake is all throughout my old JS code in general, because I didn't understand scoping.