기능 프로그래밍 - 불변성은 비용이 많이 드나요?
문제는 두 부분으로 나눠져 있다.첫 번째는 개념적인 것입니다.다음은 스칼라에서 같은 질문을 좀 더 구체적으로 살펴본다.
- 프로그래밍 언어로 불변의 데이터 구조만을 사용하면 특정 알고리즘/로직 구현에 본질적으로 더 많은 계산 비용이 발생합니까?이는 불변성이 순전히 기능적인 언어의 핵심 원칙이라는 사실에 끌린다.여기에 영향을 미치는 다른 요인이 있습니까?
- 좀 더 구체적인 예를 들어보자.QuickSort는 일반적으로 메모리 내 데이터 구조에서 가변 연산을 사용하여 학습 및 구현됩니다.이러한 기능을 PURE 기능적 방법으로 구현하려면 어떻게 해야 하며, 컴퓨팅 및 스토리지 오버헤드는 가변 버전과 동등합니다.특히 스칼라에서요아래에 몇 가지 대략적인 벤치마크를 포함시켰습니다.
상세:
저는 필수 프로그래밍 배경(C++, Java) 출신입니다.함수 프로그래밍, 특히 스칼라를 탐구해 왔습니다.
순수 기능 프로그래밍의 주요 원칙은 다음과 같습니다.
- 기능들은 일등석 시민들이다.
- 함수는 부작용이 없으므로 객체/데이터 구조는 불변합니다.
최신 JVM은 객체 생성에 매우 효율적이며 가비지 수집은 수명이 짧은 객체의 경우 매우 저렴하지만 그래도 객체 생성을 최소화하는 것이 더 나을 수 있습니다.적어도 동시성과 잠금이 문제가 되지 않는 싱글 스레드 어플리케이션에서는.Scala는 하이브리드 패러다임이기 때문에 필요에 따라 가변 객체로 명령 코드를 작성할 수 있습니다.하지만 오랫동안 오브젝트를 재사용하고 할당을 최소화하려고 노력해 온 사람으로서.그것조차 허락하지 않는 사상을 잘 이해하고 싶다.
구체적으로는, 이 튜토리얼 6의 코드 스니펫에 조금 놀랐습니다.QuickSort의 Java 버전에 이어서 Scala의 깔끔한 실장이 되어 있습니다.
여기 구현을 벤치마킹하기 위한 저의 시도가 있습니다.자세한 프로파일링은 하지 않았습니다.그러나 할당된 개체 수가 선형(재귀 호출당 1개)이기 때문에 Scala 버전이 더 느릴 수 있습니다.테일콜 최적화가 실행될 가능성이 있습니까?내 말이 맞다면 Scala는 자기재귀 콜의 테일콜 최적화를 지원합니다.그러니 도움이 될 수 밖에 없어요Scala 2.8을 사용하고 있습니다.
자바 버전
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;
}
}
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 <)))
}
}
구현을 비교하는 스칼라 코드
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"))
결과.
5회 연속 실행 시간(밀리초)
Immutable/Functional/Scala 467 178 184 187 183
Mutable/Imperative/Java 51 14 12 12 12
이 근처에는 몇 가지 오해가 떠돌고 있기 때문에, 몇 가지 요점을 명확히 하고 싶습니다.
"in-place" 퀵소트는 실제로 인플레이스가 아닙니다(또한 퀵소트는 정의상 인플레이스가 아닙니다.재귀 스텝을 위해 스택스페이스 형식의 추가 스토리지가 필요합니다.최적의 경우 O(log n), 최악의 경우 O(n)의 순서로 되어 있습니다.
어레이로 동작하는 기능상의 바리안트 QuickSort를 실장하는 것은 목적에 어긋납니다.어레이는 절대 불변하지 않습니다.
QuickSort의 "적절한" 기능 구현에서는 불변의 목록을 사용합니다.물론 인플레이스는 아니지만 절차 인플레이스 버전과 마찬가지로 최악의 경우 점근 런타임(O(n^2) 및 공간 복잡도(O(n))가 있습니다.
평균적으로 실행 시간은 아직 임플레이스 바리안트(O(n log n))의 실행 시간과 동등합니다.그러나 공간의 복잡성은 여전히 O(n)입니다.
기능적인 QuickSort 구현에는 두 가지 명백한 단점이 있습니다.다음에서는 Haskell의 도입부터 Haskell(Scala는 모릅니다)에서의 이 레퍼런스 실장에 대해 설명하겠습니다.
qsort [] = []
qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater
where lesser = (filter (< x) xs)
greater = (filter (>= x) xs)
첫 번째 단점은 매우 유연하지 않은 피벗 요소를 선택하는 것입니다.최신 QuickSort 구현의 강점은 현명한 피벗 선택에 크게 의존하고 있습니다(Bentley 등의 "Engineering a sort 함수" 비교).이 점에서 위의 알고리즘은 빈약하여 평균 성능을 크게 저하시킵니다.
둘째, 이 알고리즘은 O(n) 연산인 목록 구성 대신 목록 연결을 사용합니다.이것은 점근 복잡성에는 영향을 주지 않지만 측정 가능한 요인입니다.
세 번째 단점은 다소 숨겨져 있습니다.인플레이스(in-place) 변종과 달리 이 구현은 목록의 콘스 셀을 위해 힙에서 지속적으로 메모리를 요구하며 잠재적으로 메모리를 분산시킵니다.그 결과 이 알고리즘은 캐시 인접성이 매우 낮습니다.최신 기능 프로그래밍 언어의 스마트 할당기가 이를 완화할 수 있을지는 모르겠지만, 최신 기계에서는 캐시 누락이 주요 성능 저하 요인이 되고 있습니다.
결론은?다른 것과 달리 퀵소트는 본질적으로 필수적이며, 그렇기 때문에 FP 환경에서는 성능이 저하된다고는 말할 수 없습니다.반대로, QuickSort는 기능 알고리즘의 완벽한 예라고 생각합니다.즉, 퀵소트는 불변의 환경으로 심리스하게 변환되며, 점근적인 실행 시간과 공간의 복잡성은 절차적 구현과 동등하며, 절차적 구현에서도 재귀가 사용됩니다.
그러나 이 알고리즘은 불변의 도메인으로 제한되어도 성능이 저하됩니다.그 이유는 알고리즘이 어레이에서만 효율적으로 수행할 수 있는 많은(때로는 낮은 수준의) 미세 조정에서 이점을 얻는 고유한 특성이 있기 때문입니다.QuickSort에 대한 간단한 설명에는 이러한 복잡함이 모두 누락되어 있습니다(기능적 및 절차적 변형 모두).
"Engineering a sort function"을 읽고 나니 더 이상 Quicksort를 우아한 알고리즘으로 간주할 수 없습니다.효율적으로 구현되면, 그것은 예술가가 아닌, 투박한 엉망진창이며, 엔지니어의 작품입니다(공학을 평가절하하는 것은 아닙니다! 이것은 그 자체의 미학을 가지고 있습니다).
그러나 이 점은 퀵소트에 특유하다는 점도 지적하고 싶습니다.모든 알고리즘이 동일한 종류의 낮은 수준의 조정을 수용할 수 있는 것은 아닙니다.많은 알고리즘과 데이터 구조를 불변의 환경에서 성능 저하 없이 표현할 수 있습니다.
또한 불변성은 비용이 많이 드는 복사본이나 크로스 스레드 동기화가 필요하지 않으므로 성능 비용도 절감할 수 있습니다.
즉, "불변성은 비용이 많이 드는가?"라는 질문에 답할 수 있습니다.- QuickSort의 경우 불변성에 따른 비용이 발생합니다.하지만 일반적으로, 아니다.
기능적 프로그래밍의 기준으로서 이것에는 많은 잘못된 점이 있습니다.주요 내용은 다음과 같습니다.
- 기본 요소를 사용하고 있으며, 이 경우 상자에 넣거나 상자를 해제해야 할 수 있습니다.원시 물체를 감싸는 데 드는 오버헤드를 테스트하려는 것이 아니라 불변성을 테스트하려는 것입니다.
- 사내 작업이 비정상적으로 효과적인 알고리즘을 선택했습니다(가능한 경우).변경 가능하게 실장했을 때에 보다 고속의 알고리즘이 존재하는 것을 나타내는 경우는, 이것이 적절한 선택입니다.그렇지 않으면 오해를 일으킬 가능성이 있습니다.
- 잘못된 타이밍 기능을 사용하고 있습니다.
System.nanoTime. - 벤치마크가 너무 짧아서 JIT 컴파일이 측정 시간의 중요한 부분을 차지하지 못할 것이라고 확신할 수 없습니다.
- 어레이가 효율적으로 분할되어 있지 않다.
- 어레이는 가변성이 있기 때문에 FP와 함께 사용하는 것은 이상한 비교입니다.
따라서 이 비교는 고성능 코드를 작성하기 위해 언어(및 알고리즘)를 자세히 이해해야 하는 훌륭한 예입니다.그러나 FP와 비FP의 비교는 그다지 좋지 않습니다.그걸 원한다면 해스켈 대 해스켈 대 해스켈 대 해스켈을 봐 컴퓨터 언어 벤치마크 게임에서 C++를 획득했습니다.여기서 알 수 있는 메시지는 벌칙이 보통 2 또는 3배 이하라는 것입니다만, 실제로는 의존합니다.(Haskell 사람들이 가능한 한 빠른 알고리즘을 개발했다는 약속도 없지만, 적어도 그들 중 일부는 시도했을 것이다!한편, 일부 Haskell은 C 라이브러리를 호출합니다.
이제 Quicksort의 보다 합리적인 벤치마크를 원하는 경우를 가정해 보겠습니다.이는 FP와 가변 알고리즘의 최악의 경우 중 하나일 가능성이 높으며 데이터 구조 문제를 무시합니다(즉, 어레이를 불변으로 할 수 있다고 가정합니다).
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
}
}
가능하면 데이터를 한 번만 통과하도록 QuickSort 기능을 수정하고 삽입 정렬과 비교합니다.실행 시 다음과 같은 결과를 얻을 수 있습니다.
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
따라서 사용자 고유의 정렬을 작성하는 것은 좋지 않은 생각이라는 것을 깨닫는 것 외에, 퀵소트를 약간 신중하게 구현하면 불변의 퀵소트에 대해 약 3배의 패널티가 발생한다는 것을 알 수 있습니다.(또한 3개의 어레이를 반환하는 3개의 어레이를 작성할 수도 있습니다.이러한 어레이는 피벗보다 작은 어레이, 동등한 어레이, 피벗보다 큰 어레이입니다.이렇게 하면 작업 속도가 약간 빨라질 수 있습니다.)
스칼라 버전은 실제로 테일 재귀적이라고 생각하지 않습니다.Array.concat.
또한 이것이 관용적인 스칼라 코드라고 해서 이것이 그것을 하는 최선의 방법이라는 것을 의미하지는 않는다.
가장 좋은 방법은 Scala의 내장된 정렬 기능 중 하나를 사용하는 것입니다.이렇게 하면 불변의 보증을 받을 수 있고 빠른 알고리즘이 있음을 알 수 있습니다.
예를 들어 Stack Overflow 질문 Scala에서 어레이를 정렬하려면 어떻게 해야 합니까?를 참조하십시오.
불변성은 비싸지 않다.프로그램이 수행해야 하는 작업의 작은 서브셋을 측정하고 퀵소트 측정과 같은 가변성을 바탕으로 솔루션을 선택하면 비용이 많이 들 수 있습니다.
간단히 말하면, 기능적인 언어만을 사용하는 경우는, 재빠르게 분류할 수 없습니다.
다른 각도에서 생각해 봅시다.다음 두 가지 기능에 대해 살펴보겠습니다.
// 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)
}
그것을 벤치마킹하면 가변 데이터 구조를 사용하는 코드는 어레이를 복사해야 하지만 불변의 코드는 그 자체와 무관하기 때문에 성능이 훨씬 떨어진다는 것을 알 수 있습니다.
불변의 데이터 구조를 사용하여 프로그래밍하는 경우 코드를 구성하여 그 장점을 활용할 수 있습니다.단순한 데이터 유형이나 개별 알고리즘이 아닙니다.프로그램은 다른 방식으로 설계될 것입니다.
그렇기 때문에 벤치마킹은 보통 의미가 없습니다.어떤 스타일에 자연스러운 알고리즘을 선택하면 해당 스타일이 승리하거나 애플리케이션 전체를 벤치마킹할 수 있습니다.이는 실용적이지 않은 경우가 많습니다.
배열 정렬은 우주에서 가장 긴요한 작업입니다.어레이 정렬 마이크로벤치마크에서 많은 우아한 '불변의' 전략/실장이 제대로 작동하지 않는 것은 놀라운 일이 아닙니다.그러나 이는 불변성이 "일반적으로" 비용이 많이 든다는 것을 의미하지는 않는다.불변의 구현이 가변 구현과 동등한 성능을 발휘하는 작업은 많지만 어레이 정렬은 그 중 하나가 아닌 경우가 많습니다.
명령형 알고리즘과 데이터 구조를 기능형 언어로 다시 쓰는 것만으로 비용이 많이 들고 쓸모가 없습니다.이러한 것들을 빛나게 하려면 기능 프로그래밍에서만 사용할 수 있는 기능(데이터 구조 지속성, 게으른 평가 등)을 사용해야 합니다.
Scala의 불변성 비용
다음은 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
}
}
이 버전에서는 어레이의 복사본을 만들고 Java 버전을 사용하여 어레이를 정렬한 후 복사본을 반환합니다.Scala는 내부적으로 불변의 구조를 사용하도록 강요하지 않습니다.
따라서 Scala의 이점은 필요에 따라 가변성과 불변성을 활용할 수 있다는 것입니다.단점은 그렇게 잘못하면 불변의 혜택을 제대로 받지 못한다는 것입니다.
Quick Sort는 인플레이스 작업 시 빠른 것으로 알려져 있기 때문에 이는 공정한 비교가 되지 않습니다.
그렇게 말하면...Array.concat?그 외에는 명령형 프로그래밍에 최적화된 수집 유형이 함수 알고리즘에서 사용하려고 하면 특히 느려집니다. 다른 거의 모든 선택지가 더 빠릅니다.
고려해야 할 또 하나의 매우 중요한 포인트는 아마도 두 가지 접근 방식을 비교할 때 가장 중요한 문제일 것입니다. "이것이 여러 노드/코어로 얼마나 잘 확장됩니까?"입니다.
불변의 퀵소트를 찾고 있다면 실제로는 병행 퀵소트를 원하기 때문에 그렇게 할 가능성이 높습니다.위키피디아에는 이 주제에 대한 인용문이 몇 개 있습니다.http://en.wikipedia.org/wiki/Quicksort#Parallelizations
scala 버전은 함수가 반복되기 전에 단순히 분기할 수 있기 때문에 사용 가능한 코어가 충분한 경우 수십억 개의 엔트리가 포함된 목록을 매우 빠르게 정렬할 수 있습니다.
현재 시스템의 GPU는 128개의 코어를 갖추고 있습니다.이 코어로 Scala 코드를 실행할 수 있다면 현재보다 2년 늦은 심플한 데스크톱 시스템에서 사용할 수 있습니다.
그게 어떻게 단일 스레드 방식의 필수 접근법에 맞설 수 있을까요?
따라서 더 중요한 질문은 다음과 같습니다.
"개개의 코어가 더 이상 빨라지지 않고 동기화/잠금 기능이 병렬화에 실질적인 어려움을 겪고 있다는 점을 고려하면, 변동성은 비용이 많이 들까요?
OO프로그래밍은 복잡성을 감추기 위해 추상화를 사용하고 함수프로그래밍은 복잡성을 없애기 위해 불변성을 사용한다고 합니다.스칼라의 하이브리드 세계에서는 애플리케이션 코드를 남기는 명령 코드를 숨기기 위해 OO를 사용할 수 있습니다.사실 도서관은 많은 명령 코드를 사용하지만 그렇다고 우리가 그것들을 사용하지 말아야 한다는 뜻은 아니다.다른 사람들이 말했듯이, 주의해서 사용한다면, 여기서 두 가지 장점을 모두 얻을 수 있습니다.
언급URL : https://stackoverflow.com/questions/4101924/functional-programming-is-immutability-expensive
'programing' 카테고리의 다른 글
| 외부 볼륨을 연결하는 동안 도커 구성과 문제를 사용하여 mariadb 10.4.8 도커 컨테이너를 사용하는 사용자 'root'@'localhost'에 대한 액세스가 거부되었습니다. (0) | 2023.01.10 |
|---|---|
| Pivotal Cloud Foundry는 MariaDB를 지원합니까? (0) | 2023.01.10 |
| JSON의 RestTemplate를 통한 POST 요청 (0) | 2023.01.10 |
| 사전 목록을 panda DataFrame으로 변환 (0) | 2022.12.26 |
| 부동값이 정수인지 확인하는 방법 (0) | 2022.12.26 |