C++에서 데이터의 메모리 크기를 줄이는 방법은 무엇입니까?

Question

저는 C++에서 작업하고 있고 데이터를 저장하기 위해 멀티 맵을 사용하고 있습니다.

struct data 
{ 
     char* value1; 
     char* value2; 

     data(char* _value1, char* _value2) 
     { 
      int len1 = strlen(_value1); 
      value1 = new char[len1+1]; 
      strcpy(value1,_value1); 

      int len2 = strlen(_value2); 
      value2 = new char[len2+2]; 
      strcpy(value2,_value2); 
     } 
     ~data() 
     { 
      delete[] value1; 
      delete[] value2; 
     } 
} 

struct ltstr 
{ 
    bool operator()(const char* s1, const char* s2) const 
    { 
      return strcmp(s1, s2) < 0; 
    } 
}; 


multimap <char*, data*, ltstr> m; 

샘플 입력 :

Key    Value 
    ABCD123456  Data_Mining Indent Test Fast Might Must Favor List Myself Janki Jyoti Sepal Petal Catel Katlina Katrina Tesing Must Motor blah blah. 
    ABCD123456  Datfassaa_Minifasfngf Indesfsant Tfdasest Fast Might Must Favor List My\\fsad\\\self Jfasfsa Katrifasdna Tesinfasfg Must Motor blah blah. 
    tretD152456  fasdfa fasfsaDfasdfsafata_Mafsfining Infdsdent Tdfsest Fast Might Must Favor List Myself Janki 

입력에 2,700 만 항목이 있습니다. 입력 크기 = 14GB

그러나 기억 소비는 56GB에 도달했습니다. 내가 어떻게 메모리 크기를 줄일 수 있는지 알아?

Answer 1

실제로 저장하는 데이터의 양을 줄일 수없는 경우 오버 헤드가 적은 다른 컨테이너를 사용하거나 (맵 및 멀티 맵에 상당히 많은 비트가 있음) 데이터를 메모리에 저장합니다.

당신은이 라이브러리를 살펴 걸릴 수도 있습니다 :

• STXXL : http://stxxl.sourceforge.net/

• 구글 CPP-BTREE : https://code.google.com/p/cpp-btree/

Answer 2

가 첫 번째 최적화 저장하는 것을 포인터 대신 data 개의 개체

std::multimap <char*, data, ltstr> m; 

data*을 사용하면 할당에 추가 메모리 오버 헤드가 추가되기 때문입니다.

또 다른 하나는 pool allocator/Memory pool을 사용하여 동적 메모리 할당의 공간을 줄입니다.

동일한 키 문자열이 많은 경우 키를 다시 사용할 수있는 경우이를 향상시킬 수 있습니다.

Answer 3

하나의 가능성은 멀티 맵 대신 std::map<char *, std::vector<data> >을 사용하는 것입니다. 멀티 맵에서 각 항목에 키 문자열을 저장합니다. 지도에는 키 문자열의 복사본이 하나만 있고 여러 개의 data 항목이 첨부되어 있습니다.

Answer 4

일부 데이터를 보지 않고도 프로젝트의 메모리 사용을 향상시킬 수있는 몇 가지 사항이 있습니다.

첫째, 올라프 (Olaf)가 제안했듯이 데이터 객체를 포인터 대신 멀티 맵에 저장합니다. 나는 당신의 데이터 구조를 위해 풀을 사용하는 것을 제안하지 않는다. 단지 메모리 절약없이지도에 직접 저장하는 것보다 복잡하다.

그래도 할 수있는 일은 std::pair<char*, data> 개의 개체를 할당하는 맵용 특수 할당 자입니다. 이렇게하면 약간의 오버 헤드와 힙 조각화를 줄일 수 있습니다.

다음으로 집중해야 할 주요 사항은 데이터에 두 개의 char* 포인터를 제거하는 것입니다. 14 기가의 데이터로 일부 겹치는 부분이 있습니다. 어떤 데이터인지에 따라 약간 다르게 저장할 수 있습니다.

예를 들어 데이터가 이름 또는 키워드 인 경우 중앙 해시에 저장하는 것이 좋습니다. 네, 위에 제안 된 DAWG와 같은보다 정교한 솔루션이 있지만 먼저 간단한 솔루션을 먼저 시도해야한다고 생각합니다.

단순히 std::set<std::string>에 저장하고 iterator를 저장하면 많은 데이터를 절약 할 수있는 모든 복제본을 압축 할 수 있습니다. 이것은 문자열을 제거하지 않는다고 가정합니다. 문자열을 제거하면 참조 카운팅을해야하므로 std::map<std::string, unsinged long>과 같은 것을 사용할 수 있습니다. 난 당신이 상속 /이 해시 대신 귀하의 데이터 클래스에 참조 계산 논리를 퍼팅 클래스를 작성하는 것이 좋습니다.

저장하는 데이터에 겹치는 부분이 많지 않은 경우 (예 : 이진 데이터이기 때문에 대신 std::string 또는 std::vector<char>에 저장하는 것이 좋습니다. 이유는 데이터 구조의 논리를 없애고 심지어 std::pair으로 바꿀 수 있기 때문입니다.

여러분의 키가 데이터 구조에 저장하고있는 포인터 중 하나가 아니라고 가정합니다. 그렇다면 확실히 제거하고 멀티 맵에서 std::pair의 first 속성을 사용하십시오.

저장하는 데이터 유형에 따라 추가 개선이 가능할 수도 있습니다.

그래서, 아마도 데이터에 적용되지 않는 가정의 많은 당신은 할 수있는이 한 작은 :

typedef std::set<std:string> StringMap; 
typedef StringMap::const_iterator StringRef; 
typedef std::multimap<StringRef, std::pair<StringRef, StringRef>> DataMap; 

Answer 5

난 당신이 누출 또는 불필요하게 키에 메모리를 복제하고 있다는 의심 것 . char * 문자열은 어디에서 왔으며 어떻게 메모리를 관리합니까?

데이터 객체와 동일한 문자열 인 경우 multimap 대신 multiset<data *, ltdata>을 사용하는 것이 좋습니다.

많은 중복 문자열이있는 경우 set<char *,ltstr>에 문자열을 풀링하여 중복을 제거하는 것이 좋습니다.

Answer 6

나는 아직도 어떤 일이 일어나고 있는지 확실하지 않지만 메모리 오버 헤드가 문제의 적어도 일부라고 생각합니다. 그러나 전체 메모리 소비는 data 구조에 필요한 약 4 배입니다. 27M 레코드가 14GB를 차지하지만 레코드 공간이 56GB 인 경우 레코드 당 약 500 바이트가 있습니다. 나에게 이것은 여기에 표시된 것보다 더 많은 데이터가 저장되어 있거나 적어도 일부 데이터가 두 번 이상 저장되었음을 나타냅니다.

"힙 스토리지를위한 추가 데이터"는 실제로 나를 위해 그것을하지 않습니다. 리눅스에서 메모리 할당은 약 32 바이트의 데이터를 가져온다. 오버 헤드가 16 바이트이고 할당 된 메모리 자체가 16 바이트의 배수가됩니다.

는 그래서 multimap에 저장 한 data * 기록, 우리는 필요한 다음과 multimap의 각 노드는 두 개의 포인터를해야합니다

16 bytes of header for the memory allocation. 
8 bytes of rounding on average. 

?? bytes from the file. (Y) 

24 + Y bytes total. 

(I :

16 bytes of header for the memory allocation 
8 bytes for pointer of `value1` 
8 bytes for pointer of `value2` 
16 bytes of header for the string in value1 
16 bytes of header for the string in value2 
8 bytes (on average) "size rounding" for string in value 1 
8 bytes (on average) "size rounding" for string in value 2 

?? bytes from the file. (X) 

80 + X bytes total. 

우리는 다음과 multimap에 char *이 일종의 이진 트리라고 가정) :

16 bytes of header for the memory allocation of the node. 
8 bytes of pointer to "left" 
8 bytes of pointer to "right" 

32 bytes total. 

그래서, 그쪽으로 파일에서 항목 당 136 바이트의 "오버 헤드"를 만듭니다. 27M 레코드의 경우 4GB가 조금 넘습니다.

파일에는 내가 말한 것처럼 항목 당 500 바이트가 포함되어 있으므로 14GB가됩니다.

총 18GB입니다.

어딘가에 뭔가 누수가 있거나 수학이 잘못되었습니다. 여기서 계산을 할 수는 있지만, 위의 모든 것이 계산 된 공간의 두 배가 되더라도 계산되지 않은 20GB의 공간이 있습니다.

1) data에서 두 문자열을 할당하지 마십시오

확실히 우리가 메모리를 절약하기 위해 할 수있는 몇 가지가 있습니다. 먼저 두 길이를 계산 메모리를 하나 개의 덩어리를 할당하고, 서로 직후 문자열을 저장 : 항목 당 평균 24 바이트를 절약 할 수

data(char* _value1, char* _value2) 
    { 
     int len1 = strlen(_value1); 
     int len2 = strlen(_value2); 
     value1 = new char[len1 + len2 +2]; 
     strcpy(value1,_value1); 

     value2 = value1 + len1 + 1; 
     strcpy(value2,_value2); 
    } 

합니다. 똑똑하고 데이터 value1과 value2에 대한 메모리를 한꺼번에 할당함으로써 훨씬 더 많은 것을 저장할 수 있습니다. 그러나 그것은 약간 "너무 똑똑 할"수 있습니다.

2) 큰 슬래브를 data 개 할당하고 한 번에 하나씩 돌리면 도움이됩니다.

struct data 
{ 
    ... 
    data() {}; 
    ... 
    set_values(char* _value1, char* _value2) 
    { 
     int len1 = strlen(_value1); 
     int len2 = strlen(_value2); 
     value1 = new char[len1 + len2 +2]; 
     strcpy(value1,_value1); 

     value2 = value1 + len1 + 1; 
     strcpy(value2,_value2); 
    } 
} 

std::string v1[100], v2[100], key[100]; 

for(i = 0; i < 100; i++) 
{ 
    if (!read_line_from_file(key[i], v1[i], v2[i])) 
    { 
     break; 
    } 
}  

data* data_block = new data[i]; 

for(j = 0; j < i; j++) 
{ 
    data_block[j].setValues[v1[j].c_str(), v2[j].c_str()); 
    m.insert(key[i].c_str(), &data_block[j]); 
} 

다시 말하지만,이 메모리의 엄청난 금액을 저장하지,하지만 각 16 바이트 지역은 일부 메모리를 저장 :이 작업을 위해, 우리는 빈 생성자 및 "setvalues"방법이 필요합니다. 위의 코드는 완전한 코드가 아니며 "어떻게 수행 할 수 있는지 보여주는"것입니다.

3) 멀티 맵에서 "키"가 어디에서 왔는지 여전히 확실하지 않지만 키가 value1 및 value2 항목 중 하나 인 경우 다른 사본을 저장하는 대신 키 중 하나를 다시 사용할 수 있습니다 [ 그것이 현재 어떻게되고 있는지 가정 해 보자.

이것이 진정한 대답이 아닌 경우 유감이지만 '내가하고있는 일에 대한 설명에 어딘가에서 설명되지 않은 것'이라는 의미에서 대답이라고 생각합니다.

프로그램에서 어떤 할당이 이루어 졌는지 이해하면 분명 도움이 될 것입니다.