With a mutable vector, the fast path for appending an object is to increment the count and store a value at the end. That's two stores. With a persistent vecto

With a mutable vector, the fast path for appending an object is to increment the count and store a value at the end. That's two stores. With a persistent vector, the fast path for appending an object is to allocate memory, copy the old structure into the new one (incurring several write barriers), increment the count, store the new object at the end, and then (eventually) deallocate the old structure. Is it that hard to imagine that the persistent vector fast path will be 80x slower than the mutable vector fast path? As you say, a single cache miss can be responsible for that slowdown, and a cache miss is likely with the freshly allocated memory. So then, by your argument, we ought to characterize the "constant time" persistent vector operation as logarithmic, since it's 80x slower.