내 눈 에 보 이 는 Nginx (1): Nginx 와 비트 연산
Nginx 는 성능 으로 유명 하 다. 이것 은 우수한 코드 실현 과 밀접 한 관 계 를 가진다. 본 고 에서 말 하고 자 하 는 비트 연산 도 Nginx 의 우수한 성능 을 추진 하 는 원인 중 하나 이다.
비트 연산 은 Nginx 의 소스 코드 에서 곳곳에서 볼 수 있 습 니 다. 명령 의 유형 (얼마나 많은 파 라 메 터 를 휴대 할 수 있 고 어떤 설정 블록 에 나타 날 수 있 습 니까?) 을 정의 하 는 것 부터 현재 요청 이 완료 되 지 않 은 데이터 가 있 는 지 표시 하 는 것, 그리고 Nginx 이벤트 모듈 에서 포인터 의 최 하위 로 이벤트 가 만 료 되 었 는 지 표시 하 는 것 까지 비트 연산 의 신기 함 과 매력 을 나타 내지 않 습 니 다.
본 고 는 Nginx 소스 코드 의 전형 적 인 비트 연산 사용 을 소개 하고 분석 하 며 다른 비트 연산 기 교 를 확장 하여 소개 할 것 이다.
맞추다
Nginx 내부 에서 메모리 분 배 를 할 때 메모리 시작 주소 의 정렬, 즉 메모리 정렬 (일부 성능 향상 으로 바 꿀 수 있 음) 에 매우 주의 합 니 다. 이것 은 프로세서 의 주소 지정 특성 과 관련 이 있 습 니 다. 예 를 들 어 일부 프로세서 는 4 바이트 너비 로 주 소 를 찾 습 니 다. 이런 기계 에 서 는 0x46b1e 7 에서 시 작 된 4 개의 바이트 를 읽 어야 합 니 다.0x46b1e 7 은 4 바이트 경계 (0x46b1e 7% 4 = 3) 에 있 지 않 기 때문에 읽 을 때 두 번 으로 나 누 어 읽 습 니 다. 0x46b1e 4 에서 시 작 된 4 개의 바이트 를 처음 읽 고 3 바이트 낮 게 꺼 냅 니 다.0x46b1e 8 에서 시 작 된 4 개의 바 이 트 를 읽 고 가장 높 은 바 이 트 를 꺼 냅 니 다.읽 기와 쓰기 메모리 의 속도 가 CPU 와 일치 하지 않 는 다 는 것 을 알 고 있 습 니 다. 그러면 두 번 의 읽 기 는 분명히 더 큰 비용 을 가 져 왔 습 니 다. 이것 은 명령 의 정 체 를 일 으 키 고 CPI (명령 주기 수) 를 증가 시 켜 프로그램의 성능 을 손상 시 킬 수 있 습 니 다.
그래서 Nginx 는 정렬 작업 을 하기 위해 매크로 를 봉 인 했 습 니 다.
#define ngx_align(d, a) (((d) + (a - 1)) & ~(a - 1))
위의 코드 에서 보 듯 이 이 매크로 는 d 를 a 로 정렬 시 키 는데 그 중에서 a 는 반드시 2 의 미터 가 되 어야 합 니 다.
예 를 들 어 d 는 17 이 고 a 는 2 일 때 18 을 얻는다.d 는 15, a 는 4 시 에 16 을 얻는다.d 는 16, a 는 4 시, 16 을 얻는다.
이 매크로 는 사실 d 와 같은 첫 번 째 a 의 배 수 를 찾 고 있다.a 는 2 의 幂 次 이기 때문에 a 의 2 진법 은 00... 1... 00 이라는 형식 을 나타 낸다. 즉, 그것 은 1 개 만 있 기 때문에 a - 1 은 00... 01. 1 이라는 형식 이다. 그러면 ~ (a - 1) 은 낮은 n 위 를 모두 0 으로 설정 하고 그 중에서 n 은 a 낮은 연속 0 의 개수 이다.그래서 이때 우리 가 d 와 ~ (a - 1) 에 게 위치 와 조작 을 한 번 하 라 고 하면 d 의 낮은 n 자 리 를 0 으로 정리 할 수 있 습 니 다. 우 리 는 d 와 같은 수 를 찾 아야 하기 때문에 d + (a - 1) 를 사용 하면 됩 니 다.
비트 맵
비트 맵 은 보통 사물 의 상 태 를 표시 하 는데 '비트' 는 모든 사물 이 하나의 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트 비트
Nginx 에는 공유 메모리 분배 기 (slab) 와 같은 비트 맵 을 사용 하 는 예 가 여러 군데 있 습 니 다. 예 를 들 어 uri (Uniform Resource Identifier) 를 바 꿀 때 하나의 문자 가 보존 문자 인지 (또는 안전 하지 않 은 문자 인지) 판단 해 야 합 니 다. 이러한 문 자 는% XX 로 바 뀌 어야 합 니 다.
static uint32_t uri_component[] = {
0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
/* ?>=< ;:98 7654 3210 /.-, +*)( '&%$ #"! */
0xfc009fff, /* 1111 1100 0000 0000 1001 1111 1111 1111 */
/* _^]\ [ZYX WVUT SRQP ONML KJIH GFED CBA@ */
0x78000001, /* 0111 1000 0000 0000 0000 0000 0000 0001 */
/* ~}| {zyx wvut srqp onml kjih gfed cba` */
0xb8000001, /* 1011 1000 0000 0000 0000 0000 0000 0001 */
0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
0xffffffff /* 1111 1111 1111 1111 1111 1111 1111 1111 */
};
위 에서 보 듯 이 간단 한 배열 은 하나의 비트 맵 을 구성 하고 모두 8 개의 숫자 를 포함 하 며 모든 숫자 는 32 개의 상 태 를 표시 하기 때문에 이 비트 맵 은 256 개의 문자 (확장 ASCII 코드 포함) 를 포함한다.0 의 비트 는 일반적인 문 자 를 표시 합 니 다. 즉, 전의 가 필요 없고 1 의 비트 를 대표 하 는 것 은 전의 가 필요 합 니 다.
그럼 이 비트 맵 은 어떻게 사용 해 야 합 니까?Nginx 는 uri 를 옮 겨 다 닐 때 간단 한 문 구 를 통 해 판단 한다.
uri_component[ch >> 5] & (1U << (ch & 0x1f))
위 에서 보 듯 이 ch 는 현재 문 자 를 표시 합 니 다. ch > > 5 는 ch 오른쪽으로 5 자리 이동 합 니 다. 이것 은 32 로 나 누 는 효 과 를 가 집 니 다. 이 작업 은 ch 가 uri 에 있 음 을 확 인 했 습 니 다.component 의 몇 번 째 숫자 에서;오른쪽 에 있 는, (ch & 0x1f) 는 ch 가 5 자리 낮은 값 을 꺼 냈 는데, 이 값 은 ch 가 대응 하 는 숫자의 몇 번 째 자리 (낮은 값 에서 높 은 계산) 에 있 음 을 나타 낸다.따라서 좌우 양쪽 의 값 을 한 번 에 위치 와 조작 을 한 후에 ch 문자 가 있 는 비트 맵 상 태 를 꺼 냈 다.예 를 들 어 ch 는 '0' (즉 숫자 48) 으로 비트 맵 의 두 번 째 숫자 (48 > > 5 = 1) 에 존재 하고 이 숫자 (0xfc 009 fff) 의 16 위 에 존재 하기 때문에 그의 상 태 는 0xfc 009 fff & 0x 10000 = 0 이기 때문에 '0' 은 통용 되 는 문자 로 의 미 를 바 꾸 지 않 아 도 된다.
위의 이 예 에서 우 리 는 또 다른 비트 연산 의 기 교 를 볼 수 있다. 즉, 2 의 멱 차 의 수 를 모델 링 하거나 제거 작업 을 할 때 비트 연산 을 통 해 실현 할 수 있다. 이것 은 직접적인 나눗셈 과 모델 링 연산 보다 더 좋 은 성능 을 가진다. 비록 적당 한 최적화 단계 에서 컴 파일 러 도 우 리 를 위해 이런 최적화 를 완성 할 수 있다.
최 하위 1 의 위 치 를 찾다
이어서 우 리 는 다른 응용 기 교 를 소개 한다.
숫자 2 진법 에서 가장 낮은 1 의 위 치 를 찾 으 면 직관 적 으로 위치 에 따라 옮 겨 다 니 는 것 을 생각 할 수 있 습 니 다. 이런 알고리즘 은 시간 이 복잡 하고 O (n) 이 며 성능 이 만 족 스 럽 지 못 합 니 다.
만약 당신 이 나무 모양 의 배열 을 접 한 적 이 있다 면, 당신 은 이것 에 대해 다른 견 해 를 가지 게 될 것 입 니 다. 나무 모양 배열 의 핵심 개념 은 lowbit 를 계산 하 는 것 입 니 다. 즉, 하나의 숫자 2 진법 에서 가장 낮은 1 의 멱 차 를 계산 하 는 것 입 니 다.그것 이 좋 은 시간 복잡 도 (O (logN) 를 가 진 이 유 는 O (1) 나 상수 의 시간 안에 답 을 얻 을 수 있 기 때문이다.
int lowbit(int x)
{
return x & ~(x - 1);
}
이 기 교 는 사실상 상술 한 정렬 방식 과 유사 하 다. 예 를 들 어 x 는 00... 111000 이라는 숫자 는 x - 1 이 00... 110111 이 되 고 반대로 하면 원래 x 저 위 연속 0 이 있 는 위 치 를 0 으로 다시 놓는다 (원래 최 저 위 1 의 위 치 는 1 이다). 우 리 는 최 저 위 1 의 위 치 를 제외 하고다른 위치 에 있 는 값 과 x 는 모두 반대 되 기 때문에 이들 이 위치 와 조작 을 한 후에 결과 에 1 만 있 을 수 있 고 원래 x 의 가장 낮은 1 이다.
가장 높 은 자리 1 찾기
문 제 를 바 꾸 자 면 이번 에는 최 하위 가 아니 라 최고 위 를 찾 는 1 이다.
이 문 제 는 실제 적 인 의 미 를 가진다. 예 를 들 어 best - fit 메모리 풀 을 설계 할 때 우 리 는 사용자 가 기대 하 는 size 보다 큰 첫 번 째 2 의 멱 을 찾 아야 한다.
마찬가지 로, 너 는 아마도 먼저 두루 돌아 다 니 는 것 을 생각 할 것 이다.
사실 Intel CPU 명령 집합 에는 이러한 명령 이 있 습 니 다. 바로 하나의 바 이 너 리 에서 가장 높 은 1 의 위 치 를 계산 하 는 것 입 니 다.
size_t bsf(size_t input)
{
size_t pos;
__asm__("bsfq %1, %0" : "=r" (pos) : "rm" (input));
return pos;
}
이것 은 매우 좋 지만, 여기 서 우 리 는 여전히 비트 연산 으로 이 1 의 위 치 를 찾 기 를 기대한다.
size_t bsf(size_t input)
{
input |= input >> 1;
input |= input >> 2;
input |= input >> 4;
input |= input >> 8;
input |= input >> 16;
input |= input >> 32;
return input - (input >> 1);
}
이것 이 바로 우리 가 기대 하 는 계산 방식 이다.우 리 는 이 계산의 원 리 를 분석 해 보 자.
설명 이 필요 한 것 은 계산 해 야 할 값 이 32 자리 라면 위의 함수 의 마지막 input | = input > > 32 는 필요 하지 않 습 니 다. input | = input > > m 를 구체 적 으로 몇 번 실행 하 는 지 는 input 의 비트 길이 에 의 해 결 정 됩 니 다. 예 를 들 어 8 자 리 는 3 번, 16 자 리 는 4 번, 32 자 리 는 5 번 입 니 다.
더욱 간결 하 게 설명 하기 위해 서 우 리 는 8 자리 숫자 로 분석 하고 하나의 숫자 A 를 설정 합 니 다. 그의 바 이 너 리 는 다음 과 같 습 니 다.
A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0]
위의 계산 과정 은 다음 과 같다.
A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0]
0 A[7] A[6] A[5] A[4] A[3] A[2] A[1]
---------------------------------------
A[7] A[7]|A[6] A[6]|A[5] A[5]|A[4] A[4]|A[3] A[3]|A[2] A[2]|A[1] A[1]|A[0]
0 0 A[7] A[7]|A[6] A[6]|A[5] A[5]|A[4] A[4]|A[3] A[3]|A[2]
--------------------------------------------------------------------------
A[7] A[7]|A[6] A[7]|A[6]|A[5] A[7]|A[6]|A[5]|A[4] A[6]|A[5]|A[4]|A[3] A[5]|A[4]|A[3]|A[2] A[4]|A[3]|A[2]|A[1] A[3]|A[2]|A[1]|A[0]
0 0 0 0 A[7] A[7]|A[6] A[7]|A[6]|A[5] A[7]|A[6]|A[5]|A[4]
---------------------------------------------------------------------------------------------------------------------------------
A[7] A[7]|A[6] A[7]|A[6]|A[5] A[7]|A[6]|A[5]|A[4] A[7]|A[6]|A[5]|A[4]|A[3] A[7]|A[6]|A[5]|A[4]|A[3]|A[2] A[7]|A[6]|A[5]|A[4]|A[3]|A[2]|A[1] A[7]|A[6]|A[5]|A[4]|A[3]|A[2]|A[1]|A[0]
우 리 는 최종 A 의 최고 위 치 는 A [7] 이 고, 다음 위 치 는 A [7] | A [6] 이 며, 세 번 째 위 치 는 A [7] | A [6] | A [5] | A [2] | A [1] | A [7] | A [6] | A [5] | A [4] | A [3] | A [2] | A [1] | A [0] | A [0] 를 볼 수 있다.
가장 높 은 1 이 m 위 (오른쪽 에서 왼쪽으로 계산 하고 가장 낮은 것 을 0 위 라 고 한다) 라 고 가정 하면 이때 의 낮은 m 위 는 모두 1 이 고 다른 높 은 위 는 모두 0 이다.즉, A 는 2 의 모 멱 을 하나 더 줄 일 것 이 므 로 마지막 단계 (input - (input > > 1) 의 의도 도 매우 뚜렷 하 다. 곧 최고 위 를 제외 한 1 을 모두 0 으로 설정 하고 마지막 으로 돌아 오 는 것 은 원래 의 input 에서 가장 높 은 1 의 대응 멱 이다.
계산 1 의 개수
어떻게 하나의 숫자 이 진 표시 안에 몇 개의 1 이 있 는 지 계산 합 니까?
직관 적 으로 (옮 겨 다 니 는 것 은 정말 좋 은 것 이다) 복잡 도 를 계산 해 보 자. 한 바이트 가 O (8) 이 고 네 바이트 가 O (32) 이 며 8 바이트 가 O (64) 이다.
만약 이 계산 이 당신 의 프로그램 에 빈번하게 나타난다 면, 당신 이 perf 와 같은 성능 분석 도구 로 당신 의 응용 프로그램 을 관찰 할 때, 그것 은 아마도 당신 의 관심 을 받 을 것 이 고, 당신 은 어 쩔 수 없 이 최적화 할 방법 을 생각해 야 한다.
사실은 이라는 책 에 이 문제 가 있 습 니 다. 이 문 제 는 기호 가 없 는 긴 숫자 2 진법 에서 1 의 수 를 계산 해 야 합 니 다. 그리고 가장 좋 은 알고리즘 을 사용 하 기 를 바 랍 니 다. 최종 적 으로 이 알고리즘 의 복잡 도 는 O (8) 입 니 다.
long fun_c(unsigned long x)
{
long val = 0;
int i;
for (i = 0; i < 8; i++) {
val += x & 0x0101010101010101L;
x >>= 1;
}
val += val >> 32;
val += val >> 16;
val += val >> 8;
return val & 0xFF;
}
이 알고리즘 은 나의 다른 문장 에서 분석 한 적 이 있다.
0x 0101010101010101 이라는 수 를 관찰 하면 8 명 중 마지막 한 명 만 1 이다.그러면 x 와 그 위 치 를 따 르 면 다음 과 같은 결 과 를 얻 을 수 있 습 니 다.
A[i] x i （0 1）。
：
A[0] + (A[8] << 8) + (A[16] << 16) + (A[24] << 24) + (A[32] << 32) + (A[40] << 40) + (A[48] << 48) + (A[56] << 56)
：
A[1] + (A[9] << 8) + (A[17] << 16) + (A[25] << 24) + (A[33] << 32) + (A[41] << 40) + (A[49] << 48) + (A[57] << 56)
......
：
A[7] + (A[15] << 8) + (A[23] << 16) + (A[31] << 24) + (A[39] << 32) + (A[47] << 40) + (A[55] << 48) + (A[63] << 56)
：
(A[63] + A[62] + A[61] + A[60] + A[59] + A[58] + A[57] + A[56]) << 56 +
(A[55] + A[54] + A[53] + A[52] + A[51] + A[50] + A[49] + A[48]) << 48 +
(A[47] + A[46] + A[45] + A[44] + A[43] + A[42] + A[41] + A[40]) << 40 +
(A[39] + A[38] + A[37] + A[36] + A[35] + A[34] + A[33] + A[32]) << 32 +
(A[31] + A[30] + A[29] + A[28] + A[27] + A[26] + A[25] + A[24]) << 24 +
(A[23] + A[22] + A[21] + A[20] + A[19] + A[18] + A[17] + A[16]) << 16 +
(A[15] + A[14] + A[13] + A[12] + A[11] + A[10] + A[9] + A[8]) << 8 +
(A[7] + A[6] + A[5] + A[4] + A[3] + A[2] + A[1] + A[0])
다음 세 가지 조작:
val += val >> 32;
val += val >> 16;
val += val >> 8;
매번 val 을 반 으로 접어 서 더 합 니 다.
첫 번 째 반 으로 접 기 (val + = val > > 32) 후 얻 은 val 의 낮은 32 비트:
(A[31] + A[30] + A[29] + A[28] + A[27] + A[26] + A[25] + A[24] + A[63] + A[62] + A[61] + A[60] + A[59] + A[58] + A[57] + A[56]) << 24 +
(A[23] + A[22] + A[21] + A[20] + A[19] + A[18] + A[17] + A[16] + A[55] + A[54] + A[53] + A[52] + A[51] + A[50] + A[49] + A[48]) << 16 +
(A[15] + A[14] + A[13] + A[12] + A[11] + A[10] + A[9] + A[8] + A[47] + A[46] + A[45] + A[44] + A[43] + A[42] + A[41] + A[40]) << 8 +
(A[7] + A[6] + A[5] + A[4] + A[3] + A[2] + A[1] + A[0] + A[39] + A[38] + A[37] + A[36] + A[35] + A[34] + A[33] + A[32])
두 번 째 반 으로 접 기 (val + = val > > 16) 후 얻 은 val 의 낮은 16 비트:
15] + A[14] + A[13] + A[12] + A[11] + A[10] + A[9] + A[8] + A[47] + A[46] + A[45] + A[44] + A[43] + A[42] + A[41] + A[40] + A[31] + A[30] + A[29] + A[28] + A[27] + A[26] + A[25] + A[24] + A[63] + A[62] + A[61] + A[60] + A[59] + A[58] + A[57] + A[56]) << 8 +
(A[7] + A[6] + A[5] + A[4] + A[3] + A[2] + A[1] + A[0] + A[39] + A[38] + A[37] + A[36] + A[35] + A[34] + A[33] + A[32] + A[23] + A[22] + A[21] + A[20] + A[19] + A[18] + A[17] + A[16] + A[55] + A[54] + A[53] + A[52] + A[51] + A[50] + A[49] + A[48])
세 번 째 반 으로 접 기 (val + = val > > 8) 후 얻 은 val 의 낮은 8 자리:
(A[7] + A[6] + A[5] + A[4] + A[3] + A[2] + A[1] + A[0] + A[39] + A[38] + A[37] + A[36] + A[35] + A[34] + A[33] + A[32] + A[23] + A[22] + A[21] + A[20] + A[19] + A[18] + A[17] + A[16] + A[55] + A[54] + A[53] + A[52] + A[51] + A[50] + A[49] + A[48] + A[15] + A[14] + A[13] + A[12] + A[11] + A[10] + A[9] + A[8] + A[47] + A[46] + A[45] + A[44] + A[43] + A[42] + A[41] + A[40] + A[31] + A[30] + A[29] + A[28] + A[27] + A[26] + A[25] + A[24] + A[63] + A[62] + A[61] + A[60] + A[59] + A[58] + A[57] + A[56])
이 를 통 해 알 수 있 듯 이 세 번 의 반절 을 거 쳐 64 자리 의 수 치 를 모두 8 자리 까지 누적 한 다음 에 8 자리 낮은 수 치 를 꺼 내 는 것 이 바로 x 라 는 숫자 2 진법 에서 1 의 숫자 이다. 이 문 제 는 수학 적 으로 '한 명 무 게 를 계산 하 는 것' 이 라 고 부른다.
비트 연산 은 독특한 장점 (간결, 성능 봉) 으로 프로그래머 를 끌 어 들 인 다. 예 를 들 어 LuaJIT 는 bit 라 는 모듈 을 내장 하여 프로그래머 가 Lua 프로그램 에서 비트 연산 을 사용 할 수 있 도록 한다.비트 연산 을 배 우 는 것 은 프로그래머 에 게 도 진보 이 므 로 우리 가 계속 연구 할 만하 다.
추천 읽 기:
클 라 우 드 오픈 레 스 티 / Nginx 서비스 최적화 실천
클 라 우 드 딩 설 봉: 자체 캐 시 구성 요소 BearCache, CDN 디스크 응답 속도 38%
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
