SSE 사용 및 경계 확인 제거 (또는 기타 고급 최적화)를 허용하도록 Java를 코딩하려면 어떻게해야합니까?

https://stackoverflow.com/questions/1352422

20-09-2019
|

문제

그 상황:

LZF 압축 알고리즘의 Pure-Java 구현을 최적화하고 있는데, 여기에는 해싱 및 비교를위한 많은 바이트 [] 액세스 및 기본 INT 수학이 포함됩니다. 압축의 목표는 I/O 요구 사항을 줄이는 것이기 때문에 성능은 실제로 중요합니다. 코드는 아직 정리되지 않았으므로 코드를 게시하지 않으며 크게 재구성 될 수 있습니다.

질문 :

더 빠른 SSE 작업을 사용하여 jit-compile를 양식으로 컴파일 할 수 있도록 코드를 작성하려면 어떻게해야합니까?
컴파일러가 배열 바운드 체크를 쉽게 제거 할 수 있도록 어떻게 구조화 할 수 있습니까?
특정 수학 운영의 상대적 속도에 대한 광범위한 참조가 있습니까 (일반적인 추가/빼기와 동일하는 데 얼마나 많은 증분/감소가 필요합니까?
분기 최적화를 위해 어떻게 노력할 수 있습니까? 짧은 몸체, 또는 몇 개의 긴 몸매, 또는 중첩 된 조건이있는 짧은 조건 진술을하는 것이 더 나은가요?
현재 1.6 JVM을 사용하면 System에서 얼마나 많은 요소를 복사해야합니까? ArrayCopy는 복사 루프를 이길 수 있습니까?

내가 이미 한 일 :

조기 최적화에 대한 공격을 받기 전에 : 기본 알고리즘은 이미 우수하지만 Java 구현은 2/3 미만입니다. 동등한 C의 속도는 이미 System.arraycopy, 루프 최적화 및 UN을 제거했습니다. -필요한 운영.

나는 비트 twiddling 및 포장 바이트를 INT로 크게 사용하고 성능을 향상시키고 이동 및 마스킹을합니다.

법적 이유로, 유사한 라이브러리에서 구현을 볼 수 없으며 기존 라이브러리에는 너무 제한적인 라이센스 용어가 있습니다.

양호한 (허용) 답변 : 답변 :

용납 할 수없는 답변 : JIT 컴파일러로 얼마나 많이, 왜, 또는 테스트되지 않은 것에 대한 설명없이 "이것은 더 빠릅니다".
경계선 답변 : 핫스팟 1.4 전에 아무것도 테스트하지 않았습니다
기본 답변 : 컴파일러 레벨에서 왜 더 빠른지에 대한 일반적인 규칙과 설명을 제공 할 것입니다.
좋은 답변 : 시연 할 코드 샘플 몇 개를 포함하십시오
훌륭한 답변 : JRE 1.5와 1.6의 벤치 마크가 있습니다
완벽한 답변 : 핫스팟 컴파일러에서 작업 한 사람은 최적화 조건을 완전히 설명하거나 참조 할 수 있으며 일반적으로 얼마나 빠른지를 완전히 설명하거나 참조 할 수 있습니다. 핫스팟에서 생성 된 Java 코드 및 샘플 어셈블리 코드가 포함될 수 있습니다.

또한 : 핫스팟 최적화 및 분기 성능의 내장을 자세히 설명하는 링크가있는 사람이라면 환영합니다. Bytecode에 대해 Sourcecode 레벨이 아닌 바이트 코드에서 성능을 분석하는 사이트가 도움이 될 것이라는 것을 충분히 알고 있습니다.

(편집) 부분 답변 : 바운드 체크 타원 :

이것은 핫스팟 내부 Wiki에 대한 제공된 링크에서 다음과 같습니다. https://wikis.oracle.com/display/hotspotinternals/rangecheckelimination

핫스팟은 다음 조건이있는 루프의 모든 내용의 범위 검사를 제거합니다.

배열은 루프 불변입니다 (루프 내에서 재 할당되지 않음)
인덱스 변수는 일정한 보폭을 가지고 있습니다 (가능한 경우 한 지점에서만 일정한 양으로 증가/감소).
배열은 변수의 선형 함수에 의해 인덱싱됩니다.

예시: int val = array[index*2 + 5]

또는: int val = array[index+9]

아니다: int val = array[Math.min(var,index)+7]

코드의 초기 버전 :

이것은 샘플 버전입니다. H2 데이터베이스 프로젝트에 대한 미공개 버전의 코드이므로 훔치지 마십시오. 최종 버전은 오픈 소스입니다. 이것은 여기에서 코드에 대한 최적화입니다. H2 compresslzf 코드

논리적으로, 이것은 개발 버전과 동일하지만, a (...) 루프를 사용하여 입력을 밟고 문자 그럴 및 역 참조 모드 간의 다른 논리에 대한 if/else 루프를 사용합니다. 모드간에 배열 액세스 및 검사를 줄입니다.

public int compressNewer(final byte[] in, final int inLen, final byte[] out, int outPos){
        int inPos = 0;
        // initialize the hash table
        if (cachedHashTable == null) {
            cachedHashTable = new int[HASH_SIZE];
        } else {
            System.arraycopy(EMPTY, 0, cachedHashTable, 0, HASH_SIZE);
        }
        int[] hashTab = cachedHashTable;
        // number of literals in current run
        int literals = 0;
        int future = first(in, inPos);
        final int endPos = inLen-4;

        // Loop through data until all of it has been compressed
        while (inPos < endPos) {
                future = (future << 8) | in[inPos+2] & 255;
//                hash = next(hash,in,inPos);
                int off = hash(future);
                // ref = possible index of matching group in data
                int ref = hashTab[off];
                hashTab[off] = inPos;
                off = inPos - ref - 1; //dropped for speed

                // has match if bytes at ref match bytes in future, etc
                // note: using ref++ rather than ref+1, ref+2, etc is about 15% faster
                boolean hasMatch = (ref > 0 && off <= MAX_OFF && (in[ref++] == (byte) (future >> 16) && in[ref++] == (byte)(future >> 8) && in[ref] == (byte)future));

                ref -=2; // ...EVEN when I have to recover it
                // write out literals, if max literals reached, OR has a match
                if ((hasMatch && literals != 0) || (literals == MAX_LITERAL)) {
                    out[outPos++] = (byte) (literals - 1);
                    System.arraycopy(in, inPos - literals, out, outPos, literals);
                    outPos += literals;
                    literals = 0;
                }

                //literal copying split because this improved performance by 5%

                if (hasMatch) { // grow match as much as possible
                    int maxLen = inLen - inPos - 2;
                    maxLen = maxLen > MAX_REF ? MAX_REF : maxLen;
                    int len = 3;
                    // grow match length as possible...
                    while (len < maxLen && in[ref + len] == in[inPos + len]) {
                        len++;
                    }
                    len -= 2;

                    // short matches write length to first byte, longer write to 2nd too
                    if (len < 7) {
                        out[outPos++] = (byte) ((off >> 8) + (len << 5));
                    } else {
                        out[outPos++] = (byte) ((off >> 8) + (7 << 5));
                        out[outPos++] = (byte) (len - 7);
                    }
                    out[outPos++] = (byte) off;
                    inPos += len;

                    //OPTIMIZATION: don't store hashtable entry for last byte of match and next byte
                    // rebuild neighborhood for hashing, but don't store location for this 3-byte group
                    // improves compress performance by ~10% or more, sacrificing ~2% compression...
                    future = ((in[inPos+1] & 255) << 16) | ((in[inPos + 2] & 255) << 8) | (in[inPos + 3] & 255);
                    inPos += 2;
                } else { //grow literals
                    literals++;
                    inPos++;
                } 
        }

        // write out remaining literals
        literals += inLen-inPos;
        inPos = inLen-literals;
        if(literals >= MAX_LITERAL){
            out[outPos++] = (byte)(MAX_LITERAL-1);
            System.arraycopy(in, inPos, out, outPos, MAX_LITERAL);
            outPos += MAX_LITERAL;
            inPos += MAX_LITERAL;
            literals -= MAX_LITERAL;
        }
        if (literals != 0) {
            out[outPos++] = (byte) (literals - 1);
            System.arraycopy(in, inPos, out, outPos, literals);
            outPos += literals;
        }
        return outPos; 
    }

최종 편집 :

마감일이 거의 증가했기 때문에 받아 들여지는 가장 좋은 답변을 표시했습니다. 코드를 게시하기로 결정하기 전에 오래 걸렸으므로 가능한 경우 계속해서 의견에 응답하고 응답 할 것입니다. 코드가 지저분한 경우 사과합니다.이 코드는 개발중인 코드를 대표하며 커밋을 위해 세련되지 않았습니다.

해결책

완전한 대답이 아니라, 나는 단순히 질문이 필요로하는 자세한 벤치 마크를 할 시간이 없지만 희망적으로 유용합니다.

당신의 적을 알고 있습니다

JVM (본질적으로 JIT)과 기본 CPU/메모리 서브 시스템의 조합을 목표로합니다. 따라서 "이것은 JVM X에서 더 빠릅니다"는보다 공격적인 최적화로 이동함에 따라 모든 경우에 유효하지 않을 것입니다.

대상 시장/응용 프로그램이 특정 아키텍처에서 크게 실행되면 특정 도구에 대한 투자를 고려해야합니다. * x86의 성능이 중요한 요소 인 경우 Intel의 vtune 일종의 시추에 탁월합니다 JIT 출력 분석 당신은 설명합니다. * 64 비트와 32 비트 요트의 차이는 특히 컨벤션이 변경 될 수있는 X86 플랫폼에서 상당 할 수 있습니다. 등록 기회는 매우 다릅니다.

올바른 도구를 얻으십시오

샘플링 프로파일 러를 얻고 싶을 것입니다. 특정 요구에 대한 계측기 (및 인라인, 캐시 오염 및 코드 크기 인플레이션과 같은 관련 사항)의 오버 헤드 (및 관련된 노크)는 너무 커질 것입니다. Intel Vtune 분석기는 실제로 Java에 사용될 수 있지만 통합은 다른 것만 큼 타이트하지는 않습니다.
Sun JVM을 사용하고 있고 최신/가장 큰 버전이 무엇을하고 있는지 아는 것만으로도 행복하다면 JIT의 출력을 조사하십시오 약간의 어셈블리를 알고 있다면 상당합니다. 이것 기사는이 기능을 사용하여 흥미로운 분석을 자세히 설명합니다

다른 구현에서 배우십시오

변화 역사 Change History는 이전 인라인 어셈블리가 실제로 반대 생산성이 좋았으며 컴파일러가 출력을 완전히 제어 할 수 있음을 나타냅니다 ( 암호 어셈블리에서 지시를받는 대신)는 더 나은 결과를 얻었습니다.

일부 세부 사항

LZF는 최신 데스크탑 CPU에서 효율적으로 관리되지 않은 구현에서 대부분 메모리 대역폭 제한 (따라서 최적화되지 않은 Memcpy의 속도로 연합)이므로 레벨 1 캐시 내에 완전히 유지하려면 코드가 필요합니다.
따라서 상수로 만들 수없는 모든 정적 필드는 동일한 클래스 내에 배치되어야합니다.이 값은 종종 클래스와 관련된 VTABLE 및 메타 데이터에 전념하는 동일한 메모리 영역 내에 배치됩니다.

탈출 분석으로 갇힐 수없는 객체 할당 (1.6 이후)을 피해야합니다.

그만큼 C 코드 루프를 무너 뜨리는 공격을 적극적으로 사용합니다. 그러나 오래된 (1.4 ERA) VM에서 이것의 성능은 JVM이있는 모드에 크게 의존합니다. 후자의 SUN JVM 버전은 특히 서버 모드에서 인라인 및 롤링에서 더 공격적입니다.

JIT에 의해 생성 된 프리 페치 악기는 메모리 바운드가 거의없는 코드의 모든 차이를 만들 수 있습니다.

"우리를 위해 똑바로옵니다"

당신의 목표가 움직이고 있으며 계속 될 것입니다. 다시 Marc Lehmann의 이전 경험 :

기본 HLOG 크기는 이제 15입니다 (CPU 캐시가 증가했습니다)

JVM에 대한 사소한 업데이트조차도 관련 될 수 있습니다 중요한 컴파일러 변경

6544668 런타임에 정렬 할 수없는 배열 작업을하지 마십시오. 6536652 SIMD (Superword) 최적화 구현 6531696 즉각적인 16 비트 값 저장소를 Intel CPU 6468290의 메모리에 사용하지 마십시오.

선장 명백한

측정, 측정, 측정. 라이브러리가 관련 정보 (VM 버전, CPU, OS, 명령 줄 스위치 등)를 기록하는 간단하고 쉽게 실행하기 쉬운 간단하고 실행하기 쉬운 간단하고 실행하기 쉬운 간단하고 실행하기 쉬운 간단하고 실행하기 쉬운 간단하고 실행하기 쉬운 간단하고 실행하기 쉬운 간단하고 실행하기 쉽고이 간단하게 보낼 수 있도록하는 경우 (별도의 DLL) 보험 혜택을 늘리십시오. 무엇보다도 그 치료를 사용하는 사람들을 커버 할 것입니다.

다른 팁

한 경계 검사 제거 새로운 JDK에는 가능할 때마다 제거하는 개선 된 알고리즘이 포함될 것이라고 생각합니다. 이것들은이 주제에 관한 두 가지 주요 논문입니다.

V. Mikheev, S. Fedoseev, V. Sukharev, N. Lipsky. 2002Java에서 루프 버전의 효과적인 향상. 링크. 이 논문은 Excelsior의 사람들이 제트기 JVM.
Würthinger, Thomas, Christian Wimmer 및 Hanspeter Mössenböck. 2007. 배열 바운드 Java Hotspot 클라이언트 컴파일러의 제거 제거. pppj. 링크. 위의 논문을 기준으로 약간, 이것은 다음에 포함될 구현입니다. JDK. 달성 속도를 높이십시오 또한 제시됩니다.

도 있습니다 이것 논문 중 하나를 피상적으로 논의하고 배열뿐만 아니라 새로운 JDK의 산술에 대한 일부 벤치마킹 결과를 제시하는 블로그 항목. 위의 논문의 저자는 매우 흥미로운 의견을 제시하고 논쟁을 논의하기 때문에 블로그 항목의 의견은 매우 흥미 롭습니다. 또한이 주제에 대한 다른 유사한 블로그 게시물에 대한 몇 가지 포인터가 있습니다.

도움이되기를 바랍니다.

LZW와 같은 간단한 숫자 크런치 알고리즘을 최적화하는 데 JIT 컴파일러가 크게 도움이 될 것 같지는 않습니다. Shuggycouk는 이것을 언급했지만 추가주의를 기울여야한다고 생각합니다.

코드의 캐시 친화 성이 큰 요소가 될 것입니다.

Woking 세트의 크기를 줄이고 가능한 한 데이터 액세스 지역을 개선해야합니다. 당신은 "성능을 위해 int에 바이트 포장"을 언급합니다. 이것은 int를 사용하여 바이트 값을 고정하여 단어를 정렬시키기 위해 바이트 값을 유지하는 것처럼 들립니다. 그렇게하지 마십시오! 증가 된 데이터 세트 크기는 모든 이익을 능가합니다 (한 번은 ECC 번호 크런치 코드를 int []에서 바이트 []로 변환하고 2 배 속도 업을 얻었습니다).

당신이 이것을 알지 못할 가능성이 있으면 : 일부 데이터를 바이트와 int로 처리 해야하는 경우, 이동할 필요가 없습니다. ByteBuffer.asIntBuffer() 및 관련 방법.

현재 1.6 JVM을 사용하면 System에서 얼마나 많은 요소를 복사해야합니까? ArrayCopy는 복사 루프를 이길 수 있습니까?

벤치 마크를 더 잘하는 것이 좋습니다. Java에서 1.3 번이나 다시 돌아 왔을 때, 그것은 약 2000 개의 요소 어딘가에있었습니다.

지금까지 많은 답변이 있지만 몇 가지 추가 사항 :

측정, 측정, 측정. 대부분의 Java 개발자가 마이크로 벤치 마킹에 대해 경고하는 한, 변화 사이의 성능을 비교해야합니다. 측정 가능한 개선을 초래하지 않는 최적화는 일반적으로 유지할 가치가 없습니다 (물론, 때로는 사물의 조합이며 까다 롭습니다)
타이트 루프는 C와 마찬가지로 Java와 마찬가지로 중요합니다. 나는 단일 바이트 케이스 (7 비트 ASCII)를 단단한 (ER) 내부 루프로 처리하기 위해 타이트 루프를 재정렬하여 UTF-8 디코딩 속도를 실제로 두 배로 늘려서 다른 케이스를 남겨 둡니다.
대형 배열 할당 및/또는 청소 비용을 과소 평가하지 마십시오. LZF 인코딩/디코딩이 중소형 청크 (megabyte 크기가 아님)의 경우 더 빠르기를 원한다면 BYTE의 모든 할당 []/int [] ]는 다소 비용이 많이 듭니다. GC 때문이 아니라 JVM이 공간을 지워야하기 때문입니다.

H2 구현은 또한 상당히 최적화되었습니다 (예 : 해시 배열을 더 이상 지우지 않으면 종종 의미가 있습니다). 그리고 실제로 다른 Java 프로젝트에서 사용하기 위해 수정하는 데 도움이되었습니다. 저의 기여는 주로 변화하는 경우가 아닌 경우에 더 최적이지만 타이트한 인코딩/디코드 루프에 닿지 않았습니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow