자바 성능 튜닝 이야기 요약 (ch1 - 8)Table of Contents1. desdign pattern1.1. Transfer Object1.2. Service Locator2. APM3. String3.1. string builder3.2. string buffer4. Collection4.1. Set4.1.1. HashSet4.1.2. TreeSet4.1.3. LinkedHashSet4.2. red black tree4.3. List4.3.1. Vector4.3.2. ArrayList4.3.3. LinkedList4.4. Map4.4.1. HashTable4.4.2. HashMap4.4.3. TreeMap4.4.4. LinkedHashMap4.5. Queue4.5.1. priorityQueue4..
1. CAS 일반적으로 쓰는 락은 소프트웨어 락으로, 인스트럭션이 굉장히 많이 소모 된다. 하드웨어 lock은 CAS를 어셈으로 구현하고, compare and set을 수행될 때까지 루프를 도는 spin lock을 말한다. lock에 소모되는 인스트럭션 수가 적어 훨씬 빠르다. 하지만 spin lock이니 lock acquire까지 너무 많은 시간이 소요될 경우 비효율 적이다. 어셈으로 구현되다 보니, 아키텍쳐마다 구현이 다르다. DPDK에서 지원하는 락이 CAS로 구현되어 있다. 2. RCU read-copy-update. publish and subscribe 모델의 일종. read가 읽고 있을때 update가 발생하면 복사본을 만든다. read가 다 읽으면 reader가 바라보고 있는 포인터를 새..
vip hash lookup시 조회 안되는 문제 해결 key 계산시 잘못된 key length 문제였음.attribute packed가 없어서 2바이트가 추가 됨.stack에 해시 테이블을 두면 이 2 바이트가 0이지만 heap 에 두면 키의 끝 2바이트에 쓰레기 값.vip struct가 8바이트가 아닌 6바이트로 처리되도록 attribute packed 붙임. /* packed가 안되어 있으면 끝에 0이 아닌 바이트가 더 붙어서 cmp 가 비정상 동작함. 4바이트로 안떨어지는 ipv4_vip의 경우 packed 필요. (sizeof(ipv4_vip)가 8이 아닌 6임을 보장 받으려면 packed 필요) */ typedef struct ipv4_vip{ uint32_t ip; uint16_t port; ..
consistent hash는 bucket이 추가되더라도, 추가된 버킷으로 이동한 엘리먼트를 뺀 나머지 엘리먼트는 버킷의 변화가 없는 해시를 말한다. 가장 대표적인 게 링에 버킷 구역을 끼워 넣는 karger hash... 근데 대부분의 해시는 버킷 밸런스가 매우 안 좋은 편이다. jump consistent hashgoogle에서 jump consistent hash를 만들었다.버킷이 n개일 때 1개가 추가되면 1(n+1)의 확률로 새로 추가 된 버킷으로 옮겨간다. 이 아이디어를 그대로 옮기면 다음이 된다. ---------------------------------------------------------------------- int ch(int key, int num_buckets) { rand..
c coding convention Table of Contents 1. Name 1.1. functon name 1.2. unit name 1.3. structure name 1.4. variable names on the stack 1.5. poineter name 1.6. global variables 1.7. global constants 1.8. macro name 1.9. enum names 1.10. header file guards 2. formatting 2.1. brace placement 2.2. add comment to end bracelet 2.3. characters in one line 2.4. if then else format 2.5. condition formatting..
Table of Contents 1. ch. 2 1.1. shell 실행 1.2. shell 이란 1.3. permission 1.4. 스크립트 실행 2. ch.3 shell variables and env 2.1. system variable 2.2. variable 사용 2.3. default variable 2.4. naming 2.5. echo 2.6. printf 2.7. quoting (expansion) 2.8. backslash 기타 기능 2.9. export 2.10. unset 2.11. read ( user input) 2.12. arithmetic operation 2.13. readonly (constant var) 2.14. variable null check 2.15. cust..
1. n writer, n reader semaphore 사용. 매우 느림. 심지어 wait 상태도 busy.....하므로 2. n writer, 1 reader writer들과 reader의 자원을 분리한다. writer의 업데이트를 reader에 알려주는 방식으로 reader 스레드가 업데이트를 받아 직접 자료를 수정하고 읽는다. 3. 1 writer, n reader RCU 사용. (read copy update) writer가 자원을 미러링한 후 수정 -> reader에게 새로운 자원 포인터 넘김 * 3의 경우가 가장 많은 경우 커널엔 RCU가 구현되어있지만 (http://jake.dothome.co.kr/rcu/) 유저레벨 개발에선 직접 RCU를 구현해야 함.
The rule to map a key to its bucket can simply be to use the key signature (modulo the number of table buckets) as the table bucket ID: bucket_id = f_hash(key) % n_buckets; By selecting the number of buckets to be a power of two, the modulo operator can be replaced by a bitwise AND logical operation: bucket_id = f_hash(key) & (n_buckets - 1);
* 일반 해시테이블의 한계 일반 해시테이블의 경우 검색이 O (1 + a)인데, 리사이징을 하지 않는 경우, a의 바운더리에 대한 보장이 없다. 이 문제를 해결하는 해시테이블 형태가 있는데 robinhood hash O(log n) , cuckoo hashing O (1), FKS hashing O (1)이 있다. cuckoo hashing은 검색이 O (1)이다! dpdk에서 지원하는 해시 라이브러리기도 하다. dpdk 라이브러리를 보다가 cuckoo hashing이 나와서 찾아봤다. 스탠포드 cs166datat structure렉처 노트를 참고했다. * 동작 해시 테이블은 두 개를 준비하고, 1 번 테이블에 원소를 넣는다. . 만약 해당 엔트리가 차 있을 경우에는 2 번 테이블에 원소를 넣는다. 만약..