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

What Every Programmer Should Know About Memory (2007) [pdf]

akkadia.org

Post reply on HN
Print view View original

41–50 of 101 posts

Re: What Every Programmer Should Know About Memory (2007) [pdf]

#41

Post by bogomipz »

dragontamer wrote: post #18
mbauman wrote: post #17

Earlier quoted context omitted.

Indeed, there are a limited number of hard-hitting topics that are definitely must-haves: * Rough latency timings * Caching * Prefetching * Sequential vs. random access * N-dimensional layouts (row/column major and arbitrarily strided) * Design of cache-oblivious algorithms * SIMD-able access patterns * False sharing * Instruction cache & code size * Branch prediction and speculative execution I'd be curious to hear…

Good list. I'd add "Virtual Memory" to that list. In particular, the TLB cache, memory pages (4kB, 2MB "Large Pages", 2GB "Huge Pages). Although x86 specific, I'd also add x86-64 has 48-bit physical pointers: the top 16-bits are basically ignored by the current virtual memory system. I dunno if the whole Page Directory / Directory Tables / etc. etc. needs to be fully explained, but programmers should have an overall…

>"Although x86 specific, I'd also add x86-64 has 48-bit physical pointers: the top 16-bits are basically ignored by the current virtual memory system."

Could you elaborate on this? Which pointers exactly?

Re: What Every Programmer Should Know About Memory (2007) [pdf]

#42

Post by ontologiae »

saberience wrote: post #8

Is this title and content supposed to be ironic? I quickly perused the article and I think this link should be renamed "What 99.9% of programmers don't need to know about memory." I've managed to go from Associate to Principal without knowing 99% of what's covered in this document, and I'm struggling to understand why the average Java, C#, Python, Rust, programmer would need to know about transistor configurations or…

Every programmers should know something about memory, because software are becoming bloat [1] [2] because of a new generation of programmers who doesn't optimize their code.

So, of course, you had a wonderful career, but it doesn't prove that you write efficient code

[1] http://www.rntz.net/post/against-software-development.html [2] http://tonsky.me/blog/disenchantment/

Re: What Every Programmer Should Know About Memory (2007) [pdf]

#43

Post by okl »

v_lisivka wrote: post #11
busfahrer wrote: post #7

Ulrich Drepper used to be the glibc maintainer, IIRC

memcpy != memmove , $#$@#@ https://sourceware.org/bugzilla/show_bug.cgi?id=12518

https://sourceware.org/bugzilla/show_bug.cgi?id=3266

https://sourceware.org/bugzilla/show_bug.cgi?id=12701

https://sourceware.org/bugzilla/show_bug.cgi?id=386

https://sourceware.org/bugzilla/show_bug.cgi?id=10134

Re: What Every Programmer Should Know About Memory (2007) [pdf]

#44

Post by dragontamer »

bogomipz wrote: post #40
dragontamer wrote: post #21

Earlier quoted context omitted.

> I'm not saying it's not interesting, but it's not going to change how I write my for-loops and if statements or make calls to BigTable, etc. You might be surprised at how much changing your for loops can be when accessing matrix data. for(int i=0; i Test that out, and you'll see a major performance improvement. ----------- If someone is writing high performance code, the #1 goal is to be able to read your profiler'…

Can you elaborate why the second is faster in the general case? Is this an issue of row major vs column major orientation? Also does your example also hold in the absence of SIMD? Thanks.

There's at least 2 reasons (+1 non-reason) why it is slow.

1. L1 cache lines are 64-bytes long. By fetching column-wise, you are wasting the bandwidth between L1 and main-memory. L1 cache will always fetch 64-bytes. By moving "with" the cache, you allow the L1 --> Main Memory data-transfers to be far more efficient.

2. Virtual Memory is translated by the TLB before it returns the actual value. Moving within a 4kB page is more efficient than moving across pages.

The non-reason:

* Hardware prefetcher probably works, even on column-oriented data.

All of these reasons hold even if the SIMD-optimizer fails. If the SIMD-optimizer is actually working, you'll more efficiently load/store to L1 cache. But this is likely a memory-bound problem and optimizing the core isn't as important.

Re: What Every Programmer Should Know About Memory (2007) [pdf]

#45

Post by saberience »

gdy wrote: post #36
saberience wrote: post #8

Is this title and content supposed to be ironic? I quickly perused the article and I think this link should be renamed "What 99.9% of programmers don't need to know about memory." I've managed to go from Associate to Principal without knowing 99% of what's covered in this document, and I'm struggling to understand why the average Java, C#, Python, Rust, programmer would need to know about transistor configurations or…

You should get acquainted with 'What Every Computer Scientist Should Know About Floating-Point Arithmetic' after which similar articles are named. I'd bet you would suggest to rename it too.

Computer Science is a different discipline to Software Engineering.

I would argue that sure, if you want to be a PhD, academic, researcher etc, in Computer Science, then reading said article might be useful.

For engineers working at companies whose goal is to get product to market faster, coding ruby on rails, javascript, making web apps, websites, it's far more useful knowing your web frameworks well and being able to iterate fast, than knowing the intimate mathematical details of floating point arithmetic.

Computer Science != engineering. It's like saying knowing physics is the same thing as knowing how to build a building.

Re: What Every Programmer Should Know About Memory (2007) [pdf]

#46

Post by wuxb »

saberience wrote: post #8

Is this title and content supposed to be ironic? I quickly perused the article and I think this link should be renamed "What 99.9% of programmers don't need to know about memory." I've managed to go from Associate to Principal without knowing 99% of what's covered in this document, and I'm struggling to understand why the average Java, C#, Python, Rust, programmer would need to know about transistor configurations or…

I write user-level C/C++ programs and think that this book is 100% relevant. Yes the details about the transistors can be skipped for first-time readers. But eventually these explain what programmers should expect from the machine, and why.

Re: What Every Programmer Should Know About Memory (2007) [pdf]

#47

Post by [deleted] »

gdy wrote: post #36
saberience wrote: post #8

Is this title and content supposed to be ironic? I quickly perused the article and I think this link should be renamed "What 99.9% of programmers don't need to know about memory." I've managed to go from Associate to Principal without knowing 99% of what's covered in this document, and I'm struggling to understand why the average Java, C#, Python, Rust, programmer would need to know about transistor configurations or…

You should get acquainted with 'What Every Computer Scientist Should Know About Floating-Point Arithmetic' after which similar articles are named. I'd bet you would suggest to rename it too.

[deleted]

Re: What Every Programmer Should Know About Memory (2007) [pdf]

#48

Post by dragontamer »

jawnv6 wrote: post #29
dragontamer wrote: post #18

Earlier quoted context omitted.

Good list. I'd add "Virtual Memory" to that list. In particular, the TLB cache, memory pages (4kB, 2MB "Large Pages", 2GB "Huge Pages). Although x86 specific, I'd also add x86-64 has 48-bit physical pointers: the top 16-bits are basically ignored by the current virtual memory system. I dunno if the whole Page Directory / Directory Tables / etc. etc. needs to be fully explained, but programmers should have an overall…

how is MESI "an abstraction"? why is it the only model proffered instead of MESIF/MOESI? and "the top 16-bits are basically ignored" is a funny way to spell "general protection exception on linear memory reference in non-canonical space" but sure, guess we're just handwaving here

> how is MESI "an abstraction"? why is it the only model proffered instead of MESIF/MOESI?

Because no CPU actually implements MESI. All CPUs implement more complicated stuff, like MESIF / MOESI. Instead of going into MESIF (which only Intel CPUs implement) or MOESI (only older AMD CPUs implement), lets just stick with the textbook MESI.

Which is "wrong", but its "correct enough" to explain the concept. That's what I mean by an abstraction, no CPU today actually does MESI, its simply a concept to introduce to solidify the student's understanding of cache coherency. Its close enough to reality without getting into the tricky CPU-specific details of the real world.

> guess we're just handwaving

I mean, you have to set those bits back to 0 before using them as a pointer.

But the system will literally never use those top 16-bits for anything. So some highly optimized code stores data in those top 16-bits and then zeros them out before using. IIRC, Lisp machines and various interpreters.

Re: What Every Programmer Should Know About Memory (2007) [pdf]

#49

Post by dragontamer »

bogomipz wrote: post #41
dragontamer wrote: post #18

Earlier quoted context omitted.

Good list. I'd add "Virtual Memory" to that list. In particular, the TLB cache, memory pages (4kB, 2MB "Large Pages", 2GB "Huge Pages). Although x86 specific, I'd also add x86-64 has 48-bit physical pointers: the top 16-bits are basically ignored by the current virtual memory system. I dunno if the whole Page Directory / Directory Tables / etc. etc. needs to be fully explained, but programmers should have an overall…

>"Although x86 specific, I'd also add x86-64 has 48-bit physical pointers: the top 16-bits are basically ignored by the current virtual memory system." Could you elaborate on this? Which pointers exactly?

All pointers in user-space are 48-bits. All 48-bit pointers are translated by the page-directory virtual memory system into a real physical location.

There's an extension to use 55-bits or 56-bits... I forget exactly. But I don't think its actually been implemented yet on any CPU yet.

EDIT: It was Intel's 57-bit memory: https://en.wikipedia.org/wiki/Intel_5-level_paging . Yeah, I knew it was a weird number. But I guessed wrong earlier.

Re: What Every Programmer Should Know About Memory (2007) [pdf]

#50

Post by dragontamer »

3JPLW wrote: post #34
dragontamer wrote: post #18

Earlier quoted context omitted.

Good list. I'd add "Virtual Memory" to that list. In particular, the TLB cache, memory pages (4kB, 2MB "Large Pages", 2GB "Huge Pages). Although x86 specific, I'd also add x86-64 has 48-bit physical pointers: the top 16-bits are basically ignored by the current virtual memory system. I dunno if the whole Page Directory / Directory Tables / etc. etc. needs to be fully explained, but programmers should have an overall…

I don't think you need to explain the intricacies of the MESI protocol — just explaining the fact that caches need to be consistent is quite sufficient. Perhaps throw in why they must be consistent. It then becomes clear that the cores need to communicate (somehow) to maintain this consistency if they're touching data within the same cache line.

MESI isn't really that complicated. Cache-lines are either Exclusive owned, Shared, Invalid, or Modified. CPU Cores communicate to each other which lines are owned or unowned, and that's how the caches stay coherent. If a CPU Core wants to change a cache-line owned by another core, they have to wait until the line is closed (set to "Invalid" state) by the other core.

I think its easier to explain cache-coherence through MESI, rather than to abstractly just say "Caches are coherent". At least personally, I didn't understand cache coherence until I sat down and really tried to understand MESI.

I guess other people learn differently than I do, but I always view cache-coherence through the MESI lens.

Post reply on HN