optimization: to avoid &rest allocation for :TEST and :KEY parameters
Affects | Status | Importance | Assigned to | Milestone | |
---|---|---|---|---|---|
SBCL |
Fix Released
|
Low
|
Unassigned |
Bug Description
Passing functions that take a &REST list as :TEST or :KEY parameters
results in consing, even though we know that a &rest list does not
have to be allocated for such cases.
The compiler could transform something like
(find #\Space seq :test #'char=)
into
(find #\Space seq :test #'(lambda (x y)
(char= x y)))
for all functions that are either /known/ or /inlineable/, and that
take a &REST list.
The same applies to predicate arguments for FOO-IF, FOO-IF-NOT, and
also SORT, and STABLE-SORT.
Test case:
(declaim (optimize speed))
(defun make-randomized
(declare (fixnum n))
(let ((vector (make-array n)))
(loop for i from 0 below n do (setf (aref vector i) (random n)))
vector))
(defun sort-vector-1 (vector)
(sort vector #'<))
(defun sort-vector-2 (vector)
(sort vector #'(lambda (x y) (< x y))))
You'll see that SORT-VECTOR-2 is twice as fast as SORT-VECTOR-1:
CL-USER> (let ((v (make-randomize
(time (sort-vector-1 v))
nil)
Evaluation took:
2.292 seconds of real time
2.292143 seconds of total run time (2.288143 user, 0.004000 system)
100.00% CPU
4,266,494,958 processor cycles
11,006,752 bytes consed
NIL
CL-USER> (let ((v (make-randomize
(time (sort-vector-2 v))
nil)
Evaluation took:
1.056 seconds of real time
1.048065 seconds of total run time (1.048065 user, 0.000000 system)
99.24% CPU
1,966,816,029 processor cycles
228,656 bytes consed
NIL
description: | updated |
I cannot replicate the consing on 1.0.23.51 on x86/darwin, but the performance effect is similar (~70% speedup.)
An alternative is to transform to global two-arg versions for such functions:
(defun two-arg-< (x y)
(< x y))
(defun sort-vector-3 (vector)
(sort vector #'two-arg-<))
Performs just as well as the one with a lambda, but is takes less space in large applications.
Finally, if we do take the inline lambda transform, whatever is known about the sequence argument can be used to drive optimization of :TEST and :KEY. In
(sort (the (simple-array single-float (*)) vector) :test #'<)
#'< can be replaced with (lambda (x y) (declare (single-float x y)) (< x y)) -- which is likely to be a significant win over the generic version.