<commit_before>;;;
;;; reuse-distance.lisp
;;;
;;; Measure Reuse Distance
;;;

(defparameter *trace* '(a b b c c c d c a b c b a b c d d c c a))

(defun reuse-distance-histogram (trace)
  (if (null trace)
    (values nil nil)
    (let ((elem (car (last trace)))     ; ELEM - the last element in TRACE
          (cycle (1- (length trace))))  ; CYCLE - the position of ELEM in TRACE
      (multiple-value-bind
        (histogram          ; HISTOGRAM - reuse distance histogram of TRACE
          last-accesses)    ; LAST-ACCESS - previous emergence of ELEM
        (reuse-distance-histogram (subseq trace 0 cycle))
        (if (null (assoc elem last-accesses))
          ; ELEM never appeared
          (values
            (append histogram (list (list elem nil)))
            (append last-accesses (list (list elem cycle))))
          ; LAST-ACCESS - previous position of ELEM
          (let ((last-access (cadr (assoc elem last-accesses))))
            ; update the lastest position of ELEM
            (setf (cadr (assoc elem last-accesses)) cycle)
            (values
              (append histogram
                      (list (list elem
                                  ; reuse distance from the last occurence of ELEM
                                  (length (remove-duplicates (subseq trace last-access cycle))))))
              last-accesses)))))))
<commit_msg>Add runtime version of measuring reuse distance.<commit_after>;;;;
;;;; reuse-distance.lisp
;;;;
;;;; Measure Reuse Distance.
;;;;

;;; TRACE - a list of memory references, like '(a b b a a c b a)
(defun reuse-distance-histogram (trace)
  "Return reuse distance histogram and last-accesses of a memory reference trace. If TRACE is NIL, return NIL."
  (if (null trace)
    (values nil nil)
    (let ((elem (car (last trace)))     ; ELEM - the last element in TRACE
          (cycle (1- (length trace))))  ; CYCLE - the position of ELEM in TRACE
      (multiple-value-bind
        (histogram          ; HISTOGRAM - reuse distance histogram of TRACE
          last-accesses)    ; LAST-ACCESS - previous emergence of ELEM
        (reuse-distance-histogram (butlast trace))
        (if (null (assoc elem last-accesses))
          ;; ELEM never appeared
          (values
            (append histogram `((,elem nil)))
            (append last-accesses `((,elem ,cycle))))
          ; LAST-ACCESS - previous position of ELEM
          (let ((last-access (cadr (assoc elem last-accesses))))
            ; update the lastest position of ELEM
            (setf (cadr (assoc elem last-accesses)) cycle)
            (values
              (append histogram
                      `((,elem
                          ; reuse distance from the last occurence of ELEM
                          ,(1- (length (remove-duplicates
                                         (subseq trace
                                                 last-access
                                                 cycle)))))))
              last-accesses)))))))

;;; Runtime version of measuring reuse distance
(defun make-reuse-distance ()
  "Return a function with a memory reference as argument and reuse distance histogram as return value"
  (let ((trace nil)
        (histogram nil)
        (last-accesses nil))
    #'(lambda (elem)
        (let ((cycle (length trace)))
          (setf trace (append trace `(,elem)))
          (if (null (assoc elem last-accesses))
            (progn
              (push `(,elem ,cycle) last-accesses)
              (push `(,elem nil) histogram)
              (values histogram trace last-accesses))
            (let ((last-access (cadr (assoc elem last-accesses))))
              (push
                `(,elem ,(1- (length (remove-duplicates (subseq
                                                          trace
                                                          last-access
                                                          cycle)))))
                histogram)
              (setf (cadr (assoc elem last-accesses)) cycle)
              (values histogram trace last-accesses)))))))


(defun reuse-distance-histogram-runtime (trace)
  (defun reuse-intern (reuse-fn trace)
    (case (length trace)
      ((0) nil)
      ((1) (funcall reuse-fn (car trace)))
      (otherwise
        (progn (funcall reuse-fn (car trace))
               (reuse-intern reuse-fn (rest trace))))))
  (let ((reuse (make-reuse-distance)))
    (reuse-intern reuse trace)))

{'fraction_non_alphanumeric': 0.10782765621475299, 'fraction_numerical': 0.0015790660951951275, 'mean_word_length': 1.650328750747161, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2054346', 'n_tokens_mistral': 1218, 'n_tokens_neox': 1163, 'n_words': 412}