# How to make \`String.Index\` with \`Int\` offset (distance) in O(1) time?

**URL:** <https://forums.swift.org/t/how-to-make-string-index-with-int-offset-distance-in-o-1-time/28624>\
**Category:** Using Swift\
**Tags:** string\
**Created:** [September 8, 2019, 12:41am UTC](https://forums.swift.org/t/how-to-make-string-index-with-int-offset-distance-in-o-1-time/28624 "2019-09-08T00:41:53Z")\
**Posts on this page:** 1\
**Showing post:** 33

<div class="post-metadata">

**Author:** ![Michael\_Ilseman](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/michael_ilseman/32/44640_2.png) [@Michael\_Ilseman](https://forums.swift.org/u/Michael_Ilseman)\
**Post date:** [September 11, 2019, 6:05pm UTC](https://forums.swift.org/t/how-to-make-string-index-with-int-offset-distance-in-o-1-time/28624/33 "2019-09-11T18:05:02Z")

</div>

> [@gnuoyd](#):
>
> Is there any circumstance where one can rely on those operations to be  
> O(1) on the _UTF16View_ ? That would facilitate creating a fast, compact  
> implementation in Swift of NSTextStorage, which is indexed by UTF-16  
> code units.

They are currently _amortized_ O(1) thanks to breadcrumbing, but there are some caveats in practice. You'll get constant-ish access, but with higher coefficients than if it were natively encoded as UTF-16. You will pay a O(n) scan the very first time you call such a method on the UTF16View. If you mutate the content, that will invalidate the results of the scan, so it will be performed again the next time.

There's a little more written in the [blog post](https://swift.org/blog/utf8-string/) and some [forum discussions](https://forums.swift.org/t/offset-indexing-and-slicing/28333/37).

Swift String still bridges to NSString lazily, and still services NSString's API in amortized O(1) time with these breadcrumbs. Since NSStrings are often accessed through message sends in the first place (at least without access to implementation details), this amortization cost is not generally significant. When we did performance analysis, we absolutely hammered these public interfaces in app-like scenarios and couldn't measure a reasonable regression. But, in theory, if you could subvert Objective-C message sends and CF bridging checks on NSString, then you might tell the difference.

We hope to speed up the constant factors considerably with SIMD work, which I just filed [a bug](https://bugs.swift.org/browse/SR-11455) to track. The savings would allow us to make better performance vs memory tradeoffs. We also don't have any API to expose what the current tradeoff is. If you have any benchmarks or scenarios where you can observe salient performance differences, please let us know.

We don't formally document this guarantee; not until we have a better idea of where [opaque or indirect strings](https://forums.swift.org/t/piercing-the-string-veil/21700) might be headed. But, any String that could be lazily bridged to NSString has to provide performance roughly indistinguishable from O(1).

If you want to provide something like a NSTextStorage equivalent, but supporting both modern UTF-8 interfaces and legacy UTF-16 interfaces, you could consider making the backing be contiguous UTF-8 and rely on these breadcrumbs. Obviously, `Array<UInt16>` would be faster and more direct, but depending on the operation (especially if it's behind a message send), it may not matter. Otherwise, you can also maintain your own mapping between UTF8View indices and UTF16View indices at the cost of greater memory impact.

---

_[View the full topic](https://forums.swift.org/t/how-to-make-string-index-with-int-offset-distance-in-o-1-time/28624)._