Arc 3.1‎ > ‎

Optimizations

These are some improvements (changes, at any rate) that you can make to the internals of arc3.1 to make things run faster/better.

case-lambda for some variadic functions.

Use Racket's case-lambda to define some of the n-argument functions that are almost always called with two arguments, such as >, <, is, and +.  For example, in ac.scm, we see:

(xdef < (lambda args (pairwise ar-<2 args)))

The problem with this is that it conses--it allocates memory, probably for the argument list, which is immediately thrown away.  Thus, it generates garbage (to be specific, 64 bytes per call on waterhouse's 64-bit Racket build), which triggers garbage collections, which are annoying and inconvenient.  Ideally, it would allocate 0 bytes per call.

Now, arc3.1 allows you to set a few compiler flags with a function called declare, and if you go (declare 'direct-calls t), then the Arc expression (< a b) will get compiled into (ar-<2 a b)--which does not cons--instead of (ar-funcall2 _< a b).  It has special cases for binary versions of all four abovementioned functions.  However, this is insufficient: if you say (sort < xs) or (reduce + xs), even with direct-calls activated, it will use the memory-allocating n-argument version.  (You might think we could teach the compiler to compile that as (sort ar-<2 xs).  This would require it figuring out that < will only be called with two arguments in this context, which seems rather difficult to do in a way that would scale to, say, user-defined functions to which < is passed as an argument.)

The solution is to use Racket's case-lambda.  It allocates zero memory in the two-argument case, as desired.

(xdef < (case-lambda
          ((x y) (ar-<2 x y))
          (args (pairwise ar-<2 args))))

We can do likewise for the other wannabe-binary functions.  If we have access with $ to the underlying Racket, then we can cover all these cases relatively elegantly with a macro from the Arc frontend, instead of modifying ac.scm:

(mac cl-binary (f)
  (let bname (sym:string "ar-" f 2)
    `($:case-lambda
       ((x y) (,bname x y))
       (args (pairwise ,bname args))))))

(= <  cl-binary.<
   >  cl-binary.>
   is cl-binary.is)

Unfortunately, pairwise is only for predicates, so if we want to handle + as well, it'll have to be a special case.

(= + ($:case-lambda
      ((x y) (ar-+2 x y))
      (args (cond ((null? args) 0)
                 ((char-or-string? (car args))
                  (apply string-append 
                         (map (lambda (a) (ar-coerce a 'string))
                              args)))
                 ((arc-list? (car args)) 
                  (ac-niltree (apply append (map ar-nil-terminate args))))
                 (#t (apply + args))))))

Improve len.

In arc3.1, list lengths are calculated like this:

(xdef len (lambda (x)
             (cond ((string? x) (string-length x))
                   ((hash-table? x) (hash-table-count x))
                   (#t (length (ar-nil-terminate x))))))

(ar-nil-terminate x) copies the entire list into a Racket ()-terminated list, and then we use the built-in length function.  This produces O(n) garbage. *cringe* Here is a version that produces zero garbage.

(xdef len (lambda (x)
             (cond ((string? x) (string-length x))
                   ((hash-table? x) (hash-table-count x))
                   (#t (ar-length x)))))

(define (ar-length x)
  (let loop ((x x) (n 0))
    (if (or (eqv? x 'nil) (null? x))
        n
        (loop (cdr x) (+ n 1)))))

Properly mutate Racket lists.

In addition, you can use the destructive list-reversal function nrev (also described in the link) in place of rev when the list to be reversed may be destroyed.  Usually this is when the list has just been constructed, as in accumdrainn-of, and dedup.  If desired, one could also construct destructive versions of map, keep/rem, join, and probably others.
Comments