콜라츠 수열 계산은 /2, *3+1 이다. 원래 계획했던 동적 계획법을 사용하면, 배열에 있는 값을 읽기 위해 ram을 읽어야 한다.
cpu는 ram에서 값을 읽어올 때 64byte를 읽어온다. (cache line)
[SSD/HDD]
│ (4KB Page)
▼
[RAM]
│ (64B Cache Line)
▼
[CPU Cache: L3 → L2 → L1]
│ (8~64B Register width)
▼
[Registers]
▼
[ALU]
| 계층 | 용량 | 속도 | 위치 / 특징 | 접근 비용(대략) |
|---|---|---|---|---|
| Register | 수십~수백 Byte | 매우 빠름 | CPU ALU 바로 옆 | ~1 cycle |
| L1 Cache | 32KB ~ 64KB / 코어 | 매우 빠름 | 각 CPU 코어 내부 | ~4 cycle |
| L2 Cache | 256KB ~ 1MB / 코어 | 빠름 | 각 CPU 코어 내부 | ~12 cycle |
| L3 Cache | 몇 MB ~ 수십 MB (공유) | 중간 | 여러 코어가 공유 | ~40 cycle |
| RAM | GB 단위 | 느림 | CPU 외부 (메모리 버스) | ~100~200 cycle |
| SSD | 수십~수백 GB | 매우 느림 | 메모리 계층 바깥 (I/O) | ~100,000 cycle |
내 프로젝트처럼 속도가 중요할 때, 그냥 연산하는 것보다 의미가 있으려면 적어도 cpu캐시 안에는 데이터가 있어야 한다.
근데 그 안에 들려면 64b정도의 용량을 사용하는데, 1bit씩 써도 512개밖에 못쓴다.
그러므로 동적계획법은 안한다. 원래 숫자보다 작아질 떄 종료하는 것까지만 한다.
이제 멀티스레드를 사용해야 한다.
use rayon::prelude::*;
use std::io::{self, Write};
use std::time::Instant;
fn main(){
let start = Instant::now();
let goal_num=1 << 28;
(3..goal_num).into_par_iter()
.filter(|x| x % 2 == 1)
.for_each(|i| {
calculation(i);
if i%(goal_num/16-1)==0{print!("{i} ");}
io::stdout().flush().unwrap();
});
println!("end {goal_num} numbers");
let elapsed = start.elapsed();
println!("걸린 시간: {:?}", elapsed);
}
fn calculation(i:u128){
let mut n=i;
while n>=i{
if n%2==0{n=n>>1;}
else{n=(n<<1)+n+1;}
}
}
rayon으로 병렬 처리, std::time::Instant으로 시간 측정했다.
rayon이 cpu스레드 개수를 자동 인식한다고 한다. 생각보다 편하다.
if문을 없애고 비트연산으로 바꾸어야 병렬처리가 효율이 높아진다.
저수준 최적화를 해보니, cs지식이 중요하다는걸 느낀다.
유행타는 지식과 다르게 cs지식/수학개념 등은 쉽게 변하지 않는다고 생각한다. 이런 지식은 책 한권은 보고 제대로 공부를 하고, 유행타는 지식은 인터넷으로 빠르게 배우는게 좋을 것 같다.
또 어설프게 최적화 하면 더 느려진다는걸 알게 되었다. ㅎㅎ