Programação funcional - a imutabilidade é cara? [fechadas]

A pergunta divide-se em duas partes. O primeiro é conceitual. O próximo analisa a mesma questão de forma mais concreta no Scala.

1. Usar apenas estruturas de dados imutáveis ​​em uma linguagem de programação torna a implementação de certos algoritmos / lógica inerentemente mais dispendiosa em termos computacionais na prática? Isso leva ao fato de que a imutabilidade é um princípio central das linguagens puramente funcionais. Existem outros fatores que impactam isso?
2. Vamos dar um exemplo mais concreto. O Quicksort é geralmente ensinado e implementado usando operações mutáveis ​​em uma estrutura de dados na memória. Como alguém implementa tal coisa de uma forma funcional PURE com uma sobrecarga computacional e de armazenamento comparável à versão mutável. Especificamente no Scala. Incluí alguns benchmarks grosseiros abaixo.

Mais detalhes:

Eu venho de uma experiência de programação imperativa (C ++, Java). Tenho explorado a programação funcional, especificamente Scala.

Alguns dos princípios básicos da programação funcional pura:

1. As funções são cidadãos de primeira classe.
2. As funções não têm efeitos colaterais e, portanto, os objetos / estruturas de dados são imutáveis .

Embora as JVMs modernas sejam extremamente eficientes com a criação de objetos e a coleta de lixo seja muito barata para objetos de curta duração, provavelmente ainda é melhor minimizar a criação de objetos, certo? Pelo menos em um aplicativo de thread único em que a simultaneidade e o bloqueio não são um problema. Uma vez que Scala é um paradigma híbrido, pode-se escolher escrever código imperativo com objetos mutáveis, se necessário. Mas, como alguém que passou muitos anos tentando reutilizar objetos e minimizar a alocação. Eu gostaria de um bom entendimento da escola de pensamento que nem isso permitiria.

Como um caso específico, fiquei um pouco surpreso com este snippet de código neste tutorial 6 . Ele tem uma versão Java do Quicksort seguida por uma implementação do mesmo em Scala.

Aqui está minha tentativa de comparar as implementações. Não fiz perfis detalhados. Mas, meu palpite é que a versão Scala é mais lenta porque o número de objetos alocados é linear (um por chamada de recursão). Existe alguma chance de que as otimizações de chamada final possam entrar em ação? Se eu estiver certo, o Scala oferece suporte para otimizações de chamadas autorrecursivas. Então, isso só deveria estar ajudando. Estou usando o Scala 2.8.

Versão Java

public class QuickSortJ {

    public static void sort(int[] xs) {
      sort(xs, 0, xs.length -1 );
    }

    static void sort(int[] xs, int l, int r) {
      if (r >= l) return;
      int pivot = xs[l];
      int a = l; int b = r;
      while (a <= b){
        while (xs[a] <= pivot) a++;
        while (xs[b] > pivot) b--;
        if (a < b) swap(xs, a, b);
      }
      sort(xs, l, b);
      sort(xs, a, r);
    }

    static void swap(int[] arr, int i, int j) {
      int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
    }
}

Versão Scala

object QuickSortS {

  def sort(xs: Array[Int]): Array[Int] =
    if (xs.length <= 1) xs
    else {
      val pivot = xs(xs.length / 2)
      Array.concat(
        sort(xs filter (pivot >)),
        xs filter (pivot ==),
        sort(xs filter (pivot <)))
    }
}

Código Scala para comparar implementações

import java.util.Date
import scala.testing.Benchmark

class BenchSort(sortfn: (Array[Int]) => Unit, name:String) extends Benchmark {

  val ints = new Array[Int](100000);

  override def prefix = name
  override def setUp = {
    val ran = new java.util.Random(5);
    for (i <- 0 to ints.length - 1)
      ints(i) = ran.nextInt();
  }
  override def run = sortfn(ints)
}

val benchImmut = new BenchSort( QuickSortS.sort , "Immutable/Functional/Scala" )
val benchMut   = new BenchSort( QuickSortJ.sort , "Mutable/Imperative/Java   " )

benchImmut.main( Array("5"))
benchMut.main( Array("5"))

Resultados

Tempo em milissegundos para cinco execuções consecutivas

Immutable/Functional/Scala    467    178    184    187    183
Mutable/Imperative/Java        51     14     12     12     12

Uma vez que existem alguns equívocos circulando por aqui, gostaria de esclarecer alguns pontos.

• O quicksort “no local” não está realmente no local (e o quicksort não está, por definição, no local). Ele requer armazenamento adicional na forma de espaço de pilha para a etapa recursiva, que está na ordem de O (log n ) no melhor caso, mas O ( n ) no pior caso.

• Implementar uma variante funcional do quicksort que opera em matrizes anula o propósito. As matrizes nunca são imutáveis.

• A implementação funcional “adequada” do quicksort usa listas imutáveis. É claro que não está no local, mas tem o mesmo tempo de execução assintótico de pior caso ( O ( n ^ 2)) e complexidade de espaço ( O ( n )) que a versão procedural local.

  Em média, seu tempo de execução ainda está em paridade com o da variante no local ( O ( n log n )). Sua complexidade espacial, entretanto, ainda é O ( n ).

Existem duas desvantagens óbvias de uma implementação de quicksort funcional. A seguir, vamos considerar esta implementação de referência em Haskell (não sei Scala ...) da introdução de Haskell :

qsort []     = []
qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater
    where lesser  = (filter (< x) xs)
          greater = (filter (>= x) xs)

1. A primeira desvantagem é a escolha do elemento pivô , que é muito inflexível. A força das implementações de quicksort modernas depende muito de uma escolha inteligente do pivô (compare “Engenharia de uma função de classificação” de Bentley et al. ). O algoritmo acima é pobre nesse aspecto, o que degrada o desempenho médio consideravelmente.

2. Em segundo lugar, este algoritmo usa concatenação de lista (em vez de construção de lista), que é uma operação O ( n ). Isso não afeta a complexidade assintótica, mas é um fator mensurável.

Uma terceira desvantagem está um tanto oculta: ao contrário da variante “in-loco”, esta implementação solicita continuamente memória do heap para as células contras da lista e potencialmente espalha a memória por todo o lugar. Como resultado, esse algoritmo tem uma localidade de cache muito pobre . Não sei se alocadores inteligentes em linguagens de programação funcionais modernas podem atenuar isso - mas em máquinas modernas, as perdas de cache se tornaram um grande assassino de desempenho.

Qual é a conclusão? Ao contrário de outros, eu não diria que o quicksort é inerentemente imperativo e é por isso que funciona mal em um ambiente de FP. Muito pelo contrário, eu diria que quicksort é um exemplo perfeito de um algoritmo funcional: ele se traduz perfeitamente em um ambiente imutável, seu tempo de execução assintótico e complexidade de espaço estão no mesmo nível da implementação procedural e até mesmo sua implementação procedural emprega recursão.

Mas esse algoritmo ainda tem um desempenho pior quando restrito a um domínio imutável. A razão para isso é que o algoritmo tem a propriedade peculiar de se beneficiar de muitos ajustes finos (às vezes de baixo nível) que só podem ser executados com eficiência em matrizes. Uma descrição ingênua do quicksort perde todas essas complexidades (tanto na variante funcional quanto na de procedimento).

Depois de ler “Engenharia de uma função de classificação”, não posso mais considerar o quicksort um algoritmo elegante. Implementado de forma eficiente, é uma bagunça desajeitada, obra de um engenheiro, não de um artista (para não desvalorizar a engenharia! Isso tem sua própria estética).

Mas também gostaria de salientar que esse ponto é específico do quicksort. Nem todo algoritmo é receptivo ao mesmo tipo de ajuste de baixo nível. Muitos algoritmos e estruturas de dados realmente podem ser expressos sem perda de desempenho em um ambiente imutável.

E a imutabilidade pode até diminuir os custos de desempenho, eliminando a necessidade de cópias caras ou sincronizações cross-thread.

Então, para responder à pergunta original, “a imutabilidade é cara? ”- No caso particular do quicksort, existe um custo que é mesmo resultado da imutabilidade. Mas, em geral, não .

Há um monte de coisas erradas com isso como uma referência de programação funcional. Os destaques incluem:

• Você está usando primitivos, que podem ter que ser encaixotados / desencaixotados. Você não está tentando testar a sobrecarga de envolver objetos primitivos, está tentando testar a imutabilidade.
• Você escolheu um algoritmo em que a operação no local é extraordinariamente eficaz (e comprovadamente eficaz). Se você deseja mostrar que existem algoritmos que são mais rápidos quando implementados de forma mutável, esta é uma boa escolha; caso contrário, é provável que isso seja enganoso.
• Você está usando a função de temporização errada. Use System.nanoTime.
• O benchmark é muito curto para que você tenha certeza de que a compilação JIT não será uma parte significativa do tempo medido.
• O array não é dividido de maneira eficiente.
• Arrays são mutáveis, então usá-los com FP é uma comparação estranha de qualquer maneira.

Portanto, essa comparação é uma ótima ilustração de que você deve entender sua linguagem (e algoritmo) em detalhes para escrever um código de alto desempenho. Mas não é uma comparação muito boa entre FP e não FP. Se você quiser isso, dê uma olhada em Haskell vs. C ++ no jogo de comparação de linguagens de computador . A mensagem para levar para casa é que a penalidade normalmente não é mais do que um fator de 2 ou 3 ou mais, mas realmente depende. (Não há promessas de que o pessoal de Haskell escreveu os algoritmos mais rápidos possíveis, mas pelo menos alguns deles provavelmente tentaram! Então, novamente, alguns dos Haskell chamam bibliotecas C ...)

Agora, suponha que você queira um benchmark mais razoável do Quicksort, reconhecendo que este é provavelmente um dos piores casos para algoritmos FP vs. mutáveis ​​e ignorando o problema de estrutura de dados (ou seja, fingir que podemos ter um Array imutável):

object QSortExample {
  // Imperative mutable quicksort
  def swap(xs: Array[String])(a: Int, b: Int) {
    val t = xs(a); xs(a) = xs(b); xs(b) = t
  }
  def muQSort(xs: Array[String])(l: Int = 0, r: Int = xs.length-1) {
    val pivot = xs((l+r)/2)
    var a = l
    var b = r
    while (a <= b) {
      while (xs(a) < pivot) a += 1
      while (xs(b) > pivot) b -= 1
      if (a <= b) {
        swap(xs)(a,b)
        a += 1
        b -= 1
      }
    }
    if (l<b) muQSort(xs)(l, b)
    if (b<r) muQSort(xs)(a, r)
  }

  // Functional quicksort
  def fpSort(xs: Array[String]): Array[String] = {
    if (xs.length <= 1) xs
    else {
      val pivot = xs(xs.length/2)
      val (small,big) = xs.partition(_ < pivot)
      if (small.length == 0) {
        val (bigger,same) = big.partition(_ > pivot)
        same ++ fpSort(bigger)
      }
      else fpSort(small) ++ fpSort(big)
    }
  }

  // Utility function to repeat something n times
  def repeat[A](n: Int, f: => A): A = {
    if (n <= 1) f else { f; repeat(n-1,f) }
  }

  // This runs the benchmark
  def bench(n: Int, xs: Array[String], silent: Boolean = false) {
    // Utility to report how long something took
    def ptime[A](f: => A) = {
      val t0 = System.nanoTime
      val ans = f
      if (!silent) printf("elapsed: %.3f sec\n",(System.nanoTime-t0)*1e-9)
      ans
    }

    if (!silent) print("Scala builtin ")
    ptime { repeat(n, {
      val ys = xs.clone
      ys.sorted
    }) }
    if (!silent) print("Mutable ")
    ptime { repeat(n, {
      val ys = xs.clone
      muQSort(ys)()
      ys
    }) }
    if (!silent) print("Immutable ")
    ptime { repeat(n, {
      fpSort(xs)
    }) }
  }

  def main(args: Array[String]) {
    val letters = (1 to 500000).map(_ => scala.util.Random.nextPrintableChar)
    val unsorted = letters.grouped(5).map(_.mkString).toList.toArray

    repeat(3,bench(1,unsorted,silent=true))  // Warmup
    repeat(3,bench(10,unsorted))     // Actual benchmark
  }
}

Observe a modificação no Quicksort funcional para que apenas passe pelos dados uma vez, se possível, e a comparação com a classificação integrada. Quando o executamos, obtemos algo como:

Scala builtin elapsed: 0.349 sec
Mutable elapsed: 0.445 sec
Immutable elapsed: 1.373 sec
Scala builtin elapsed: 0.343 sec
Mutable elapsed: 0.441 sec
Immutable elapsed: 1.374 sec
Scala builtin elapsed: 0.343 sec
Mutable elapsed: 0.442 sec
Immutable elapsed: 1.383 sec

Portanto, além de aprender que tentar escrever seu próprio tipo é uma má ideia, descobrimos que há uma penalidade de ~ 3x para um quicksort imutável se o último for implementado com algum cuidado. (Você também pode escrever um método trisect que retorna três arrays: aqueles menores que, iguais e maiores que o pivô. Isso pode acelerar as coisas um pouco mais.)

Não acho que a versão do Scala seja recursiva na cauda, ​​já que você está usando Array.concat.

Além disso, só porque esse é um código Scala idiomático, isso não significa que seja a melhor maneira de fazê-lo.

A melhor maneira de fazer isso seria usar uma das funções de classificação integradas do Scala. Dessa forma, você obtém a garantia de imutabilidade e sabe que tem um algoritmo rápido.

Consulte a pergunta sobre Stack Overflow Como faço para classificar uma matriz no Scala? Por exemplo.

A imutabilidade não é cara. Com certeza pode ser caro se você medir um pequeno subconjunto das tarefas que um programa deve fazer e escolher uma solução baseada na mutabilidade para inicializar - como medir a classificação rápida.

Para simplificar, você não faz uma classificação rápida ao usar linguagens puramente funcionais.

Vamos considerar isso de outro ângulo. Vamos considerar essas duas funções:

// Version using mutable data structures
def tailFrom[T : ClassManifest](arr: Array[T], p: T => Boolean): Array[T] = {
  def posIndex(i: Int): Int = {
    if (i < arr.length) {
      if (p(arr(i)))
        i
      else
        posIndex(i + 1)
    } else {
      -1
    }
  }

  var index = posIndex(0)

  if (index < 0) Array.empty
  else {
    var result = new Array[T](arr.length - index)
    Array.copy(arr, index, result, 0, arr.length - index)
    result
  }
}

// Immutable data structure:

def tailFrom[T](list: List[T], p: T => Boolean): List[T] = {
  def recurse(sublist: List[T]): List[T] = {
    if (sublist.isEmpty) sublist
    else if (p(sublist.head)) sublist
    else recurse(sublist.tail)
  }
  recurse(list)
}

Faça um teste de referência com ISSO, e você descobrirá que o código que usa estruturas de dados mutáveis ​​tem um desempenho muito pior, porque precisa copiar o array, enquanto o código imutável não precisa se preocupar com isso.

Ao programar com estruturas de dados imutáveis, você estrutura seu código para aproveitar suas vantagens. Não é simplesmente o tipo de dados, ou mesmo algoritmos individuais. O programa será desenhado de uma maneira diferente.

É por isso que o benchmarking geralmente não faz sentido. Ou você escolhe algoritmos que são naturais para um estilo ou outro, e esse estilo vence, ou você faz o benchmark de todo o aplicativo, o que geralmente é impraticável.

Classificar uma matriz é, tipo, a tarefa mais imperativa do universo. Não é surpreendente que muitas estratégias / implementações elegantes 'imutáveis' falhem mal em um microbenchmark 'classificar uma matriz'. Isso não significa que a imutabilidade seja cara "em geral", no entanto. Existem muitas tarefas em que as implementações imutáveis ​​serão executadas de forma comparável às mutáveis, mas a classificação do array geralmente não é uma delas.

Se você estiver simplesmente reescrevendo seus algoritmos imperativos e estruturas de dados em uma linguagem funcional, isso realmente será caro e inútil. Para fazer as coisas brilharem, você deve usar os recursos disponíveis apenas na programação funcional: persistência de estruturas de dados, avaliações preguiçosas etc.

O custo da imutabilidade em Scala

Esta é uma versão quase tão rápida quanto a do Java. ;)

object QuickSortS {
  def sort(xs: Array[Int]): Array[Int] = {
    val res = new Array[Int](xs.size)
    xs.copyToArray(res)
    (new QuickSortJ).sort(res)
    res
  }
}

Essa versão faz uma cópia do array, classifica-o no local usando a versão Java e retorna a cópia. Scala não força você a usar a estrutura imutável internamente.

Portanto, o benefício do Scala é que você pode alavancar a mutabilidade e a imutabilidade conforme achar necessário. A desvantagem é que, se você fizer isso errado, não obterá realmente os benefícios da imutabilidade.

O QuickSort é conhecido por ser mais rápido quando feito no local, portanto, essa não é uma comparação justa!

Dito isso ... Array.concat? Se nada mais, você está mostrando como um tipo de coleção otimizado para programação imperativa é particularmente lento quando você tenta usá-lo em um algoritmo funcional; quase qualquer outra escolha seria mais rápida!

Outro ponto muito importante a considerar, talvez o questão mais importante ao comparar as duas abordagens: "quão bem isso se expande para vários nós / núcleos?"

Provavelmente, se você está procurando um quicksort imutável, está fazendo isso porque na verdade deseja um quicksort paralelo. A Wikipedia possui algumas citações sobre este assunto: http://en.wikipedia.org/wiki/Quicksort#Parallelizations

A versão do scala pode simplesmente bifurcar antes que a função recorra, permitindo que ela classifique rapidamente uma lista contendo bilhões de entradas se você tiver núcleos suficientes disponíveis.

No momento, a GPU em meu sistema tem 128 núcleos disponíveis para mim se eu pudesse apenas executar o código Scala nela, e isso está em um sistema desktop simples dois anos atrás da geração atual.

Como isso se compara à abordagem imperativa de thread único, eu me pergunto ...

Talvez a questão mais importante seja, portanto:

"Dado que os núcleos individuais não ficarão mais rápidos e a sincronização / bloqueio representam um verdadeiro desafio para a paralelização, a mutabilidade é cara?"

Já foi dito que a programação OO usa abstração para ocultar a complexidade e a programação funcional usa imutabilidade para remover a complexidade. No mundo híbrido do Scala, podemos usar OO para ocultar o código imperativo, deixando o código do aplicativo sem saber o que fazer. Na verdade, as bibliotecas de coleções usam muito código imperativo, mas isso não significa que não devemos usá-las. Como outros já disseram, usado com cuidado, você realmente obtém o melhor dos dois mundos aqui.