Java 의 Boolean 배열을 사용할 때 CPU 사용률이 급등하는 현상이 발생하는데 왜 그럴까요?
에라토스네테스의 체를 작업해보았는데요. 우선 boolean 배열로 다음과 같이 작업해보았습니다.
최대판단 정수 한계는 2억입니다.
약간 난해할 수 있는데 짝수는 2를 제외하고 소수 (prime number) 가 아니므로 2 를 예외로 특별히 처리하고, 홀수에 대해서만 다루도록 해놓았습니다.
시험해본 Java version 은 19 입니다.
class SieveBool { static final int MAX_LIMIT = 200_000_000; public static void main(String[] args) { var sieve = new boolean[MAX_LIMIT + 1]; for (int i = 2; i <= MAX_LIMIT; i++) sieve[i] = true; for (int i = 3; i * i <= MAX_LIMIT; i += 2) { if (sieve[i]) { int i2 = i + i; for (int j = i + i2; j <= MAX_LIMIT; j += i2) { sieve[j] = false; } } } var primes = new java.util.ArrayList<Integer>(); primes.add(2); for (int i = 3; i <= MAX_LIMIT; i += 2) { if (sieve[i]) { primes.add(i); } } int len = primes.size(); System.out.printf( "%b %b %d %d %d", sieve[MAX_LIMIT - 1], sieve[MAX_LIMIT - 3], len, primes.get(len - 1), primes.get(len - 2)); } }
이런 작업을 해보니 primitive wrapper 의 부하를 한번 시험해보고 싶다는 생각이 들어서 변경해 보았습니다.
그 결과 memory 를 많이 사용하고 느려져서 한계를 4천만으로 줄여야 했습니다.
class SieveBoolean { static final int MAX_LIMIT = 40_000_000; public static void main(String[] args) { var sieve = new Boolean[MAX_LIMIT + 1]; for (int i = 2; i <= MAX_LIMIT; i++) sieve[i] = true; for (int i = 3; i * i <= MAX_LIMIT; i += 2) { if (sieve[i]) { int i2 = i + i; for (int j = i + i2; j <= MAX_LIMIT; j += i2) { sieve[j] = false; } } } var primes = new java.util.ArrayList<Integer>(); primes.add(2); for (int i = 3; i <= MAX_LIMIT; i += 2) { if (sieve[i]) { primes.add(i); } } int len = primes.size(); System.out.printf( "%b %b %d %d %d", sieve[MAX_LIMIT - 1], sieve[MAX_LIMIT - 3], len, primes.get(len - 1), primes.get(len - 2)); } }
그런데 특이한 현상이 발견되었습니다. CPU 사용률이 급상승한 것이죠. 보다시피 thread 는 사용되지 않았습니다. 그런데도 6 core, 12 논리적 thread 의 CPU 사용률이 80% 를 넘겼습니다. 저는 GC 와 cache 에 의해 이런 동작을 하지 않을까 싶어서 true, false 에 관해 이미 만들어진 Boolean.TRUE, Boolean.FALSE 객체를 사용하도록 변경해보았는데요. 다음과 같습니다.
class SieveRef { static final int MAX_LIMIT = 40_000_000; public static void main(String[] args) { var sieve = new Boolean[MAX_LIMIT + 1]; for (int i = 2; i <= MAX_LIMIT; i++) sieve[i] = Boolean.TRUE; for (int i = 3; i * i <= MAX_LIMIT; i += 2) { if (sieve[i] == Boolean.TRUE) { int i2 = i + i; for (int j = i + i2; j <= MAX_LIMIT; j += i2) { sieve[j] = Boolean.FALSE; } } } var primes = new java.util.ArrayList<Integer>(); primes.add(2); for (int i = 3; i <= MAX_LIMIT; i += 2) { if (sieve[i] == Boolean.TRUE) { primes.add(i); } } int len = primes.size(); System.out.printf( "%b %b %d %d %d", sieve[MAX_LIMIT - 1], sieve[MAX_LIMIT - 3], len, primes.get(len - 1), primes.get(len - 2)); } }
하지만 별다른 차이를 만들지 못하더군요. CPU 사용률은 여전히 높고, 특히 놀라운 점은 memory 사용량이 변하지 않는다는 것이었습니다. 제가 알고 있는 오래된 Java 에 관한 지식으로는 두번째는 wrapper 객체를 약 4천만개를 만들테고, 세번째는 이미 존재하는 Boolean.TRUE, Boolean.FALSE 를 sieve 배열에서 참조하기만 할텐데 말이죠.
자동 포장 기법은 C# 에서도 존재하는 것을 알기에 동일하게 시도해보았는데요. 이미 내용이 길어졌으므로 source code 는 첨부하지 않겠습니다. 그 결과는 전통적으로 제가 알던 것과 일치했습니다. CPU 사용률은 10% 를 넘기지 못했습니다. object 배열을 통해 자동 포장을 사용하면 memory 사용량이 Java 로 작업했던 것보다 크고 느렸지만, 두개에 대해 참조만으로 동작시키니까 훨씬 빨라지더군요. 여전히 CPU 사용률은 10% 를 넘기지 않았습니다.
이런 결과를 보니 Java 내부에 대해서 의문이 들더군요. CPU 사용률이 매우 높은 것을 보면 뭔가 내부적으로 많은 작업을 하는 것은 알겠고, 기본적인 동작방식이 C# 보다 memory 도 적게 사용하고 빠르니 좋은 것 같지만 참조를 통해서만 동작시키는 것은 왜 별다른 차이를 만들지 못하게 되어 C# 과 같은 전통적인 동작박식보다 느려지게 되었을까요?...
뭔가 다른 개선책이 있을까요? Java 에는 BitSet 이 있다는 것을 알고 있으며 이미 시도해보았습니다. 하지만 제 의문의 범위에는 포함되지 않으므로 거기에 대해서는 다루지 않았으면 합니다.
관심 있으실 분은 별로 없을 것 같지만 그래도 알게 된 바가 있어 덧붙입니다.
최근 Java 20 에서 변화가 있어서 G1 GC 는 개선된 것 같네요. 아마도 다음 변경인 것 같은데 2015년에 개설된 issue 네요.
https://bugs.openjdk.org/browse/JDK-8137022
댓글 달기