Thorsten Ball 님의 블로그를 의역/요약한 글입니다.

—-

Zed가 오픈 소스로 공개되었을 때, HackerNews에서 누군가 현재 버퍼에 담긴 단어를 문서 전체에서 찾는것은 SublimeText가 Zed보다 빠르다 라고 했습니다. Zed는 약 1초가 걸렸고 SublimeText는 약 200ms 걸렸죠.

단어 전체 찾기란: 현재 커서의 위치에서, cmd-shift-l을 쳤을 때 해당 단어를 버퍼에 담고, 전체 문서에서 단어 위치에 커서를 놓아줘서, 멀티 커서 작업을 하게 해주는 기능입니다.

그러니까 Sublime은 이걸 400ms 만에 하는데 Zed는 1초 걸린다는거죠. 흠?

Zed의 공동 창업자인 Antonio는 확신에 찬 어투로 “이거 더 빠르게 만들 수 있어요.” 라고 했고 아직 코드 베이스에 익숙하지 않았던 저는 머리속으로 “과연?” 이라는 작은 불신을 안고 코드 작업에 들어갔습니다.

문제가 될 만한 코드는 이겁니다.

 pub fn select_all_matches(
     &mut self,
     action: &SelectAllMatches,
     cx: &mut ViewContext<Self>
 ) -> Result<()> {
      self.push_to_selection_history();
      let display_map = self.display_map.update(cx, |map, cx| map.snapshot(cx));

      loop {
          self.select_next_match_internal(&display_map, action.replace_newest, cx)?;

          if self.select_next_state.as_ref().map(|selection_state| selection_state.done).unwrap_or(true)
          {
              break;
          }
      }

      Ok(())
  }

자세한 건 나중에 보고, 현재 중요한건 중간에 보이는 저 loop입니다. 해당 코드는 대부분의 사람들이 자연스럽게 코드를 구현하는 방식일겁니다. select_all_matches에서 반복문을 돌며 select_next_match가 없을 때까지 시행하는 것이죠.

Antonio랑 같이 코드를 보고 있던 저는 아마 지금 이 글을 읽고 있는 여러분 수준의 이해도였지만, Antonio는 내부적인 로직을 이해하고 있었습니다. 그의 방법은 select_next_match_internal을 인라인 처리한 뒤 배치로 수정하는 거 였습니다.

웹 어플리케이션에서 N+1 문제를 다루는 방식과 유사하다고 생각해주시면 됩니다. 이런식으로 요청을 처리하는 것 보다:

loop {
  user = loadNextUser()
  if user == null {
    break
  }
  profilePicture = loadUserProfilePicture(user)
  blogPosts = loadLastFiveBlogPosts(user)

  render_template("user_profile", user)
}

이런 느낌이랄까요.

users = loadAllUsers()
pictures = loadUserProfilePicturesForUsers(users)
blogPosts = loadLastFiveBlogPostsForUsers(users)
for user in users {
  render_template("user_profile", user)
}

뭐 대충 이런식이죠.

위 방식을 아까 코드에 적용 시켰다고 보면 됩니다. 자세한 건 대충 훑어보시고, 전체적인 흐름만 이해하면 됩니다.

pub fn select_all_matches(
    &mut self,
    _action: &SelectAllMatches,
    cx: &mut ViewContext<Self>,
) -> Result<()> {
    self.push_to_selection_history();
    let display_map = self.display_map.update(cx, |map, cx| map.snapshot(cx));

    self.select_next_match_internal(&display_map, false, None, cx)?;
    let Some(select_next_state) = self.select_next_state.as_mut() else {
        return Ok(());
    };
    if select_next_state.done {
        return Ok(());
    }

    let mut new_selections = self.selections.all::<usize>(cx);

    let buffer = &display_map.buffer_snapshot;
    let query_matches = select_next_state
        .query
        .stream_find_iter(buffer.bytes_in_range(0..buffer.len()));

    for query_match in query_matches {
        let query_match = query_match.unwrap(); // can only fail due to I/O
        let offset_range = query_match.start()..query_match.end();
        let display_range = offset_range.start.to_display_point(&display_map)
            ..offset_range.end.to_display_point(&display_map);

        if !select_next_state.wordwise
            || (!movement::is_inside_word(&display_map, display_range.start)
                && !movement::is_inside_word(&display_map, display_range.end))
            {
                self.selections.change_with(cx, |selections| {
                    new_selections.push(Selection {
                        id: selections.new_selection_id(),
                        start: offset_range.start,
                        end: offset_range.end,
                        reversed: false,
                        goal: SelectionGoal::None,
                    });
                });
            }
    }

    new_selections.sort_by_key(|selection| selection.start);
    let mut ix = 0;
    while ix + 1 < new_selections.len() {
        let current_selection = &new_selections[ix];
        let next_selection = &new_selections[ix + 1];
        if current_selection.range().overlaps(&next_selection.range()) {
            if current_selection.id < next_selection.id {
                new_selections.remove(ix + 1);
            } else {
                new_selections.remove(ix);
            }
        } else {
            ix += 1;
        }
    }

    select_next_state.done = true;
    self.unfold_ranges(
        new_selections.iter().map(|selection| selection.range()),
        false, false, cx,
    );
    self.change_selections(Some(Autoscroll::fit()), cx, |selections| {
        selections.select(new_selections)
    });

    Ok(())
}

70 줄이나 되는 코드인데 syntax highlighting이 없군요. 죄송합니다. 아무튼, 코드를 본 적이 없어도 이 코드가 대충 무슨 일을 하는지 이해 되실 겁니다.

1. 다음 selection이 있는지 확인, 없으면 리턴

2. 현재 버퍼에 있는 모든 selections을 가져옴 (let mut new_selections = …)

3. 현재 버퍼에 일치하는 값 확인 (select_next_state.query.stream_find_iter)

4. 일치 할 때 마다, new_selections에 추가 및 단어 경계 검증 로직 모듈화

5. selections 정렬 및 중복 제거

6. selections를 다시 펼침

7. 에디터에 현재 selections를 바꿔주고 렌더 시켜줌 (self.change_selections)

중간에 있는 while-loop 빼고는 대충 고차원 코드죠?

코드만 봤을 때는 최적화 한 것 같지도 않습니다. 보통 코드 최적화를 하면 생기는 흔적들이 보이지 않죠. 가령 반복문 제거를 위한 추가적인 데이터 구조, 포인터 난장판, SIMD, 신박한 데이터 구조 같은 것들이요.

하지만 보세요. 제가 이 글을 쓴 이유이자 지난 3주간 이 코드가 계속 생각난 이유입니다.

이 최적화 코드를 처음 돌렸을 때 런타임이 1s 에서 4ms로 줄었습니다. 4 ms!

믿을 수 없었죠. 4ms 라니, 코드는 아직 고차원이고 수많은 unfold_range를 호출하고, 일치하는 단어를 모두 검색하고, 단어 경계를 검증하는 코드와, 정렬 및 중복 제거에 렌더링까지 다시 하는데 4ms 라니요!

만약 이걸 읽으면서 “4ms? 어쩌라고? 요즘 컴퓨터에서 4ms는 엄청 느린건데?” 라고 생각한다면, 당신이 맞아요. 4ms는 컴퓨터에게 정말 긴 시간입니다. 다만 당신의 반응으로만 짐작건대 저랑 같은 세대의 프로그래머가 아닌 것 같군요. 전 웹 사이트, 웹 어플리케이션, 백엔드를 무수히 개발하면서 4ms 걸리는 프로그램을 본적이 거의 없습니다. 프랑크푸르트에서 가장 가까운 데이터 센터까지 핑 쏘는데 10ms가 걸리는데 어떤 프로그램이 그보다 더 적은 시간을 기록할 수 있을까요?

아무튼 전 이 코드가 4ms 걸리는 것을 보면서, “이게 Rust 애호가들이 그렇게 외치던 무비용 추상화인가?” 라고 생각했습니다. 물론, 이 주장을 처음 듣는 것도 아니고 Rust로 몇년 간 코딩 했으니 Rust가 빠르다는 주장이 딱히 새롭지도 않습니다.

하지만 2351번의 일치 기록을 5184 줄의 XML 파일에서 단 4ms 만에 찾아 내는 것을 보면, 잘 모르겠네요. 제 생각이 바뀔지도요.

—-

원글: https://registerspill.thorstenball.com/p/from-1s-to-4ms