Uploaded image for project: 'Swift'
  1. Swift
  2. SR-11335

excessive ARC on String algorithm

    XMLWordPrintable

    Details

      Description

      From the example program https://github.com/adtrevor/ParserBuilder which seems to retain a little to much, I compiled a reduced example which uses the same sort of things from the Swift language: Strings, Substrings, index(after, (Sub)String subscript with index and (Sub)String subscript with a range.

      func find<S: StringProtocol>(_ string: S,
                                   needle1: Character,
                                   needle2: Character?,
                                   needle3: Character?) -> String.Index? {
          var index = string.startIndex
          while index < string.endIndex {
              if string[index] == needle1 {
                  if let needle2 = needle2 {
                      if find(string[string.index(after: index)...],
                              needle1: needle2,
                              needle2: needle3,
                              needle3: nil) == string.index(after: index) {
                        return index
                      }
                  } else {
                      return index
                  }
              }
              index = string.index(after: index)
          }
          return nil
      }
      
      let howMany = 1_000_000
      let end = CommandLine.arguments.dropFirst().reduce(into: "") { $0.append($1) }
      print("xx[\(howMany)]xx\(end)")
      let s = String(repeating: "x", count: howMany) + end
      if let found = find(s, needle1: "f", needle2: "o", needle3: "o") {
          print(s[found ... s.index(after: s.index(after: found))])
      } else {
          print(":( didn't find foo")
      }
      

      The algorithm is a simple algorithm to find the letters foo in a string that is 1M {{x}}s followed by a concatenation of all command line args.

      If we run this like this:

      $ swiftc -O test.swift && sudo dtrace -n 'pid$target::swift_retain*:entry { @c = count(); } :::END { printa(@c); } ' -c './test foo'
      dtrace: description 'pid$target::swift_retain*:entry ' matched 4 probes
      xx[1000000]xxfoo
      foo
      dtrace: pid 25468 has exited
      CPU     ID                    FUNCTION:NAME
        8      2                             :END 
                3000030
      

      we see that this program calls swift_retain over 3M 2M times (for a string that's 1M+3 characters long...) with roughly Xcode 11 beta 6.

      I think that's way too many.

      With swift-DEVELOPMENT-SNAPSHOT-2019-08-03-a.xctoolchain the number of retains drops to 2M 1M, quite good but not good enough .

      Update:

      When running with

      jw-swift-latest swiftc -O test.swift && sudo dtrace -n 'pid$target::swift_retain*:entry { @c[ustack()] = count(); } :::END { printa(@c); } ' -c './test foo'
      

      we can see that 1M of those retains are from String(repeating: "x", count: howMany) which I don't care much about.

                    [smallfry]
      
                    libswiftCore.dylib`swift_retain
                    libswiftCore.dylib`swift_bridgeObjectRetain+0x46
                    libswiftCore.dylib`_StringGuts.append(_:)+0x21c
                    libswiftCore.dylib`specialized String.init(repeating:count:)+0x16e
                    libswiftCore.dylib`String.init(repeating:count:)+0x12
                    test`main+0x26a
                    libdyld.dylib`start+0x1
                    test`0x2
                1000000
      
                    libswiftCore.dylib`swift_retain
                    libswiftCore.dylib`swift_bridgeObjectRetain+0x46
                    test`specialized find<A>(_:needle1:needle2:needle3:)+0x133
                    test`main+0x2d8
                    libdyld.dylib`start+0x1
                    test`0x2
                1000001
      

      Xcode 11 beta 6ish has as expected two retains in find:

                    libswiftCore.dylib`swift_retain
                    libswiftCore.dylib`swift_bridgeObjectRetain+0x46
                    test`specialized find<A>(_:needle1:needle2:needle3:)+0xf8
                    test`main+0x2d8
                    libdyld.dylib`start+0x1
                    test`0x2
                1000001
      
                    libswiftCore.dylib`swift_retain
                    libswiftCore.dylib`swift_bridgeObjectRetain+0x46
                    test`specialized find<A>(_:needle1:needle2:needle3:)+0x1e8
                    test`main+0x2d8
                    libdyld.dylib`start+0x1
                    test`0x2
                1000001
      

        Attachments

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              jw Johannes Weiss
            • Votes:
              0 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

              • Created:
                Updated: