title: Iterator-based code vs procedural code: how to make the iterator-based algorithm faster?
body: <p>I can see a huge difference in terms of performance, between an iterator-based algorithm (slow) and a procedural algorithm (fast). I want to improve the speed of the iterator-based algorithm but I don't know how to do it.</p>
  <h3>Context</h3>
  <p>I need to convert strings like <code>12345678</code> to <code>12_345_678</code>. Questions like this have already been asked like <a href="https://stackoverflow.com/questions/26998485/is-it-possible-to-print-a-number-formatted-with-thousand-separator-in-rust">in this question</a>. (Note: I don't want to use a crate for this, because I have some custom needs about it).</p>
  <p><em>Edit</em>: it is assumed that the input string is ASCII.</p>
  <p>I wrote two versions of the algorithm:</p>
  <ul>
  <li>an iterator-based version, but I'm not satisfied because there is two <code>.collect()</code>, which means many allocations (at least one <code>.collect()</code> is extra, without being able to remove it, see the code below);</li>
  <li>a procedural version of it.</li>
  </ul>
  <p>Then I compared the execution time of the two versions: my iterator version is about <em>~8x slower</em> compared to the procedural version.</p>
  <h3>Benchmark code</h3>
  <pre><code>use itertools::Itertools; // Using itertools v0.10.0
  
  /// Size of the string blocks to separate:
  const BLOCK_SIZE: usize = 3;
  
  /// Procedural version.
  fn procedural(input: &amp;str) -&gt; String {
      let len = input.len();
      let nb_complete_blocks = (len as isize - 1).max(0) as usize / BLOCK_SIZE;
      let first_block_len = len - nb_complete_blocks * BLOCK_SIZE;
  
      let capacity = first_block_len + nb_complete_blocks * (BLOCK_SIZE + 1);
      let mut output = String::with_capacity(capacity);
  
      output.push_str(&amp;input[..first_block_len]);
  
      for i in 0..nb_complete_blocks {
          output.push('_');
          let start = first_block_len + i * BLOCK_SIZE;
          output.push_str(&amp;input[start..start + BLOCK_SIZE]);
      }
  
      output
  }
  
  /// Iterator version.
  fn with_iterators(input: &amp;str) -&gt; String {
      input.chars()
          .rev()
          .chunks(BLOCK_SIZE)
          .into_iter()
          .map(|c| c.collect::&lt;String&gt;())
          .join(&quot;_&quot;)
          .chars()
          .rev()
          .collect::&lt;String&gt;()
  }
  
  fn main() {
      let input = &quot;12345678&quot;;
  
      macro_rules! bench {
          ( $version:ident ) =&gt; {{
              let now = std::time::Instant::now();
              for _ in 0..1_000_000 {
                  $version(input);
              }
              println!(&quot;{:.2?}&quot;, now.elapsed());
          }};
      }
  
      print!(&quot;Procedural benchmark: &quot;);
      bench!(procedural);
  
      print!(&quot;Iterator benchmark: &quot;);
      bench!(with_iterators);
  }
  </code></pre>
  <h3>Typical benchmark result</h3>
  <pre class="lang-none prettyprint-override"><code>Procedural benchmark: 17.07ms
  Iterator benchmark: 240.19ms
  </code></pre>
  <h3>Question</h3>
  <p>How can I improve the iterator-based version, in order to reach the performance of the procedural version ?</p>