Как повысить скорость работы цикла в Swift на 87%

Современные устройства обладают невероятной мощностью, что часто заставляет нас забывать о важности эффективности кода и его оптимизации. Легко подумать — зачем заботиться об эффективности, если у нас есть высокопроизводительные процессоры, такие как монструозные M2 в наших Mac или iPad? Однако такой образ мышления вреден. Время от времени необходимо совершенствовать основы, искать новые способы оптимизации кода. Это способно обогатить наши знания и повысить квалификацию как разработчиков, даже если не всегда может быть практичными.

Итак, давайте рассмотрим функцию, которую мы используем ежедневно: метод filter.

Написание собственного метода фильтрации

Фильтрация массивов — обычная задача, поэтому интересно попробовать ее оптимизировать.

Возьмем массив имен и попробуем отфильтровать конкретное имя:

    func filterName(name: String, fromArray collection: [String]) -> [String] {

        var result: [String] = []
        
        let indices = collection.indices
        var currentIndex = indices.lowerBound
        
        while currentIndex < indices.upperBound {
            let tempName = collection[currentIndex]
            if tempName == name {
                result.append(tempName)
            }
            currentIndex = indices.index(after: currentIndex)
        }
        
        return result
    }

Код для этой задачи достаточно прост. Мы выполняем итерации по массиву от нижней границы до верхней, обращаемся к каждому элементу и сравниваем с искомым. Наконец, мы возвращаем все отфильтрованные элементы.

Я провел тест на 500,000 элементах, и время выполнения составило 0,056 секунды. Неплохо! Теперь давайте рассмотрим некоторые возможные оптимизации для дальнейшего повышения производительности.

Использование forEach

Некоторые из вас, возможно, заметили, что предыдущая функция несколько громоздкая. В конце концов, зачем возиться с созданием нижних и верхних границ, если можно просто использовать метод forEach для массива? Давайте рассмотрим пример того же кода, но реализованного с помощью forEach:

    func filterName(name: String, fromArray collection: [String]) -> [String] {
        var result: [String] = []
        for tempName in collection {
            if tempName == name {
                result.append(tempName)
            }
        }
        return result
    }

Теперь, когда я выполняю этот код на тех же 500,000 элементах, результаты значительно быстрее: время выполнения составляет 0.031 секунды. Это поразительное улучшение на 42%!

Но почему так происходит? На самом деле, сама функция forEach все еще выполняет итерацию. Однако стоит отметить, что forEach — это встроенный метод, который может быть оптимизирован базовой средой выполнения или компилятором, что потенциально может привести к повышению производительности по сравнению с циклами, реализуемыми вручную.

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

Обработка двух элементов в каждой итерации

До сих пор мы обрабатывали по одному элементу, 500,000 раз. Однако что если попробовать другой подход и обработать два элемента вместе, но всего за 250,000 итераций? У меня есть подозрение, что обработка 500,000 итераций может быть сопряжена с издержками производительности. Давайте проверим это на практике и посмотрим на результаты:

public func filterNameHalfLoop(name: String, fromArray collection: [String]) -> [String] {
        var result: [String] = []
        let count = collection.count
        var index = 0
        
        while index < count {
            let tempName1 = collection[index]
            
            if index + 1 < count {
                let tempName2 = collection[index + 1]
                
                if tempName1 == name {
                    result.append(tempName1)
                }
                if tempName2 == name {
                    result.append(tempName2)
                }
            }
            
            index += 2
        }
        
        return result
    }

Вспомним, что при использовании цикла forEach время выполнения составляло 0.031 секунды. С помощью нового подхода мы добились впечатляющего прироста производительности, в результате чего время выполнения составило всего 0.007 секунды. Это на 71% больше, чем при использовании цикла forEach, и на 87% больше, чем в исходном коде!

Посмотрите на разницу:

Это удивительно, но почему так происходит?

Этот трюк называется «размоткой цикла» (loop unrolling). При этом мы выполняем несколько шагов за одну итерацию цикла, тем самым уменьшая общее количество итераций. Вы можете спросить: «Но это же та же самая логика, какого черта?». Оказывается, за большое количество итераций приходится платить. Во-первых, увеличивается общее количество инструкций, поскольку обработка цикла, проверка условия и переход к началу цикла требуют дополнительных инструкций. Кроме того, когда процессор «знает» больше о следующих инструкциях, которые ему необходимо выполнить, он может лучше оптимизировать свою работу.

Последние слова об оптимизациях

Первое правило оптимизаций — «Не делай».

Второе правило оптимизаций — «Пока не надо».

Пожалуйста, избегайте немедленной «размотки» ваших циклов в результате этой заметки. Цель этой статьи — дать вам знания, которые помогут вам стать лучшим программистом. Возможно, когда-нибудь вы столкнетесь со сценариями, требующими оптимизации тяжелых циклов, и такое изменение может оказаться приемлемым решением. В повседневной работе и так 99% циклов будут работать просто отлично.

Источник