95 %의 경우에 값이 0 또는 1 일 때 매우 큰 배열에 대한 임의 액세스 최적화?
매우 큰 배열에서 임의 액세스에 대한 가능한 최적화가 있습니까? (현재는을 사용 uint8_t하고 무엇이 더 좋은지 묻고 있습니다)
uint8_t MyArray[10000000];
배열의 임의 위치의 값이
- 모든 경우의 95 % 에 대해 0 또는 1
- 사례의 4 % 에서 2
- 다른 1 % 의 경우 3 에서 255 사이 ?
그렇다면 uint8_t이것을 사용하기 위해 배열 보다 좋은 것이 있습니까? 전체 배열을 임의의 순서로 반복하는 것이 가능한 한 빨라야하며, 이는 RAM 대역폭에서 매우 무거 우므로 여러 어레이에 대해 동시에 여러 스레드를 수행하는 경우 (현재 전체 RAM 대역폭) 빠르게 포화됩니다.
실제로 5 %를 제외한 거의 모든 값이 0 또는 1이라는 것을 알 때 큰 배열 (10 MB)을 갖는 것은 매우 비효율적이라고 생각하기 때문에 배열의 모든 값의 95 %가 실제로 8 비트 대신 1 비트 만 있으면 메모리 사용량이 거의 1 배 줄어 듭니다. 이에 필요한 RAM 대역폭을 크게 줄이는 더 효율적인 메모리 솔루션이 있어야하므로 임의 액세스의 경우 훨씬 더 빠릅니다.
기억할 수있는 간단한 가능성은 일반적인 경우 값당 2 비트의 압축 배열을 유지하고 값당 4 바이트 (원래 요소 인덱스의 경우 24 비트, 실제 값의 경우 8 비트 (idx << 8) | value))로 분리 된 배열을 유지하는 것입니다. 다른 것들.
값을 찾을 때 먼저 2bpp 배열에서 조회를 수행합니다 (O (1)). 0, 1 또는 2를 찾으면 원하는 값입니다. 3을 찾으면 2 차 배열에서 찾아야한다는 의미입니다. 여기에서 이진 검색을 수행하여 8만큼 왼쪽으로 이동 한 관심 지수 (작은 n을 가진 O (log (n), 1 % 여야 함)를 찾고 4에서 값을 추출합니다. 바이트 물건.
std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;
uint8_t lookup(unsigned idx) {
// extract the 2 bits of our interest from the main array
uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
// usual (likely) case: value between 0 and 2
if(v != 3) return v;
// bad case: lookup the index<<8 in the secondary array
// lower_bound finds the first >=, so we don't need to mask out the value
auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
// some coherency checks
if(ptr == sec_arr.end()) std::abort();
if((*ptr >> 8) != idx) std::abort();
#endif
// extract our 8-bit value from the 32 bit (index, value) thingie
return (*ptr) & 0xff;
}
void populate(uint8_t *source, size_t size) {
main_arr.clear(); sec_arr.clear();
// size the main storage (round up)
main_arr.resize((size+3)/4);
for(size_t idx = 0; idx < size; ++idx) {
uint8_t in = source[idx];
uint8_t &target = main_arr[idx>>2];
// if the input doesn't fit, cap to 3 and put in secondary storage
if(in >= 3) {
// top 24 bits: index; low 8 bit: value
sec_arr.push_back((idx << 8) | in);
in = 3;
}
// store in the target according to the position
target |= in << ((idx & 3)*2);
}
}
제안한 것과 같은 배열의 경우 첫 번째 배열의 경우 10000000 / 4 = 2500000 바이트에 두 번째 배열의 경우 10000000 * 1 % * 4 B = 400000 바이트가 필요합니다. 따라서 2900000 바이트, 즉 원래 배열의 1/3 미만이며 가장 많이 사용 된 부분은 모두 메모리에 함께 보관되므로 캐싱에 적합해야합니다 (L3에 적합 할 수도 있음).
24 비트 이상의 주소 지정이 필요한 경우 "보조 저장소"를 조정해야합니다. 이것을 확장하는 간단한 방법은 256 요소 포인터 배열을 사용하여 인덱스의 상위 8 비트를 전환하고 위와 같이 24 비트 인덱스 정렬 배열로 전달하는 것입니다.
빠른 벤치 마크
#include <algorithm>
#include <vector>
#include <stdint.h>
#include <chrono>
#include <stdio.h>
#include <math.h>
using namespace std::chrono;
/// XorShift32 generator; extremely fast, 2^32-1 period, way better quality
/// than LCG but fail some test suites
struct XorShift32 {
/// This stuff allows to use this class wherever a library function
/// requires a UniformRandomBitGenerator (e.g. std::shuffle)
typedef uint32_t result_type;
static uint32_t min() { return 1; }
static uint32_t max() { return uint32_t(-1); }
/// PRNG state
uint32_t y;
/// Initializes with seed
XorShift32(uint32_t seed = 0) : y(seed) {
if(y == 0) y = 2463534242UL;
}
/// Returns a value in the range [1, 1<<32)
uint32_t operator()() {
y ^= (y<<13);
y ^= (y>>17);
y ^= (y<<15);
return y;
}
/// Returns a value in the range [0, limit); this conforms to the RandomFunc
/// requirements for std::random_shuffle
uint32_t operator()(uint32_t limit) {
return (*this)()%limit;
}
};
struct mean_variance {
double rmean = 0.;
double rvariance = 0.;
int count = 0;
void operator()(double x) {
++count;
double ormean = rmean;
rmean += (x-rmean)/count;
rvariance += (x-ormean)*(x-rmean);
}
double mean() const { return rmean; }
double variance() const { return rvariance/(count-1); }
double stddev() const { return std::sqrt(variance()); }
};
std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;
uint8_t lookup(unsigned idx) {
// extract the 2 bits of our interest from the main array
uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
// usual (likely) case: value between 0 and 2
if(v != 3) return v;
// bad case: lookup the index<<8 in the secondary array
// lower_bound finds the first >=, so we don't need to mask out the value
auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
// some coherency checks
if(ptr == sec_arr.end()) std::abort();
if((*ptr >> 8) != idx) std::abort();
#endif
// extract our 8-bit value from the 32 bit (index, value) thingie
return (*ptr) & 0xff;
}
void populate(uint8_t *source, size_t size) {
main_arr.clear(); sec_arr.clear();
// size the main storage (round up)
main_arr.resize((size+3)/4);
for(size_t idx = 0; idx < size; ++idx) {
uint8_t in = source[idx];
uint8_t &target = main_arr[idx>>2];
// if the input doesn't fit, cap to 3 and put in secondary storage
if(in >= 3) {
// top 24 bits: index; low 8 bit: value
sec_arr.push_back((idx << 8) | in);
in = 3;
}
// store in the target according to the position
target |= in << ((idx & 3)*2);
}
}
volatile unsigned out;
int main() {
XorShift32 xs;
std::vector<uint8_t> vec;
int size = 10000000;
for(int i = 0; i<size; ++i) {
uint32_t v = xs();
if(v < 1825361101) v = 0; // 42.5%
else if(v < 4080218931) v = 1; // 95.0%
else if(v < 4252017623) v = 2; // 99.0%
else {
while((v & 0xff) < 3) v = xs();
}
vec.push_back(v);
}
populate(vec.data(), vec.size());
mean_variance lk_t, arr_t;
for(int i = 0; i<50; ++i) {
{
unsigned o = 0;
auto beg = high_resolution_clock::now();
for(int i = 0; i < size; ++i) {
o += lookup(xs() % size);
}
out += o;
int dur = (high_resolution_clock::now()-beg)/microseconds(1);
fprintf(stderr, "lookup: %10d µs\n", dur);
lk_t(dur);
}
{
unsigned o = 0;
auto beg = high_resolution_clock::now();
for(int i = 0; i < size; ++i) {
o += vec[xs() % size];
}
out += o;
int dur = (high_resolution_clock::now()-beg)/microseconds(1);
fprintf(stderr, "array: %10d µs\n", dur);
arr_t(dur);
}
}
fprintf(stderr, " lookup | ± | array | ± | speedup\n");
printf("%7.0f | %4.0f | %7.0f | %4.0f | %0.2f\n",
lk_t.mean(), lk_t.stddev(),
arr_t.mean(), arr_t.stddev(),
arr_t.mean()/lk_t.mean());
return 0;
}
(코드와 데이터는 항상 내 Bitbucket에서 업데이트됩니다)
위의 코드는 게시물에 지정된 OP로 분산 된 임의의 데이터로 10M 요소 배열을 채우고 내 데이터 구조를 초기화 한 다음 :
- 내 데이터 구조로 10M 요소의 무작위 조회를 수행합니다.
- 원래 배열을 통해 동일하게 수행합니다.
(순차적 조회의 경우 배열은 항상 캐시에 친숙한 조회이므로 엄청나게 이깁니다.)
이 마지막 두 블록은 50 번 반복되고 시간이 정해집니다. 마지막으로 각 유형의 조회에 대한 평균 및 표준 편차가 속도 향상 (lookup_mean / array_mean)과 함께 계산 및 인쇄됩니다.
-O3 -static우분투 16.04에서 g ++ 5.4.0 ( 및 일부 경고)으로 위의 코드를 컴파일하고 일부 컴퓨터에서 실행했습니다. 그들 대부분은 우분투 16.04, 일부 오래된 리눅스, 일부 새로운 리눅스를 실행하고 있습니다. 이 경우 OS가 전혀 관련이 없다고 생각합니다.
CPU | cache | lookup (µs) | array (µs) | speedup (x)
Xeon E5-1650 v3 @ 3.50GHz | 15360 KB | 60011 ± 3667 | 29313 ± 2137 | 0.49
Xeon E5-2697 v3 @ 2.60GHz | 35840 KB | 66571 ± 7477 | 33197 ± 3619 | 0.50
Celeron G1610T @ 2.30GHz | 2048 KB | 172090 ± 629 | 162328 ± 326 | 0.94
Core i3-3220T @ 2.80GHz | 3072 KB | 111025 ± 5507 | 114415 ± 2528 | 1.03
Core i5-7200U @ 2.50GHz | 3072 KB | 92447 ± 1494 | 95249 ± 1134 | 1.03
Xeon X3430 @ 2.40GHz | 8192 KB | 111303 ± 936 | 127647 ± 1503 | 1.15
Core i7 920 @ 2.67GHz | 8192 KB | 123161 ± 35113 | 156068 ± 45355 | 1.27
Xeon X5650 @ 2.67GHz | 12288 KB | 106015 ± 5364 | 140335 ± 6739 | 1.32
Core i7 870 @ 2.93GHz | 8192 KB | 77986 ± 429 | 106040 ± 1043 | 1.36
Core i7-6700 @ 3.40GHz | 8192 KB | 47854 ± 573 | 66893 ± 1367 | 1.40
Core i3-4150 @ 3.50GHz | 3072 KB | 76162 ± 983 | 113265 ± 239 | 1.49
Xeon X5650 @ 2.67GHz | 12288 KB | 101384 ± 796 | 152720 ± 2440 | 1.51
Core i7-3770T @ 2.50GHz | 8192 KB | 69551 ± 1961 | 128929 ± 2631 | 1.85
결과는 ... 혼합입니다!
- 일반적으로 이러한 머신의 대부분에는 속도가 다소 떨어지거나 최소한 동등합니다.
- 어레이가 실제로 "스마트 구조"조회보다 우월한 두 가지 경우는 캐시가 많고 특히 사용량이 많지 않은 컴퓨터에 있습니다. 위의 Xeon E5-1650 (15MB 캐시)은 야간 유휴 상태입니다. Xeon E5-2697 (35MB 캐시)은 유휴 상태에서도 고성능 계산을위한 기계입니다. 원래 어레이는 거대한 캐시에 완전히 들어 맞기 때문에 컴팩트 한 데이터 구조는 복잡성을 증가시킵니다.
- "성능 스펙트럼"의 반대편에 있지만 어레이가 약간 더 빠를 경우 NAS에 전원을 공급하는 겸손한 Celeron이 있습니다. 캐시가 너무 적기 때문에 배열이나 "스마트 구조"가 전혀 맞지 않습니다. 캐시가 작은 다른 컴퓨터도 비슷한 성능을 발휘합니다.
- Xeon X5650은주의해서 사용해야합니다. 이들은 매우 바쁜 듀얼 소켓 가상 머신 서버의 가상 머신입니다. 명목상으로는 상당한 양의 캐시가 있지만 테스트 시간 동안 완전히 관련되지 않은 가상 머신에 의해 여러 번 선점됩니다.
다른 옵션은
- 결과가 0, 1 또는 2인지 확인
- 정기적 인 조회를하지 않으면
다른 말로하면 :
unsigned char lookup(int index) {
int code = (bmap[index>>2]>>(2*(index&3)))&3;
if (code != 3) return code;
return full_array[index];
}
여기서 bmap"other"를 의미하는 값 3을 갖는 요소 당 2 비트를 사용합니다.
이 구조는 업데이트하기가 쉽지 않으며 25 % 더 많은 메모리를 사용하지만 대부분의 경우 5 % 만 검색됩니다. 물론, 평소와 같이, 그것이 좋은 아이디어인지 아닌지는 다른 많은 조건에 의존하기 때문에 유일한 대답은 실제 사용법을 실험하는 것입니다.
이것은 구체적인 답변보다 "긴 의견"에 가깝습니다.
귀하의 데이터가 잘 알려진 것이 아닌 한, 나는 누군가가 귀하의 질문에 직접 대답 할 수 있을지 의심합니다 (그리고 귀하의 설명과 일치하는 것을 알지 못하지만 모든 종류의 데이터 패턴에 대해 모든 것을 모릅니다) 유스 케이스의 종류). 희소 데이터는 고성능 컴퓨팅에서 일반적인 문제이지만 일반적으로 "매우 큰 배열을 갖지만 일부 값은 0이 아닙니다"입니다.
내가 생각하는 것과 같은 잘 알려지지 않은 패턴의 경우, 아무도 더 나은 것을 직접 알 수 없으며 세부 사항에 따라 다릅니다. 임의의 액세스가 임의의 수-시스템이 데이터 항목의 클러스터에 액세스합니까? 균일 한 난수 생성기. 테이블 데이터가 완전히 임의적입니까, 다른 값의 산란과 함께 0의 시퀀스와 1의 시퀀스가 있습니까? 실행 길이 인코딩은 0과 1의 합리적으로 긴 시퀀스가 있으면 잘 작동하지만 "체커 보드가 0/1"이면 작동하지 않습니다. 또한 "시작점"테이블을 유지해야하므로 관련 장소로 합리적으로 빠르게 이동할 수 있습니다.
오랜 시간 동안 일부 큰 데이터베이스는 RAM의 큰 테이블 (이 예에서는 전화 교환 가입자 데이터) 일 뿐이며 프로세서의 캐시 및 페이지 테이블 최적화는 쓸모가 없다는 문제 중 하나입니다. 발신자는 최근에 누군가를 호출 한 사람과 거의 같지 않으므로 사전로드 된 데이터가 없으며 순전히 무작위입니다. 큰 페이지 테이블은 해당 유형의 액세스에 가장 적합한 최적화입니다.
많은 경우에있어서, "속도와 작은 크기"사이의 타협은 소프트웨어 엔지니어링에서 선택해야하는 것 중 하나입니다 (다른 엔지니어링에서는 반드시 그렇게 타협 할 필요는 없습니다). 따라서 "더 간단한 코드를위한 메모리 낭비"가 선호되는 경우가 많습니다. 이런 의미에서 "간단한"솔루션은 속도면에서 훨씬 우수하지만, RAM에 "더 나은"사용을하는 경우 테이블 크기를 최적화하면 충분한 성능과 크기를 개선 할 수 있습니다. 주석에서 제안한 것처럼 2 ~ 3 개의 가장 일반적인 값이 저장되는 2 비트 필드와 다른 값에 대한 대체 데이터 형식-해시 테이블은 내 방법이 될 수 있습니다. 첫 번째 방법이지만 목록 또는 이진 트리도 다시 작동 할 수 있습니다. "0, 1 또는 2가 아닌"의 패턴에 따라 다릅니다. 다시, 그것은 테이블에서 값이 어떻게 흩어져 있는지에 달려 있습니다-그것들은 클러스터에 있습니까, 아니면 더 고르게 분포 된 패턴입니까?
그러나 문제는 여전히 RAM에서 데이터를 읽는다는 것입니다. 그런 다음 "이것은 일반적인 값이 아닙니다"에 대처하기 위해 일부 코드를 포함하여 데이터 처리에 더 많은 코드를 소비하고 있습니다.
가장 일반적인 압축 알고리즘의 문제점은 언 패킹 시퀀스를 기반으로하므로 임의로 액세스 할 수 없다는 것입니다. 그리고 빅 데이터를 한 번에 256 개의 항목으로 분할하고 256을 uint8_t 배열로 압축 해제하고 원하는 데이터를 가져온 다음 압축되지 않은 데이터를 버리는 오버 헤드는 좋은 결과를 내지 못할 것입니다. 물론 성능이 중요하다고 가정합니다.
결국, 당신은 아마도 테스트하기 위해 주석 / 응답에 하나 또는 몇 가지 아이디어를 구현해야 할 것입니다.
내가 과거에 한 일은 비트 세트 앞에서 해시 맵을 사용하는 것 입니다.
이것은 Matteo의 답변에 비해 공간을 절반으로 줄이지 만 "예외"조회가 느리면 (즉, 많은 예외가있는 경우) 느려질 수 있습니다.
그러나 종종 "캐시는 왕이다".
데이터에 패턴이 없다면 합리적인 속도 나 크기 최적화가있을 가능성이 적습니다. 일반적인 컴퓨터를 대상으로 가정 할 경우 10MB가 그렇게 큰 문제는 아닙니다.
귀하의 질문에는 두 가지 가정이 있습니다.
- 모든 비트를 사용하지 않기 때문에 데이터가 제대로 저장되지 않습니다
- 더 잘 저장하면 일이 더 빨라집니다.
나는이 두 가지 가정이 모두 틀렸다고 생각합니다. 대부분의 경우 데이터를 저장하는 적절한 방법은 가장 자연스러운 표현을 저장하는 것입니다. 귀하의 경우, 이것은 당신이 간 것입니다 : 0에서 255 사이의 숫자 바이트. 다른 표현은 더 복잡 할 것입니다. 이 일반적인 원칙에서 벗어나려면 데이터의 95 %에서 잠재적으로 6 개의 "폐기"비트보다 강력한 이유가 필요합니다.
두 번째 가정의 경우, 어레이 크기를 변경하여 캐시 누락이 실질적으로 줄어드는 경우에만 해당됩니다. 이것이 일어날 지 여부는 작업 코드를 프로파일 링하여 결정적으로 만 결정할 수 있지만 실질적인 차이는 거의 없을 것입니다. 두 경우 모두 어레이에 무작위로 액세스하기 때문에 프로세서는 캐시 할 데이터 비트를 알고 두 경우 모두 유지하려고 애를 씁니다.
데이터와 액세스가 균일하게 무작위로 분배되는 경우 성능은 아마도 외부 액세스 캐시 누락을 피하는 액세스 비율에 따라 달라질 수 있습니다. 이를 최적화하려면 캐시에 어떤 크기의 어레이를 안정적으로 수용 할 수 있는지 알아야합니다. 캐시가 5 개의 셀마다 1 바이트를 수용 할만큼 충분히 큰 경우 가장 간단한 방법은 1 바이트가 0-2 범위의 5 개의 기본 3 인코딩 값을 보유하도록하는 것입니다 (5 개의 값의 243 조합이 있으므로 기본 -3 값이 "2"를 나타낼 때마다 쿼리되는 10,000,000 바이트 배열과 함께 바이트에 맞추기).
캐시가 크지 않지만 8 셀 당 1 바이트를 수용 할 수 있다면 1 바이트 값을 사용하여 8 개의 기본 3 값의 6,561 개의 가능한 조합 중에서 선택할 수는 없지만 유일한 효과는 0 또는 1을 2로 변경하면 불필요하게 조회가 발생하고 정확성을 위해 6,561을 모두 지원할 필요는 없습니다. 대신 256 개의 "유용한"값에 집중할 수 있습니다.
특히 0이 1보다 흔하거나 그 반대 일 경우, 217 개의 값을 사용하여 5 이하의 1을 포함하는 0과 1의 조합을 인코딩하고 16 개의 값은 xxxx0000부터 xxxx1111까지, 16은 0000xxxx부터 1111xxxx 및 하나는 xxxxxxxx입니다. 다른 용도로는 4 가지 값이 남아 있습니다. 설명 된대로 데이터가 무작위로 분포 된 경우 모든 쿼리의 거의 대부분이 0과 1을 포함하는 바이트에 도달합니다 (8 개 그룹의 모든 그룹 중 약 2/3에서 모든 비트는 0과 1, 약 7/8). 그것들은 6 비트 이하의 1 비트를 가질 것이다); 4 개의 x를 포함하는 바이트에 착륙하지 않았고 50 %의 확률로 0 또는 1에 착륙 할 가능성이 큰 사람들. 따라서 4 개의 쿼리 중 약 1 개만 큰 배열 조회가 필요합니다.
데이터가 무작위로 분배되었지만 캐시가 8 개 요소 당 1 바이트를 처리하기에 충분히 크지 않은 경우, 8 개 이상의 항목을 처리하는 각 바이트에이 방법을 사용할 수 있지만 0 또는 1에 대한 강한 편향이없는 한 큰 배열에서 조회를 수행하지 않고 처리 할 수있는 값의 비율은 각 바이트에서 처리하는 수가 증가함에 따라 줄어 듭니다.
그의 말이 약간 혼란 스러울 수 있기 때문에 @ o11c 의 답변에 추가 할 것 입니다. 마지막 비트와 CPU 사이클을 짜야하는 경우 다음을 수행하십시오.
우리는 5 % "다른 것"사례를 보유한 균형 잡힌 이진 검색 트리를 구성하는 것으로 시작합니다 . 모든 검색에 대해 트리를 빠르게 탐색합니다. 10000000 개의 요소가 있습니다. 5 %는 트리에 있습니다. 따라서 트리 데이터 구조에는 500000 개의 요소가 있습니다. 이것을 O (log (n)) 시간 안에 걸 으면 19 회 반복됩니다. 나는 이것에 전문가가 아니지만 메모리 효율적인 구현이 있다고 생각합니다. 추측하자 :
- 균형 트리, 하위 트리 위치를 계산할 수 있습니다 (표시는 트리의 노드에 저장할 필요가 없습니다). 힙 (데이터 구조)이 선형 메모리에 저장되는 것과 같은 방식입니다.
- 1 바이트 값 (2 ~ 255)
- 인덱스의 3 바이트 (10000000은 23 비트, 3 바이트에 해당)
총계, 4 바이트 : 500000 * 4 = 1953kB 캐시에 맞습니다!
다른 모든 경우 (0 또는 1)의 경우 비트 벡터를 사용할 수 있습니다. 랜덤 액세스의 경우 5 % 다른 경우는 1.19MB로 지정할 수 없습니다.
이 두 가지 조합은 약 3,099MB를 사용합니다. 이 기술을 사용하면 3.08의 메모리를 절약 할 수 있습니다.
그러나 이것은 불행한 @Matteo Italia (2.76 MB 사용) 의 대답을 능가하지 않습니다 . 추가로 할 수있는 일이 있습니까? 가장 많은 메모리를 소비하는 부분은 트리에서 3 바이트의 인덱스입니다. 이 값을 2로 줄이면 488kB를 절약 할 수 있으며 총 메모리 사용량은 2.622MB입니다.
우리는 이것을 어떻게합니까? 인덱싱을 2 바이트로 줄여야합니다. 다시 10000000은 23 비트를 사용합니다. 7 비트를 떨어 뜨릴 수 있어야합니다. 10000000 요소 범위를 78125 요소의 2 ^ 7 (= 128) 영역으로 분할하여 간단히 수행 할 수 있습니다. 이제 각 지역마다 평균 3906 개의 요소가있는 균형 잡힌 트리를 만들 수 있습니다. 올바른 트리를 선택하는 것은 대상 인덱스를 2 ^ 7 (또는 bitshift >> 7) 로 간단히 나눔으로써 수행 됩니다. 이제 저장에 필요한 인덱스는 나머지 16 비트로 표현할 수 있습니다. 저장해야하는 트리 길이에 약간의 오버 헤드가 있지만, 이는 무시할 수 있습니다. 또한이 분할 메커니즘은 트리를 걷는 데 필요한 반복 횟수를 줄입니다. 이제 7 비트가 떨어지기 때문에 이제 7 반복 횟수가 줄어 듭니다 .12 반복 만 남았습니다.
이론적으로 다음 8 비트를 차단하기 위해 프로세스를 반복 할 수 있지만 평균 ~ 305 개의 요소로 2 ^ 15 개의 균형 잡힌 트리를 만들어야합니다. 이로 인해 2.143MB가 발생하여 트리를 걸을 때 단 4 번의 반복 만 수행하며, 이는 처음 시작한 19 개의 반복에 비해 상당히 빠른 속도입니다.
마지막 결론으로, 이것은 약간의 메모리 사용으로 2 비트 벡터 전략을 능가하지만 구현하기가 완전히 어려워집니다. 그러나 캐시를 맞추는 것 사이에 차이를 만들 수 있다면 시도해 볼 가치가 있습니다.
읽기 작업 만 수행하는 경우 단일 인덱스에 값을 할당하는 것이 아니라 인덱스 간격에 값을 할당하는 것이 좋습니다.
예를 들면 다음과 같습니다.
[0, 15000] = 0
[15001, 15002] = 153
[15003, 26876] = 2
[25677, 31578] = 0
...
이것은 구조체로 수행 할 수 있습니다. OO 접근 방식이 마음에 들면 이와 비슷한 클래스를 정의 할 수도 있습니다.
class Interval{
private:
uint32_t start; // First element of interval
uint32_t end; // Last element of interval
uint8_t value; // Assigned value
public:
Interval(uint32_t start, uint32_t end, uint8_t value);
bool isInInterval(uint32_t item); // Checks if item lies within interval
uint8_t getValue(); // Returns the assigned value
}
Now you just have to iterate trough a list of intervals and check if your index lies within one of them which can be much less memory intensive in average but costs more CPU resources.
Interval intervals[INTERVAL_COUNT];
intervals[0] = Interval(0, 15000, 0);
intervals[1] = Interval(15001, 15002, 153);
intervals[2] = Interval(15003, 26876, 2);
intervals[3] = Interval(25677, 31578, 0);
...
uint8_t checkIntervals(uint32_t item)
for(int i=0; i<INTERVAL_COUNT-1; i++)
{
if(intervals[i].isInInterval(item) == true)
{
return intervals[i].getValue();
}
}
return DEFAULT_VALUE;
}
If you order the intervals by descending size you increase the probability that the item you are looking for is found early which further decreases your average memory and CPU resource usage.
You could also remove all intervals with a size of 1. Put the corresponding values into a map and check them only if the item you are looking for wasn't found in the intervals. This should also raise the average performance a bit.
Long long time ago, I can just remember...
In university we got a task to accelerate a ray tracer program, that has to read by algorithm over and over again from buffer arrays. A friend told me to always use RAM-reads that are multiples of 4Bytes. So I changed the array from a pattern of [x1,y1,z1,x2,y2,z2,...,xn,yn,zn] to a pattern of [x1,y1,z1,0,x2,y2,z2,0,...,xn,yn,zn,0]. Means I add a empty field after each 3D coordinate. After some performance testing: It was faster. So long story short: Read multiple of 4 Bytes from your array from RAM, and maybe also from the right starting position, so you read a little cluster where the searched index is in it and read the searched index from this little cluster in cpu. (In your case you will not need to inserting fill-fields, but the concept should be clear)
Maybe also other multiples could be the key in newer systems.
I don't know if this will work in your case, so if it doesn't work: Sorry. If it work I would be happy to hear about some test results.
PS: Oh and if there is any access pattern or nearby accessed indices, you can reuse the cached cluster.
PPS: It could be, that the multiple factor was more like 16Bytes or something like that, it's too long ago, that I can remember exactly.
Looking at this, you could split your data, for example:
- a bitset which gets indexed and represents the value 0 (std::vector would be useful here)
- a bitset which gets indexed and represents the value 1
- a std::vector for the values of 2, containing the indexes which refer to this value
- a map for the other values (or std::vector>)
In this case, all values appear till a given index, so you could even remove one of bitsets and represents the value as it being missing in the other ones.
This will save you some memory for this case, though would make the worst case worse. You'll also need more CPU power to do the lookups.
Make sure to measure!
Like Mats mentions in his comment-answer, it is hard to say what is actually the best solution without knowing specifically what kind of data you have (e.g., are there long runs of 0's, and so on), and what your access pattern looks like (does "random" mean "all over the place" or just "not strictly in completely linear fashion" or "every value exactly once, just randomized" or ...).
That said, there are two mechanisms coming to mind:
- Bit arrays; i.e., if you only had two values, you could trivially compress your array by a factor of 8; if you have 4 values (or "3 values + everything else") you can compress by a factor of two. Which might just not be worth the trouble and would need benchmarks, especially if you have really random access patterns which escape your caches and hence do not change the access time at all.
(index,value)or(value,index)tables. I.e., have one very small table for the 1% case, maybe one table for the 5% case (which only needs to store the indexes as all have the same value), and a big compressed bit array for the final two cases. And with "table" I mean something which allows relatively quick lookup; i.e., maybe a hash, a binary tree, and so on, depending on what you have available and your actual needs. If these subtables fit into your 1st/2nd level caches, you might get lucky.
I am not very familiar with C, but in C++ you can use unsigned char to represent an integer in the range 0 - 255.
Compared to normal int (again, I am coming from Java and C++ world) in which 4 byte (32 bit) are required, an unsigned char requires 1 byte (8 bits). so it might reduce the total size of the array by 75%.
You have succinctly described all the distribution characteristics of your array; toss the array.
You can easily replace the array with a randomized method that produces the same probabilistic output as the array.
If consistency matters (producing the same value for the same random index), consider using a bloom filter and/or hash map to track repeat hits. If your array accesses really are random, though, this is totally unnecessary.
'development' 카테고리의 다른 글
| CMD.EXE (Windows Command Interpreter)는 스크립트를 어떻게 구문 분석합니까? (0) | 2020.06.30 |
|---|---|
| jQuery Data () API를 사용하여 데이터 속성을 설정할 수 없습니다 (0) | 2020.06.30 |
| PowerShell : 스크립트 디렉토리에서 명령 실행 (0) | 2020.06.29 |
| 동일한 시스템 내에서 다른 프로젝트에 대해 여러 사용자 이름을 git [duplicate] (0) | 2020.06.29 |
| Django로 '대량 업데이트'하는 방법은 무엇입니까? (0) | 2020.06.29 |