범위 배열에서 멤버십 검색

Question

시스템 시뮬레이션의 일부로 스파 스 메모리 배열을 사용하여 64 비트 주소 지정을 사용하여 메모리 공간을 모델링하고 해당 메모리 내에 할당 된 버퍼를 추적하는 개체 목록을 유지합니다. 메모리 공간. 버퍼는 동적으로 할당 및 할당 해제됩니다.

할당 된 버퍼 내에서 주어진 주소 또는 주소 범위를 검색하여 메모리 모델에 대한 액세스가 할당 된 공간에 있는지 여부를 확인하는 기능이 있습니다. 그리고 "내 첫 번째 차단"을 찾을 때까지 모든 버퍼를 검색합니다. match "는 우리의 시뮬레이션을 10 % 느리게 만듭니다. 우리의 UUT는 시뮬레이션으로 검사해야하는 많은 메모리 액세스를 수행합니다.

그래서 최적화를 시도하고 있습니다. 메모리 버퍼 객체에는 시작 주소와 길이가 포함됩니다. 개체 작성시 주소를 시작하여 개체 배열을 정렬하고 검사 기능이 호출 될 때 주어진 주소가 시작/끝 범위 내에 있는지보기 위해 배열을 통해 이진 검색을 수행하려고합니다.

더 빠르고 더 빠른 방법이 있습니까? 힙이나 해시 서명 또는 일부를 사용하여 더 빠른/쿨러 알고리즘이 있어야합니다. 맞습니까?

Answer 1

정렬 된 배열을 통한 이진 검색은 작동하지만 할당/할당 취소 속도가 느립니다.

단순한 경우는 삽입 (할당), 제거 (할당 취소) 및 검색이 모두 O (로그)가되도록 정렬 된 이진 트리 (red-black 트리, AVR 트리 등)를 시작 주소로 인덱싱하는 것입니다. 엔). 대부분의 현대 언어는 이미 그러한 데이터 구조 (예 : C++의 std::map)를 제공합니다.

Answer 2

내 첫 번째 생각도 이진 검색이었고 좋은 생각이라고 생각합니다. 당신도 신속하게 삽입하고 제거 할 수 있어야합니다. 해시를 사용하면 주소를 버킷에 넣을 수 있습니다 (내 의견으로는). 그러면 올바른 버킷에 빠르게 도착한 다음 버킷을 검색해야합니다.

Answer 3

기본적으로 문제는 "유효한"메모리의 간격이 정의되어 있고 그 간격을 벗어난 메모리가 "유효하지 않음"이며 올바른 메모리 블록 안에 있는지 여부를 확인하려는 것입니다.

할당 된 모든 블록의 시작 주소를 이진 트리에 저장하여 확실히 수행 할 수 있습니다. 그런 다음 쿼리 한 주소 또는 그 이하의 주소에서 가장 큰 주소를 검색하고 주소가 유효한 주소 길이 내에 있는지 확인하십시오. 이것은 당신에게 O (log n) 쿼리 시간을줍니다. 여기서 n은 할당 된 블록의 수입니다. 동일한 쿼리가 블록 자체를 실제로 찾는데도 사용될 수 있으므로 주어진 주소에서 블록의 내용을 읽을 수도 있습니다. 그러면 해당 블록의 내용도 필요할 것입니다.

그러나이 방법이 가장 효율적인 방법은 아닙니다. 대신 1 차원 공간 하위 분할 트리를 사용하여 유효하지 않은 메모리 영역을 표시 할 수 있습니다. 예를 들어, 내부적으로 무효 한 주소만을 가진 16kB 블록을 모두 "1"로 매핑하고 다른 블록을 "0"으로 매핑하는 분기 계수가 256 인 트리 (8 비트에 해당)를 사용하십시오. 트리는 2 단계로 구성되어 질의에 매우 효율적입니다. 주소를 볼 때, 틀림없이 틀린 경우에이 나무 모양을 첫째로 사문하십시오; 그렇지 않은 경우에만 다른 하나를 쿼리하십시오. 실제적으로 많은 메모리 참조가 실제로 발생하는 경우에만 속도를 향상시킬 수 있습니다. 모든 메모리 참조가 실제로 유효하고 사용자가 주장하는 경우 아무 것도 저장하지 않습니다. 그러나이 아이디어를 뒤집어서 유효한 주소 만 가진 16kB 또는 256B 블록 모두에 트리 표시를 사용할 수도 있습니다. 트리가 얼마나 커지는가는 시뮬레이트 된 메모리 할당자가 어떻게 작동하는지에 달려 있습니다.