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