[vivace-graph-devel] every time we UUID 128 bits die down the bit hole
MON KEY
monkey at sandpframing.com
Fri Sep 9 07:48:15 UTC 2011
On Wed, Sep 7, 2011 at 3:53 PM, Kevin Raison <raison at chatsubo.net> wrote:
> I am convinced that this is an excellent idea; I also noticed that you
> have been working on it in your github branch of VG. Let me know when
> it is ready to merge into the mainline so that we can play around.
>
Following illustrates some possilbe utiliy of Unicly w/r/t indexes
(requires Unicly from Git)
(defvar *global-entity-index* (make-hash-table :test 'unicly:uuid-eql))
(defconstant +context-Z-namespace-as-ub128+
317192554773903544674993329975922389959)
(defconstant +context-Y-namespace-as-ub128+
003012593477302450121124084036000723448)
(defvar *context-Z* '())
(defvar *context-Y* '())
(defclass context ()
((namespace
:reader namespace)
(namespace-uuid
:reader namespace-uuid)
(namespace-table
:reader namespace-table)
(namespace-index
:reader namespace-index)))
(defun initialize-context (integer global-idx)
(let ((instance (make-instance 'context)))
(setf (slot-value instance 'namespace)
(unicly:uuid-from-bit-vector
(unicly::uuid-integer-128-to-bit-vector
integer)))
(setf (slot-value instance 'namespace-uuid)
(unicly:make-v5-uuid (namespace instance)
(unicly:uuid-princ-to-string (namespace
instance))))
(setf (slot-value instance 'namespace-table)
(make-hash-table :test 'unicly:uuid-eql))
(setf (slot-value instance 'namespace-index)
global-idx)
(setf (gethash (namespace instance)
(namespace-index instance))
(namespace-uuid instance))
(setf (gethash (namespace-uuid instance)
(namespace-index instance))
(namespace-table instance))
instance))
(defun get-entity-in-context (string-entity context-instance &key
(set-if-not nil))
(declare (string string-entity)
(boolean set-if-not)
(context context-instance))
(let ((entity-uuid (unicly:make-v5-uuid (namespace context-instance)
string-entity))
(index (namespace-index context-instance))
(did-set '()))
(labels ((get-global-entity-uuid ()
(gethash entity-uuid index))
(set-global-entity-uuid ()
(setf (gethash entity-uuid index) string-entity
did-set t)
entity-uuid)
(unset-whatset-global-entity ()
(remhash entity-uuid index)
(setf did-set nil)
(return-from get-entity-in-context (values nil nil)))
(global-entity-chk ()
(let ((entity-if (get-global-entity-uuid)))
(etypecase entity-if
(null
(if set-if-not
(set-global-entity-uuid)
(return-from get-entity-in-context nil)))
(string
(if (string= entity-if string-entity)
entity-uuid
(return-from get-entity-in-context
(when set-if-not (values nil did-set))))))))
(deref-context-table ()
(let* ((entity-chk (global-entity-chk))
(context-chk (gethash (namespace
context-instance) index))
(context-deref (if context-chk
;; we have the uuid of
context-namespace
(gethash context-chk index)
(cond (did-set
(unset-whatset-global-entity))
(t
(return-from
get-entity-in-context nil)))))
(table-deref (if context-deref
;; we have the assoicated
context hash-table
context-deref
(cond (did-set
(unset-whatset-global-entity))
(t
(return-from
get-entity-in-context nil)))))
(table-get-if (gethash entity-chk table-deref)))
(if table-get-if
table-get-if
(when set-if-not
(setf (gethash entity-chk table-deref) string-entity
did-set t))))))
(if set-if-not
(values (deref-context-table) did-set)
(deref-context-table)))))
(setf *context-Z* (initialize-context +context-Z-namespace-as-ub128+
*global-entity-index*))
(setf *context-Y* (initialize-context +context-Y-namespace-as-ub128+
*global-entity-index*))
(setf (gethash (unicly:make-v5-uuid (namespace *context-Z*) "ENTITY-W")
(namespace-index *context-Z*))
"ENTITY-W")
(setf (gethash (unicly:make-v5-uuid (namespace *context-Z*) "ENTITY-W")
(namespace-table *context-Z*))
"ENTITY-W")
(setf (gethash (unicly:make-v5-uuid (namespace *context-Y*) "ENTITY-W")
(namespace-index *context-Y*))
"ENTITY-W")
(setf (gethash (unicly:make-v5-uuid (namespace *context-Y*) "ENTITY-W")
(namespace-table *context-Y*))
"ENTITY-W")
(get-entity-in-context "ENTITY-W" *context-Z*)
(get-entity-in-context "ENTITY-W" *context-Y*)
(get-entity-in-context "ENTITY-O" *context-Z*)
(get-entity-in-context "ENTITY-O" *context-Z* :set-if-not t)
(get-entity-in-context "ENTITY-O" *context-Y*)
(get-entity-in-context "ENTITY-O" *context-Y* :set-if-not t)
> Also, to justify the original use of make-v1-uuid: it was simply easy
> and worked well enough. Now that there are others interested in this
> project, it is definitely time to use a better solution.
Great! I'm glad you agree.
FTR following are the timings i get using the uuid library from Quicklisp
comparing make-v1-uuid with make-v4-uuid
(sb-ext:gc :full t)
(time
(dotimes (i 10000)
(uuid:make-v1-uuid)))
;=>Evaluation took:
; 8.396 seconds of real time
; 0.500924 seconds of total run time (0.326950 user, 0.173974 system)
; 5.97% CPU
; 25,125,295,748 processor cycles
; 8,235,056 bytes consed
(sb-ext:gc :full t)
(time
(dotimes (i 10000)
(uuid:make-v4-uuid)))
;=>Evaluation took:
; 0.020 seconds of real time
; 0.018998 seconds of total run time (0.017998 user, 0.001000 system)
; 95.00% CPU
; 58,466,168 processor cycles
; 2,311,272 bytes consed
For posterity here's an illustration of _why_ make-v1-uuid is such a dog:
(in-package #:uuid)
;; Redefine uuid::get-timestamp to show us when it calls sleep:
(let ((uuids-this-tick 0)
(last-time 0)
;; add a counter to track how times sleep has been called
(sleep-count 0))
(defun get-timestamp ()
"Get timestamp, compensate nanoseconds intervals"
(unwind-protect
(tagbody
restart
(let ((time-now (+ (* (get-universal-time) 10000000)
100103040000000000)))
;10010304000 is time between 1582-10-15 and 1900-01-01 in seconds
(cond ((not (= last-time time-now))
(setf uuids-this-tick 0
last-time time-now)
(return-from get-timestamp time-now))
(T
(cond ((< uuids-this-tick *ticks-per-count*)
(incf uuids-this-tick)
(return-from get-timestamp (+ time-now
uuids-this-tick)))
(T
;; add a logging form to show us how many
times we sleep per invocation:
(format t "slept count: ~D~%" (incf sleep-count))
(sleep 0.0001)
(go restart)))))))
(setf sleep-count 0))))
(dotimes (i 10000)
(uuid:make-v1-uuid))
`uuid:make-v1-uuid' relies on `uuid::get-timestamp' which evaluates
(sleep 0.0001) quite a bit (at least on my
machine 32bit x86 running SBCL 1.50)
More information about the vivace-graph-devel
mailing list