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

Szymon ssbm2 at o2.pl
Tue May 2 16:29:29 UTC 2006

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


(progn (test-split-list-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))
                     (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))
                   (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*
         ;; 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)
   (setq *test-result*
         (nsplit-list-if #'white-space-p *test-data*)))

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

(defun test-split-sequence-if ()
  (load-test-data) (gc)
   (setq *test-result*
          :remove-empty-subseqs t)))

Regards, Szymon.

More information about the cl-utilities-devel mailing list