destructuring lambda lists repeatedly CDR down the list from the start instead of keeping a reference to the current position

Bug #707573 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 (a b c d e f g h i &rest rest &key k1 k2 k3)
    '(va vb vc vd ve vf vg vh vi)
  (values a b c d e f rest k1 k2 k3))

What happens:
Here's the expansion. Notice the ridiculous CDRing.

(LET ((#:WHOLE1141 '(VA VB VC VD VE VF VG VH VI)))
  (DECLARE (TYPE LIST #:WHOLE1141))
  (LET* ((#:KEYWORDS-1143
          (CDR (CDR (CDR (CDR (CDR (CDR (CDR (CDR (CDR #:WHOLE1141)))))))))))
    (DECLARE (SB-EXT:MUFFLE-CONDITIONS SB-EXT:CODE-DELETION-NOTE))
    (DECLARE (IGNORABLE #:KEYWORDS-1143))
    (MULTIPLE-VALUE-BIND (#:PROBLEM1145 #:INFO1146)
        (SB-KERNEL::VERIFY-KEYWORDS #:KEYWORDS-1143 '(:K3 :K2 :K1) 'NIL)
      (WHEN #:PROBLEM1145
        (ERROR 'SB-KERNEL::DEFMACRO-LAMBDA-LIST-BROKEN-KEY-LIST-ERROR :KIND
               'DESTRUCTURING-BIND :PROBLEM #:PROBLEM1145 :INFO #:INFO1146)))
    (LET ((#:ARGS1144 #:WHOLE1141))
      (UNLESS (SB-INT:LIST-OF-LENGTH-AT-LEAST-P #:ARGS1144 9)
        (SB-KERNEL::ARG-COUNT-ERROR 'DESTRUCTURING-BIND 'NIL #:ARGS1144
                                    '(A B C D E F G H I &REST REST &KEY K1 K2
                                      K3)
                                    9 NIL)))
    (LET* ((A (CAR #:WHOLE1141))
           (B (CAR (CDR #:WHOLE1141)))
           (C (CAR (CDR (CDR #:WHOLE1141))))
           (D (CAR (CDR (CDR (CDR #:WHOLE1141)))))
           (E (CAR (CDR (CDR (CDR (CDR #:WHOLE1141))))))
           (F (CAR (CDR (CDR (CDR (CDR (CDR #:WHOLE1141)))))))
           (G (CAR (CDR (CDR (CDR (CDR (CDR (CDR #:WHOLE1141))))))))
           (H (CAR (CDR (CDR (CDR (CDR (CDR (CDR (CDR #:WHOLE1141)))))))))
           (I
            (CAR (CDR (CDR (CDR (CDR (CDR (CDR (CDR (CDR #:WHOLE1141))))))))))
           (REST
            (CDR (CDR (CDR (CDR (CDR (CDR (CDR (CDR (CDR #:WHOLE1141))))))))))
           (K1
            (IF (SB-KERNEL::KEYWORD-SUPPLIED-P :K1 #:KEYWORDS-1143)
                (SB-KERNEL::LOOKUP-KEYWORD :K1 #:KEYWORDS-1143)
                NIL))
           (K2
            (IF (SB-KERNEL::KEYWORD-SUPPLIED-P :K2 #:KEYWORDS-1143)
                (SB-KERNEL::LOOKUP-KEYWORD :K2 #:KEYWORDS-1143)
                NIL))
           (K3
            (IF (SB-KERNEL::KEYWORD-SUPPLIED-P :K3 #:KEYWORDS-1143)
                (SB-KERNEL::LOOKUP-KEYWORD :K3 #:KEYWORDS-1143)
                NIL)))
      (VALUES A B C D E F REST K1 K2 K3))))

I'm aware that some of this may or may not be optimized away by the compiler, but this strikes me as a pretty ridiculous expansion nonetheless.

What I expected to happen:
Probably the best way to handle this would be to keep a pointer to the current position in the list, updating it as we advance.

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) wrote :

We had a performance issue due to this in QPX, so have been using a shadowing DS-BIND which handles just enough to make our code work, but falls back to CL:DS-BIND if there are keyword arguments, which we never use in inner loops.
We expand like this:

* (macroexpand '(destructuring-bind (foo bar mum . baz) item (frob-it baz bar foo mum)))
(LET* ((#:G2459 ITEM)
       (FOO (POP #:G2459))
       (BAR (POP #:G2459))
       (MUM (NTH 0 #:G2459))
       (BAZ (NTHCDR 1 #:G2459)))
  (FROB-IT BAZ BAR FOO MUM))

I present the above, as I was about to report another issue about DS-BIND, but found that because of at least 4 open complaints, you probably don't want another. But essentially this bug is better served by an expansion that depends on current compilation policy. In our code we we have DS-BIND in inner loops, so not only is the extra CDRing bad, the list-of-length-p is pessimal also.
Mind you we also have code that thinks that (SIXTH (TENTH x)) is a perfectly reasonable and sane way to access a data structure, and doesn't want to first check that it's a list of 10.

Also, the reason for 'NTH' and 'NTHCDR' above is that sometimes we use a 'nil' as a dont-care value, in something like:
* (macroexpand '(destructuring-bind (foo bar nil nil nil mum . baz) item (frob-it baz bar foo mum)))
(LET* ((#:G2460 ITEM)
       (FOO (POP #:G2460))
       (BAR (POP #:G2460))
       (MUM (CAR (SETQ #:G2460 (NTHCDR 3 #:G2460))))
       (BAZ (NTHCDR 1 #:G2460)))
  (FROB-IT BAZ BAR FOO MUM))

I couldn't figure out if that was technically legal, but we do it, and in LOOP (which is deliberately not the same), it is legal.
One interpretation is that NIL is an empty nested destructuring lambda list, which could simply be ignored in unsafe code. I found that 3 Lisp implementations differed on what nil means in this context - choke, require a nil as the input for that place, or shutup and do nothing. I would like to know, if indeed I finish our homebrew implementation to submit back upstream.

The other issue, a genuine bug, not that it belongs here, is unexpectedly out-of-order evaluation of supplied-p variables.
Try this example and see why it might matter:
    (macroexpand '(cl:destructuring-bind (foo bar baz &key (a (not *foo-active-p*)) (b (compute-it) *foo-active-p*)) item (body)))

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