search

dgryski / go-perfbook

Thoughts on Go performance optimization
10.68k stars 596 forks source link

Worry about O(1) #42

Closed kokes closed 5 years ago

kokes commented 5 years ago

When outlining big-O notation, you describe O(1) as

O(1): a field access, array or map lookup

Advice: don't worry about it

But similarly to O(n), O(1) algorithms can differ in performance quite wildly. You note that O(n) has a constant factor, but I would note this about O(1) as well, because once we have O(1) in a hot loop, we're essentially solving an O(n) problem.

What I'm getting at is that map lookup involving hashing a value is an order of magnitude (or more) slower than an array lookup, which involves just a bit of pointer chasing. I did some very basic benchmarking (n=1) a while ago, but the gist of it should hold, more or less (I didn't really worry about caches, branch predictions etc.).

dgryski commented 5 years ago

Good point. I'll add a sentence or two.

dgryski commented 5 years ago

How about 

  Advice: don't worry about it (but keep in mind the constant factor)

?

kokes commented 5 years ago

Yup, sounds good.

And if you want, you can elaborate on the differences between maps and arrays/slices in terms of performance. And to stress that in case one knows a lot about their key domain and if it's numerical and constrained (and small enough), they might benefit from an array/slice.