message: Optimise join
  Summary: Previously we always allocated into an unknown-size buffer. Now we don't allocate for 0 or 1 size iterators, and for others we take a reasonable guess at the capacity to reduce allocation.
diff: @@ -29,6 +29,7 @@ use crate::{
  };
  use anyhow::anyhow;
  use gazebo::prelude::*;
  +use std::cmp;
  // This does not exists in rust, split would cut the string incorrectly and
  // split_whitespace cannot take a n parameter.
  @@ -607,27 +608,53 @@ pub(crate) fn string_methods(builder: &mut GlobalsBuilder) {
  ///
  /// ```
  /// # starlark::assert::all_true(r#"
  + /// ", ".join([]) == ""
  + /// ", ".join(("x", )) == "x"
  /// ", ".join(["one", "two", "three"]) == "one, two, three"
  /// "a".join("ctmrn".elems()) == "catamaran"
  /// # "#);
  /// ```
  - fn join(this: &str, ref to_join: Value) -> String {
  - let mut r = String::new();
  - let to_join_iter = to_join.iterate(heap)?;
  - for (index, item) in to_join_iter.enumerate() {
  - if index != 0 {
  - r.push_str(this);
  + fn join(this: &str, ref to_join: Value) -> Value<'v> {
  + #[inline(always)]
  + fn as_str<'v>(x: Value<'v>) -> anyhow::Result<&'v str> {
  + match x.unpack_str() {
  + None => Err(ValueError::IncorrectParameterTypeNamed("to_join".to_owned()).into()),
  + Some(v) => Ok(v),
  + }
  }
  - match item.unpack_str() {
  +
  + to_join.with_iterator(heap, |it| {
  + match it.next() {
  + None => Ok(Value::new_empty_string()),
  + Some(x1) => {
  + match it.next() {
  None => {
  - return Err(
  - ValueError::IncorrectParameterTypeNamed("to_join".to_owned()).into(),
  - );
  + as_str(x1)?;
  + // If there is a singleton we can avoid reallocation
  + Ok(x1)
  + }
  + Some(x2) => {
  + let s1 = as_str(x1)?;
  + let s2 = as_str(x2)?;
  + // guess towards the upper bound, since we throw away over-allocations quickly
  + // include a buffer (20 bytes)
  + let n = it.size_hint().0 + 2;
  + let guess =
  + (cmp::max(s1.len(), s2.len()) * n) + (this.len() * (n - 1)) + 20;
  + let mut r = String::with_capacity(guess);
  + r.push_str(s1);
  + r.push_str(this);
  + r.push_str(s2);
  + for x in it {
  + r.push_str(this);
  + r.push_str(as_str(x)?);
  + }
  + Ok(heap.alloc(r))
  + }
  }
  - Some(v) => r.push_str(v),
  }
  }
  - Ok(r)
  + })?
  }
  /// [string.lower](
  