조합 정렬, 병목 해결과 성능 개선하기

Alex·2024년 8월 30일

Seoul_Nolgoat

목록 보기

10/11

원인을 알 수 없는 병목 현상

 public List<CombinationDto> sortByDistance(
            List<Store> firstStores,
            List<Store> secondStores,
            List<Store> thirdStores) {

        DistanceCalculator distanceCalculator = new DistanceCalculator();

        List<CombinationDto> combinationDtos = combineForDistance(firstStores, secondStores, thirdStores);

        combinationDtos.sort((a, b) -> {
            double totalDistanceOfA = distanceCalculator.calculateDistance(a);
            double totalDistanceOfB = distanceCalculator.calculateDistance(b);

            return Double.compare(totalDistanceOfB, totalDistanceOfA);
        });

        distanceCalculator.distanceCacheClear();

        return combinationDtos;
    }

    public List<CombinationDto> combineForDistance(
            List<Store> firstStores,
            List<Store> secondStores,
            List<Store> thirdStores) {

        List<CombinationDto> combinations = new ArrayList<>();
        int firstSize = firstStores.size();
        int secondSize = secondStores.size();
        int thirdSize = thirdStores.size();

        IntStream.range(0, firstSize).forEach(i -> {
            Store firstStore = firstStores.get(i);
            IntStream.range(0, secondSize).forEach(j -> {
                Store secondStore = secondStores.get(j);
                IntStream.range(0, thirdSize).forEach(k -> {
                    Store thirdStore = thirdStores.get(k);
                    combinations.add(new CombinationDto(List.of(firstStore, secondStore, thirdStore)));
                });
            });
        });

        return combinations;
    }

조합들을 정렬하는 과정에서 병목이 생겼다.
이유를 파악하기는 어려웠다.
사람들에게 원인이 무엇일지 의견을 구하다가 로직에 문제가 있는지 확인해보라른 말을 들었다.

그렇다면, 거리 계산과 sorting 작업을 동시에 하기 때문에 문제가 생긴 것은 아닐까? 하는 생각이 떠올랐다.

이에, 모든 조합들의 거리 계산을 다 끝내고 sorting을 하기로 했다.

그랬더니 30초 정도씩 걸리던 작업를 4초 정도로 끝낼 수 있었다.

추가로 성능 개선해보기

성능 개선을 위해서 캐시적용, 병렬 프로그래밍을 모두 활용해봤다.
결과는 좋지 않았다.

private double calculate(Coordination firstCoordination, Coordination secondCoordination) {

        String key = firstCoordination.getLatitude() + "," + firstCoordination.getLongitude() +
                "-" + secondCoordination.getLatitude() + "," + secondCoordination.getLongitude();

        // 캐시에서 거리 찾기
        double cahedDistance = distanceCache.getOrDefault(key, Double.NaN);
        if (!Double.isNaN(cahedDistance)) {
            return cahedDistance;
        }


		(생략)
    }
    
    //가게1과 가게2의 거리를 구했으면 이를 캐시로 담아서 
    //그 다음에 가게1과 가게2의 거리를 구하려고 할 때 
    //캐시에 담아둔 걸 꺼내서 반환한다.

근데 오히려 캐시를 썼더니 시간이 더 오래 걸렸다.

캐시를 쓰면 1.6초가

안 쓰면 0.8초가 걸렸다.

멀티스레드를 쓰면 속도가 빨라질까 싶어서 적용했는데

public List<CombinationDto> combineForDistance(
            List<Store> firstStores,
            List<Store> secondStores,
            List<Store> thirdStores) {

        DistanceCalculator distanceCalculator = new DistanceCalculator();
        ConcurrentLinkedQueue<CombinationDto> combinations = new ConcurrentLinkedQueue<>();
        int firstSize = firstStores.size();
        int secondSize = secondStores.size();
        int thirdSize = thirdStores.size();

        IntStream.range(0, firstSize).parallel().forEach(i -> {
            Store firstStore = firstStores.get(i);
            IntStream.range(0, secondSize).parallel().forEach(j -> {
                Store secondStore = secondStores.get(j);
                IntStream.range(0, thirdSize).parallel().forEach(k -> {
                    Store thirdStore = thirdStores.get(k);
                    CombinationDto combinationDto = new CombinationDto(List.of(firstStore, secondStore, thirdStore));
                    double totalDistance = distanceCalculator.calculateDistance(combinationDto);
                    combinationDto.setDistance(totalDistance);
                    combinations.add(combinationDto);
                });
            });
        });

        return new ArrayList<>(combinations);
    }