0.6.12.26:
[sbcl.git] / src / code / profile.lisp
1 ;;;; This software is part of the SBCL system. See the README file for
2 ;;;; more information.
3 ;;;;
4 ;;;; This software is derived from the CMU CL system, which was
5 ;;;; written at Carnegie Mellon University and released into the
6 ;;;; public domain. The software is in the public domain and is
7 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
8 ;;;; files for more information.
9
10 (in-package "SB-PROFILE") ; (SB-, not SB!, since we're built in warm load.)
11 \f
12 ;;;; reading internal run time with high resolution and low overhead
13
14 ;;; FIXME: It might make sense to replace this with something
15 ;;; with finer resolution, e.g. milliseconds or microseconds.
16 ;;; For that matter, maybe we should boost the internal clock
17 ;;; up to something faster, like milliseconds.
18
19 (defconstant +ticks-per-second+ internal-time-units-per-second)
20
21 (declaim (inline get-internal-ticks))
22 (defun get-internal-ticks () (get-internal-run-time))
23 \f
24 ;;;; PCOUNTER
25
26 ;;; a PCOUNTER is used to represent an unsigned integer quantity which
27 ;;; can grow bigger than a fixnum, but typically does so, if at all,
28 ;;; in many small steps, where we don't want to cons on every step.
29 ;;; (Total system consing, time spent in a profiled function, and
30 ;;; bytes consed in a profiled function are all examples of such
31 ;;; quantities.)
32 (defstruct (pcounter (:copier nil))
33   (integer 0);; :type unsigned-byte)
34   (fixnum 0));; :type (and fixnum unsigned-byte)))
35
36 ;;;(declaim (ftype (function (pcounter unsigned-byte) pcounter) incf-pcounter))
37 ;;;(declaim (inline incf-pcounter)) ; FIXME: maybe inline when more stable
38 (defun incf-pcounter (pcounter delta)
39   (aver (typep delta 'unsigned-byte))
40   (let ((sum (+ (pcounter-fixnum pcounter) delta)))
41     (aver (typep sum 'unsigned-byte))
42     ;;(declare (type unsigned-byte sum))
43     (cond ((typep sum 'fixnum)
44            (setf (pcounter-fixnum pcounter) sum))
45           (t
46            (incf (pcounter-integer pcounter) sum)
47            (setf (pcounter-fixnum pcounter) 0))))
48   pcounter)
49
50 (declaim (ftype (function (pcounter) integer) pcounter->integer))
51 ;;;(declaim (inline pcounter->integer)) ; FIXME: maybe inline when more stable
52 (defun pcounter->integer (pcounter)
53   (+ (pcounter-integer pcounter)
54      (pcounter-fixnum pcounter)))
55 \f
56 ;;;; operations on (OR PCOUNTER FIXNUM)
57 ;;;;
58 ;;;; When we don't want to cons a PCOUNTER unless we're forced to, we
59 ;;;; start with a FIXNUM counter and only create a PCOUNTER if the
60 ;;;; FIXNUM overflows.
61
62 (declaim (ftype (function ((or pcounter fixnum) integer) (or pcounter fixnum)) %incf-pcounter-or-fixnum))
63 ;;;(declaim (inline %incf-pcounter-or-fixnum)) ; FIXME: maybe inline when more stable
64 (defun %incf-pcounter-or-fixnum (x delta)
65   (etypecase x
66     (fixnum
67      (let ((sum (+ x delta)))
68        (if (typep sum 'fixnum)
69            sum
70            (make-pcounter :integer sum))))
71     (pcounter
72      (incf-pcounter x delta))))
73   
74 (define-modify-macro incf-pcounter-or-fixnum (delta) %incf-pcounter-or-fixnum)
75
76 ;;; Trade off space for execution time by handling the common fast
77 ;;; (TYPEP DELTA 'FIXNUM) case inline and only calling generic
78 ;;; arithmetic as a last resort.
79 (defmacro fastbig-incf-pcounter-or-fixnum (x delta)
80   (let ((delta-sym (gensym "DELTA")))
81     `(let ((,delta-sym ,delta))
82        (aver (typep ,delta-sym 'unsigned-byte))
83        ;;(declare (type unsigned-byte ,delta-sym))
84        (if (typep ,delta-sym 'fixnum)
85            (incf-pcounter-or-fixnum ,x ,delta)
86            (incf-pcounter-or-fixnum ,x ,delta)))))
87
88 (declaim (ftype (function ((or pcounter fixnum)) integer) pcounter-or-fixnum->integer))
89 (declaim (maybe-inline pcounter-or-fixnum->integer))
90 (defun pcounter-or-fixnum->integer (x)
91   (etypecase x
92     (fixnum x)
93     (pcounter (pcounter->integer x))))
94 \f
95 ;;;; implementation-dependent interfaces
96
97 #|
98 ;;; To avoid unnecessary consing in the "encapsulation" code, we want
99 ;;; find out the number of required arguments, and use &REST to
100 ;;; capture only non-required arguments. This function returns (VALUES
101 ;;; MIN-ARGS OPTIONALS-P), where MIN-ARGS is the number of required
102 ;;; arguments and OPTIONALS-P is true iff there are any non-required
103 ;;; arguments (such as &OPTIONAL, &REST, or &KEY).
104 (declaim (ftype (function ((or symbol cons)) (values fixnum t)) fun-signature))
105 (defun fun-signature (name)
106   (let ((type (info :function :type name)))
107     (cond ((not (function-type-p type))
108            (values 0 t))
109           (t
110            (values (length (function-type-required type))
111                    (or (function-type-optional type)
112                        (function-type-keyp type)
113                        (function-type-rest type)))))))
114 |#
115 \f
116 ;;;; global data structures
117
118 ;;; We associate a PROFILE-INFO structure with each profiled function
119 ;;; name. This holds the functions that we call to manipulate the
120 ;;; closure which implements the encapsulation.
121 (defvar *profiled-function-name->info* (make-hash-table))
122 (defstruct (profile-info (:copier nil))
123   (name              (required-argument) :read-only t)
124   (encapsulated-fun  (required-argument) :type function :read-only t)
125   (encapsulation-fun (required-argument) :type function :read-only t)
126   (read-stats-fun    (required-argument) :type function :read-only t)
127   (clear-stats-fun   (required-argument) :type function :read-only t))
128
129 ;;; These variables are used to subtract out the time and consing for
130 ;;; recursive and other dynamically nested profiled calls. The total
131 ;;; resource consumed for each nested call is added into the
132 ;;; appropriate variable. When the outer function returns, these
133 ;;; amounts are subtracted from the total.
134 (defvar *enclosed-ticks* 0)
135 (defvar *enclosed-consing* 0)
136 (declaim (type (or pcounter fixnum) *enclosed-ticks* *enclosed-consing*))
137
138 ;;; This variable is also used to subtract out time for nested
139 ;;; profiled calls. The time inside the profile wrapper call --
140 ;;; between its two calls to GET-INTERNAL-TICKS -- is accounted
141 ;;; for by the *ENCLOSED-TIME* variable. However, there's also extra
142 ;;; overhead involved, before we get to the first call to
143 ;;; GET-INTERNAL-TICKS, and after we get to the second call. By
144 ;;; keeping track of the count of enclosed profiled calls, we can try
145 ;;; to compensate for that.
146 (defvar *enclosed-profiles* 0)
147 (declaim (type (or pcounter fixnum) *enclosed-profiles*))
148
149 ;;; the components of profiling overhead
150 (defstruct (overhead (:copier nil))
151   ;; the number of ticks a bare function call takes. This is
152   ;; factored into the other overheads, but not used for itself.
153   (call (required-argument) :type single-float :read-only t)
154   ;; the number of ticks that will be charged to a profiled
155   ;; function due to the profiling code
156   (internal (required-argument) :type single-float :read-only t)
157   ;; the number of ticks of overhead for profiling that a single
158   ;; profiled call adds to the total runtime for the program
159   (total (required-argument) :type single-float :read-only t))
160 (defvar *overhead*)
161 (declaim (type overhead *overhead*))
162 \f
163 ;;;; profile encapsulations
164
165 ;;; Trade off space for time by handling the usual all-FIXNUM cases
166 ;;; inline.
167 (defmacro fastbig- (x y)
168   (once-only ((x x) (y y))
169     `(if (and (typep ,x 'fixnum)
170               (typep ,y 'fixnum))
171          (- ,x ,y)
172          (- ,x ,y))))
173 (defmacro fastbig-1+ (x)
174   (once-only ((x x))
175     `(if (typep ,x 'index)
176          (1+ ,x)
177          (1+ ,x))))
178
179 ;;; Return a collection of closures over the same lexical context,
180 ;;;   (VALUES ENCAPSULATION-FUN READ-STATS-FUN CLEAR-STATS-FUN).
181 ;;;
182 ;;; ENCAPSULATION-FUN is a plug-in replacement for ENCAPSULATED-FUN,
183 ;;; which updates statistics whenver it's called.
184 ;;;
185 ;;; READ-STATS-FUN returns the statistics:
186 ;;;   (VALUES COUNT TIME CONSING PROFILE).
187 ;;; COUNT is the count of calls to ENCAPSULATION-FUN. TICKS is
188 ;;; the total number of ticks spent in ENCAPSULATED-FUN.
189 ;;; CONSING is the total consing of ENCAPSULATION-FUN. PROFILE is the
190 ;;; number of calls to the profiled function, stored for the purposes
191 ;;; of trying to estimate that part of profiling overhead which occurs
192 ;;; outside the interval between the profile wrapper function's timer
193 ;;; calls.
194 ;;;
195 ;;; CLEAR-STATS-FUN clears the statistics.
196 ;;;
197 ;;; (The reason for implementing this as coupled closures, with the
198 ;;; counts built into the lexical environment, is that we hope this
199 ;;; will minimize profiling overhead.)
200 (defun profile-encapsulation-lambdas (encapsulated-fun)
201   (declare (type function encapsulated-fun))
202   (let* ((count 0)
203          (ticks 0)
204          (consing 0)
205          (profiles 0))
206     (declare (type (or pcounter fixnum) count ticks consing profiles))
207     (values
208      ;; ENCAPSULATION-FUN
209      (lambda (sb-c:&more arg-context arg-count)
210        (declare (optimize speed safety))
211        ;; FIXME: Probably when this is stable, we should optimize (SAFETY 0).
212        (fastbig-incf-pcounter-or-fixnum count 1)
213        (let ((dticks 0)
214              (dconsing 0)
215              (inner-enclosed-profiles 0))
216          ;;(declare (type unsigned-byte dticks dconsing))
217          ;;(declare (type unsigned-byte inner-enclosed-profiles))
218          (aver (typep dticks 'unsigned-byte))
219          (aver (typep dconsing 'unsigned-byte))
220          (aver (typep inner-enclosed-profiles 'unsigned-byte))
221          (multiple-value-prog1
222              (let ((start-ticks (get-internal-ticks))
223                    ;; KLUDGE: We add (THE UNSIGNED-BYTE ..) wrappers
224                    ;; around GET-BYTES-CONSED because as of
225                    ;; sbcl-0.6.4, at the time that the FTYPE of
226                    ;; GET-BYTES-CONSED is DECLAIMed, the
227                    ;; cross-compiler's type system isn't mature enough
228                    ;; to do anything about it. -- WHN 20000503
229                    (start-consing (the unsigned-byte (get-bytes-consed)))
230                    (*enclosed-ticks* 0)
231                    (*enclosed-consing* 0)
232                    (*enclosed-profiles* 0))
233                (declare (inline pcounter-or-fixnum->integer))
234                (multiple-value-prog1
235                    (multiple-value-call encapsulated-fun
236                                         (sb-c:%more-arg-values arg-context
237                                                                0
238                                                                arg-count))
239                  (setf dticks (fastbig- (get-internal-ticks) start-ticks)
240                        dconsing (fastbig- (the unsigned-byte
241                                                (get-bytes-consed))
242                                           start-consing))
243                  (setf inner-enclosed-profiles
244                        (pcounter-or-fixnum->integer *enclosed-profiles*))
245                  (when (minusp dticks) ; REMOVEME
246                    (error "huh? (GET-INTERNAL-TICKS)=~S START-TICKS=~S"
247                           (get-internal-ticks) start-ticks))
248                  (aver (not (minusp dconsing))) ; REMOVEME
249                  (aver (not (minusp inner-enclosed-profiles))) ; REMOVEME
250                  (let ((net-dticks (fastbig- dticks *enclosed-ticks*)))
251                    (when (minusp net-dticks) ; REMOVEME
252                      (error "huh? DTICKS=~S, *ENCLOSED-TICKS*=~S"
253                             dticks *enclosed-ticks*))
254                    (fastbig-incf-pcounter-or-fixnum ticks net-dticks))
255                  (let ((net-dconsing (fastbig- dconsing *enclosed-consing*)))
256                    (when (minusp net-dconsing) ; REMOVEME
257                      (error "huh? DCONSING=~S, *ENCLOSED-CONSING*=~S"
258                             dticks *enclosed-ticks*))
259                    (fastbig-incf-pcounter-or-fixnum consing net-dconsing))
260                  (fastbig-incf-pcounter-or-fixnum profiles
261                                                   inner-enclosed-profiles)))
262            (fastbig-incf-pcounter-or-fixnum *enclosed-ticks* dticks)
263            (fastbig-incf-pcounter-or-fixnum *enclosed-consing* dconsing)
264            (fastbig-incf-pcounter-or-fixnum *enclosed-profiles*
265                                             (fastbig-1+
266                                              inner-enclosed-profiles)))))
267      ;; READ-STATS-FUN
268      (lambda ()
269        (format t "/entering READ-STATS-FUN ~S ~S ~S ~S~%"
270                count ticks consing profiles) ; REMOVEME (and M-V-PROG1 below)
271        (multiple-value-prog1
272            (values (pcounter-or-fixnum->integer count)
273                    (pcounter-or-fixnum->integer ticks)
274                    (pcounter-or-fixnum->integer consing)
275                    (pcounter-or-fixnum->integer profiles))
276          (print "/returning from READ-STATS-FUN")))
277      ;; CLEAR-STATS-FUN
278      (lambda ()
279        (setf count 0
280              ticks 0
281              consing 0
282              profiles 0)))))
283 \f
284 ;;;; interfaces
285
286 ;;; A symbol or (SETF FOO) list names a function, a string names all
287 ;;; the functions named by symbols in the named package.
288 (defun mapc-on-named-functions (function names)
289   (dolist (name names)
290     (etypecase name
291       (symbol (funcall function name))
292       (list
293        ;; We call this just for the side effect of checking that
294        ;; NAME is a legal function name:
295        (function-name-block-name name)
296        ;; Then we map onto it.
297        (funcall function name))
298       (string (let ((package (find-undeleted-package-or-lose name)))
299                 (do-symbols (symbol package)
300                   (when (eq (symbol-package symbol) package)
301                     (when (fboundp symbol)
302                       (funcall function symbol))
303                     (let ((setf-name `(setf ,symbol)))
304                       (when (fboundp setf-name)
305                         (funcall function setf-name)))))))))
306   (values))
307
308 ;;; Profile the named function, which should exist and not be profiled
309 ;;; already.
310 (defun profile-1-unprofiled-function (name)
311   (declare #.*optimize-byte-compilation*)
312   (let ((encapsulated-fun (fdefinition name)))
313     (multiple-value-bind (encapsulation-fun read-stats-fun clear-stats-fun)
314         (profile-encapsulation-lambdas encapsulated-fun)
315       (setf (fdefinition name)
316             encapsulation-fun)
317       (setf (gethash name *profiled-function-name->info*)
318             (make-profile-info :name name
319                                :encapsulated-fun encapsulated-fun
320                                :encapsulation-fun encapsulation-fun
321                                :read-stats-fun read-stats-fun
322                                :clear-stats-fun clear-stats-fun))
323       (values))))
324
325 ;;; Profile the named function. If already profiled, unprofile first.
326 (defun profile-1-function (name)
327   (declare #.*optimize-byte-compilation*)
328   (cond ((fboundp name)
329          (when (gethash name *profiled-function-name->info*)
330            (warn "~S is already profiled, so unprofiling it first." name)
331            (unprofile-1-function name))
332          (profile-1-unprofiled-function name))
333         (t
334          (warn "ignoring undefined function ~S" name)))
335   (values))
336
337 ;;; Unprofile the named function, if it is profiled.
338 (defun unprofile-1-function (name)
339   (declare #.*optimize-byte-compilation*)
340   (let ((pinfo (gethash name *profiled-function-name->info*)))
341     (cond (pinfo
342            (remhash name *profiled-function-name->info*)
343            (if (eq (fdefinition name) (profile-info-encapsulation-fun pinfo))
344                (setf (fdefinition name) (profile-info-encapsulated-fun pinfo))
345                (warn "preserving current definition of redefined function ~S"
346                      name)))
347           (t
348            (warn "~S is not a profiled function." name))))
349   (values))
350
351 (defmacro profile (&rest names)
352   #+sb-doc
353   "PROFILE Name*
354
355    If no names are supplied, return the list of profiled functions.
356
357    If names are supplied, wrap profiling code around the named functions.
358    As in TRACE, the names are not evaluated. A symbol names a function.
359    A string names all the functions named by symbols in the named
360    package. If a function is already profiled, then unprofile and
361    reprofile (useful to notice function redefinition.)  If a name is
362    undefined, then we give a warning and ignore it. See also
363    UNPROFILE, REPORT and RESET."
364   (declare #.*optimize-byte-compilation*)
365   (if (null names)
366       `(loop for k being each hash-key in *profiled-function-name->info*
367              collecting k)
368       `(mapc-on-named-functions #'profile-1-function ',names)))
369
370 (defmacro unprofile (&rest names)
371   #+sb-doc
372   "Unwrap any profiling code around the named functions, or if no names
373   are given, unprofile all profiled functions. A symbol names
374   a function. A string names all the functions named by symbols in the
375   named package. NAMES defaults to the list of names of all currently 
376   profiled functions."
377   (declare #.*optimize-byte-compilation*)
378   (if names
379       `(mapc-on-named-functions #'unprofile-1-function ',names)
380       `(unprofile-all)))
381
382 (defun unprofile-all ()
383   (declare #.*optimize-byte-compilation*)
384   (dohash (name profile-info *profiled-function-name->info*)
385     (declare (ignore profile-info))
386     (unprofile-1-function name)))
387
388 (defun reset ()
389   "Reset the counters for all profiled functions."
390   (dohash (name profile-info *profiled-function-name->info*)
391     (declare (ignore name))
392     (funcall (profile-info-clear-stats-fun profile-info))))
393 \f
394 ;;;; reporting results
395
396 (defstruct (time-info (:copier nil))
397   name
398   calls
399   seconds
400   consing)
401
402 ;;; Return our best guess for the run time in a function, subtracting
403 ;;; out factors for profiling overhead. We subtract out the internal
404 ;;; overhead for each call to this function, since the internal
405 ;;; overhead is the part of the profiling overhead for a function that
406 ;;; is charged to that function.
407 ;;;
408 ;;; We also subtract out a factor for each call to a profiled function
409 ;;; within this profiled function. This factor is the total profiling
410 ;;; overhead *minus the internal overhead*. We don't subtract out the
411 ;;; internal overhead, since it was already subtracted when the nested
412 ;;; profiled functions subtracted their running time from the time for
413 ;;; the enclosing function.
414 (defun compensate-time (calls ticks profile)
415   (let ((raw-compensated
416          (- (/ (float ticks) (float +ticks-per-second+))
417             (* (overhead-internal *overhead*) (float calls))
418             (* (- (overhead-total *overhead*)
419                   (overhead-internal *overhead*))
420                (float profile)))))
421     (max raw-compensated 0.0)))
422
423 (defun report ()
424   "Report results from profiling. The results are
425 approximately adjusted for profiling overhead, but when RAW is true
426 the unadjusted results are reported. The compensation may be somewhat
427 inaccurate when bignums are involved in runtime calculation, as in
428 a very-long-running Lisp process."
429   (declare #.*optimize-external-despite-byte-compilation*)
430   (unless (boundp '*overhead*)
431     (setf *overhead*
432           (compute-overhead)))
433   (let ((time-info-list ())
434         (no-call-name-list ()))
435     (dohash (name pinfo *profiled-function-name->info*)
436       (unless (eq (fdefinition name)
437                   (profile-info-encapsulation-fun pinfo))
438         (warn "Function ~S has been redefined, so times may be inaccurate.~@
439                PROFILE it again to record calls to the new definition."
440               name))
441       (multiple-value-bind (calls ticks consing profile)
442           (funcall (profile-info-read-stats-fun pinfo))
443         (if (zerop calls)
444             (push name no-call-name-list)
445             (push (make-time-info :name name
446                                   :calls calls
447                                   :seconds (compensate-time calls
448                                                             ticks
449                                                             profile)
450                                   :consing consing)
451                   time-info-list))))
452
453     (setf time-info-list
454           (sort time-info-list
455                 #'>=
456                 :key #'time-info-seconds))
457
458     (format *trace-output*
459             "~&  seconds  |  consed   |  calls  |  sec/call  |  name~@
460                ------------------------------------------------------~%")
461
462     (let ((total-time 0.0)
463           (total-consed 0)
464           (total-calls 0))
465       (dolist (time-info time-info-list)
466         (incf total-time (time-info-seconds time-info))
467         (incf total-calls (time-info-calls time-info))
468         (incf total-consed (time-info-consing time-info))
469         (format *trace-output*
470                 "~10,3F | ~9:D | ~7:D | ~10,6F | ~S~%"
471                 (time-info-seconds time-info)
472                 (time-info-consing time-info)
473                 (time-info-calls time-info)
474                 (/ (time-info-seconds time-info)
475                    (float (time-info-calls time-info)))
476                 (time-info-name time-info)))
477       (format *trace-output*
478               "------------------------------------------------------~@
479               ~10,3F | ~9:D | ~7:D |        | Total~%"
480               total-time total-consed total-calls)
481       (format *trace-output*
482               "~%estimated total profiling overhead: ~4,2F seconds~%"
483               (* (overhead-total *overhead*) (float total-calls)))
484       (format *trace-output*
485               "~&overhead estimation parameters:~%  ~Ss/call, ~Ss total profiling, ~Ss internal profiling~%"
486               (overhead-call *overhead*)
487               (overhead-total *overhead*)
488               (overhead-internal *overhead*)))
489
490     (when no-call-name-list
491       (format *trace-output*
492               "~%These functions were not called:~%~{~<~%~:; ~S~>~}~%"
493               (sort no-call-name-list #'string<
494                     :key (lambda (name)
495                            (symbol-name (function-name-block-name name))))))
496
497     (values)))
498 \f
499 ;;;; overhead estimation
500
501 ;;; We average the timing overhead over this many iterations.
502 (defconstant +timer-overhead-iterations+ 50000)
503
504 ;;; a dummy function that we profile to find profiling overhead
505 (declaim (notinline compute-overhead-aux))
506 (defun compute-overhead-aux (x)
507   (declare (ignore x)))
508
509 ;;; Return a newly computed OVERHEAD object.
510 (defun compute-overhead ()
511   (flet ((frob ()
512            (let ((start (get-internal-ticks))
513                  (fun (symbol-function 'compute-overhead-aux)))
514              (dotimes (i +timer-overhead-iterations+)
515                (funcall fun fun))
516              (/ (float (- (get-internal-ticks) start))
517                 (float +ticks-per-second+)
518                 (float +timer-overhead-iterations+)))))
519     (let (;; Measure unprofiled calls to estimate call overhead.
520           (call-overhead (frob))
521           total-overhead
522           internal-overhead)
523       ;; Measure profiled calls to estimate profiling overhead.
524       (unwind-protect
525           (progn
526             (profile compute-overhead-aux)
527             (setf total-overhead
528                   (- (frob) call-overhead)))
529         (let* ((pinfo (gethash 'compute-overhead-aux
530                                *profiled-function-name->info*))
531                (read-stats-fun (profile-info-read-stats-fun pinfo))
532                (time (nth-value 1 (funcall read-stats-fun))))
533           (setf internal-overhead
534                 (/ (float time)
535                    (float +ticks-per-second+)
536                    (float +timer-overhead-iterations+))))
537         (unprofile compute-overhead-aux))
538       (make-overhead :call call-overhead
539                      :total total-overhead
540                      :internal internal-overhead))))
541
542 ;;; It would be bad to compute *OVERHEAD*, save it into a .core file,
543 ;;; then load old *OVERHEAD* value from the .core file into a
544 ;;; different machine running at a different speed. We avoid this by
545 ;;; erasing *CALL-OVERHEAD* whenever we save a .core file.
546 (pushnew (lambda ()
547            (makunbound '*overhead*))
548          *before-save-initializations*)