program - Desempenho do Swift Beta: ordenar matrizes




swift syntax (6)

Eu estava implementando um algoritmo no Swift Beta e percebi que o desempenho era muito ruim. Depois de cavar mais fundo, percebi que um dos gargalos era algo tão simples quanto ordenar matrizes. A parte relevante está aqui:

let n = 1000000
var x =  [Int](repeating: 0, count: n)
for i in 0..<n {
    x[i] = random()
}
// start clock here
let y = sort(x)
// stop clock here

Em C ++, uma operação semelhante leva 0.06s no meu computador.

Em Python, são necessários 0,6s (sem truques, apenas y = classificado (x) para uma lista de números inteiros).

No Swift, é preciso 6s se eu compilar com o seguinte comando:

xcrun swift -O3 -sdk `xcrun --show-sdk-path --sdk macosx`

E é preciso até 88s se eu compilá-lo com o seguinte comando:

xcrun swift -O0 -sdk `xcrun --show-sdk-path --sdk macosx`

As temporizações no Xcode com versões "Release" e "Debug" são semelhantes.

O que está errado aqui? Eu poderia entender alguma perda de desempenho em comparação com o C ++, mas não uma desaceleração de 10 vezes em comparação com o Python puro.

Edit: mweathers notou que mudar -O3 para -Ofast faz este código rodar quase tão rápido quanto a versão C ++! No entanto, -Ofast altera muito a semântica da linguagem - em meus testes, ela desabilitou as verificações de estouros de inteiros e estouros de indexação de matrizes . Por exemplo, com -Ofast o seguinte código Swift é executado silenciosamente sem travar (e imprime algum lixo):

let n = 10000000
print(n*n*n*n*n)
let x =  [Int](repeating: 10, count: n)
print(x[n])

Então -Ofast não é o que queremos; O ponto principal do Swift é que temos as redes de segurança no lugar. É claro que as redes de segurança têm algum impacto no desempenho, mas não devem tornar os programas 100 vezes mais lentos. Lembre-se que Java já verifica limites de array, e em casos típicos a lentidão é por um fator muito menor que 2. E no Clang e no GCC temos -ftrapv para verificar overflow de inteiro (assinado), e não é tão lento, .

Daí a pergunta: como podemos obter um desempenho razoável no Swift sem perder as redes de segurança?

Edit 2: Eu fiz mais alguns benchmarking, com loops muito simples ao longo das linhas de

for i in 0..<n {
    x[i] = x[i] ^ 12345678
}

(Aqui a operação xor está lá apenas para que eu possa encontrar mais facilmente o loop relevante no código de montagem. Eu tentei escolher uma operação que seja fácil de detectar, mas também "inofensiva" no sentido de que não deveria exigir nenhuma verificação relacionada para transbordamentos de inteiros.

Novamente, houve uma enorme diferença no desempenho entre -O3 e -Ofast . Então eu dei uma olhada no código assembly:

  • Com -Ofast fico muito bem o que eu esperaria. A parte relevante é um loop com 5 instruções de linguagem de máquina.

  • Com -O3 eu recebo algo que estava além da minha imaginação mais selvagem. O laço interno abrange 88 linhas de código de montagem. Eu não tentei entender tudo isso, mas as partes mais suspeitas são 13 invocações de "callq _swift_retain" e outras 13 invocações de "callq _swift_release". Isto é, 26 chamadas de subrotina no circuito interno !

Edit 3: Nos comentários, Ferruccio pediu benchmarks que são justos no sentido de que eles não dependem de funções embutidas (eg sort). Eu acho que o seguinte programa é um bom exemplo:

let n = 10000
var x = [Int](repeating: 1, count: n)
for i in 0..<n {
    for j in 0..<n {
        x[i] = x[j]
    }
}

Não há aritmética, então não precisamos nos preocupar com transbordamentos de inteiros. A única coisa que fazemos é apenas muitas referências de matriz. E os resultados estão aqui - Swift -O3 perde por fator quase 500 em comparação com -Ofast:

  • C ++ -O3: 0,05 s
  • C ++ -O0: 0,4 s
  • Java: 0,2 s
  • Python com PyPy: 0,5 s
  • Python: 12 s
  • Swift -Ofast: 0,05 s
  • Swift -O3: 23 s
  • Swift -O0: 443 s

(Se você está preocupado que o compilador pode otimizar os loops sem sentido completamente, você pode mudá-lo para, por exemplo, x[i] ^= x[j] , e adicionar uma declaração de impressão que produz x[0] . Isso não muda nada os horários serão bem parecidos.)

E sim, aqui a implementação do Python era uma implementação Python pura e estúpida com uma lista de ints e loops aninhados. Deve ser muito mais lento que o Swift não otimizado. Algo parece estar seriamente quebrado com a indexação Swift e array.

Edit 4: Esses problemas (bem como alguns outros problemas de desempenho) parecem ter sido corrigidos no Xcode 6 beta 5.

Para classificação, agora tenho os seguintes horários:

  • clang ++ -O3: 0.06 s
  • swiftc -Ofast: 0,1 s
  • swiftc -O: 0,1 s
  • swiftc: 4 s

Para loops aninhados:

  • clang ++ -O3: 0.06 s
  • swiftc -Ofast: 0,3 s
  • swiftc -O: 0,4 s
  • swiftc: 540 s

Parece que não há mais razão para usar o inseguro -Ofast (aka -Ounchecked ); plain -O produz código igualmente bom.


A partir do Xcode 7, você pode ativar a Fast, Whole Module Optimization . Isso deve aumentar seu desempenho imediatamente.


A questão principal que é mencionada por outros, mas não é chamada o suficiente, é que -O3 não faz nada no Swift (e nunca o fez), então, quando compilado com ele, é efetivamente não otimizado ( -Onone ).

Os nomes das opções mudaram ao longo do tempo, por isso algumas outras respostas têm sinalizadores obsoletos para as opções de construção. Opções atuais corretas (Swift 2.2) são:

-Onone // Debug - slow
-O     // Optimised
-O -whole-module-optimization //Optimised across files

A otimização de todo o módulo tem uma compilação mais lenta, mas pode otimizar entre os arquivos dentro do módulo, ou seja, dentro de cada estrutura e dentro do código real do aplicativo, mas não entre eles. Você deve usar isso para qualquer desempenho crítico)

Você também pode desabilitar as verificações de segurança para obter ainda mais velocidade, mas com todas as afirmações e condições prévias não apenas desabilitadas, mas otimizadas com base no fato de estarem corretas. Se você alguma vez acertar uma afirmação, isso significa que você está em um comportamento indefinido. Use com extrema cautela e somente se você determinar que o aumento de velocidade vale a pena para você (por teste). Se você achar valioso para algum código, recomendo separar esse código em uma estrutura separada e apenas desabilitar as verificações de segurança para esse módulo.


Eu decidi dar uma olhada nisso por diversão, e aqui estão os horários que eu recebo:

Swift 4.0.2           :   0.83s (0.74s with `-Ounchecked`)
C++ (Apple LLVM 8.0.0):   0.74s

Rápido

// Swift 4.0 code
import Foundation

func doTest() -> Void {
    let arraySize = 10000000
    var randomNumbers = [UInt32]()

    for _ in 0..<arraySize {
        randomNumbers.append(arc4random_uniform(UInt32(arraySize)))
    }

    let start = Date()
    randomNumbers.sort()
    let end = Date()

    print(randomNumbers[0])
    print("Elapsed time: \(end.timeIntervalSince(start))")
}

doTest()

Resultados:

Swift 1.1

xcrun swiftc --version
Swift version 1.1 (swift-600.0.54.20)
Target: x86_64-apple-darwin14.0.0

xcrun swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 1.02204304933548

Swift 1.2

xcrun swiftc --version
Apple Swift version 1.2 (swiftlang-602.0.49.6 clang-602.0.49)
Target: x86_64-apple-darwin14.3.0

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 0.738763988018036

Swift 2.0

xcrun swiftc --version
Apple Swift version 2.0 (swiftlang-700.0.59 clang-700.0.72)
Target: x86_64-apple-darwin15.0.0

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 0.767306983470917

Parece ser o mesmo desempenho se eu compilar com -Ounchecked .

Swift 3.0

xcrun swiftc --version
Apple Swift version 3.0 (swiftlang-800.0.46.2 clang-800.0.38)
Target: x86_64-apple-macosx10.9

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 0.939633965492249

xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift
./SwiftSort     
Elapsed time: 0.866258025169373

Parece ter havido uma regressão de desempenho do Swift 2.0 para o Swift 3.0, e também estou vendo uma diferença entre -O e -Ounchecked pela primeira vez.

Swift 4.0

xcrun swiftc --version
Apple Swift version 4.0.2 (swiftlang-900.0.69.2 clang-900.0.38)
Target: x86_64-apple-macosx10.9

xcrun -sdk macosx swiftc -O SwiftSort.swift
./SwiftSort     
Elapsed time: 0.834299981594086

xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift
./SwiftSort     
Elapsed time: 0.742045998573303

O Swift 4 melhora o desempenho novamente, mantendo um espaço entre -O e -Ounchecked . -O -whole-module-optimization não pareceu fazer diferença.

C ++

#include <chrono>
#include <iostream>
#include <vector>
#include <cstdint>
#include <stdlib.h>

using namespace std;
using namespace std::chrono;

int main(int argc, const char * argv[]) {
    const auto arraySize = 10000000;
    vector<uint32_t> randomNumbers;

    for (int i = 0; i < arraySize; ++i) {
        randomNumbers.emplace_back(arc4random_uniform(arraySize));
    }

    const auto start = high_resolution_clock::now();
    sort(begin(randomNumbers), end(randomNumbers));
    const auto end = high_resolution_clock::now();

    cout << randomNumbers[0] << "\n";
    cout << "Elapsed time: " << duration_cast<duration<double>>(end - start).count() << "\n";

    return 0;
}

Resultados:

Apple Clang 6.0

clang++ --version
Apple LLVM version 6.0 (clang-600.0.54) (based on LLVM 3.5svn)
Target: x86_64-apple-darwin14.0.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.688969

Apple Clang 6.1.0

clang++ --version
Apple LLVM version 6.1.0 (clang-602.0.49) (based on LLVM 3.6.0svn)
Target: x86_64-apple-darwin14.3.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.670652

Apple Clang 7.0.0

clang++ --version
Apple LLVM version 7.0.0 (clang-700.0.72)
Target: x86_64-apple-darwin15.0.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.690152

Apple Clang 8.0.0

clang++ --version
Apple LLVM version 8.0.0 (clang-800.0.38)
Target: x86_64-apple-darwin15.6.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.68253

Apple Clang 9.0.0

clang++ --version
Apple LLVM version 9.0.0 (clang-900.0.38)
Target: x86_64-apple-darwin16.7.0
Thread model: posix

clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
./CppSort     
Elapsed time: 0.736784

Veredito

No momento em que este artigo foi escrito, o tipo de Swift é rápido, mas ainda não tão rápido quanto o tipo de C ++ quando compilado com -O , com os compiladores e bibliotecas acima. Com -Ounchecked , parece ser tão rápido quanto o C ++ no Swift 4.0.2 e no Apple LLVM 9.0.0.


O dr. Swift 1.0 é agora tão rápido quanto C por este benchmark usando o nível de otimização de liberação padrão [-O].

Aqui está um quicksort no local no Swift Beta:

func quicksort_swift(inout a:CInt[], start:Int, end:Int) {
    if (end - start < 2){
        return
    }
    var p = a[start + (end - start)/2]
    var l = start
    var r = end - 1
    while (l <= r){
        if (a[l] < p){
            l += 1
            continue
        }
        if (a[r] > p){
            r -= 1
            continue
        }
        var t = a[l]
        a[l] = a[r]
        a[r] = t
        l += 1
        r -= 1
    }
    quicksort_swift(&a, start, r + 1)
    quicksort_swift(&a, r + 1, end)
}

E o mesmo em C:

void quicksort_c(int *a, int n) {
    if (n < 2)
        return;
    int p = a[n / 2];
    int *l = a;
    int *r = a + n - 1;
    while (l <= r) {
        if (*l < p) {
            l++;
            continue;
        }
        if (*r > p) {
            r--;
            continue;
        }
        int t = *l;
        *l++ = *r;
        *r-- = t;
    }
    quicksort_c(a, r - a + 1);
    quicksort_c(l, a + n - l);
}

Ambos funcionam:

var a_swift:CInt[] = [0,5,2,8,1234,-1,2]
var a_c:CInt[] = [0,5,2,8,1234,-1,2]

quicksort_swift(&a_swift, 0, a_swift.count)
quicksort_c(&a_c, CInt(a_c.count))

// [-1, 0, 2, 2, 5, 8, 1234]
// [-1, 0, 2, 2, 5, 8, 1234]

Ambos são chamados no mesmo programa da escrita.

var x_swift = CInt[](count: n, repeatedValue: 0)
var x_c = CInt[](count: n, repeatedValue: 0)
for var i = 0; i < n; ++i {
    x_swift[i] = CInt(random())
    x_c[i] = CInt(random())
}

let swift_start:UInt64 = mach_absolute_time();
quicksort_swift(&x_swift, 0, x_swift.count)
let swift_stop:UInt64 = mach_absolute_time();

let c_start:UInt64 = mach_absolute_time();
quicksort_c(&x_c, CInt(x_c.count))
let c_stop:UInt64 = mach_absolute_time();

Isso converte os tempos absolutos em segundos:

static const uint64_t NANOS_PER_USEC = 1000ULL;
static const uint64_t NANOS_PER_MSEC = 1000ULL * NANOS_PER_USEC;
static const uint64_t NANOS_PER_SEC = 1000ULL * NANOS_PER_MSEC;

mach_timebase_info_data_t timebase_info;

uint64_t abs_to_nanos(uint64_t abs) {
    if ( timebase_info.denom == 0 ) {
        (void)mach_timebase_info(&timebase_info);
    }
    return abs * timebase_info.numer  / timebase_info.denom;
}

double abs_to_seconds(uint64_t abs) {
    return abs_to_nanos(abs) / (double)NANOS_PER_SEC;
}

Aqui está um resumo dos níveis de otimização do compilador:

[-Onone] no optimizations, the default for debug.
[-O]     perform optimizations, the default for release.
[-Ofast] perform optimizations and disable runtime overflow checks and runtime type checks.

Tempo em segundos com [-Onone] para n = 10_000 :

Swift:            0.895296452
C:                0.001223848

Aqui está a classificação interna do Swift () para n = 10_000 :

Swift_builtin:    0.77865783

Aqui está [-O] para n = 10_000 :

Swift:            0.045478346
C:                0.000784666
Swift_builtin:    0.032513488

Como você pode ver, o desempenho do Swift melhorou por um fator de 20.

Como resposta de mweathers , definindo [-Ofast] faz a diferença real, resultando nestes tempos para n = 10_000 :

Swift:            0.000706745
C:                0.000742374
Swift_builtin:    0.000603576

E para n = 1_000_000 :

Swift:            0.107111846
C:                0.114957179
Swift_sort:       0.092688548

Para comparação, isso é com [-Onone] para n = 1_000_000 :

Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272

Portanto, o Swift sem otimizações foi quase 1000x mais lento que o C nesse benchmark, neste estágio de desenvolvimento. Por outro lado, com os dois compiladores configurados para [-Ofast] Swift, na verdade, eram pelo menos tão bons, se não um pouco melhores que C.

Foi apontado que [-Ofast] altera a semântica da linguagem, tornando-a potencialmente insegura. Isto é o que a Apple afirma nas notas de lançamento do Xcode 5.0:

Um novo nível de otimização - OOf, disponível no LLVM, permite otimizações agressivas. -Ofast relaxa algumas restrições conservadoras, principalmente para operações de ponto flutuante, que são seguras para a maioria dos códigos. Ele pode gerar ganhos significativos de alto desempenho do compilador.

Todos eles, mas defendem isso. Se isso é sensato ou não, eu não poderia dizer, mas pelo que posso dizer, parece razoável o suficiente usar o [-Ofast] em uma versão se você não estiver fazendo aritmética de ponto flutuante de alta precisão e não estiver confiante em número inteiro ou transbordamentos de matriz são possíveis em seu programa. Se você precisar de verificações de alto desempenho e estouro / aritmética precisa, escolha outro idioma por enquanto.

ATUALIZAÇÃO DO BETA 3:

n = 10_000 com [-O] :

Swift:            0.019697268
C:                0.000718064
Swift_sort:       0.002094721

O Swift em geral é um pouco mais rápido e parece que o tipo integrado do Swift mudou significativamente.

ATUALIZAÇÃO FINAL:

[-Onone] :

Swift:   0.678056695
C:       0.000973914

[-O] :

Swift:   0.001158492
C:       0.001192406

[-Ounchecked] :

Swift:   0.000827764
C:       0.001078914

O Swift 4.1 introduz o novo modo de otimização de -Osize .

No Swift 4.1, o compilador agora suporta um novo modo de otimização que permite otimizações dedicadas para reduzir o tamanho do código.

O compilador Swift vem com otimizações poderosas. Ao compilar com -O o compilador tenta transformar o código para que ele seja executado com desempenho máximo. No entanto, essa melhoria no desempenho do tempo de execução pode, às vezes, vir com uma compensação do aumento do tamanho do código. Com o novo modo de otimização -Osize, o usuário tem a opção de compilar para um tamanho de código mínimo, em vez de para a velocidade máxima.

Para ativar o modo de otimização de tamanho na linha de comando, use -Osize em vez de -O.

Outras leituras: https://swift.org/blog/osize/


TL; DR : Sim, a única implementação da linguagem Swift está lenta, agora . Se você precisar de código rápido, numérico (e outros tipos de código, presumivelmente), use outro. No futuro, você deve reavaliar sua escolha. Pode ser bom o suficiente para a maioria dos códigos de aplicativos escritos em um nível mais alto, no entanto.

Pelo que estou vendo no SIL e LLVM IR, parece que eles precisam de um monte de otimizações para remover retenções e lançamentos, que podem ser implementados no Clang (para Objective-C), mas ainda não foram portados. Essa é a teoria com a qual estou indo (por enquanto… eu ainda preciso confirmar que o Clang faz algo a respeito), já que uma execução do profiler no último teste desta questão produz este resultado “bonito”:

Como foi dito por muitos outros, -Ofast é totalmente inseguro e muda a semântica da linguagem. Para mim, é no estágio “Se você for usar isso, apenas use outra língua”. Eu vou reavaliar essa escolha mais tarde, se mudar.

-O3 nos faz um monte de chamadas swift_release e swift_release que, honestamente, não parecem estar lá para este exemplo. O otimizador deve ter eliminado (a maioria) deles o AFAICT, já que ele conhece a maioria das informações sobre o array, e sabe que ele tem (pelo menos) uma forte referência a ele.

Ele não deve emitir mais retenções quando não estiver chamando funções que possam liberar os objetos. Eu não acho que um construtor de matriz pode retornar uma matriz que é menor do que o que foi solicitado, o que significa que muitas verificações que foram emitidas são inúteis. Ele também sabe que o inteiro nunca estará acima de 10k, então as verificações de overflow podem ser otimizadas (não por causa da estranheza -Ofast , mas por causa da semântica da linguagem (nada mais está mudando que var nem pode acessá-lo, e somando para 10k é seguro para o tipo Int ).

O compilador pode não ser capaz de desmarcar a matriz ou os elementos da matriz, já que eles estão sendo passados ​​para sort() , que é uma função externa e precisa obter os argumentos esperados. Isso nos fará ter que usar os valores Int indiretamente, o que tornaria um pouco mais lento. Isso poderia mudar se a função genérica sort() (não na forma multi-método) estivesse disponível para o compilador e fosse embutida.

Esta é uma linguagem muito nova (publicamente), e está passando por aquilo que eu suponho que são muitas mudanças, já que há pessoas (pesadamente) envolvidas com a linguagem Swift pedindo feedback e todas elas dizem que a linguagem não está terminada e mudança.

Código utilizado:

import Cocoa

let swift_start = NSDate.timeIntervalSinceReferenceDate();
let n: Int = 10000
let x = Int[](count: n, repeatedValue: 1)
for i in 0..n {
    for j in 0..n {
        let tmp: Int = x[j]
        x[i] = tmp
    }
}
let y: Int[] = sort(x)
let swift_stop = NSDate.timeIntervalSinceReferenceDate();

println("\(swift_stop - swift_start)s")

PS: Eu não sou um especialista em Objective-C, nem todas as instalações de Cocoa , Objective-C, ou os tempos de execução Swift. Eu também poderia estar assumindo algumas coisas que eu não escrevi.







compiler-optimization