gnucash stable: [gnc-autoclear.cpp] prune search if remaining amounts are too small

[Christopher Lam]

Updated	 via  https://github.com/Gnucash/gnucash/commit/7c73e2ab (commit)
	from  https://github.com/Gnucash/gnucash/commit/e4d61b30 (commit)



commit 7c73e2ab2c757177c3143bfb9035e2e47fd9120f
Author: Christopher Lam <christopher.lck at gmail.com>
Date:   Sun Nov 16 11:53:37 2025 +0800

    [gnc-autoclear.cpp] prune search if remaining amounts are too small
    
    this optimisation will greatly reduce the search size. first, sort
    splits by reverse absolute amount. then precompute the positive and
    negative sum(amounts) of remaining splits. when exploring any branch,
    if the target is falls outside the range remaining negative to
    positive sums, then any combination of subsequent splits will not
    reach target. bail early.

diff --git a/libgnucash/app-utils/gnc-autoclear.cpp b/libgnucash/app-utils/gnc-autoclear.cpp
index 2a31f5f01b..11fd4d58a4 100644
--- a/libgnucash/app-utils/gnc-autoclear.cpp
+++ b/libgnucash/app-utils/gnc-autoclear.cpp
@@ -69,6 +69,8 @@ struct RuntimeMonitor
 struct SplitInfo
 {
     int64_t m_amount;
+    int64_t m_rem_pos;
+    int64_t m_rem_neg;
     Split* m_split;
 };
 
@@ -111,8 +113,11 @@ subset_sum (SplitInfoVec::const_iterator iter,
             SplitInfoVec& path, Solution& solution,
             int64_t target, RuntimeMonitor& monitor)
 {
-    DEBUG ("this=%" PRId64" target=%" PRId64 " path=%s",
-           iter == end ? 0 : iter->m_amount, target, path_to_str (path));
+    DEBUG ("this=%" PRId64" target=%" PRId64 " rem_pos=%" PRId64
+           " rem_neg=%" PRId64 " path=%s",
+           iter == end ? 0 : iter->m_amount, target,
+           iter == end ? 0 : iter->m_rem_pos,
+           iter == end ? 0 : iter->m_rem_neg, path_to_str (path));
 
     if (target == 0)
     {
@@ -139,6 +144,13 @@ subset_sum (SplitInfoVec::const_iterator iter,
         return;
     }
 
+    if (target < iter->m_rem_neg || target > iter->m_rem_pos)
+    {
+        DEBUG ("PRUNE target=%" PRId64 " rem_pos=%" PRId64" rem_neg=%" PRId64,
+               target, iter->m_rem_pos, iter->m_rem_neg);
+        return;
+    }
+
     auto next = std::next(iter);
 
     // 1st path: use current_num
@@ -177,7 +189,7 @@ gnc_account_get_autoclear_splits (Account *account, gnc_numeric toclear_value,
         else if (amt == 0)
             DEBUG ("skipping zero-amount split %p", split);
         else
-            splits.push_back ({amt, split});
+            splits.push_back ({amt, 0, 0, split});
     }
 
     static GQuark autoclear_quark = g_quark_from_static_string ("autoclear");
@@ -188,6 +200,24 @@ gnc_account_get_autoclear_splits (Account *account, gnc_numeric toclear_value,
         return nullptr;
     }
 
+    // sort splits in descending absolute amount
+    std::sort (splits.begin(), splits.end(),
+               [](const SplitInfo& a, const SplitInfo& b)
+               {
+                   int64_t aa = std::llabs(a.m_amount);
+                   int64_t bb = std::llabs(b.m_amount);
+                   return (aa == bb) ? a.m_amount > b.m_amount : aa > bb;
+               });
+
+    // for each split, precompute sums of remaining pos or neg amounts
+    int64_t rem_pos{0}, rem_neg{0};
+    std::for_each (splits.rbegin(), splits.rend(),
+                   [&rem_pos, &rem_neg](SplitInfo& s)
+                   {
+                       s.m_rem_pos = rem_pos += std::max<int64_t>(s.m_amount, 0);
+                       s.m_rem_neg = rem_neg += std::min<int64_t>(s.m_amount, 0);
+                   });
+
     RuntimeMonitor monitor{max_seconds};
     Solution solution;
     SplitInfoVec path;



Summary of changes:
 libgnucash/app-utils/gnc-autoclear.cpp | 36 +++++++++++++++++++++++++++++++---
 1 file changed, 33 insertions(+), 3 deletions(-)