On 10/8/20 5:40 AM, Marc Nieper-Wißkirchen wrote:

> (2) Scheme does not guarantee O(1) access for vector elements. You can
> hardly promise more, I guess. So it is probably safer to write that
> flexvectors have an access time comparable to vectors.

Thinking out loud about this issue in particular:

Performance is the only selling point of flexvectors that distinguishes
them from lists. Contiguousness, in particular, is important for cache
performance. But, if Scheme vectors can promise neither contiguousness
nor O(1) random access, how do I describe the performance guarantees of
flexvectors?

Current idea: "Flexvectors have the same random-access performance
guarantees as ordinary vectors. In particular, if a given Scheme
implements vectors with contiguous memory locations and O(1) random
access and mutation, flexvectors must also have these performance
characteristics. Additionally, appending to the back of a flexvector has
the same (amortized) performance as setting an existing location in the
same flexvector."