Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Optimizing the Particle Life: From 400 to 4M particles

programmingattack.com

Post reply on HN
Print view View original

21–30 of 71 posts

Re: Optimizing the Particle Life: From 400 to 4M particles

#21

Post by Jupe »

smlacy wrote: post #16
Jupe wrote: post #10

This is pretty neat... Having an interest in the space for many years (on-and-off; life gets busy sometimes) - I've often lamented the lack of good pixel-level performance optimizations in graphics cards. Everything seems hell-bent on polygons. Some years ago, DirectDraw on Windows was an excellent way to optimize the graphics portion of these types of things, but that all went away as "3D Is The Way" mentality took…

The thing you describe as "per-pixel optimizations" is exactly what a fragment shader is? You don't need "a polygon" per say, you can just run said code over ever pixel in the frame for each frame. This is how simple screenspace effects are implemented, compositing, HDR, etc.

Interesting. While I've played with ShaderToy a bit, I've not gotten such a thing to run locally. Maybe I should revisit this..

I guess all that I'd need would be in-memory buffer of my field, then a single function to copy the buffer (or section of the buffer if I want larger than screen fields) to the video buffer.

Re: Optimizing the Particle Life: From 400 to 4M particles

#23

Post by Jupe »

pixelpoet wrote: post #12
Jupe wrote: post #10

This is pretty neat... Having an interest in the space for many years (on-and-off; life gets busy sometimes) - I've often lamented the lack of good pixel-level performance optimizations in graphics cards. Everything seems hell-bent on polygons. Some years ago, DirectDraw on Windows was an excellent way to optimize the graphics portion of these types of things, but that all went away as "3D Is The Way" mentality took…

There's no lack of "pixel-level performance optimisations" on GPUs, and just because basically the whole world seems to think that graphics programming == using some rasterisation library like OpenGL or DX or Vulkan or whatever for realtime applications, doesn't mean you're forced to use it or that that's all there is. Just fire up OpenCL (or CUDA, if you must) and start executing some data-parallel kernels.

That's all a little beyond me at this point. But very compelling!

As the original simulation shows, the idea is to calculate the difference and proximity of the pixels. So the drawing part is just a projection...

The ease of getting a memory buffer pointer, setting pixels within my calculation loop with simple offsets was very simple and compelling. I think I should look deeper into OpenCL/CUDA for this use-case, as I mentioned in the other response to my comment.

Thanks!

Re: Optimizing the Particle Life: From 400 to 4M particles

#24

Post by iainmerrick »

CyberDildonics wrote: post #5

This is fairly trivial stuff with underwhelming results. 4 million particles isn't much on modern hardware, even with spatial partitioning. The hardest part of spatial partitioning is probably the one dimensional partition algorithm in the first place, which can be found here: https://en.cppreference.com/w/cpp/algorithm/partition

It's not rocket science, but "trivial" is very harsh. This stuff is fiddly to get right. The author (who I assume is a student) seems to have done a good job and it's a nice writeup.

Re: Optimizing the Particle Life: From 400 to 4M particles

#25

Post by danielam »

This reminds me of a paper[0] I co-wrote during a college internship that involved simulating the evolution of a Brownian system of particles with production and annihilation rules as the evolution of probability density distributions for each particle type within a partitioned cubic periodic box. Because we were interested in how these particles segregated spatially, visualization was a matter of finding the boundaries separating each domain of particles. I made some fun little videos of the evolution of the system over time (which tracks very conspicuously the entropy production, plotted in the paper), but unfortunately, they've since been taken down from the institute's website where they were hosted. (The paper does contain some snapshots that went into these visualizations, however.)

[0] https://pubs.aip.org/aip/jcp/article-abstract/122/17/174105/...

Re: Optimizing the Particle Life: From 400 to 4M particles

#27

Post by CyberDildonics »

iainmerrick wrote: post #24
CyberDildonics wrote: post #5

This is fairly trivial stuff with underwhelming results. 4 million particles isn't much on modern hardware, even with spatial partitioning. The hardest part of spatial partitioning is probably the one dimensional partition algorithm in the first place, which can be found here: https://en.cppreference.com/w/cpp/algorithm/partition

It's not rocket science, but "trivial" is very harsh. This stuff is fiddly to get right. The author (who I assume is a student) seems to have done a good job and it's a nice writeup.

I guess you could argue that, but it's strange that people want to give a student's first project (with a lot of huge mistakes like thinking node is going to outperform C because they didn't turn optimizations on) so much interest. I think people are taken in by big numbers and assume there is something cutting edge because they don't know any better.

The results are just some particles in an extremely basic pattern, there isn't a lot of payoff.

Re: Optimizing the Particle Life: From 400 to 4M particles

#28

Post by pixelpoet »

Jupe wrote: post #23
pixelpoet wrote: post #12

Earlier quoted context omitted.

There's no lack of "pixel-level performance optimisations" on GPUs, and just because basically the whole world seems to think that graphics programming == using some rasterisation library like OpenGL or DX or Vulkan or whatever for realtime applications, doesn't mean you're forced to use it or that that's all there is. Just fire up OpenCL (or CUDA, if you must) and start executing some data-parallel kernels.

That's all a little beyond me at this point. But very compelling! As the original simulation shows, the idea is to calculate the difference and proximity of the pixels. So the drawing part is just a projection... The ease of getting a memory buffer pointer, setting pixels within my calculation loop with simple offsets was very simple and compelling. I think I should look deeper into OpenCL/CUDA for this use-case, as…

No problem, and I highly recommend using OpenCL to get started, it's actually pretty short and straightforward (lookin' at you, Vulkan compute!). So basically, the stuff in the for-loops you had before, that's the kernel you'll be writing.

I daresay it's actually easier to render things this way than getting lost in the weeds with API docs etc. A simple Mandelbrot hello-world example should be easy to understand and get compiling, and you can go from there.

Re: Optimizing the Particle Life: From 400 to 4M particles

#29

Post by pvg »

hyperbrainer wrote: post #18
pvg wrote: post #7

Earlier quoted context omitted.

Author mentions they didn't use optimization flags but doesn't include the compilation details. You can sort of guess that (relatively) unoptimized C might perform worse than V8's JIT on short, straight computational code - you're more or less testing two native code generators doing a simple thing except one has more optimizations enabled and wins.

Oh, I assumed he still did -O2, and did not do anything else. Is that bad to assume? PS: I do not use C beyond reading some of its code for inspiration, so kinda unaware

It just says 'no optimization flags' and that's that, I don't think even the compiler is mentioned so the author is not giving you a lot to go on here - you don't even know what the default is.

A modern C optimizing compiler is going to go absolutely HAM on this sort of code snippet if you tell it to and do next to nothing if you don't - that's, roughly, the explanation for this little discrepancy.

Re: Optimizing the Particle Life: From 400 to 4M particles

#30

Post by Twirrim »

The thing that strikes me as particularly weird about this is the use of numpy there. In other languages, they're using native code. In python they're reaching out to numpy, which is a great library, but not awesome inside a hot loop unless you're keeping the operation you're carrying out within numpy itself. This means, right in that hot loop, they're doing a lot of translating of numbers between python representation and native c representation.

Cutting numpy out by making the line "t = [0.0]*l" gets it down to 17059 ms, without attempting any other optimisations. Using that plus pypy (so you get the JIT that you have with javascript/v8) gets it down to 958 ms.

To show the cost of those translations, sticking with numpy. If we switch that inner loop to:

        temp_t_i = t[i]
        temp_t_i += 0.02 * j
        temp_t_i *= 0.03 * j
        temp_t_i -= 0.04 * j
        temp_t_i /= 0.05 * (j+1)
        temp_t_i = temp_t_i
It speeds us up from 47552 ms to 28251 ms. Almost half the execution time. That's still doing two hops back and forth, though. If you cut it down to a single line it's even faster at 18458 ms, cutting execution time down to about a third of the original example. Pypy isn't able to help here at all, this is sort of a pathological case for it.

edit: I'll add, I'm not that good with numpy, rarely use it myself. Not sure if it's possible to do that inner loop all within numpy somehow. I imagine that'd be a lot faster still.

Post reply on HN