PagedArray Class
재할당 없이 별도의 메모리 페이지들을 사용하는 랜덤 컨테이너입니다.
template <class Type>
class PagedArray : public RandomContainer< Type >
Template 파라미터
- Type
-
배열이 저장하는 항목들의 타입입니다.
멤버
생성자
내용 관리
내용 쿼리
| Enumerate |
배열 내용의 열거를 허용합니다.
|
| Begin |
배열의 1번째 항목을 참조하는 반복자(iterator)를 리턴합니다.
|
| End |
배열의 마지막 직전 항목을 참조하는 반복자(iterator)를 리턴합니다.
|
성능 튜닝
Public 타입
설명
PagedArray는 재할당 없이 별도의 메모리 페이지들 안에 항목들을 저장하는 RandomContainer 구현입니다.
할당 전략에 따라 하나 이상의 페이지들이 포함된 할당 단위로 메모리를 할당합니다.
public 메소드들은 비-가상이며 적절한 경우 인라인입니다.
랜덤 컨테이너 구현 중에서 PagedArray는 다음 장점을 갖고 있습니다:
- 재할당이 되지 않아 끝에 새로운 항목을 삽입(push)하고 끝에서 항목을 제거(pop)하는 속도가 빠릅니다.
새로운 항목이 마지막 페이지에 맞지 않으면 새로운 항목(또는 할당 전략에 따른 새로운 항목들)을 할당합니다.
적어도 두 페이지가 (또는 더 정확히 두 개의 할당 단위들이) 비어 있으면 해당 페이지는 해제됩니다.
- 메모리 활용도가 매우 우수합니다. 일정한 할당 전략으로 최대 2 페이지만 낭비됩니다.
선형 할당 전략을 이용하면 최대 sqrt (8 * page_count + 1) - 2 페이지만 낭비합니다.
그러나 지수(exponential) 할당 전략의 메모리 활용률은 나쁘고 그 특성은 Array의 그것과 비슷합니다.
- 항목들에게 저장 오버헤드를 거의 부과하지 않습니다:
항목 저장 셀의 총 비용은 항목을 포함하는 페이지 외에도 페이지에 대한 포인터를 포함하는 페이지 테이블이 있기 때문에 항목의 물리적 크기보다 다소 더 큽니다.
- 메모리를 거의 할당하지 않으며 선형(4 Gb에서 최대 약 10000)과 지수(4 Gb에서 최대 32) 할당 전략으로 거의 할당 단위들을 보유하지 않습니다.
그러나 상수 할당 전략과 많은 수의 항목들을 할당하면 자주 할당하고 상대적으로 많은 수의 할당 단위들을 보유하게 됩니다. (이 경우 단일 페이지)
- 중간 고유 크기를 갖고 있습니다: 현재 28 바이트입니다.
- 항상 마지막에 삽입 및 제거가 발생하는 경우 항목들에 대한 참조들을 장기간 저장할 수 있습니다.
랜덤 컨테이너 구현 중에서 PagedArray는 다음 단점을 갖고 있습니다:
- 삽입과 제거는 상대적으로 느릴 수 있습니다. 왜냐하면 삽입 또는 제거 지점 위의 모든 항목들은 항목들에 대한 할당 연산자를 호출할 때 위 또는 아래로 이동하기 때문입니다.
- 만약 임의의 인덱스에서 삽입과 제거가 발생하면 항목들에 대한 참조들은 배열에서 다음 변경 동작을 호출할 때까지만 저장할 수 있습니다.
항목들은 기본 생성자와 복사 생성자, 할당 연산자를 가져야 합니다. 이외에도 비교 연산자(==와 !=)를 갖고 있다면, 값 종속적인 연산(예. Find, Count, Contains 등) 역시 사용할 수 있게 됩니다.
다음 그림은 상수(constant) 할당 전략을 이용하는 PagedArray의 내부 레이아웃을 보여줍니다:
다음 그림은 선형(linear) 할당 전략을 이용하는 PagedArray의 내부 레이아웃을 보여줍니다:
다음 그림은 지수(exponential) 할당 전략을 이용하는 PagedArray의 내부 레이아웃을 보여줍니다:
요구사항
네임스페이스: GS
헤더: PagedArray.hpp
참고사항
Array | StableArray
