Vai al contenuto


STRIP

Array Speed Test Imparando Swift... E Risultati.

Recommended Posts

Buongiorno a tutti.

 

Sono un novellino con il linguaggio Swift e - per migliorare la mia conoscenza e per divertimento - ho scritto un'app su linea di comando per testare quant'è veloce la gestione degli array da parte di questo nuovo linguaggio inventato da Mamma-Apple.

 

Come test ho utilizzato una funzione dimostrativa, computazionalmente dispendiosa e non parallelizzabile (niente multithread o GCD).

QUI il diagramma di flusso.

 

La prima soluzione tentata - un banale metodo a forza bruta - ha fornito prestazioni veramente miserrime; ho quindi sviluppato un secondo metodo - un'ottimizzazione utilizzante un dizionario - e la velocità è migliorata parecchio.
Ma... confrontando i risultati ottenuti con quelli che normalmente ottengo su altre piattaforme (RHEL, Windows) e/o con altri linguaggi (C++, Objective-C), essi apparivano alquanto scarsi.

 

Ho così deciso di convertire alcuni algoritmi proprietari - da me sviluppati inizialmente in C++ e successivamente traslati in Objective-C - in Swift, ottenendo un impressionante incremento delle prestazioni: per fare un esempio, con un "target buffer" di 64 milioni di elementi il tempo di esecuzione era circa 1,000 volte inferiore a quello ottenuto con il metodo ottimizzato.

QUI il report con i risultati ed i grafici comparativi.

 

QUI - ed a seguire - il codice sorgente da me sviluppato con i due metodi (standard ed ottimizzato).

Può essere copiato/incollato direttamente nel file "main.swift" di un progetto di tipo "Command Line Tool" per macOS - in Xcode - e compilato con una configurazione standard di build.

I file con i sorgenti della classe (una specie di Extension degli Array Swift) utilizzata nel terzo metodo - con gli algoritmi proprietari - non è presente; sia perchè gli algoritmi sono - appunto - proprietari (e non divulgabili), sia perchè sono circa 27,000 linee di codice.

Nei sorgenti è inclusa anche una funzione (richiamabile dai parametri a riga di comando - vedere lo "Usage") per generare - e salvare su un file - i valori di test (che sono generati con numeri casuali ed è importante utilizzare gli stessi dati - tra un test e l'altro - al fine di avere una coerenza nei risultati relativi ai tempi di esecuzione).


//-------------------------------------------------------------------------

//

//  main.swift

//  Test

//

//  Created by STRIP on 19/09/2016.

//¬† Copyright √É‚Äö√ā¬© 2016 STRIP. All rights reserved.

//

//-------------------------------------------------------------------------

import Foundation

//-------------------------------------------------------------------------

func generateAndSaveItems (toItemsPath   anItemsPath    : String,

                          numberOfItems aNumberOfItems : Int    ) -> Void

{

  var itemsBuffer : ContiguousArray <Int> = ContiguousArray <Int> (repeating : 0             ,

                                                                   count     : aNumberOfItems )

  let itemsData   : Data                  = Data (bytesNoCopy : UnsafeMutableRawPointer (itemsBuffer.withUnsafeMutableBufferPointer { $0.baseAddress! }),

                                                  count       : (itemsBuffer.count         *

                                                                 MemoryLayout <Int>.stride  )                                                           ,

                                                  deallocator : Data.Deallocator.none                                                                    )

  for testIndex in 0 ..< aNumberOfItems

  {

    itemsBuffer [testIndex] = Int (arc4random ())

  }

  try? itemsData.write (to : URL (fileURLWithPath : anItemsPath))

}

//-------------------------------------------------------------------------

func loadItems (fromItemsPath anItemsPath      : String                     ,

                intoBuffer    aContiguousArray : inout ContiguousArray <Int> ) -> Void

{

  let itemsData : NSData? = try? NSData (contentsOf : URL (fileURLWithPath : anItemsPath),

                                         options    : NSData.ReadingOptions.uncached      )

  precondition (itemsData != nil)

  itemsData!.getBytes (         UnsafeMutableRawPointer (aContiguousArray.withUnsafeMutableBufferPointer { $0.baseAddress! }),

                       length : (aContiguousArray.count    *

                                 MemoryLayout <Int>.stride  )                                                                 )

}

//-------------------------------------------------------------------------

func STD_testFunction (sourceBuffer        aSourceBuffer        : inout ContiguousArray <Int>,

                       targetBuffer        aTargetBuffer        : inout Array <Int>          ,

                       numberOfTargetItems aNumberOfTargetItems : Int                        ,

                       numberOfTestItems   aNumberOfTestItems   : Int                        ,

                       maxTargetValues     aMaxTargetValues     : Int                         ) -> Void

{

  let nSourceItems : Int = (aNumberOfTargetItems +

                            aNumberOfTestItems    )

  for sourceIndex : Int in 0 ..< aNumberOfTargetItems

  {

    let targetValue : Int = (aSourceBuffer [sourceIndex] %

                             aMaxTargetValues             )

    aTargetBuffer.append (targetValue)

  }

  //------- Start test function sampling time

  let startDate : Date = Date ()

  for sourceIndex : Int in aNumberOfTargetItems ..< nSourceItems

  {

    let testValue                     : Int         = aSourceBuffer [sourceIndex]

    let searchValue                   : Int         = aTargetBuffer [testValue           %

                                                                     aTargetBuffer.count  ]

    var searchValueOccurrencesIndices : Array <Int> = Array <Int> ()

    for searchValueIndex : Int in 0 ..< aTargetBuffer.count

    {

      if (aTargetBuffer [searchValueIndex] == searchValue)

      {

        searchValueOccurrencesIndices.append (searchValueIndex)

      }

    }

    let targetValueIndex : Int = searchValueOccurrencesIndices [testValue                           %

                                                                searchValueOccurrencesIndices.count  ]

    if (aTargetBuffer.count < aNumberOfTargetItems)

    {

      let targetValue : Int = (testValue        %

                               aMaxTargetValues  )

      aTargetBuffer.insert (     targetValue     ,

                            at : targetValueIndex )

    }

    else

    {

      aTargetBuffer.remove (at : targetValueIndex)

    }

  }

  //------- End test function sampling time

  let endDate : Date = Date ()

  print ("-------------------------------------"                       + "\n" +

         "Test type........: STD (standard)"                           + "\n" +

         "Target items.....: \(aNumberOfTargetItems)"                  + "\n" +

         "Test items.......: \(aNumberOfTestItems)"                    + "\n" +

         "Max target values: \(aMaxTargetValues)"                      + "\n" +

         "-------------------------------------"                       + "\n" +

         "Test time........: \(endDate.timeIntervalSince (startDate))" + "\n" +

         "-------------------------------------"                       + "\n" +

                                                                         "\n"  )

}

//-------------------------------------------------------------------------

func OPT_testFunction (sourceBuffer        aSourceBuffer        : inout ContiguousArray <Int>,

                       targetBuffer        aTargetBuffer        : inout Array <Int>          ,

                       numberOfTargetItems aNumberOfTargetItems : Int                        ,

                       numberOfTestItems   aNumberOfTestItems   : Int                        ,

                       maxTargetValues     aMaxTargetValues     : Int                         ) -> Void

{

  let nSourceItems                      : Int                  = (aNumberOfTargetItems +

                                                                  aNumberOfTestItems    )

  var targetValuesOccurrencesDictionary : Dictionary <Int,Int> = Dictionary <Int,Int> ()

  for sourceIndex : Int in 0 ..< aNumberOfTargetItems

  {

    let targetValue : Int = (aSourceBuffer [sourceIndex] %

                             aMaxTargetValues             )

    if let targetValueOccurrences : Int = targetValuesOccurrencesDictionary [targetValue]

    {

      targetValuesOccurrencesDictionary [targetValue] = (targetValueOccurrences +

                                                         1                       )

    }

    else

    {

      targetValuesOccurrencesDictionary [targetValue] = 1

    }

    aTargetBuffer.append (targetValue)

  }

  //------- Start test function sampling time

  let startDate : Date = Date ()

  for sourceIndex : Int in aNumberOfTargetItems ..< nSourceItems

  {

    let testValue              : Int = aSourceBuffer [sourceIndex]

    let searchValue            : Int = aTargetBuffer [testValue           %

                                                      aTargetBuffer.count  ]

    var searchValueOccurrences : Int = (testValue                                        %

                                        targetValuesOccurrencesDictionary [searchValue]!  )

    var targetValueIndex       : Int = 0

    for searchValueIndex : Int in 0 ..< aTargetBuffer.count

    {

      if (aTargetBuffer [searchValueIndex] == searchValue)

      {

        if (searchValueOccurrences == 0)

        {

          targetValueIndex = searchValueIndex

          break

        }

        searchValueOccurrences -= 1

      }

    }

    if (aTargetBuffer.count < aNumberOfTargetItems)

    {

      let targetValue : Int = (testValue        %

                               aMaxTargetValues  )

      if let targetValueOccurrences : Int = targetValuesOccurrencesDictionary [targetValue]

      {

        targetValuesOccurrencesDictionary [targetValue] = (targetValueOccurrences +

                                                           1                       )

      }

      else

      {

        targetValuesOccurrencesDictionary [targetValue] = 1

      }

      aTargetBuffer.insert (     targetValue     ,

                            at : targetValueIndex )

    }

    else

    {

      let targetValue            : Int = aTargetBuffer [targetValueIndex]

      let targetValueOccurrences : Int = targetValuesOccurrencesDictionary [targetValue]!

      if (targetValueOccurrences > 1)

      {

        targetValuesOccurrencesDictionary [targetValue] = (targetValueOccurrences -

                                                           1                       )

      }

      else

      {

        targetValuesOccurrencesDictionary.removeValue (forKey : targetValue)

      }

      aTargetBuffer.remove (at : targetValueIndex)

    }

  }

  //------- End test function sampling time

  let endDate : Date = Date ()

  print ("-------------------------------------"                       + "\n" +

         "Test type........: OPT (optimized)"                          + "\n" +

         "Target items.....: \(aNumberOfTargetItems)"                  + "\n" +

         "Test items.......: \(aNumberOfTestItems)"                    + "\n" +

         "Max target values: \(aMaxTargetValues)"                      + "\n" +

         "-------------------------------------"                       + "\n" +

         "Test time........: \(endDate.timeIntervalSince (startDate))" + "\n" +

         "-------------------------------------"                       + "\n" +

                                                                         "\n"  )

}

//-------------------------------------------------------------------------

//func SW_testFunction (sourceBuffer        aSourceBuffer        : inout ContiguousArray <Int>,

//                      targetBuffer        aTargetBuffer        : inout SWArray <Int>        ,

//                      numberOfTargetItems aNumberOfTargetItems : Int                        ,

//                      numberOfTestItems   aNumberOfTestItems   : Int                        ,

//                      maxTargetValues     aMaxTargetValues     : Int                         ) -> Void

//{

//  let nSourceItems : Int = (aNumberOfTargetItems +

//                            aNumberOfTestItems    )

//  for sourceIndex : Int in 0 ..< aNumberOfTargetItems

//  {

//    let targetValue : Int = (aSourceBuffer [sourceIndex] %

//                             aMaxTargetValues             )

//    aTargetBuffer.append (targetValue)

//  }

//  //------- Start test function sampling time

//  let startDate : Date = Date ()

//  for sourceIndex : Int in aNumberOfTargetItems ..< nSourceItems

//  {

//    let testValue              : Int = aSourceBuffer [sourceIndex]

//    let searchValue            : Int = aTargetBuffer [testValue           %

//                                                      aTargetBuffer.count  ]

//    let searchValueOccurrences : Int = aTargetBuffer.occurrences (ofElement : searchValue)

//    let targetValueIndex       : Int = aTargetBuffer.index (ofElement         : searchValue               ,

//                                                            atOccurrenceIndex : (testValue              %

//                                                                                 searchValueOccurrences  ) )

//    if (aTargetBuffer.count < aNumberOfTargetItems)

//    {

//      let targetValue : Int = (testValue        %

//                               aMaxTargetValues  )

//      aTargetBuffer.insert (     targetValue     ,

//                            at : targetValueIndex )

//    }

//    else

//    {

//      aTargetBuffer.remove (at : targetValueIndex)

//    }

//  }

//  //------- End test function sampling time

//  let endDate : Date = Date ()

//  print ("-------------------------------------"                       + "\n" +

//         "Test type........: SW (proprietary algorithm)"               + "\n" +

//         "Target items.....: \(aNumberOfTargetItems)"                  + "\n" +

//         "Test items.......: \(aNumberOfTestItems)"                    + "\n" +

//         "Max target values: \(aMaxTargetValues)"                      + "\n" +

//         "-------------------------------------"                       + "\n" +

//         "Test time........: \(endDate.timeIntervalSince (startDate))" + "\n" +

//         "-------------------------------------"                       + "\n" +

//                                                                         "\n"  )

//}

//-------------------------------------------------------------------------

 

 

 

//-------------------------------------------------------------------------

// Usage: AppName 1st          2nd                    3rd                      4th

//        test    <items_path> <number_of_test_items>                                                   e.g. "test /Users/gnagna/Desktop/randoms.dta 134217728

//        test    <items_path> <STD | OPT | SW>       <number_of_target_items> <number_of_test_items>   e.g. "test /Users/gnagna/Desktop/randoms.dta       STD 1024 1024

//-------------------------------------------------------------------------

precondition ((CommandLine.argc == 3) ||

              (CommandLine.argc == 5)   )

if (CommandLine.argc == 3) // Generation of test values data file

{

  precondition (Int (CommandLine.arguments [2]) != nil)

  let itemsPath  : String = CommandLine.arguments [1]

  let nTestItems : Int    = Int (CommandLine.arguments [2])!

  generateAndSaveItems (toItemsPath   : itemsPath ,

                        numberOfItems : nTestItems )

}

else  // Execute test function (STD or OPT or SW)

{

  precondition (((CommandLine.arguments [2] == "STD") ||

                 (CommandLine.arguments [2] == "OPT") ||

                 (CommandLine.arguments [2] == "SW")    ) &&

                (Int (CommandLine.arguments [3])  != nil) &&

                (Int (CommandLine.arguments [3])! >= 0)   &&

                (Int (CommandLine.arguments [4])  != nil) &&

                (Int (CommandLine.arguments [4])! >= 0)     )

  let itemsPath       : String                = CommandLine.arguments [1]

  let testFunction    : String                = CommandLine.arguments [2]

  let nTargetItems    : Int                   = Int (CommandLine.arguments [3])!

  let nTestItems      : Int                   = Int (CommandLine.arguments [4])!

  let maxTargetValues : Int                   = Int (sqrt (Float (nTargetItems)))

  var sourceBuffer    : ContiguousArray <Int> = ContiguousArray <Int> (repeating : 0               ,

                                                                       count     : (nTargetItems +

                                                                                    nTestItems    ) )

  loadItems (fromItemsPath : itemsPath,

             intoBuffer    : &sourceBuffer)

  if (testFunction == "STD")

  {

    var targetBuffer : Array <Int> = Array <Int> ()

    STD_testFunction (sourceBuffer        : &sourceBuffer  ,

                      targetBuffer        : &targetBuffer  ,

                      numberOfTargetItems : nTargetItems   ,

                      numberOfTestItems   : nTestItems     ,

                      maxTargetValues     : maxTargetValues )

  }

  if (testFunction == "OPT")

  {

    var targetBuffer : Array <Int> = Array <Int> ()

    OPT_testFunction (sourceBuffer        : &sourceBuffer  ,

                      targetBuffer        : &targetBuffer  ,

                      numberOfTargetItems : nTargetItems   ,

                      numberOfTestItems   : nTestItems     ,

                      maxTargetValues     : maxTargetValues )

  }

  if (testFunction == "SW")

  {

//    var targetBuffer : SWArray <Int> = SWArray <Int> ()

//    SW_testFunction (sourceBuffer        : &sourceBuffer  ,

//                     targetBuffer        : &targetBuffer  ,

//                     numberOfTargetItems : nTargetItems   ,

//                     numberOfTestItems   : nTestItems     ,

//                     maxTargetValues     : maxTargetValues )

  }

}

//-------------------------------------------------------------------------

 

Se qualcuno vuole cimentarsi nell'impresa - a scopo puramente didattico - e proporre soluzioni alternative (od altri test)...

Un saluto,

STRIP (Selettore Tipo Risposta Ideale Programmata)

Modificato da STRIP

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti


Crea un account o accedi per lasciare un commento

You need to be a member in order to leave a comment

Crea un account

Iscriviti alla nostra comunit√†. √ą facile!

Crea un nuovo account

Accedi

Sei già iscritto? Accedi qui.

Accedi Ora

  • Statistiche forum

    528864
    Discussioni Totali
    6332091
    Risposte Totali
  • Statistiche Utenti

    122005
    Utenti totali
    14120
    Record utenti online
    Luca Musumeci
    Nuovo iscritto
    Luca Musumeci
    Iscritto
  • Statistiche annunci

    105
    Annunci attivi
    17
    Domande
    0
    Recensioni
    0
    Offerte
    Ultimi Annunci
    By Francesco F
    mese e 1 giorno
√ó