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

Memory Bandwidth Napkin Math

forrestthewoods.com

Post reply on HN
Print view View original

41–50 of 56 posts

Re: Memory Bandwidth Napkin Math

#41

Post by hinkley »

staticfloat wrote: post #36
hinkley wrote: post #20

> Let this sink in. Random access into the cache has comparable performance to sequential access from RAM. The drop off from sub-L1 16 KB to L2-sized 256 KB is 2x or less. > I think this has profound implications. I think I agree. Can anyone here posit a theory why this is true? Is this a consequence of all the stream processing work in recent generations of processor? Or something else? Is he saying that pointer cha…

I actually don't think this is that profound; when OP is testing datasets that fit within cache, what's happening is that we are simply not waiting for data to be loaded in from RAM. Let's look at this from a different angle; instead of looking at GB/s, let's think about the CPU as a machine that executes instructions as fast as it can, then look at what can go wrong. I could write a program in assembly that is simpl…

I think I see the problem. OP thinks these sentences say the same thing:

"Random access into the cache has comparable performance to sequential access from RAM."

"Sequential access from RAM has comparable performance to random access into the cache."

Whereas I do not.

Re: Memory Bandwidth Napkin Math

#42

Post by ramblenode »

Sirupsen wrote: post #6

I’ve been fascinated by the 'napkin math' topic recently, but felt a need for a way to routinely practise. It’s an acquired skill once it’s effortless to do the order of magnitude calculations in a meeting, or zipping through possible solutions on a whiteboard (what I imagine Jeff Dean does). Will it be fast enough? How much will it cost? Does the benchmarked performance match the order of magnitude we’d expect? To p…

This sort of order of magnitude estimation is essentially a Fermi question [1]. Anyone interested in these might also check out problems from the high school Science Olympiad event of the same name. Here is a page which links to some past tests: [2]

[1] https://en.wikipedia.org/wiki/Fermi_problem

[2] https://www.sciencenc.com/resources/high-school/fermi-questi...

Re: Memory Bandwidth Napkin Math

#43

Post by rckoepke »

paranoidrobot wrote: post #40
rckoepke wrote: post #34

Earlier quoted context omitted.

Light travels 31% slower in fiber optic cables than it does in a vacuum. (Speed of light is only constant in a vacuum, not in arbitrary media). It can be faster to send the signal into space and bounce it off a satellite, than it would be through a perfect "great circle" surface fiber cable. This is the plan for SpaceX's Starlink constellation. Mark Handley makes an excellent series of YouTube videos explaining some…

Another idea was to use beams of Neutrinos and go point-to-point. It's been demonstrated[1] already. [1] https://physicsworld.com/a/neutrino-based-communication-is-a...

Thank you for sharing this!

Re: Memory Bandwidth Napkin Math

#44

Post by forrestthewoods »

staticfloat wrote: post #36
hinkley wrote: post #20

> Let this sink in. Random access into the cache has comparable performance to sequential access from RAM. The drop off from sub-L1 16 KB to L2-sized 256 KB is 2x or less. > I think this has profound implications. I think I agree. Can anyone here posit a theory why this is true? Is this a consequence of all the stream processing work in recent generations of processor? Or something else? Is he saying that pointer cha…

I actually don't think this is that profound; when OP is testing datasets that fit within cache, what's happening is that we are simply not waiting for data to be loaded in from RAM. Let's look at this from a different angle; instead of looking at GB/s, let's think about the CPU as a machine that executes instructions as fast as it can, then look at what can go wrong. I could write a program in assembly that is simpl…

Hi. OP here.

> The reason I find random access into cache having the same performance as sequential access as not that profound is because it falls out directly from the above scenario

Correct. The behavior can be logically explained. There's no magic involved.

> sequential access into RAM _is_ random access of cache

I actually like your statement even better than my post. Sequential access into RAM _is_ random access of the cache! What a delightfully profound statement.

High-performance computing is your specialty. Of course everything in my post is obvious to you. Elementary even.

If you want to argue the semantics as to whether a logical conclusion constitutes as profound or not. Well, I guess?

Not gonna lie. Your comment kind of comes across as a long-winded humblebrag. "Everything OP said is true. I just think it's obvious." Sorry if that wasn't your intent.

Re: Memory Bandwidth Napkin Math

#45

Post by staticfloat »

forrestthewoods wrote: post #44
staticfloat wrote: post #36

Earlier quoted context omitted.

I actually don't think this is that profound; when OP is testing datasets that fit within cache, what's happening is that we are simply not waiting for data to be loaded in from RAM. Let's look at this from a different angle; instead of looking at GB/s, let's think about the CPU as a machine that executes instructions as fast as it can, then look at what can go wrong. I could write a program in assembly that is simpl…

Hi. OP here. > The reason I find random access into cache having the same performance as sequential access as not that profound is because it falls out directly from the above scenario Correct. The behavior can be logically explained. There's no magic involved. > sequential access into RAM _is_ random access of cache I actually like your statement even better than my post. Sequential access into RAM _is_ random acces…

Sorry, I don't mean for this to come across as playing down your post; you're right that "profoundness" is completely subjective and there's no use in me saying "it's not that profound", for that I apologize.

I enjoyed your post quite a bit, especially how far you went in order to get concrete results that back up the theory. Thank you for going through the effort of writing this post and educating others on your findings. :)

Re: Memory Bandwidth Napkin Math

#46

Post by nkurz »

rckoepke wrote: post #34
wincy wrote: post #29

Earlier quoted context omitted.

Plenty of money to be made if you drill through the earth and run some fiber optics.

Light travels 31% slower in fiber optic cables than it does in a vacuum. (Speed of light is only constant in a vacuum, not in arbitrary media). It can be faster to send the signal into space and bounce it off a satellite, than it would be through a perfect "great circle" surface fiber cable. This is the plan for SpaceX's Starlink constellation. Mark Handley makes an excellent series of YouTube videos explaining some…

> Most fiber optic cable has a melting point of 70C

This seems very unlikely, or at least unlikely to be relevant. The type of fiber optic cable that melts at 70C is PMMA acrylic plastic. To my understanding, this type of fiber not used for long distance communication. Instead, glass fibers with lower losses(which happen to have a much higher melting point) are used: "Because of these properties silica fibers are the material of choice in many optical applications, such as communications (except for very short distances with plastic optical fiber)" (https://en.wikipedia.org/wiki/Optical_fiber). Do you know more than my limited Wikipedia level of understanding, and are confident in saying that long haul cables indeed have a 70C melting point, or should you perhaps include a few more caveats on your napkin math?

Re: Memory Bandwidth Napkin Math

#47

Post by forrestthewoods »

staticfloat wrote: post #45
forrestthewoods wrote: post #44

Earlier quoted context omitted.

Hi. OP here. > The reason I find random access into cache having the same performance as sequential access as not that profound is because it falls out directly from the above scenario Correct. The behavior can be logically explained. There's no magic involved. > sequential access into RAM _is_ random access of cache I actually like your statement even better than my post. Sequential access into RAM _is_ random acces…

Sorry, I don't mean for this to come across as playing down your post; you're right that "profoundness" is completely subjective and there's no use in me saying "it's not that profound", for that I apologize. I enjoyed your post quite a bit, especially how far you went in order to get concrete results that back up the theory. Thank you for going through the effort of writing this post and educating others on your fin…

Thanks, I appreciate that. :)

Re: Memory Bandwidth Napkin Math

#48

Post by nkurz »

staticfloat wrote: post #36
hinkley wrote: post #20

> Let this sink in. Random access into the cache has comparable performance to sequential access from RAM. The drop off from sub-L1 16 KB to L2-sized 256 KB is 2x or less. > I think this has profound implications. I think I agree. Can anyone here posit a theory why this is true? Is this a consequence of all the stream processing work in recent generations of processor? Or something else? Is he saying that pointer cha…

I actually don't think this is that profound; when OP is testing datasets that fit within cache, what's happening is that we are simply not waiting for data to be loaded in from RAM. Let's look at this from a different angle; instead of looking at GB/s, let's think about the CPU as a machine that executes instructions as fast as it can, then look at what can go wrong. I could write a program in assembly that is simpl…

> I could write a program in assembly that is simply 1000000 triplets of (load, add, store) instructions, each reading from a sequentially-increasing memory location. We could think of it like a fully-unrolled addition loop. My CPU, operating at 3GHz, supposedly should complete this program in ~1ms (3 million instructions running at 3 billion instructions per second), but (spoiler alert) it doesn't. Why?

I'll bite. Why doesn't it? And how long do you expect it to take? I'll claim that with a modern processor a simple loop in C probably beats this speed. If you want, we can test afterward to see if our respective theories are true.

The linked article claims that single-threaded reading speed of sequential memory (on his machine) is 11 GB/s. This means a 3 GHz system has a throughput of a little over 3B per cycle (11/3). This means that ever 3 cycles we can pull down 11B, which should be enough to comfortably finish our 1M loads in 1 ms. With 64-bit integers, it's getting a little tighter, but still should be possible.

I guess on a technicality you might be right, but not in a good way. If you were to fully unroll the assembly, you might be able to slow things down enough such that you were running at less than 1 integer per 3 cycles. A simple loop is going to be faster here. Done right (fused SUB/JNZ) the loop overhead should actually be zero. Depending on what you are doing with the store (in place, or to another sequential array?) I'd guess you'd be able to get down to less than 2 cycles per 32-bit int with simple C, and pretty close to 1 cycle per int if you went all out with software prefetching and huge pages.

Re: Memory Bandwidth Napkin Math

#49

Post by myself248 »

ColanR wrote: post #5

It's funny, I had this conversation last week as the coworker, but didn't actually know how to go about calculating this without running tests. It does seem like there are classes of problems which are completely bandwidth-limited. I've heard this is the next area of expansion for hardware tech, but I haven't seen much yet.

I swear I saw something recently where they're putting mediocre little processors right into the RAM packages.

So you send the task to the memory, and it's done right there, where the latency is lowest. And the more RAM you have, the more processors you have working in parallel. When they arrive at an answer, they send it back.

Sort of like content-addressable memory, but even more so.

Re: Memory Bandwidth Napkin Math

#50

Post by fulafel »

Taniwha wrote: post #22
fulafel wrote: post #21

Where does the 5 GB/s napkin estimate for RAM come from? Its lower than the pointer chasing fihure of 7 GB/s.

Unlike just reading a bunch of random data the read instructions can't be pipelined, the instruction that uses the read pointer can't be dispatched to the load-store unit until after it's address has arrived in the CPU (two reads where you know the address can just be queued, and even finished out of order if the second one hits in a closer cache than the first one)

I think you are describing the pessimal pointer chasing case, that should be the smaller figure.
Post reply on HN