Ускоряем .dropLast()

18.07.2020

3 мин

Недавно я разработал приложение для оценки времени сборки проекта. Сначала взял готовый парсер Xcode логов, затем написал свой. В итоге приложение ускорилось на 95%. А в этом посте опишу подход к оптимизации кода на примере метода .dropLast().

Подготовка

Давайте подготовим пример, напишем метод .skip(). Его задача пропустить последний символ из строки.

1. Берем последний символ если он есть;
2. Удаляем его с помощью метода .dropLast();
3. Возвращаем удаленный символ.

Также пометим этот метод @discardableResult, так как скорее всего нам не нужен пропущенный символ.

@discardableResult
mutating func skip() -> Character? {
    guard let last = content.last else { return nil }
    content = content.dropLast()
    return last
}

Измеряем

Отлично, но предположим у нас появилось подозрение, что написанный нами метод медленный. Как это проверить? Можно написать тест с помощью measure(). Для простоты, я не буду проверять результат через XCTAssert. Иначе пример будет сложнее.

1. Создаем большую строку "аааааа...";
2. Создаем Scanner, где мы объявили метод .skip();
3. Используем функцию measure() для оценки скорости выполнения;
4. И наконец вызываем наш метод .skip().

func testSkip() {
    let src = String(repeating: "a", count: 10_000_000)
    var scanner = Scanner(src)
    measure {
        scanner.skip()
    }
}

Давайте запустим этот тест.

Итак, теперь нам необходимо выставить baseline. Это базовое значение, относительно которого мы будем оценивать стало ли решение лучше или хуже.

Запускаем ещё раз после установки baseline.

Подозрительно медленно. Но мы получили оценку метода. Теперь можем попробовать улучшить его реализацию и посмотреть изменилась ли скорость выполнения. Давайте попробуем.

Своя реализация .dropLast с блэкджеком

До этого момента я не упоминал, что Scanner работает не с типом String. На самом деле он использует более оптимальный для изменений тип SubString. Этот тип не создает копию строки.

Вместо того чтобы убирать последний символ, создадим SubString с длиной на один символ меньше. Но в Swift с индексами строк всё не так просто. Символы не фиксированной длинны и поэтому индексы не являются целыми числами. Мы не сможем написать так content[0..<(content.count - 1)].

1. Вместо этого получим последний индекс content.endIndex;
2. А затем сдвинем его с помощью content.index(before:);
3. После этого мы сможем взять строку без последнего символа content[..<secondLast].

@discardableResult
mutating func skip() -> Character? {
    guard let last = content.last else { return nil }
    let secondLast = content.index(before: content.endIndex)
    content = content[..<secondLast]
    return last
}

Запускаем тест ещё раз.

Ииии 0.000 sec, 100% better! Вот так то лучше!

Но почему так вышло?

Чтобы разобраться с этим давайте обратимся к документации метода. Ниже я привожу лишь самый важный отрывок.

/// - Complexity: O(1) if the collection conforms to RandomAccessCollection;
/// otherwise, O(k), where k is the number of elements to drop.

String не поддерживает RandomAccessCollection. Как я упоминал выше, мы не можем обращаться к символу по целочисленному индексу. Вместо этого нам нужно его высчитывать с помощью методов строки. Но как нам удалось написать быстрее используя только индексы?

Swift STD

Давайте пойдем чуть дальше и посмотрим на реализацию метода .dropLast(). Стандартная библиотека Swift лежит в открытом доступе на GitHub. Скачаем её и найдем нужный метод с помощью grep.

swift-master ••• grep --color=always -r "func dropLast(_ k" *
stdlib/public/core/Collection.swift: func dropLast(_ k: Int = 1) -> SubSequence
stdlib/public/core/Sequence.swift: func dropLast(_ k: Int = 1) -> [Element]
stdlib/public/core/BidirectionalCollection.swift: func dropLast(_ k: Int) -> SubSequence

Похоже нужный нам метод находится здесь: stdlib/public/core/Collection.swift.

@inlinable
public __consuming func dropLast(_ k: Int = 1) -> SubSequence {
    _precondition(k >= 0, "Can't drop a negative number of elements")
    let amount = Swift.max(0, count - k)
    let end = index(startIndex, offsetBy: amount, limitedBy: endIndex) ?? endIndex
    return self[startIndex..<end]
}

С ходу не понятно, что делает этот метод таким медленным. Наша идея реализации на индексах очень похожа.

Разбираемся

Если присмотреться внимательнее и вспомнить о чем я уже упоминал в этом посте, то можно заметить обращение к свойству count. Если символы строк не фиксированного размера, то как посчитать count? Давайте взглянем на документацию.

/// To check whether a collection is empty, use its isEmpty property
/// instead of comparing count to zero. Unless the collection guarantees
/// random-access performance, calculating count can be an O(n)
/// operation.

Из описания становится ясно, что обращение к свойству count у коллекций без произвольного доступа равносильно проходу по всей коллекции. Это очень медленно. И нам это совсем не нужно.

Только представьте, чтобы удалить последний символ в огромном логе Xcode нам потребовалось бы просмотреть каждый символ лога? Безумие!

Поэтому имеет смысл реализация своего метода .dropLast(), когда мы выбрасываем только один символ. Тогда нам не нужно проверять длину строки с помощью count. И мы её уже написали.

Результат

• В этом посте мы реализовали простой метод для пропуска символа .skip();
• Разобрались как можно измерить его скорость работы с помощью measure();
• Немного почитали документацию, а не Stack Overflow (полезно иногда);
• Нашли исходный код стандартной библиотеки Swift и разобрались в нем (но это не точно);
• Написали свой легкий метод .dropLast() для пропуска только одного последнего символа;
• А самое главное, описали стратегию оптимизации методов.

На этом пока всё, я надеюсь пост был для вас интересным и полезным.
Подписывайтесь в Twitter и ещё увидимся.