[racket] Immutable vectors

On 09/05/2013 08:42 AM, Konrad Hinsen wrote:
> Scott Klarenbach writes:
>
>   > Check out some of the functional data structures found here:
>   >
>   > http://www.ccs.neu.edu/racket/pubs/sfp10-kth.pdf
>   >
>   > VLists may be of particular interest in your case.
>
> That's the stuff in the pfds package, right?
>
>    https://pkg.racket-lang.org/info/pfds
>
> Interesting indeed, makes me think of Clojure vectors. And written to
> be used as a drop-in replacement for lists. I'll play with that as
> well!
>
> The implementation is in Typed Racket as well, so should I expect the
> same performance problems as with arrays when I work in plain Racket?

Yes. A first-order data structure gets traversed every time it passes 
from untyped to typed code, to ensure its structure conforms to its 
type. This makes all operations Omega(n) in untyped code; i.e. an 
O(log(n)) operation becomes O(n), and an O(n*log(n)) operation remains 
O(n*log(n)).

The best advice I have is to keep performance-critical loops either all 
typed or all untyped, unless the only things that cross the contract 
boundary are flat first-order datums like flonums, strings and vectors. 
(The math library's flonum functions, for example, are plenty fast to 
call from untyped code.) Speeding up the contract boundary is an active 
area of research, so I expect to have to modify this advice in the future.

Neil ⊥