Java - native method With System.arraycopy() (Feat. ArrayList)

요즘, 그동안 기본기를 너무 챙기지 않고 프레임 워크와 아키텍쳐에 빠졌나 싶어서, 자료구조와 알고리즘을 다시 보고 있다가, 실질적으로 jdk 의 List 구현체인 ArrayList 를 까서 보았다.

그러다가 흥미로운 것을 보게되었고, 실질적으로 jdk 를 까보는 것도 재미가 있어서 블로깅을 해본다.

다들 알겠지만, ArrayList 는 말 그대로 내부적으로 data 를 저장하는 배열(array) 을 가지고 있다.

자료구조와 알고리즘 공부를 하게되면, 기본중의 기본인 ArrayList 와 LinkedList 의 비교를 하게 된다.

ArrayList 의 add() 메서드는 끝에 집어 넣을 때 O(1) 상수 시간이고, 처음에 집어 넣을 때와 일반적인 상황에서 O(n) 으로 선형 시간이 된다. 

remove() 메서드도 배열의  제일 마지막을 지울 경우 O(1) 상수 시간이고, 처음을 지울 때와 일반적인 상황에서는 O(n) 으로 선형 시간이 된다.

배열을 내부적으로 가지고 있기 때문에, 당연하게 시작 혹은 중간에 data 를 삽입하게 되면
삽입 지점 index 에 있던 원래 있던 data 부터 배열의 끝까지의 모든 데이터들을 다음 index 공간(오른쪽)으로 Shift 연산을 해야 한다. 즉 해당 index 지점부터 배열의 끝까지 순회 하면서 오른쪽으로 한 칸 씩 밀어주게 된다.

반대로 remove 삭제의 경우에도, 시작 혹은 중간에 data 를 지우려고 하면

해당 지점 index 한칸 뒤에 있는 지점부터 배열의 끝까지의 data 들을 한칸 씩 모두 왼쪽으로 Shift 연산을 해야 한다. 즉 해당 index 다음 지점부터 배열의 끝까지 순회 하면서 왼쪽으로 한 칸 씩 밀어주게 된다.

이미지 제작의 귀찮음으로 아래 사이트의 이미지를 사용했다.
https://cloudstudying.kr/lectures/138

그래서 Shift 연산이 필요하기 때문에 선형 시간 O(n) 의 시간 복잡도를 가진다.

자, 그렇다면 이제 JDK 를 까보자.

필자가 까는 JDK 버전은 11 이다.

java.util 패키지 아래의 ArrayList 이다. Object[] 

아래는 끝에 add 하는 메서드이다. 내부적으로 private add(E e, Object[] elementData, ints) 메서드에게 위임한다.

먼저 if 문에서 지금의 배열 사이즈를 체킹하고 배열이 가득찼다면, this.grow() 통해서 배열의 size 를 늘린다. 그리고 배열의 마지막에 대입한다.

아래는 grow() 메서드 이다. 내부적으로 Arrays.copy() 메서드를 통해서 length 를 확장한다.

Arrays.copy() 메서드 또한 System.arraycopy() 메서드와 동일한 성격이지만, 이번 글에서는 다루지 않겠다.

그렇다면, 이제 이번 글의 하이라이트 시작 혹은 일반적으로 배열 중간에 삽입하는 메서드를 보자.

먼저 rangeCheckForAdd() 메서드를 통해서 index 파라메터의 validation 을 한다.

마찬가지로 현재 배열의 크기가 가득 찼는지 확인하고 가득찼다면 grow() 메서드를 통해서 배열의 크기를 증가 시킨다. 그리고 이번글의 메인 이벤트인 System.arraycopy() 메서드를 통해서 오른쪽으로 Shift 연산을 하고 있다. Shift 연산이 끝나면 해당 index 에 element 를 대입하고 사이즈를 증가시키고 add() 메서드가 끝이 난다.

그렇다면 이제 System.arraycopy() 메서드를 한 번 까보자.

우선 System class 를 말하자면, java.lang 패키지 및에 final class 로 static 메서드만을 제공하고 있다.

아래에서 확인할 수 있듯이 final 을 선언함으로 System 은 상속이 더 이상 불가능하며,

생성자 또한 private 접근 제한자로 new 연산자를 사용하지 못하도록 해놓았다.

그렇다면 아래로 내려가서 arraycopy() 메서드를 보자.

@HotSpotInrinsicCandidate 어노테이션과 native 키워드가 눈에 들어온다.

우선 아래 글에서 native 키워드에 대한 설명을 확인할 수 있다.

https://www.baeldung.com/java-native

native method 는 java 가 아닌 C/C++ 와 같은 다른언어로 구현된 method 이다.

또한 method body 가 없고 구현은 하지 java 가 아닌 low level language 로 구현된다.

아래에 문법의 예시를 통해 알 수 있다.

[ public | protected | private] native [return_type] method ();

그렇다면, native method 는 언제 사용 하느냐?

1. 다른 PL 로 작성된 시스템 호출 혹은 라이브러리의 인터페이스 구현을 위해서

2. 다른 PL 로만 접근 가능한 시스템 혹은 하드웨어 자원에 대하여 접근 할 때

3. C / C++ 로 작성된 기존 레거시 코드를 java 어플리케이션에 통합 시킬 때

4. Java 로 작성된 임의의 코드로 컴파일 되어 동적으로 로드 되는 라이브러리를 호출 할 때

@HotSpotIntrinsicCandiate 어노테이션에 대해서 조금 더 찾아보고 공부해봐야 겠지만,

일단 HotSpot 은 JVM 을 의미한다.

내가 아는 JVM 종류는 HotSpot, openj9 으로 알고 있다. 물론 이 둘의 차이점이 뭐고 장단점이 무엇인지는 전혀 모른다. JVM 공부도 해야겠다고 느꼈다.

아래 링크에서 확인할 수 있는 내용이 있다.

http://hg.openjdk.java.net/jdk9/jdk9/jdk/file/tip/src/java.base/share/classes/jdk/internal/HotSpotIntrinsicCandidate.java

해당 어노테이션에 대한 설명을 주석으로 작성해놓았다.

HotSpot 은 가상 머신이다. 앞서 내가 작성했던 내용과 일치한다. 해당 메서드는 HotSpot VM 에 본질적임을 나타내는 어노테이션이라고 한다. 해당 어노테이션이 붙은 메서드는 assembly 또는 compiler IR 을 통해서 성능을 향상할 수 있다고 한다.

내가 이해한 바로는 보다 low level language 에 초점이 되어 있다. 아무래도 메모리를 직접적으로 다루는 managed language 로 구현한다면 성능측에서 이점이 있을 수 있다고 생각한다. 혹은 다른 언어와 대통합을 위해서 존재하는 듯 하다. 이는 더 공부를 해봐야 할 부분이라고 느꼈다.

그렇다면, 다시 돌아와서 System.arraycopy() 메서드가 하는 일이 무엇인지 알아보고 마무리하겠다.

앞서 ArrayList 의 경우 처음 혹은 일반적으로 중간에 삽입 혹은 삭제를 하게 되면 오른쪽으로 Shift 연산을 하게 된다. 따라서 선형 시간이 걸리게 된다. 이는 당연하게도 array 의 길이가 길어질수록 성능 이슈가 발생한다.

따라서 Shift 연산을 보다 우수한 성능으로 low level 에서 할 수 있도록 native method 를 사용한 것으로 추측된다. 일반적으로 java 로 구현한 array Shift 연산 보다 assembly 혹은 C 와 같은 언어로 array 의 Shift 연산을 해주는 것이 훨씬 빠를것이라고 생각한다. 각각의 언어마다 장단점이 있는것은 누구나 알고 있다.

그래서 정리하자면 ArrayList 의 add() 혹은 remove() 의 내부적인 array Shift 연산을 성능적으로 도와주는 메서드가 System.arraycopy() 라고 정리할 수 있겠다.

이번글은 여기서 마무리하겠다.

이번 정리를 통해서, JVM 과 보다 더 low 한 영역에 대해서 공부가 필요하다는 점을 많이 느꼈다.