블로그 이미지
평범하게 살고 싶은 월급쟁이 기술적인 토론 환영합니다.같이 이야기 하고 싶으시면 부담 말고 연락주세요:이메일-bwcho75골뱅이지메일 닷컴. 조대협


Archive»


 

'resize'에 해당되는 글 1

  1. 2016.02.05 dynamic array resizing에 대해서. (5)
 

dynamic array resizing에 대해서.

프로그래밍/알고리즘 | 2016. 2. 5. 02:52 | Posted by 조대협

알고리즘쪽을 파다보니 재미있는게, 예전에 알았던 자료 구조도 구현 방식등에 대해서 다시 되짚어 볼 수 있는게 좋은데. (그간 생각하던 구현 방식과 다른 방식도 종종 나와서.)


보통 메모리 문제 때문에 불확실한 데이타 크기를 가지는 데이타 구조는 LinkedList를 사용하는게 유리하다고 생각했는데, 내용중에, 배열을 사용하고, 배열이 다 차면 그크기를 늘리는 (새롭게 더 큰 배열을 만들어서 기존 배열 내용을 복사해서 대처 하는것) 방식 (Array Resize)를 봤다.  일반적인 방식이기는 하지만 메모리 소모량이나 배열 복사 속도 때문에 그다지 바람직하다고 생각 안하고 있었는데, JDK내의 Map 클래스의 구현 부분을 보니, 실제로 Map 클래스에서도  array resize를 사용하고 있다.


(출처 : http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.addEntry%28int%2Cjava.lang.Object%2Cjava.lang.Object%2Cint%29 )

꽉 막혀서 생각할 것이 아니라, 이런 방식도 융통성 있게 고려를 해봐야겠다.


본인은 구글 클라우드의 직원이며, 이 블로그에 있는 모든 글은 회사와 관계 없는 개인의 의견임을 알립니다.

댓글을 달아 주세요

  1. Mei 2016.02.05 20:37  댓글주소  수정/삭제  댓글쓰기

    평소에 블로그를 잘 보고 있는 개발자입니다.
    HashMap의 table을 배열이 아니라 List로 만들게 되면,
    탐색시간이 O(n)이 되기 때문에 Hash를 사용하는 의미가 없어져 버립니다.
    Constant time에 접근을 하기 위해서는 반드시 배열을 사용해야 합니다.
    즉, 이 코드에서 table 증가시 array resize를 하는 것은 어쩔 수 없는 측면인 것이죠.

    • 조대협 2016.02.06 01:09 신고  댓글주소  수정/삭제

      의견 감사합니다.
      HashTable의 O(n)의 검색 시간이 나오지 않는 것으로 알고 있습니다.
      index의 충돌이 생겼을때, 충돌을 해결하기 위해서 추가 검색이 발생하고, Linked List를 이용했을 경우에는 n의 검색이 소요 됩니다.
      실제로 JDK 1.8에서는 내부적으로 index에 대한 bucket에 대해서, List 구조로 충돌된 index의 데이타를 사용하고, 해당 index에 대해서 충돌 데이타가 많을 경우에는 Tree구조로 바꿔서 저장하고 있습니다.

      참고 : http://d2.naver.com/helloworld/831311

  2. Mei 2016.02.06 08:04  댓글주소  수정/삭제  댓글쓰기

    HashMap의 table은 일반적으로 이야기하는 bucket이 아닌지요?
    제가 말씀드린 것은 bucket(=table in HashMap)의 탐색 시간을 말씀드린 것입니다.
    즉, bucket 탐색 시간이 constant time (n이 아닙니다)이 되기 위해서는 array가 되어야 하는 것이죠.
    동일 hash를 갖는 bucket 내부의 element 들은 아래 get함수를 보면 아시겠지만 실제로 linked list 입니다.
    http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.get%28java.lang.Object%29

  3. kisow 2016.02.11 19:49  댓글주소  수정/삭제  댓글쓰기

    안녕하세요^^. 저도 블로그를 구독해 보고 있는 개발자입니다.
    다양한 분야의 좋은 글들 많이 읽고 있습니다.
    매번 읽기만 하다가 관심있는 주제라 글을 남겨봅니다.

    Mei님 말씀처럼 HashTable의 bucket access는 자료구조 특성상 O(1) 시간 복잡도가 요구되므로
    bucket 저장에 Linked List 자료구조는 애당초 의미가 없습니다. chain 방식이나 open address 방식에서
    충돌을 해결하기 위해서 Linked list 유사하게 선형 탐색하는 부분은 버킷크기가 충분히 큰 경우 어짜피 상수처리되기 때문에 중요하지 않구요.
    HashTable bucket에서 dynamic array를 쓰는 것은 본문에 생각하신 이유보다 더 직접적으로는
    HashTable ADT에 기대되는 시간복잡도를 충족시키기 위한 제약사항에 가깝습니다.

    하지만 본문의 중심 생각에는 100% 공감하고 동의 합니다.
    아주 예전에 acmicpc 준비하면서 알고리즘 한참 파던 때는 알고리즘/자료구조의 시간/공간 복잡도가 절대적이라고 생각했었는데,
    최근에 10년가까이 대용량 데이터를 다루다보니 항상 그런 것은 아니더군요.
    N이 충분히 작지 않은 경우에도 기존 시공간 복잡도 분석의 상식을 뒤엎을 만큼 성능에 영향을 미칠 수 있는 시스템 상의 요소들이 많고,
    H/W나 O/S 같은 하단 인프라가 발전하면서 눈에 보이지 않던 그 영향이 점점 더 커지고 있습니다.
    일만 PC나 commodity server 같은 보편화된 환경에서 특히 더 그런 것 같고요.

    특히 Linked List vs vector(dynamic array) 간의 성능 특성에 대한 상식에 논란이 있습니다.
    몇년 전에 Linked List 이제 그만 쓰고 무조건 vector 쓰라는 주장도 나올 정도로 논란도 됐었고요.
    http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html#more-818
    http://highscalability.com/blog/2013/5/22/strategy-stop-using-linked-lists.html

    극단적으로 얘기해서 그렇지 최적화 관점에서 보면 충분히 의미 있는 지적이라고 생각합니다.
    실제로 저희도 훨씬 이전부터 Linked List를 꼭 써야 하는 경우가 아니면 성능상 vector를 쓰는데, 꼭 Linked List를 써야하는 경우가 많지 않더군요.굳이 꼽자면 사용자 API로 덩치도 크고 복합적인 non-POD 데이터들의 목록을 뽑아줄 때, 성능은 크게 중요하지 않고
    (어짜피 튜닝포인트도 아니고, POD도 아니라 어짜피 최적화도 기대하기 힘들고)
    API 사용자들의 창의적인 조합에도 리소스를 덜 써야 하는 경우에만 썼던 것 같습니다.

    특히 본문에 언급하신 "불확실한 데이터 크기"가 유일한 이유라면 dynamic array resize가 더 낫습니다.
    SIMD나 GPGPU까지 가지 않더라도 아래와 같은 이유 때문에라도 dynamic array를 쓰면서 resize하는게 전체적으로 더 효율적인 선택일 수 있습니다.

    1.
    추가하는건 원소가 작은 POD라면 복사비용 자체도 생각보다 비싸지 않습니다.
    게다가 벌크 복사는 최신 CPU에 맞게 컴파일러가 알아서 최적화(vectorization) 해줄테고,
    메모리 대역폭도 거의 정체된 다른 리소스들에 비해서 아직은 점점 좋아지고 있고요.
    패턴상 realloc 자체가 armotized cost 라 항상 치르는 비용도 아니어서 realloc이 필요 없는 횟수만큼 비용 자체가 분할상환될테고
    미리 예상되는 만큼 적당히 realloc해두면 효과를 볼 수 있어서
    생각보다 dynamic array에서의 실제 추가 비용이 떨어지지 않을 수 있습니다.

    2.
    탐색 비용은 연속적인 array 형태가 불연속 적인 Linked List 보다 압도적으로 좋습니다.
    알고리즘 상 랜덤 엑세스가 가능한 것도 그렇지만 순차 탐색만 놓고 보더라도 지역성 때문에 array가 훨씬 좋습니다.

    보통 컴파일러 최적화 수준에서 데이터 의존성이 없는 경우에 instruction 수행 순서를 바꿔서 명령어 수행의 파이프라이닝을 극대화 하는 경우가 많은데,
    노드를 이동 해봐야 다음 노드 위치를 알 수 있는 Linked List는 이런 최적화를 기대하기 어렵습니다.
    또, H/W 레벨에서 상대적으로 느린 메모리 대역폭을 보완하기 위해서 prefetch 할 수 있는데
    연속된 array는 효과를 볼 수 있겠지만 링크된 데이터 구조에서는 역시 기대하기 어렵습니다.

    게다가 Linked List는 DRAM과 TLB의 지역성에도 않좋은 영향을 미치고 cache 히트율을 떨어뜨립니다.
    불연속적이고 더 잦은 메모리 할당을 하는 Linked List는 리스트 하나가 여러 DRAM 페이지에 흩어질 가능성이 높고
    결과적으로 더 많은 DRAM 페이지를 요구하고 단편화도 있을테니 물리적인 메모리 usage도 올라갈껍니다.
    리스트 하나를 접근하는 관점에서 봐도 사용하는 DRAM 페이지가 많다는건 그만큼 지역성이 떨어지고
    그 자체로 한정된 CPU cache 용량에서 히트율 자체에도 손해를 볼테고요.
    현대 O/S에 보편적인 가상 메모리를 지원하기 위해 CPU에 있는 TLB 역시 DRAM 페이지 번호를 찾기 위한 캐시인 만큼
    요구되는 DRAM 페이지가 많아지면 같은 매커니즘으로 히트율 손해를 볼겁니다.

    어떻게 allocator를 잘 짜서 간접층을 두고 실제로는 연속적인 메모리 공간을 크게 할당하도록 컨트롤하면
    어느 정도 완화는 되겠지만 Linked List에만 있는 링크 자체도 낭비고 그렇게 하는 것 자체가 크게 보면
    dynamic array resizing이고요.

  4. 조대협 2016.02.12 13:55 신고  댓글주소  수정/삭제  댓글쓰기

    의견 감사드립니다. 여러가지로 생각하게 만드는 의견이네요