배열을 트리밍 할 수없는 이유는 무엇입니까?

배열을 트리밍 할 수없는 이유는 무엇입니까?

---

MSDN 문서 사이트에서 Array.Resize방법 에 대해 다음과 같이 말합니다 .

newSize가 이전 배열의 길이보다 크면 새 배열이 할당되고 모든 요소가 이전 배열에서 새 배열로 복사됩니다.

newSize가 이전 배열의 길이보다 작 으면 새 배열이 할당되고 새 배열이 채워질 때까지 요소가 이전 배열에서 새 배열로 복사됩니다. 이전 배열의 나머지 요소는 무시됩니다.

배열은 인접한 메모리 블록의 시퀀스입니다. 더 큰 배열이 필요하면 옆에있는 메모리가 다른 데이터에 의해 이미 요청되었을 수 있으므로 메모리를 추가 할 수 없다는 것을 이해합니다. 그래서 우리는 원하는 더 큰 크기의 인접 메모리 블록의 새로운 시퀀스를 요구하고 거기에 항목을 복사하고 이전 공간에 대한 요구를 제거해야합니다.

하지만 왜 더 작은 크기의 새 어레이를 만들까요? 어레이가 마지막 메모리 블록의 주장을 제거 할 수없는 이유는 무엇입니까? 그러면 지금처럼 O (n) 대신 O (1) 연산이됩니다.

컴퓨터 아키텍처 또는 물리적 수준에서 데이터가 구성되는 방식과 관련이 있습니까?

---

귀하의 질문에 답하려면 메모리 관리 시스템의 설계와 관련이 있습니다.

이론적으로 자신의 메모리 시스템을 작성하는 경우 말한대로 정확하게 작동하도록 완전히 설계 할 수 있습니다.

그런 다음 질문은 왜 그렇게 설계되지 않았는지가됩니다. 대답은 메모리 관리 시스템이 메모리의 효율적인 사용과 성능 사이에서 균형을 이룬다는 것입니다.

예를 들어 대부분의 메모리 관리 시스템은 메모리를 바이트 단위로 관리하지 않습니다. 대신 메모리를 8KB 청크로 분할합니다. 이것에 대한 이유는 대부분 성능에 관한 것입니다.

이유 중 일부는 프로세서가 메모리를 얼마나 잘 이동하는지와 관련이 있습니다. 예를 들어 프로세서가 한 번에 8KB의 데이터를 복사하는 것이 훨씬 더 좋았다고 가정 해 봅시다. 그런 다음 데이터를 8KB 청크로 저장하면 성능상의 이점이 있습니다. 그것은 CPU 아키텍처를 기반으로 한 설계 절충안입니다.

알고리즘 성능 상충 관계도 있습니다. 예를 들어 대부분의 응용 프로그램의 동작을 조사한 결과 응용 프로그램의 99 %가 6KB에서 8KB 크기의 데이터 블록을 할당한다는 것을 알 수 있습니다.

메모리 시스템이 4KB를 할당하고 해제하는 것을 허용했다면 할당의 99 %를 사용할 수없는 무료 4KB 청크가 남게됩니다. 4KB 만 필요하더라도 8KB에 초과 할당하는 대신 훨씬 더 재사용 할 수 있습니다.

또 다른 디자인을 고려하십시오. 크기에 상관없이 사용 가능한 메모리 위치 목록이 있고 2KB의 메모리를 할당하도록 요청했다고 가정 해 보겠습니다. 한 가지 접근 방식은 사용 가능한 메모리 목록을 살펴보고 최소 2KB 크기의 메모리를 찾는 것입니다. 그러나 전체 목록을 살펴보면서 가장 작은 블록을 찾습니까? 아니면 충분히 큰 첫 번째 블록을 찾아 사용하십시오. 그.

첫 번째 방법은 더 효율적이지만 느리고 두 번째 방법은 덜 효율적이지만 더 빠릅니다.

"메모리 관리"가있는 C # 및 Java와 같은 언어에서는 더욱 흥미로워집니다. 관리 메모리 시스템에서는 메모리가 해제되지도 않습니다. 그것은 단지 사용을 멈추고, 가비지 컬렉터는 나중에 어떤 경우에는 훨씬 나중에 감지하고 해제합니다.

다른 메모리 관리 및 할당에 대한 자세한 내용은 Wikipedia의이 기사를 참조하십시오.

https://en.wikipedia.org/wiki/Memory_management

---

사용되지 않은 메모리는 실제로 사용되지 않습니다. 힙의 구멍을 추적하는 것은 모든 힙 구현의 작업입니다. 최소한 관리자는 구멍의 크기를 알아야하고 위치를 추적해야합니다. 항상 최소 8 바이트가 필요합니다.

.NET에서 System.Object는 중요한 역할을합니다. 모든 사람들은 그것이 무엇을하는지 알고 있으며, 물체가 수집 된 후에도 계속 살아남을만큼 분명하지 않은 것은 무엇인지 압니다. 개체 헤더의 두 추가 필드 (syncblock 및 유형 핸들)는 이전 / 다음 자유 블록에 대한 뒤로 및 앞으로 포인터로 바뀝니다. 또한 32 비트 모드에서 최소 크기는 12 바이트입니다. 객체를 수집 한 후 사용 가능한 블록 크기를 저장할 수있는 충분한 공간이 항상 있음을 보장합니다.

따라서 이제 문제를 볼 수 있습니다. 배열의 크기를 줄여도이 세 필드에 맞을만큼 충분히 큰 구멍이 만들어지는 것은 아닙니다. 할 수있는 것은 없지만 "할 수 없습니다"예외가 발생합니다. 또한 과정의 비트에 달려 있습니다. 고려하기에는 너무 못 생겼습니다.

---

나는 그것이 매우 흥미로운 질문이라는 것을 알았 기 때문에 귀하의 질문에 대한 답변을 찾고있었습니다. 흥미로운 첫 번째 줄이있는 이 답변 을 찾았 습니다.

배열의 일부를 해제 할 수 없습니다. free()가져온 포인터 만 malloc()사용할 수 있으며 그렇게하면 요청한 모든 할당이 해제됩니다.

따라서 실제로 문제는 할당 된 메모리를 유지하는 레지스터입니다. 할당 한 블록의 일부만 해제 할 수 없으며 완전히 해제해야하거나 전혀 해제하지 않습니다. 즉, 해당 메모리를 해제하려면 먼저 데이터를 이동해야합니다. .NET 메모리 관리가 이와 관련하여 특별한 일을하는지 모르겠지만이 규칙이 CLR에도 적용된다고 생각합니다.

---

나는 이것이 오래된 배열이 파괴되지 않았기 때문이라고 생각합니다. 다른 곳에서 참조되고 있고 여전히 액세스 할 수있는 경우 여전히 존재합니다. 이것이 새 어레이가 새 메모리 위치에 생성되는 이유입니다.

예:

int[] original = new int[] { 1, 2, 3, 4, 5, 6 };
int[] otherReference = original; // currently points to the same object

Array.Resize(ref original, 3);

Console.WriteLine("---- OTHER REFERENCE-----");

for (int i = 0; i < otherReference.Length; i++)
{
    Console.WriteLine(i);
}

Console.WriteLine("---- ORIGINAL -----");

for (int i = 0; i < original.Length; i++)
{
    Console.WriteLine(i);
}

인쇄물:

---- OTHER REFERENCE-----
0
1
2
3
4
5
---- ORIGINAL -----
0
1
2

---

realloc을있는 그대로 정의하는 데는 두 가지 이유가 있습니다. 첫째, 더 작은 크기로 realloc을 호출하면 동일한 포인터가 반환된다는 보장이 없다는 것이 절대적으로 분명합니다. 프로그램이 이러한 가정을하면 프로그램이 손상됩니다. 포인터가 99.99 %의 시간 동안 동일하더라도. 많은 빈 공간의 중간에 큰 블록이 오른쪽으로 쳐서 힙 조각화가 발생하면 realloc은 가능하면 자유롭게 이동할 수 있습니다.

둘째,이를 수행하는 것이 절대적으로 필요한 구현이 있습니다. 예를 들어, MacOS X에는 1 ~ 16 바이트의 malloc 블록을 할당하는 데 하나의 대형 메모리 블록이 사용되며, 17 ~ 32 바이트의 malloc 블록에 대한 또 다른 대형 메모리 블록, 33 ~ 48 바이트의 malloc 블록에 대해 하나 등이 사용됩니다. 따라서 33 ~ 48 바이트 범위에 머무르는 모든 크기 변경은 동일한 블록을 반환하지만 32 바이트 또는 49 바이트로 변경 하면 블록을 재 할당 해야 한다는 것을 매우 자연스럽게 만듭니다 .

realloc의 성능에 대한 보장은 없습니다. 그러나 실제로 사람들은 크기를 조금 더 작게 만들지 않습니다. 주요 사례는 다음과 같습니다. 필요한 크기의 예상 상한에 메모리를 할당하고 채운 다음 실제 훨씬 더 작은 필요한 크기로 크기를 조정합니다. 또는 메모리를 할당 한 다음 더 이상 필요하지 않을 때 매우 작은 크기로 크기를 조정합니다.

---

.NET 런타임의 디자이너 만이 실제 추론을 말할 수 있습니다. 그러나 내 생각에는 메모리 안전성이 .NET에서 가장 중요하며 메모리 안전성과 가변 배열 길이를 모두 유지하는 것은 매우 비싸고 배열이있는 코드가 얼마나 복잡할지는 말할 것도 없습니다.

간단한 경우를 고려하십시오.

var fun = 0;
for (var i = 0; i < array.Length; i++)
{
  fun ^= array[i];
}

메모리 안전성을 유지하려면 array경계 검사가 다른 스레드에 의해 중단되지 않도록 모든 액세스를 경계 검사해야합니다 (.NET 런타임은 C 컴파일러보다 훨씬 더 엄격한 보증을 제공합니다).

따라서 배열에서 데이터를 읽는 동시에 경계를 확인하는 스레드로부터 안전한 작업이 필요합니다. CPU에는 이러한 명령이 없으므로 유일한 옵션은 일종의 동기화 기본 요소입니다. 코드는 다음과 같이 바뀝니다.

var fun = 0;
for (var i = 0; i < array.Length; i++)
{
  lock (array)
  {
    if (i >= array.Length) throw new IndexOutOfBoundsException(...);

    fun ^= array[i];
  }
}

말할 필요도없이 이것은 엄청나게 비싸다. 어레이 길이를 변경 불가능하게 만들면 두 가지 성능이 크게 향상됩니다.

• 길이는 변경할 수 없기 때문에 경계 검사를 동기화 할 필요가 없습니다. 이렇게하면 각 개별 경계 검사가 훨씬 저렴 해집니다.
• ... 안전성을 증명할 수 있는지 확인하는 경계를 생략 할 수 있습니다.

In reality, what the runtime actually does ends up being something more like this:

var fun = 0;
var len = array.Length; // Provably safe

for (var i = 0; i < len; i++)
{
  // Provably safe, no bounds checking needed
  fun ^= array[i];
}

You end up having a tight loop, no different from what you'd have in C - but at the same time, it's entirely safe.

Now, let's see the pros and cons of adding array shrinking the way you want it:

Pros:

• In the very rare scenario where you'd want to make an array smaller, this would mean the array doesn't need to be copied over to change its length. However, it would still require a heap compaction in the future, which involves a lot of copying.
• If you store object references in the array, you might get some benefits from cache locality if the allocation of the array and the items happens to be colocated. Needless to say, this is even rarer than Pro #1.

Cons:

• Any array access would become hideously expensive, even in tight loops. So everyone would use unsafe code instead, and there goes your memory safety.
• Every single piece of code dealing with arrays would have to expect that the length of the array can change at any time. Every single array access would need a try ... catch (IndexOutOfRangeException), and everyone iterating over an array would need to be able to deal with the changing size - ever wondered why you can't add or remove items from List<T> you're iterating over?
• A huge amount of work for the CLR team that couldn't be used on another, more important feature.

There's some implementation details that make this even less of a benefit. Most importantly, .NET heap has nothing to do with malloc/free patterns. If we exclude the LOH, the current MS.NET heap behaves in a completely different way:

• Allocations are always from the top, like in a stack. This makes allocations almost as cheap as stack allocation, unlike malloc.
• Due to the allocation pattern, to actually "free" memory, you must compact the heap after doing a collection. This will move objects so that the free spaces in the heap are filled, which makes the "top" of the heap lower, which allows you to allocate more objects in the heap, or just free the memory for use by other applications on the system.
• To help maintain cache locality (on the assumption that objects that are commonly used together are also allocated close to one another, which is quite a good assumption), this may involve moving every single object in the heap that's above the freed space down. So you might have saved yourself a copy of a 100-byte array, but then you have to move 100 MiB of other objects anyway.

Additionally, as Hans explained very well in his answer, just because the array is smaller doesn't necessarily mean that there's enough space for a smaller array in the same amount of memory, due to the object headers (remember how .NET is designed for memory safety? Knowing the right type of an object is a must for the runtime). But what he doesn't point out is that even if you do have enough memory, you still need to move the array. Consider a simple array:

ObjectHeader,1,2,3,4,5

Now, we remove the last two items:

OldObjectHeader;NewObjectHeader,1,2,3

Oops. We need the old object header to keep the free-space list, otherwise we couldn't compact the heap properly. Now, it could be done that the old object header would be moved beyond the array to avoid the copy, but that's yet another complication. This is turning out to be quite an expensive feature for something that noöne will ever use, really.

And that's all still in the managed world. But .NET is designed to allow you to drop down to unsafe code if necessary - for example, when interoperating with unmanaged code. Now, when you want to pass data to a native application, you have two options - either you pin the managed handle, to prevent it from being collected and moved, or you copy the data. If you're doing a short, synchronous call, pinning is very cheap (though more dangerous - the native code doesn't have any safety guarantees). The same goes for e.g. manipulating data in a tight loop, like in image processing - copying the data is clearly not an option. If you allowed Array.Resize to change the existing array, this would break entirely - so Array.Resize would need to check if there's a handle associated with the array you're trying to resize, and throw an exception if that happens.

More complications, much harder to reason about (you're going to have tons of fun with tracking the bug that only occurs once in a while when it so happens that the Array.Resize tries to resize an array that just so happens to right now be pinned in memory).

As others have explained, native code isn't much better. While you don't need to maintain the same safety guarantees (which I wouldn't really take as a benefit, but oh well), there's still complications related to the way you allocate and manage memory. Called realloc to make a 10-item array 5-item? Well, it's either going to be copied, or it's still going to be the size of a 10-item array, because there's no way to reclaim the left-over memory in any reasonable manner.

So, to make a quick summary: you're asking for a very expensive feature, that would be of very limited benefit (if any) in an extremely rare scenario, and for which there exists a simple workaround (making your own array class). I don't see that passing the bar for "Sure, let's implement this feature!" :)

---

There might be many sophisticated data-structures operating "under the hood" in any heap-management system. They might, for instance, store blocks according to their present size. It would add a lot of complications if blocks were allowed to "be split, grow, and shrink." (And, it really wouldn't make things any 'faster.')

Therefore, the implementation does the always-safe thing:   it allocates a new block, and moves values as needed. It is known that "this strategy will always work reliably, on any system." And, it really won't slow things down at all.

---

Under the hood, Arrays are stored in continuous memory block but is still a primitive type in many languages.

To answer your question, the space allocated to an array is considered as one single block and stored in stack in case of local variables or bss/data segments when it is global. AFAIK, when you access an array like array[3], at low level, OS will get you a pointer to the first element and jumps/skip till it reaches (thrice in case of above example) the required block. So it might be an architectural decision that an array size can't be changed once it is declared.

Similar way, OS cannot know if it's valid index of an array before it accesses the required index. When it tries to access the requested index by reaching memory block after the jumping process and finds out that the memory block reached is not part of the array, it'll throw an Exception

참고URL : https://stackoverflow.com/questions/38453335/why-can-arrays-not-be-trimmed