AppendOnly
1.0.0
고속 C# 불변 추가 전용 목록입니다. (업데이트: 9월 24일 23일; 사용하지 않는 것이 좋습니다. 근거와 대안은 하단의 참고 사항을 참조하세요.)
dotnet 패키지 추가 AppendOnly
첫째, 기존 불변 컬렉션은 새 컬렉션을 반환하는 추가, 삭제 및 업데이트를 수행하는 데 정말 어려움을 겪습니다. 그들은 문자 그대로 많은 것을 복사해야 합니다. 추가만 하는 경우 LinkedList가 친구가 되어 즉시 "복사"된 것처럼 나타날 수 있습니다.
둘째, 기존 불변 라이브러리는 복잡하고 사용하기 어렵습니다. 이를 위해서는 빌더 클래스와 실제 메커니즘에 대한 좋은 이해가 필요합니다. 그렇지 않으면 심각하게 나쁜 성능 문제가 발생하게 됩니다.
마지막으로: 이 클래스는 매우 긴밀한 루프에서 사용하기에 완전히 안전합니다. 최대한 꽉 조이세요.
AppendOnly는 내부적으로 linkedList를 사용하며 새로운 "불변" 복사본을 생성할 때 컬렉션 항목을 복사하지 않습니다. 이는 단순히 동일한 내부 "변경 가능" linkedList를 공유하는 새 컬렉션 클래스를 반환하지만 이를 변경하기 위한 메서드를 노출하지 않고 컬렉션의 첫 번째(n) 항목을 반복하는 인터레이터만 노출합니다.
따라서 컬렉션이 커짐에 따라 컬렉션 클래스의 이전(오래된) 인스턴스는 목록 끝에 추가된 새 항목을 결코 볼 수 없습니다(열거자를 통해 노출). AppendOnly transactionCollection에 1000개의 새로운 "트랜잭션"을 추가한 후에는 (새로 생성된 각 컬렉션에 대한 참조를 유지한 경우) 각각 1, 2, 3, 4 등의 항목을 포함하는 컬렉션에 대한 1000개의 포인터를 갖게 되지만 추가 항목은 거의 0에 가깝습니다. 메모리 오버헤드.
빌더와 함께 다른 불변 라이브러리를 사용하는 경우 대부분은 최소 500,000개의 객체 인스턴스를 제공합니다.
내가 틀렸을 수도 있습니다. 이것이 출발점입니다. 이것을 사용하면 알려주세요. 비슷한 라인을 따라 더 많은 컬렉션을 만들 예정입니다.
var move = new AppendOnlyList<Moves>();var new_moves = new AppendOnlyList<Moves>();Debug.Assert(moves.Length == 0);// 10개의 무작위 이동 추가(int i=0; i<10) ; i++) new_moves = new_moves.Add(randomMove());// new_list가 항목을 추가했음에도 불구하고 원래 이동에는 여전히 항목이 없습니다. List.Debug.Assert(moves.Length == 0);// new_list에는 컬렉션에 10개의 항목이 있습니다.Debug.Assert(new_moves.Length == 10);// 이 목록은 여러 번 반복해도 안전하며 스레드로부터 안전합니다./ / 아래 코드는 전체 목록을 10번 반복하는 것을 보여줍니다. 이는 일반적으로 캐시한 열거형에 대해서만 수행하는 작업입니다. 즉, 로컬을 생성한 경우 copy.// 별로 효과가 없어 보이는 건 알지만 정말 중요합니다. // 또한, 다른 스레드가 동일한 기본 컬렉션에 추가하느라 바쁠 때 이 작업을 수행하는 것이 안전합니다. // 이는 스레딩 세계에서 엄청난 양의 작업입니다. 여기서는 완전히 안전합니다.for(int i = 0; i<10; i++){foreach(var move in new_moves.Items) wait DoSomethingFunkyAsync(move);} 위 코드에서 new_moves 와 원래 moves 동일한 기본 연결 목록을 공유합니다. AppendOnlyList의 새 복사본이 생성되면 새 복제본이 만들어지지 않고 목록의 헤드에 대한 지점과 길이만 유지됩니다.
이는 복사가 이루어지지 않기 때문에 매우 빠르므로 복사본을 생성하는 다른 불변 컬렉션보다 무한히 빠릅니다.
그리고 컬렉션이 다른 스레드에서 열거되는 동안 컬렉션을 반복하는 것은 스레드로부터 안전합니다! 팔! ... 또는 더 구체적으로 "붐 없음!".
이는 버전 0.1.3 이므로 프로덕션 용도로 사용할 준비가 되지 않았습니다. 이는 개념 증명이므로 위의 주장을 증명하기 위해 몇 가지 스레딩 테스트를 작성한 다음 동료에게 검토하고 알려주도록 요청해야 합니다.
또한 이 컬렉션과 다른 컬렉션 간의 속도 비교는 물론 나란히 비교도 하고 싶습니다.
이 패키지가 마음에 든다면 실제 구현을 살펴보세요. 문자 그대로 AppendOnlyList 및 LinkedListExtensions 2개의 클래스로 구성되어 있으며 매우 작습니다.
당신의 생각을 알려주세요?
:디
질문이 있으시면 저에게 연락해주세요.
Alan Hemmings, twitter : @snowcode LinkedIn : https://www.linkedin.com/in/goblinfactory www : https://goblinfactory.co.uk
...별로 사용하지 않았는데 잊어버렸네요. 이 글을 작성한 이후로 C#은 많은 발전을 이루었습니다. C#에는 많은 변화가 있었지만 그 중 어느 것도 크게 단순화된 것은 없습니다. 불행하게도 나는 새로운 언어 변경에 비추어 이 패키지를 언제 사용해야 하는지에 대한 위의 내 생각이 쓰레기일 수도 있고...상당히 결함이 있을 수도 있다고 생각합니다. 추가 작업을 수행하기 전에 반드시 테스트가 필요합니다. 다음은 이 프로젝트에 대한 재검토를 제안하는 AI C# 설계자와의 빠른 채팅에서 얻은 몇 가지 메모입니다. TBH 내 생각에 이 프로젝트는 여전히 보증될 수 있지만 아마도 추가 전용 유형 구조를 적절하게 생성하는 다양한 방법에 대한 DSL 래퍼(일종의 간단한 팩토리 클래스)일 수 있습니다. 너프가 말했다; 피드백은 다음과 같습니다.
(초안 메모, 테스트 및 확인이 필요합니다!)
예, C#에서는 효율적으로 열거할 수 있는 보다 효율적인 추가 전용 및 메모리 효율적인 구조를 위해 System.Collections.Generic.ArrayBuffer<T> 또는 System.Buffers.ArrayPool<T> 을 사용할 수 있습니다. 그러나 보다 실용적이고 효율적인 추가 전용 구조를 원한다면 다음 옵션을 고려하십시오.
ImmutableArray<T>.Builder
System.Collections.Immutable 패키지에서 제공하는 추가 전용 구조입니다.
효율적인 추가가 가능하고 빌드하는 동안 변경이 가능하지만 ImmutableArray<T> 로 변환되면 변경이 불가능해집니다.
var builder = ImmutableArray.CreateBuilder<int>();builder.Add(1);builder.Add(2);var immutableArray = builder.ToImmutable();
ArrayPool<T> 를 사용한 Memory<T> 및 Span<T>
최소한의 메모리 할당으로 대규모 데이터 블록을 처리하는 데 효율적입니다.
List<T> 에 비해 빈번한 재할당을 방지하기 위해 메모리를 직접 관리합니다.
메모리 사용량을 더 많이 제어하고 싶지만 신중한 관리가 필요한 경우에 적합합니다.
var pool = ArrayPool<int>.Shared;int[] array = pool.Rent(1000); // 풀에서 배열을 요청합니다. // 여기에 데이터를 추가하고 관리합니다.pool.Return(array); // 완료되면 풀로 돌아갑니다.
ValueListBuilder<T> (System.Buffers에서)
스택 할당 방식으로 컬렉션을 구축하는 효율적인 방법을 제공합니다.
데이터 크기가 제한되어 있고 힙 할당 없이 고성능을 원하는 경우 특히 유용합니다.
Span<int>initialSpan = stackalloc int[16]; var valueListBuilder = new ValueListBuilder<int>(initialSpan);valueListBuilder.Append(1);valueListBuilder.Append(2);ReadOnlySpan<int> 범위 = valueListBuilder.AsSpan();
System.IO.Pipelines의 Sequence<T>
추가 전용 방식으로 데이터 시퀀스를 효율적으로 처리하는 데 적합합니다.
고성능 I/O 작업 및 스트리밍 데이터가 필요한 시나리오에 적합합니다.
List<T> : 추가(상각 O(1) )에 적합하고 연속 메모리로 인해 빠른 열거를 제공합니다.
ImmutableArray<T>.Builder : 추가한 후 불변으로 만드는 데 효율적입니다.
ArrayPool<T> 를 사용하는 Memory<T> : 할당을 줄이는 데 적합합니다.
ValueListBuilder<T> : 크기가 알려진 경우 효율적인 스택 기반 빌드입니다. 스택 기반으로 임시적이고 효율적인 컬렉션에 적합합니다.
Sequence<T> : 효율적인 추가가 필요한 높은 처리량 시나리오에 적합합니다.
특정 성능 및 메모리 요구 사항에 따라 선택하십시오.
ChatGPT가 말했습니다.
C#의 LinkedList<T> 는 추가 전용 메모리 구조에 대한 옵션이지만 다음과 같은 이유로 인해 다른 구조에 비해 일반적으로 메모리 효율성이 낮고 열거 속도가 느립니다.
LinkedList<T> 관련 고려사항: 메모리 오버헤드 : LinkedList<T> 의 각 노드에는 다음 노드와 이전 노드에 대한 참조가 포함되어 있어 배열이나 List<T> 와 같은 연속 구조에 비해 상당한 메모리 오버헤드가 발생합니다.
캐시 비효율성 : 연속 메모리에 저장되는 배열 또는 List<T> 와 달리 LinkedList<T> 노드는 힙 전체에 분산되어 있습니다. 이로 인해 캐시 친화적이지 않아 반복 및 액세스 시간이 느려집니다.
열거 성능 : LinkedList<T> 추가 작업(끝에 추가하는 경우 O(1) )에 효율적이지만 캐시 지역성 이점이 없기 때문에 일반적으로 열거 성능이 배열이나 목록보다 느립니다.
LinkedList<T> 사용하는 경우:양쪽 끝이나 중간에서 자주 삽입이나 삭제가 필요한 경우.
List<T> 와 같이 요소 이동을 피하려는 경우.
LinkedList<T> 추가 전용 시나리오에 사용할 수 있지만 일반적으로 List<T> 또는 기타 최신 데이터 구조에 비해 열거 또는 메모리 사용에 가장 효율적인 선택은 아닙니다.
