lua 테이블 단상

2021/08/18

lua의 테이블은 배열이자 맵으로 사용하는데, 배열 속성이 있어서 혹시나 ordered 해시맵 처럼 동작하나 실험해보니 역시나 아니다. 파이썬이나 마찬가지다.

현대 언어에서 해시 자료 구조들은 대부분 해시 값으로 버킷 분기를 태우고 각 버킷의 리스트는 책에서처럼 리스트로 유지하는 것이 아니라 RB트리로 유지하는 것으로 알고 있다. 실제로 O(1)은 아닌 것이다. 어쨌든 키에 의한 탐색은 매우 빠른데, 문제는 요즘에 우리가 하는 일들의 자료구조가 원하는 속성은 이게 다가 아니다.

즉 대규모 데이터의 배치 처리, 통계, 인공지능 연산이라고 치면 필요로 하는 미덕이란 아마도 이럴 것 같다.

1. 키에 의한 빠른 탐색 (존재 체크 포함)은 기본으로 필요하다.
2. 고속 이터레이션 (이것은 캐시를 깨지 않고 물리적으로 연속적으로 배치되어 있음을 말한다. 똘똘하게 짠 많은 벡터 구조들이 단순 할당 리스트가 아니며 캐시 힛트와 고속 이터레이션을 고려하고 있을 것이다. 일반적인 트리는 이렇지가 않다. 그래서 고속화 구현을 하자면 트리를 리스트로 직렬화 했다가 도로 트리로 바꿨다가 하는 고난한 일을 해 본 사람들이 있다.)
3. 일부 삭제는 거의 발생하지 않는다. 대부분 통삽입, 통삭제가 많다. 자료구조의 수명 주기가 길지 않다. 길다해도 삽입 / 삭제 / 갱신이 발생하며 너덜해지는 일이 별로 없다. 그냥 read only 인 경우가 많다. 그래서 보통 내가 하던 일은 트리에 데이터 삽입 완결이 되면, 이에 대해 트리 순회를 하며 인덱스를 벡터로 구축하는 것이다. 삽입 삭제가 발생하면 꽤 복잡한 연산을 수반하게 되겠지만 RO 라고 가정하면 별 일이 아니다. 그리고 뺑뱅이 돌릴 때는 벡터로 찾는다.

그건 그렇고 요즘 들어 함수형 언어나, 내가 즐겨쓰는 파이썬의 map - lambda 류를 보고 있으면 순회가 참 쌈박하다는 느낌이 드는데 이것도 이게 다가 아니다. 스택 오버 플로에서 여러 예제를 찾다보면 이터레이터 안에 IO를 수행하는 일들도 있다. 극단적으로 말하자면 파이썬 식으로 설명해서 yiield 쪽에서 시스템 콜을 매번 호출 할 수도 있다. CSW가 발생해서 시스템 자원 쭉 뽑아 먹는다는 뜻이다. 각 언어가 이터레이터를 구현 할 때 캐시힛팅과 파이프스톨 예방에 중점을 두었을까 싶지만 그 보다는 메모리를 아끼는 스트리밍 처리에 줌점을 뒀을 것 같다. 내가 선호하는 방향은 아니다. 극단까지 가지는 않더라고 CPU 뽑아먹기 좋다. 청크단위 순회 할 일을 바이트 단위로 하는 예제도 가끔 본다. CPU 뽑힌다.

[t:/] is not "technology - root". dawnsea, rss