3 ms·
Think of the following line of code: blah = blah->next A simple linked-list traversal: 50-nanoseconds on a typical consumer CPU. This could represent a DO
by dragontamer 6y ago
Think of the following line of code:
blah = blah->next
A simple linked-list traversal: 50-nanoseconds on a typical consumer CPU. This could represent a DOM-tree traversal. Or it could be a Javascript object being allocated. Or it could be the text getting added to the end of your rope-data structure. Or it could be a binary-search (finding a new address to check next). Or a malloc() (which traverses a linked-list to find memory). This dereference happens very often.
50-nanoseconds to hit main-RAM, 10-nanoseconds if L3 cache, 4-nanoseconds if in L2 cache, 1-nanosecond if in L1 cache.
This sort of operation is very fast on CPUs, especially if you're cached. Heck, your CPU won't even wait on the result: its going to branch-predict the answer and start executing the next bit of code before it even knows its correct.
----------
That same memory-dereference is 300-nanoseconds from GPU VRAM, and maybe 100-nanoseconds if you're in GPU L1 cache.
If you got a tree, its probably going to be far faster to traverse on a CPU. Where the GPU wins is Raytracing: you can have millions of individual tasks traversing the same tree, in parallel, at larger overall bandwidths than a CPU ever could.
IE: GPUs can perform 1000 binary searches faster than a CPU can perform 1000 binary searches.
But how many applications need 1000 binary searches? Usually, you need 1 binary search, and once you get the result, you need to do something else. (And that result can be branch predicted for even further accelerations to speed).
- jedbrown 6y agoI agree in general, but I'm not confident of this: > GPUs can perform 1000 binary searches faster than a CPU can perform 1000 binary searches. With several vector lanes and ILP on a 64+ core node, the 1000 parallel searches on the CPU may well beat the GPU. It'd have to be tested in any case.
- dragontamer 6y agoHmmmm... 1000 is still a "small" number when we're talking about GPU cores. I probably should have said 100,000 binary searches, or 1,000,000 binary searches. You're right, 1000 is a small enough number where the CPU might still win. If its a large-enough data-structure to hit VRAM (ie: a binary search across a 8GB vector), that's what'd be best for the GPU. Raytracing is millions rays per scene. 4k is 8,294,400 rays at 1-sample per pixel, and each one of those rays has to traverse a BVH tree (similar to a binary tree). Each of those rays MIGHT set off a 2nd or 3rd ray, depending on what its bouncing against. The big BVH tree that organizes all of the video game triangles / objects is shared for all rays. That's the "1000s of binary tree searches in parallel" I was trying to reference. But I guess its closer to 10s of millions.