[Swift] Int(String(SubString)), Int(SubString)의 속도 차이 원인

안녕하세요 Pingu입니다🐧

 

백준에서 알고리즘 문제들을 Swift 언어로 풀다 보면 가끔 Int(String(Substring))은 시간 초과가 안 나는데 Int(Substring)은 시간 초과가 나는 것을 겪었었는데요, 예를 들면 아래 문제가 있습니다.

icksw.tistory.com/93

[백준] 1753번 최단 경로 [Swift]

 

이거 때문에 날린 시간이 너무 억울해서 도대체 왜 이런가에 대해 한 번 알아봤습니다.😂

 

참고 자료는 실제 Swift의 구현 코드 입니다.

https://github.com/apple/swift/blob/main/stdlib/public/core/IntegerParsing.swift

apple/swift

public init?<S: StringProtocol>(_ text: S, radix: Int = 10) {
    _precondition(2...36 ~= radix, "Radix not in range 2...36")

    if let str = text as? String, str._guts.isFastUTF8 {
      guard let ret = str._guts.withFastUTF8 ({ utf8 -> Self? in
        var iter = utf8.makeIterator()
        return _parseASCII(codeUnits: &iter, radix: Self(radix))
      }) else {
        return nil
      }
      self = ret
      return
    }

    // TODO(String performance): We can provide fast paths for common radices,
    // native UTF-8 storage, etc.

    var iter = text.utf8.makeIterator()
    guard let ret = Self._parseASCIISlowPath(
      codeUnits: &iter, radix: Self(radix)
    ) else { return nil }

    self = ret
}

위의 부분이 StringProtocol을 채택한 타입들을 Int로 변환하는 부분입니다.

 

코드 부분을 나눠서 한 번 살펴보겠습니다.

 

String을 Int로 파싱 할 때

if let str = text as? String, str._guts.isFastUTF8 {
    guard let ret = str._guts.withFastUTF8 ({ utf8 -> Self? in
        var iter = utf8.makeIterator()
        return _parseASCII(codeUnits: &iter, radix: Self(radix))
    }) else {
        return nil
    }
    self = ret
    return
}

위의 부분을 보시면 String으로 타입 캐스팅에 성공하면 str._guts.isFastUTF8 이라는 부분을 확인합니다.

만약 이 부분이 true라면 바로 파싱 된 값을 반환합니다. 

_guts.isFastUTF8는 해당 객체가 fastPath를 지원하는지에 대한 여부를 반환해주며 아래와 같이 구현되어 있어요.

internal var isFastUTF8: Bool { return _fastPath(_object.providesFastUTF8) }

즉 fastPath를 지원한다면 해당 값으로 _guts.withFastUTF8를 수행합니다.

_guts.withFastUTF8은 아래와 같이 구현되어있습니다.

@inlinable @inline(__always)
  internal func withFastUTF8<R>(
    _ f: (UnsafeBufferPointer<UInt8>) throws -> R
  ) rethrows -> R {
    _internalInvariant(isFastUTF8)

    if self.isSmall { return try _SmallString(_object).withUTF8(f) }

    defer { _fixLifetime(self) }
    return try f(_object.fastUTF8)
  }

  @inlinable @inline(__always)
  internal func withFastUTF8<R>(
    range: Range<Int>,
    _ f: (UnsafeBufferPointer<UInt8>) throws -> R
  ) rethrows -> R {
    return try self.withFastUTF8 { wholeUTF8 in
      return try f(UnsafeBufferPointer(rebasing: wholeUTF8[range]))
    }
  }

이 부분도 성공적으로 수행하면 드디어 반환합니다.

 

만약 이 부분에서 false가 나오거나 실패하게 된다면 다음으로 가게 되면 아래 코드가 수행됩니다.

String이 아닌 StringProtocol 타입의 값을 Int로 파싱 할 때

var iter = text.utf8.makeIterator()
guard let ret = Self._parseASCIISlowPath(
      codeUnits: &iter, radix: Self(radix)
) else { return nil }

타입 캐스팅에 실패하면 Self._parseASCIISlowPath를 수행하는 것을 볼 수 있는데요, _parseASCIISlowPath는 아래와 같이 구현되어 있습니다.

internal static func _parseASCIISlowPath<
    CodeUnits: IteratorProtocol, Result: FixedWidthInteger
  >(
    codeUnits: inout CodeUnits, radix: Result
  ) -> Result?
  where CodeUnits.Element: UnsignedInteger {
    return _parseASCII(codeUnits: &codeUnits, radix: radix)
}

 물론 두 부분 다 실패하면 nil을 반환하는 건 같습니다. 하지만 재밌는 건 하나는 Fast이고 하나는 Slow라는 점입니다. 즉 String 타입은 따로 취급을 받아 빠르게 처리가 된다는 것을 알 수 있어요.

 

근데 Substring은 String 타입으로 사용할 수 없나??라는 질문이 발생해서 Substring의 정의 부분을 살펴봤습니다.

위와 같은 주석을 찾을 수 있었는데요, Substring을 String으로 사용하려면 String(_:) 생성자로 새로운 String을 생성하여 사용해야 한다! 라고 적혀있습니다.

 

오!!

 

이건 Swift 문서에도 나와있는 내용입니다.

Substring은 String의 메모리 공간을 참조만 하고 있기 때문에 String으로 사용하려면 실제로 메모리를 할당해줘야 한다고 되어있었어요.

 

즉 결론은 Substring를 fastpath로 분기시켜주기 위해서는 String값으로 변환해준 뒤 수행해야 한다! 라는 것입니다. 그렇지 않으면 slowPath로 분기되어 느리게 처리되는 것이었어요.

 

Int(String(Substring))이 더 빠른 이유를 이젠 알 것 같아요!

 

감사합니다