undefined

points

by asveikau3 hours ago |

comments

by spider-mario2 hours ago|

[-]

Or even, stuff it into several parallel vectors (structure of arrays instead of array of structures).

by stackghost2 hours ago|

prev|

[-]

I too am in the "premature optimization bad" camp.

Beyond the low-hanging fruit like ensuring you aren't creating O(n^2) complexity by accident, I think C++ is fast enough/has mature-enough compilers that by the time you're worrying about cache hits materially affecting performance, you're probably also sufficiently staffed and capitalized to pay people to A/B test that performance.

by asveikau1 hours ago|

parent|

[-]

I don't know if this advice is strictly advocating to avoid premature optimization. Many problems are modeled intuitively with lots of tiny allocations and pointer heavy structures, and this advice is saying to avoid that.

I think it's more like: prioritize cache locality over big O compexity.

by srean2 hours ago|

parent|

prev|

[-]

And how would that staff have learned it ?

by stackghost59 minutes ago|

parent|

[-]

I don’t understand the question. Are you implying someone cannot know how to do something in a particular codebase unless they’ve already done it on that same codebase?

by jeffbee1 hours ago|

parent|

prev|

[-]

I don't really agree because it's so hard to reform a full application that's been written without regard to performance, after it's been written. You really need to pay attention from the beginning.

by bluGill2 hours ago|

prev|

[-]

While this advice isn't wrong, it is misleading. In my benchmarks std::map beats vector after 9 elements. Less than that and linear search is better but branch prediction and cache loading is very good.

Run your own benchmarks on your own data of course. Also map is not considered the best key value store.

by mandarax82 hours ago|

parent|

[-]

Because in your benchmark all std::map nodes were allocated in succession, most likely being placed in adjacent memory locations...

This likely won't be true in a real application with a non-trivial allocation pattern.

by bluGill1 hours ago|

parent|

[-]

That might or might not be true in the real world. Often in my applications I'm creating at startup and then referencing later.

Still a custom map that allocated a bunch of nodes would be a useful optimization.

by einpoklum1 hours ago|

parent|

prev|

[-]

Actually it really depends, because allocators can also be kind of smart (and you don't have to use the default allocator).

And then, on the other hand - I really doubt GP's map beats a vector, with all of those pointers bins and stuff, in a non-contrived benchmark with 10 elements.

Finally - it's not either-or: There are better hash maps whose memory is sequentially allocated and/or are otherwise cache-aware. And there are data structures geared towards parallel execution on multiple threads; and towards SIMD; etc. etc.