연결리스트 vs 배열리스트 선택하기 (+성능 향상 사례)

이 글에서는 연결리스트와 배열리스트의 차이, 그리고 성능 향상 사례를 대해 다룹니다.

연결리스트 vs 배열리스트

연결리스트(LinkedList)

배열리스트(ArrayList)

 

	배열리스트(Array List)	연결리스트(Linked List)
구현 방법	- 배열을 이용하는 방식	- 여러 노드를 연결하는 방식 (노드: 데이터, 다음 노드 주소를 관리하는 객체)
조회	- 데이터가 연속된 공간에 저장 - 배열 0번째 주소 + (배열원소타입 크기 x 인덱스)를 계산하여 데이터 조회 - 시간복잡도: O(1)	- 노드들은 불연속적인 공간에 저장 - 첫번째 노드부터 인덱스에 해당하는 노드에 도착할 때까지 순회 - 시간복잡도: 최악의 경우 O(n)
삽입	- 데이터를 삽입하려는 위치부터 모든 데이터를 한 칸 씩 미루고, 데이터를 삽입 - 배열은 크기가 정적으로 고정되어 있어, 배열이 꽉 차면 동적으로 배열 크기를 늘림 - 시간복잡도: 최악의 경우 O(n)	- 새로운 노드를 삽입하고, 노드 간의 연결관계를 업데이트 - 시간복잡도: O(1)
삭제	- 원하는 데이터를 삭제하고, 다음 위치부터 데이터를 한 칸씩 앞으로 당김 - 공간 낭비를 하지 않도록 동적으로 배열의 크기를 줄임 - 시간복잡도: 최악의 경우 O(n)	- 노드를 삭제하고, 노드 간의 연결관계를 업데이트 - 시간복잡도: O(1)

 

성능 향상 사례

프로젝트를 수행하며 연결리스트를 배열리스트로 수정하여 성능을 향상시킨 사례를 소개하겠습니다.

애플리케이션이 시작되면 다량의 더미 데이터를 데이터베이스에 Insert 하는 기능을 구현하였습니다.

그럼 구현 내용을 살펴보겠습니다.

전체 코드는 https://github.com/korjun1993/compare-linkedlist-arraylist 에서 확인할 수 있습니다.

 

데이터베이스는 단순하게 boarad 테이블 하나로 구성됩니다.

CREATE TABLE IF NOT EXISTS board
(
    id          BIGINT NOT NULL AUTO_INCREMENT,
    title       VARCHAR(100),
    author      VARCHAR(32),
    description VARCHAR(300),

    PRIMARY KEY (id)
);

 

Board 클래스는 데이터베이스의 board 테이블과 매칭되는 엔티티입니다.

@Getter
@Builder
public class Board {
    private Long id;
    private String title;
    private String author;
    private String description;
}

 

BoardRepository 클래스는 데이터 삽입을 담당합니다.

saveAll() 메서드는 매개변수로 전달받은 리스트를 크기가 n인 서브리스트로 분할한 후, 데이터베이스에 batch Insert 합니다. 성능을 측정하기 위해  로그로 소요 시간을 출력하였습니다.  

 

@Slf4j
@Repository
@RequiredArgsConstructor
public class BoardRepository {

    private final JdbcTemplate jdbcTemplate;

    public void saveAll(List<Board> boards, int n) {
        List<List<Board>> partition = Lists.partition(boards, n);
        for (List<Board> subBoards : partition) {
            long startTime = System.currentTimeMillis();
            batchInsert(subBoards);
            long resultTime = System.currentTimeMillis() - startTime;
            log.info("{}ms가 소요됐습니다.", resultTime);
        }
    }

    public void batchInsert(List<Board> subBoards) {
        String sql = "INSERT INTO board (title, author, description) VALUES (?, ?, ?)";

        jdbcTemplate.batchUpdate(sql, new BatchPreparedStatementSetter() {
            @Override
            public void setValues(PreparedStatement ps, int i) throws SQLException {
                Board board = subBoards.get(i);
                ps.setString(1, board.getTitle());
                ps.setString(2, board.getAuthor());
                ps.setString(3, board.getDescription());
            }

            @Override
            public int getBatchSize() {
                return subBoards.size();
            }
        });
    }
}

 

SaveDummyDateRunner 클래스는 스프링 애플리케이션이 시작되면 자동으로 run() 메서드를 수행합니다.

1,000,000 개의 더미 데이터를 지닌 리스트를 생성하여, 앞서 만든 BoardRepository.saveAll() 을 호출하여 더미 데이터를 데이터베이스에 삽입합니다.

@Component
@RequiredArgsConstructor
public class SaveDummyDataRunner implements CommandLineRunner {

    private final BoardRepository boardRepository;

    // application 이 시작되는 시점에 수행되는 로직
    // n 개의 가짜 데이터를 생성하여 DB에 저장
    @Override
    public void run(String... args) {
        int dataSize = 10000000;
        int batchSize = 10000;
        boardRepository.saveAll(dummyData(dataSize), batchSize);
    }

    public List<Board> dummyData(int n) {
        List<Board> boards = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            Board board = Board.builder()
                .title(i + "번째 글의 제목입니다")
                .description(i + "번째 글의 내용입니다")
                .author("작성자" + i)
                .build();
            boards.add(board);
        }

        return boards;
    }
}

 

 

실행 결과

실행해보니 batch Insert 속도가 점점 느려지는 것을 확인할 수가 있습니다.

 

 

그러더니 796,175 ms 동안 커넥션을 사용하지 않아 커넥션이 끊겨버립니다.

 

분석

 

3가지 상황을 의심해봤습니다.

 

1️⃣ 삽입하려는 데이터가 워낙 많아, 객체가 많아져서 FULL GC가 연속적으로 발생하는 상황

2️⃣ 데이터베이스 서버의 자원(Connection, CPU, Memory) 부족 의심

3️⃣ 리스트 자료구조 의심

 

Visual GC 확인 결과 힙 메모리의 여유는 충분했고, 데이터베이스 서버의 자원도 충분했습니다. → 1️⃣ 2️⃣ PASS

 

시간이 점점 오래 걸리는 상황을 보아, 연결리스트의 조회와 밀접한 관련이 있겠다는 생각이 들었습니다. → 3️⃣ 의심...!

그래서 코드를 분석해봤습니다.

 

SaveDummyDataRunner 클래스는 BoardRepository의 saveAll 메서드를 호출합니다. dummyData 메서드를 호출하여 saveAll에 전달하기 위한 매개변수를 생성하고 있습니다. 이 때, 생성하는 리스트 타입이 연결리스트인 것을 확인할 수 있습니다.

 

BoardRepository의 saveAll 메서드 내에서 Guava 라이브러리의 partition() 메서드를 사용합니다. 

 

 

partition() 메서드는 Partition 인스턴스를 반환합니다.

 

Partition 클래스는 get() 메서드를 제공합니다. subList()를 호출하여 원본 리스트의 부분집합을 반환하고 있습니다.

 

BoardRepository의 saveAll 메서드 내에서 반복문으로 List<List<Board>> 타입인 partition을 순회하며, Partition 클래스의 get() 메서드를 사용하고 있습니다. 즉, for 반복문의 subBoards는 saveAll 메서드의 매개변수인 boards의 서브리스트이며, 타입은 연결리스트입니다.

 

batchInsert 메서드 내에서 연결리스트인 subBoards를 조회합니다. 시간이 지날수록 조회 인덱스(i)가 커지면서 조회 속도가 느려졌기 때문에 커넥션 끊김 현상이 발생했던 것입니다.

 

개선 및 개선결과

 

SaveDummyDataRunner의 dummyData 메서드 내에서 생성하는 리스트 타입을 ArrayList 타입으로 변경하였습니다.

 

실행 결과, 훨씬 빠른 속도와 일관된 성능을 보여줍니다.

연결리스트를 사용했을 때, 796,175ms 가 걸렸을 때와 비교해보면 대략 13,000배의 차이입니다.

 

결론

리스트를 사용할 때, 조회 vs 쓰기 중 어느 것을 많이 활용할지 고민하자. 쓰기를 많이 활용한다면 연결리스트를, 조회를 많이 활용한다면 배열리스트를 선택하자.