배열을 최적화하는 방법

배열을 사용하여 여러 데이터들을 정렬하다보면 문득 배열도 최적화할 수 있지 않을까를 생각해보게 된다. C#에서 배열은 unsafe context를 사용하여 선언하지 않는 이상 무조건 heap 에 할당된다. 이러한 특이사항은 재밌게도 클래스내 필드, 그리고 함수 내에서도 전부 동일한데, fixed keyword를 사용하지 않으면 배열의 고정 메모리 주소를 받아올 수 없고, 배열이 담긴 레퍼런스를 반환한다. 그리고 생성되고 레퍼런스되지않는 배열은 GC가 수집해가는데, 배열이 매번 반복적으로 필요한 상황에서 지속적인 배열 생성은 꽤나 큰 부담으로 작용될 수 있을 것이다.

 

ArrayPool<T>

이미지 출처:&nbsp;https://medium.com/@epeshk/the-big-performance-difference-between-arraypools-in-net-b25c9fc5e31d

 

이런 상황에서 ArrayPool 은 꽤나 매력적인 선택으로 다가올 수 있다. 사용을 다한 배열을 반환하고, 다른 사용자가 나타나면 재사용할 수 있도록 하는 것이다. ArrayPool은 tls 로 구현되어 설계되었으며, 생성시 배열의 최대 길이와 bucket 당 최대 배열의 개수를 지정하여 생성한다. 단점은 이로 인해 처음 생성 또는 Shared를 사용시 비교적 큰폭의 오버헤드가 발생하며, 만약 길이가 매우 큰 배열을 요청한다면 더 큰 오버헤드가 발생하고, 추후 GC까지 퍼포먼스에 큰 영향을 줄 수 있다. 그래서 ArrayPool은 비교적 길이가 작지만 반복적으로 사용하여야하는 부분에서 유용하게 사용될 수 있다.

 

예를 들어, 계산을 위해 잠깐 배열을 사용하여야하는데, 그 계산이 매 프레임마다 존재하고 필요한 길이가 변칙적이라면 사용을 고려해볼 수 있다.

 

Fragmentation

만약 하나의 배열을 시작으로, 파생되는 여러 배열이 필요한 경우에는 어떻게하면 될까? 이런 경우, 배열을 여러 부분(fragment)로 나누어 활용할 수 있다.

 

ArraySegment<T>

배열에서 파생되어 사용할 부분이 연속적이라면, 즉 길이가 100인 배열에서 인덱스 5부터 50까지 연속된 부분이 필요하다면 세그먼트를 고려해볼 수 있다. 이렇게 생성된 세그먼트는 원래의 배열의 레퍼런스를 갖고, offset 과 length로 부분적인 레퍼런스를 참조시키게 한다.

 

그러나 만약, 연속된 부분이 아닌 집합을 다루는 경우는 어떨까? 만약 10의 길이를 갖는 배열에서 1과 5, 그리고 7부터 9까지의 인덱스를 갖는 부분 집합을 갖고 싶다면 추가적인 구현을 통해 달성할 수 있을 것이다.

 

ArrayFragment<T>

#region Copyrights

// Copyright 2024 Syadeu
// Author : Seung Ha Kim (Syadeu)
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// File created : 2024, 3, 12 22:45

#endregion

using System;
using Unity.Mathematics;
using UnityEngine.Assertions;

namespace Vvr
{
    public struct ArrayFragment<T> : IDisposable
    {
        private T[]   m_Array;
        private BitArray64[] m_Indices;

        public T this[int index]
        {
            get => ElementAt(index);
            set => SetElementAt(index, value);
        }


        public int Length
        {
            get
            {
                ulong sum = 0;
                {
                    for (int i = 0; i < m_Indices.Length; i++)
                    {
                        sum += m_Indices[i].Value;
                    }
                }
                if (sum == 0) return 0;
                if (sum == 1) return 1;

                int count = 0;
                if ((sum & 1) == 1)
                {
                    count++;
                    sum -= 1;
                }

                count += (int)math.log2(sum);
                return count;
            }
        }

        public ArrayFragment(T[] array)
        {
            m_Array   = array;
            m_Indices = new BitArray64[m_Array.Length / 64 + 1];
        }

        public T ElementAt(int index)
        {
            int length = Length;
            Assert.IsTrue(index < length, "index < Length");
            int c      = 0;
            int i      = 0;
            while (c < index && i < length)
            {
                int yy = i >> 6,
                    xx = i & 0b_11_1111;
                c += m_Indices[yy][xx].ToByte();
                i++;
            }

            return m_Array[c];
        }

        public void SetElementAt(int index, T t)
        {
            int length = Length;
            Assert.IsTrue(index < length, "index < Length");
            int c      = 0;
            int i      = 0;
            while (c < index && i < length)
            {
                int yy = i >> 6,
                    xx = i & 0b_11_1111;
                c += m_Indices[yy][xx].ToByte();
                i++;
            }

            m_Array[c] = t;
        }

        public void Add(int index)
        {
            int yy = index >> 6,
                xx = index & 0b_11_1111;
            m_Indices[yy][xx] = true;
        }
        public void Remove(int index)
        {
            int yy = index >> 6,
                xx = index & 0b_11_1111;
            m_Indices[yy][xx] = false;
        }

        public void Dispose()
        {
            m_Array   = null;
            m_Indices = null;
        }
    }
}

 

추가적인 BitArray64 구현을 통해, ulong 8bytes 를 64개의 비트로 쪼개어 받아올 수 있는 구조체를 선언하고, 그것을 활용하여 배열의 길이가 64 넘는 경우 추가로 8bytes씩 할당하게 하여, occupied index를 알 수 있는 구조체 ArrayFragment<T> 를 선언한다. 모든 BitArray64 배열의 합, 즉 모든 ulong의 합이 0일 경우에는 길이가 0이며, 1인 경우에는 1개, 그리고 그 이상일 경우에는 첫번째 비트가 1인지를 검사하고, 로그를 통해 지수를 얻는다. 즉, 지수값과 첫번째 비트만 검사하면 현재 이 구조체가 담는 최대 길이를 반환할 수 있다.

 

---

참조

1. https://stackoverflow.com/questions/32274102/when-is-array-allocated-on-stack-in-c
2. https://learn.microsoft.com/ko-kr/dotnet/api/system.buffers.arraypool-1?view=net-8.0
3. https://medium.com/@epeshk/the-big-performance-difference-between-arraypools-in-net-b25c9fc5e31d

---

© 2024 - 2024 Vvidr - All Rights Reserved.