Short about 'sort'

Hello again,

my progress in Lisp is continuing mainly thanks to your help. Thanks a lot.

Now there is small question.

I want to sort a list of following shape:
((a1 x1 (something1)) (a2 x2 (something2)) ... (an xn (something)))

using predicate (< ai aj) for any i, j.

I did it following way:

(sort '(--- my list ---) #'(lambda (x y) (< (car x) (car y))))

than I found much shorter way:

(sort '(--- my list ---) #'< :key 'car)

Natural question arises:
Are these two ways identical (according to 'EVAL of course' , which is 'more functional''?

The answer is important for me, because I still do not know how complicated will be the structure in my project, so probably I would like to write " < " relation myself.

Best regards, A.

I believe that the two are identical, two ways to describe the same operation. I think that you can regard the second as a shorthand for the first, and I find it more convenient.

The second I think is more idiomatic. Just note that SORT is destructive, and destroying quoted literals is not usually a good idea.

Ajschylos wrote:The answer is important for me, because I still do not know how complicated will be the structure in my project, so probably I would like to write " < " relation myself.

Specifying a KEY is absolutely the right thing to do here.

Should you find yourself in need of a custom test later then just switch over to a TEST clause (or add it if the KEY still applies).

Ramarren, I am not sure that I understand You well, as I suppose, sort might destroy the sorted entity, not the relation predicate expressed in lambda form, am I right?

Ajschylos wrote:Ramarren, I am not sure that I understand You well, as I suppose, sort might destroy the sorted entity, not the relation predicate expressed in lambda form, am I right?

Yes, I was referring to your examples, where you have:

'(--- my list ---)

Which is literal and constant list, and destroying it might in principle cause memory violation, although I don't think that any implementation actually puts them into read-only memory. But it might cause the program to act unpredictably. I once made such a mistake, though not with sort, but some other destructive function, and was wondering why the function only worked the first time it was called.

Ajschylos wrote: Natural question arises:
Are these two ways identical (according to 'EVAL of course' , which is 'more functional''?

The answer is important for me, because I still do not know how complicated will be the structure in my project, so probably I would like to write " < " relation myself.

Yes, these are two different ways of doing the same thing. I would choose the second, myself. As people said, it's more idiomatic. In general, it makes it obvious that you're sorting things using #'< as the predicate and that you're comparing the CAR of the items. The LAMBDA performs the same operation but generally includes more syntactic "goop" that tends to obscure the meaning. While it generally shouldn't concern you, there may be slight efficiencies in using the LAMBDA form over the version using :KEY--there are probably a couple of separate FUNCALLs to each of the predicate and the :KEY function in the :KEY version, one of which probably goes away with the LAMBDA where the CAR can be open-coded. In all but an extreme inner-loop, I wouldn't worry about that, though.

Yes, the second code snippet is more idiomatic. However, if performance is critical, the first may be faster. If performance is an issue, profile both methods in situ and see which one is faster.

fadrian wrote:Yes, the second code snippet is more idiomatic. However, if performance is critical, the first may be faster. If performance is an issue, profile both methods in situ and see which one is faster.

I don't want to advise against profiling, but I see no reason to suspect that the first could be any faster. I would rather expect both to produce almost exactly the same machine instructions.

Harleqin wrote:

fadrian wrote:Yes, the second code snippet is more idiomatic. However, if performance is critical, the first may be faster. If performance is an issue, profile both methods in situ and see which one is faster.

I don't want to advise against profiling, but I see no reason to suspect that the first could be any faster. I would rather expect both to produce almost exactly the same machine instructions.

It depends how the compiler optimizes FUNCALLs in this instance. With the CAR separated out into the :KEY parameter, the default behavior will be for SORT to implement two FUNCALLs (one to call the :KEY parameter, and the other to call the LAMBDA with the result). With the larger LAMBDA form and no :KEY form, SORT will FUNCALL the LAMBDA, but then the CAR can be open-coded into the LAMBDA form for a most-efficient call sequence. Every time something goes through FUNCALL, the default behavior is that it's late-bound and very dynamic. That's an efficiency hit. And two efficiency hits is worse than one efficiency hit. When you splat CAR right into the middle of the LAMBDA, the compiler can recognize that it's a primitive function and inline the call completely (it ceases to be a function call at all and just becomes direct machine instructions that implement CAR. It's therefore more efficient. A good compiler might be able to generate fairly equivalent code by proving to itself that they are essentially functionally equivalent and making the call to CAR more efficient, but it takes more work, and you'll be relying on a very good compiler to essentially inline a late-bound, dynamic call site.

As I said, however, I would still use :KEY unless you found that a particular inner loop was a problem to your overall performance, and that through profiling rather than hunch and guesswork. Micro-optimization like this is better left for once the code is done and you have measured it and know that you have a performance problem, and even in that case, you're better off trying to figure out whether you can eliminate the call to SORT completely.

Just to convince myself...

(in-package :cl-user)

(defvar *big-list*)

(defun init-big-list (length)
  (setf *big-list*
        (loop
           for i from 0 below length
           collect (cons (random 1000000) 'x)))
  nil)

(defun sort1 ()
  (setf *big-list* (sort *big-list* #'< :key #'car))
  nil)

(defun sort2 ()
  (setf *big-list* (sort *big-list* #'(lambda (x y) (< (car x) (car y)))))
  nil)

This is SBCL 1.0.22, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
* (load "temp.lisp")

T
* (init-big-list 100000)

NIL
* (time (sort1))

Evaluation took:
  0.255 seconds of real time
  0.247963 seconds of total run time (0.247963 user, 0.000000 system)
  97.25% CPU
  465,859,427 processor cycles
  0 bytes consed

NIL
* (init-big-list 100000)

NIL
* (time (sort2))

Evaluation took:
  0.230 seconds of real time
  0.219966 seconds of total run time (0.214967 user, 0.004999 system)
  95.65% CPU
  420,188,509 processor cycles
  0 bytes consed

NIL
*

So, the version with everything in a single LAMBDA is slightly faster, as predicted. This is consistent across multiple invocations with SBCL.