Skip to content

Commit

Permalink
seq: optimize append
Browse files Browse the repository at this point in the history
There are two changes in this commit.

The first change builds the list from a variadic append operation
from right to left, which is the natural order for list construction.
This speeds up the following program:

```
(time
 (void
  (append* (for/list ([i 30000])
             (if b '() '(1))))))
```

from 5 seconds to 1 second.

The second change avoids making an assertion when doing unsafe/append
on two symbolic unions. This is fine because all calls to unsafe/append
is already guarded via type casting to make them symbolic unions
of rosette-contract?, so there is no need to add another guard.

Thanks to @camoy for raising up the issue about the unnecessary assertions.
  • Loading branch information
sorawee committed Mar 12, 2024
1 parent edf682d commit d905189
Showing 1 changed file with 6 additions and 9 deletions.
15 changes: 6 additions & 9 deletions rosette/base/adt/seq.rkt
Original file line number Diff line number Diff line change
Expand Up @@ -69,22 +69,19 @@
[((? racket-contract?) (union vs)) (unsafe-merge** vs (proc xs _))]
[((union vs) (? racket-contract?)) (unsafe-merge** vs (proc _ ys))]
[((union vs) (union ws))
(apply unsafe-merge*
(assert-some
(for*/list ([v vs] [w ws] [g (in-value (&& (car v) (car w)))] #:when g)
(cons g (proc (cdr v) (cdr w))))
#:unless (* (length vs) (length ws))
(arguments-error (quote proc) (format "expected ~a ~a" rosette-contract? rosette-contract?)
"first argument" vs "second argument" ws)))]))]
(apply unsafe-merge*
(for*/list ([v vs] [w ws] [g (in-value (&& (car v) (car w)))] #:when g)
(cons g (proc (cdr v) (cdr w)))))]))]
(define #,(lift-id #'proc)
(case-lambda
[() (racket-constructor)]
[(xs) (type-cast rosette-contract? xs (quote proc))]
[(xs ys) (unsafe/append (type-cast rosette-contract? xs (quote proc))
(type-cast rosette-contract? ys (quote proc)))]
[xss (for/fold ([out (racket-constructor)])
([xs (for/list ([ys xss]) (type-cast rosette-contract? ys (quote proc)))])
(unsafe/append out xs))])))]))
([xs (for/list ([ys (in-list (reverse xss))])
(type-cast rosette-contract? ys (quote proc)))])
(unsafe/append xs out))])))]))

(define-syntax (define/lift/split stx)
(syntax-case stx ()
Expand Down

0 comments on commit d905189

Please sign in to comment.