| [ CnUnix ] in KIDS 글 쓴 이(By): swhan (Nameless 1) 날 짜 (Date): 2003년 4월 15일 화요일 오전 10시 12분 23초 제 목(Title): Re: [Q]8개의 값을 가장 빠르게 비교하는 � 뚜렷한 답은 안나오지만 그냥 주저리주저리 적어보겠습니다. 언듯 생각해보면 한 방에 갈 수 있는 것은 벡터연산이나 hash밖에 없을 것 같은데 hash의 경우 연산에 대한 오버헤드가 8개 연속된 if나 or보다 클 가능성이 농후하죠. 벡터연산이라면 CPU와 Compiler를 많이 타겠지만 .. 16또는 8개의 비교 후 or(또는 if)의 연속을 3단계 정도로 줄일 수 있을 것 같아보입니다. 그런데 일반적인 상황에서는 이게 불가능하니 hash를 생각해야 할 것 같은데.. 제가 수학적인 지식이 없는 관계로 이거 단순화시킬만한 방법은 mapping밖에 생각이 나지 않는군요. 8byte integer를 1:1로 mapping하려면 말로 표현할 수 없는 절라 많은 메모리가 필요하므로 포기하고 4byte씩 2개로 나눈다면 4GB씩 2개가 필요하군요. 3,3,2로 나눈다면... 16메가 2개 64K 1개. 2,2,2,2로 나눈다면 64K가 4개 필요합네요. 3 3 2로 해서 3번 mapping에 or 2개로 친다면.. 아주 후진 CPU에서 16단계로 처리할 일이 3단계로 줄어들 것 같은데.. 문제는. 메모리 오버헤드가 되겠죠. 로드 3번과 register내에서 8Byte를 3,3,2 정도로 잘라서 카피하고 하는 등등의.. 아주 잘 만들지 않는다면 그냥 or 7번이 더 빠르겠습니다. @ 이거 아주 happy하게 해결할 수 있는 hash함수를 만들 수 있을까요? @ 속도가 아주 크리티컬하다면 해당 CPU의 메뉴얼 보면서 명령어당 클럭수 계산하고 벡터나 SIMD나 CPU가 지원하는 가장 적합한 해결책을 이용해서 어셈블리로 짜는 것이 가장 성능이 좋을 것 같습니다. (배보다 배꼽이 커지는군요) @ 그냥 CPU의 종류와 특성을 안다면 컴파일러가 대충 처리해주도록 적당한 형식으로 C로 작성하는 방법이 정신건강에 가장 좋을 것 같군요. 이것만으로도 거의 2배정도 속도 차이를 가져올 수 있을 것 같은데.. 어떨까요.. |