tr1 :: boost :: thread :: id?

StackOverflow https://stackoverflow.com/questions/772192

문제

나는 사용하기 시작했다 unordered_set 수업 tr1 평원 (트리 기반) STL에 대한 속도로 액세스 할 수있는 네임 스페이스 map. 그러나 Boost에 Threads ID에 대한 참조를 저장하고 싶었습니다.boost::thread::id), 해당 식별자의 API가 너무 불투명하여 해시를 명확하게 얻을 수 없다는 것을 깨달았습니다.

놀랍게도 부스트는 일부를 구현합니다 tr1 (포함 hash 그리고 unordered_set), 그러나 스레드 ID를 해시 할 수있는 해시 클래스를 정의하지는 않습니다.

문서를보고 있습니다 boost::thread::id 스레드 ID가 스트림에 출력 될 수 있다는 것을 알았으므로 해싱을 수행하는 솔루션은 다음과 같습니다.

struct boost_thread_id_hash
{
    size_t operator()(boost::thread::id const& id) const
    {
        std::stringstream ostr;
        ostr << id;
        std::tr1::hash<std::string> h;
        return h(ostr.str());
    }
};

즉, 직렬화하고 해시를 결과 문자열에 적용합니다. 그러나 이것은 실제로 STL을 사용하는 것보다 덜 효율적인 것 같습니다. map<boost::thread::id>.

그래서 내 질문 : 더 나은 방법을 찾으십니까? 부스트와 TR1의 분명한 불일치입니까? hash<boost::thread::id> 수업?

감사.

도움이 되었습니까?

해결책

문자열의 오버 헤드 thread::id (나중에 문자열 해시를 계산하기 위해서만), 당신이 거의 말한 것처럼, 성능 혜택에 비해 천문학적입니다. tr1::unordered_map Vis-a-vis를 부를 수 있습니다 std::map. 그래서 짧은 대답은 다음과 같습니다. std :: map <스레드 :: id, ...>

만약 너라면 물론 정렬되지 않은 컨테이너를 사용해야합니다. 사용하려고 노력하십시오native_handle_type 대신에 thread::id 가능하면 선호합니다 tr1::unordered_map< thread::native_handle_type, ... >, 호출 thread::native_handle() 대신에 thread::get_id() 언제 inserting and find잉.

다음과 같은 것을 시도하지 마십시오:

struct boost_thread_id_hash {
   // one and only member of boost::thread::id is boost::thread::id::thread_data
   //   of type boost::detail::thread_data_ptr;
   // boost::thread::id::operator==(const id&) compares boost::thread::id::thread_data's
   size_t operator()(boost::thread::id const& id) const {
      const boost::detail::thread_data_ptr* pptdp = \
        reinterpret_cast< boost::detail::thread_data_ptr* >(&id);
      return h(pptdp->get());
   }
};

효과가 있지만 매우 부서지기 쉬우 며 거의 보장 된 시간 폭탄이 있습니다. 그것은 내면의 내부 작업에 대한 친밀한 지식을 가정합니다. thread::id 구현. 다른 개발자들에 의해 저주를받을 것입니다. 유지 가능성이 우려되는 경우에는하지 마십시오! 패치조차도 boost/thread/detail/thread.hpp 추가하려면 size_t hash_value(const id& tid) 친구로 thread::id 더 나은". :)

다른 팁

명백한 질문은 왜 실제로 해시를 사용하고 싶습니까?

나는 문제를 이해합니다 map / set 성능 크리티컬 코드의 경우 실제로 해당 컨테이너는 매우 다른 메모리 위치에 항목이 할당 될 수 있기 때문에 캐시 친화적이지 않습니다.

Keithb가 제안한 것처럼 (2 ID가 결국 동일한 바이너리 표현을 가지고 있음을 보장하지 않기 때문에 이진 표현을 사용하는 것에 대해서는 언급하지 않습니다 ...) vector 항목이 거의없는 경우 코드 속도를 높일 수 있습니다.

정렬 된 벡터 / deques는 훨씬 더 캐시 친화적이지만 켜짐) 관련된 복사로 인해 삽입/지우기의 복잡성. 수백 개의 실에 도달하면 (많은 것을 본 적이 없음) 아프게 될 수 있습니다.

그러나 맵과 분류 벡터의 이점을 연관시키려는 데이터 구조가 있습니다. B+트리.

각 노드에 하나 이상의 요소 (정렬 된 순서)가 포함 된 맵으로 볼 수 있습니다. 잎 노드 만 사용됩니다.

더 많은 성능을 얻으려면 다음과 같습니다.

  • 잎을 선형으로 연결하십시오. 즉, 뿌리는 첫 번째와 마지막 잎에 대한 포인터를 캐시하며 잎이 서로 연결되어 선형 이동이 인터랙 노드를 완전히 우회합니다.
  • 루트에서 마지막으로 접근 한 잎을 캐시하고, 다음에 액세스 한 다음 잎이 될 것입니다.

점근 성능은 균형 바이너리 트리로 구현되기 때문에 맵과 동일하지만 값은 그룹으로 포장되어 있으므로 코드가 상수로 더 빠르게 될 수 있습니다.

진정한 어려움은 각 "버킷"의 크기를 맞춤화하는 것입니다. 구현에서 일부 사용자 정의가 허용되면 더 나은 프로파일 링이 필요합니다 (코드가 실행되는 아키텍처에 따라 다름).

왜 세트에 이것들을 저장하고 싶습니까? 평범하지 않은 일을하지 않으면 적은 수의 스레드가있을 것입니다. 세트를 유지 관리하는 오버 헤드는 아마도 벡터에 넣고 선형 검색을 수행하는 것보다 높을 것입니다.

검색이 추가 및 삭제보다 더 자주 발생하는 경우 정렬 된 벡터 만 사용할 수 있습니다. <연산자가 boost :: Thread :: ID로 정의 된 <연산자가 있으므로 각 추가 또는 삭제 후 벡터 (또는 올바른 위치에 삽입)를 정렬하고 사용 할 수 있습니다. lower_bound() 이진 검색을 수행합니다. 이것은 세트를 검색하는 것과 동일한 복잡성이며 소량의 데이터에 대해 더 낮은 오버 헤드를 가져야합니다.

여전히이 작업을 수행 해야하는 경우 크기로 취급하는 방법 (boost :: Thread : ID) 바이트로, 그에 따라 작동하는 것은 어떻습니까?

이 예제는 Boost :: Thread :: ID의 크기가 int 크기의 배수이며 포장 및 가상 함수가 없다고 가정합니다. 그것이 사실이 아닌 경우, 수정되어야하거나 전혀 작동하지 않아야합니다.

편집 : 나는 그것을 보았다 boost::thread::id 클래스, 그리고 그것은 a boost::shared_pointer<> 회원으로서 아래 코드는 끔찍하게 깨졌습니다. 유일한 해결책은 boost::thread 해시 기능을 추가하십시오. 다른 상황에서 유용 할 경우를 대비하여 예제를 남기고 있습니다.

boost::thread::id id;
unsigned* data;
// The next line doesn't do anything useful in this case.
data = reinterpret_cast<unsigned *>(&id);
unsigned hash = 0;

for (unsigned int i = 0; i < sizeof(boost::thread::id)/4; i++)
  hash ^= data[i];

이 질문에 대답하기 위해 몇 년 늦었지만 STD :: unordered_map을 키로 부스트 :: thread :: id를 부스트하려고 할 때 가장 관련성이 높은 질문으로 나타났습니다. 기본 핸들을 얻는 것은이 _thread에서 사용할 수 없다는 점을 제외하고 허용 된 답장에서 좋은 제안이었습니다.

대신에 언젠가는 thread :: id에 대한 Hash_Value가 있으므로 이것은 나에게 잘 작동했습니다.

namespace boost {
  extern std::size_t hash_value(const thread::id &v);
}

namespace std {
  template<>
  struct hash<boost::thread::id> {
    std::size_t operator()(const boost::thread::id& v) const {
      return boost::hash_value(v);
    }
  };
}

물론 Libboost_thread 라이브러리와 연결해야합니다.

해시로 사용할 수있는 스레드 :: id와 무언가 (예 : 정수) 사이에 매핑하는 클래스를 만들 수 있습니다. 유일한 단점은 시스템에 맵핑 오브젝트 인스턴스가 하나만 있는지 확인해야한다는 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top