데이터 구조의 매력 을 느끼다: 검색 성능 최적화

몇 주 전에 성능 최 적 화 를 한 적 이 있다. 만약 에 응용 장면 에 부 딪 힌 문 제 를 추상 화하 면 사실은 3 차원 배열 의 검색 성능 최적화 이다.여러 가지 방안 을 반복 적 으로 시도 한 후에 마침내 지금까지 가장 효율 적 인 방안 을 찾 았 다.
문제 배경
하나의 함 수 는 수신 메시지 부하 에 있 는 요 소 를 그룹 으로 나 눈 다음 에 이 요 소 를 그룹 단위 로 보 내야 합 니 다.한 이미지 의 예 를 들 어 한 택배 회 사 는 화물 택배 효율 을 높이 기 위해 전국 각 도시 에서 각 환 승 역 의 직통 선 로 를 개통 했다.한 차 의 소포 가 A 지 중계 역 에 도착 하면 A 지 의 중계 역 은 즉시 이 소 포 를 선별 한 후 화물 목적 도시 에 따라 차 를 나 누 어 환 적 할 수 있다.이 문제 의 배경 은 '택배 환 승 소 에서 소포 에 대한 선별, 환 적 절차' 와 같다. 나 누 어 보면 이 절 차 는 대체적으로 다음 과 같은 세 부분 을 포함한다.

새로 도착 한 소포 저장

새로 도착 한 소 포 를 묶 기

이 그룹 을 보 냅 니 다

이것 은 비교적 간단 한 처리 과정 입 니 다. 다음 과 같은 위조 코드 를 작성 할 수 있 습 니 다.

//       、  、      group          ，  
// group             
PacketGroupType g_PacketGroups[MAX_PROVINCE_NUM][MAX_CITY_NUM][MAX_TOWN_NUM];

//                 group  
void PacketsGrouping(void *msg)
{
    PacketsCarrierMsgType *pMsg = (PacketsCarrierMsgType *) GetPayloadFromMsy(msg);
    packetsNum = pMsg->number;

    for (int i = 0; i <packetsNum; i ++ )
    {
        PacketsType packet = pMsg->packets[i];

        int provinceNo = GetProvinceNo(&packet);
        int cityNo = GetCityNo(&packet);
        int townNo = GetTownNo(&packet);

        g_PacketGroups[provinceNo][cityNo][townNo].elemsNum++;
        AddPacketIntoGroup(packet, &g_PacketGroups[provinceNo][cityNo][townNo]);
    }
    ...
}

//   group     ，       0   ，  
void PacketsSending(void *msg)
{
    ...

    for (int i = 0; i < MAX_PROVINCE_NUM; i ++)
    {
        for (int j = 0; j < MAX_CITY_NUM; j ++)        
        {
            for (int k = 0; k < MAX_TOWN_NUM; k ++) 
            {
                if (g_PacketGroups[i][j][k].elemsNum != 0)
                {
                    SendPacketGroup(&g_PacketGroups[i][j][k]);
                }
            }
        }
    }
    ...
}

태그 비트 사용 하기
위의 이러한 실현 방안 은 현재 도착 한 소포 의 수량 이 얼마 가 되 든 최종 적 으로 몇 group 로 나 뉘 든 모두 하나씩 g 를 옮 겨 다 녀 야 합 니 다.Packet Groups 의 모든 group 은 의미 없 는 작업 을 많이 했 습 니 다.첫 번 째 간단 한 최 적 화 를 시작 할 수 있 습 니 다. 표시 위 치 를 사용 하여 발송 시의 검색 효율 을 높 일 수 있 습 니 다.자세 한 것 은 소포 수가 0 이 아 닌 group 에 표시 위 치 를 설정 하고 표시 위치 에 다른 추가 정 보 를 인 코딩 하여 불필요 한 검색 을 피 하 는 것 입 니 다.다음 과 같다.

//          
unsigned char g_ElementInGroupFlag[MAX_PROVINCE_NUM][MAX_CITY_NUM][MAX_TOWN_NUM];

//             “                group”
// g_ElementInGroupFlag[0][0][0]     4   0   g_ElementInGroupFlag[0][0]            ，       MAX_TOWN_NUM ；
// g_ElementInGroupFlag[0][1][0]     4   0   g_ElementInGroupFlag[0][1]            ，       MAX_TOWN_NUM ；
...

//             “               group”
// g_ElementInGroupFlag[1][0][0]     4   0   g_ElementInGroupFlag[0]            ，       MAX_TOWN_NUM*MAX_CITY_NUM ；
// g_ElementInGroupFlag[2][0][0]     4   0   g_ElementInGroupFlag[1]            ，       MAX_TOWN_NUM*MAX_CITY_NUM ；

//          ，                。
void PacketsGrouping(void *msg)
{
    PacketsCarrierMsgType *pMsg = (PacketsCarrierMsgType *) GetPayloadFromMsy(msg);
    packetsNum = pMsg->number;

    for (int i = 0; i <packetsNum; i ++ )
    {
        PacketsType packet = pMsg->packets[i];

        int provinceNo = GetProvinceNo(&packet);
        int cityNo = GetCityNo(&packet);
        int townNo = GetTownNo(&packet);

        g_ElementInGroupFlag[provinceNo][cityNo][townNo] = 1;
        g_ElementInGroupFlag[provinceNo][cityNo][0] |= 1 << 4;
        g_ElementInGroupFlag[provinceNo][0][0] |= 1 << 4;

        g_PacketGroups[provinceNo][cityNo][townNo].elemsNum++;
        AddPacketIntoGroup(packet, &g_PacketGroups[provinceNo][cityNo][townNo]);
    }
    ...
}

void PacketsSending(void *msg)
{
    ...

    for (int i = 0; i < MAX_PROVINCE_NUM; i ++)
    {
        if (g_ElementInGroupFlag[i][0][0] != 1)
        {
            continue;
        }

        for (int j = 0; j < MAX_CITY_NUM; j ++)        
        {        
            if (g_ElementInGroupFlag[provinceNo][j][0] != 1)
            {
                continue;
            }

            for (int k = 0; k < MAX_TOWN_NUM; k ++) 
            {
                if (g_ElementInGroupFlag[i][j][k] != 0)
                {
                    SendPacketGroup(&g_PacketGroups[provinceNo][cityNo][townNo]);
                }
            }
        }
    }
    ...
}

이렇게 하 는 것 은 효율 이 좀 높 지만, 매우 보기 흉 하 다.특히 여기 if... contine... 매크로 를 사용 하여 최적화 할 수 있 습 니 다.

#define CONTINU_IF(EXPR)  \
    if (EXPR) \
    {\
        continue; \
    }\

용기 의 방법
표기 위치의 최적화 방법 은 전체 효율 에 확실히 개선 되 었 지만, 여전히 매우 부족 하 다.더 나 아가 용 기 를 사용 하 는 것 을 고려 하여 group 을 용기 로 하 는 요소 에 따라 용기 에 추가 하고 소 포 를 보 낼 때 용 기 를 직접 옮 겨 다 니 면 됩 니 다.

새로 도착 한 소 포 를 저장 할 때 한 소포 에 대해 두 가지 작업 을 해 야 한다. 먼저 소 포 를 group 에 나 누고 그 다음 에 group 을 용기 에 저장 해 야 한다

.

다른 소 포 를 계속 조작 합 니 다. 소 포 를 group 에 나 누 어 줍 니 다.그룹 이 용기 에 존재 한다 면 그룹 에 소 포 를 직접 저장 합 니 다.그룹 이 용기 에 존재 하지 않 는 다 면, 이 그룹 도 용기 에 추가 로 저장 해 야 합 니 다.즉, '같은 group 을 용기 에 중복 저장 하지 않도록'

위의 두 단계 로 모든 소 포 를 처리 한 후 용 기 를 옮 겨 다 니 며 각 group 을 보 냅 니 다

//       、  、      group          
PacketGroupType g_PacketGroups[MAX_PROVINCE_NUM][MAX_CITY_NUM][MAX_TOWN_NUM];
PacketGroupType g_PacketGroupContainer[MAX_PROVINCE_NUM * MAX_CITY_NUM * MAX_TOWN_NUM];

//                 group  
void PacketsGrouping(void *msg)
{
    PacketsCarrierMsgType *pMsg = (PacketsCarrierMsgType *) GetPayloadFromMsy(msg);
    packetsNum = pMsg->number;

    for (int i = 0; i <packetsNum; i ++ )
    {
        PacketsType packet = pMsg->packets[i];

        int provinceNo = GetProvinceNo(&packet);
        int cityNo = GetCityNo(&packet);
        int townNo = GetTownNo(&packet);

        g_PacketGroups[provinceNo][cityNo][townNo].elemsNum++;
        AddPacketIntoGroup(packet, g_PacketGroups[provinceNo][cityNo][townNo]);

        if (g_PacketGroups[provinceNo][cityNo][townNo] is not in g_PacketGroupContainer)
        {
             AddGroupPacketIntoContainer(g_PacketGroups[provinceNo][cityNo][townNo], g_PacketGroupContainer);
        }
    }
    ...
}

//   group   ，     group
void PacketsSending(void *msg)
{
    ...
           
    for (group in g_PacketGroupContainer)
    {
       SendPacketGroup(group);
    }
    ...
}

현재 코드 는 DSP 의 각 core 에서 실행 되 며 메모리 관리 가 엄격 하여 STL 용기 의 기본 메모리 분배 기 를 직접 사용 할 수 없 기 때문에 라 이브 러 리 에 있 는 용 기 를 사용 하지 않 습 니 다.이 방안 은 이미 비교적 이상 적 인 방안 이지 만 싫어 하 는 '무 거 운 제거' 작업 은 정말 큰 흠 이 라 처리 하기 어렵다.
교묘 한 링크 기법
용기 의 방안 은 이미 상당히 OK 이지 만, 더욱 효율 적 인 방법 이 있다!위의 용기 의 방법 에 비해 이런 방법 은 두 가지 장점 이 있다.

첫째, 더 적은 메모리 자원 사용

둘째, '무게 제거' 기능 을 편리 하 게 해결 할 수 있다

.

//       、  、      group          
PacketGroupType g_PacketGroups[MAX_PROVINCE_NUM][MAX_CITY_NUM][MAX_TOWN_NUM];
PacketGroupManager g_PacketGroupManager;

typedef strunct PacketGroupInfo{   
    int provinceNo;
    int cityNo;
    int townNo;

    PacketGroupInfo *next;
    boolean isInGroupManager;
}

typedef strunct{

    PacketGroupInfo *head;
    PacketGroupInfo groupsInfo[MAX_PROVINCE_NUM][MAX_CITY_NUM][MAX_TOWN_NUM];
}PacketGroupManager;

//                 group  
void PacketsGrouping(void *msg)
{
    PacketsCarrierMsgType *pMsg = (PacketsCarrierMsgType *) GetPayloadFromMsy(msg);
    packetsNum = pMsg->number;

    for (int i = 0; i <packetsNum; i ++ )
    {
        PacketsType packet = pMsg->packets[i];

        int provinceNo = GetProvinceNo(&packet);
        int cityNo = GetCityNo(&packet);
        int townNo = GetTownNo(&packet);

        g_PacketGroups[provinceNo][cityNo][townNo].elemsNum++;
        AddPacketIntoGroup(packet, g_PacketGroups[provinceNo][cityNo][townNo]);

        if (g_PacketGroupManager.groupsInfo[provinceNo][cityNo][townNo].isInGroupManager == 0)
        {
             AddGroupIntoManager(g_PacketGroups[provinceNo][cityNo][townNo], g_PacketGroupManager);
        }
    }
    ...
}

//   group Manager     ，     group
void PacketsSending(void *msg)
{
    ...
           
    for (PacketGroupInfo *pItem = g_PacketGroupManager.head; pItem != NULL; pItem = pItem->next)
    {
       SendPacketGroup(pItem );
    }
    ...
}

이러한 방안 의 특수성 은 기 존의 group 저장 구조 와 대응 되 지만 필요 한 정보 만 포함 하 는 경량급 관리 구 조 를 사용 하 는 동시에 정적 링크 방식 으로 조건 을 만족 시 키 는 group 정 보 를 유지 하고 노드 의 배분 과 방출 작업 을 추가 로 수행 하지 않 는 다 는 것 이다.