beautifulsoups.dev
Published on

Rust 이터레이터·클로저로 N+1 루프 제거 최적화

Authors

서버 사이드 Rust 코드를 보다 보면, 데이터 구조를 여러 번 훑거나 매 항목마다 비싼 연산을 호출해서 성능이 급격히 나빠지는 경우가 많습니다. 흔히 DB에서 말하는 N+1 문제처럼, 애플리케이션 레벨에서도 N개를 처리하면서 내부에서 또 N 또는 M번 반복하거나 조회를 수행하는 “N+1 루프”가 발생합니다.

이 글에서는 Rust의 이터레이터와 클로저를 이용해 이런 구조를 한 번의 패스로 바꾸고, 불필요한 할당과 해시 조회, 락 경합까지 줄이는 방법을 다룹니다. 단순히 for를 map으로 바꾸는 수준이 아니라, 데이터 흐름을 재구성해 비용을 구조적으로 없애는 것이 목표입니다.

성능 문제를 다루는 관점은 프론트의 Long Task 추적과도 유사합니다. 병목을 “측정하고, 원인을 분해한 뒤, 비용을 이동 또는 제거”해야 합니다. 관련해서는 Chrome INP 급락? Long Task 10분 추적·해결도 함께 보면 사고방식에 도움이 됩니다.

N+1 루프란 무엇인가

여기서 말하는 N+1 루프는 대체로 아래 패턴 중 하나로 나타납니다.

  1. 중첩 반복: 바깥에서 N개를 돌고, 안쪽에서 매번 전체 목록을 다시 스캔
  2. 반복 조회: 바깥에서 N개를 돌고, 안쪽에서 매번 해시맵 조회 또는 정렬, 파싱 같은 비싼 연산
  3. 락 경합: 바깥에서 N개를 돌고, 안쪽에서 매번 Mutex 잠금
  4. 불필요한 할당: 매 항목마다 Vec를 새로 만들고 push

핵심은 “같은 정보를 여러 번 계산하거나, 같은 컬렉션을 여러 번 훑는다”입니다.

예제 1: 중첩 루프를 HashMap 인덱스로 바꾸기

가장 흔한 케이스는 “ID로 매번 선형 탐색”입니다.

문제 코드: O(n*m) 선형 탐색

#[derive(Clone, Debug)]
struct User {
    id: u64,
    name: String,
}

#[derive(Clone, Debug)]
struct Order {
    id: u64,
    user_id: u64,
    total: i64,
}

fn attach_user_names(users: &[User], orders: &[Order]) -> Vec<(u64, String, i64)> {
    let mut out = Vec::with_capacity(orders.len());

    for o in orders {
        // 매 주문마다 users 전체를 스캔: O(n*m)
        let user_name = users
            .iter()
            .find(|u| u.id == o.user_id)
            .map(|u| u.name.clone())
            .unwrap_or_else(|| "unknown".to_string());

        out.push((o.id, user_name, o.total));
    }

    out
}

겉보기엔 깔끔하지만 orders가 N, users가 M이면 최악의 경우 N*M 탐색이 됩니다.

개선: 한 번만 인덱스 만들고 O(n+m)

이터레이터와 클로저를 쓰면 “인덱스 구축”과 “결과 생성”을 명확히 분리하면서도 코드가 짧아집니다.

use std::collections::HashMap;

fn attach_user_names_fast(users: &[User], orders: &[Order]) -> Vec<(u64, String, i64)> {
    let user_by_id: HashMap<u64, &User> = users.iter().map(|u| (u.id, u)).collect();

    orders
        .iter()
        .map(|o| {
            let name = user_by_id
                .get(&o.user_id)
                .map(|u| u.name.as_str())
                .unwrap_or("unknown");

            (o.id, name.to_string(), o.total)
        })
        .collect()
}

포인트는 다음과 같습니다.

  • users를 한 번만 순회해 HashMap을 구축
  • orders는 한 번만 순회하면서 O(1) 평균 조회
  • 클로저 내부에서는 &str로 받고 마지막에만 String 할당

만약 결과에서 String 복제가 부담이면, 반환 타입을 Cow로 바꾸는 것도 방법입니다.

use std::borrow::Cow;
use std::collections::HashMap;

fn attach_user_names_cow<'a>(users: &'a [User], orders: &'a [Order]) -> Vec<(u64, Cow<'a, str>, i64)> {
    let user_by_id: HashMap<u64, &'a User> = users.iter().map(|u| (u.id, u)).collect();

    orders
        .iter()
        .map(|o| {
            let name = user_by_id
                .get(&o.user_id)
                .map(|u| Cow::Borrowed(u.name.as_str()))
                .unwrap_or_else(|| Cow::Borrowed("unknown"));

            (o.id, name, o.total)
        })
        .collect()
}

예제 2: filter + map로 같은 컬렉션을 두 번 훑는 문제

이터레이터가 항상 빠른 것은 아닙니다. 잘못 쓰면 “두 번 순회”가 생깁니다. 예를 들어 아래는 조건을 만족하는 항목만 뽑아 변환하는데, 중간에 collect를 끼워 넣으면 메모리와 순회 비용이 늘어납니다.

문제 코드: 중간 Vec로 N+1에 준하는 비용 증가

fn expensive_transform(x: i64) -> i64 {
    // 예: 파싱, 정규화, 암호화 등
    x * 2
}

fn pipeline_bad(input: &[i64]) -> Vec<i64> {
    let filtered: Vec<i64> = input.iter().copied().filter(|x| x % 2 == 0).collect();
    filtered.into_iter().map(expensive_transform).collect()
}

개선: 단일 패스, filter_map 또는 then_some

fn pipeline_good(input: &[i64]) -> Vec<i64> {
    input
        .iter()
        .copied()
        .filter_map(|x| (x % 2 == 0).then_some(expensive_transform(x)))
        .collect()
}

이 방식은

  • 중간 Vec 할당 제거
  • 한 번의 순회로 완료

예제 3: 그룹핑에서 흔한 N+1 push 패턴을 fold로 정리

“ID별로 묶기”는 자주 나오고, 구현이 조금만 어긋나도 불필요한 조회가 늘어납니다.

문제 코드: 매번 entry를 여러 번 건드리는 형태

use std::collections::HashMap;

fn group_orders_bad(orders: &[Order]) -> HashMap<u64, Vec<Order>> {
    let mut map: HashMap<u64, Vec<Order>> = HashMap::new();

    for o in orders {
        if !map.contains_key(&o.user_id) {
            map.insert(o.user_id, Vec::new());
        }
        map.get_mut(&o.user_id).unwrap().push(o.clone());
    }

    map
}

contains_key와 get_mut로 해시 조회가 사실상 두 번 일어나고, 분기까지 늘어납니다.

개선: entry + 이터레이터 fold

use std::collections::HashMap;

fn group_orders_good(orders: &[Order]) -> HashMap<u64, Vec<Order>> {
    orders.iter().cloned().fold(HashMap::new(), |mut acc, o| {
        acc.entry(o.user_id).or_insert_with(Vec::new).push(o);
        acc
    })
}
  • 해시 조회 1회로 수렴
  • 클로저로 누산을 표현해 로직이 짧고 명확

성능을 더 챙기면 or_insert_with(Vec::new) 대신 or_default()도 가능합니다.

acc.entry(o.user_id).or_default().push(o);

예제 4: 락 기반 N+1을 collect 후 단일 커밋으로 바꾸기

멀티스레드 환경에서 자주 보는 패턴입니다. 매 항목마다 Mutex를 잠그면 락 경합이 곧 병목이 됩니다.

문제 코드: 매 반복마다 락 획득

use std::sync::{Arc, Mutex};

fn push_with_lock_bad(shared: Arc<Mutex<Vec<i64>>>, input: &[i64]) {
    for &x in input {
        let mut guard = shared.lock().unwrap();
        guard.push(x);
    }
}

개선: 로컬에서 모아 한 번에 합치기

use std::sync::{Arc, Mutex};

fn push_with_lock_good(shared: Arc<Mutex<Vec<i64>>>, input: &[i64]) {
    let local: Vec<i64> = input.iter().copied().collect();

    let mut guard = shared.lock().unwrap();
    guard.extend(local);
}
  • 락 획득이 N번에서 1번으로 감소
  • extend는 내부적으로 더 효율적인 경로를 사용 가능

이 패턴은 “작업을 분리하고 마지막에 커밋”한다는 점에서 분산 트랜잭션의 보상 설계 사고와도 닮아 있습니다. 더 넓은 설계 관점은 Kafka SAGA 보상 트랜잭션 설계 실전 7패턴에서 참고할 수 있습니다.

예제 5: flat_map으로 중첩 루프를 평탄화하고, 불필요한 임시 벡터 제거

중첩 루프가 항상 나쁜 것은 아니지만, “각 단계에서 임시 Vec를 만든 뒤 합치는” 구조는 비용이 커집니다.

문제 코드: 임시 벡터의 연쇄

fn explode_bad(input: &[i64]) -> Vec<i64> {
    let mut out = Vec::new();

    for &x in input {
        let tmp = vec![x, x + 1, x + 2];
        out.extend(tmp);
    }

    out
}

개선: flat_map + array::IntoIter

fn explode_good(input: &[i64]) -> Vec<i64> {
    input
        .iter()
        .copied()
        .flat_map(|x| [x, x + 1, x + 2])
        .collect()
}

임시 Vec가 사라지고, 결과는 스트리밍 방식으로 생성됩니다.

실전 체크리스트: Rust에서 N+1 루프를 의심해야 할 신호

1) find가 루프 안에 있다

  • 루프 안의 iter().find(...)는 거의 항상 “매번 선형 탐색”입니다.
  • 해결: 사전 인덱스 HashMap 또는 정렬 후 이진 탐색.

2) contains_key 다음에 get_mut을 한다

  • 해시 조회가 중복됩니다.
  • 해결: entry로 합치기.

3) collect가 파이프라인 중간에 있다

  • 중간 컬렉션이 필요 없다면 단일 패스로 합치세요.
  • 해결: filter_map, flat_map, fold, 혹은 마지막에만 collect.

4) 락이 루프 안에 있다

  • 락이 N번이면 비용이 기하급수적으로 커질 수 있습니다.
  • 해결: 로컬 버퍼에 모아서 단일 extend 또는 배치 업데이트.

5) 클로저가 캡처하는 값이 무겁다

  • 큰 구조체를 클로저가 move로 캡처하면 복사가 커질 수 있습니다.
  • 해결: 참조 캡처, 또는 필요한 필드만 추출.

벤치마크 팁: 개선이 실제로 빨라졌는지 확인하기

Rust는 체감상 빨라져 보여도, 컴파일러 최적화와 데이터 분포에 따라 결과가 달라집니다. 가능하면 criterion으로 확인하세요.

// Cargo.toml에 criterion 추가 후 사용
// [dev-dependencies]
// criterion = "0.5"

use criterion::{black_box, Criterion, criterion_group, criterion_main};

fn bench_attach(c: &mut Criterion) {
    let users: Vec<User> = (0..50_000)
        .map(|i| User { id: i, name: format!("u{ i }") })
        .collect();

    let orders: Vec<Order> = (0..200_000)
        .map(|i| Order { id: i, user_id: i % 50_000, total: i as i64 })
        .collect();

    c.bench_function("attach_user_names_fast", |b| {
        b.iter(|| {
            let out = attach_user_names_fast(black_box(&users), black_box(&orders));
            black_box(out);
        })
    });
}

criterion_group!(benches, bench_attach);
criterion_main!(benches);

벤치마크 시에는

  • 데이터 크기와 분포를 실제와 비슷하게
  • black_box로 과도한 제거 최적화 방지
  • “인덱스 구축 비용”을 포함할지 여부를 명확히

마무리: 이터레이터·클로저는 문법이 아니라 구조 최적화 도구

Rust 이터레이터와 클로저는 단순히 함수형 스타일을 위한 장식이 아닙니다. 다음을 가능하게 합니다.

  • 비용이 큰 연산을 “한 번만” 하도록 데이터 흐름 재구성
  • 중간 할당 제거로 메모리 압박 감소
  • 해시 조회, 락 획득 같은 병목을 배치 처리로 전환

정리하면, N+1 루프 제거의 핵심은 map을 쓰는 것이 아니라 반복의 의미를 바꾸는 것입니다. “매번 찾지 말고, 먼저 인덱싱하라”, “매번 잠그지 말고, 모아서 커밋하라”, “중간 컬렉션을 만들지 말고, 스트리밍하라”를 습관화하면 Rust에서도 체감 성능이 크게 달라집니다.

Discuss on Twitter • View on GitHub