为何嵌套循环迭代更快？基准测试多趋势带异常原因探究

问题1：嵌套循环比单次大循环更快的原因 #

对调用随机数生成函数的R代码做基准测试后发现：单次10000次迭代的循环，比10次外层循环包裹1000次内层循环的嵌套循环慢很多。想了解相同总迭代次数下，嵌套循环更快的原因。

问题2：基准测试图中三条趋势带的成因 #

为寻找内循环最优迭代数，测试了不同数值并绘图，发现内循环迭代数约300时性能最优，但数据呈现出三条明显的趋势带，希望明确该现象的成因。

基准测试代码 #

n_step <- c(50:3000)
benchmark1<-data.frame(matrix(ncol=12,nrow=0))
for (n in n_step){
  start_time<-Sys.time()
  best_chr<-generate_data(n)[1,]
  end_time<-Sys.time()
  run_time <- end_time - start_time
  measure <- data.frame(n, run_time, time_per_chr_roll = run_time/n) 
  measure <- cbind(best_chr, measure)
  benchmark1 <- rbind(benchmark1, measure)
  }
   
plot(benchmark1$n,benchmark1$time_per_chr_roll)

性能测试图 #

补充函数代码 #

roll_stats<-function(){
stat<-floor(runif(3,min=1,max=7))
stat=sum(stat)
return(stat)
}

generate_stats<-function(){
  stats<-c(1:6)
  for (i in c(1:6)){
    stats[i]<-roll_stats()
  }
  return(stats)
}

generate_data<-function(n){
stat_data<-data.frame()
for (i in c(1:n)){
  stats<-generate_stats()
stat_data<-rbind(stat_data,stats)
}
colnames(stat_data)<-c("roll1","roll2","roll3","roll4","roll5","roll6")
stat_data<-stat_data %>%
  mutate(sum = roll1+roll2+roll3+roll4+roll5+roll6, average = sum/6)
stat_data$count.18<-apply(stat_data,1,function(x) length(which(x==18)))
stat_data<-stat_data[order(-stat_data$sum,-stat_data$count.18),]
#write.csv(stat_data,file=paste0(n," 3d6 x6 ", floor(runif(1,min=1,max=99999999999)),".csv"))
return(stat_data)
}

一、嵌套循环比单次大循环更快的原因 #

核心源于代码中内存操作与垃圾回收的差异：

• 内存扩容开销差异：单次大循环调用generate_data(10000)时，会通过rbind不断动态扩容数据框——每次rbind都要重新分配内存、复制已有数据，数据量越大，该开销呈指数级增长。而嵌套循环每次仅处理1000行，rbind的扩容规模小，累计内存复制开销远低于单次大循环。
• 垃圾回收负担不同：单次大循环会产生超大临时对象，触发垃圾回收的频率和成本更高；嵌套循环的小批量处理让GC负担更小，不会出现单次大内存释放的阻塞。
• 函数调用压力分摊：generate_stats和roll_stats的调用开销在嵌套循环中被小批量迭代分摊，而单次大循环中大量连续的函数调用会增大解释器栈压力，间接影响执行效率。

二、基准测试图中三条趋势带的成因 #

三条趋势带与generate_data的随机数生成、排序逻辑及内存特性直接相关：

• 随机数批次生成差异：runif底层按批次获取随机数种子，不同n对应的随机数批次数量不同，不同批次的生成效率存在微小差异，形成不同趋势带。
• 排序开销的波动：generate_data最后会按sum和count.18排序数据框，排序实际开销受数据分布影响：当sum值分布集中时，排序比较操作更少；分布分散时则更多。而sum是6个3d6的和（范围6~54），不同n下的sum分布会出现阶段性集中/分散，导致排序开销呈阶梯式差异，对应图中三条趋势带。
• 内存对齐与缓存命中：当n达到不同内存页阈值时，数据框存储会触发不同内存对齐策略，CPU缓存命中率出现变化，进而导致单次迭代耗时出现阶段性差异，形成趋势带。

内容的提问来源于stack exchange，提问作者Phenomniverse