Skip to content

Commit

Permalink
Optimized Int8Array a little
Browse files Browse the repository at this point in the history
  • Loading branch information
@tonsky
tonsky committed Nov 22, 2022
1 parent 645b43e commit 353652a
Show file tree
Hide file tree
Showing 2 changed files with 60 additions and 42 deletions.
22 changes: 15 additions & 7 deletions bench-clojure/me/tonsky/persistent_sorted_set/bench.cljc
View file
Original file line number Diff line number Diff line change
Expand Up @@ -51,12 +51,23 @@
(defn contains?-10K []
(doseq [x ints-10K]
(contains? set-10K x)))
(defn iterate-300K []

(defn doseq-300K []
(let [*res (volatile! 0)]
(doseq [x set-300K]
(vswap! *res + x))
@*res))

(defn next-300K []
(loop [xs set-300K
res 0]
(if-some [x (first xs)]
(recur (next xs) (+ res x))
res)))

(defn reduce-300K []
(reduce + 0 set-300K))

#?(:clj
(defn into-50K []
(into (set/sorted-set) ints-50K)))
Expand All @@ -67,10 +78,6 @@
(into (set/sorted-set) ints-50K)
(test-storage/storage))))

#?(:clj
(defn reduce-300K []
(reduce + 0 set-300K)))

#?(:clj
(defn reduce-300K-lazy []
(reset! (:*memory storage-300K) {})
Expand All @@ -80,13 +87,14 @@
{"conj-10K" conj-10K
"disj-10K" disj-10K
"contains?-10K" contains?-10K
"iterate-300K" iterate-300K
"doseq-300K" doseq-300K
"next-300K" next-300K
"reduce-300K" reduce-300K
#?@(:clj
["conj-transient-10K" conj-transient-10K
"disj-transient-10K" disj-transient-10K
"into-50K" into-50K
"store-50K" store-50K
"reduce-300K" reduce-300K
"reduce-300K-lazy" reduce-300K-lazy])})

(defn ^:export -main [& args]
Expand Down
80 changes: 45 additions & 35 deletions src-clojure/me/tonsky/persistent_sorted_set.cljs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -38,50 +38,60 @@
; idx :: Cached idx in keys array
; Keys and idx are cached for fast iteration inside a leaf"


(def ^:const min-len 16)
(def ^:const max-len 32)
(def ^:private ^:const avg-len (arrays/half (+ max-len min-len)))

(defn empty-path [len]
(defn empty-path [^number len]
(js/Int8Array. len))

(defn- path-get [path level]
(aget path level))
(defn- path-clone [path]
(js/Int8Array. path))

(defn- path-get ^number [path ^number level]
(arrays/aget path level))

(defn- path-mutate [path ^number level ^number idx]
(arrays/aset path level idx)
path)

(defn- path-set [path level idx]
(let [path' (js/Int8Array. path)]
(aset path' level idx)
path'))
(defn- path-set [path ^number level ^number idx]
(path-mutate (path-clone path) level idx))

(defn- path-inc [path]
(path-set path 0 (inc (path-get path 0))))

(defn- path-dec [path]
(path-set path 0 (dec (path-get path 0))))

(defn- path-cmp [path1 path2]
(loop [level (dec (arrays/alength path1))]
(if (< level 0)
0
(let [i1 (aget path1 level)
i2 (aget path2 level)]
(cond
(< i1 i2) -1
(> i1 i2) 1
:else (recur (dec level)))))))

(defn- path-lt [path1 path2]
(defn- path-len ^number [path]
(arrays/alength path))

(defn- path-cmp
([path1 path2]
(path-cmp path1 path2 0))
([path1 path2 ^number end-level]
(loop [level (dec (path-len path1))]
(if (< level end-level)
0
(let [i1 (aget path1 level)
i2 (aget path2 level)]
(cond
(< i1 i2) -1
(> i1 i2) 1
:else (recur (dec level))))))))

(defn- path-lt ^boolean [path1 path2]
(< (path-cmp path1 path2) 0))

(defn- path-lte [path1 path2]
(defn- path-lte ^boolean [path1 path2]
(<= (path-cmp path1 path2) 0))

(defn- path-eq [path1 path2]
(defn- path-eq ^boolean [path1 path2]
(== 0 (path-cmp path1 path2)))

(defn- path-near [path1 path2]
(path-eq (path-set path1 0 0) (path-set path2 0 0)))
(defn- path-same-leaf ^boolean [path1 path2]
(== 0 (path-cmp path1 path2 1)))

(defn- binary-search-l [cmp arr r k]
(loop [l 0
Expand Down Expand Up @@ -468,15 +478,15 @@
;; nested node overflow
(if (< (inc idx) (arrays/alength (.-pointers node)))
;; advance current node idx, reset subsequent indexes
(path-set (empty-path (arrays/alength path)) level (inc idx))
(path-mutate (empty-path (path-len path)) level (inc idx))
;; current node overflow
nil)
;; keep current idx
(path-set sub-path level idx)))
(path-mutate sub-path level idx)))
;; leaf
(if (< (inc idx) (arrays/alength (.-keys node)))
;; advance leaf idx
(path-set (empty-path (arrays/alength path)) 0 (inc idx))
(path-mutate (empty-path (path-len path)) 0 (inc idx))
;; leaf overflow
nil))))

Expand All @@ -490,16 +500,16 @@
;; inner node
(recur
(arrays/alast (.-pointers node))
(path-set path level (dec (arrays/alength (.-pointers node))))
(path-mutate path level (dec (arrays/alength (.-pointers node))))
(dec level))
;; leaf
(path-set path 0 (dec (arrays/alength (.-keys node)))))))
(path-mutate path 0 (dec (arrays/alength (.-keys node)))))))

(defn- next-path
"Returns path representing next item after `path` in natural traversal order.
Will overflow at leaf if at the end of the tree"
[set path]
(if (path-eq (path-dec (empty-path (inc (.-shift set)))) path)
(if (neg? (path-get path 0))
(empty-path (inc (.-shift set)))
(or
(-next-path (.-root set) path (.-shift set))
Expand All @@ -516,16 +526,16 @@
(if (>= (dec idx) 0)
;; advance current node idx, reset subsequent indexes
(let [idx (dec idx)
sub-path (-rpath (arrays/aget (.-pointers node) idx) path sub-level)]
(path-set sub-path level idx))
sub-path (-rpath (arrays/aget (.-pointers node) idx) (path-clone path) sub-level)]
(path-mutate sub-path level idx))
;; current node overflow
nil)
;; keep current idx
(path-set sub-path level idx)))
(path-mutate sub-path level idx)))
;; leaf
(if (>= (dec idx) 0)
;; advance leaf idx
(path-set (empty-path (arrays/alength path)) 0 (dec idx))
(path-mutate (empty-path (path-len path)) 0 (dec idx))
;; leaf overflow
nil))))

Expand Down Expand Up @@ -626,7 +636,7 @@

IChunkedSeq
(-chunked-first [this]
(let [end-idx (if (path-near left right)
(let [end-idx (if (path-same-leaf left right)
;; right is in the same node
(path-get right 0)
;; right is in a different node
Expand Down

0 comments on commit 353652a

Please sign in to comment.