9 ms·
Optimizing the Particle Life: From 400 to 4M particles
- hyperbrainer 3y agoWhy was C slower though?
- KeplerBoy 3y agoNo optimization flags could be a big part of the reason. Haven't looked closely at the code or tried it, but with -O3, -fopenmp and a well-placed pragma the performance could increase many-fold. Heck, with NVC++ you could offload that thing to a GPU with minimal effort and have it flying at the memory bandwidth limit.
- wzdd 3y agoSimply compiling it with -O3 produces something which completes in half the time of the JavaScript version (350ms for C, 750ms for JS), so perhaps that. Edit for Twirrim: on this system (Ryzen 7, gcc 11): "-O3": 350ms; "-O3 -march=native": 208ms; "-O2": 998ms; "-O2 -march=native": 1040ms. Edit 2: Interestingly, changing the C from float to double produces a 3.5x speedup, taking the time elapsed (with "-O3 -march=native") to 58ms, or about 12x faster than JS. This also makes what it's computing closer to the JavaScript version.
- anon946 3y agoDid you add output of the results to the C code?
- wzdd 3y agoI did not, but I confirmed with objdump that my compiler was not removing the code. (But to be sure, I just ran it again with an output and got the same value.)
- Twirrim 3y agoFor fun and frolics: No flags: 1843ms -march=native: 2183 ms -O2: 423 ms -O2 -march=native: 250 ms -O3: 425 ms -O3 -march=native: 255 ms O3 doesn't seem to be helping in my case.
- Tadpole9181 3y agoThey didn't use any optimization flags.
- Twirrim 3y agoYeah, I was just trying to show the difference. Doing it without optimisation flags is an utterly bewildering decision by the author.
- deleted 3y ago[deleted]
- nickpsecurity 3y agoEspecially given the goal was increasing performance.
- jasonjmcghee 3y agoSeems crazy to me that double would produce that kind of speed up. Is float getting emulated somehow? Don't they end up the same size?
- jlarocco 3y ago> Don't they end up the same size? No. Float is half the size of double.
- suby 3y agoMy intuition would have been that floats were faster because of this. Less memory to iterate through.
- fartsucker69 3y agoit is faster in just about every way. less memory, even the cpu instructions (which are usually not the problem) are faster. there's something fucky going on with code gen here. or it could also simply be the measurement procedure that is doing something weird like working with not properly cold or equally warmed up data or instruction caches.
- pvg 3y agoAuthor 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.
- hyperbrainer 3y agoOh, 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
- pvg 3y agoIt 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.
- anon946 3y agoIMO, not using any optimization flags with C is somewhat arbitrary, since the compiler writers could have just decided that by default we'll do thing X, Y, and Z, and then you'd need to turn them off explicitly. FWIW, without -O, with -O, and with -O4, I get 2500ms, 1500ms, and 550ms respectively. I didn't bother to look at the .S to see the code improvements. (Of course, I edited the code to output the results, otherwise, it just optimized out everything.)
- hyperbrainer 3y ago> (Of course, I edited the code to output the results, otherwise, it just optimized out everything.) O(1) :)
- caranea 3y agoThanks for posting your results! Since I was already set on writing in-browser particle life, I didn't benchmark C code with different flags.
- anon946 3y agoCompletely reasonable. I'd probably edit your blog post a bit to indicate that.
- TylerE 3y agoShould also test -Os when doing this sort of thing. Sometimes the reduced size greatly improves cache behavior, and even when not it's often outright competitive with at least -O2 anyway (usually compiles faster too!)
- abainbridge 3y agoOne optimization for the C code is to put "f" suffixes on the floating point constants. For example convert this line: t[i] += 0.02 * (float)j; to: t[i] += 0.02f * (float)j; I believe this helps because 0.02 is a double and doing double * float and then converting the result to float can produce a different answer to just doing float * float. The compiler has to do the slow version because that's what you asked for. Adding the -ffast-math switch appears to make no difference. I'm never sure what -ffast-math does exactly. Minimal case on Godbolt: https://godbolt.org/z/W18YsnMY5 https://godbolt.org/z/W18YsnMY5 - without the f https://godbolt.org/z/oc1s8WKeG https://godbolt.org/z/oc1s8WKeG - with the f
- CyberDildonics 3y agoThis 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 https://en.cppreference.com/w/cpp/algorithm/partition
- deleted 3y ago[deleted]
- iainmerrick 3y agoIt'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.
- CyberDildonics 3y agoI 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.
- caranea 3y agoOne point needs correcting though - nowhere in the article I say that node is outperforming C, on the contrary - I stressed that I didn't use any flags so that people don't come to a conclusion that C would be always slower, and I explicitly mentioned not get fixated on such benchmarks. What it was meant to show is that V8 is *good enough* to even consider it for the job :)
- CyberDildonics 3y ago
- atulvi 3y ago4M particles is not the question. what's the framerate?
- bee_rider 3y agoYou can go to the “next” story at the bottom of the post, and then the author has some links to an online implementation.
- jasonjmcghee 3y agoWould vary significantly based on the GPU, I would assume.
- Jupe 3y agoThis 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 over. My explorations of Processing.* were neat, but lacked the IDE and library support I like as a developer.
- pixelpoet 3y agoThere'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.
- Jupe 3y agoThat'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!
- pixelpoet 3y agoNo 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.
- deleted 3y ago[deleted]
- bee_rider 3y agoSince I’m on my phone, I can only try the 2D js versions, but the quadtree version does seem to provide some really obvious and nice frame rate improvements. It seems like good work, although I don’t know much about this field. Sidenote: I’m often too self conscious to put anything technical online with my real name on it, probably a bit of imposter syndrome or something. I think based on > For one of my programming classes this semester, my task was writing a program in Python. It was only an introductory course, so it didn’t have to be anything fancy. the author is sort of early on in their career. I often suspect I’d be better off if I’d gotten over myself and thrown more early experiments online. I dunno, maybe this stuff just isn’t a big deal for some people, but I have to applaud the bravery.
- _neil 3y agoGive yourself to the embarrassment. Publish for your past self. Or publish for someone smarter to come along and correct you. (Currently trying to take this advice as well)
- alook 3y agoLove this advice. I’ve always struggled with the same thing. One friend started telling me to get over myself and publish, then he reworded it to: “Get over being under yourself.” For some reason that one stuck with me and gave me the strength to ship my first few pieces of writing.
- peter_l_downs 3y agoI was having trouble finding the link to the actual project, so here you go: - Github repo https://github.com/Caranea/gpulife https://github.com/Caranea/gpulife - Finished particle simulator https://webgpulife.netlify.app/ https://webgpulife.netlify.app/
- danielam 3y agoThis 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/922173/Pattern-formation-in-nonextensive-thermodynamics https://pubs.aip.org/aip/jcp/article-abstract/122/17/174105/...
- Monalisa12 3y ago[flagged]
- Twirrim 3y agoThe 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.
- nerpderp82 3y agoThis is the problem that Numba was designed to solve. https://numba.readthedocs.io/en/stable/user/5minguide.html https://numba.readthedocs.io/en/stable/user/5minguide.html
- cl3misch 3y agoNo. The problem in this post can be vectorized (== expressed as array OPs) with idiomatic numpy, making it very fast (see sibling comment). Numba is designed to speed up code where looping is unavoidable, i.e. the code can't be (easily) expressed as array OPs.
- GeompMankle 3y agoNegative again, a series of array operations which are individually idiomatic numpy like this will run very very fast in numba as it can coalesce the ops into a single pass through memory. Numpy can't do this and has to pass through the array for each individually array operation. There's nothing wrong with straight numpy but if you want it compiled-C fast for the whole ensemble of array ops, you need a JIT.
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- chris_va 3y agoSounds like they are slowly learning electrostatic PIC codes from first principles.