[bpt/guile.git] / oop / goops / dispatch.scm

;;;; 	Copyright (C) 1999, 2000, 2001, 2003, 2006 Free Software Foundation, Inc.
;;;;
;;;; This library is free software; you can redistribute it and/or
;;;; modify it under the terms of the GNU Lesser General Public
;;;; License as published by the Free Software Foundation; either
;;;; version 2.1 of the License, or (at your option) any later version.
;;;; 
;;;; This library is distributed in the hope that it will be useful,
;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
;;;; Lesser General Public License for more details.
;;;; 
;;;; You should have received a copy of the GNU Lesser General Public
;;;; License along with this library; if not, write to the Free Software
;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
;;;;
\f

(define-module (oop goops dispatch)
  :use-module (oop goops)
  :use-module (oop goops util)
  :use-module (oop goops compile)
  :export (memoize-method!)
  :no-backtrace
  )

;;;
;;; This file implements method memoization.  It will finally be
;;; implemented on C level in order to obtain fast generic function
;;; application also during the first pass through the code.
;;;

;;;
;;; Constants
;;;

(define hashsets 8)
(define hashset-index 6)

(define hash-threshold 3)
(define initial-hash-size 4) ;must be a power of 2 and >= hash-threshold

(define initial-hash-size-1 (- initial-hash-size 1))

(define the-list-of-no-method '(no-method))

;;;
;;; Method cache
;;;

;; (#@dispatch args N-SPECIALIZED #((TYPE1 ... ENV FORMALS FORM1 ...) ...) GF)
;; (#@dispatch args N-SPECIALIZED HASHSET MASK
;;             #((TYPE1 ... ENV FORMALS FORM1 ...) ...)
;;             GF)

;;; Representation

;; non-hashed form

(define method-cache-entries cadddr)

(define (set-method-cache-entries! mcache entries)
  (set-car! (cdddr mcache) entries))

(define (method-cache-n-methods exp)
  (n-cache-methods (method-cache-entries exp)))

(define (method-cache-methods exp)
  (cache-methods (method-cache-entries exp)))

;; hashed form

(define (set-hashed-method-cache-hashset! exp hashset)
  (set-car! (cdddr exp) hashset))

(define (set-hashed-method-cache-mask! exp mask)
  (set-car! (cddddr exp) mask))

(define (hashed-method-cache-entries exp)
  (list-ref exp 5))

(define (set-hashed-method-cache-entries! exp entries)
  (set-car! (list-cdr-ref exp 5) entries))

;; either form

(define (method-cache-generic-function exp)
  (list-ref exp (if (method-cache-hashed? exp) 6 4)))

;;; Predicates

(define (method-cache-hashed? x)
  (integer? (cadddr x)))

(define max-non-hashed-index (- hash-threshold 2))

(define (passed-hash-threshold? exp)
  (and (> (vector-length (method-cache-entries exp)) max-non-hashed-index)
       (struct? (car (vector-ref (method-cache-entries exp)
				 max-non-hashed-index)))))

;;; Converting a method cache to hashed form

(define (method-cache->hashed! exp)
  (set-cdr! (cddr exp) (cons 0 (cons initial-hash-size-1 (cdddr exp))))
  exp)

;;;
;;; Cache entries
;;;

(define (n-cache-methods entries)
  (do ((i (- (vector-length entries) 1) (- i 1)))
      ((or (< i 0) (struct? (car (vector-ref entries i))))
       (+ i 1))))

(define (cache-methods entries)
  (do ((i (- (vector-length entries) 1) (- i 1))
       (methods '() (let ((entry (vector-ref entries i)))
		      (if (struct? (car entry))
			  (cons entry methods)
			  methods))))
      ((< i 0) methods)))

;;;
;;; Method insertion
;;;

(define (method-cache-insert! exp entry)
  (let* ((entries (method-cache-entries exp))
	 (n (n-cache-methods entries)))
    (if (>= n (vector-length entries))
	;; grow cache
	(let ((new-entries (make-vector (* 2 (vector-length entries))
					the-list-of-no-method)))
	  (do ((i 0 (+ i 1)))
	      ((= i n))
	    (vector-set! new-entries i (vector-ref entries i)))
	  (vector-set! new-entries n entry)
	  (set-method-cache-entries! exp new-entries))
	(vector-set! entries n entry))))

(define (hashed-method-cache-insert! exp entry)
  (let* ((cache (hashed-method-cache-entries exp))
	 (size (vector-length cache)))
    (let* ((entries (cons entry (cache-methods cache)))
	   (size (if (<= (length entries) size)
		     size
		     ;; larger size required
		     (let ((new-size (* 2 size)))
		       (set-hashed-method-cache-mask! exp (- new-size 1))
		       new-size)))
	   (min-misses size)
	   (best #f))
      (do ((hashset 0 (+ 1 hashset)))
	  ((= hashset hashsets))
	(let* ((test-cache (make-vector size the-list-of-no-method))
	       (misses (cache-try-hash! min-misses hashset test-cache entries)))
	  (cond ((zero? misses)
		 (set! min-misses 0)
		 (set! best hashset)
		 (set! cache test-cache)
		 (set! hashset (- hashsets 1)))
		((< misses min-misses)
		 (set! min-misses misses)
		 (set! best hashset)
		 (set! cache test-cache)))))
      (set-hashed-method-cache-hashset! exp best)
      (set-hashed-method-cache-entries! exp cache))))

;;;
;;; Caching
;;;

(define (cache-hashval hashset entry)
  (let ((hashset-index (+ hashset-index hashset)))
    (do ((sum 0)
	 (classes entry (cdr classes)))
	((not (and (pair? classes) (struct? (car classes))))
         sum)
      (set! sum (+ sum (struct-ref (car classes) hashset-index))))))

;;; FIXME: the throw probably is expensive, given that this function
;;; might be called an average of 3 or 4 times per rehash...
(define (cache-try-hash! min-misses hashset cache entries)
  (let ((max-misses 0)
	(mask (- (vector-length cache) 1)))
    (catch 'misses
	   (lambda ()
	     (do ((ls entries (cdr ls))
		  (misses 0 0))
		 ((null? ls) max-misses)
	       (do ((i (logand mask (cache-hashval hashset (car ls)))
		       (logand mask (+ i 1))))
		   ((and (pair? (vector-ref cache i))
                         (eq? (car (vector-ref cache i)) 'no-method))
		    (vector-set! cache i (car ls)))
		 (set! misses (+ 1 misses))
		 (if (>= misses min-misses)
		     (throw 'misses misses)))
	       (if (> misses max-misses)
		   (set! max-misses misses))))
	   (lambda (key misses)
	     misses))))

;;;
;;; Memoization
;;;

;; Backward compatibility
(if (not (defined? 'lookup-create-cmethod))
    (define (lookup-create-cmethod gf args)
      (no-applicable-method (car args) (cadr args))))

(define (memoize-method! gf args exp)
  (if (not (slot-ref gf 'used-by))
      (slot-set! gf 'used-by '()))
  (let ((applicable ((if (eq? gf compute-applicable-methods)
			 %compute-applicable-methods
			 compute-applicable-methods)
		     gf args)))
    (cond (applicable
	   ;; *fixme* dispatch.scm needs rewriting Since the current
	   ;; code mutates the method cache, we have to work on a
	   ;; copy.  Otherwise we might disturb another thread
	   ;; currently dispatching on the cache.  (No need to copy
	   ;; the vector.)
	   (let* ((new (list-copy exp))
		  (res
		   (cond ((method-cache-hashed? new)
			  (method-cache-install! hashed-method-cache-insert!
						 new args applicable))
			 ((passed-hash-threshold? new)
			  (method-cache-install! hashed-method-cache-insert!
						 (method-cache->hashed! new)
						 args
						 applicable))
			 (else
			  (method-cache-install! method-cache-insert!
						 new args applicable)))))
	     (set-cdr! (cdr exp) (cddr new))
	     res))
	  ((null? args)
	   (lookup-create-cmethod no-applicable-method (list gf '())))
	  (else
	   ;; Mutate arglist to fit no-applicable-method
	   (set-cdr! args (list (cons (car args) (cdr args))))
	   (set-car! args gf)
	   (lookup-create-cmethod no-applicable-method args)))))

(set-procedure-property! memoize-method! 'system-procedure #t)

(define method-cache-install!
  (letrec ((first-n
	    (lambda (ls n)
	      (if (or (zero? n) (null? ls))
		  '()
		  (cons (car ls) (first-n (cdr ls) (- n 1)))))))
    (lambda (insert! exp args applicable)
      (let* ((specializers (method-specializers (car applicable)))
	     (n-specializers
	      (if (list? specializers)
		  (length specializers)
		  (+ 1 (slot-ref (method-cache-generic-function exp)
				 'n-specialized)))))
	(let* ((types (map class-of (first-n args n-specializers)))
	       (entry+cmethod (compute-entry-with-cmethod applicable types)))
	  (insert! exp (car entry+cmethod)) ; entry = types + cmethod
	  (cdr entry+cmethod) ; cmethod
	  )))))
Commit	Line	Data
6e7d5622	1	;;;; Copyright (C) 1999, 2000, 2001, 2003, 2006 Free Software Foundation, Inc.
327d4dd3	2	;;;;
73be1d9e MV	3	;;;; This library is free software; you can redistribute it and/or
	4	;;;; modify it under the terms of the GNU Lesser General Public
	5	;;;; License as published by the Free Software Foundation; either
	6	;;;; version 2.1 of the License, or (at your option) any later version.
	7	;;;;
	8	;;;; This library is distributed in the hope that it will be useful,
14f1d9fe	9	;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
73be1d9e MV	10	;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	11	;;;; Lesser General Public License for more details.
	12	;;;;
	13	;;;; You should have received a copy of the GNU Lesser General Public
	14	;;;; License along with this library; if not, write to the Free Software
92205699	15	;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
327d4dd3	16	;;;;
14f1d9fe MD	17	\f
	18
	19	(define-module (oop goops dispatch)
	20	:use-module (oop goops)
	21	:use-module (oop goops util)
	22	:use-module (oop goops compile)
1a179b03	23	:export (memoize-method!)
14f1d9fe MD	24	:no-backtrace
	25	)
	26
14f1d9fe MD	27	;;;
	28	;;; This file implements method memoization. It will finally be
	29	;;; implemented on C level in order to obtain fast generic function
	30	;;; application also during the first pass through the code.
	31	;;;
	32
	33	;;;
	34	;;; Constants
	35	;;;
	36
	37	(define hashsets 8)
8b958d72	38	(define hashset-index 6)
14f1d9fe MD	39
	40	(define hash-threshold 3)
	41	(define initial-hash-size 4) ;must be a power of 2 and >= hash-threshold
	42
	43	(define initial-hash-size-1 (- initial-hash-size 1))
	44
	45	(define the-list-of-no-method '(no-method))
	46
	47	;;;
	48	;;; Method cache
	49	;;;
	50
	51	;; (#@dispatch args N-SPECIALIZED #((TYPE1 ... ENV FORMALS FORM1 ...) ...) GF)
	52	;; (#@dispatch args N-SPECIALIZED HASHSET MASK
	53	;; #((TYPE1 ... ENV FORMALS FORM1 ...) ...)
	54	;; GF)
	55
	56	;;; Representation
	57
	58	;; non-hashed form
	59
	60	(define method-cache-entries cadddr)
	61
	62	(define (set-method-cache-entries! mcache entries)
	63	(set-car! (cdddr mcache) entries))
	64
	65	(define (method-cache-n-methods exp)
	66	(n-cache-methods (method-cache-entries exp)))
	67
	68	(define (method-cache-methods exp)
	69	(cache-methods (method-cache-entries exp)))
	70
	71	;; hashed form
	72
	73	(define (set-hashed-method-cache-hashset! exp hashset)
	74	(set-car! (cdddr exp) hashset))
	75
	76	(define (set-hashed-method-cache-mask! exp mask)
	77	(set-car! (cddddr exp) mask))
	78
	79	(define (hashed-method-cache-entries exp)
	80	(list-ref exp 5))
	81
	82	(define (set-hashed-method-cache-entries! exp entries)
	83	(set-car! (list-cdr-ref exp 5) entries))
	84
	85	;; either form
	86
	87	(define (method-cache-generic-function exp)
	88	(list-ref exp (if (method-cache-hashed? exp) 6 4)))
	89
	90	;;; Predicates
	91
	92	(define (method-cache-hashed? x)
	93	(integer? (cadddr x)))
	94
	95	(define max-non-hashed-index (- hash-threshold 2))
	96
	97	(define (passed-hash-threshold? exp)
	98	(and (> (vector-length (method-cache-entries exp)) max-non-hashed-index)
	99	(struct? (car (vector-ref (method-cache-entries exp)
	100	max-non-hashed-index)))))
	101
	102	;;; Converting a method cache to hashed form
103
104	(define (method-cache->hashed! exp)
105	(set-cdr! (cddr exp) (cons 0 (cons initial-hash-size-1 (cdddr exp))))
106	exp)
107
108	;;;
109	;;; Cache entries
110	;;;
111
112	(define (n-cache-methods entries)
113	(do ((i (- (vector-length entries) 1) (- i 1)))
114	((or (< i 0) (struct? (car (vector-ref entries i))))
115	(+ i 1))))
116
117	(define (cache-methods entries)
118	(do ((i (- (vector-length entries) 1) (- i 1))
119	(methods '() (let ((entry (vector-ref entries i)))
120	(if (struct? (car entry))
121	(cons entry methods)
122	methods))))
123	((< i 0) methods)))
124
125	;;;
126	;;; Method insertion
127	;;;
128
129	(define (method-cache-insert! exp entry)
130	(let* ((entries (method-cache-entries exp))
131	(n (n-cache-methods entries)))
132	(if (>= n (vector-length entries))
133	;; grow cache
134	(let ((new-entries (make-vector (* 2 (vector-length entries))
135	the-list-of-no-method)))
136	(do ((i 0 (+ i 1)))
137	((= i n))
138	(vector-set! new-entries i (vector-ref entries i)))
139	(vector-set! new-entries n entry)
140	(set-method-cache-entries! exp new-entries))
141	(vector-set! entries n entry))))
142
143	(define (hashed-method-cache-insert! exp entry)
144	(let* ((cache (hashed-method-cache-entries exp))
145	(size (vector-length cache)))
146	(let* ((entries (cons entry (cache-methods cache)))
147	(size (if (<= (length entries) size)
148	size
149	;; larger size required
150	(let ((new-size (* 2 size)))
151	(set-hashed-method-cache-mask! exp (- new-size 1))
152	new-size)))
153	(min-misses size)
154	(best #f))
155	(do ((hashset 0 (+ 1 hashset)))
156	((= hashset hashsets))
157	(let* ((test-cache (make-vector size the-list-of-no-method))
158	(misses (cache-try-hash! min-misses hashset test-cache entries)))
159	(cond ((zero? misses)
160	(set! min-misses 0)
161	(set! best hashset)
162	(set! cache test-cache)
163	(set! hashset (- hashsets 1)))
164	((< misses min-misses)
165	(set! min-misses misses)
166	(set! best hashset)
167	(set! cache test-cache)))))
168	(set-hashed-method-cache-hashset! exp best)
169	(set-hashed-method-cache-entries! exp cache))))
170
171	;;;
172	;;; Caching
173	;;;
174
14f1d9fe MD	175	(define (cache-hashval hashset entry)
	176	(let ((hashset-index (+ hashset-index hashset)))
	177	(do ((sum 0)
	178	(classes entry (cdr classes)))
05b37c17 AW	179	((not (and (pair? classes) (struct? (car classes))))
05b37c17 AW	180	sum)
14f1d9fe MD	181	(set! sum (+ sum (struct-ref (car classes) hashset-index))))))
14f1d9fe MD	182
5e390de6 AW	183	;;; FIXME: the throw probably is expensive, given that this function
5e390de6 AW	184	;;; might be called an average of 3 or 4 times per rehash...
14f1d9fe MD	185	(define (cache-try-hash! min-misses hashset cache entries)
	186	(let ((max-misses 0)
	187	(mask (- (vector-length cache) 1)))
	188	(catch 'misses
	189	(lambda ()
	190	(do ((ls entries (cdr ls))
	191	(misses 0 0))
	192	((null? ls) max-misses)
ca83b028 DH	193	(do ((i (logand mask (cache-hashval hashset (car ls)))
ca83b028 DH	194	(logand mask (+ i 1))))
05b37c17 AW	195	((and (pair? (vector-ref cache i))
05b37c17 AW	196	(eq? (car (vector-ref cache i)) 'no-method))
14f1d9fe MD	197	(vector-set! cache i (car ls)))
	198	(set! misses (+ 1 misses))
	199	(if (>= misses min-misses)
	200	(throw 'misses misses)))
	201	(if (> misses max-misses)
	202	(set! max-misses misses))))
	203	(lambda (key misses)
	204	misses))))
	205
	206	;;;
	207	;;; Memoization
	208	;;;
	209
	210	;; Backward compatibility
	211	(if (not (defined? 'lookup-create-cmethod))
	212	(define (lookup-create-cmethod gf args)
	213	(no-applicable-method (car args) (cadr args))))
	214
b39eac3a	215	(define (memoize-method! gf args exp)
14f1d9fe MD	216	(if (not (slot-ref gf 'used-by))
	217	(slot-set! gf 'used-by '()))
	218	(let ((applicable ((if (eq? gf compute-applicable-methods)
	219	%compute-applicable-methods
	220	compute-applicable-methods)
	221	gf args)))
	222	(cond (applicable
	223	;; fixme dispatch.scm needs rewriting Since the current
	224	;; code mutates the method cache, we have to work on a
	225	;; copy. Otherwise we might disturb another thread
	226	;; currently dispatching on the cache. (No need to copy
	227	;; the vector.)
	228	(let* ((new (list-copy exp))
	229	(res
	230	(cond ((method-cache-hashed? new)
	231	(method-cache-install! hashed-method-cache-insert!
	232	new args applicable))
	233	((passed-hash-threshold? new)
	234	(method-cache-install! hashed-method-cache-insert!
	235	(method-cache->hashed! new)
	236	args
	237	applicable))
	238	(else
	239	(method-cache-install! method-cache-insert!
	240	new args applicable)))))
	241	(set-cdr! (cdr exp) (cddr new))
	242	res))
	243	((null? args)
	244	(lookup-create-cmethod no-applicable-method (list gf '())))
	245	(else
	246	;; Mutate arglist to fit no-applicable-method
	247	(set-cdr! args (list (cons (car args) (cdr args))))
	248	(set-car! args gf)
	249	(lookup-create-cmethod no-applicable-method args)))))
	250
	251	(set-procedure-property! memoize-method! 'system-procedure #t)
	252
b39eac3a TTN	253	(define method-cache-install!
	254	(letrec ((first-n
	255	(lambda (ls n)
	256	(if (or (zero? n) (null? ls))
	257	'()
	258	(cons (car ls) (first-n (cdr ls) (- n 1)))))))
	259	(lambda (insert! exp args applicable)
	260	(let* ((specializers (method-specializers (car applicable)))
	261	(n-specializers
	262	(if (list? specializers)
	263	(length specializers)
	264	(+ 1 (slot-ref (method-cache-generic-function exp)
	265	'n-specialized)))))
	266	(let* ((types (map class-of (first-n args n-specializers)))
	267	(entry+cmethod (compute-entry-with-cmethod applicable types)))
	268	(insert! exp (car entry+cmethod)) ; entry = types + cmethod
	269	(cdr entry+cmethod) ; cmethod
	270	)))))