Go: math/rand/v2 Lemire's algorithm 알고리즘

https://choiseokwon.tistory.com/340

Floating Parsing: Eisel-Lemire algorithm

 

위에도 들어있던 Lemire이란 사람의 알고리즘인 것 같다.

 

math/rand/v2 가 추가되었다고 해서 살펴봤다.

math/rand/v2: revised API for math/rand · Issue #61716 · golang/go

 

그중 Lemire 알고리즘을 써서 Int31n, Int63N에서 성능 향상이 있다고 하는데 궁금해서 읽어봤다.

 

Lemire

전통적인 modulo 환원법보다 효율적으로 특정 range 내의 임의의 정수를 생성할 수 있는 방법인 것 같다.

코드를 읽어보면, 큰 수의 집합을 더 작은 범위인 [0, N - 1] 로 줄일 때 흔히 사용하는 modulo (x % N)의 비효율성을 해결하고 있다.

(모듈로는 나누기가 사용되어서 +-* 연산보다 좀 더 expensive 함 = high latency/low throughput)

 

1. Multiplication and Promotion (곱셈 및 프로모션): 입력된 정수 x에 N을 곱하여 더 높은 비트폭으로 promote 한다.

2. bitwise shift: bitwise 우측 쉬프트를 수행하여 분할 연산의 계산 비용 없이 2^32 만큼 분할한다.

프로세서들이 곱셈/비트 단위 연산은 빠름을 이용해서 푼 듯 하다.

성능도 좋고, fair 하다. ( [0, N - 1] 범위 내에서 거의 균일한 값의 분포 보장)

 

Java

간단히.. 자바로 써보면? 일단 자바에는 기본으론 unsigned 32bit arithmetic을 지원하지 않는다.

public class LemireRandom {
    private final java.util.Random random;

    public LemireRandom() {
        this.random = new java.util.Random(); // Random 객체 생성
    }

    public int randomInt(int n) {
        long x = random.nextInt() & 0xFFFFFFFFL; // 32비트 정수를 무작위로 생성하고 부호 없는 정수로 처리
        long m = x * n; // 생성된 난수 x에 n을 곱함
        long l = m & 0xFFFFFFFFL; // 곱셈 결과의 하위 32비트
        long h = (m >>> 32);      // 곱셈 결과의 상위 32비트

        // 하위 비트가 n보다 작은 경우, 이 값들을 거부하여 편향을 피함
        if (l < n) {
            long t = (0xFFFFFFFFL + 1) % n;
            while (l < t) {
                x = random.nextInt() & 0xFFFFFFFFL; // 새로운 난수를 생성
                m = x * n; // 난수와 n의 새로운 곱셈
                l = m & 0xFFFFFFFFL; // 새로운 하위 32비트
                h = (m >>> 32); // 새로운 상위 32비트
            }
        }
        return (int) h; // 상위 32비트를 반환하여 범위 내 값으로 사용
    }

    public static void main(String[] args) {
        LemireRandom lr = new LemireRandom();
        int N = 100; // 예제 범위
        int sampleSize = 1000; // 생성할 무작위 값의 수

        // 무작위 값을 생성하여 출력
        for (int i = 0; i < sampleSize; i++) {
            System.out.println(lr.randomInt(N));
        }
    }
}

 

java.util.Random 벤치마크

간단한 Lemire 구현 버전과 자바의 기본 라이브러리 벤치마크를 해보았다.

보통 Random.nextInt 보다 빠르긴 한데 랜덤성이 있다 보니 가끔은 더 느리게 나왔다.

JDK 17

JDK 17

 

import java.util.Random;

public class BenchmarkRandom {
    private static final Random random = new Random();
    private static final int SAMPLE_SIZE = 1000000;

    public static void main(String[] args) {
        int n = 1000; // Example range
        benchmarkJavaRandom(n);
        benchmarkLemireRandom(n);
    }

    public static void benchmarkJavaRandom(int n) {
        long startTime = System.nanoTime();
        for (int i = 0; i < SAMPLE_SIZE; i++) {
            random.nextInt(n);
        }
        long endTime = System.nanoTime();
        double duration = (endTime - startTime) / 1_000_000.0; // milliseconds
        System.out.println("Java Random.nextInt: " + duration + " ms");
    }

    public static void benchmarkLemireRandom(int n) {
        LemireRandom lemireRandom = new LemireRandom();
        long startTime = System.nanoTime();
        for (int i = 0; i < SAMPLE_SIZE; i++) {
            lemireRandom.randomInt(n);
        }
        long endTime = System.nanoTime();
        double duration = (endTime - startTime) / 1_000_000.0; // milliseconds
        System.out.println("Lemire Random: " + duration + " ms");
    }
}

class LemireRandom {
    private final Random random = new Random();

    public int randomInt(int n) {
        long x = random.nextInt() & 0xFFFFFFFFL;
        long m = x * n;
        long l = m & 0xFFFFFFFFL;
        long h = (m >>> 32);
        if (l < n) {
            long t = (0xFFFFFFFFL + 1) % n;
            while (l < t) {
                x = random.nextInt() & 0xFFFFFFFFL;
                m = x * n;
                l = m & 0xFFFFFFFFL;
                h = (m >>> 32);
            }
        }
        return (int) h;
    }
}