3 ms·

Kinda missing the point of C++ by using a linked-list. If you're going to spend the time to implement an algorithm in C++ at least take the time to make it cac

Kinda missing the point of C++ by using a linked-list. If you're going to spend the time to implement an algorithm in C++ at least take the time to make it cache aware. Otherwise it's not really surprising when the performance is the same when you're doing the exact same thing. Would be curious to see what the performance looks like with a tightly packed scene and static dispatch on a discrete number of primitives instead of using virtual functions.

mden 11y ago
I was curious about whether using a vector over list would have any effect even though the size is so small and the answer seems no (I guess as it could be expected). It seems like the listed OCaml program has a default level of 9 where as the C++ one uses 6? Times using original listing (minus print stmts): $ time ./ray-cpp real 0m3.369s user 0m3.347s sys 0m0.010s $ time ./ray-ml real 0m4.710s user 0m4.703s sys 0m0.003s Time after changing the 9 in the ocaml program to a six: $ time ./ray-ml real 0m4.032s user 0m4.026s sys 0m0.003s Seems like C++ has a good edge. Above was ran on a 64 bit machine.
- vvanders 11y ago
  List is just one part that makes the C++ impl sub-optimal. All the scenes are allocated on the heap so you're actually bouncing around memory twice(once for the next link list entry, second for the actual heap allocation). Lastly the virtual call again has the chance to cache miss(although probably only once seeing as we've just got a few impls). In a small example like this there's a good chance that most of the heap allocations are close together but put this approach into production and you can very easily see fragmentation start driving up your cache misses. (FWIW I'd also store radius*radius on creation, use a BSP/kd-tree and all sorts of other tricks that really help in these types of computations).
  - altern 11y ago
    I did a qucik and dirty test with levels = 14. # program time change ./ray-ml: 21.46 # Original ocaml ./ray-cpp: 17.63 # Original c++ ./ray-cpp-no-dtor: 13.86 # Removed all cleanup, ocaml doesn't do it ./ray-cpp-2: 8.90 # Changed list to vector ./ray-cpp-3: 7.89 # Removed virtual functions ./ray-cpp-4: 5.64 # Preallocated large array for all Groups
    - vvanders 11y ago
      Solid stuff, glad to see someone testing my assumptions :). If there's one thing I could teach new CS-grads it's how much your memory access patterns(and cache) really-effing-matter. Everything else is almost noise in comparison.
      - sanderjd 11y ago
        I'm pretty curious about this: have memory access patterns and cache awareness become more of a big deal in the past decade or so, or has it only recently reached my awareness? I studied CS in the early 2000s and while I was aware of various trade-offs between contiguous and linked data structures, it's only in the last few years that the importance of cache (and non-"system" languages' widespread flouting of its importance) has really bubbled up in my consciousness. It's certainly likely that I just didn't take the right kinds of classes, or that I did but just missed or failed to really internalize this, but I'm curious if something else is going on. Has the bottleneck increasingly become memory rather than CPU? Have we more thoroughly exhausted other areas of optimization? I was thinking about this while watching a talk[0] given by someone from Google about data structures in the STL, which decried that the standardized specification for `std::unordered_map` more or less forces an implementation to use buckets instead of the more cache-friendly technique of probing. I'm sure that the people who standardized it were very competent, which makes me think that, at least at the time, buckets were thought to be the better implementation. [0]: https://www.youtube.com/watch?v=fHNmRkzxHWs https://www.youtube.com/watch?v=fHNmRkzxHWs Edit: Added video link.
        blt 11y ago

mden 11y ago

I was curious about whether using a vector over list would have any effect even though the size is so small and the answer seems no (I guess as it could be expected). It seems like the listed OCaml program has a default level of 9 where as the C++ one uses 6? Times using original listing (minus print stmts): $ time ./ray-cpp real 0m3.369s user 0m3.347s sys 0m0.010s $ time ./ray-ml real 0m4.710s user 0m4.703s sys 0m0.003s Time after changing the 9 in the ocaml program to a six: $ time ./ray-ml real 0m4.032s user 0m4.026s sys 0m0.003s Seems like C++ has a good edge. Above was ran on a 64 bit machine.

vvanders 11y ago
List is just one part that makes the C++ impl sub-optimal. All the scenes are allocated on the heap so you're actually bouncing around memory twice(once for the next link list entry, second for the actual heap allocation). Lastly the virtual call again has the chance to cache miss(although probably only once seeing as we've just got a few impls). In a small example like this there's a good chance that most of the heap allocations are close together but put this approach into production and you can very easily see fragmentation start driving up your cache misses. (FWIW I'd also store radius*radius on creation, use a BSP/kd-tree and all sorts of other tricks that really help in these types of computations).
- altern 11y ago
  I did a qucik and dirty test with levels = 14. # program time change ./ray-ml: 21.46 # Original ocaml ./ray-cpp: 17.63 # Original c++ ./ray-cpp-no-dtor: 13.86 # Removed all cleanup, ocaml doesn't do it ./ray-cpp-2: 8.90 # Changed list to vector ./ray-cpp-3: 7.89 # Removed virtual functions ./ray-cpp-4: 5.64 # Preallocated large array for all Groups
  - vvanders 11y ago
    Solid stuff, glad to see someone testing my assumptions :). If there's one thing I could teach new CS-grads it's how much your memory access patterns(and cache) really-effing-matter. Everything else is almost noise in comparison.
    - sanderjd 11y ago
      I'm pretty curious about this: have memory access patterns and cache awareness become more of a big deal in the past decade or so, or has it only recently reached my awareness? I studied CS in the early 2000s and while I was aware of various trade-offs between contiguous and linked data structures, it's only in the last few years that the importance of cache (and non-"system" languages' widespread flouting of its importance) has really bubbled up in my consciousness. It's certainly likely that I just didn't take the right kinds of classes, or that I did but just missed or failed to really internalize this, but I'm curious if something else is going on. Has the bottleneck increasingly become memory rather than CPU? Have we more thoroughly exhausted other areas of optimization? I was thinking about this while watching a talk[0] given by someone from Google about data structures in the STL, which decried that the standardized specification for `std::unordered_map` more or less forces an implementation to use buckets instead of the more cache-friendly technique of probing. I'm sure that the people who standardized it were very competent, which makes me think that, at least at the time, buckets were thought to be the better implementation. [0]: https://www.youtube.com/watch?v=fHNmRkzxHWs https://www.youtube.com/watch?v=fHNmRkzxHWs Edit: Added video link.
      - blt 11y ago