destructuring lambda lists inefficiently traverse the list of supplied keyword arguments twice, once to check if the keyword was supplied and a second time to return the value

Bug #707578 reported by Jean-Philippe Paradis on 2011-01-25
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
SBCL
Wishlist
Douglas Katzman

Bug Description

What I do:
(destructuring-bind (&key a b c d e f g h i) '(:c c :f f :h h)
  (values a b c d e f g h i))

What happens:
Here's the expansion:
(LET ((#:WHOLE1147 '(:C C :F F :H H)))
  (DECLARE (TYPE LIST #:WHOLE1147))
  (LET* ((#:KEYWORDS-1149 #:WHOLE1147))
    (DECLARE (SB-EXT:MUFFLE-CONDITIONS SB-EXT:CODE-DELETION-NOTE))
    (DECLARE (IGNORABLE #:KEYWORDS-1149))
    (MULTIPLE-VALUE-BIND (#:PROBLEM1150 #:INFO1151)
        (SB-KERNEL::VERIFY-KEYWORDS #:KEYWORDS-1149
                                    '(:I :H :G :F :E :D :C :B :A) 'NIL)
      (WHEN #:PROBLEM1150
        (ERROR 'SB-KERNEL::DEFMACRO-LAMBDA-LIST-BROKEN-KEY-LIST-ERROR :KIND
               'DESTRUCTURING-BIND :PROBLEM #:PROBLEM1150 :INFO #:INFO1151)))
    (LET* ((A
            (IF (SB-KERNEL::KEYWORD-SUPPLIED-P :A #:KEYWORDS-1149)
                (SB-KERNEL::LOOKUP-KEYWORD :A #:KEYWORDS-1149)
                NIL))
           (B
            (IF (SB-KERNEL::KEYWORD-SUPPLIED-P :B #:KEYWORDS-1149)
                (SB-KERNEL::LOOKUP-KEYWORD :B #:KEYWORDS-1149)
                NIL))
           (C
            (IF (SB-KERNEL::KEYWORD-SUPPLIED-P :C #:KEYWORDS-1149)
                (SB-KERNEL::LOOKUP-KEYWORD :C #:KEYWORDS-1149)
                NIL))
           (D
            (IF (SB-KERNEL::KEYWORD-SUPPLIED-P :D #:KEYWORDS-1149)
                (SB-KERNEL::LOOKUP-KEYWORD :D #:KEYWORDS-1149)
                NIL))
           (E
            (IF (SB-KERNEL::KEYWORD-SUPPLIED-P :E #:KEYWORDS-1149)
                (SB-KERNEL::LOOKUP-KEYWORD :E #:KEYWORDS-1149)
                NIL))
           (F
            (IF (SB-KERNEL::KEYWORD-SUPPLIED-P :F #:KEYWORDS-1149)
                (SB-KERNEL::LOOKUP-KEYWORD :F #:KEYWORDS-1149)
                NIL))
           (G
            (IF (SB-KERNEL::KEYWORD-SUPPLIED-P :G #:KEYWORDS-1149)
                (SB-KERNEL::LOOKUP-KEYWORD :G #:KEYWORDS-1149)
                NIL))
           (H
            (IF (SB-KERNEL::KEYWORD-SUPPLIED-P :H #:KEYWORDS-1149)
                (SB-KERNEL::LOOKUP-KEYWORD :H #:KEYWORDS-1149)
                NIL))
           (I
            (IF (SB-KERNEL::KEYWORD-SUPPLIED-P :I #:KEYWORDS-1149)
                (SB-KERNEL::LOOKUP-KEYWORD :I #:KEYWORDS-1149)
                NIL)))
      (VALUES A B C D E F G H I))))

Here's the implementation of SB-KERNEL::KEYWORD-SUPPLIED-P:
(defun keyword-supplied-p (keyword key-list)
  (do ((remaining key-list (cddr remaining)))
      ((endp remaining))
    (when (eq keyword (car remaining))
      (return t))))

Here's the implementation of SB-KERNEL::LOOKUP-KEYWORD:
(defun lookup-keyword (keyword key-list)
  (do ((remaining key-list (cddr remaining)))
      ((endp remaining))
    (when (eq keyword (car remaining))
      (return (cadr remaining)))))

The wastage is manifest.

What I expected to happen:
SBCL should check to see if the keyword is supplied and fetch the value in one step.

SBCL version: 1.0.42
uname -a: Linux dynamorph 2.6.32-27-generic #49-Ubuntu SMP Wed Dec 1 23:52:12 UTC 2010 i686 GNU/Linux

*features*:
(:SWANK :QUICKLISP :SB-BSD-SOCKETS-ADDRINFO :ASDF2 :ASDF :ANSI-CL :COMMON-LISP
 :SBCL :SB-DOC :SB-TEST :SB-LDB :SB-PACKAGE-LOCKS :SB-UNICODE :SB-EVAL
 :SB-SOURCE-LOCATIONS :IEEE-FLOATING-POINT :X86 :UNIX :ELF :LINUX :SB-THREAD
 :LARGEFILE :GENCGC :STACK-GROWS-DOWNWARD-NOT-UPWARD :C-STACK-IS-CONTROL-STACK
 :COMPARE-AND-SWAP-VOPS :UNWIND-TO-FRAME-AND-CALL-VOP :RAW-INSTANCE-INIT-VOPS
 :STACK-ALLOCATABLE-CLOSURES :STACK-ALLOCATABLE-VECTORS
 :STACK-ALLOCATABLE-LISTS :STACK-ALLOCATABLE-FIXED-OBJECTS :ALIEN-CALLBACKS
 :CYCLE-COUNTER :INLINE-CONSTANTS :MEMORY-BARRIER-VOPS :LINKAGE-TABLE
 :OS-PROVIDES-DLOPEN :OS-PROVIDES-PUTWC :OS-PROVIDES-SUSECONDS-T)

Nikodemus Siivola (nikodemus) wrote :

I would be happy to merge a patch that does this, as long as it doesn't complicate the code.

I am, however, not likely to ever work on this myself absent a test-case where this actually shows up as a performance issue. :)

Changed in sbcl:
importance: Undecided → Wishlist
status: New → Triaged
Douglas Katzman (dougk) on 2015-06-11
Changed in sbcl:
assignee: nobody → Douglas Katzman (dougk)
Douglas Katzman (dougk) on 2015-07-02
Changed in sbcl:
status: Triaged → Fix Committed
Changed in sbcl:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers