[vivace-graph-devel] Rucksack Btree number-indexes on UUID integer-128 representations -- a sketch

[MON KEY]

Some timings using the procedures in unicly/unicly-timings.lisp

First we populate an array of 1mil elts each a random length string of
1,36 randomly chosen UTF-8 characters.

Next we get a baseline timing for unicly::make-v5-uuid  by iterating
over that array.
 Our baseline shows that unicly::make-v5-uuid can generate approx.
79611.50 v5 UUIDs per second

Following that we over iterate the same array with
`make-v5-uuid-indexed' as per the definition from the previous
message.
This measurement indicates we can generate approx. 28376.04 v5 UUIDs
per second where each of these UUID objects contains a cache of its
128-bit integer representation as well as an equivalent bit-vector.
IOW, the speed cost of minting a v5 UUID with the two additional
cached slots is approx 2.8x the un-cached version.
This doesn't seem an insurmountable cost given that we would no longer
have to worry about performing a conversion when walking the Btree for
lookup/insertion.

Timings follow:
On SBCL 1.051 1.0.51.28-42fbc5e x86-32 on Linux using recent Unicly from Github.

(loop
   for x from 0 below 1000000
   do (setf (aref *tt--rnd* x) (make-random-string 36)))

(generic-gc)
(time
 (loop
    for x across *tt--rnd*
    do (unicly::make-v5-uuid unicly::*uuid-namespace-dns* x)))
; Evaluation took:
;   12.561 seconds of real time
;   12.549092 seconds of total run time (12.526096 user, 0.022996 system)
;   [ Run times consist of 0.837 seconds GC time, and 11.713 seconds
non-GC time. ]
;   99.90% CPU
;   20,882,950,670 processor cycles
;   961,227,776 bytes consed

(format nil "~,2F v5 UUIDs per second" (/ 1000000  12.561))
"79611.50 v5 UUIDs per second"

(generic-gc)
(time
 (loop
    for x across *tt--rnd*
    do (make-v5-uuid-indexed unicly::*uuid-namespace-dns* x)))
; Evaluation took:
;   35.241 seconds of real time
;   35.243642 seconds of total run time (35.156655 user, 0.086987 system)
;   [ Run times consist of 3.851 seconds GC time, and 31.393 seconds
non-GC time. ]
;   100.01% CPU
;   58,586,949,330 processor cycles
;   4,101,235,976 bytes consed

(format nil "~,2F v5 UUIDs per second" (/ 1000000 35.241))
;=> "28376.04 v5 UUIDs per second"