cgiosy.dev

현대 CPU는 코어 당 한 사이클에 최대 3 - 4개 정도의 micro intrinsics를 처리 가능하다. 하지만 고도로 최적화된 프로그램이 아닌 한, 상당수가 기껏해야 0.5개 정도를 쓰는 것에 그친다. 여기엔 여러 이유가 있으나, 보통 메모리 레이턴시가 주 원인이다. CPU가 아무리 병렬화, OoO를 위해 노력해도 메모리를 읽어와야 해서 흐름이 끊기거나, 명령어들이 서로 아주 긴밀하게 얽혀 있는 등의 상황에선 성능을 완전히 활용할 수 없는 것이다. 이를 위해 메모리 읽기를 비롯한 각종 연산 사이에 동일 코어에 배정된 다른 스레드를 실행하는 기술이 고안됐고, 이것이 하이퍼스레딩이다. 활성화할 경우 한 코어 위에서 여러 프로그램들이 돌아갈 때나, 멀티스레드 프로그램의 경우 성능이 유의미하게 향상되는 편..

$k$차원 평면에서 점 $N$개, 초직사각형 $Q$개가 주어진다. 단, 각 초직사각형에 대해 원소가 $\infty$ 혹은 $-\infty$로만 이뤄진 점이 하나 존재해야 한다. 주어진 점 집합에 단일 점을 추가하는 어떤 연산 $*$에 대해, 각 초직사각형 내부의 점들을 해당 연산으로 합친 결과를 구해야 한다. 여기서 모스(Mo's) 알고리즘을 사용하면, 특정 연산들을 사용 가능할 때 $O(NQ^{1 - \frac{1}{k}})$ 정도에 문제를 해결할 수 있다. 2차원 모스 알고리즘이 가장 자주 사용되는 상황으로 예를 들어보자. 크기 $N$의 배열 $A$와 $[l, r]$ 구간 쿼리 $Q$개가 주어진다. 그러면 2차원 평면에서 $A$의 $i$번째 원소는 좌표 $(i, i)$에 위치하며 값 $A_i$..

순서 보존 (문자열, 순열 등) 이 경우, 라빈 카프 해싱으로 잘 알려진 $\sum_{i=1}^{n}{c^{n-i} A_i}$를 쓰는 게 일반적이다. 그냥 쓰긴 너무 크니까 보통 적당한 자연수 $m$로 나눈 나머지를 쓰는데, $c$와 $m$이 서로소이며 $A_i$의 최댓값보다 커야 품질이 좋다. $A_i$보다 작으면 서로 다른 $A$가 동일한 해시값을 가질 수 있다. ($\mod m$을 안 붙였을 때 기준) 즉 중복이 발생한다. $c$와 $m$이 서로소가 아니면 $\mod m$ 했을 때 0 나오기 쉽다. 그리고 굳이 이게 아니어도 딱히 좋진 않을 듯 $c$를 $m$의 원시근으로 잡으면 좋긴 한데, 사실 PS 범위에선 그까진 필요없고 $c^0, ..., c^{1,000,000}$에서 중복이 없는 정도면 충..

HTTP Proxy Server Benchmarks h2load를 사용해 리버스 프록시 서버로서의 H2O와 Nginx를 벤치마크 및 비교해 보았다. HTTP/2와 HTTP/3 각각에 대해 테스트하였고, 벤치마크 명령어를 다섯 번 실행하여 시간이 가장 적게 소모된 경우를 뽑았다. Configurations H2O 2022년 1월 8일 기준 최신 커밋을 빌드하였으며, ECDH Curves 관련 PR을 적용했다. h2o.conf send-server-name: OFF access-log: /app/log/h2o-access.log error-log: /app/log/h2o-error.log error-log.emit-request-errors: ON hosts: "localhost": listen: &www_..

인터넷을 확인해보아도 정확한 자료가 없어 직접 측정 후 정리해 보았다. 적절한 폭과 높이는 흔히 알려진 기준을 기반으로, 두 시간정도 모니터를 뚫어지게 쳐다보며 직접 값을 튜닝해본 결과를 썼다. 영문(알파벳 + 특수 문자, 커닝 포함) 글의 글자 당 평균 너비: 산세리프 (Arial, Pretendard, 산돌네오): 0.45em 세리프 (Times New Roman): 0.4em Reuters-21578 데이터를 넣고 손수 측정해본 결과이다. 굵기는 400 기준이며, 700으로 할 시 0.02em 이내의 차이가 발생했다. 한국어(한글 + 영문자 포함) 글의 글자 당 평균 너비: 산세리프 (Pretendard, 산돌네오, 본고딕): 0.7em 뉴스를 위주로 해 임의의 인터넷 글들을 넣어보며 측정했다. 화..

(아직 미완성인 글이다. 추후 더 정확히 벤치마크해서 자료를 추가할 예정.) 데이터를 통신 및 스트리밍할 때, 대역폭(IO나 네트워크 속도)보다 빠른 압축 알고리즘은 보통 필요치 않다. 이 글에선 사용례에 따라 잘 알려진 압축 알고리즘들을 분류해본다. 오라클 Ampere A1과 맥북 에어 M1 CPU를 기준으로 측정했다. 일반적인 클라우드의 CPU 성능은 이 사이에 존재하는 편이기에, 중간 정도의 값을 테스트해보고 결과에 따라 압축 수준을 낮추거나 높이도록 하자. 싱글 스레드를 기준으로 하며, 멀티 스레드의 경우 대역폭을 CPU의 물리 코어 수로 나눠서 보면 될 것 같다. Disk I/O 읽기와 쓰기에 대한 대역폭이 제한된 것이므로, (원본 크기 + 압축 크기) / 소요 시간 / 1 MiB을 기준으로 계..

일급 함수 있는 언어에서 익명 재귀함수 만드는 테크닉. 재귀함수를 인자로 넘기는 상황이나 딱 한 번만 쓸 때 써봄직하다. 재귀 없는 언어에선 재귀 구현이 가능하게 해주나, 그런 언어는 안 쓰이니 실용성은 없다. Z 컴비네이터에 적당한 규격의 함수, 예를 들어 Z(self => n => (n ? n + self(n - 1) : 0)) 처럼 넣으면 n까지의 합을 구하는 익명 재귀함수를 만들 수 있다. 그래서 이걸 어떻게 만들까? 우선 f에서 자기자신을 호출하기 위해 스스로를 인자로 받아야 하므로, 첫 번째 인자인 self를 f로 채워주는 함수 M = f => f(f)를 선언한다. 그러면 M(f)를 했을 때 self에 f 자신, self => n => ... 부분이 들어갈 것이다. f에선 self(self)를..

https://cgiosy.github.io/posts/lis