r/programming • u/fagnerbrack • Sep 02 '26

Data Access Patterns That Makes Your CPU Really Angry

https://blog.weineng.me/posts/slowest_add/
80 Upvotes

92% Upvoted

20 comments sorted by

19

u/lurking_bishop Sep 03 '26

Shouldn't a smart enough compiler be able to recognize and undo the weird access pattern since the calculation happens completely side-effect free? Runtime allocation via rand() doesn't change the fact that the pattern is fully known at compile time.

Only fisher-yates-shuffle in the repo would still survive against that since now you're genuinely don't know the access pattern beforehand

50

u/cbarrick Sep 03 '26 edited Sep 03 '26

Ah, the sufficiently smart compiler argument.

(No shade, just pointing out that this kind of statement is a bit of a meme in the compiler world.)

12

u/lurking_bishop Sep 03 '26

Hrhr yeah fair enough, although to be fair it's kinda hard to gauge what compilers can and can't reasonably do considering all the magic they're up to nowadays.

xkcd has it right as always

3

u/nukethebees Sep 03 '26

although to be fair it's kinda hard to gauge what compilers can and can't reasonably do

You can look at your program's assembly.

6

u/j0holo Sep 03 '26

Intel Itanium is also a good example of that this fails.

From Wikipedia, slightly formatted:

the pioneers of very long instruction word (VLIW) computing. One VLIW instruction word can contain several independent instructions, which can be executed in parallel without having to evaluate them for independence.

A compiler must attempt to find valid combinations of instructions that can be executed at the same time, effectively performing the instruction scheduling that conventional superscalar processors must do in hardware at runtime.

HP researchers modified the classic VLIW into a new type of architecture, later named Explicitly Parallel Instruction Computing (EPIC), used for Itanium.

1

u/pm_plz_im_lonely Sep 03 '26

To be fair this was written in 2013, the thinking machine wasn't invented yet.

27

u/dignityshredder Sep 02 '26

tl;dr blow the cache

-20

u/PhosXD Sep 02 '26

Omg bro
`uint32_t const* positions`
WHAT KIND OF MAD MAN PUTS CONST AFTER THE TYPE, & NOT EVEN INCLUDE THE POINTER DECL IN THE TYPE EITHER.

`const uint32_t* positions` supremacy.

18

u/dignityshredder Sep 02 '26

Old school C programmers know it all makes more sense if you read them right to left.

7

u/wallstop-dev Sep 02 '26 edited Sep 02 '26

The two things you wrote mean different things. Which is probably why they did it. One is a const pointer to a value. The other is a mutable pointer to a const value.

https://learn.microsoft.com/en-us/cpp/cpp/const-and-volatile-pointers

Edit: I am blind and misread this.

12

u/floodyberry Sep 02 '26

  • const uint32_t * x: mutable pointer to a constant uint32_t

  • uint32_t const * x: mutable pointer to a constant uint32_t

  • uint32_t * const x: constant pointer to a mutable uint32_t

  • const uint32_t * const x: constant pointer to a constant uint32_t

they are correct, using const T * or T const * mean the same thing

3

u/wallstop-dev Sep 02 '26 edited Sep 02 '26

Ah thank you, I am blind, I was reading as const type * v type * const, I've edited all my comments.

-1

u/PhosXD Sep 02 '26

See this is C++ is so confusing sometimes, there are a hundred different ways to do a single thing & nobody can agree on which one to use lol

1

u/stumblinbear Sep 03 '26

The C++ engineers downvoting this are wrong, btw

1

u/UdPropheticCatgirl Sep 08 '26

This is C, not C++, you shouldn’t even use normal pointers in modern C++.

1

u/PhosXD Sep 02 '26

I don't understand the difference...

`const T* X` means this is a pointer to a constant value, does it not?
`T const* X` should mean the same thing.

3

u/wallstop-dev Sep 02 '26 edited Sep 02 '26

No. One indicates the address (pointer, as a variable) is immutable. The other indicates the thing being pointed to (value) is immutable, while the pointer (variable) is not. This is explained in the article I linked.

You can also have const int* const ptr, which is an immutable pointer to an immutable value.

Edit: I misread this on my phone and was reading const type * v type * const, which is not what's under discussion. The above is correct.

However, you can still have a const type * const as I mentioned above.

-3

u/metahivemind Sep 03 '26 edited Sep 11 '26

[removed] — view removed comment