constexpr std::size_t finder = ( std::size_t )0x0101010101010101ULL;
constexpr std::size_t masker = ( std::size_t )0x8080808080808080ULL;
constexpr std::size_t has_zero_7bit( const std::size_t n )
{
return ( n - finder ) & masker;
}
constexpr std::size_t has_zero_8bit( const std::size_t n )
{
return has_zero_7bit( n ) & ~n;
}
inline auto where_zero( const std::size_t* w )
{
auto* p = (const char*)w;
while( *p++ );
return p - 1;
}
template< int bits >
auto strend_bit( const char* s )
{
const int step = sizeof finder == 4 ? 8 : 4;
const auto has_zero = bits == 7 ? has_zero_7bit : has_zero_8bit;
if( has_zero( *(std::size_t*)s ) )
return where_zero( (std::size_t*)s );
auto w = (std::size_t*)( (std::size_t)s & ~std::size_t( sizeof finder - 1 ) ) + 1;
while( 1 )
{
if( has_zero( w[ 0 ] ) ) return where_zero( w );
if( has_zero( w[ 1 ] ) ) return where_zero( w + 1 );
if( has_zero( w[ 2 ] ) ) return where_zero( w + 2 );
if( has_zero( w[ 3 ] ) ) return where_zero( w + 3 );
if( sizeof finder == 4 )
{
if( has_zero( w[ 4 ] ) ) return where_zero( w + 4 );
if( has_zero( w[ 5 ] ) ) return where_zero( w + 5 );
if( has_zero( w[ 6 ] ) ) return where_zero( w + 6 );
if( has_zero( w[ 7 ] ) ) return where_zero( w + 7 );
}
w += step;
}
}
auto strlen_fast( const char* s )
{
return strend_bit< 8 >( strend_bit< 7 >( s ) ) - s;
}
며칠 전에 기본 루프 테스트 해 보고 루프비용 싸진김에
where_zero 를 while 문 돌리는게 inline 화에 더 적합할것 같아서
( code cache 를 적게 소모 )
해 보니 쪼금 더 빨라짐.
gcc strlen 보다 3.98 배 빠름.
gcc에서 무슨컴파일러로갓는지 안적혀있는데
예전엔 32비트 컴파일러 지금은 64비트 컴파일러. 근데 루프 기본 비용이 싸진걸 보면 CPU 빨임.
strend_bit에서 탈출문 많으면 분기예측 힘들다고 피하라고 주워들었는데 저거슨 왜 저리빠른건가여
일단 if 에서 분기예측이 걸러지기 때문이지. 분기예측기는 기본적으로 false 조건에 적응하게 됨.
이 코드는 if 와장창 돈 다음 마지막에 뿅. 이라 분기예측은 if 들 레벨에서 끝나게됨. 출구가 많아 보이지만 복잡한 return 형식과는 다른것.
=> 분기예측은 false가 디폴트다, 좋은거 배워갑니다
실제로 false 가 디폴트지만 몇 바퀴 돌면 제대로 예측하게 돼. 그렇게 간단한 문제가 아니야 ㅋㅋ
와 굇수..
허미쉿벌... 코드가 돌면서 분기는 if 단에서 캐싱이 되기 때문에 return문과 상관없이 예측잘한다 개쩜..