<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="">Hi Swift-Dev, <div class=""><br class=""></div><div class="">We care deeply about the size of binaries that are generated by the Swift compiler and make an effort to optimize and shrink the generated binaries. One of the problems that we have today is that swift symbols are mangled into extremely long strings. This is especially a problem for libraries, and almost half of the size of libswiftCore.dylib (the swift runtime library on x86_64 OSX) is string tables. On MacOSX you can use the command ’size -m file.dylib’ to read the size of the string table. C++ also suffers from the problem of long names, but since we control the Swift ABI we can do better than C++.</div><div class=""><br class=""></div><div class="">Here are two names that I found in our libraries:</div><div class=""><br class=""></div><div class=""><div class=""><b class=""> __TIF14StdlibUnittest13checkSequenceu0_Rxs14CollectionType_s12SequenceTypeWx9Generator7Element_zW_9GeneratorS3__rFTxq_KT_SS9showFrameSb10stackTraceVS_14SourceLocStack4fileSS4lineSu16resiliencyChecksVS_32CollectionMisuseResiliencyChecks9sameValueFTWxS2_S3__WxS2_S3___Sb_T_A6_</b></div></div><div class=""><br class=""></div><div class=""><div class=""> <b class="">__TTSg5VSS13CharacterViewS_s14CollectionTypes_GVs17IndexingGeneratorS__GS1_S__s13GeneratorTypes_VS_5IndexS3_s16ForwardIndexTypes_SiSis18_SignedIntegerTypes_SiSis33_BuiltinIntegerLiteralConvertibles_Vs20_DisabledRangeIndex__S_S_s9IndexablesS_s12SequenceTypes_GS1_S__GS1_S__S2_s_Vs9Character_S3_S3_S4_s_SiSiS5_s_SiSiS6_s_S7__S__S10__S10____TFFSS12replaceRangeuRxs14CollectionTypeWx9Generator7Element_zVs9CharacterrFTGVs5RangeVVSS13CharacterView5Index_4withx_T_U_FRS4_T_</b></div></div><div class=""><br class=""></div><div class="">One way to solve this problem is to implement a better string table format that will include some kind of compression or tree encoding into MachO, ELF and PE. The work on MachO, ELF and PE is beyond the scope of the Swift project and I’d like to focus on improving things on the Swift side. </div><div class=""><br class=""></div><div class="">I see two independent tasks that we can do to shorten the length of string symbols. First, we can improve the existing mangling. We can do things like use non-decimal length specifiers, etc. The second task, which is the subject of the rest of this email, is the implementation of a compression layer on top of the existing mangling scheme. </div><div class=""><br class=""></div><div class=""><b class=""><u class="">Compressing long symbols</u></b></div><div class=""> </div><div class="">The Swift compiler is free to encode Swift names in whatever way it likes, but we need to follow a few basic rules. First, the character encoding space needs to be [_a-zA-Z0-9]. We can’t use non-ascii characters to encode Swift names because this is the character space that ELF supports. Second, names need to be unique and independent. We can’t just compress the whole string table or create names that are a running counter because we need to be able to inspect each name independently. We need to be able to decode the name independently and extract the information that’s stored in the name. We also need to be able to decode the name to be able to present something useful in the debugger. This means that a simple one directional hashing of the name is not an option.</div><div class=""><br class=""></div><div class="">With these restrictions in mind, I believe that the problem that we need to solve is independent compression of names. I suggest that we add a post-processing string compression pass. The input to the compress method would be a string mangled name, like the two names I showed above, and the output would be a shorter string. We would also need a decompression method that would return the original string. </div><div class=""><br class=""></div><div class="">Obviously, gzipping each string independently won’t be effective. I believe that we need to implement our own compression algorithm here that will work with the restrictions that I mentioned above (being textual) and with the prior knowledge we have. </div><div class=""><br class=""></div><div class=""><b class=""><u class=""><br class=""></u></b></div><div class=""><b class=""><u class="">Example of a basic compression algorithm</u></b> </div><div class=""><br class=""></div><div class="">In this section I describe a trivial compression algorithm that can reduce the size of the string tables by 30%. This algorithm is not optimal but it is a good starting point for our discussion. One example of "prior knowledge” that I mentioned above is that we know what are the common sub-strings that are used in Swift names. Some of the most common substrings in Swift mangled names are:</div><div class=""><br class=""></div><div class="">1. "S_S_S_S"</div><div class="">2. "ollectio” </div><div class="">3. “Type”</div><div class="">4. “Index”</div><div class="">5. “erator”</div><div class="">6. “7Element"</div><div class="">7. “able"</div><div class=""><br class=""></div><div class="">We can use this prior knowledge about names of Swift types to compress our mangling! Consider the following encoding:</div><div class=""><br class=""></div><div class="">A string like this:</div><div class=""><br class=""></div><div class=""><b class="">__TTSg5VSS13CharacterView</b></div><div class=""><b class=""><br class=""></b></div><div class="">Would be translated into something like:</div><div class=""><br class=""></div><div class=""><span class="" style="font-weight: bold;">__TTSg5</span><reference to word #67><span class="" style="font-weight: bold;">13</span><reference to word #43><span class="" style="font-weight: bold;">View</span></div><div class=""><br class=""></div><div class="">Commonly used strings can be encoded as references to global tables. We need to have some escape character (that needs to be ascii-printable), and use that character to encode the reference. </div><div class="">One interesting bit of information is that the character ‘Y’ is only used 4 times in the entire standard library! The letter J, and a few other letters are also not used very frequently. We can use these letters as escape characters. </div><div class=""><br class=""></div><div class="">The basic encoding that I experimented with used the following rules:</div><div class=""><br class=""></div><div class="">1. Use two escape characters that are not frequently used in names (Y and Z). These characters are escape character and can’t be used without escaping. ‘Y’ will be encoded as ‘YY’, and ‘Z’ would be encoded as ‘YZ’. </div><div class=""><br class=""></div><div class="">2. The most commonly used sub-strings (calculated as length of substring times number of occurrences) would be encoded with a single escape character and a single index character. The table of highly repetitive substrings can only contain 61 entries (a-zA-Z0-9_, minus two escape characters).</div><div class=""><br class=""></div><div class="">A reference to the very frequent substrings would be encoded as “Yx”, where x is the character that’s translated into a numeric index. This is two chars per substring. </div><div class=""><br class=""></div><div class="">3. The less commonly used substrings are encoded as three-character sequence. “Zxx”, where xx is the numeric index in the large table (that can hold 63*63 substrings).</div><div class=""><br class=""></div><div class="">It is obvious how to reverse this compression using the same string table used to compress the names. </div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">With this encoding scheme the name “<b class="">__TwxxV14StdlibUnittest24MinimalForwardCollection</b>” becomes “<b class="">Y5wxxJ0UJ1HJ3_Jyn4J5VJ6SdY9on</b>” and the name “<b class="">__TMPVs15ContiguousArray</b>” becomes “<b class="">Y5MPJ3r5J5EJ82</b>”.</div><div class=""><br class=""></div><div class="">I benchmarked this basic technique by using 5 dylibs as the training set (SwiftCore, Simd, unittests, etc) and compressed the string tables of these binaries. The result was a ~31% reduction in size.</div><div class=""><br class=""></div><div class=""><img apple-inline="yes" id="B97BAEBF-7DBB-42FB-A24F-7071E5144DCB" height="288" width="474" apple-width="yes" apple-height="yes" src="cid:9242B717-F728-4A70-86CF-30A5EE04373E@hsd1.ca.comcast.net." class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">On the Swift dylib itself (training set and input to the compressor) the wins are about ~25%.</div><div class=""><br class=""></div><div class="">This encoding makes the symbol name a lot less intuitive for humans, but at the SIL-level we already print human readable strings above function names as comments. I believe that the debugger would just work as-is since the internal APIs won’t change. </div><div class=""><br class=""></div><div class="">One of the disadvantages of using a constant string table is that once we rename the APIs in the standard library the string table would be less effective in compressing it and code that uses it. </div><div class=""><b class=""><u class=""><br class=""></u></b></div><div class=""><b class=""><u class="">What’s next?</u></b></div><div class=""><br class=""></div><div class="">The small experiment I described above showed that compressing the names in the string table has a huge potential for reducing the size of swift binaries. I’d like for us (swift-developers) to talk about the implications of this change and start working on the two tasks of tightening our existing mangling format and on implementing a new compression layer on top. </div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Nadav</div></body></html>