title: Dynamic Time Warping in Swift
body: <p>I translated a DTW matlab function to Swift. The code looks as follows:</p>
  <pre><code>private func dtw(x1 : [Double], x2 : [Double]) -&gt; Double {
      let n1 = x1.count;
      let n2 = x2.count;
      var table =  [[Double]](repeating: [Double](repeating: 0, count: n2 + 1), count: 2);
      table[0][0] = 0;
      for i in 1...n2 { table[0][i] = Double.infinity }
      
      for i in 1 ... n1 {
          table[1][0] = Double.infinity;
          for j in 1 ... n2 {
              let cost = abs(x1[i - 1] - x2[j - 1]);
              var min = table[0][j - 1];
              if (min &gt; table[0][j]) {
                  min = table[0][j];
              }
              if (min &gt; table[1][j - 1]) { min = table[1][j - 1]; }
              
              table[1][j] = cost + min;
          }
          let swap = table[0];
          table[0] = table[1];
          table[1] = swap;
      }
      return table[0][n2];
  }
  </code></pre>
  <p>This function takes an average of 16 ms to complete on an iPhone 11. For my use case, this is very slow. I want to investigate ways to improve speed. I recently read these two articles : <a href="https://learning.oreilly.com/library/view/machine-learning-with/9781787121515/145416fd-5499-4377-9466-cf16b53093d8.xhtml" rel="nofollow noreferrer">DTW in Swift Orailly</a> and <a href="https://medium.com/flawless-app-stories/basics-of-parallel-programming-with-swift-93fee8425287" rel="nofollow noreferrer">Parallel programming with Swift</a>. In the first article, there is a good quote:</p>
  <blockquote>
  <p>Our implementation of DTW is naïve, and can be accelerated using parallel computing. To calculate the new row/column in a distance matrix, you don't need to wait until the previous one is finished; you only need it to be filled one cell ahead of your row/column</p>
  </blockquote>
  <p>This would make the for j in 1 ... n2 { for loop an ideal candidate. ( I think ) Looking at the code, only these two operations should be thread-safe due to the read / write:</p>
  <pre><code>table[1][j - 1]
  
  table[1][j]
  </code></pre>
  <p>The problem I am currently experiencing in introducing parallel computing ( from article 2 ) is that I cannot figure out how to tell swift run everything in parallel, except when I come to the two below lines, as they depend on their predocessor:</p>
  <pre><code>if (min &gt; table[1][j - 1]) { min = table[1][j - 1]; }
  table[1][j] = cost + min;
  </code></pre>
  <p>I suspect I could solve this issue with <a href="https://developer.apple.com/documentation/dispatch/dispatchqueue/2016088-concurrentperform" rel="nofollow noreferrer">DispatchQueue.concurrentPerform</a> and an NSLock(), if I implemented it correctly. ( I have not ) It could also be the wrong tool of choice, yielding me back to my question:</p>
  <p>What can I do, to improve the speed of my DTW function where the only constraint in performing a task is that the previous execution in an array had to have completed ( parallelization, concurrency, etc. ) A code example would go a long way.</p>