search

numenta / nupic.core-legacy

Implementation of core NuPIC algorithms in C++ (under construction)
http://numenta.org
GNU Affero General Public License v3.0
272 stars 276 forks source link

SP: optimize using minmax_element 25% faster #1326

Closed breznak closed 7 years ago

breznak commented 7 years ago

than using both min() and max() separately

Fixes #1325

breznak commented 7 years ago

@mrcslws Please see here

breznak commented 7 years ago

Why do you say this is 25% faster? Did you run a quick microbenchmark on these two approaches?

Not the whole sp, but this function is. Before it was 2x O(n), now 1x O(3/2n), I think I mentioned it in the commit description.

mrcslws commented 7 years ago

You can't really assign a number to this improvement a priori. It's doing 1 pass instead of 2, which is good, but it's hard to predict how much faster it actually is. Doing 2 passes isn't as slow as you might think, since the CPU prefetches memory during sequential lookups.

(I don't see this in any of your commit descriptions. I checked before saying anything.)

Anyway, this is still a good change.

breznak commented 7 years ago

(I don't see this in any of your commit descriptions. I checked before saying anything.)

My bad, sorry. I thought I've documented that somewhere.

Should I try some micro-benchmark, or is it ok as is? (except the whitespaces..)

mrcslws commented 7 years ago

This is good as-is, just fix the whitespace and I'll merge it.

breznak commented 7 years ago

@mrcslws Sorry for the long delay, I'm back home. Fixed the cleanup and should be ready.

rhyolight commented 7 years ago

👏