<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">On Jan 10, 2018, at 11:55 AM, Michael Ilseman via swift-dev <<a href="mailto:swift-dev@swift.org" class="">swift-dev@swift.org</a>> wrote:<div><blockquote type="cite" class=""><div class=""><meta http-equiv="Content-Type" content="text/html; charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">(A gist-formatted version of this email can be found at <a href="https://gist.github.com/milseman/bb39ef7f170641ae52c13600a512782f" class="">https://gist.github.com/milseman/bb39ef7f170641ae52c13600a512782f</a>)<br class=""></div></div></blockquote><div><br class=""></div>I’m very very excited for this, thank you for the detailed writeup and consideration of the effects and tradeoffs involved.</div><div><br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Given that ordering is not fit for human consumption, but rather machine processing, it might as well be fast. The current ordering differs on Darwin and Linux platforms, with Linux in particular suffering from poor performance due to choice of ordering (UCA with DUCET) and older versions of ICU. Instead, [String Comparison Prototype](<a href="https://github.com/apple/swift/pull/12115" class="">https://github.com/apple/swift/pull/12115</a>) provides a simpler ordering that allows for many common-case fast-paths and optimizations. For all the Unicode enthusiasts out there, this is the lexicographical ordering of NFC-normalized UTF-16 code units.<br class=""></div></div></blockquote><div><br class=""></div>Thank you for fixing this. Your tradeoffs make perfect sense to me.</div><div><br class=""></div><div><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">### Small String Optimization<br class=""></div></div></blockquote>..<br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">For example, assuming a 16-byte String struct and 8 bits used for flags and discriminators (including discriminators for which small form a String is in), 120 bits are available for a small string payload. 120 bits can hold 7 UTF-16 code units, which is sufficient for most graphemes and many common words and separators. 120 bits can also fit 15 ASCII/UTF-8 code units without any packing, which suffices for many programmer/system strings (which have a strong skew towards ASCII).<br class=""><br class="">We may also want a compact 5-bit encoding for formatted numbers, such as 64-bit memory addresses in hex, `Int.max` in base-10, and `Double` in base-10, which would require 18, 19, and 24 characters respectively. 120 bits with a 5-bit encoding would fit all of these. This would speed up the creation and interpolation of many strings containing numbers.<br class=""></div></div></blockquote><div><br class=""></div><div>I think it is important to consider that having more special cases and different representations slows down nearly *every* operation on string because they have to check and detangle all of the possible representations. Given the ability to hold 15 digits of ascii, I don’t see why it would be worthwhile to worry about a 5-bit representation for digits. String should be an Any!</div><div><br class=""></div><div>The tradeoff here is that you’d be biasing the design to favor creation and interpolation of many strings containing *large* numbers, at the cost of general string performance anywhere. This doesn’t sound like a good tradeoff for me, particularly when people writing extremely performance sensitive code probably won’t find it good enough anyway.</div><br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Final details are still in exploration. If the construction and interpretation of small bit patterns can remain behind a resilience barrier, new forms could be added in the future. However, the performance impact of this would need to be carefully evaluated.<br class=""></div></div></blockquote><div><br class=""></div><div>I’d love to see performance numbers on this. Have you considered a design where you have exactly one small string representation: a sequence of 15 UTF8 bytes? This holds your 15 bytes of ascii, probably more non-ascii characters on average than 7 UTF16 codepoints, and only needs one determinator branch on the entry point of hot functions that want to touch the bytes. If you have a lot of algorithms that are sped up by knowing they have ascii, you could go with two bits: “is small” and “isascii”, where isascii is set in both the small string and normal string cases.</div><div><br class=""></div><div>Finally, what tradeoffs do you see between a 1-word vs 2-word string? Are we really destined to have 2-words? That’s still much better than the 3 words we have now, but for some workloads it is a significant bloat.</div><div><br class=""></div><div><br class=""></div><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">### Unmanaged Strings<br class=""><br class="">Such unmanaged strings can be used when the lifetime of the storage is known to outlive all uses. </div></div></blockquote><div><br class=""></div><div>Just like StringRef! +1, this concept can be a huge performance win… but can also be a huge source of UB if used wrong.. :-(</div><br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">As such, they don’t need to participate in reference counting. In the future, perhaps with ownership annotations or sophisticated static analysis, Swift could convert managed strings into unmanaged ones as an optimization when it knows the contents would not escape. Similarly in the future, a String constructed from a Substring that is known to not outlive the Substring’s owner can use an unmanaged form to skip copying the contents. This would benefit String’s status as the recommended common-currency type for API design.<br class=""></div></div></blockquote><div><br class=""></div><div>This could also have implications for StaticString.</div><br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">Some kind of unmanaged string construct is an often-requested feature for highly performance-sensitive code. We haven’t thought too deeply about how best to surface this as API and it can be sliced and diced many ways. Some considerations:<br class=""></div></div></blockquote><div><br class=""></div><div>Other questions/considerations:</div><div>- here and now, could we get the vast majority of this benefit by having the ABI pass string arguments as +0 and guarantee their lifetime across calls? What is the tradeoff of that?</div><div>- does this concept even matter if/when we can write an argument as “borrowed String”? I suppose this is a bit more general in that it should be usable as properties and other things that the (initial) ownership design isn’t scoped to support since it doesn’t have lifetimes.</div><div>- array has exactly the same sort of concern, why is this a string-specific problem?</div><div>- how does this work with mutation? Wouldn’t we really have to have something like MutableArrayRef since its talking about the mutability of the elements, not something that var/let can support?</div><div><br class=""></div><div>When I think about this, it seems like an “non-owning *slice*” of some sort. If you went that direction, then you wouldn’t have to build it into the String currency type, just like it isn’t in LLVM.</div><div><br class=""></div><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">### Performance Flags<br class=""></div></div></blockquote><div><br class=""></div>Nice.</div><div><br class=""></div><div><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">### Miscellaneous<br class=""><br class="">There are many other tweaks and improvements possible under the new ABI prior to stabilization, such as:<br class=""><br class="">* Guaranteed nul-termination for String’s storage classes for faster C bridging.<br class=""></div></div></blockquote><div><br class=""></div><div>This is probably best as another perf flag.</div><br class=""><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">* Unification of String and Substring’s various Views.<br class="">* Some form of opaque string, such as an existential, which can be used as an extension point.<br class="">* More compact/performant indices.<br class=""></div></div></blockquote><div><br class=""></div><div>What is the current theory on eager vs lazy bridging with Objective-C? Can we get to an eager bridging model? That alone would dramatically simplify and speed up every operation on a Swift string.</div><div><br class=""></div><blockquote type="cite" class=""><div class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">## String Ergonomics<br class=""></div></div></blockquote><div><br class=""></div></div>I need to run now, but I’ll read and comment on this section when I have a chance.<div class=""><br class=""></div><div class="">That said, just today I had to write the code below and the ‘charToByte’ part of it is absolutely tragic. Is there any thoughts about how to improve character literal processing?<div class=""><br class=""></div><div class=""><div class="">-Chris</div></div><div class=""><br class=""></div><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""><span style="color: #ba2da2" class="">func</span> decodeHex(<span style="color: #ba2da2" class="">_</span> string: <span style="color: #703daa" class="">String</span>) -> [<span style="color: #703daa" class="">UInt8</span>] {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""> <span style="color: #ba2da2" class="">func</span> charToByte(<span style="color: #ba2da2" class="">_</span> c: <span style="color: #703daa" class="">String</span>) -> <span style="color: #703daa" class="">UInt8</span> {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(0, 132, 0); background-color: rgb(255, 255, 255);" class=""><span style="color: #000000" class=""> </span><span style="color: #ba2da2" class="">return</span><span style="color: #000000" class=""> c.</span><span style="color: #703daa" class="">utf8</span><span style="color: #000000" class="">.</span><span style="color: #703daa" class="">first</span><span style="color: #000000" class="">! </span>// swift makes char processing grotty. :-(</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""> }</div><div style="margin: 0px; line-height: normal; background-color: rgb(255, 255, 255); min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""> <span style="color: #ba2da2" class="">func</span> hexToInt(<span style="color: #ba2da2" class="">_</span> c : <span style="color: #703daa" class="">UInt8</span>) -> <span style="color: #703daa" class="">UInt8</span> {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""> <span style="color: #ba2da2" class="">switch</span> c {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(49, 89, 93); background-color: rgb(255, 255, 255);" class=""><span style="color: #000000" class=""> </span><span style="color: #ba2da2" class="">case</span><span style="color: #000000" class=""> </span>charToByte<span style="color: #000000" class="">(</span><span style="color: #d12f1b" class="">"0"</span><span style="color: #000000" class="">)...</span>charToByte<span style="color: #000000" class="">(</span><span style="color: #d12f1b" class="">"9"</span><span style="color: #000000" class="">): </span><span style="color: #ba2da2" class="">return</span><span style="color: #000000" class=""> c - </span>charToByte<span style="color: #000000" class="">(</span><span style="color: #d12f1b" class="">"0"</span><span style="color: #000000" class="">)</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(49, 89, 93); background-color: rgb(255, 255, 255);" class=""><span style="color: #000000" class=""> </span><span style="color: #ba2da2" class="">case</span><span style="color: #000000" class=""> </span>charToByte<span style="color: #000000" class="">(</span><span style="color: #d12f1b" class="">"a"</span><span style="color: #000000" class="">)...</span>charToByte<span style="color: #000000" class="">(</span><span style="color: #d12f1b" class="">"f"</span><span style="color: #000000" class="">): </span><span style="color: #ba2da2" class="">return</span><span style="color: #000000" class=""> c - </span>charToByte<span style="color: #000000" class="">(</span><span style="color: #d12f1b" class="">"a"</span><span style="color: #000000" class="">) + </span><span style="color: #272ad8" class="">10</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(49, 89, 93); background-color: rgb(255, 255, 255);" class=""><span style="color: #000000" class=""> </span><span style="color: #ba2da2" class="">case</span><span style="color: #000000" class=""> </span>charToByte<span style="color: #000000" class="">(</span><span style="color: #d12f1b" class="">"A"</span><span style="color: #000000" class="">)...</span>charToByte<span style="color: #000000" class="">(</span><span style="color: #d12f1b" class="">"F"</span><span style="color: #000000" class="">): </span><span style="color: #ba2da2" class="">return</span><span style="color: #000000" class=""> c - </span>charToByte<span style="color: #000000" class="">(</span><span style="color: #d12f1b" class="">"A"</span><span style="color: #000000" class="">) + </span><span style="color: #272ad8" class="">10</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(209, 47, 27); background-color: rgb(255, 255, 255);" class=""><span style="color: #000000" class=""> </span><span style="color: #ba2da2" class="">default</span><span style="color: #000000" class="">: </span><span style="color: #3e1e81" class="">fatalError</span><span style="color: #000000" class="">(</span>"invalid hexadecimal character"<span style="color: #000000" class="">)</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""> }</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""> }</div><div style="margin: 0px; line-height: normal; background-color: rgb(255, 255, 255); min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""> <span style="color: #ba2da2" class="">var</span> result: [<span style="color: #703daa" class="">UInt8</span>] = []</div><div style="margin: 0px; line-height: normal; background-color: rgb(255, 255, 255); min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(209, 47, 27); background-color: rgb(255, 255, 255);" class=""><span style="color: #000000" class=""> </span><span style="color: #3e1e81" class="">assert</span><span style="color: #000000" class="">(string.</span><span style="color: #703daa" class="">count</span><span style="color: #000000" class=""> & </span><span style="color: #272ad8" class="">1</span><span style="color: #000000" class=""> == </span><span style="color: #272ad8" class="">0</span><span style="color: #000000" class="">, </span>"must get a pair of hexadecimal characters"<span style="color: #000000" class="">)</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""> <span style="color: #ba2da2" class="">var</span> it = string.<span style="color: #703daa" class="">utf8</span>.<span style="color: #3e1e81" class="">makeIterator</span>()</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""> <span style="color: #ba2da2" class="">while</span> <span style="color: #ba2da2" class="">let</span> byte1 = it.<span style="color: #3e1e81" class="">next</span>(),</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""> <span style="color: #ba2da2" class="">let</span> byte2 = it.<span style="color: #3e1e81" class="">next</span>() {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""> result.<span style="color: #3e1e81" class="">append</span>((<span style="color: #31595d" class="">hexToInt</span>(byte1) << <span style="color: #272ad8" class="">4</span>) | <span style="color: #31595d" class="">hexToInt</span>(byte2))</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""> }</div><div style="margin: 0px; line-height: normal; background-color: rgb(255, 255, 255); min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class=""> <span style="color: #ba2da2" class="">return</span> result</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; background-color: rgb(255, 255, 255);" class="">}</div><div style="margin: 0px; line-height: normal; background-color: rgb(255, 255, 255); min-height: 14px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(49, 89, 93); background-color: rgb(255, 255, 255);" class=""><span style="color: #3e1e81" class="">print</span><span style="color: #000000" class="">(</span>decodeHex<span style="color: #000000" class="">(</span><span style="color: #d12f1b" class="">"01FF"</span><span style="color: #000000" class="">))</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(49, 89, 93); background-color: rgb(255, 255, 255);" class=""><span style="color: #3e1e81" class="">print</span><span style="color: #000000" class="">(</span>decodeHex<span style="color: #000000" class="">(</span><span style="color: #d12f1b" class="">"8001"</span><span style="color: #000000" class="">))</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(209, 47, 27); background-color: rgb(255, 255, 255);" class=""><span style="color: #3e1e81" class="">print</span><span style="color: #000000" class="">(</span><span style="color: #31595d" class="">decodeHex</span><span style="color: #000000" class="">(</span>"80a1bcd3"<span style="color: #000000" class="">))</span></div></div><div class=""><br class=""><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><br class=""></div></div></div></body></html>