src/pcl/cache.lisp

   1 ;;;; the basics of the PCL wrapper cache mechanism
   2
   3 ;;;; This software is part of the SBCL system. See the README file for
   4 ;;;; more information.
   5
   6 ;;;; This software is derived from software originally released by Xerox
   7 ;;;; Corporation. Copyright and release statements follow. Later modifications
   8 ;;;; to the software are in the public domain and are provided with
   9 ;;;; absolutely no warranty. See the COPYING and CREDITS files for more
  10 ;;;; information.
  11
  12 ;;;; copyright information from original PCL sources:
  13 ;;;;
  14 ;;;; Copyright (c) 1985, 1986, 1987, 1988, 1989, 1990 Xerox Corporation.
  15 ;;;; All rights reserved.
  16 ;;;;
  17 ;;;; Use and copying of this software and preparation of derivative works based
  18 ;;;; upon this software are permitted. Any distribution of this software or
  19 ;;;; derivative works must comply with all applicable United States export
  20 ;;;; control laws.
  21 ;;;;
  22 ;;;; This software is made available AS IS, and Xerox Corporation makes no
  23 ;;;; warranty about the software, its performance or its conformity to any
  24 ;;;; specification.
  25
  26 ;;;; Note: as of SBCL 1.0.6.3 it is questionable if cache.lisp can
  27 ;;;; anymore be considered to be "derived from software originally
  28 ;;;; released by Xerox Corporation", as at that time the whole cache
  29 ;;;; implementation was essentially redone from scratch.
  30
  31 (in-package "SB-PCL")
  32
  33 ;;;; Public API:
  34 ;;;;
  35 ;;;;   fill-cache
  36 ;;;;   probe-cache
  37 ;;;;   make-cache
  38 ;;;;   map-cache
  39 ;;;;   emit-cache-lookup
  40 ;;;;   copy-cache
  41 ;;;;   hash-table-to-cache
  42 ;;;;
  43 ;;;; This is a thread and interrupt safe reimplementation loosely
  44 ;;;; based on the original PCL cache by Kickzales and Rodrigues,
  45 ;;;; as described in "Efficient Method Dispatch in PCL".
  46 ;;;;
  47 ;;;; * Writes to cache are made atomic using compare-and-swap on
  48 ;;;;   wrappers. Wrappers are never moved or deleted after they have
  49 ;;;;   been written: to clean them out the cache need to be copied.
  50 ;;;;
  51 ;;;; * Copying or expanding the cache drops out incomplete and invalid
  52 ;;;;   lines.
  53 ;;;;
  54 ;;;; * Since the cache is used for memoization only we don't need to
  55 ;;;;   worry about which of simultaneous replacements (when expanding
  56 ;;;;   the cache) takes place: the losing one will have its work
  57 ;;;;   redone later. This also allows us to drop entries when the
  58 ;;;;   cache is about to grow insanely huge.
  59 ;;;;
  60 ;;;; The cache is essentially a specialized hash-table for layouts, used
  61 ;;;; for memoization of effective methods, slot locations, and constant
  62 ;;;; return values.
  63 ;;;;
  64 ;;;; Subsequences of the cache vector are called cache lines.
  65 ;;;;
  66 ;;;; The cache vector uses the symbol SB-PCL::..EMPTY.. as a sentinel
  67 ;;;; value, to allow storing NILs in the vector as well.
  68
  69 (defstruct (cache (:constructor %make-cache)
  70                   (:copier %copy-cache))
  71   ;; Number of keys the cache uses.
  72   (key-count 1 :type (integer 1 (#.call-arguments-limit)))
  73   ;; True if we store values in the cache.
  74   (value)
  75   ;; Number of vector elements a single cache line uses in the vector.
  76   ;; This is always a power of two, so that the vector length can be both
  77   ;; an exact multiple of this and a power of two.
  78   (line-size 1 :type (integer 1 #.most-positive-fixnum))
  79   ;; Cache vector, its length is always both a multiple of line-size
  80   ;; and a power of two. This is so that we can calculate
  81   ;;   (mod index (length vector))
  82   ;; using a bitmask.
  83   (vector #() :type simple-vector)
  84   ;; The bitmask used to calculate
  85   ;;   (mod (* line-size line-hash) (length vector))).
  86   (mask 0 :type fixnum)
  87   ;; Current probe-depth needed in the cache.
  88   (depth 0 :type index)
  89   ;; Maximum allowed probe-depth before the cache needs to expand.
  90   (limit 0 :type index))
  91
  92 (defun compute-cache-mask (vector-length line-size)
  93   ;; Since both vector-length and line-size are powers of two, we
  94   ;; can compute a bitmask such that
  95   ;;
  96   ;;  (logand <mask> <combined-layout-hash>)
  97   ;;
  98   ;; is "morally equal" to
  99   ;;
 100   ;;  (mod (* <line-size> <combined-layout-hash>) <vector-length>)
 101   ;;
 102   ;; This is it: (1- vector-length) is #b111... of the approriate size
 103   ;; to get the MOD, and (- line-size) gives right the number of zero
 104   ;; bits at the low end.
 105   (logand (1- vector-length) (- line-size)))
 106
 107 (defun cache-statistics (cache)
 108   (let* ((vector (cache-vector cache))
 109          (size (length vector))
 110          (line-size (cache-line-size cache))
 111          (total-lines (/ size line-size)))
 112     (values (loop for i from 0 by line-size below size
 113                   count (neq (svref vector i) '..empty..))
 114             total-lines (cache-depth cache) (cache-limit cache))))
 115
 116 ;;; Don't allocate insanely huge caches: this is 4096 lines for a
 117 ;;; value cache with 8-15 keys -- probably "big enough for anyone",
 118 ;;; and 16384 lines for a commonplace 2-key value cache.
 119 (defconstant +cache-vector-max-length+ (expt 2 16))
 120
 121 ;;; Compute the maximum allowed probe depth as a function of cache size.
 122 ;;; Cache size refers to number of cache lines, not the length of the
 123 ;;; cache vector.
 124 ;;;
 125 ;;; FIXME: It would be nice to take the generic function optimization
 126 ;;; policy into account here (speed vs. space.)
 127 (declaim (inline compute-limit))
 128 (defun compute-limit (size)
 129   (ceiling (sqrt (sqrt size))))
 130
 131 ;;; Returns VALUE if it is not ..EMPTY.., otherwise executes ELSE:
 132 (defmacro non-empty-or (value else)
 133   (with-unique-names (n-value)
 134     `(let ((,n-value ,value))
 135        (if (eq ,n-value '..empty..)
 136            ,else
 137            ,n-value))))
 138
 139 ;;; Fast way to check if a thing found at the position of a cache key is one:
 140 ;;; it is always either a wrapper, or the ..EMPTY.. symbol.
 141 (declaim (inline cache-key-p))
 142 (defun cache-key-p (thing)
 143   (not (symbolp thing)))
 144
 145 ;;; Atomically update the current probe depth of a cache.
 146 (defun note-cache-depth (cache depth)
 147   (loop for old = (cache-depth cache)
 148         while (and (< old depth)
 149                    (not (eq old (compare-and-swap (cache-depth cache)
 150                                                   old depth))))))
 151
 152 ;;; Compute the starting index of the next cache line in the cache vector.
 153 (declaim (inline next-cache-index))
 154 (defun next-cache-index (mask index line-size)
 155   (declare (type (unsigned-byte #.sb-vm:n-word-bits) index line-size mask))
 156   (logand mask (+ index line-size)))
 157
 158 ;;; Returns the hash-value for layout, or executes ELSE if the layout
 159 ;;; is invalid.
 160 (defmacro hash-layout-or (layout else)
 161   (with-unique-names (n-hash)
 162     `(let ((,n-hash (layout-clos-hash ,layout)))
 163        (if (zerop ,n-hash)
 164            ,else
 165            ,n-hash))))
 166
 167 ;;; Compute cache index for the cache and a list of layouts.
 168 (declaim (inline compute-cache-index))
 169 (defun compute-cache-index (cache layouts)
 170   (let ((index (hash-layout-or (car layouts)
 171                                (return-from compute-cache-index nil))))
 172     (declare (fixnum index))
 173     (dolist (layout (cdr layouts))
 174       (mixf index (hash-layout-or layout (return-from compute-cache-index nil))))
 175     ;; align with cache lines
 176     (logand index (cache-mask cache))))
 177
 178 ;;; Emit code that does lookup in cache bound to CACHE-VAR using
 179 ;;; layouts bound to LAYOUT-VARS. Go to MISS-TAG on event of a miss or
 180 ;;; invalid layout. Otherwise, if VALUE-VAR is non-nil, set it to the
 181 ;;; value found. (VALUE-VAR is non-nil only when CACHE-VALUE is true.)
 182 ;;;
 183 ;;; In other words, produces inlined code for COMPUTE-CACHE-INDEX when
 184 ;;; number of keys and presence of values in the cache is known
 185 ;;; beforehand.
 186 (defun emit-cache-lookup (cache-var layout-vars miss-tag value-var)
 187   (with-unique-names (probe n-vector n-depth n-mask
 188                       MATCH-WRAPPERS EXIT-WITH-HIT)
 189     (let* ((num-keys (length layout-vars))
 190            (pointer
 191             ;; We don't need POINTER if the cache has 1 key and no value,
 192             ;; or if FOLD-INDEX-ADDRESSING is supported, in which case adding
 193             ;; a constant to the base index for each cell-ref yields better code.
 194             #-(or x86 x86-64)
 195             (when (or (> num-keys 1) value-var) (make-symbol "PTR")))
 196            (line-size (power-of-two-ceiling (+ num-keys (if value-var 1 0)))))
 197       `(let ((,n-mask (cache-mask ,cache-var))
 198              (,probe (hash-layout-or ,(car layout-vars) (go ,miss-tag))))
 199          (declare (index ,probe))
 200          ,@(mapcar (lambda (layout-var)
 201                      `(mixf ,probe (hash-layout-or ,layout-var (go ,miss-tag))))
 202                    (cdr layout-vars))
 203          ;; align with cache lines
 204          (setf ,probe (logand ,probe ,n-mask))
 205          (let ((,n-depth (cache-depth ,cache-var))
 206                (,n-vector (cache-vector ,cache-var))
 207                ,@(when pointer `((,pointer ,probe))))
 208            (declare (index ,n-depth ,@(when pointer (list pointer))))
 209            (tagbody
 210             ,MATCH-WRAPPERS
 211             (when (and ,@(loop for layout-var in layout-vars
 212                                for i from 0
 213                                collect
 214                              (if pointer
 215                                  `(prog1 (eq ,layout-var
 216                                              (svref ,n-vector ,pointer))
 217                                     (incf ,pointer))
 218                                  `(eq ,layout-var
 219                                       (svref ,n-vector
 220                                              (the index (+ ,probe ,i)))))))
 221               ,@(when value-var
 222                  `((setf ,value-var
 223                          (non-empty-or (svref ,n-vector
 224                                               ,(or pointer
 225                                                    `(the index
 226                                                          (+ ,probe ,num-keys))))
 227                                        (go ,miss-tag)))))
 228               (go ,EXIT-WITH-HIT))
 229             (when (zerop ,n-depth) (go ,miss-tag))
 230             (decf ,n-depth)
 231             (setf ,probe (next-cache-index ,n-mask ,probe ,line-size))
 232             ,@(if pointer `((setf ,pointer ,probe)))
 233             (go ,MATCH-WRAPPERS)
 234             ,EXIT-WITH-HIT))))))
 235
 236 ;;; Probes CACHE for LAYOUTS.
 237 ;;;
 238 ;;; Returns two values: a boolean indicating a hit or a miss, and a secondary
 239 ;;; value that is the value that was stored in the cache if any.
 240 (defun probe-cache (cache layouts)
 241   (declare (optimize speed))
 242   (unless (consp layouts)
 243     (setf layouts (list layouts)))
 244   (let ((vector (cache-vector cache))
 245         (key-count (cache-key-count cache))
 246         (line-size (cache-line-size cache))
 247         (mask (cache-mask cache)))
 248     (flet ((probe-line (base)
 249              (declare (optimize (sb-c::type-check 0)))
 250              (tagbody
 251                 (loop for offset of-type index from 0 below key-count
 252                       for layout in layouts do
 253                       (unless (eq layout (svref vector (+ base offset)))
 254                         ;; missed
 255                         (go :miss)))
 256                 ;; all layouts match!
 257                 (let ((value (when (cache-value cache)
 258                                (non-empty-or (svref vector (+ base key-count))
 259                                              (go :miss)))))
 260                   (return-from probe-cache (values t value)))
 261               :miss
 262                 (return-from probe-line (next-cache-index mask base line-size)))))
 263       (declare (ftype (function (index) (values index &optional)) probe-line))
 264       (let ((index (compute-cache-index cache layouts)))
 265         (when index
 266           (loop repeat (1+ (cache-depth cache))
 267                 do (setf index (probe-line index)))))))
 268   (values nil nil))
 269
 270 ;;; Tries to write LAYOUTS and VALUE at the cache line starting at
 271 ;;; the index BASE. Returns true on success, and false on failure.
 272 (defun try-update-cache-line (cache base layouts value)
 273   (declare (index base))
 274   (let ((vector (cache-vector cache))
 275         (new (pop layouts)))
 276     ;; If we unwind from here, we will be left with an incomplete
 277     ;; cache line, but that is OK: next write using the same layouts
 278     ;; will fill it, and reads will treat an incomplete line as a
 279     ;; miss -- causing it to be filled.
 280     (loop for old = (compare-and-swap (svref vector base) '..empty.. new)  do
 281           (when (and (cache-key-p old) (not (eq old new)))
 282             ;; The place was already taken, and doesn't match our key.
 283             (return-from try-update-cache-line nil))
 284           (unless layouts
 285             ;; All keys match or successfully saved, save our value --
 286             ;; just smash it in. Until the first time it is written
 287             ;; there is ..EMPTY.. here, which probes look for, so we
 288             ;; don't get bogus hits. This is necessary because we want
 289             ;; to be able store arbitrary values here for use with
 290             ;; constant-value dispatch functions.
 291             (when (cache-value cache)
 292               (setf (svref vector (1+ base)) value))
 293             (return-from try-update-cache-line t))
 294           (setf new (pop layouts))
 295           (incf base))))
 296
 297 ;;; Tries to write LAYOUTS and VALUE somewhere in the cache. Returns
 298 ;;; true on success and false on failure, meaning the cache is too
 299 ;;; full.
 300 (defun try-update-cache (cache layouts value)
 301   (let ((index (or (compute-cache-index cache layouts)
 302                    ;; At least one of the layouts was invalid: just
 303                    ;; pretend we updated the cache, and let the next
 304                    ;; read pick up the mess.
 305                    (return-from try-update-cache t)))
 306         (line-size (cache-line-size cache))
 307         (mask (cache-mask cache)))
 308     (declare (index index))
 309     (loop for depth from 0 upto (cache-limit cache) do
 310           (when (try-update-cache-line cache index layouts value)
 311             (note-cache-depth cache depth)
 312             (return-from try-update-cache t))
 313           (setf index (next-cache-index mask index line-size)))))
 314
 315 ;;; Constructs a new cache.
 316 (defun make-cache (&key (key-count (missing-arg)) (value (missing-arg))
 317                    (size 1))
 318   (let* ((line-size (power-of-two-ceiling (+ key-count (if value 1 0))))
 319          (adjusted-size (power-of-two-ceiling size))
 320          (length (* adjusted-size line-size)))
 321     (if (<= length +cache-vector-max-length+)
 322         (%make-cache :key-count key-count
 323                      :line-size line-size
 324                      :vector (make-array length :initial-element '..empty..)
 325                      :value value
 326                      :mask (compute-cache-mask length line-size)
 327                      :limit (compute-limit adjusted-size))
 328         ;; Make a smaller one, then
 329         (make-cache :key-count key-count :value value :size (ceiling size 2)))))
 330
 331 ;;;; Copies and expands the cache, dropping any invalidated or
 332 ;;;; incomplete lines.
 333 (defun copy-and-expand-cache (cache layouts value)
 334   (let ((copy (%copy-cache cache))
 335         (length (length (cache-vector cache)))
 336         (drop-random-entries nil))
 337     (declare (index length))
 338     (when (< length +cache-vector-max-length+)
 339       (setf length (* 2 length)))
 340     (tagbody
 341      :again
 342        ;; Blow way the old vector first, so a GC potentially triggered by
 343        ;; MAKE-ARRAY can collect it.
 344        (setf (cache-vector copy) #()
 345              (cache-vector copy) (make-array length :initial-element '..empty..)
 346              (cache-depth copy) 0
 347              (cache-mask copy) (compute-cache-mask length (cache-line-size cache))
 348              (cache-limit copy) (compute-limit (/ length (cache-line-size cache))))
 349        ;; First insert the new one -- if we don't do this first and
 350        ;; the cache has reached its maximum size we may end up looping
 351        ;; in FILL-CACHE.
 352        (unless (try-update-cache copy layouts value)
 353          (bug "Could not insert ~S:~S to supposedly empty ~S." layouts value copy))
 354        (map-cache (if drop-random-entries
 355                       ;; The cache is at maximum size, and all entries
 356                       ;; do not fit in. Drop a random ~50% of entries,
 357                       ;; to make space for new ones. This needs to be
 358                       ;; random, since otherwise we might get in a
 359                       ;; rut: add A causing B to drop, then add B
 360                       ;; causing A to drop... repeat ad nauseam,
 361                       ;; spending most of the time here instead of
 362                       ;; doing real work. 50% because if we drop too
 363                       ;; few we need to do this almost right away
 364                       ;; again, and if we drop too many, we need to
 365                       ;; recompute more then we'd like.
 366                       ;; _Experimentally_ 50% seems to perform the
 367                       ;; best, but it would be nice to have a proper
 368                       ;; analysis...
 369                       (randomly-punting-lambda (layouts value)
 370                         (try-update-cache copy layouts value))
 371                       (lambda (layouts value)
 372                         (unless (try-update-cache copy layouts value)
 373                           ;; Didn't fit -- expand the cache, or drop
 374                           ;; a few unlucky ones.
 375                           (if (< length +cache-vector-max-length+)
 376                               (setf length (* 2 length))
 377                               (setf drop-random-entries t))
 378                           (go :again))))
 379                   cache))
 380     copy))
 381
 382 (defun cache-has-invalid-entries-p (cache)
 383   (let ((vector (cache-vector cache))
 384         (line-size (cache-line-size cache))
 385         (key-count (cache-key-count cache))
 386         (mask (cache-mask cache))
 387         (index 0))
 388     (loop
 389       ;; Check if the line is in use, and check validity of the keys.
 390       (let ((key1 (svref vector index)))
 391         (when (cache-key-p key1)
 392           (if (zerop (layout-clos-hash key1))
 393               ;; First key invalid.
 394               (return-from cache-has-invalid-entries-p t)
 395               ;; Line is in use and the first key is valid: check the rest.
 396               (loop for offset from 1 below key-count
 397                     do (let ((thing (svref vector (+ index offset))))
 398                          (when (or (not (cache-key-p thing))
 399                                    (zerop (layout-clos-hash thing)))
 400                            ;; Incomplete line or invalid layout.
 401                            (return-from cache-has-invalid-entries-p t)))))))
 402       ;; Line empty of valid, onwards.
 403       (setf index (next-cache-index mask index line-size))
 404       (when (zerop index)
 405         ;; wrapped around
 406         (return-from cache-has-invalid-entries-p nil)))))
 407
 408 (defun hash-table-to-cache (table &key value key-count)
 409   (let ((cache (make-cache :key-count key-count :value value
 410                            :size (hash-table-count table))))
 411     (maphash (lambda (class value)
 412                (setq cache (fill-cache cache (class-wrapper class) value)))
 413              table)
 414     cache))
 415
 416 ;;; Inserts VALUE to CACHE keyd by LAYOUTS. Expands the cache if
 417 ;;; necessary, and returns the new cache.
 418 (defun fill-cache (cache layouts value)
 419   (labels
 420       ((%fill-cache (cache layouts value expand)
 421          (cond ((try-update-cache cache layouts value)
 422                 cache)
 423                ((and (not expand) (cache-has-invalid-entries-p cache))
 424                 ;; Don't expand yet: maybe there will be enough space if
 425                 ;; we just drop the invalid entries.
 426                 (%fill-cache (copy-cache cache) layouts value t))
 427                (t
 428                 (copy-and-expand-cache cache layouts value)))))
 429     (%fill-cache cache (ensure-list layouts) value nil)))
 430
 431 ;;; Calls FUNCTION with all layouts and values in cache.
 432 (defun map-cache (function cache)
 433   (let* ((vector (cache-vector cache))
 434          (key-count (cache-key-count cache))
 435          (valuep (cache-value cache))
 436          (line-size (cache-line-size cache))
 437          (mask (cache-mask cache))
 438          (fun (if (functionp function)
 439                   function
 440                   (fdefinition function)))
 441          (index 0))
 442     (tagbody
 443      :map
 444        (let ((layouts
 445               (loop for offset from 0 below key-count
 446                     collect (non-empty-or (svref vector (+ offset index))
 447                                           (go :next)))))
 448          (let ((value (when valuep
 449                         (non-empty-or (svref vector (+ index key-count))
 450                                       (go :next)))))
 451            ;; Let the callee worry about invalid layouts
 452            (funcall fun layouts value)))
 453      :next
 454        (setf index (next-cache-index mask index line-size))
 455        (unless (zerop index)
 456          (go :map))))
 457   cache)
 458
 459 ;;; Copying a cache without expanding it is very much like mapping it:
 460 ;;; we need to be carefull because there may be updates while we are
 461 ;;; copying it, and we don't want to copy incomplete entries or invalid
 462 ;;; ones.
 463 (defun copy-cache (cache)
 464   (let* ((vector (cache-vector cache))
 465          (copy (make-array (length vector) :initial-element '..empty..))
 466          (line-size (cache-line-size cache))
 467          (key-count (cache-key-count cache))
 468          (valuep (cache-value cache))
 469          (mask (cache-mask cache))
 470          (size (/ (length vector) line-size))
 471          (index 0)
 472          (depth 0))
 473     (tagbody
 474      :copy
 475        (let ((layouts (loop for offset from 0 below key-count
 476                             collect (non-empty-or (svref vector (+ index offset))
 477                                                   (go :next)))))
 478          ;; Check validity & compute primary index.
 479          (let ((primary (or (compute-cache-index cache layouts)
 480                             (go :next))))
 481            ;; Check & copy value.
 482            (when valuep
 483              (setf (svref copy (+ index key-count))
 484                    (non-empty-or (svref vector (+ index key-count))
 485                                  (go :next))))
 486            ;; Copy layouts.
 487            (loop for offset from 0 below key-count do
 488                  (setf (svref copy (+ index offset)) (pop layouts)))
 489            ;; Update probe depth.
 490            (let ((distance (/ (- index primary) line-size)))
 491              (setf depth (max depth (if (minusp distance)
 492                                         ;; account for wrap-around
 493                                         (+ distance size)
 494                                         distance))))))
 495      :next
 496        (setf index (next-cache-index mask index line-size))
 497        (unless (zerop index)
 498          (go :copy)))
 499     (%make-cache :vector copy
 500                  :depth depth
 501                  :key-count (cache-key-count cache)
 502                  :line-size line-size
 503                  :value valuep
 504                  :mask mask
 505                  :limit (cache-limit cache))))
 506
 507 ;;;; For debugging & collecting statistics.
 508
 509 (defun map-all-caches (function)
 510   (dolist (p (list-all-packages))
 511     (do-symbols (s p)
 512       (when (eq p (symbol-package s))
 513         (dolist (name (list s
 514                             `(setf ,s)
 515                             (slot-reader-name s)
 516                             (slot-writer-name s)
 517                             (slot-boundp-name s)))
 518           (when (fboundp name)
 519             (let ((fun (fdefinition name)))
 520               (when (typep fun 'generic-function)
 521                 (let ((cache (gf-dfun-cache fun)))
 522                   (when cache
 523                     (funcall function name cache)))))))))))
 524
 525 (defun check-cache-consistency (cache)
 526   (let ((table (make-hash-table :test 'equal)))
 527     (map-cache (lambda (layouts value)
 528                  (declare (ignore value))
 529                  (if (gethash layouts table)
 530                      (cerror "Check futher."
 531                              "Multiple appearances of ~S." layouts)
 532                      (setf (gethash layouts table) t)))
 533                cache)))