7 ms·

Revisiting the Business Card Raytracer

176 points by vanni 6y ago

ntry 6y ago
101,000ms to 150ms is a phenomenal speedup. Props
- correct_horse 6y ago
  To be fair, the thing he started with was totally unreadable and fits on a business card and the thing he ended up with was readable, but didn't fit. It isn't apples-to-apples.
  - sp332 6y ago
    The original is 1,287 bytes after removing comments and line endings where possible. After just a bit of search-and-replace to shrink variable names, I got the new one down to 2,373 bytes including the same error checking and output at the end. So 1.8 business cards, which is not too bad. And no I haven't tried to compile it. https://pastebin.com/LDRd6U4e https://pastebin.com/LDRd6U4e
    - a1369209993 6y ago
      Hmm, some further improvements: typedef float F;typedef int I; // saves 2 lines (but zero bytes) #define R return // OR #define O(S,A,R) operator S(A){return R;} #define E(F){E_((F||cudaPeekAtLastError)(),__FILE__,__LINE__);} and so on - although you'd probably have to make semantic chages to get onto a single card. (Or use a smaller font, but that's presumably cheating.)
      - sp332 6y ago
        I feel like the self-timing and error-checking is unnecessary, and you can at least fit it on the front + back of a business card with enough room left for your name and an email address.
bigcheesegs 6y ago
> Opening the binary with Binary Ninja revealed that clang had already managed to leverage the SSE registers. X86-64 uses SSE registers for all floating point operations. I'm not sure that the author realized that they were looking at an -O0 binary. -O0 does not do vectorization (or anything else for that matter).
- slavik81 6y ago
  Looking at it on Godbolt, it doesn't really leverage SSE on -O3, either. You can get a reasonable grasp of whether it's using SSE effectively or not just by looking at the instruction names. mulss: multiplication of a single single-precision floating point value. mulsd: multiplication of a single double-precision floating point value. mulps: multiplication of a packed group of single-precision floating point values. mulpd: multiplication of a packed group of double-precision floating point values. If you're mostly seeing -ps suffixes only on moves and shuffles, you're looking at code that is not being vectorized. (And, actually, if you're seeing a lot of shuffles, that's also a good sign its not well-vectorized.) Incidentally, if you're seeing unexpected -sd suffixes, those are often due to unintended conversions between float and double. They can have a noticeable effect on performance, especially if you end up calling the double versions of math functions (as they often use iterative algorithms that need more iterations to achieve double-precision). I'm linking GCC output, because it's simpler to follow, but you see more or less the same struggle with Clang. https://godbolt.org/z/XtVqsU https://godbolt.org/z/XtVqsU
  - gorgoiler 6y ago
    Off topic: I teach compilers in high school and godbolt.org looks amazing, thanks for the link!
    - skavi 6y ago
      Wow, really cool that there are high schools teaching compilers.
      - 6y ago
lonk 6y ago
If you increase resolution you can put more code on business card :P
- mjcohen 6y ago
  4 point font!
- Y_Y 6y ago
  If you make your business cards out of silicon wafer I can get you 10nm resolution.
blondin 6y ago
i love what fabien is doing with his website! also been experimenting with pure html with an itsy-bitsy amount of css. for months now i wondered how to display code without involving javascript. that textarea is so perfect! and i bet you when you copy and paste into word or your todo list application they won't even try to be "smart" about knowing what "rich text" is... that's very cool.
- GuiA 6y ago
  i am glad that there is a small village of indomitable developers holding out against tens of megabytes of reactive functional progress modern javascript frameworks. thank you
  - wetmore 6y ago
    There is a place for both.
    - GuiA 6y ago
      It’s not so much that there’s a place for both rather than both necessarily exist as two points in the same space. But the reality is that more websites than not these days will send you many megabytes of JS, mainly for the purpose of tracking you and extracting money/time from you, under the guise of “user experience”. So when I see some of those rare people who still actually care about quality, speed, performance, accessibility, etc I make sure to appreciate their work.
- nucleardog 6y ago
  Yeah, damn, I thought I'd done well getting my page+css+font down to ~100kB (css/font cached after first load, so ~2kB on subsequent pages) but his site is tiny. Even with his CSS inlined to save a request the entire page is 15kB gzipped.
- Kwantuum 6y ago
  > that textarea is so perfect! There are no textarea on that page. The code sections are using a <pre>
danielscrubs 6y ago
Well there goes my weekend. :) I also tried to optimise the code, and got great speed increases with just constexpr the vector methods and could quickly see that rand was problematic and then Fabien releases this post with nvcc that are another level. Really great blog post!
tomsmeding 6y ago
Nice work on the GPU programming, and the multicore before that, but I'm mystified why going from -O0 to -O3 is named an "optimisation". All respect for Fabien, but running code that's supposed to run faster than a snail (and if you're not debugging and require -O0 for reasonable output) implies -O2 or -O3. (In practice, -O3 often doesn't give much performance over -O2, despite increasing compile times.) The initial time is not 101.8 seconds, it's 11.6 seconds.
- slavik81 6y ago
  You could also add -ffast-math, which loosens the rules for floating point optimizations. For example, it would allow the compiler to turn floating point divisions into multiplications by an inverse, and to group operations more efficiently even if doing so would slightly affect rounding. It also rounds denormal numbers down to zero, which can greatly improve performance on a lot of hardware. -march=native may also be useful, as it would allow the compiler to use newer CPU instructions, and tune the generated code to your hardware. That would make the program less portable, but it's not like CUDA is portable either. My machine matches those numbers surprisingly closely. With -O0 it took 89.6s. With -O3, it took 11.7s. With -Ofast (which combines -O3 and -ffast-math), it took 10.6s. With -Ofast -march=native, it took 8.9s. I would expect those gains to extrapolate to the multi-threaded version, maybe pushing it down to 1 second without any further work. (Note: I'm using GCC on Ubuntu 18.04 with a Haswell i7. Your mileage may vary.)
  - amelius 6y ago
    Offtopic, but I think that languages should have special float types that trigger the use of fast math. That way, a programmer can better control which parts of a program are done with approximate floating point operations.
    - slavik81 6y ago
      One of the reasons why I think Zig looks appealing is that you can set the policy for these sorts of things on a per-block basis: https://ziglang.org/documentation/master/#setFloatMode https://ziglang.org/documentation/master/#setFloatMode
mianos 6y ago
I wonder if the tool-chain would be better under Linux? It is kind if funny the way Windows development has always been a hassle. Mscvars.bat and such has been there for at least 20 years.
fegu 6y ago
Almost into passable frame rate territory. Next version could be business card VR:)
deleted 6y ago
[deleted]
ectoplasmaboiii 6y ago
A Ray-Tracer in 7 Lines of K: http://nsl.com/k/ray/ray.k http://nsl.com/k/ray/ray.k
- jagged-chisel 6y ago
  7? Just remove those comments and the last few newlines and it’ll be one line. I don’t know K, but it looks like it uses semicolons to end statements. It’s “cheating” on line count to compress statements by just removing \n. After all, how many “lines” are in the business card raytracer? 4.
rwmj 6y ago
Is there a mistake in the original code on the right hand side? I get: card.cpp:16:2: error: ‘g’ was not declared in this scope 16 | <g;p)t=p,n=v(0,0,1),m=1;for(i k=19;k--;) | ^ Edit: Yes there is. The ‘<g;’ seems like it should have been the single character ‘<’, perhaps a corrupted HTML escape.
- joeraut 6y ago
  Yep, I got the same error. The version here [0] works fine. [0] https://fabiensanglard.net/postcard_pathtracer/ https://fabiensanglard.net/postcard_pathtracer/
- a_e_k 6y ago
  (Original author of this code[0] here.) Yes, that looks like a corrupted copy. The line should be: <p)t=p,n=v(0,0,1),m=1;for(i k=19;k--;) [0] http://www.cs.utah.edu/~aek/code/card.cpp http://www.cs.utah.edu/~aek/code/card.cpp
rrss 6y ago
This was really fun to read, thanks fsanglard. > This is correlated with the warning nvcc issued. Because the raytracer uses recursion, it uses a lot of stacks. So much actually that the SM cannot keep more than a few alive. Stack frame size / "local memory" size doesn't actually directly limit occupancy. There's a list of the limiters here: https://docs.nvidia.com/gameworks/content/developertools/desktop/analysis/report/cudaexperiments/kernellevel/achievedoccupancy.htm https://docs.nvidia.com/gameworks/content/developertools/des.... I'm not sure why the achieved occupancy went up after removing the recursion, but I'd guess it was something like the compiler was able to reduce register usage.

176 points by vanni 6y ago

ntry 6y ago

101,000ms to 150ms is a phenomenal speedup. Props

correct_horse 6y ago
To be fair, the thing he started with was totally unreadable and fits on a business card and the thing he ended up with was readable, but didn't fit. It isn't apples-to-apples.
- sp332 6y ago
  The original is 1,287 bytes after removing comments and line endings where possible. After just a bit of search-and-replace to shrink variable names, I got the new one down to 2,373 bytes including the same error checking and output at the end. So 1.8 business cards, which is not too bad. And no I haven't tried to compile it. https://pastebin.com/LDRd6U4e https://pastebin.com/LDRd6U4e
  - a1369209993 6y ago
    Hmm, some further improvements: typedef float F;typedef int I; // saves 2 lines (but zero bytes) #define R return // OR #define O(S,A,R) operator S(A){return R;} #define E(F){E_((F||cudaPeekAtLastError)(),__FILE__,__LINE__);} and so on - although you'd probably have to make semantic chages to get onto a single card. (Or use a smaller font, but that's presumably cheating.)
    - sp332 6y ago
      I feel like the self-timing and error-checking is unnecessary, and you can at least fit it on the front + back of a business card with enough room left for your name and an email address.

bigcheesegs 6y ago

> Opening the binary with Binary Ninja revealed that clang had already managed to leverage the SSE registers. X86-64 uses SSE registers for all floating point operations. I'm not sure that the author realized that they were looking at an -O0 binary. -O0 does not do vectorization (or anything else for that matter).

slavik81 6y ago
Looking at it on Godbolt, it doesn't really leverage SSE on -O3, either. You can get a reasonable grasp of whether it's using SSE effectively or not just by looking at the instruction names. mulss: multiplication of a single single-precision floating point value. mulsd: multiplication of a single double-precision floating point value. mulps: multiplication of a packed group of single-precision floating point values. mulpd: multiplication of a packed group of double-precision floating point values. If you're mostly seeing -ps suffixes only on moves and shuffles, you're looking at code that is not being vectorized. (And, actually, if you're seeing a lot of shuffles, that's also a good sign its not well-vectorized.) Incidentally, if you're seeing unexpected -sd suffixes, those are often due to unintended conversions between float and double. They can have a noticeable effect on performance, especially if you end up calling the double versions of math functions (as they often use iterative algorithms that need more iterations to achieve double-precision). I'm linking GCC output, because it's simpler to follow, but you see more or less the same struggle with Clang. https://godbolt.org/z/XtVqsU https://godbolt.org/z/XtVqsU
- gorgoiler 6y ago
  Off topic: I teach compilers in high school and godbolt.org looks amazing, thanks for the link!
  - skavi 6y ago
    Wow, really cool that there are high schools teaching compilers.
    - 6y ago

lonk 6y ago

If you increase resolution you can put more code on business card :P

mjcohen 6y ago
4 point font!
Y_Y 6y ago
If you make your business cards out of silicon wafer I can get you 10nm resolution.

blondin 6y ago

i love what fabien is doing with his website! also been experimenting with pure html with an itsy-bitsy amount of css. for months now i wondered how to display code without involving javascript. that textarea is so perfect! and i bet you when you copy and paste into word or your todo list application they won't even try to be "smart" about knowing what "rich text" is... that's very cool.

GuiA 6y ago
i am glad that there is a small village of indomitable developers holding out against tens of megabytes of reactive functional progress modern javascript frameworks. thank you
- wetmore 6y ago
  There is a place for both.
  - GuiA 6y ago
    It’s not so much that there’s a place for both rather than both necessarily exist as two points in the same space. But the reality is that more websites than not these days will send you many megabytes of JS, mainly for the purpose of tracking you and extracting money/time from you, under the guise of “user experience”. So when I see some of those rare people who still actually care about quality, speed, performance, accessibility, etc I make sure to appreciate their work.
nucleardog 6y ago
Yeah, damn, I thought I'd done well getting my page+css+font down to ~100kB (css/font cached after first load, so ~2kB on subsequent pages) but his site is tiny. Even with his CSS inlined to save a request the entire page is 15kB gzipped.
Kwantuum 6y ago
> that textarea is so perfect! There are no textarea on that page. The code sections are using a <pre>

danielscrubs 6y ago

Well there goes my weekend. :) I also tried to optimise the code, and got great speed increases with just constexpr the vector methods and could quickly see that rand was problematic and then Fabien releases this post with nvcc that are another level. Really great blog post!

tomsmeding 6y ago

Nice work on the GPU programming, and the multicore before that, but I'm mystified why going from -O0 to -O3 is named an "optimisation". All respect for Fabien, but running code that's supposed to run faster than a snail (and if you're not debugging and require -O0 for reasonable output) implies -O2 or -O3. (In practice, -O3 often doesn't give much performance over -O2, despite increasing compile times.) The initial time is not 101.8 seconds, it's 11.6 seconds.

slavik81 6y ago
You could also add -ffast-math, which loosens the rules for floating point optimizations. For example, it would allow the compiler to turn floating point divisions into multiplications by an inverse, and to group operations more efficiently even if doing so would slightly affect rounding. It also rounds denormal numbers down to zero, which can greatly improve performance on a lot of hardware. -march=native may also be useful, as it would allow the compiler to use newer CPU instructions, and tune the generated code to your hardware. That would make the program less portable, but it's not like CUDA is portable either. My machine matches those numbers surprisingly closely. With -O0 it took 89.6s. With -O3, it took 11.7s. With -Ofast (which combines -O3 and -ffast-math), it took 10.6s. With -Ofast -march=native, it took 8.9s. I would expect those gains to extrapolate to the multi-threaded version, maybe pushing it down to 1 second without any further work. (Note: I'm using GCC on Ubuntu 18.04 with a Haswell i7. Your mileage may vary.)
- amelius 6y ago
  Offtopic, but I think that languages should have special float types that trigger the use of fast math. That way, a programmer can better control which parts of a program are done with approximate floating point operations.
  - slavik81 6y ago
    One of the reasons why I think Zig looks appealing is that you can set the policy for these sorts of things on a per-block basis: https://ziglang.org/documentation/master/#setFloatMode https://ziglang.org/documentation/master/#setFloatMode

mianos 6y ago

I wonder if the tool-chain would be better under Linux? It is kind if funny the way Windows development has always been a hassle. Mscvars.bat and such has been there for at least 20 years.

fegu 6y ago

Almost into passable frame rate territory. Next version could be business card VR:)

deleted 6y ago

[deleted]

ectoplasmaboiii 6y ago

A Ray-Tracer in 7 Lines of K: http://nsl.com/k/ray/ray.k http://nsl.com/k/ray/ray.k

jagged-chisel 6y ago
7? Just remove those comments and the last few newlines and it’ll be one line. I don’t know K, but it looks like it uses semicolons to end statements. It’s “cheating” on line count to compress statements by just removing \n. After all, how many “lines” are in the business card raytracer? 4.

rwmj 6y ago

Is there a mistake in the original code on the right hand side? I get: card.cpp:16:2: error: ‘g’ was not declared in this scope 16 | <g;p)t=p,n=v(0,0,1),m=1;for(i k=19;k--;) | ^ Edit: Yes there is. The ‘<g;’ seems like it should have been the single character ‘<’, perhaps a corrupted HTML escape.

joeraut 6y ago
Yep, I got the same error. The version here [0] works fine. [0] https://fabiensanglard.net/postcard_pathtracer/ https://fabiensanglard.net/postcard_pathtracer/
a_e_k 6y ago
(Original author of this code[0] here.) Yes, that looks like a corrupted copy. The line should be: <p)t=p,n=v(0,0,1),m=1;for(i k=19;k--;) [0] http://www.cs.utah.edu/~aek/code/card.cpp http://www.cs.utah.edu/~aek/code/card.cpp

rrss 6y ago

This was really fun to read, thanks fsanglard. > This is correlated with the warning nvcc issued. Because the raytracer uses recursion, it uses a lot of stacks. So much actually that the SM cannot keep more than a few alive. Stack frame size / "local memory" size doesn't actually directly limit occupancy. There's a list of the limiters here: https://docs.nvidia.com/gameworks/content/developertools/desktop/analysis/report/cudaexperiments/kernellevel/achievedoccupancy.htm https://docs.nvidia.com/gameworks/content/developertools/des.... I'm not sure why the achieved occupancy went up after removing the recursion, but I'd guess it was something like the compiler was able to reduce register usage.