I presume arc3.1 is only faster if you use plt4, which is attributable to plt4 being faster than mzscheme 372 thanks to improvements to the language implementation. The speed boost obviously doesn't come from making conses immutable, since Arc still has mutable conses.
If you're asking why immutable conses could speed up a programming language in general, well, a compiler can make more powerful optimizations if it's allowed to assume that lists won't mutate mid-flight. Obviously a specific program that used mutability of conses would need to be rewritten, and might end up faster or slower; but code that doesn't take advantage of the mutability of conses (of which there is a lot, Scheme having the functional heritage it does) can be speeded up.
Of course, given that Arc's mutable conses are accomplished by using pointer hacking to mutate plt4's supposedly immutable conses, one would hope the plt4 compiler doesn't take real advantage of the immutability of their conses, otherwise it might make assumptions that Arc will break, leading to difficult-to-detect bugs.
; Eli's code to modify mzscheme-4's immutable pairs.
;; to avoid a malloc on every call, reuse a single pointer, but make
;; it thread-local to avoid races
(define ptr (make-thread-cell #f))
(define (get-ptr)
(or (thread-cell-ref ptr)
(let ([p (malloc _scheme 1)]) (thread-cell-set! ptr p) p)))
;; set a pointer to the cons cell, then dereference it as a pointer,
;; and bang the new value in the given offset
(define (set-ca/dr! offset who p x)
(if (pair? p)
(let ([p* (get-ptr)])
(ptr-set! p* _scheme p)
(ptr-set! (ptr-ref p* _pointer 0) _scheme offset x))
(raise-type-error who "pair" p)))
(define (n-set-car! p x) (set-ca/dr! 1 'set-car! p x))
(define (n-set-cdr! p x) (set-ca/dr! 2 'set-cdr! p x))
Really. (This is an excerpt from arc3.1's ac.scm.)
