Hoare’s Rebuttal and Bubble Sort’s Comeback

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by chubot on Saturday May 30, 2020 @07:24PM (#23365743)

Hm interesting, so is there any analysis / theory that will capture branch mispredictions?

e.g. like big-O for something closer to real machines.

I feel like CPU cycles should already be analyzed separately from memory accesses (although I guess they are usually proportional). But analyzing branch mispredicts seems harder

How does this hold up on ARM and other architectures? (RISC V, etc.)

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by lumberjackstian on Sunday May 31, 2020 @07:35AM (#23368881)

I'm not sure about much analysis and theory that explicitly captures branch prediction, but in last year's cppcon keynote Andrei offered a possible metric [0] where he takes into account the average "distance" between two subsequent array accesses.

It's basically, (C(n) + M(n) + kD(n)) / n

Where M is moves, C is comparisons, k is a some constant, and D is "distance".

[0]: https://youtu.be/FJJTYQYB1JQ?t=2943

[ Parent | on HN ]

Re:Hoare’s Rebuttal and Bubble Sort’s Comeback by matt_d on Sunday May 31, 2020 @02:29PM (#23371502)

See my other reply: https://news.ycombinator.com/item?id=23371399

[ Parent | on HN ]