Implement O(1) OP_IF/NOTIF/ELSE/ENDIF logic

sipa · sipa · commit e6e622e5a0e2 · 2019-11-07T09:12:26.000-08:00
This optimization was first suggested by Sergio Demian Lerner in https://bitslog.wordpress.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/. The implementation follows the suggested approach there, but with a slightly simpler representation.
diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
@@ -289,16 +289,56 @@ namespace {
  * expose whether the stack is empty and whether or not any false values are
  * present at all. To implement OP_ELSE, a toggle_top modifier is added, which
  * flips the last value without returning it.
+ *
+ * This uses an optimized implementation that does not materialize the
+ * actual stack. Instead, it just stores the size of the would-be stack,
+ * and the position of the first false value in it.
  */
 class ConditionStack {
 private:
-    std::vector<bool> m_flags;
+    //! A constant for m_first_false_pos to indicate there are no falses.
+    static constexpr uint32_t NO_FALSE = std::numeric_limits<uint32_t>::max();
+
+    //! The size of the implied stack.
+    uint32_t m_stack_size = 0;
+    //! The position of the first false value on the implied stack, or NO_FALSE if all true.
+    uint32_t m_first_false_pos = NO_FALSE;
+
 public:
-    bool empty() { return m_flags.empty(); }
-    bool all_true() { return !std::count(m_flags.begin(), m_flags.end(), false); }
-    void push_back(bool f) { m_flags.push_back(f); }
-    void pop_back() { m_flags.pop_back(); }
-    void toggle_top() { m_flags.back() = !m_flags.back(); }
+    bool empty() { return m_stack_size == 0; }
+    bool all_true() { return m_first_false_pos == NO_FALSE; }
+    void push_back(bool f)
+    {
+        if (m_first_false_pos == NO_FALSE && !f) {
+            // The stack consists of all true values, and a false is added.
+            // The first false value will appear at the current size.
+            m_first_false_pos = m_stack_size;
+        }
+        ++m_stack_size;
+    }
+    void pop_back()
+    {
+        assert(m_stack_size > 0);
+        --m_stack_size;
+        if (m_first_false_pos == m_stack_size) {
+            // When popping off the first false value, everything becomes true.
+            m_first_false_pos = NO_FALSE;
+        }
+    }
+    void toggle_top()
+    {
+        assert(m_stack_size > 0);
+        if (m_first_false_pos == NO_FALSE) {
+            // The current stack is all true values; the first false will be the top.
+            m_first_false_pos = m_stack_size - 1;
+        } else if (m_first_false_pos == m_stack_size - 1) {
+            // The top is the first false value; toggling it will make everything true.
+            m_first_false_pos = NO_FALSE;
+        } else {
+            // There is a false value, but not on top. No action is needed as toggling
+            // anything but the first false value is unobservable.
+        }
+    }
 };
 }
 
