“loop unrolling” в Swift или как разогнать ваш код с помощью одного небольшого фокуса

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

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

Пишем собственный метод 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
    }

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

Посмотрите на различия:

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

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

Заключение

В заключение скажу пару слов об оптимизации:

Первое правило оптимизации гласит: “Лучше не стоит”.

Второе правило оптимизации гласит: “Скорее всего еще слишком рано этим заниматься”.

Пожалуйста, только не срывайтесь в судорожное “развертывание” всех ваших циклов после прочтения этой статьи. Моя цель здесь заключается в том, чтобы загрузить вас знаниями, чтобы вы могли стать лучшим программистом. Когда-нибудь вы можете столкнуться со сценариями с очень громоздкими циклами, которые требуют оптимизации, и развертывание циклов может быть вполне жизнеспособным решением. Но в вашей повседневной работе 99% циклов будут прекрасно работать без каких-либо дополнительных ухищрений.

Перевод статьи подготовлен в преддверии старта курса IOS Developer. Professional, также приглашаем вас на бесплатный вебинар, где подробно обсудим новый инструмент для работы с данными от Apple - представленный на WWDC 2023 фреймворк SwiftData.

• Зарегистрироваться на бесплатный вебинар