Быстрая производительность: map() и reduce() vs для циклов

Ответ 1

Не следует, чтобы встроенные методы Array были быстрее, чем наивный подход для выполнения таких операций? Может быть, кто-то с более низким уровнем знаний, чем я могу пролить свет на ситуацию.

Я просто хочу попытаться решить эту часть вопроса и многое другое с концептуального уровня (с небольшим пониманием природы оптимизатора Swift с моей стороны) с "необязательно". Это происходит скорее из-за фона в дизайне компилятора и компьютерной архитектуры, чем глубокое знание природы оптимизатора Swift.

Навыки вызова

С такими функциями, как map и reduce, принимающими функции в качестве входных данных, это создает большую нагрузку на оптимизатор, чтобы поместить его в одну сторону. Естественный соблазн в таком случае, за исключением некоторой очень агрессивной оптимизации, состоит в том, чтобы постоянно отворачиваться назад и вперед между реализацией, скажем, map и предоставленным вами закрытием, а также передавать данные через эти разрозненные ветки кода (через регистры и стек, как правило).

Подобные ветвящиеся/вызывающие накладные расходы для оптимизатора очень сложно устранить, особенно учитывая гибкость закрытия Swift (не невозможно, а концептуально довольно сложно). Оптимизаторы С++ могут встраивать вызовы функциональных объектов, но с гораздо большими ограничениями и методами генерации кода, необходимыми для этого, когда компилятору будет эффективно генерировать целый новый набор инструкций для map для каждого типа объекта функции, который вы проходите (и с явная помощь программиста, указывающая шаблон функции, используемый для генерации кода).

Таким образом, не должно быть большого удивления обнаружить, что ваши ручные петли могут работать быстрее - они прикладывают гораздо меньше усилий к оптимизатору. Я видел, как некоторые люди ссылаются на то, что эти функции более высокого порядка должны быть быстрее, поскольку поставщик может делать такие вещи, как параллелизация цикла, но для эффективного распараллеливания цикла сначала требуется тип информации, которая обычно позволяют оптимизатору встроить вложенные вызовы функций внутри точки, где они становятся такими же дешевыми, как ручные свертки. В противном случае реализация функции/закрытия, которую вы проходите, будет эффективно непрозрачной для таких функций, как map/reduce: они могут только называть ее и оплачивать накладные расходы, делая это, и не могут ее распараллелить, поскольку они ничего не могут предположить о характере стороны эффекты и безопасность потоков при этом.

Конечно, все это концептуально - Swift может оптимизировать эти случаи в будущем или, возможно, уже сможет это сделать сейчас (см. -Ofast как часто цитируемый способ сделать Swift быстрее стоимость некоторой безопасности). Но он, по крайней мере, ставит более тяжелую нагрузку на оптимизатор, чтобы использовать эти функции над ручными циклами, а различия во времени, которые вы видите в первом тесте, похоже, отражают различия, которые могут быть ожидайте с дополнительными дополнительными накладными вызовами. Лучший способ узнать - посмотреть на сборку и попробовать различные флаги оптимизации.

Стандартные функции

Это не должно препятствовать использованию таких функций. Они более четко выражают намерение, они могут повысить производительность. И полагаясь на них, вы можете позволить своей кодовой базе быстрее развиваться в будущих версиях Swift без какого-либо участия с вашей стороны. Но они не всегда всегда будут быстрыми. Хорошим общим правилом считается, что функция библиотеки более высокого уровня, которая более прямо выражает то, что вы хотите сделать, будет быстрее, но всегда есть исключения из (но лучше всего обнаружить в ретроспективе с профилировщиком в руке, так как гораздо лучше ошибиться на стороне доверия, чем недоверие здесь).

Искусственные бенчмарки

Что касается второго эталона, это почти наверняка результат компилятора, который оптимизирует код, который не имеет побочных эффектов, влияющих на пользовательский вывод. Искусственные тесты имеют тенденцию заведомо вводить в заблуждение в результате того, что оптимизаторы делают для устранения нерелевантных побочных эффектов (побочные эффекты, которые не влияют на выход пользователя, по существу). Поэтому вы должны быть осторожны при построении тестов со временем, которые кажутся слишком хорошими, чтобы быть правдой, что они не являются результатом того, что оптимизатор просто пропускает всю работу, которую вы на самом деле хотели сравнить. По крайней мере, вы хотите, чтобы ваши тесты выдавали какой-то окончательный результат, полученный из вычисления.

Ответ 2

Я не могу сказать много о вашем первом тесте (map() vs append() в цикле) но я могу подтвердить ваши результаты. Цикл append становится еще быстрее, если вы добавляете

output.reserveCapacity(array.count)

после создания массива. Кажется, Apple может улучшить ситуацию здесь и вы можете записать отчет об ошибке.

В

for _ in 0..<100_000 {
    var sum: Float = 0
    for element in array {
        sum += element
    }
}

компилятор (возможно) удаляет весь цикл потому что вычисленные результаты не используются вообще. Я могу только предположить, почему подобная оптимизация не выполняется в

for _ in 0..<100_000 {
    let sum = array.reduce(0, combine: {$0 + $1})
}

но было бы сложнее решить, вызывает ли вызов reduce() с закрытием какие-либо побочные эффекты или нет.

Если тестовый код слегка изменен для вычисления и печати общей суммы

do {
    var total = Float(0.0)
    let start = NSDate()
    for _ in 0..<100_000 {
        total += array.reduce(0, combine: {$0 + $1})
    }
    let elapsed = NSDate().timeIntervalSinceDate(start)
    print("sum with reduce:", elapsed)
    print(total)
}

do {
    var total = Float(0.0)
    let start = NSDate()
    for _ in 0..<100_000 {
        var sum = Float(0.0)
        for element in array {
            sum += element
        }
        total += sum
    }
    let elapsed = NSDate().timeIntervalSinceDate(start)
    print("sum with loop:", elapsed)
    print(total)
}

тогда оба варианта занимают около 10 секунд в моем тесте.