Skip to content

Instantly share code, notes, and snippets.

@MRobertEvers
Last active January 8, 2019 13:35
Show Gist options
  • Save MRobertEvers/9af9d6516eda70c2ae86bf9ababd88c2 to your computer and use it in GitHub Desktop.
Save MRobertEvers/9af9d6516eda70c2ae86bf9ababd88c2 to your computer and use it in GitHub Desktop.
Computer Systems

Caching Effects In Arrays

https://stackoverflow.com/questions/9936132/why-does-the-order-of-the-loops-affect-performance-when-iterating-over-a-2d-arra

https://stackoverflow.com/questions/11413855/why-is-transposing-a-matrix-of-512x512-much-slower-than-transposing-a-matrix-of?noredirect=1&lq=1

Branch Prediction

https://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array

Data alignment

Data alignment refers to how data is stored in memory at addresses that are a multiple of some number. E.g. Ints are stored at addresses that are 4 byte aligned and longs are stored at 8 byte aligned addresses.

Natural alignment seems to mean when an object is aligned to an address that is a multiple of its size. (There appears to be some discrepancy in definition). One definition here https://www.kernel.org/doc/Documentation/unaligned-memory-access.txt.

Alignment is used to improve memory accesses on a particular hardware. AFAIK, alignment will always be a power of 2 (simply because that is how processors are designed).

Data alignment importance and what it looks like on the hardware. https://www.ibm.com/developerworks/library/pa-dalign/index.html

https://stackoverflow.com/questions/381244/purpose-of-memory-alignment

Other things about data alignment. https://www.quora.com/What-is-natural-alignment-Why-should-a-generic-pointer-be-aligned

https://stackoverflow.com/questions/17136547/memory-alignment-in-an-array-of-structures

Generally speaking, C and C++ compilers handle alignment automatically. When it comes to composite structures like structs, then an array of a struct will be aligned to the MOST ALIGNED element of the struct (perhaps a long or int).

I think the 'MOST ALIGNED' consequence comes from 2 things. 1, this guarantees that that most aligned member is aligned properly, and 2, that alignment requirements are strict multiples of two (1, 2, 4, 8...). Because of 2, if data is aligned at a higher alignment, then the lower requirement members' alignment requirements are also satisfied.

Additionally, most processor architectures only require natural alignment on SOME sizes, e.g. ints (4 bytes) and longs (8 bytes). Thus, compilers can get away with the 'MOST ALIGNED' strategy because the architecture doesn't requres a 256 byte struct to be aligned at 256.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment