5 ms·

An Optimization Story

80 points by lukastyrychtr 5y ago

petermcneeley 5y ago
Great post. Nice to see some comp phys on HN. I do think a few diagrams would help clear up whats happening here. For example explaining why the Hamiltonian is 8x8.
sampo 5y ago
This kind of procedural array-based numerical code, would be easier to rewrite in Fortran than in Rust. Fortran syntax is closer to the original Python syntax, than Rust is. And Fortran is easier to learn than Rust. But the author already knows Rust, so.
dahart 5y ago
How big are the spectra, and how big is the data for a full run here? I had a hard time getting a sense for that. I was expecting the story to turn and show a huge ~100x coming from numpy, and surprised by the very small impact. That’s exactly what’s happened to me when I’ve switched image processing or simulations from raw python to numpy. Maybe I’m completely misunderstanding the problem, but it looks like the issue might be that numpy is not bubbled all the way up to be the outside of the main loop, maybe in this case on the outside of the entire spectrum calculation (if I’m understanding the problem at all). To see the real gains from numpy, you have to turn your program all the way inside out.
- dr_zoidberg 5y ago
  I got a weird feeling from the article in which the author seems to know quite a bit about numpy (citing a few parts of the source even!) but then it uses python loops all around! Just like you, I'm not really following the domain calculations, so maybe there's a reason that code can't be properly vectorized. But as others have commented, I'm a bit at a loss why the author didn't try numba or Cython.
geysersam 5y ago
This looks like a situation where Numba would be very useful. https://numba.pydata.org/ https://numba.pydata.org/
gorg_dc 5y ago
Disclaimer: I do not understand enough of the code and of the domain. The code itself looks slow and barely readable. A lot of for loops, few named functions. It needs a very strong refactoring to work properly with numpy. That should be done first, instead of pulling up the RuStIsFast card. It is not surprising that the results were not so great as expected. In general, the article is too long to be properly understood...
- cogman10 5y ago
  Agreed. But also, there were a few missed optimizations. The most obvious (to me) is the constant indexing into pigs. It was hit on in the article (and gave a 25% increase in speed), yet I don't think the author went far enough in elimination. Pushing the pig_j lookup up into the "for j" scope instead of computing it on each inner loop would have likely saved a large number of the lookups. In fact, I'd guess that'd be one of the optimizations that rust pulls out. Python is far less likely to pull those sorts of optimizations.
  - Twirrim 5y ago
    I did a double take at that section, the text implied they'd spotted that one, and shifted the look up, and I was trying to figure out if they'd shared the wrong bit of code and assumed they had. But after seeing your comment and re-reading that passage I'm not sure they did.
- deleted 5y ago
  [deleted]
boyter 5y ago
Nice. I love these posts so much I keep a collection of them. For this though “one of the easiest ways to make a program faster is to make it do less work”. Correct me if I am wrong but isn’t that the only way to make programs faster? Do less work on a single core is the only method I have ever seen. Everything, from memory alignment to SIMD is just reducing the amount of steps. Would be happy to know an exception to this.
- rageoholic 5y ago
  There's also stuff you can optimize like cache efficiency. Sometimes you can do more work on an array than a linked list but the array is faster because linked lists miss cache pretty consistently.
dmitrygr 5y ago
[flagged]
rstuart4133 5y ago
This was the surprising new factoid for me: > The [Rust to] Python interop was shockingly easy. I wouldn't even know how to begin doing this with C. I do know how to do it with C. I would not describe it as "shockingly easy". It's not difficult either, but a type safe shockingly easy alternative is definitely worth a look.

80 points by lukastyrychtr 5y ago

Great post. Nice to see some comp phys on HN. I do think a few diagrams would help clear up whats happening here. For example explaining why the Hamiltonian is 8x8.

sampo 5y ago

This kind of procedural array-based numerical code, would be easier to rewrite in Fortran than in Rust. Fortran syntax is closer to the original Python syntax, than Rust is. And Fortran is easier to learn than Rust. But the author already knows Rust, so.

dahart 5y ago

How big are the spectra, and how big is the data for a full run here? I had a hard time getting a sense for that. I was expecting the story to turn and show a huge ~100x coming from numpy, and surprised by the very small impact. That’s exactly what’s happened to me when I’ve switched image processing or simulations from raw python to numpy. Maybe I’m completely misunderstanding the problem, but it looks like the issue might be that numpy is not bubbled all the way up to be the outside of the main loop, maybe in this case on the outside of the entire spectrum calculation (if I’m understanding the problem at all). To see the real gains from numpy, you have to turn your program all the way inside out.

dr_zoidberg 5y ago
I got a weird feeling from the article in which the author seems to know quite a bit about numpy (citing a few parts of the source even!) but then it uses python loops all around! Just like you, I'm not really following the domain calculations, so maybe there's a reason that code can't be properly vectorized. But as others have commented, I'm a bit at a loss why the author didn't try numba or Cython.

geysersam 5y ago

This looks like a situation where Numba would be very useful. https://numba.pydata.org/ https://numba.pydata.org/

gorg_dc 5y ago

Disclaimer: I do not understand enough of the code and of the domain. The code itself looks slow and barely readable. A lot of for loops, few named functions. It needs a very strong refactoring to work properly with numpy. That should be done first, instead of pulling up the RuStIsFast card. It is not surprising that the results were not so great as expected. In general, the article is too long to be properly understood...

cogman10 5y ago
Agreed. But also, there were a few missed optimizations. The most obvious (to me) is the constant indexing into pigs. It was hit on in the article (and gave a 25% increase in speed), yet I don't think the author went far enough in elimination. Pushing the pig_j lookup up into the "for j" scope instead of computing it on each inner loop would have likely saved a large number of the lookups. In fact, I'd guess that'd be one of the optimizations that rust pulls out. Python is far less likely to pull those sorts of optimizations.
- Twirrim 5y ago
  I did a double take at that section, the text implied they'd spotted that one, and shifted the look up, and I was trying to figure out if they'd shared the wrong bit of code and assumed they had. But after seeing your comment and re-reading that passage I'm not sure they did.
deleted 5y ago
[deleted]

boyter 5y ago

Nice. I love these posts so much I keep a collection of them. For this though “one of the easiest ways to make a program faster is to make it do less work”. Correct me if I am wrong but isn’t that the only way to make programs faster? Do less work on a single core is the only method I have ever seen. Everything, from memory alignment to SIMD is just reducing the amount of steps. Would be happy to know an exception to this.

rageoholic 5y ago
There's also stuff you can optimize like cache efficiency. Sometimes you can do more work on an array than a linked list but the array is faster because linked lists miss cache pretty consistently.

dmitrygr 5y ago

[flagged]

rstuart4133 5y ago

This was the surprising new factoid for me: > The [Rust to] Python interop was shockingly easy. I wouldn't even know how to begin doing this with C. I do know how to do it with C. I would not describe it as "shockingly easy". It's not difficult either, but a type safe shockingly easy alternative is definitely worth a look.