최대 성능을 위해 어떤 비트셋 구현을 사용해야합니까?

현재 JIT (Just In Time) 컴파일러에서 다양한 알고리즘을 구현하려고합니다. 대부분의 알고리즘은 비트 맵 (비트 맵)에서 작동합니다.최대 성능을 위해 어떤 비트셋 구현을 사용해야합니까?

C++에는 비트 셋을 구현하는 다양한 방법이 있습니다. 진정한 C++ 개발자로서 나는 STL에서 무언가를 사용하는 것을 선호한다. 가장 중요한 부분은 성능입니다. 반드시 동적으로 크기를 재조정 할 수있는 비트 셋이 필요하지는 않습니다.

내가보기에 세 가지 옵션이 있습니다.

I. 하나의 옵션은 공간 최적화 된 std::vector<bool>을 사용하는 것입니다. 이것은 또한 데이터가 메모리에서 연속적 일 필요가 없음을 나타냅니다. 나는 이것이 성능을 떨어 뜨릴 수 있다고 생각한다. 반면에 각 bool 값에 대해 1 비트를 갖는 것은 매우 캐시 친화적이기 때문에 속도를 향상시킬 수 있습니다.

II. 또 다른 옵션은 std::vector<char>을 대신 사용하는 것입니다. 데이터가 메모리에서 연속적이며 개별 요소에 액세스하는 것이 더 쉽습니다. 그러나이 옵션은 비트셋이 아니기 때문에 이상하게 느껴집니다.

III. 세 번째 옵션은 실제 std::bitset을 사용하는 것입니다. 동적으로 크기를 조정할 수 없다는 사실은 중요하지 않습니다.

최대 성능을 위해 어느 것을 선택해야합니까?

출처

2012-07-29 Man of One Way

벤치 마크! [관련.] (http://www.youtube.com/watch?v=wg4trPZFUwc) –

[Boost.Dynamic Bitset] (http://www.boost.org/doc/libs/1_50_0/libs/)도 있습니다. dynamic_bitset/dynamic_bitset.html)을 고려해야합니다. 하지만 실제로는 사용 패턴을 모른 채 어떤 성능이 가장 좋은 성능인지 알 수있는 방법이 없습니다. 예 : 컬렉션이 작고 자주 액세스하는 경우 '벡터 '은 비트 시프트/마스킹을 수행 할 필요가 없으므로 비트 세트에 더 빨리 액세스 할 수 있습니다. 그러나 액세스 빈도가 적어 액세스 빈도가 낮을수록 캐시 누락이 많아지면 그 이점이 사라질 수 있습니다. – Grizzly

무언가를 분명하게 지적 할 위험이 있습니다 : std :: bitset은 스택에 할당되므로 대부분의 경우 최대 크기가 상당히 제한됩니다. 그러나 저장해야하는 데이터의 양에 대해서는 알지 못합니다. – identity

가장 좋은 방법은 모든 상황이 다르기 때문에 벤치마킹하는 것입니다.

나는 std::vector<bool>을 사용하지 않을 것입니다. 나는 그것을 한 번 시도하고 성과는 무섭다. 대신 std::vector<char>을 사용하여 응용 프로그램의 성능을 향상시킬 수 있습니다.

저는 std::bitset와 std::vector<char>을 실제로 비교하지 않았습니다. 그러나 공간에 문제가 없다면 std::vector<char>으로 갈 것입니다. 그것은 비트셋보다 8 배 더 많은 공간을 사용하지만 데이터를 가져 오거나 설정하기 위해 비트 연산을 수행 할 필요가 없기 때문에 더 빨라야합니다.

물론 bitset/vector에 많은 양의 데이터를 저장해야한다면 비트 셋을 사용하는 것이 프로세서의 캐시에 맞기 때문에 유용 할 수 있습니다.

가장 쉬운 방법은 typedef를 사용하고 구현을 숨기는 것입니다. bitset과 vector는 모두 [] 연산자를 지원하므로 하나의 구현을 다른 것으로 전환하는 것이 쉬워야합니다.

출처

2012-07-29 20:21:02 Patrick

'operator []'는 충분히 유사 합니다만, 생성자는 그렇지 않습니다. –

@MooingDuck : 사실. 하나의 유형에서 다른 유형으로의 마이그레이션을 단순화하기 위해 typedef를 사용하지만 쉽게 만들 수는 없습니다. 또한 typedef를 콜렉션에 사용하여 실제 구현 (list, vector, deque, ...)을 숨길 수 있으므로 컨테이너 유형을 변경하면 실제 코드 변경이 약 90 % 줄어 듭니다. – Patrick

당신은이 (다소 일자) 종이에 관심이있을 수 있습니다 http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf

출처

2014-01-03 19:58:47

간단히 말하자면 다음과 같습니다 : "boost :: dynamic_bitset은 실행 속도면에서 다른 구현물 인 보다 훨씬 효율적입니다. 구현 방법은'std :: vector '은 다른 메모리보다 성능이 뛰어나다 "고 덧붙였다. – davidhigh

나는이 포럼에서 최근에 유사한 질문에 대답. 내 BITSCAN library을 권하고 싶습니다. 방금 버전 1.0을 릴리스했습니다. BITSCAN은 고속 비트 스캔 작업을 위해 특별히 설계되었습니다.

BitBoard 클래스는 일반적인 작업 등 BSF 64 비트 단어 또는 BSR popcount (일명 bitboards)의 다른 구현 예들을 감싼다. BitBoardN, BBIntrin 및 BBSentinel 클래스는 비트 스캔을 비트 문자열로 확장합니다. BITSCAN의 비트 문자열은 비트 보드의 배열입니다. 비트 문자열의 기본 래퍼 클래스는 BitBoardN입니다. BBIntrin은 64 비트 보드를 통해 Windows 컴파일러 내장 함수를 사용하여 BitBoardN을 확장합니다.BBIntrin은 적절한 asm 함수를 사용하여 POSIX로 이식 가능합니다.

저는 그래프 도메인에서 NP 조합 문제에 대한 여러 가지 효율적인 해결사를 구현하기 위해 BITSCAN을 사용했습니다. 일반적으로 그래프의 인접 행렬과 정점 집합은 비트 열로 인코딩되며 일반적인 계산은 비트 마스크를 사용하여 수행됩니다. 간단한 비트 인코딩 된 그래프 개체의 코드는 GRAPH에서 사용할 수 있습니다. BITSCAN 및 GRAPH 사용 방법의 예도 제공됩니다.

STL에서 BITSCAN 전형적인 구현의 비교 (는를 비트 세트) 및 BOOST (dynamic_bitset)은 여기에서 찾을 수있다 : http://blog.biicode.com/bitscan-efficiency-at-glance/

출처

2014-07-22 18:39:28 chesslover

최대 성능을 위해 어떤 비트셋 구현을 사용해야합니까?

답변

관련 문제