[입 개발] Redis의 bitcount 에 대한 오해.

Redis github의 issue 란에 재미난 질문이 하나 올라왔습니다. bitcount 명령이 의도한 대로 동작을 하지 않는다는 것입니다.(https://github.com/antirez/redis/issues/860), bitcount 만 보자면 해당 동작은 정상적으로 동작하였습니다. 그런데 setbit, getbit 와 bitcount의 semantic 이 서로 다르기 때문에, 쉽게 일어날 수 있는 오해이기 때문에, 여기서 한번 간단하게 정리하려고 합니다.

bitcount를 알아보기 전에 먼저 setbit와 getbit를 알아보도록 하겠습니다.

edis> SETBIT mykey 7 1
(integer) 0
redis> SETBIT mykey 7 0
(integer) 1
redis> GET mykey
"\u0000"
redis> 

setbit 와 getbit는 파라매터로 bit offset이 들어갑니다. 즉, 7이라면 7번째 bit 값이 되는 것입니다. 모두가 알다시피 1 byte는 = 8bit 라는 아름다운 그런 명제가 있습니다.

그런데 bitcount는 어떻게 동작하는가? bitcount는 해당 데이터 내의 또는 특정 범위 내의 1로 셋된 bit의 개수를 돌려줍니다.

redis> SET mykey "foobar"
OK
redis> BITCOUNT mykey
(integer) 26
redis> BITCOUNT mykey 0 0
(integer) 4
redis> BITCOUNT mykey 1 1
(integer) 6
redis> 

그럼 무엇이 문제인가? 제가 초반에 semantic 이 서로 다르다고 했는데, bitcount의 start end offset은 byte offset 입니다. 즉 setbit, getbit는 bit offset 으로 동작하는데, bitcount는 byte offset으로 동작하므로 쉽게 착각하게 됩니다. 소스를 보면 간단하게 이해가 되지만, 그전까지 예제만 보고 쉽게 알아차리긴 힘들듯 합니다.

먼저 setbit의 소스의 일부분을 간단하게 보면 다음과 같습니다. bit offset 이기 때문에, shift 연산을 통해서 byte 위치를 찾고, 해당 바이트에 특정 bit를 set을 하게 됩니다.

    /* Grow sds value to the right length if necessary */
    byte = bitoffset >> 3;
    o->ptr = sdsgrowzero(o->ptr,byte+1);

    /* Get current values */
    byteval = ((uint8_t*)o->ptr)[byte];
    bit = 7 - (bitoffset & 0x7);
    bitval = byteval & (1 << bit);

    /* Update byte with new bit value and return original value */
    byteval &= ~(1 << bit);
    byteval |= ((on & 0x1) << bit);
    ((uint8_t*)o->ptr)[byte] = byteval;

그럼 bitcount는 어떻게 되느냐? 다음과 같습니다. popcount라는 명령에서 계산하게 됩니다. 보시면 count는 byte offset 입니다.

long popcount(void *s, long count) {
    long bits = 0;
    unsigned char *p;
    uint32_t *p4 = s;
    static const unsigned char bitsinbyte[256] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};

    /* Count bits 16 bytes at a time */
    while(count>=16) {
        uint32_t aux1, aux2, aux3, aux4;

        aux1 = *p4++;
        aux2 = *p4++;
        aux3 = *p4++;
        aux4 = *p4++;
        count -= 16;

        aux1 = aux1 - ((aux1 >> 1) & 0x55555555);
        aux1 = (aux1 & 0x33333333) + ((aux1 >> 2) & 0x33333333);
        aux2 = aux2 - ((aux2 >> 1) & 0x55555555);
        aux2 = (aux2 & 0x33333333) + ((aux2 >> 2) & 0x33333333);
        aux3 = aux3 - ((aux3 >> 1) & 0x55555555);
        aux3 = (aux3 & 0x33333333) + ((aux3 >> 2) & 0x33333333);
        aux4 = aux4 - ((aux4 >> 1) & 0x55555555);
        aux4 = (aux4 & 0x33333333) + ((aux4 >> 2) & 0x33333333);
        bits += ((((aux1 + (aux1 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
                ((((aux2 + (aux2 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
                ((((aux3 + (aux3 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24) +
                ((((aux4 + (aux4 >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24);
    }
    /* Count the remaining bytes */
    p = (unsigned char*)p4;
    while(count--) bits += bitsinbyte[*p++];
    return bits;
}

즉 다음과 같이 setbit를 사용하면 결과적으로 아래와 같은 형태과 됩니다.
“setbit test1 10 1” means 00000000 00100000, so it is set in byte offset 1
“setbit test1 20 1” means 00000000 00000000 00001000, so it is set in byte offset 2
“setbit test1 30 1” means 00000000 00000000 00000000 00000010, so it is set in byte offset 3

그럼 bitcount를 사용하실 때 실수 없으시길 바랍니다. bitcount에서 bit offset 대신에 byte offset을 사용하기 때문에 정확하게 어느 비트부터 어디 까지 몇개의 1이 있는지는 알 수가 없습니다. 그럼 고운하루되시기 바랍니다.