glibc 의 strcasestr 과의 속도 비교

[codesaf..(codesafer)]

나도 아까 이 소스 봤다가 two_way_short_needle 이랑 two_way_long_needle 함수도 없고 그거 정의된 헤더에도 엉겨있는 다른 헤더들이 없는게 많아서

걍 귀찮아서 냅뒀다가

ideone 에서 돌려봄.

http://ideone.com/4iXsZU

결과.

함수명         찾은 위치      경과 클럭   

strcasestr   104857500 322824 ex_strstr    104857500 178072 (내꺼)

[익명(211.36)]

지립니다

[codesafer(codesafer)]

테스트 코드 만들어서 돌리면 되는데 랜덤으로 테스트 하는 경우가 있고, 알고리즘상 선택된 케이스 따져서 돌리는 경우가 있고, 디비에서 밀어넣는 경우가 있고 그렇지 뭐.

[익명(211.36)]

궁금한게있는데 has_zero_byte 이런 함수는 뭐하는 함수고 저런 연산은 어디서 배우나요?

[익명(211.36)]

문자열에 관해 어떤 지식이 있어야 저런 코딩이 가능한지..ㅋㅋ

[codesafer(codesafer)]

정상적이라면 QA 쪽에서 요구사항들을 탄탄히 정리해놓고, 개발자가 구현을 하고, 내부 테스트를 거친 후 QC 에서 테스트 하는거지.

[codesafer(codesafer)]

has_zero_byte 는 널문자로 끝나는 위치를 4바이트 워드 단위로 감지하기 위한 함수야.

[codesafer(codesafer)]

https://graphics.stanford.edu/~seander/bithacks.html
여기 가면 기본적인 트릭들은 나와 있어.

[codesafer(codesafer)]

한 바이트씩 비교하면 너무 느리니까 저런 트릭을 쓰는건데, 단순히 문자열의 끝까지 트레버스 하는 경우는 2배쯤 빠르다고 생각하면 됨.

[익명(211.36)]

워드가 뭔가여? 1바이트 2바이트 4바이트가 바이트 워드 디워드로 알고있었는데

[codesafer(codesafer)]

물론 내가 작성한 코드도 중복패턴이 많은 문서에서 접두사 접미사 등의 패턴이 있는 단어를 찾을땐 불리한데, 그건 뭐 손품좀 팔면 되니까. 기본 아이디어가 중요하지.

[codesafer(codesafer)]

시스템 워드에 대해선 포인터 강좌에 적어놨어.

[codesafer(codesafer)]

바이트 워드 디워드는 16비트 시절부터 내려오던 전통 네이밍이고, 시스템 워드라는건, 해당 컴파일러에서 기본단위로 사용하는 바이트 수를 의미하지.

[codesafer(codesafer)]

32비트 컴파일러에선 32비트가 시스템 워드. 64비트 컴파일러에선 64비트가 시스템 워드가 돼. 즉, 포인터의 크기랑 일치하지.

[익명(211.36)]

ㅇㅎ

[sh(142.241)]

glibc패치고고씽

[codesafer(codesafer)]

패치해주려면 패턴 스킵 코딩해줘야됨 귀찮음.