32 비트 정수가 오버플로되면 64 비트 길이 대신 40 비트 구조를 사용할 수 있습니까?
예를 들어 32 비트 정수가으로 업그레이드 int하는 대신 오버플로되는 long경우 2 40 이내의 범위 만 필요하면 40 비트 유형을 사용할 수 있으므로 모든 항목에 대해 24 (64-40) 비트를 절약 할 수 있습니다. 정수?
그렇다면 어떻게?
수십억 달러를 처리해야하고 공간이 더 큰 제약입니다.
네,하지만...
확실히 가능 하지만 일반적 으로이 숫자를 수십억 개 를 사용하지 않는 프로그램의 경우 말도 안됩니다 .
#include <stdint.h> // don't want to rely on something like long long
struct bad_idea
{
uint64_t var : 40;
};
여기서는
훨씬
덜 효율적인 코드가 생성 var되는 대신 40 비트의 너비를 갖게
됩니다 ( "많은"가 매우 잘못된 것으로 밝혀졌습니다. 측정 된 오버 헤드는 단 1-2 %에 불과합니다. 아래 타이밍 참조). 일반적으로 소용이 없습니다. 동일한 구조로 압축하려는 다른 24 비트 값 (또는 8 비트 및 16 비트 값)이 필요하지 않은 경우 정렬은 얻을 수있는 모든 것을 상실합니다.
어쨌든 수십억 개의 메모리가 없으면 메모리 소비의 효과적인 차이는 눈에 띄지 않을 것입니다 (하지만 비트 필드를 관리하는 데 필요한 추가 코드는 눈에 띄게됩니다!).
참고 :
이 질문은 실제로 수십억 개의 숫자가 필요하다는 것을 반영하기 위해 업데이트되었습니다 . 따라서 구조 정렬 및 패딩으로 인해 이득을 잃지 않도록 조치를 취했다고 가정하면 실행 가능한 일이 될 수 있습니다. 나머지 24 비트에 다른 것을 저장하거나 40 비트 값을 8 개 또는 그 배수의 구조로 저장하여).
3 바이트 를 10 억 번 절약 하는 것은 눈에 띄게 적은 메모리 페이지를 필요로하므로 캐시 및 TLB 누락이 줄어들고 모든 페이지 오류 (수천만 명령에 가중치가 부여 된 단일 페이지 오류)가 발생하므로 가치가 있습니다.
위의 스 니펫은 나머지 24 비트를 사용하지 않지만 (단순히 "40 비트 사용"부분을 보여줍니다), 메모리 보존 측면에서이 접근 방식을 실제로 유용하게 만들려면 다음과 유사한 것이 필요합니다. 실제로 구멍에 넣을 다른 "유용한"데이터가 있습니다.
struct using_gaps
{
uint64_t var : 40;
uint64_t useful_uint16 : 16;
uint64_t char_or_bool : 8;
};
구조 크기와 정렬은 64 비트 정수와 같으므로 10 억 개의 그러한 구조의 배열을 만들면 아무 것도 낭비되지 않습니다 (컴파일러 별 확장을 사용하지 않더라도). 8 비트 값을 사용하지 않는 경우 48 비트 및 16 비트 값을 사용할 수도 있습니다 (더 큰 오버플로 마진 제공).
또는 유용성을 희생하면서 8 개의 40 비트 값을 구조체에 넣을 수 있습니다 (40과 64의 최소 공배수는 320 = 8 * 40 임). 물론 구조 배열의 요소에 액세스하는 코드는 훨씬 더 복잡해질 것입니다 ( operator[]선형 배열 기능을 복원하고 구조 복잡성을 숨기는를 구현할 수도 있지만 ).
업데이트 :
비트 필드 (및 비트 필드 참조로 오버로딩하는 연산자)에 어떤 오버 헤드가 있는지 확인하기 위해 빠른 테스트 스위트를 작성했습니다. gcc.godbolt.org에 게시 된 코드 (길이로 인해) , 내 Win7-64 시스템의 테스트 출력은 다음과 같습니다.
Running test for array size = 1048576
what alloc seq(w) seq(r) rand(w) rand(r) free
-----------------------------------------------------------
uint32_t 0 2 1 35 35 1
uint64_t 0 3 3 35 35 1
bad40_t 0 5 3 35 35 1
packed40_t 0 7 4 48 49 1
Running test for array size = 16777216
what alloc seq(w) seq(r) rand(w) rand(r) free
-----------------------------------------------------------
uint32_t 0 38 14 560 555 8
uint64_t 0 81 22 565 554 17
bad40_t 0 85 25 565 561 16
packed40_t 0 151 75 765 774 16
Running test for array size = 134217728
what alloc seq(w) seq(r) rand(w) rand(r) free
-----------------------------------------------------------
uint32_t 0 312 100 4480 4441 65
uint64_t 0 648 172 4482 4490 130
bad40_t 0 682 193 4573 4492 130
packed40_t 0 1164 552 6181 6176 130
사람이 볼 수있는 것은 비트 필드의 추가 오버 헤드는 무시할 수 있지만 편의상 비트 필드 참조로 오버로드하는 연산자는 캐시 친화적 인 방식으로 데이터에 선형으로 액세스 할 때 다소 과감합니다 (약 3 배 증가). 반면 랜덤 액세스에서는 거의 중요하지 않습니다.
이러한 타이밍은 단순히 64 비트 정수를 사용하는 것이 전체적으로 비트 필드보다 더 빠르기 때문에 (더 많은 메모리를 건드려도) 더 좋을 것임을 시사하지만, 물론 훨씬 더 큰 데이터 세트의 페이지 오류 비용을 고려하지 않습니다. 실제 RAM이 부족하면 매우 다르게 보일 수 있습니다 (테스트하지 않았습니다).
다음과 같이 4 * 40 비트 정수를 160 비트 구조체로 매우 효과적으로 압축 할 수 있습니다.
struct Val4 {
char hi[4];
unsigned int low[4];
}
long getLong( const Val4 &pack, int ix ) {
int hi= pack.hi[ix]; // preserve sign into 32 bit
return long( (((unsigned long)hi) << 32) + (unsigned long)pack.low[i]);
}
void setLong( Val4 &pack, int ix, long val ) {
pack.low[ix]= (unsigned)val;
pack.hi[ix]= (char)(val>>32);
}
이것들은 다시 다음과 같이 사용할 수 있습니다.
Val4[SIZE] vals;
long getLong( int ix ) {
return getLong( vals[ix>>2], ix&0x3 )
}
void setLong( int ix, long val ) {
setLong( vals[ix>>2], ix&0x3, val )
}
VLE (Variable-Lenght Encoding)를 고려할 수 있습니다.
아마도 많은 숫자를 어딘가에 (RAM, 디스크, 네트워크를 통해 전송하는 등) 저장 한 다음 하나씩 가져 와서 일부 처리를 수행했을 것입니다.
한 가지 접근 방식은 VLE를 사용하여 인코딩하는 것입니다. Google의 protobuf 문서 (CreativeCommons 라이선스)에서
Varint는 하나 이상의 바이트를 사용하여 정수를 직렬화하는 방법입니다. 숫자가 작을수록 바이트 수가 적습니다.
마지막 바이트를 제외하고 varint의 각 바이트에는 최상위 비트 (msb)가 설정되어 있습니다. 이는 앞으로 올 바이트가 더 있음을 나타냅니다. 각 바이트의 하위 7 비트는 숫자의 2의 보수 표현을 7 비트 그룹, 최하위 그룹 먼저 저장하는 데 사용됩니다.
예를 들어 여기에 숫자 1이 있습니다. 단일 바이트이므로 msb가 설정되지 않았습니다.
0000 0001여기 300 개가 있습니다. 이것은 좀 더 복잡합니다.
1010 1100 0000 0010이것이 300이라는 것을 어떻게 알 수 있습니까? 먼저 각 바이트에서 msb를 삭제합니다. 이것은 숫자의 끝에 도달했는지 여부를 알려주기위한 것입니다.
장점
- 작은 숫자가 많으면 평균적으로 정 수당 40 바이트 미만을 사용합니다. 아마도 훨씬 적습니다.
- 작은 숫자에 대한 벌금을 지불하지 않고 앞으로 더 큰 숫자 (40 비트 이상)를 저장할 수 있습니다.
단점
- 숫자의 7 개 중요한 비트마다 추가 비트를 지불합니다. 즉, 40 개의 유효 비트를 가진 숫자에는 6 바이트가 필요합니다. 대부분의 숫자에 40 개의 유효 비트가있는 경우 비트 필드 접근 방식이 더 좋습니다.
- 인덱스가 주어진 숫자로 쉽게 이동할 수있는 기능을 잃게됩니다 (현재 항목에 액세스하려면 배열의 모든 이전 요소를 적어도 부분적으로 구문 분석해야합니다.
- 숫자로 유용한 작업을 수행하기 전에 어떤 형식의 디코딩이 필요합니다 (비트 필드와 같은 다른 접근 방식에서도 마찬가지 임).
(편집 : 우선-원하는 것이 가능하고 경우에 따라 의미가 있습니다 .Netflix 챌린지를 위해 무언가를 시도했을 때 비슷한 일을해야했고 메모리가 1GB 밖에 없었습니다. 두 번째-아마도 가장 좋습니다. 정렬 문제와 구조체 패킹 pragma를 엉망으로 만들 필요가 없도록 40 비트 저장소에 char 배열을 사용합니다. 셋째-이 디자인은 중간 결과에 대해 64 비트 산술을 사용해도 괜찮다고 가정합니다. Int40을 사용할 어레이 스토리지; 넷째 : 이것이 나쁜 생각이라는 모든 제안을 얻지는 못합니다. 사람들이 메시 데이터 구조를 포장하기 위해 어떤 과정을 거치는 지 읽어 보면 비교하면 어린이 놀이처럼 보입니다).
원하는 것은 데이터를 40 비트 정수로 저장하는 데만 사용되지만 산술을 위해 암시 적으로 int64_t로 변환하는 구조체입니다. 유일한 트릭은 부호 확장을 40 비트에서 64 비트로 올바르게하는 것입니다. unsigned int로 괜찮다면 코드는 더 간단 할 수 있습니다. 이렇게하면 시작할 수 있습니다.
#include <cstdint>
#include <iostream>
// Only intended for storage, automatically promotes to 64-bit for evaluation
struct Int40
{
Int40(int64_t x) { set(static_cast<uint64_t>(x)); } // implicit constructor
operator int64_t() const { return get(); } // implicit conversion to 64-bit
private:
void set(uint64_t x)
{
setb<0>(x); setb<1>(x); setb<2>(x); setb<3>(x); setb<4>(x);
};
int64_t get() const
{
return static_cast<int64_t>(getb<0>() | getb<1>() | getb<2>() | getb<3>() | getb<4>() | signx());
};
uint64_t signx() const
{
return (data[4] >> 7) * (uint64_t(((1 << 25) - 1)) << 39);
};
template <int idx> uint64_t getb() const
{
return static_cast<uint64_t>(data[idx]) << (8 * idx);
}
template <int idx> void setb(uint64_t x)
{
data[idx] = (x >> (8 * idx)) & 0xFF;
}
unsigned char data[5];
};
int main()
{
Int40 a = -1;
Int40 b = -2;
Int40 c = 1 << 16;
std::cout << "sizeof(Int40) = " << sizeof(Int40) << std::endl;
std::cout << a << "+" << b << "=" << (a+b) << std::endl;
std::cout << c << "*" << c << "=" << (c*c) << std::endl;
}
라이브로 시도 할 수있는 링크는 다음과 같습니다. http://rextester.com/QWKQU25252
비트 필드 구조를 사용할 수 있지만 메모리를 절약하지는 못합니다.
struct my_struct
{
unsigned long long a : 40;
unsigned long long b : 24;
};
이러한 40 비트 변수 8 개를 하나의 구조로 압축 할 수 있습니다.
struct bits_16_16_8
{
unsigned short x : 16;
unsigned short y : 16;
unsigned short z : 8;
};
struct bits_8_16_16
{
unsigned short x : 8;
unsigned short y : 16;
unsigned short z : 16;
};
struct my_struct
{
struct bits_16_16_8 a1;
struct bits_8_16_16 a2;
struct bits_16_16_8 a3;
struct bits_8_16_16 a4;
struct bits_16_16_8 a5;
struct bits_8_16_16 a6;
struct bits_16_16_8 a7;
struct bits_8_16_16 a8;
};
이렇게하면 (8 개의 "표준"64 비트 변수를 사용하는 것과 비교하여) 약간의 메모리가 절약되지만 이러한 각 변수에 대한 모든 연산 (특히 산술 연산)을 여러 연산으로 분할해야합니다.
따라서 메모리 최적화는 런타임 성능을 위해 "거래"됩니다.
의견에서 알 수 있듯이 이것은 상당한 작업입니다.
많은 RAM을 저장 하지 않는 한 아마도 불필요한 번거 로움 이 될 것입니다. 그러면 훨씬 더 의미가 있습니다. (RAM 절약은 RAM에 저장된 수백만 개의 long값에서 절약 된 총 비트 수입니다. )
5 바이트 / 문자 (5 * 8 비트 = 40 비트)의 배열을 사용하는 것이 좋습니다. 그런 다음 (오버플로 된 int-따라서 a long) 값에서 바이트 배열로 비트를 이동하여 저장해야합니다.
값을 사용하려면 비트를 다시 a로 이동하면 값을 사용할 long수 있습니다.
그러면 RAM과 값의 파일 저장소가 40 비트 (5 바이트)가됩니다. 그러나 a struct를 사용 하여 5 바이트를 유지하려면 데이터 정렬을 고려해야 합니다. 이 비트 이동 및 데이터 정렬 의미에 대해 자세히 설명해야하는지 알려주세요.
마찬가지로 64 비트 사용할 수 있습니다 long, 그리고 숨기기 당신이 사용하지 않는 나머지 24 비트에 다른 값을 (3 개 문자 아마도). 다시-비트 이동을 사용하여 24 비트 값을 추가하고 제거합니다.
도움이 될 수있는 또 다른 변형은 구조를 사용하는 것입니다.
typedef struct TRIPLE_40 {
uint32_t low[3];
uint8_t hi[3];
uint8_t padding;
};
이러한 구조는 16 바이트를 차지하고 16 바이트로 정렬되면 단일 캐시 라인에 완전히 맞습니다. 구조의 어느 부분을 사용할 것인지 식별하는 것이 구조가 3 개가 아닌 4 개의 요소를 보유하는 경우보다 더 비쌀 수 있지만, 하나의 캐시 라인에 액세스하는 것이 2 개에 액세스하는 것보다 훨씬 저렴할 수 있습니다. 성능이 중요한 경우 일부 시스템은 divmod-3 작업을 저렴하게 수행하고 캐시 라인 가져 오기 당 비용이 높은 반면 다른 시스템은 더 저렴한 메모리 액세스와 더 비싼 divmod-3를 가질 수 있으므로 일부 벤치 마크를 사용해야합니다.
나는 그것을 가정 할 것이다
- 이것은 C이고
- 하나의 큰 40 비트 숫자 배열이 필요합니다.
- 당신은 리틀 엔디안 머신에 있고
- 귀하의 기계는 정렬을 처리 할 수있을만큼 똑똑합니다.
- 필요한 40 비트 숫자의 수로 크기를 정의했습니다.
unsigned char hugearray[5*size+3]; // +3 avoids overfetch of last element
__int64 get_huge(unsigned index)
{
__int64 t;
t = *(__int64 *)(&hugearray[index*5]);
if (t & 0x0000008000000000LL)
t |= 0xffffff0000000000LL;
else
t &= 0x000000ffffffffffLL;
return t;
}
void set_huge(unsigned index, __int64 value)
{
unsigned char *p = &hugearray[index*5];
*(long *)p = value;
p[4] = (value >> 32);
}
두 교대로 겟을 처리하는 것이 더 빠를 수 있습니다.
__int64 get_huge(unsigned index)
{
return (((*(__int64 *)(&hugearray[index*5])) << 24) >> 24);
}
수십억 개의 40 비트 부호있는 정수를 저장하고 8 비트 바이트를 가정하는 경우 8 개의 40 비트 부호있는 정수를 구조체에 패킹 할 수 있습니다 (아래 코드에서는이를 수행하기 위해 바이트 배열을 사용함). 이 구조체는 일반적으로 정렬되어 있으므로 이러한 패킹 된 그룹의 논리적 배열을 만들고 그에 대한 일반적인 순차적 인덱싱을 제공 할 수 있습니다.
#include <limits.h> // CHAR_BIT
#include <stdint.h> // int64_t
#include <stdlib.h> // div, div_t, ptrdiff_t
#include <vector> // std::vector
#define STATIC_ASSERT( e ) static_assert( e, #e )
namespace cppx {
using Byte = unsigned char;
using Index = ptrdiff_t;
using Size = Index;
// For non-negative values:
auto roundup_div( const int64_t a, const int64_t b )
-> int64_t
{ return (a + b - 1)/b; }
} // namespace cppx
namespace int40 {
using cppx::Byte;
using cppx::Index;
using cppx::Size;
using cppx::roundup_div;
using std::vector;
STATIC_ASSERT( CHAR_BIT == 8 );
STATIC_ASSERT( sizeof( int64_t ) == 8 );
const int bits_per_value = 40;
const int bytes_per_value = bits_per_value/8;
struct Packed_values
{
enum{ n = sizeof( int64_t ) };
Byte bytes[n*bytes_per_value];
auto value( const int i ) const
-> int64_t
{
int64_t result = 0;
for( int j = bytes_per_value - 1; j >= 0; --j )
{
result = (result << 8) | bytes[i*bytes_per_value + j];
}
const int64_t first_negative = int64_t( 1 ) << (bits_per_value - 1);
if( result >= first_negative )
{
result = (int64_t( -1 ) << bits_per_value) | result;
}
return result;
}
void set_value( const int i, int64_t value )
{
for( int j = 0; j < bytes_per_value; ++j )
{
bytes[i*bytes_per_value + j] = value & 0xFF;
value >>= 8;
}
}
};
STATIC_ASSERT( sizeof( Packed_values ) == bytes_per_value*Packed_values::n );
class Packed_vector
{
private:
Size size_;
vector<Packed_values> data_;
public:
auto size() const -> Size { return size_; }
auto value( const Index i ) const
-> int64_t
{
const auto where = div( i, Packed_values::n );
return data_[where.quot].value( where.rem );
}
void set_value( const Index i, const int64_t value )
{
const auto where = div( i, Packed_values::n );
data_[where.quot].set_value( where.rem, value );
}
Packed_vector( const Size size )
: size_( size )
, data_( roundup_div( size, Packed_values::n ) )
{}
};
} // namespace int40
#include <iostream>
auto main() -> int
{
using namespace std;
cout << "Size of struct is " << sizeof( int40::Packed_values ) << endl;
int40::Packed_vector values( 25 );
for( int i = 0; i < values.size(); ++i )
{
values.set_value( i, i - 10 );
}
for( int i = 0; i < values.size(); ++i )
{
cout << values.value( i ) << " ";
}
cout << endl;
}
수십억 개의 정수를 처리해야한다면 단일 40 비트 숫자 대신 40 비트 숫자 배열 을 캡슐화하려고 합니다. 이렇게하면 나머지 코드를 변경하지 않고도 다양한 배열 구현 (예 : 데이터를 즉시 압축하는 구현 또는 덜 사용되는 데이터를 디스크에 저장하는 구현)을 테스트 할 수 있습니다.
다음은 샘플 구현입니다 ( http://rextester.com/SVITH57679 ).
class Int64Array
{
char* buffer;
public:
static const int BYTE_PER_ITEM = 5;
Int64Array(size_t s)
{
buffer=(char*)malloc(s*BYTE_PER_ITEM);
}
~Int64Array()
{
free(buffer);
}
class Item
{
char* dataPtr;
public:
Item(char* dataPtr) : dataPtr(dataPtr){}
inline operator int64_t()
{
int64_t value=0;
memcpy(&value, dataPtr, BYTE_PER_ITEM); // Assumes little endian byte order!
return value;
}
inline Item& operator = (int64_t value)
{
memcpy(dataPtr, &value, BYTE_PER_ITEM); // Assumes little endian byte order!
return *this;
}
};
inline Item operator[](size_t index)
{
return Item(buffer+index*BYTE_PER_ITEM);
}
};
참고 : memcpy40 비트에서 64 비트로 의 -conversion은 litte-endianness를 가정하므로 기본적으로 정의되지 않은 동작입니다. 하지만 x86 플랫폼에서 작동합니다.
참고 2 : 분명히 이것은 프로덕션 준비 코드가 아니라 개념 증명 코드입니다. 실제 프로젝트에서 사용하려면 다음을 추가해야합니다.
- 오류 처리 (malloc이 실패 할 수 있습니다!)
- 복사 생성자 (예 : 데이터 복사, 참조 카운트 추가 또는 복사 생성자를 비공개로 설정)
- 이동 생성자
- const 과부하
- STL 호환 반복자
- 인덱스에 대한 경계 검사 (디버그 빌드에서)
- 값에 대한 범위 검사 (디버그 빌드에서)
- 암시 적 가정 (리틀 엔디안)을 주장합니다.
- As it is,
Itemhas reference semantics, not value semantics, which is unusual foroperator[]; You could probably work around that with some clever C++ type conversion tricks
All of those should be straightforward for a C++ programmer, but they would make the sample code much longer without making it clearer, so I've decided to omit them.
Yes, you can do that, and it will save some space for large quantities of numbers
You need a class that contains a std::vector of an unsigned integer type.
You will need member functions to store and to retrieve an integer. For example, if you want do store 64 integers of 40 bit each, use a vector of 40 integers of 64 bits each. Then you need a method that stores an integer with index in [0,64] and a method to retrieve such an integer.
These methods will execute some shift operations, and also some binary | and & .
I am not adding any more details here yet because your question is not very specific. Do you know how many integers you want to store? Do you know it during compile time? Do you know it when the program starts? How should the integers be organized? Like an array? Like a map? You should know all this before trying to squeeze the integers into less storage.
There are quite a few answers here covering implementation, so I'd like to talk about architecture.
We usually expand 32-bit values to 64-bit values to avoid overflowing because our architectures are designed to handle 64-bit values.
Most architectures are designed to work with integers whose size is a power of 2 because this makes the hardware vastly simpler. Tasks such as caching are much simpler this way: there are a large number of divisions and modulus operations which can be replaced with bit masking and shifts if you stick to powers of 2.
As an example of just how much this matters, The C++11 specification defines multithreading race-cases based on "memory locations." A memory location is defined in 1.7.3:
A memory location is either an object of scalar type or a maximal sequence of adjacent bit-fields all having non-zero width.
In other words, if you use C++'s bitfields, you have to do all of your multithreading carefully. Two adjacent bitfields must be treated as the same memory location, even if you wish computations across them could be spread across multiple threads. This is very unusual for C++, so likely to cause developer frustration if you have to worry about it.
Most processors have a memory architecture which fetches 32-bit or 64-bit blocks of memory at a time. Thus use of 40-bit values will have a surprising number of extra memory accesses, dramatically affecting run-time. Consider the alignment issues:
40-bit word to access: 32-bit accesses 64bit-accesses
word 0: [0,40) 2 1
word 1: [40,80) 2 2
word 2: [80,120) 2 2
word 3: [120,160) 2 2
word 4: [160,200) 2 2
word 5: [200,240) 2 2
word 6: [240,280) 2 2
word 7: [280,320) 2 1
On a 64 bit architecture, one out of every 4 words will be "normal speed." The rest will require fetching twice as much data. If you get a lot of cache misses, this could destroy performance. Even if you get cache hits, you are going to have to unpack the data and repack it into a 64-bit register to use it (which might even involve a difficult to predict branch).
It is entirely possible this is worth the cost
There are situations where these penalties are acceptable. If you have a large amount of memory-resident data which is well indexed, you may find the memory savings worth the performance penalty. If you do a large amount of computation on each value, you may find the costs are minimal. If so, feel free to implement one of the above solutions. However, here are a few recommendations.
- Do not use bitfields unless you are ready to pay their cost. For example, if you have an array of bitfields, and wish to divide it up for processing across multiple threads, you're stuck. By the rules of C++11, the bitfields all form one memory location, so may only be accessed by one thread at a time (this is because the method of packing the bitfields is implementation defined, so C++11 can't help you distribute them in a non-implementation defined manner)
- Do not use a structure containing a 32-bit integer and a char to make 40 bytes. Most processors will enforce alignment and you wont save a single byte.
- Do use homogenous data structures, such as an array of chars or array of 64-bit integers. It is far easier to get the alignment correct. (And you also retain control of the packing, which means you can divide an array up amongst several threads for computation if you are careful)
- Do design separate solutions for 32-bit and 64-bit processors, if you have to support both platforms. Because you are doing something very low level and very ill-supported, you'll need to custom tailor each algorithm to its memory architecture.
- Do remember that multiplication of 40-bit numbers is different from multiplication of 64-bit expansions of 40-bit numbers reduced back to 40-bits. Just like when dealing with the x87 FPU, you have to remember that marshalling your data between bit-sizes changes your result.
This begs for streaming in-memory lossless compression. If this is for a Big Data application, dense packing tricks are tactical solutions at best for what seems to require fairly decent middleware or system-level support. They'd need thorough testing to make sure one is able to recover all the bits unharmed. And the performance implications are highly non-trivial and very hardware-dependent because of interference with the CPU caching architecture (e.g. cache lines vs packing structure). Someone mentioned complex meshing structures : these are often fine-tuned to cooperate with particular caching architectures.
It's not clear from the requirements whether the OP needs random access. Given the size of the data it's more likely one would only need local random access on relatively small chunks, organised hierarchically for retrieval. Even the hardware does this at large memory sizes (NUMA). Like lossless movie formats show, it should be possible to get random access in chunks ('frames') without having to load the whole dataset into hot memory (from the compressed in-memory backing store).
I know of one fast database system (kdb from KX Systems to name one but I know there are others) that can handle extremely large datasets by seemlessly memory-mapping large datasets from backing store. It has the option to transparently compress and expand the data on-the-fly.
If what you really want is an array of 40 bit integers (which obviously you can't have), I'd just combine one array of 32 bit and one array of 8 bit integers.
To read a value x at index i:
uint64_t x = (((uint64_t) array8 [i]) << 32) + array32 [i];
To write a value x to index i:
array8 [i] = x >> 32; array32 [i] = x;
Obviously nicely encapsulated into a class using inline functions for maximum speed.
There is one situation where this is suboptimal, and that is when you do truly random access to many items, so that each access to an int array would be a cache miss - here you would get two cache misses every time. To avoid this, define a 32 byte struct containing an array of six uint32_t, an array of six uint8_t, and two unused bytes (41 2/3rd bits per number); the code to access an item is slightly more complicated, but both components of the item are in the same cache line.
'IT TIP' 카테고리의 다른 글
| 동적으로 양식 생성 및 제출 (0) | 2020.10.17 |
|---|---|
| 조각에서 활동 시작 (0) | 2020.10.17 |
| Swift 3 GCD API 변경 후 dispatch_once (0) | 2020.10.17 |
| 서버에 업로드하기 전에 iOS에서 이미지를 압축 / 크기 조정하는 방법은 무엇입니까? (0) | 2020.10.17 |
| 컬이 활성화 또는 비활성화되었는지 확인하는 방법 (0) | 2020.10.17 |