fast-iter-equality.clj

(require '[datascript.btset :as btset])
(require '[datascript.arrays :as da])

;; What?
;; Fast equality check for btset/Iter
;;
;; Why?
;; There's no history or (d/since ) API and I want to know what's changed between two databases.
;; With fast Iter equality checks, I can quickly check if an attribute has changed between
;; my two database values like so:
;; (iter-equals? (d/datoms db1 <index> <attr> ...)
;;               (d/datoms db2 <index> <attr> ...))
;;
;; Why is it fast?
;; If I understand the datastructure correctly, it's fast because the check for 
;; (identical? (.-keys iter1) (.-keys iter2)) returns true most of the time, comparing 
;; up to 64 or 128 items at a time.

;; ----------------------
;; -- btset/Iter equallity

(defn- keys-eq? [a b]
  (or (identical? (.-keys a) (.-keys b))
      (let [achunk (btset/iter-chunk a)
            bchunk (btset/iter-chunk b)]
        (and (= (count achunk) (count bchunk))
             (every? #(= (nth achunk %)
                         (nth bchunk %))
                     (range (count achunk)))))))

(defn iter-equals?
  "Given two btset/Iter, return true if they iterate of the
  the identical items."
  [a b]
  (if (and (nil? a) (nil? b))
    true
    (when (and (some? a) (some? b) (keys-eq? a b))
      (recur (btset/iter-chunked-next a)
             (btset/iter-chunked-next b)))))

(comment
  ;; Usage
  (require '[datascript.core :as d])

  (let [conn (d/create-conn {})
        _ (d/transact! conn [{:foo :bar}])
        db1 (d/db conn)
        _ (d/transact! conn [{:abc :xyz}])
        db2 (d/db conn)]
    ;; Fast check whether datoms are equal.
    ;; Will hit (identical? (.-keys iter) (.-keys iter2))
    ;; most of the time, comparing a bunch of items at
    ;; the same time.
    (assert (iter-equals? (d/datoms db1 :aevt :foo)
                          (d/datoms db2 :aevt :foo)))

    (assert (not (iter-equals? (d/datoms db1 :aevt :abc)
                               (d/datoms db2 :aevt :abc))))))