Taewoo An
Taewoo An
Images       
Benchmark: cargo criterion --bench sequential (only run bench_string_vs_btreemap) Envirnment: - SW: Windows 10 Pro 10.0.19043 Build 19043, WSL 2 Ubuntu 20.04(5.10.16.3-microsoft-standard-WSL2), w/ other minor programs running (Chrome, etc...) - HW:...
MacBook Air (M1, 2020)에서 `debug_art`를 돌려서 각 struct의 size를 구해보면 다음과 같다. ```text V is 8 byte. NodeV is 24 byte. NodeHeader is 16 byte. Node is 8 byte. Node4...
와 이거 언제 뜯어 고치냐...
조금 고민해봤는데, 어차피 실제로 DB 짤 때는 이거 안 쓸 거 같아서, ascii(or base64급)에 맞게 최적화한 ART 만드는 거름으로 쓰는 게 좋을 듯? 이거는 그냥 legacy로 두면 뭐 기념비적일 듯
아니 근데 진짜 생각 열심히 해봤는데, `head != tail && head.next == NULL`이 어떻게 가능한건지 이해가 안 감...
- https://core.ac.uk/download/pdf/144148591.pdf - https://www.researchgate.net/profile/Faith-Ellen/publication/221344000_Non-blocking_Binary_Search_Trees/links/09e4150a26e6f2d9de000000/Non-blocking-Binary-Search-Trees.pdf - https://arxiv.org/pdf/1712.05020.pdf - https://imada.sdu.dk/~kslarsen/Papers/Resources/LF96j/paper.pdf - https://wiki.eecs.yorku.ca/course_archive/2010-11/W/6490A/_media/public:elise.pdf
B-Tree가 AVL Tree나 RB Tree와는 다르게 단순히 removal에서 비워놓고 나중에 치우는 구조가 불가능하다. 왜냐하면 edge로부터 채워넣는게 크기가 안 맞으면 거의 불가능하기 때문... 위의 논문들에서도 인접한 sibling으로부터 값을 가져온다는 등의 전략을...
일단은 다음과 같이 분석을 하였다. - B-tree를 쓰기는 좋지 않다. 왜냐면 removal시 successor나 predecessor와 replace하고 제거하는 것이 일반적인 invariant인데, concurreny 환경에서는 이게 상당한 bottleneck이 되기 때문이다. - 설령 위의 문제를...
https://dev.to/gh-campus-experts/create-your-first-github-bot-with-probot-e6o