branch: externals/phpinspect
commit db0924aaaac3165e5df014c8fde329dc7cf77e02
Author: Hugo Thunnissen <de...@hugot.nl>
Commit: Hugo Thunnissen <de...@hugot.nl>
Add avl-tree benchmark for comparison to splay-tree (+ add random-access
pass)
---
benchmarks/splay-tree.el | 124 +++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 124 insertions(+)
diff --git a/benchmarks/splay-tree.el b/benchmarks/splay-tree.el
index ef350f8267..5d8afbf15e 100644
--- a/benchmarks/splay-tree.el
+++ b/benchmarks/splay-tree.el
@@ -25,6 +25,22 @@
(require 'phpinspect-splayt)
+(defun swap (LIST el1 el2)
+ "in LIST swap indices EL1 and EL2 in place"
+ (let ((tmp (elt LIST el1)))
+ (setf (elt LIST el1) (elt LIST el2))
+ (setf (elt LIST el2) tmp)))
+
+(defun shuffle (LIST)
+ "Shuffle the elements in LIST.
+shuffling is done in place."
+ (cl-loop for i in (reverse (number-sequence 1 (1- (length LIST))))
+ do (let ((j (random (+ i 1))))
+ (swap LIST i j)))
+ LIST)
+
+(defconst phpi-randomized-access (shuffle (number-sequence 0 10000)))
+
(let ((tree (phpinspect-make-splayt))
result)
(message "Splay tree 10000 insertions:")
@@ -48,6 +64,28 @@
(message "Elapsed time: %f (%f in %d GC's)"
(car result) (caddr result) (cadr result))
+ (message "Splay tree 10000 randomized lookups:")
+ (garbage-collect)
+ (setq result
+ (benchmark-run 1
+ (dolist (i phpi-randomized-access)
+ (phpinspect-splayt-find tree i))))
+
+ (message "Elapsed time: %f (%f in %d GC's)"
+ (car result) (caddr result) (cadr result))
+
+ (message "Splay tree 10000 repeated (constant number 5) lookups:")
+ (garbage-collect)
+ (setq result
+ (benchmark-run 1
+ (dotimes (_i 10000)
+ (phpinspect-splayt-find tree 5))))
+
+ (message "Elapsed time: %f (%f in %d GC's)"
+ (car result) (caddr result) (cadr result))
+
+
+
(message "Splay tree 10000 items traversal:")
(garbage-collect)
(setq result
@@ -101,3 +139,89 @@
(message "Elapsed time: %f (%f in %d GC's)"
(car result) (caddr result) (cadr result)))
+
+
+(require 'avl-tree)
+(let ((avl-tree (avl-tree-create #'car-less-than-car))
+ result)
+ (message "AVL tree 10000 insertions:")
+ (garbage-collect)
+
+ (setq result
+ (benchmark-run 1
+ (dotimes (i 10000)
+ (avl-tree-enter avl-tree (cons i 'value)))))
+
+ (message "Elapsed time: %f (%f in %d GC's)"
+ (car result) (caddr result) (cadr result))
+
+ (message "AVL tree 10000 lookups:")
+ (garbage-collect)
+ (setq result
+ (benchmark-run 1
+ (dotimes (i 10000)
+ (avl-tree-member avl-tree (cons i nil)))))
+
+ (message "Elapsed time: %f (%f in %d GC's)"
+ (car result) (caddr result) (cadr result))
+
+ (message "AVL tree 10000 randomized lookups:")
+ (garbage-collect)
+ (setq result
+ (benchmark-run 1
+ (dolist (i phpi-randomized-access)
+ (avl-tree-member avl-tree (cons i nil)))))
+
+ (message "Elapsed time: %f (%f in %d GC's)"
+ (car result) (caddr result) (cadr result))
+
+ (message "AVL tree 10000 repeated (constant number 5) lookups:")
+ (garbage-collect)
+ (setq result
+ (benchmark-run 1
+ (dotimes (_i 10000)
+ (avl-tree-member avl-tree (cons 5 nil)))))
+
+ (message "Elapsed time: %f (%f in %d GC's)"
+ (car result) (caddr result) (cadr result))
+
+ (message "AVL tree 10000 items LR traversal:")
+ (garbage-collect)
+ (setq result
+ (benchmark-run 1
+ (iter-do (i (avl-tree-iter avl-tree))
+ (ignore i))))
+
+ (message "Elapsed time: %f (%f in %d GC's)"
+ (car result) (caddr result) (cadr result)))
+
+;; Results (ran at [2024-09-08 12:38])
+
+;; Splay tree 10000 insertions:
+;; Elapsed time: 0.006082 (0.000000 in 0 GC’s)
+;; Splay tree 10000 lookups:
+;; Elapsed time: 0.003710 (0.000000 in 0 GC’s)
+;; Splay tree 10000 randomized lookups:
+;; Elapsed time: 0.021548 (0.000000 in 0 GC’s)
+;; Splay tree 10000 repeated (constant number 5) lookups:
+;; Elapsed time: 0.000574 (0.000000 in 0 GC’s)
+;; Splay tree 10000 items traversal:
+;; Elapsed time: 0.170038 (0.108029 in 3 GC’s)
+;; Splay tree 10000 items LR traversal:
+;; Elapsed time: 0.000919 (0.000000 in 0 GC’s)
+;; Hashtable 10000 insertions:
+;; Elapsed time: 0.000757 (0.000000 in 0 GC’s)
+;; Hashtable 10000 lookups:
+;; Elapsed time: 0.000253 (0.000000 in 0 GC’s)
+;; Hashtable 10000 iterations:
+;; Elapsed time: 0.000137 (0.000000 in 0 GC’s)
+;; AVL tree 10000 insertions:
+;; Elapsed time: 0.010190 (0.000000 in 0 GC’s)
+;; AVL tree 10000 lookups:
+;; Elapsed time: 0.003857 (0.000000 in 0 GC’s)
+;; AVL tree 10000 randomized lookups:
+;; Elapsed time: 0.004604 (0.000000 in 0 GC’s)
+;; AVL tree 10000 repeated (constant number 5) lookups:
+;; Elapsed time: 0.003011 (0.000000 in 0 GC’s)
+;; AVL tree 10000 items LR traversal:
+;; Elapsed time: 0.005048 (0.000000 in 0 GC’s)
