Is it strange that it's slower in jart's testing but claimed to be faster in the AlphaDev blog post?
jart doesn't provide detail about length of sequences used in testing, and AlphaDev basically says that between 6 and 249,999 elements the optimizations are slower (they only claim improvement for very small and 250k+ element sequences).
The AlphaDev numbers are so curious as well. AFAICT there's extra branching when you splice the tiny-sequence optimized versions (slower), but better sorting for the tiny sequences (faster).
Is it, like, branch prediction gets an edge when the leaf nodes of the recursion are all sorting tiny sequences? In jart's code, it's DFS, which I can only guess would trample a bit on branch prediction. I wonder if a BFS search could be better
No idea what would cause this though, curious if anyone has other ideas, I really don't know.
jart doesn't provide detail about length of sequences used in testing, and AlphaDev basically says that between 6 and 249,999 elements the optimizations are slower (they only claim improvement for very small and 250k+ element sequences).
The AlphaDev numbers are so curious as well. AFAICT there's extra branching when you splice the tiny-sequence optimized versions (slower), but better sorting for the tiny sequences (faster).
Is it, like, branch prediction gets an edge when the leaf nodes of the recursion are all sorting tiny sequences? In jart's code, it's DFS, which I can only guess would trample a bit on branch prediction. I wonder if a BFS search could be better
No idea what would cause this though, curious if anyone has other ideas, I really don't know.