From 8938331915c53e34be8f98002fe8d56d8b7ada08 Mon Sep 17 00:00:00 2001
From: Mark <markjordanthom@gmail.com>
Date: Fri, 15 Dec 2023 00:39:29 -0700
Subject: [PATCH] improve performance of lower_bound_of_target_clause (#1598)

---
 src/lib/builtins.pl    |  1 +
 src/machine/compile.rs | 50 +++++++++++++++++++-----------------------
 2 files changed, 24 insertions(+), 27 deletions(-)

diff --git a/src/lib/builtins.pl b/src/lib/builtins.pl
index 9cb533d1..1a2b35d4 100644
--- a/src/lib/builtins.pl
+++ b/src/lib/builtins.pl
@@ -1238,6 +1238,7 @@ call_retract_helper(Head, Body, P, Module) :-
        ClauseQualifier = builtins
     ;  ClauseQualifier = Module
     ),
+    '$debug_hook',
     ClauseQualifier:'$clause'(Head, Body),
     '$get_clause_p'(Head, P, Module).
 
diff --git a/src/machine/compile.rs b/src/machine/compile.rs
index 296d076f..da2e4bc1 100644
--- a/src/machine/compile.rs
+++ b/src/machine/compile.rs
@@ -42,42 +42,38 @@ pub(super) fn bootstrapping_compile(
     Ok(())
 }
 
-fn lower_bound_of_target_clause(skeleton: &PredicateSkeleton, target_pos: usize) -> usize {
+fn lower_bound_of_target_clause(skeleton: &mut PredicateSkeleton, target_pos: usize) -> usize {
     if target_pos == 0 {
         return 0;
     }
 
-    let arg_num = skeleton.clauses[target_pos - 1].opt_arg_index_key.arg_num();
+    let index = target_pos - 1;
+    let arg_num = skeleton.clauses[index].opt_arg_index_key.arg_num();
 
     if arg_num == 0 {
-        return target_pos - 1;
+        return index;
     }
 
-    let mut index_loc_opt = None;
-
-    for index in (0..target_pos).rev() {
-        let current_arg_num = skeleton.clauses[index].opt_arg_index_key.arg_num();
-
-        if current_arg_num == 0 || current_arg_num != arg_num {
-            return index + 1;
-        }
-
-        if let Some(index_loc) = index_loc_opt {
-            let current_index_loc = skeleton.clauses[index]
-                .opt_arg_index_key
-                .switch_on_term_loc();
-
-            if Some(index_loc) != current_index_loc {
-                return index + 1;
+    skeleton
+        .clauses[target_pos]
+        .opt_arg_index_key
+        .switch_on_term_loc()
+        .map(|index_loc| {
+            let search_result = skeleton.clauses.make_contiguous()
+                [0 .. skeleton.core.clause_assert_margin]
+                .partition_point(|clause_index_info| {
+                    clause_index_info.clause_start > index_loc
+                });
+
+            if search_result < skeleton.core.clause_assert_margin {
+                search_result
+            } else {
+                skeleton.clauses.make_contiguous()[skeleton.core.clause_assert_margin ..]
+                    .partition_point(|clause_index_info| {
+                        clause_index_info.clause_start < index_loc
+                    }) + skeleton.core.clause_assert_margin
             }
-        } else {
-            index_loc_opt = skeleton.clauses[index]
-                .opt_arg_index_key
-                .switch_on_term_loc();
-        }
-    }
-
-    0
+        }).unwrap_or(index)
 }
 
 fn derelictize_try_me_else(
-- 
2.54.0