equal의 동작 방식과 최적화

 

 

 

python에서 string 타입의 equal이 어떻게 동작하는지 궁금해 찾아보며 공부한 내용을 기록합니다.

 

파이썬은 문법은 파이썬을 따르지만, 그 내부 동작 원리는 C언어를 기본으로 합니다.

 

아래의 링크에서 모든 파이썬 API가 내부적으로는 C언어로 만들어져 있는 것을 확인할 수 있죠

https://github.com/python/cpython

GitHub - python/cpython: The Python programming language

 

 

많고 많은 함수 중 제가 집중해본 함수는 unicode_eq 라는 함수입니다.

출처: https://github.com/python/cpython/blob/main/Objects/stringlib/eq.h

 

해당 함수는 아래와 같이 생겼습니다.

Py_LOCAL_INLINE(int)
unicode_eq(PyObject *a, PyObject *b)
{
    if (PyUnicode_GET_LENGTH(a) != PyUnicode_GET_LENGTH(b))
        return 0;

    if (PyUnicode_GET_LENGTH(a) == 0)
        return 1;
        
    if (PyUnicode_KIND(a) != PyUnicode_KIND(b))
        return 0;

    return memcmp(PyUnicode_1BYTE_DATA(a), PyUnicode_1BYTE_DATA(b),
                  PyUnicode_GET_LENGTH(a) * PyUnicode_KIND(a)) == 0;

}

 

 

크게 어려운 함수가 아닌 것처럼 보이나, 하나씩 보면 굉장히 논리적으로 빈틈없이 설계되어 있는 것을 확인할 수 있습니다.

 

1. 

PyUnicode_GET_LENGTH(a) != PyUnicode_GET_LENGTH(b) return 0;

 

이 함수는 우선 PyObject인 a, b의 길이가 다르면 return 0, 즉 False를 해버립니다.

 

문자열을 다 확인할 필요도 없이 길이가 다르다면 바로 False를 return 해주는 것이죠.

 

 

2.

PyUnicode_GET_LENGTH(a) == 0 return 1;

 

1번에서 return 이 안되었다는 것은 a와 b의 unicode 길이는 같다는 것입니다.

그런데 여기서 a의 길이가 0 이라는 것은 b도 0이라는 것이겠죠?

 

이 때 a와 b가 모두 길이가 0이려면 두 문자열은 모두 빈 문자열 밖에 될 수 없습니다.

그래서 a와 b는 같다. 즉 return 1을 해주는 것입니다.

 

 

3.

PyUnicode_KIND(a) != PyUnicode_KIND(b) return 0;

 

3번 까지 왔다는 것은 a와 b가 unicode의 길이가 같고, 그 길이가 1이상인 값입니다.

하지만, 여기서 KIND? 가 무엇이냐?

파이썬에서는 문자열의 길이를 1바이트, 2바이트, 4바이트 등으로 나누어 저장하게 되고, 이에 따라 KIND가 바뀌게 됩니다.

 

아래 함수를 추가적으로 확인해보면 됩니다.

enum PyUnicode_Kind {
/* Return values of the PyUnicode_KIND() function: */
    PyUnicode_1BYTE_KIND = 1,
    PyUnicode_2BYTE_KIND = 2,
    PyUnicode_4BYTE_KIND = 4
};

 

즉 여기서 unicode의 길이는 어찌저찌 같아질 수 있었겠지만, 그 바이트의 크기가 다르다면 엄연히 다른 문자열이겠죠?

따라서 return 0, False값을 return 해줍니다..

 

 

4. 

return memcmp(PyUnicode_1BYTE_DATA(a), PyUnicode_1BYTE_DATA(b),
                  PyUnicode_GET_LENGTH(a) * PyUnicode_KIND(a)) == 0;

 

여기까지 온다면 a와 b는 즉 unicode의 길이가 1이상으로 같고, 그 Byte KIND도 동일하겠죠?

 

마지막 memcmp, 즉 메모리에 있는 값의 비교를 해주는 것입니다.

실제 값의 비교는 위에서 모~~든 가능한 가지치기가 이러난 이후에 진행됩니다.

이렇게 언어 속도의 최적화를 내부적으로 하고 있는 것 같습니다.

 

memcmp(비교할 1번 포인터, 비교할 2번 포인터, 비교할 Byte 크기)

memcmp의 return 값으로 1번 포인터와 2번 포인터가 Byte 크기 만큼 모든 값이 같다면, 0 이 return 되고 

그렇지 않은경우 앞의 값이 더 크다면 양수, 작다면 음수를 return 합니다.

 

이런 내용은 외울 필요는 없고, 아래의 문서에서 확인할 수 있을 정도로 될 것 같습니다.

https://cplusplus.com/reference/cstring/memcmp/

https://cplusplus.com/reference/cstring/memcmp/

 

따라서!! 4번에서 memcmp의 값이 0 이라면, 결과적으로 a와 b의 값은 같아서 1(True)이 return 될 것이고.

 

다르다면! False, 즉 0의 값이 return 되어 모든 unicode의 비교가 끝나게 됩니다.

 

 

정리

 

맨 처음 해당 함수를 봤을 때

"Pyunicode_GET_LENGTH(a) == 0 보다 KIND의 비교를 먼저 해서

return 0인 경우를 먼저 체크해줘야 하는 것이 아닌가?"

라고 생각했습니다.

 

하지만, 코드를 보며 좀 더 생각해보면, unicode 길이 비교 -> 빈문자열 -> 종류 -> 실제 비교

의 순서를 통해 논리적인 가지치기를 하고있다는 것을 알았습니다.

또한 이 논리에는 빈틈이 없었구요..

 

그러고보니, 제가 정리해본 자바에서 equals() 연산자를 비교했을 때와

굉장히 유사한 순서로 비교가 이루어지고 있었습니다.

(Python, JAVA의 비교도 재밌을 것 같습니다.)

https://driveitlikeyoustoleitt.tistory.com/entry/JAVA-equals-%EC%99%80-%EC%9D%98-%EC%B0%A8%EC%9D%B4%EA%B7%BC%EB%8D%B0-%EC%A2%80-%EC%A7%84%ED%95%98%EA%B2%8C

 

 

이런 과정으로 가장 큰 연산(시간이 오래 걸리는)을 가장 마지막으로 미루는 것이

하나의 최적화 방법이구나 깨달은 날입니다.

 

끘!!