Flutter - List, ListQueue 처리 속도 비교

List

List 타입은 흔히 볼 수 있는 Collection 타입 중 하나로, 자주 사용하는 타입 중 하나다.
흔히 배열이라고 불리는 이 List 타입은 여러 개의 값을 하나의 변수에 보관하면서
다양하게 활용할 수 있게 해주는 데이터 타입이다.

List를 사용하면서 처리 속도에 대해 고민을 할 정도로 많은 양의 데이터를 삽입할 일이 없었는데
최근 업무를 진행하면서 최소 10만개 이상의 데이터를 다룰 때 겪은 내용을 포스팅하려고 한다.

개인적으로 10만개 정도면 엄청나게 많은 양의 데이터라고 생각하지는 않는다.
그렇기에 큰 고민 없이 당연히 List로 관리하면 되겠지 하며 개발을 진행했다.
원하는 기능을 구현이 끝났고 결과도 잘나와 대수롭지 않게 생각하고 해당 기능을 마무리했었다.
근데 성능 테스트를 진행하면서 최적화가 필요하다는 결론에 도달했고 어느 부분이 문제인지 찾다보니
List를 사용한 특정 부분이 처리 속도 지연에 한 몫을 하고 있다는 것을 알게 되었다.

범인은 List의 여러 메소드 중 removeRange()라는 메소드가 문제였다.
코드 내용 중 주기적으로 특정 List들의 앞부분 데이터를 제거해줄 필요가 있었고
그에 따라 removeRange(0, length)를 사용해서 이를 처리해주는 로직을 추가해주었었는데
이 부분이 생각보다 처리 시간이 많이 소요된다는 것을 알게 되었다.

단순히 리스트에서 데이터 일부만, 그것도 앞쪽의 데이터를 지우는 것뿐인데
왜 이렇게 오래걸리는 것인지 찾아보니 바로 이해할 수 있었다.

List의 경우에는 순서가 있는 배열로 removeRange()나 removeAt()로 데이터를 삭제하게 되면
내부적으로 해당 리스트에 대해 전체 재인덱싱을 진행한다고 한다.
즉, 배열의 자연스러운 연결성을 위해서 전체 데이터가 재정렬에 들어간다는 말이었다.
그러니 당연하게도 removeRange(0, length)를 호출하면 전체 재정렬이 발생하니
에상 외의 지연 시간이 생길 수 밖에 없었던 것이었다.

그럼 실제로는 얼마나 차이가 나는 것인지, 간단하게 비교할 수 있는 예제로 테스트를 진행해봤다.

removeAt(0) vs. removeAt(list.length - 1) vs. removeRange(0, length)

  • 삭제 개수는 2,500개씩 삭제 진행
  • ms단위 보다는 μs단위가 조금 더 비교하기 편해서 μs로 진행
    10,000 100,000 1,000,000
    List.removeAt(0) 61157 μs 467991 μs 4745593 μs
    List.removeAt(list.length - 1) 189 μs 311 μs 263 μs
    List.removeRange(0, length) 253 μs 740 μs 5142 μs

직접 비교해놓고 보니 처리 속도 차이가 말도 안되게 크게 나는 것을 확인할 수 있었다.
여러 번 측정하고 비교해야 조금 더 신뢰성 있는 결과곘지만..
표에 적어둔 결과와 같이 몇번만 해봐도 차이가 분명 있다는걸 알 수 있었다.

removeRange()의 경우, 예상 외로 처리 속도가 빨라서 의외였지만 테스트 코드가 아니라
실제 프로젝트 코드에서는 여러 List에 대해 removeRange()를 수행하는 로직이기 떄문에
야금야금 지연시간이 발생하고 있었다는 것을 추측해볼 수 있었다.

removeRange()를 대체하려면 어떻게 해야할까? 라는 생각과 동시에 그럼 List.insert()는?
하는 생각에 바로 List.add()와 간단하게 비교를 해보았다.

List.add() vs List.insert()

  • ms단위 보다는 μs단위가 조금 더 비교하기 편해서 μs로 진행
    10,000 100,000 1,000,000
    List.add() 103 μs 1876 μs 11243 μs
    List.insert() 92556 μs 7121580 μs 807640533 μs

막연하게 insert가 조금 더 느리겠거니 하고 진행한 테스트인데 결과는 의외였다.
생각한거 보다 훨씬 큰 차이가 나는 것을 알 수 있었고
100만개 결과를 보고나선 함부로 List에 insert를 하면 안되겠구나를 새삼 깨닫게 되었다.

이 모든 테스트는 List로 테스트를 진행한 것인데, 아마 int가 아닌 다른 타입이나
객체를 사용하는 리스트라면 그 차이는 더 벌어질 것으로 예상된다.

그럼 이 상황을 해결해줄 수 있는 대체제는 무엇이 있을지 검색을 해보았다.
답은 의외로 간단하게 List가 아닌 ListQueue라는 타입을 사용하면 된다고 한다.

ListQueue

ListQueue는 이름과 달리 List, 그러니까 배열 보단 말 그대로 Queue라고 보면 된다고 한다.
링크트 리스트니 FIFO/FILO니 하는 타입에 대한 이론적인 설명은 능력이 부족하기 때문에 ..
더 자세한 설명은 아래 참고 링크나 검색을 통해 확인해 보는 것을 추천한다.

각설하고 내 기준 두 타입의 가장 큰 차이점을 간단히 적어보자면 다음과 같다.

  • List : 데이터 추가/삭제가 빈번하지 않고, 데이터 접근이 많을 때 사용
  • ListQueue : 데이터 목록의 앞/뒤로 빈번한 추가/삭제가 있을 때 사용

내 경우에는 데이터 중간 삽입이나 삭제보다는 앞과 뒷 부분에 대해 추가/삭제가
빈번한 로직이기 때문에 ListQueue를 사용하는 것이 더 효율적이라는 것이다.

관련 내용을 확인한 후 기존 로직에 있는 List를 대신해 ListQueue로 마이그레이션을 진행했고 결과는 ..
상당 부분 만족할만큼 처리 속도 개선이 된 것을 확인할 수 있었다.

업무 중 확인했던 부분이라 테스트 데이터를 갖고 있지는 않지만
기억상 대략 5~8ms 만큼의 시간이 줄어들었던 것으로 기억한다.
실시간으로 아주 짧은 시간 내에 데이터를 처리 해야하는 로직이기 때문에
5ms 정도만 시간이 확보되어도 성능에 꽤 많은 영향을 주기 때문에 상당히 만족스러운 결과였다.

내친김에 위의 List 관련 테스트 처럼 ListQueue도 테스트를 진행해보았다.

ListQueue.add() vs ListQueue.addFirst()

  • ms단위 보다는 μs단위가 조금 더 비교하기 편해서 μs로 진행
    10,000 100,000 1,000,000
    ListQueue.add() 51 μs 542 μs 6214 μs
    ListQueue.addFirst() 64 μs 838 μs 5750 μs

List.removeFirst() vs. List.removeLast()

  • 삭제 개수는 전체 개수
  • ms단위 보다는 μs단위가 조금 더 비교하기 편해서 μs로 진행
    10,000 100,000 1,000,000
    ListQueue.removeFirst() 74 μs 688 μs 7461 μs
    ListQueue.removeLast() 61 μs 674 μs 6478 μs

테스트를 해보니 앞뒤 데이터 처리에는 ListQueue가 List보다 조금 더 빠른 것을 알 수 있었다.
다만, 테스트 결과의 단위를 보면 ms가 아닌 μs기 때문에 실제 체감 할만큼의 차이는 아닐 수도 있다.
프로그램 입장에서야 차이가 있는 것이지만 나 처럼 매우 짧은 시간에 그런 처리를 하는 상황이 아니라면
큰 차이를 못 느낄 수도 있을 것 같다.

결론적으론 리스트 데이터의 선입선출이나 선입후출이 빈번하게 발생하는 경우가 예상된다면
List가 아닌 ListQueue를 사용하는게 속도면에서 조금이라도 이득을 챙길 수 있다는 점을 알 수 있었다.
개인적으로 여러 Collection 타입 중 List를 다소 무분별하게 사용하곤 했었는데 이번 경험을 통해
새삼 모르고 있던 다양한 Collection들이 있다는 걸 알았고, 적재적소에 필요한 요소를
잘 파악해서 적용하는 것도 개발자로써 필요한 요소가 아닌가 하는 생각이 들었다.

아는 것만 사용하면 편하지만 ..
좀 더 적극적으로 좋은 대체제를 찾아내는 습관도 생기면 좋지 않을까?

참고 링크