avoid repeated scanning of the metadata entries during formatting

there was a test that had never been working, meaning the entire entry array was being scanned for every byte of output. even had that test worked, it would still have scanned on average half the array for every byte, so that'd be where the absurd runtimes were coming from. anyway, it works now.

this gets a full hex transform invocation down from over thirteen minutes to under thirty seconds. learn your data structures and algorithms, kids.

Force-Push: yes
Change-Id: If075b256f77649fae9d2e56cb7404458ca39d189

1 files changed, 40 insertions, 9 deletions

diff --git a/transform.e b/transform.e
index 6d5907c..25442c2 100644
--- a/transform.e
+++ b/transform.e
@@ -3986,11 +3986,41 @@ allocate-transformation-state s" transformation-state" variable
 
   postprocess-metadata-entries
 
-  { over 0 <= } {
-    transformation-state transformation-state-output-metadata @
-    hex-output-metadata-first-entry
+  ~   Importantly, postprocessing leaves the entries sorted, which means we
+  ~ can go back and forth in a linear scan through the entry array while we
+  ~ also do a linear scan of the output data. It's fiddly, but we can't afford
+  ~ to be O(n^2) here, it adds up to quite a lot of runtime.
+
+  transformation-state transformation-state-output-metadata @
+  hex-output-metadata-first-entry
+  ~ (length to write, base address, initial metadata scan pointer)
+  { 2 pick 0 <= } {
     ~ (length remaining, current output address, metadata scan pointer)
-    { dup @ dup { dup 2 pick >= drop } if } {
+
+    ~   Keep inspecting entries as long as the output address is greater than
+    ~ or equal to the entry address. If we're looking at the entries that come
+    ~ before the output, this will scan through all of them first, then
+    ~ eventually catch up. Since the scan pointer is kept across iterations,
+    ~ it's important we not go beyond that point.
+    { dup @ dup
+      ~ (length remaining, current output address, metadata scan pointer,
+      ~  entry's data start, entry's data start)
+      {
+        ~   This is an nop, but for clarity's sake it's best to not depend on
+        ~ details of the structure layout that perhaps not everyone has
+        ~ memorized...
+        ~
+        ~   To get into this block, we tested for the array end indicator, but
+        ~ now that we know we have an entry here, we're looking at its
+        ~ contents.
+        hex-output-metadata-entry-data-start
+
+        dup 3 pick
+        ~ (length remaining, current output address, metadata scan pointer,
+        ~  entry's data start, entry's data start, current output address)
+        >= swap drop
+      } if
+    } {
       dup @
       2 pick = {
         ~ We found a matching metadata entry.
@@ -4187,9 +4217,9 @@ allocate-transformation-state s" transformation-state" variable
       } if
       hex-output-metadata-next-entry
     } while
-    drop
+    ~ (length remaining, current output address, metadata scan pointer)
 
-    over {
+    2 pick {
       is-fresh-line@ {
         indentation-depth@ dup indent advance-current-column
       } {
@@ -4197,14 +4227,15 @@ allocate-transformation-state s" transformation-state" variable
         1 advance-current-column
       } if-else
 
-      dup 8@ .hex8
+      over 8@ .hex8
 
       2 advance-current-column
       0 is-fresh-line!
     } if
+    ~ (length remaining, current output address, metadata scan pointer)
 
-    1+ swap 1- swap
-  } while ;
+    3unroll 1+ swap 1- swap 3roll
+  } while drop ;
 
 ~ (data start, data length)
 : hex-pack-trace