Opened 21 months ago

Last modified 11 months ago

#1236 new defect

equal? can break at random moments

Reported by: sjamaan Owned by:
Priority: critical Milestone: someday
Component: core libraries Version: 4.10.x
Keywords: Cc:
Estimated difficulty: hard

Description (last modified by sjamaan)

This is really bad. C_equal is defined to run inline, so it can't clear up stack space, but it consumes stack space! It will just bail out with an exception when it runs out of stack. This is really really bad, because it basically means that you're playing russian roulette every time you call equal?; it can break or not, which depends on the state of the stack, over which you have very little control. It is also very hard to predict when exactly it will fail.

I found this out the hard way.

Here's a standalone version that boils down to the code in the numbers tests:

;; Creates lists like (((1))) and ((((1)))) for 3 and 4, respectively.
(define-syntax recompose
   (lambda (e r c)
     (let ((n (cadr e))
           (op (caddr e))
           (arg (cadddr e)))
       (define (recompose-1 n)
         (if (= n 1)
             `(,op ,arg)
             `(,op ,(recompose-1 (- n 1)))))
       (recompose-1 n)))))

(let lp ((i 0))
  (print i " " (equal? (recompose 1000 list '(1))
                       (recompose 1000 list (list 1))))
  (lp (add1 i)))

You'll see this blows up after only 16 or so iterations. I had to up the list nesting to 1000 because 100 only seems to crash once every blue moon.

A fix could involve dynamically allocating (with malloc or so) a "working list" stack and use that to convert the recursion to a loop. Alternatively, we could "de-inline" it so it can reclaim memory. On the plus side, this allows us to convert it to Scheme. On the downside, we'd be taking a CPS hit.

Originally I thought it might be possible to use the scratch space in CHICKEN 5, but I'm not sure that's suitable in this case because there's nothing in the heap or nursery that points directly to it. We could create one and make an actual Scheme list of "todo" objects, but it would be such a long chain that it would become pretty slow I think.

Change History (6)

comment:1 Changed 21 months ago by sjamaan

  • Description modified (diff)

comment:2 Changed 21 months ago by sjamaan

  • Description modified (diff)

comment:3 Changed 21 months ago by sjamaan

According to Felix, tagged pointer tag comparisons could just be implemented with eq?/eqv?. This would be strictly backwards incompatible, so maybe only do that in CHICKEN 5?

Alternatively, deprecate the whole inline mess, but keep using it for tagged pointers. At the same time, we could also deprecate the fact that it uses equal? and switch to eqv? in a later version.

comment:4 Changed 20 months ago by sjamaan

  • Milestone changed from 4.11.0 to 5.0

comment:5 Changed 13 months ago by sjamaan

  • Estimated difficulty set to hard

comment:6 Changed 11 months ago by sjamaan

  • Milestone changed from 5.0 to someday

It seems that with some of the fixes we've made to prevent runaway stack use, it's not as pressing an issue anymore. The example program no longer crashes, unless the nesting is very extreme (lists of 10000 deep).

Last edited 11 months ago by sjamaan (previous) (diff)
Note: See TracTickets for help on using tickets.