Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the hashtrie Reference Manual, version 1.0.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Thu Sep 15 04:58:07 2022 GMT+0.
Next: Systems, Previous: The hashtrie Reference Manual, Up: The hashtrie Reference Manual [Contents][Index]
A fast Hash trie implementation based upon Clojure's.
A Hash Trie works like a Hash Set, except that it has been optimised for immutability and thread-safety.
By default, hash-trie's are persistent and immutable, but this implementation also supports transients for building sets significantly faster.
Constructor:
(htr:make-hash-trie nil "foo" 1 "bar")
;; {nil "foo", 1 "bar"}
Construct with transience:
(htr:with-transient (trans (htr:make-hash-trie))
(htr:tri-add trans 1 "bar")
(htr:tri-add trans nil "foo"))
;; {nil "foo", 1 "bar"}
Adding:
(htr:tri-add (htr:make-hash-trie 1 "foo") 1 "bar")
;; {1 "bar"}
Removing:
(htr:tri-remove (htr:make-hash-trie 1 1 2 2) 1)
;; {2 2}
Finding values:
(htr:tri-val (htr:make-hash-trie 1 "foo" 2 "bar") 1)
;; "foo"
Testing keys:
(htr:tri-has-key (htr:make-hash-trie 1 1 2 2) 1)
;; T
(htr:tri-has-key (htr:make-hash-trie 1 1 2 2) 100)
;; nil
Length/Count:
(htr:tri-length (htr:make-hash-trie 1 "foo" 2 "bar"))
;; 2
Mapping:
(htr:tri-map (htr:make-hash-trie 1 100 2 200 3 300)
(lambda (key val) (+ key val))
;; (101 202 303)
Reduce:
(htr:tri-reduce (htr:make-hash-trie 1 0 2 0 3 0)
(lambda (start key val) (+ start key val))
0)
;; 6
In theory the persistent Hash Trie is completely thread safe. This has been tested casually, but never in a production system.
This library currently uses sxhash and equal for comparison. Alternative hashing/comparison functions are not supported.
In theory should work on all Common Lisp implementations.
Has only been tested on SBCL, and CLisp.
Running SBCL, for comparison between using hash-trie and SBCL's own implementation of hashset, you can see that building SBCL's hashset is a bit over 10x faster. This is to be expected because it isn't immutable.
hashtrie
CL-USER> (time (loop for i from 0 to 1000000
for map = (htr:make-hash-trie i i) then (htr:tri-add map i i)
finally (return map)))
;Evaluation took:
; 1.158 seconds of real time
; 1.163023 seconds of total run time (1.002477 user, 0.160546 system)
; [ Run times consist of 0.486 seconds GC time, and 0.678 seconds non-GC time. ]
; 100.43% CPU
; 2,306,805,783 processor cycles
; 1,279,064,720 bytes consed
(time (htr:with-transient (trans (htr:make-hash-trie))
(dotimes (i 1000000)
(htr:tri-add trans i i))))
;Evaluation took:
; 0.640 seconds of real time
; 0.640942 seconds of total run time (0.557056 user, 0.083886 system)
; [ Run times consist of 0.297 seconds GC time, and 0.344 seconds non-GC time. ]
; 100.16% CPU
; 1,275,757,029 processor cycles
; 190,686,512 bytes consed
hashset
(time (let ((m (make-hash-table :test 'equal)))
(dotimes (i 1000000)
(setf (gethash i m) i))))
; Evaluation took:
; 0.170 seconds of real time
; 0.171739 seconds of total run time (0.152880 user, 0.018859 system)
; [ Run times consist of 0.024 seconds GC time, and 0.148 seconds non-GC time. ]
; 101.18% CPU
; 339,892,350 processor cycles
; 132,035,232 bytes consed
Also comparing the performance to clojure. Building a hash trie in sbcl is still slightly slower than doing the same in clojure, but not by much.
;Clojure 1.10.2
(defn persistent-build-map [set n]
(if (> n 0)
(recur (assoc set n n) (dec n))
set))
(defn transient-build-map [n]
(loop [i 0 v (transient {})]
(if (< i n)
(recur (inc i) (assoc! v i i))
(persistent! v))))
(time (count (persistent-build-map {} 1000000)))
;"Elapsed time: 606.96371 msecs"
(time (count (transient-build-map 1000000)))
"Elapsed time: 502.676784 msecs"
Next: Files, Previous: Introduction, Up: The hashtrie Reference Manual [Contents][Index]
The main system appears first, followed by any subsystem dependency.
An implementation of the Hash Trie datastructure, based on Clojure’s
Daniel Keogh
Eclipse 2.0
1.0.0
Next: Packages, Previous: Systems, Up: The hashtrie Reference Manual [Contents][Index]
Files are sorted by type and then listed depth-first from the systems components trees.
Next: hashtrie/package.lisp, Previous: Lisp, Up: Lisp [Contents][Index]
hashtrie (system).
Next: hashtrie/utils.lisp, Previous: hashtrie/hashtrie.asd, Up: Lisp [Contents][Index]
hashtrie (system).
Next: hashtrie/hashtrie.lisp, Previous: hashtrie/package.lisp, Up: Lisp [Contents][Index]
package.lisp (file).
hashtrie (system).
Next: hashtrie/api.lisp, Previous: hashtrie/utils.lisp, Up: Lisp [Contents][Index]
utils.lisp (file).
hashtrie (system).
Previous: hashtrie/hashtrie.lisp, Up: Lisp [Contents][Index]
hashtrie.lisp (file).
hashtrie (system).
Next: Definitions, Previous: Files, Up: The hashtrie Reference Manual [Contents][Index]
Packages are listed by definition order.
A fast implementation of the Hash Trie data structure, based on Clojure.
htr
common-lisp.
Next: Indexes, Previous: Packages, Up: The hashtrie Reference Manual [Contents][Index]
Definitions are sorted by export status, category, package, and then by lexicographic order.
Next: Internals, Previous: Definitions, Up: Definitions [Contents][Index]
Next: Macros, Previous: Public Interface, Up: Public Interface [Contents][Index]
Next: Ordinary functions, Previous: Special variables, Up: Public Interface [Contents][Index]
Within the body of this macro modify a temporary, transient copy of the hash trie. e.g. (with-transient (name (make-has-trie)) <body>). The transient copy will not be thread safe. Returns a new persistent hash trie
Next: Standalone methods, Previous: Macros, Up: Public Interface [Contents][Index]
Create a new map with the given key-value pair
Test if the key is in the hash trie
The number of pairs in the hash trie
Apply a (lambda (x y)) to each key-value pair and collect the results into a list
Apply (lambda (start key val)) to aggregate all pairs of a persistent hash map
Remove the pair from the hash trie
Get the value for a given key
Next: Structures, Previous: Ordinary functions, Up: Public Interface [Contents][Index]
Previous: Standalone methods, Up: Public Interface [Contents][Index]
structure-object.
(or null hashtrie:hash-trie)
(or null hashtrie::hash-map-node)
This slot is read-only.
boolean
This slot is read-only.
This slot is read-only.
common-lisp.
fixnum
(or null hashtrie::hash-map-node)
boolean
(hashtrie::make-box)
This slot is read-only.
Previous: Public Interface, Up: Definitions [Contents][Index]
Next: Special variables, Previous: Internals, Up: Internals [Contents][Index]
Next: Ordinary functions, Previous: Special variables, Up: Internals [Contents][Index]
Next: Generic functions, Previous: Macros, Up: Internals [Contents][Index]
val.
edit.
edit.
Next: Structures, Previous: Ordinary functions, Up: Internals [Contents][Index]
Previous: Generic functions, Up: Internals [Contents][Index]
structure-object.
structure-object.
Previous: Definitions, Up: The hashtrie Reference Manual [Contents][Index]
| Jump to: | (
A B C E F G H L M N P R S T W |
|---|
| Jump to: | (
A B C E F G H L M N P R S T W |
|---|
Next: Data types, Previous: Functions, Up: Indexes [Contents][Index]
| Jump to: | *
+
A B C E H L M N R S V |
|---|
| Jump to: | *
+
A B C E H L M N R S V |
|---|
| Jump to: | A F H P S T U |
|---|
| Jump to: | A F H P S T U |
|---|