Copy-on-Write를 구현하는 방법은 무엇입니까?

Question

커스텀 C++ String 클래스에 copy-on-write를 구현하고 싶습니다. 그리고 어떻게해야하는지 궁금합니다.

나는 몇 가지 옵션을 구현하려고 시도했지만 모두 매우 비효율적 인 것으로 나타났습니다.

당신에게 (요즘 대부분입니다) 다중 스레드 environemnt에서

Answer 1

암소가 자주 이득보다는 명중 엄청난 성능입니다 :-) 사람을 감사드립니다. 그리고 const 참조를주의 깊게 사용하면 단일 스레드 환경에서도 성능이 크게 향상되지 않습니다.

이 오래된 DDJ 기사에서는 just how bad CoW can be in a multithreaded environment, even if there's only one thread을 설명합니다.

또한 다른 사람들이 지적했듯이 CoW 문자열은 구현하기 까다 롭고 실수하기 쉽습니다. 스레딩 상황에서 퍼포먼스가 좋지 않아 일반적으로 유용성에 의문을 제기하게됩니다. C++ 11을 사용하여 시작하고 할당을 이동하면이 작업은 더욱 사실입니다.

하지만, 여기에 성능에 도움이 될 수 있습니다 구현 기술의 커플 귀하의 질문에 ....

에 대답.

먼저 문자열 자체에 길이를 저장하십시오. 길이는 꽤 자주 액세스되며 역 참조 포인터를 제거하면 도움이 될 것입니다. 나는 일관성을 위해 할당 된 길이를 그곳에두기 만했다. 이렇게하면 문자열 객체가 조금 더 커지게되지만, 공간과 복사 시간의 오버 헤드는 매우 적습니다. 특히 이러한 값이 컴파일러에서 재미있는 최적화 트릭을 더 쉽게 수행 할 수 있기 때문입니다.

이는 다음과 같습니다 문자열 클래스를 잎 :

class MyString { 
    ... 
private: 
    class Buf { 
     ... 
    private: 
     ::std::size_t refct_; 
     char *data_; 
    }; 

    ::std::size_t len_; 
    ::std::size_t alloclen_; 
    Buf *data_; 
}; 

지금, 당신이 수행 할 수있는 더 최적화가 있습니다. 거기에있는 Buf 클래스는 실제로 포함하지 않거나 많이하지 않는 것처럼 보입니다. 그리고 이것은 사실입니다. 또한 문자를 보유하려면 Buf 인스턴스와 버퍼를 모두 할당해야합니다. 이것은 오히려 낭비적인 것 같습니다. 그래서, 우리는 일반적인 C 구현 기술로 전환됩니다 신축성 버퍼 :이 방법으로 일을 할 때 alloclen_ 바이트 대신에 단지 1

을 포함 것처럼

class MyString { 
    ... 
private: 
    struct Buf { 
     ::std::size_t refct_; 
     char data_[1]; 
    }; 

    void resizeBufTo(::std::size_t newsize); 
    void dereferenceBuf(); 

    ::std::size_t len_; 
    ::std::size_t alloclen_; 
    Buf *data_; 
}; 

void MyString::resizeBufTo(::std::size_t newsize) 
{ 
    assert((data_ == 0) || (data_->refct_ == 1)); 
    if (newsize != 0) { 
     // Yes, I'm using C's allocation functions on purpose. 
     // C++'s new is a poor match for stretchy buffers. 
     Buf *newbuf = ::std::realloc(data_, sizeof(*newbuf) + (newsize - 1)); 
     if (newbuf == 0) { 
     throw ::std::bad_alloc(); 
     } else { 
     data_ = newbuf_; 
     } 
    } else { // newsize is 0 
     if (data_ != 0) { 
     ::std::free(data_); 
     data_ = 0; 
     } 
    } 
    alloclen_ = newsize; 
} 

, 당신은 다음 data_->data_을 처리 할 수 ​​있습니다 이 모든 경우에 멀티 스레드 환경에서 이것을 절대 사용하지 말아야하는지 또는 refct_이 원자 증분과 원자가 모두있는 유형인지 확인해야합니다 감소와 시험 지시.

더 긴 문자열을 설명하는 데 사용할 데이터 비트 안에 바로 짧은 문자열을 저장하는 데 유니온을 사용하는 고급 최적화 기술이 있습니다. 그러나 그것은 훨씬 더 복잡합니다. 그리고 나중에이 예제를 단순화하기 위해 이것을 편집하려고 생각하지는 않지만, 결코 알 수는 없습니다.

Answer 2

CoW에는 많은 것이 없습니다. 기본적으로 변경하려는 경우 복사하고 변경하지 않으려는 사용자는 이전 인스턴스에 대한 참조를 유지하게합니다. 개체를 계속 참조하는 사람을 추적하기 위해 참조 계산이 필요하며 새 복사본을 만들기 때문에 '이전'인스턴스의 수를 줄여야합니다.바로 가기는 그 카운트가 하나 일 때 복사본을 만들지 않는 것입니다 (유일한 참고 자료입니다).

그 외에도 직면 한 특정 문제가없는 한 말할 수있는 것이 많지 않습니다.

Answer 3

정확하게 허브 셔터의 More Exceptional C++ 책에 대한 일련의 기사가 있습니다. 액세스 권한이 없으면 인터넷 기사 인 part 1, part 2 및 part 3을 사용해보세요.

Answer 4

다른 언어 (파이썬, 내가 아는 한 C#)의 '불변'문자열을 에뮬레이트하고 싶을 수 있습니다.

아이디어는 각 문자열을 변경할 수 없으므로 문자열의 모든 작업이 새로운 불변의 하나를 만듭니다 ... 또는 폭발을 피하기 위해 기본 아이디어입니다. 유사한 것이 있으면 다른 것을 만들지 않아도됩니다. .

Answer 5

template <class T> struct cow { 
    typedef boost::shared_ptr<T> ptr_t; 
    ptr_t _data; 

    ptr_t get() 
    { 
    return boost::atomic_load(&_data); 
    } 

    void set(ptr_t const& data) 
    { 
    boost::atomic_store(&_data, data); 
    } 
} 

Answer 6

내가 제안

하나, 하나가 변경 가능한 문자열로 동작합니다 래퍼 유형을 정의해야하고, 어떤이 널 (NULL) 모두를 개최한다 (문자열 또는 무엇 이건) 기록 중 복사 효율적으로 구현하고자하는 경우 그 mutable 문자열에 대한 참조 (해당 항목에 대한 다른 참조가 존재하지 않음)와 "immutable"문자열에 대한 nullable 참조 (참조가 변경되지 않는 항목 외부에 존재하지 않음). 랩퍼는 항상 null이 아닌 참조 중 적어도 하나를 사용하여 작성됩니다. 변경 가능 항목 참조가 null이 아닌 값으로 설정되면 (건설 도중 또는 이후) 영원히 동일한 대상을 참조합니다. 두 참조가 모두 null이 아닌 경우 immutable-item 참조는 가장 최근에 완료된 돌연변이 이후 얼마 후에 만들어진 항목의 사본을 가리키고 (변경 불가능한 항목 참조는 참조를 보유하거나 보유하지 않을 수 있습니다 사전 돌연변이 값으로).

개체를 읽으려면 "mutable-item"참조가 null이 아닌지 확인하십시오. 그렇다면 사용하십시오. 그렇지 않은 경우, "immutable-item"참조가 null이 아닌지 검사하십시오. 그렇다면 사용하십시오. 그렇지 않은 경우, "변경 가능 항목"참조 (현재는 null이 아닌)를 사용하십시오.

개체를 변경하려면 "mutable-item"참조가 null이 아닌지 확인하십시오. 그렇지 않은 경우 "불변 항목"참조의 대상을 복사하고 CompareExchange는 새 오브젝트에 대한 참조를 "변경 가능한 항목"참조로 복사합니다. 그런 다음 "변경 가능한 항목"참조의 대상을 변경하고 "불변 항목"참조를 무효화하십시오.

개체를 복제하려면 복제본이 변경되기 전에 복제본이 다시 복제 될 것으로 예상되는 경우 "immutable-item"참조 값을 검색하십시오. 값이 null의 경우, 「변경 가능한 항목」타겟의 복사를 작성해, 그 새로운 오브젝트에의 참조를 불변 아이템 참조에 격납합니다. 그런 다음 "mutable-item"참조가 null이고 "immutable-item"참조가 검색된 값 (null이 아닌 경우) 또는 새 항목 (있는 경우) 중 하나 인 새 래퍼를 만듭니다.

개체를 복제하려면 복제되기 전에 복제본이 변형 될 것으로 예상되는 경우 "immutable-item"참조의 값을 검색하십시오. null의 경우, 「변경 가능 항목」참조를 가져옵니다. 검색된 참조의 대상을 복사하고 "변경 가능 항목"참조가 새 복사본을 가리키고 "변경 불가능 항목"참조가 null 인 새 래퍼를 만듭니다.

두 가지 복제 방법은 의미 상 동일하지만 주어진 상황에서 잘못된 복제 방법을 선택하면 추가 복사 작업이 수행됩니다. 일관되게 올바른 복사 작업을 선택하면 "적극적인"COW (Copy-On-Write) 접근 방식의 이점을 최대한 활용하지만 스레드 오버 헤드는 훨씬 적습니다. 모든 데이터 보유 객체 (예 : 문자열)는 변경 불가능하거나 변경 불가능한 공유가 될 것이고, 어떤 객체도 그러한 상태 사이를 전환 할 수 없습니다.따라서 래퍼 객체가 둘 이상의 스레드에서 동시에 사용되지 않는다면 원하는 경우 모든 "스레딩/동기화 오버 헤드"(CompareExchange 작업을 직선 저장소로 대체)를 제거 할 수 있습니다. 두 개의 래퍼 객체는 동일한 불변 데이터 홀더에 대한 참조를 보유 할 수 있지만 서로의 존재를 무시할 수 있습니다.

"공격적"접근 방식을 사용할 때보 다이 접근 방식을 사용할 때 몇 가지 추가 복사 작업이 필요할 수 있습니다. 예를 들어, 새 랩퍼가 새. 자열로 작성되고 해당 랩퍼가 변형되어 6 번 복사 된 경우 원래 랩퍼는 원래 문자열 홀더에 대한 참조와 데이터 사본을 보유하는 변경 불가능한 오브젝트를 보유합니다. 여섯 개의 복사 된 래퍼는 불변 문자열에 대한 참조를 보유합니다 (사본이 작성된 후에 원래 문자열이 변이되지 않은 경우 공격적인 구현은 하나의 문자열 만 가져올 수 있지만 총 두 개의 문자열). 원본 래퍼가 6 개의 복사본 중 5 개와 함께 변형 된 경우 변경 불가능한 문자열에 대한 참조 중 하나만 제외하고 모두 무효화됩니다. 이 시점에서 여섯 번째 래퍼 복사본이 변형 된 경우 적극적인 Copy-On-Write 구현은 해당 문자열에 대한 유일한 참조를 보유했음을 인식하고 사본이 필요하지 않다고 결정할 수 있습니다. 그러나 필자가 기술 한 구현은 새로운 변경 가능한 복사본을 만들고 불변의 복사본을 버립니다. 그러나 몇 가지 추가 복사 작업이 있음에도 불구하고 대부분의 경우 스레드 오버 헤드 감소는 비용을 상쇄해야합니다. 생성 된 논리적 복사본의 대부분이 변이되지 않는다면이 방법은 항상 문자열의 복사본을 만드는 것보다 효율적일 수 있습니다.