Почему Scala foldLeft имеет более низкую производительность, чем итерация с индексом для строк?

Question

Я сравниваю производительность двух реализаций atoi.Первый - это перебор входной строки с получением символов, используя charAt;вторая использует foldLeft.

object Atoi {
  def withRandomAccess(str: String, baze: Int): Int = {
      def process(acc: Int, place: Int, str: String, index: Int): Int = 
        if (index >= 0) process(acc + value(str.charAt(index)) * place, place * baze, str, index-1) else acc
      process(0, 1, str, str.length - 1)
    }

  def withFoldLeft(str: String, base: Int): Int = (0/:str) (_ * base + value(_))

  def value(c: Char): Int = { /* omitted for clarity */ }

  def symbol(i: Int): Char = { /* omitted for clarity */ }
}

. Версия foldLeft медленнее от 2х до 4х (полный эталонный код здесь ).Я этого не ожидал.Ты знаешь почему?Преобразует ли Scala строку в List перед ее обработкой?У вас есть подсказка о том, как повысить производительность foldLeft на строках?

Answer 1

Проблема не связана с встраиванием, она связана с боксом / распаковкой из Char с, который имеет место при использовании foldLeft.

Вы получаете foldLeft на String путем неявного преобразования в StringOps, которое не является специализированным.Каждый char в строке должен быть упакован в java.lang.Character, чтобы быть переданным в Function2 (аргумент foldLeft), затем распакован (намного дешевле) для передачи в метод value втело функции, , затем снова упакованное для подачи в следующую итерацию сгиба.

Бокс включает в себя накладные расходы на создание объектов и последующий сбор мусора.

С точки зрения избежания бокса, следует краткое и важное замечание:

• вам не следует пытаться избегать бокса с вероятностью почти 1.

(То есть, если вы не определили специфическое и недопустимое снижение производительности , которое может быть связано с боксом, вам не стоит об этом беспокоиться.)

Если вы уверены, что существует проблема, которую вам необходимо решить, избегайте коллекций и for -пониманий (которые используют foreach и flatMap под капотом).Если вы используете цикл, используйте while.