performance - ¿Es Swift realmente lento en el manejo de los números?

primes

Question

Mientras jugaba con un rápido tutorial, comencé a escribir un método isPrime personalizado para verificar si un determinado Int es primo o no.

Después de escribirlo, me di cuenta de que funcionaba correctamente, pero me pareció un poco lento realizar isPrime en algunos números bastante grandes (aún mucho más bajo que Int.max ).

Así que escribí el mismo código en objc y el código se ejecutó mucho más rápido (un factor de 66x).

Aquí está el código rápido:

class Swift {
    class func isPrime(n:Int) -> Bool {
        let sqr : Int = Int(sqrt(Double(n))) + 1
        for i in 2...sqr {
            if n % i == 0 {
                return false
            }
        }
        return true;
    }
    class func primesInRange(start:Int, end:Int) -> Int[] {
        var primes:Int[] = Int[]()
        for n in start...end {
            if self.isPrime(n) {
                primes.append(n)
            }
        }
        return primes;
    }
}

Y el código objc:

@implementation Utils

+ (BOOL)isPrime:(NSUInteger)n {
    NSInteger sqr = (NSUInteger)(sqrt(n))+1;
    for (NSUInteger i = 2; i < sqr; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return YES;
}

+ (NSArray*)primesInRange:(NSUInteger)start end:(NSUInteger)end {
    NSMutableArray* primes = [NSMutableArray array];
    for (NSUInteger i = start; i <= end; ++i) {
        if ([self isPrime:i])
            [primes addObject:@(i)];
    }

    return primes.copy;
}

@end

Y en main.swift :

let startDateSwift = NSDate.date()
let swiftPrimes = Swift.primesInRange(1_040_101_022_000, end: 1_040_101_022_200)
let elapsedSwift = NSDate.date().timeIntervalSinceDate(startDateSwift)*1000

let startDateObjc = NSDate.date()
let objcPrimes = Utils.primesInRange(1_040_101_022_000, end: 1_040_101_022_200)
let elapsedObjc = NSDate.date().timeIntervalSinceDate(startDateObjc)*1000

println("/(swiftPrimes) took: /(elapsedSwift)ms");
println("/(objcPrimes) took: /(elapsedObjc)ms");

Esto produce:

[1040101022027, 1040101022039, 1040101022057, 1040101022099, 1040101022153] took: 3953.82004976273ms
[1040101022027, 1040101022039, 1040101022057, 1040101022099, 1040101022153] took: 66.4250254631042ms

Sé que podría haber usado una extension en Int aquí para verificar si un número es primo, pero quería que ambos códigos fueran muy similares.

¿Alguien puede decirme por qué este código rápido es mucho más lento? El factor 66x es bastante aterrador y solo empeora a medida que incremente el rango.

Answer 1

Créditos a @sjeohp por su comentario que es básicamente la respuesta a la pregunta.

Intenté optimizar el código de la forma más agresiva en Release para las optimizaciones de LLVM y Swift:

Compiló el proyecto en Release y obtuvo:

[1040101022027, 1040101022039, 1040101022057, 1040101022099, 1040101022153] took: 63.211977481842ms
[1040101022027, 1040101022039, 1040101022057, 1040101022099, 1040101022153] took: 60.0320100784302ms

Nuevamente, gracias @sjeohp por atrapar esto!

Answer 2

Estos son los niveles de optimización para la generación de código del compilador Swift (puede encontrarlos en Configuraciones de compilación):

[-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.

Usando su código obtuve estos tiempos en diferentes niveles de optimización:

[-En uno]

Swift: 6110.98903417587ms
Objc:  134.006023406982ms

[-O]

Swift: 89.8249745368958ms
Objc:  85.5680108070374ms

[-Ofast]

Swift: 77.1470069885254ms
Objc:  76.3399600982666ms

Tenga en cuenta que -Ofrece viene con riesgos. por ejemplo, ignorará silenciosamente los desbordamientos de enteros y matrices, produciendo resultados sin sentido, por lo que si elige usarlos deberá garantizarse que los desbordamientos no son posibles en su programa.