[cl-utilities-devel] split-sequence performance problem.

[Szymon]

Hi. I discovered that split-sequence* functions are *SLOW*
when input is a list.

example:

(progn (test-split-list-if)
       (test-nsplit-list-if)
       (test-split-sequence-if))

SPLIT-LIST-IF, Evaluation took:

                 0.012 seconds of real time

                 1,445,888 bytes consed.

NSPLIT-LIST-IF, Evaluation took:

                 0.008 seconds of real time

                 0 bytes consed.

SPLIT-SEQUENCE-IF, Evaluation took:

                 124.586 seconds of real time

                 1,527,328 bytes consed.

example's code:

(defun split-list-if (test list &aux (start list) (end list))
  (loop while (and end (setq start (member-if-not test end)))
        collect (ldiff start (setq end (member-if test start)))))


(defun nsplit-list-if
  (test list &aux (list (member-if-not test list)) result tail)
  (flet ((helper (list)
           (loop for i on list
                 for j = (cdr i)
                 when (funcall test (car j)) do
                 (if (cdr j)
                     (return-from helper (values i j))
                   (progn
                     (rplacd i nil)
                     (return-from helper (values list nil)))))
           (values list nil)))
    (multiple-value-bind (a b) (helper1 list)
      (unless b (return-from nsplit-list-if list))
      (rplacd a nil)
      (setq result (setq list (rplaca b list)))
      (setq list (cdr result)))
    (rplacd result nil)
    (setq tail result)
    (loop (setq list (member-if-not test list))
          (multiple-value-bind (a b) (helper1 list)
            (cond ((null b)
                   (when a (rplacd tail (list a)))
                   (return-from nsplit-list-if result))
                  (t
                   (rplacd a nil)
                   (rplacd tail (setq list (rplaca b list)))
                   (setq list (cdr list))
                   (rplacd (setq tail (cdr tail)) nil)))))))

(defun white-space-p (char)
  (member char '(#\Space #\Newline #\Return #\Tab #\Page)))

(defvar *test-result*)

(defvar *test-data*)

(defun load-test-data ()
  (setq *test-data*
        (with-open-file
         ;; http://www.gutenberg.org/dirs/etext91/alice30.txt
         (stream #P"alice30.txt")
         (loop with char
               while (setq char (read-char stream nil nil))
               collect char))))

(defun test-nsplit-list-if ()
  (load-test-data) (gc)
  (time
   (setq *test-result*
         (nsplit-list-if #'white-space-p *test-data*)))
  (values))

(defun test-split-list-if ()
  (load-test-data) (gc)
  (time
   (setq *test-result*
         (split-list-if #'white-space-p *test-data*)))
  (values))

(defun test-split-sequence-if ()
  (load-test-data) (gc)
  (time
   (setq *test-result*
         (cl-utilities:split-sequence-if
          #'white-space-p
          *test-data*
          :remove-empty-subseqs t)))
  (values))


Regards, Szymon.