Tree Borrows

(plf.inf.ethz.ch)

1P by GN⁺ 3일전 | ★ favorite | 댓글 1개

Rust 언어의 불안전(unsafe) 코드 최적화 한계를 극복하기 위한 새로운 메모리 모델인 Tree Borrows를 제안
기존 Stacked Borrows 방식이 실무 Rust 코드에서 자주 쓰이는 여러 패턴을 허용하지 못했던 문제를 Tree Borrows가 트리 구조로 해결, 더 현실적이고 유연한 규칙을 제공함
Tree Borrows는 Stacked Borrows보다 54% 더 많은 실세계 코드 테스트 케이스를 통과시킴
주요 Rust 메모리 안전성과 최적화 가능성(특히 read-read reordering 등)을 대부분 유지함과 동시에, 최신 Rust borrow checker의 고급 기능까지 반영함
트리 기반 상태 기계 모델을 도입해, Rust 최적화와 안전성 검증 연구에 중요한 이정표를 제시함

Rust의 소유권 시스템과 unsafe 코드의 한계

Rust는 소유권 기반 타입 시스템을 통해 메모리 안전성과 데이터 레이스 방지 등 강력한 보장을 제공함
그러나 Rust에는 unsafe escape hatch가 존재하며, 이 경우 안전성 검증이 컴파일러가 아닌 개발자의 책임으로 넘어감
컴파일러는 강력한 최적화를 위해 포인터 별칭(alias) 규칙을 활용하고 싶지만, 잘못된 unsafe 코드로 인해 이러한 최적화가 무력화될 수 있음

Stacked Borrows와 그 한계

기존에는 Stacked Borrows라는 모델이 unsafe 코드의 '잘못된 동작'을 정의하고 최적화 기준을 제시함
하지만 이 방식은 실제 Rust 코드에서 흔한 여러 unsafe 패턴을 허용하지 못하고, 최근 도입된 Rust의 borrow checker 기능도 반영하지 못함

Tree Borrows의 등장

Tree Borrows는 Stacked(스택) 구조 대신 트리 구조로 메모리 권한을 추적하는 새로운 모델임
이로써 더 많은 실무 Rust 코드 패턴을 안전하게 허용하며, borrow 규칙의 유연성과 현실 적용성을 크게 높임
30,000개의 Rust 인기 크레이트 평가에서 Stacked Borrows보다 54% 더 많은 테스트 케이스를 통과함

Tree Borrows의 특징 및 장점

기존 Stacked Borrows의 주요 최적화(예: read-read reorderings) 를 대부분 유지함
더불어 최신 Rust borrow checker의 고급 기능(예: 비정형 borrow 패턴, 복잡한 포인터 조작 등)도 반영 가능
트리 기반 상태 기계 모델을 도입해, 안전성과 최적화 가능성의 균형을 맞춤

결론 및 의의

Tree Borrows는 Rust 컴파일러의 unsafe 코드 처리와 최적화 연구에 새로운 기준을 제시함
실무 Rust 코드와 최신 borrow checker 정책까지 아우르는 현실적이고 강건한 메모리 모델로 평가됨
관련 논문, 아티팩트, 소스코드는 공개되어 Rust 컴파일러 및 검증 연구 커뮤니티에 큰 영향을 줄 전망임

▲

GN⁺ 3일전 [-]

Hacker News 의견

최근 Ralf Jung의 블로그 포스트에서 더 많은 맥락 제공함 링크
보너스: Rust의 실행 의미론을 Rust의 방언으로 명확히 지정하려는 연구 그룹의 최근 발표도 추천함 유튜브
컴파일러 입장에서 포인터 에일리어싱 관련 타입 시스템의 강력한 보장을 활용해 강력한 최적화를 할 수 있다는 주장이 있는데, 실제론 얼마나 효과가 있는지 궁금함
Linus Torvalds는 C의 strict aliasing 규칙은 별 효용이 적고 오히려 문제를 일으킨다고 오랫동안 주장해왔음
그의 예시 글도 흥미로움
Rust가 본질적으로 C와 근본적으로 다른지 궁금한데, 개인적 경험으로 보면, 특히 unsafe가 연관되면 별 차이 없게 느껴짐
- C의 strict aliasing 규칙은 정말 별로라고 생각함
  Rust에서 제안하는 규칙은 훨씬 다르고, 컴파일러 입장에서도 더 유용하고, 프로그래머 입장에서도 부담이 덜하다고 봄
  in-language opt-out로 raw pointer를 사용할 수 있고, 코드를 체크할 수 있는 툴도 있음
  결국 모든 언어 설계와 마찬가지로 타협임
  Rust가 이 최적화 영역의 새로운 밸런스를 찾은 것 같고, 그 판단의 결과는 시간이 말해줄 것임
- Rust의 에일리어싱 규칙은 C와 아주 다름
  C에서는 restrict 키워드가 거의 함수 인자에만 의미가 있고, 타입 기반 에일리어싱(type-based aliasing)은 실제로는 별로 안 쓰이거나 쓰기 불편함
  Rust에서는 라이프타임, 가변성을 정교하게 표현하고 타입 자체와 무관하게 다양한 방식으로 메모리를 안전하게 다룰 수 있음
  중첩되는 &mut 참조만 안 생기고, 여러 non-overlapping &mut로 쪼개는 식으로도 이용 가능한 점이 큼
- 실제로 이게 얼마나 성능에 영향을 주는지 더 광범위한 분석이 궁금함
  간단히 에일리어싱 정보를 LLVM에 전달하는 부분을 compiler에서 전부 빼고 성능을 비교해보면 바로 알 수 있음
  'noalias' 어노테이션이 런타임에서 약 5% 성능을 개선시켜준다는 주장도 있는데, 관련 코멘트가 있음(데이터가 오래되긴 했지만)
- Linus가 컴파일러 관련해 말하는 것은 감안하는 것이 좋음
  OS 커널과 컴파일러는 완전히 다른 영역임
  요즘엔 에일리어스 분석이 정말 강력한 성능 개선의 핵심임
  가장 큰 효과는 단순한 휴리스틱에서 나오고, 복잡한 에일리어스 쿼리는 그 자체로 활용도가 낮음
  이론적으로 완벽한 에일리어스 분석이 성능을 얼마나 올릴지 실험해보고 싶은데, 일반 코드에서도 약 20% 정도가 한계일 것 같음
  물론 아주 고급 최적화(예: 데이터 레이아웃 변환)는 에일리어스 분석이 없으면 시도조차 안 하게 되는 한계가 있음
- C의 strict aliasing과 Rust의 aliasing은 개념이 다름
  C는 타입 기반 분석(TBAA)이 핵심이고, Rust는 이를 의도적으로 채택하지 않았음
Stacked Borrows 관련 과거 스레드들이 2020년, 2018년에 있었음
2020 스레드
2018 스레드
Tree Borrows 사양을 Nevin의 웹사이트에서 몇 년 전 읽었는데, 복잡한 문제도 우아하게 해결해 인상 깊었음
실제 경험상 Tree Borrows는 Stacked Borrows에서는 불가능한 합리적인 코드를 가능하게 함
Rust 표준 라이브러리의 예제 코드도 참고할 만함
Rust 또는 차세대 PL이 특성과 목적(컴파일 속도, 런타임 속도, 알고리즘 유연성 등)이 다른 여러 borrow checker 구현 중에서 선택할 수 있게 발전할 수 있을지 궁금함
- Rust는 이미 borrow checker 구현 전환을 지원함
  스코프 기반에서 비-렉시컬로 바뀌었고, Polonius라는 실험적 구현도 옵션임
  새 구현이 준비되면 구버전은 굳이 남기지 않음
  런타임 체크가 필요한 Rc, RefCell 등으로 더 유연하게 쓸 수도 있음
- affine type(Rust 사용), linear type, 효과 시스템, dependent type, 형식적 증명 등 다양한 방법이 이미 존재함
  각 방식마다 구현 비용, 성능, 개발 경험 등 특성이 달라짐
  Rust 외에도 생산성 높은 자원 자동 관리와 타입 시스템의 조합이 추구되는 경향이 있음
- 실제로 필요한 것은 함수의 precondition을 정밀하게 명시하고 중간 조건 증명까지 할 수 있는 separation logic임
  Rust의 접근법은 사람들이 실제로 원하는 보통의 불변조건을 시스템화해 강력한 최적화를 보장하는 것임
- borrow checker의 결과가 false negative만 있지 false positive는 없는 게 맞는지 궁금함
  만약 그렇다면 여러 구현을 쓰레드에서 병렬로 돌려서 빠른 승자 결과를 사용하는 것도 가능한지 의문임
- 여러 borrow checker 구현을 동시에 허용하면 생태계가 분열되기 쉽기 때문에 바람직하지 못함
논문에 나온 Rust 코드를 실제로 테스트해봤는데, 최신 안정화 컴파일러에서는 거부되지 않음을 확인함
예시 코드:
```
fn write(x: &mut i32) {*x = 10}

fn main() {
  let x = &mut 0;
  let y = x as *mut i32;
  //write(x); 
  *x = 10; 
  unsafe {*y = 15 };
}
```
- Stacked Borrows는 miri의 런타임 모델임
  miri에서 위 코드를 실행해보면 *x = 10;에서 에러를 보고하지만, write(x);에서는 에러가 발생하지 않음
  rustc는 타입시스템 관점에서 y가 *mut이기 때문에 두 버전 모두 거부할 이유가 없음
논문에서 unsafe 코드의 문제로 아래 예시를 들고 있음:
```
fn main() {
  let mut x = 42;
  let ptr = &mut x as *mut i32;
  let val = unsafe { write_both(&mut *ptr, &mut *ptr) };
  println!("{val}");
}
```
이것이 실제로 가능한지 의문임
동일 변수에 여러 mutable 참조를 포인터로 사용하는 것은 분명 UB인데, 내가 뭔가 오해하는 부분이 있는지 궁금함
- 이 연구의 핵심은 UB(정의되지 않은 동작)의 경계를 정확히 명시하는 것임
  위 코드는 Rust 컴파일러가 받아들이더라도 규칙을 위반함
  어떤 규칙이냐?

borrow checker에 통과하는 코드는 합법임
unsafe는 불법/UB도 표현 가능함
borrow checker 범위보다 넓지만 여전히 합법인 규칙 집합이 있음
이 연구는 그 경계를 엄밀히 지정하는 게 목적임
Stacked Borrows 논문은 더 단순하지만 실제 unsafe 코드에 한계를 가졌고, Tree Borrows는 더 넓은 안전 범위를 인정함
- "여러 mutable 참조 포인터가 동시에 존재할 수 없다"는 점은 분명하지만, 그걸 정확히 어느 규칙이 위반한다고 명확히 언급된 부분이 없음
  Tree Borrows는 바로 그러한 정의를 제안함
  "코드가 이런 짓을 할 수 있다"는 표현은, 실제로 해당 코드를 만들고 실행하면 뭔가가 동작하지만, Tree Borrows 같은 정의 없이는 왜 이게 잘못됐다는 근거 마련이 어렵다는 뜻임
  스스로도 Tree Borrows 같은 명확한 규칙 필요성을 이미 받아들이고 있는 것 같음
- unsafe 코드는 저런 식으로 실제 가능하고, 그것이 UB라는 점임
  예시: playground 링크
- 관련 맥락을 알고 싶으면 논문에 바로 다음 문단의 시작 부분이 의도를 잘 드러냄

Rust 컴파일러 개발자들이 에일리어싱 최적화를 원한다면, 위와 같은 반례 코드들을 배제할 방법이 필요함

역시 이게 바로 포인트임
여러 mutable 참조 불허 규칙을 지키기 어렵고, unsafe는 rust의 lifetime 시스템에서 보장된 것보다 훨씬 더 많은 걸 허용할 수 있음을 반영함
저자 중 한 명인 Neven Villani는 Fields medal 2010 수상자인 Cédric Villani의 아들임
사과는 멀리 떨어지지 않는다는 비유가 떠오름
- 그리고 "qualities도 tree에서 borrow 했다고 할 수 있음"이라고 재치있게 말해보고 싶었음
- 나는 아버지(Fields medal 수상자)와 사무실이 가까웠던 적도 있음
  정계 진출 전 이야기임
이 모델 정말 훌륭함
내가 만드는 언어에도 구현해볼 예정임
데자뷰일 리가 없음
이 포스트를 2~3개월마다 계속 보는 느낌임
- 논문이 여러 해에 걸쳐 준비됐고, 드디어 공식적으로 출판된 것임

답변달기