32비트 정수가 오버플로우 했을 경우 64비트 길이 구조가 아닌 40비트 구조를 사용할 수 있습니까?
들어 32비트 정수는 업그레이드되지 .int로로 합니다.long2 내의40 범위만 필요한 경우 40비트 타입을 사용하여 모든 정수에 대해 24비트(64-40)를 절약할 수 있습니까?
만약 그렇다면, 어떻게?
나는 수십억을 처리해야 하고 공간은 더 큰 제약이다.
수십억 개의 정수를 처리해야 하는 경우 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);
}
};
★★★★★★memcpy 엔디안을 상정하고 있기 때문에 되지 않은 40비트 64비트에서는 리트 엔디안을 상정하고 있습니다. x86합니다.
주의 2: 명백히 이것은 개념 증명 코드이며 실제 가동 가능한 코드가 아닙니다.실제 프로젝트에서 사용하려면 다음과 같이 추가해야 합니다.
- 에러 처리(syslog는 실패할 수 있습니다!)
- 복사 생성자(예를 들어 데이터를 복사하거나 참조 카운트를 추가하거나 복사 생성자를 비공개로 하여)
- 이동 컨스트럭터
- 항상 과부하
- STL 호환 리터레이터
- bounds check for index (디버깅빌드에서)
- 범위 체크, 값(디버깅빌드)
- 암묵적인 전제(리틀 엔디안)에 대해 단언하다
- 현에서, , as as as 。
Item에는 값의가 아닌 시멘틱스가 되어 있습니다.은, 「의 시멘틱스」가 , 「값의 시멘틱스」가 다릅니다.이것은, 에서는 이례적인 것입니다.operator[];++ C++ 타입의 C++, C++ 타입의 트릭 C++ 타입 C++ 를 사용할 수
모두 C++ 프로그래머라면 간단하지만, 샘플 코드를 명확하게 하지 않고 더 길게 만들 수 있기 때문에 생략하기로 했습니다.
다음과 같이 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 )
}
그래요. 하지만.....
이것은 확실히 가능하지만, 일반적으로는 무의미합니다(이러한 숫자를 수십억 개 사용하지 않는 프로그램의 경우).
#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비트 값을 8e의 구조에 저장하는 것입니다.아치 또는 그 배수).
3바이트를 10억 번 절약하는 것은 메모리 페이지가 현저하게 줄어들고 캐시와 TLB 누락이 줄어들기 때문에 가치가 있습니다.특히 페이지 폴트(1페이지 폴트에는 수천만 개의 명령 가중치 부여)가 있습니다.
위의 스니펫은 나머지 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비트 값을 사용할 수도 있습니다(오버플로우 마진을 더 크게 제공).
또는 40비트 값 8개를 하나의 구조에 넣을 수도 있습니다(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이 부족하면 매우 다르게 보일 수 있습니다(테스트하지 않았습니다).
(편집: 우선 원하는 것은 가능합니다.또한 경우에 따라서는 Netflix 과제를 위해 무언가를 하려고 했을 때 메모리 용량이 1GB밖에 없었기 때문에 비슷한 작업을 해야 했습니다.두 번째, 40비트 스토리지에 char 어레이를 사용하여 얼라인먼트 문제를 피하고 구조 패키징의 프래그마를 조작하는 것이 가장 좋습니다.세 번째 - 이 설계에서는 중간 결과를 얻기 위해 64비트 산술에 문제가 없다고 가정하고 있습니다.Int40을 사용하는 것은 대규모 어레이 스토리지뿐입니다.네 번째, 이것이 나쁜 생각이라고 생각되는 것은 아닙니다.메쉬 데이터 구조를 포장하기 위해 사람들이 겪는 일을 읽어보세요.비교적으로 보면, 이것은 어린이와 같은 것입니다).
원하는 것은 데이터를 40비트 int로만 저장하는 구조이지만 암묵적으로 산술적으로 int64_t로 변환하는 구조입니다.유일한 방법은 40비트에서 64비트로의 부호 확장을 올바르게 하는 것입니다.서명되지 않은 ints를 사용해도 괜찮다면, 코드는 더 간단해질 수 있습니다.이것으로 시작할 수 있을 겁니다.
#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;
}
라이브로 체험할 수 있는 링크는 다음과 같습니다.
코멘트에서도 알 수 있듯이, 이것은 꽤 어려운 일입니다.
RAM을 많이 절약하고 싶지 않으면 불필요한 번거로움일 수 있습니다.그러면 훨씬 더 의미가 있습니다.(RAM 절약량은 수백만 개의 메모리 용량에 걸쳐 절약된 비트의 합계입니다.longRAM ram ）
5 바이트/char (5 x 8 비트= 40 비트)의 배열을 사용하는 것을 검토합니다.그런 다음 (오버플로우)에서 비트를 전환해야 합니다. 즉,long 배열로 값을 바이트 배열에 저장합니다.
back to to 、 시 、 시 、 시 、 시 、 to 、 to 、 to 、 to 。long그 값을 사용할 수 있습니다.
과 그 가만, 40비트(5바이트)의 을 사용하는 는, 가 있습니다.struct다섯 번이 비트 이동 및 데이터 정렬에 대한 자세한 내용이 필요한 경우 알려 주십시오.
64비트도 할 수 .long나머지 24비트에서 사용하지 않는 값(3글자 정도)을 숨깁니다.다시 - 비트 이동을 사용하여 24비트 값을 추가 및 제거합니다.
구조를 사용하는 것도 도움이 될 수 있습니다.
typedef struct TRIPLE_40 {
uint32_t low[3];
uint8_t hi[3];
uint8_t padding;
};
이러한 구조에는 16바이트가 소요되며, 16바이트가 정렬된 경우 단일 캐시 행에 완전히 들어갑니다.구조의 어떤 부분을 사용하는지는 구조가 3개의 요소가 아닌 4개의 요소를 보유하고 있을 때보다 더 비쌀 수 있지만, 1개의 캐시 라인에 액세스하는 것은 2개의 캐시 라인에 액세스하는 것보다 훨씬 더 저렴할 수 있습니다.퍼포먼스가 중요한 경우 divmod-3 연산을 저렴하게 실행하고 캐시라인 페치당 비용이 높은 머신과 메모리액세스가 저렴하고 divmod-3가 비싼 머신도 있기 때문에 벤치마크를 사용하는 것이 좋습니다.
이것은 메모리 내에서의 스트리밍 무손실 압축을 필요로 합니다.빅 데이터 애플리케이션의 경우, 고밀도 패킹 기술은 상당히 괜찮은 미들웨어 또는 시스템 수준의 지원이 필요한 것으로 보이는 경우에 최적인 전술적 솔루션입니다.상처 없이 모든 부분을 복구할 수 있는지 확인하기 위해서는 철저한 테스트가 필요합니다.또한 CPU 캐싱 아키텍처(예: 캐시 라인 대 패킹 구조)에 대한 간섭으로 인해 성능에 미치는 영향은 매우 단순하고 하드웨어에 매우 의존합니다.복잡한 메싱 구조를 언급했습니다.이러한 구조는, 특정의 캐싱 아키텍처와 제휴하기 위해서 미세 조정되는 경우가 많습니다.
OP에 랜덤 액세스가 필요한지 여부는 요구 사항에서 명확하지 않습니다.데이터의 크기를 고려할 때 검색을 위해 계층적으로 구성된 비교적 작은 덩어리에 대한 로컬 랜덤 액세스만 필요할 가능성이 높습니다.하드웨어도 대용량 메모리 크기(NUMA)로 이 작업을 수행합니다.무손실 동영상 형식과 마찬가지로 전체 데이터 세트를 핫 메모리에 로드할 필요 없이 청크('프레임') 단위로 랜덤 액세스를 얻을 수 있어야 합니다(압축된 메모리 내 백업 저장소에서).
백업 저장소에서 대용량 데이터셋을 메모리 맵 없이 매핑하여 매우 큰 데이터셋을 처리할 수 있는 고속 데이터베이스 시스템(KX Systems의 kdb, 다른 시스템도 있음)을 알고 있습니다.데이터를 즉시 투명하게 압축 및 확장할 수 있는 옵션이 있습니다.
VLE(Variable-Light Encoding)을 검토할 수 있습니다.
아마도 이러한 숫자의 많은 부분을 어딘가에 저장하고(RAM, 디스크, 네트워크 경유로 송신하는 등) 그 후, 1개씩 취득해, 몇개의 처리를 실시하고 있을 것입니다.
VLE를 사용하여 부호화하는 방법이 있습니다.Google protobuf 문서(Creative Commons 라이센스)에서 확인
varints는 1개 이상의 바이트를 사용하여 정수를 직렬화하는 방법입니다.숫자가 작을수록 더 적은 바이트 수를 사용합니다.
마지막 바이트를 제외한 varint의 각 바이트에는 최상위 비트(msb)가 설정되어 있습니다.이것은 앞으로 바이트가 더 필요함을 나타냅니다.각 바이트의 하위 7비트는 7비트로 구성된 그룹으로, 가장 먼저 최하위 그룹에 두 개의 숫자 보완 표현을 저장하는 데 사용됩니다.
예를 들어, 숫자 1은 1바이트이므로 MSB는 설정되지 않습니다.
0000 0001300은 조금 더 복잡합니다.
1010 1100 0000 0010이게 300이라는 걸 어떻게 알아냈죠?먼저 각 바이트에서 MSB를 삭제합니다. MSB는 숫자의 끝에 도달했는지 알 수 있습니다(보시는 바와 같이 첫 번째 바이트로 설정됩니다).
장점
- 작은 숫자가 많으면 평균 정수당 40바이트 미만일 수 있습니다.아마 훨씬 더 적을거야.
- 앞으로 작은 숫자에 대한 위약금을 지불하지 않고 큰 숫자(40비트 이상)를 저장할 수 있습니다.
단점
- 숫자의 유효 비트 7개마다 추가 비트를 지불합니다.즉, 40개의 유효 비트를 가진 숫자는 6바이트가 필요합니다.숫자의 대부분이 40비트의 유효비트를 가지고 있는 경우는 비트필드 어프로치를 사용하는 것이 좋습니다.
- 인덱스가 지정된 수치로 쉽게 점프할 수 없게 됩니다(현재 요소에 액세스하려면 배열 내의 모든 이전 요소를 부분적으로 해석해야 합니다).
- 숫자로 유용한 작업을 수행하기 전에 어떤 형태의 디코딩이 필요합니다(비트 필드 등 다른 접근법에서도 마찬가지입니다).
40비트 정수 배열(분명히 가질 수 없음)을 원하는 경우 32비트 정수 배열 하나와 8비트 정수 배열 하나를 조합하면 됩니다.
인덱스 i에서 값 x를 읽으려면:
uint64_t x = (((uint64_t) array8 [i]) << 32) + array32 [i];
색인 i에 값 x를 쓰려면:
array8 [i] = x >> 32; array32 [i] = x;
인라인 함수를 사용하여 클래스 내에 캡슐화되어 최대 속도를 얻을 수 있습니다.
이것이 최적이라고는 할 수 없는 상황이 하나 있습니다.즉, 실제로 많은 항목에 랜덤하게 액세스하여 int 어레이에 대한 각 액세스가 캐시 누락이 되는 경우입니다.여기서는 매번 2개의 캐시 누락이 발생합니다.이를 피하려면 6개의 uint32_t 배열, 6개의 uint8_t 배열 및 2개의 미사용 바이트(번호당 41개의 2/3비트)를 포함하는 32바이트 구조를 정의합니다. 항목에 액세스하는 코드는 약간 복잡하지만 항목의 두 구성 요소는 모두 동일한 캐시 행에 있습니다.
비트필드 구조를 사용할 수 있지만 메모리를 절약할 수는 없습니다.
struct my_struct
{
unsigned long long a : 40;
unsigned long long b : 24;
};
이러한 40비트 변수 8개 중 임의의 것을 1개의 구조로 압축할 수 있습니다.
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비트 변수를 사용하는 것에 비해), 이러한 변수의 모든 연산(특히 산술 변수)을 여러 연산으로 분할해야 합니다.
따라서 메모리 최적화는 런타임 성능을 위해 "트레이드"됩니다.
라고 추측하다
- 이것은 C이고,
- 40비트 번호의 대규모 배열을 1개 필요로 합니다.
- 당신은 리틀엔디안 기계 위에 있고
- 당신의 기계는 얼라인먼트를 다룰 수 있을 만큼 똑똑하다.
- 필요한 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);
}
2교대로 하는 게 더 빠를 수도 있어요.
__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;
}
네, 그렇게 할 수 있습니다.그렇게 하면, 대량의 번호를 넣을 수 있는 공간을 절약할 수 있습니다.
부호 없는 정수 유형의 std::벡터를 포함하는 클래스가 필요합니다.
정수를 저장 및 검색하려면 멤버 함수가 필요합니다.예를 들어, 각각 40비트의 64개의 정수를 저장하려면 각각 64비트의 40개의 정수로 구성된 벡터를 사용합니다.그런 다음 인덱스가 있는 정수를 [0,64]에 저장하는 메서드와 이러한 정수를 검색하는 메서드가 필요합니다.
이러한 메서드는 몇 가지 시프트 연산과 몇 가지 바이너리| 및& 를 실행합니다.
당신의 질문이 매우 구체적이지 않기 때문에 저는 아직 여기에 더 이상의 세부사항을 추가하지 않았습니다.몇 개의 정수를 저장할지 알고 계십니까?컴파일 할 때 알아?프로그램이 언제 시작하는지 아세요?정수는 어떻게 정리해야 할까요?배열 같은 거요?지도처럼요?정수를 더 적은 스토리지로 압축하기 전에 이 모든 것을 알아야 합니다.
구현에 대한 답변이 상당히 많기 때문에 아키텍처에 대해 말씀드리겠습니다.
델의 아키텍처는 64비트 값을 처리하도록 설계되어 있기 때문에 오버플로를 피하기 위해 보통 32비트 값을 64비트 값으로 확장합니다.
대부분의 아키텍처는 크기가 2인 정수로 동작하도록 설계되어 있습니다.이것에 의해, 하드웨어가 큰폭으로 심플화되기 때문입니다.캐싱 등의 작업은 이 방법으로 훨씬 간단합니다.2의 거듭제곱을 고수할 경우 비트 마스킹 및 시프트로 대체할 수 있는 다수의 분할 및 계수 연산이 있습니다.
이것이 얼마나 중요한지를 보여주는 예로서 C++11 사양은 "메모리 위치"를 기반으로 멀티스레딩 레이스 케이스를 정의합니다.메모리 위치는 1.7.3에 정의되어 있습니다.
메모리 로케이션은 스칼라 타입의 오브젝트 또는 인접 비트필드의 최대 시퀀스 중 하나이며, 모두 폭은 0이 아닙니다.
즉, C++의 비트필드를 사용하는 경우 모든 멀티스레딩을 신중하게 수행해야 합니다.인접한 2개의 비트필드는 여러 스레드에 걸쳐 연산을 분산하는 경우에도 동일한 메모리 위치로 취급해야 합니다.이것은 C++에게는 매우 드문 일이기 때문에, 만약 당신이 그것에 대해 걱정해야 한다면 개발자의 불만을 야기할 가능성이 있습니다.
대부분의 프로세서는 한 번에 32비트 또는 64비트 메모리 블록을 가져오는 메모리 아키텍처를 갖추고 있습니다.따라서 40비트 값을 사용하면 놀라울 정도로 많은 메모리 액세스가 추가되어 런타임에 큰 영향을 미칩니다.정렬 문제를 고려합니다.
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
64비트 아키텍처에서는 4단어 중 1단어가 "표준 속도"가 됩니다.나머지는 두 배의 데이터를 가져와야 합니다.캐시 누락이 많으면 성능이 저하될 수 있습니다.캐시 적중률이 발생하더라도 데이터를 사용하려면 데이터를 언팩한 후 64비트 레지스터로 재패키지해야 합니다(브런치 예측이 어려울 수도 있음).
이것은 충분히 비용을 들일 만한 가치가 있다
이러한 벌칙이 허용될 수 있는 상황이 있습니다.충분한 인덱스를 가진 대량의 메모리 상주 데이터가 있는 경우 메모리 절감 효과는 성능 저하를 초래할 수 있습니다.각 값에 대해 많은 양의 계산을 수행하면 비용이 최소화될 수 있습니다.그렇다면 위의 솔루션 중 하나를 자유롭게 구현하십시오.단, 여기 몇 가지 권장 사항이 있습니다.
- 비용을 지불할 준비가 되지 않은 경우 비트필드를 사용하지 마십시오.예를 들어 비트필드 배열이 있는데 여러 스레드에 걸쳐 처리하기 위해 비트필드를 분할하려는 경우 교착 상태가 됩니다.C++11 규칙에 따르면 비트필드는 모두 1개의 메모리 위치를 형성하기 때문에 한 번에 1개의 스레드로만 접근할 수 있습니다(이는 비트필드를 패킹하는 방법이 구현 정의되어 있기 때문에 C++11은 구현 정의되지 않은 방법으로 비트필드를 배포할 수 없기 때문입니다).
- 32비트 정수와 문자를 포함하는 구조를 사용하여 40바이트를 만들지 마십시오.대부분의 프로세서는 정렬을 적용하기 때문에 1바이트도 절약할 수 없습니다.
- 문자 배열 또는 64비트 정수 배열과 같은 동일한 데이터 구조를 사용하십시오.얼라인먼트를 올바르게 맞추기가 훨씬 쉽습니다(또한 패킹을 제어할 수 있습니다.즉, 신중하게 계산하면 어레이를 여러 스레드로 분할할 수 있습니다).
- 두 플랫폼을 모두 지원해야 하는 경우 32비트 및 64비트 프로세서를 위한 별도의 솔루션을 설계하십시오.매우 낮은 레벨로 지원이 불충분한 작업을 수행하고 있기 때문에 각 알고리즘을 메모리 아키텍처에 맞게 커스터마이즈해야 합니다.
- 40비트 숫자의 곱셈은 40비트 숫자의 64비트 확장을 40비트로 다시 줄이는 것과 다르다는 것을 기억하십시오.x87 FPU를 다룰 때와 마찬가지로 비트사이즈 간에 데이터를 마샬링하면 결과가 달라집니다.
언급URL : https://stackoverflow.com/questions/27705409/if-a-32-bit-integer-overflows-can-we-use-a-40-bit-structure-instead-of-a-64-bit
'source' 카테고리의 다른 글
| Java의 두 개체를 가능한 null 값과 비교합니다. (0) | 2022.09.01 |
|---|---|
| '\0'은 false, '\0'은 true로 평가됩니다. (0) | 2022.09.01 |
| 페이지 새로고침 또는 직접 액세스 후 vuex-module에서 인증에 액세스할 수 없음 (0) | 2022.09.01 |
| 런타임에 Maven 아티팩트 버전 가져오기 (0) | 2022.09.01 |
| 서로 다른 메시지를 두 파일에 기록하기 위한 로그백 (0) | 2022.09.01 |