Speed up K-means clustering

[philipturner]

This pull request speeds up the single-core CPU performance for un-vectorized K-means. The optimization is generally applicable, even to a vectorized implementation, because it simply elides computations in the critical path.

I am not sure how much speedup this actually provides, and have not tested its correctness. I have not compiled CCV and any respective Swift code calling into K-means. However, you could just test the improvement to _kmeans1d_lookup, check for any regressions, then test _kmeans1d_lookup_compare afterward.

[liuliu]

It doesn't yield meaningful improvement (show slightly regression):

./kmeans1d (before the change)
elapsed: 6895ms
elapsed: 6771ms
elapsed: 6762ms
elapsed: 6771ms
elapsed: 6777ms
elapsed: 6768ms
elapsed: 6787ms
elapsed: 6807ms
elapsed: 6765ms
elapsed: 6736ms

./kmeans1d (after the change)
elapsed: 7123ms
elapsed: 6942ms
elapsed: 6914ms
elapsed: 7132ms
elapsed: 6961ms
elapsed: 6934ms
elapsed: 6950ms
elapsed: 6850ms
elapsed: 6892ms
elapsed: 6863ms

Changed used for above test: https://github.com/liuliu/ccv/commit/2210ba756bdd7077e1527d2e324fa76b46667111

liu@sz77:~/workspace/ccv/lib$ clang --version
clang version 16.0.0
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /usr/local/bin

Compile flags:

clang ccv_numeric.c -o ccv_numeric.o -c -O3 -ffast-math -Wall -I"." -I/usr/local/cuda/include  -fopenmp -fblocks -msse2 -D HAVE_CBLAS -D HAVE_LIBPNG -D HAVE_LIBJPEG -D HAVE_FFTW3 -D HAVE_PTHREAD -D HAVE_LIBLINEAR -D HAVE_TESSERACT -D HAVE_AVCODEC -D HAVE_AVFORMAT -D HAVE_AVUTIL -D HAVE_SWSCALE -D USE_OPENMP -D USE_DISPATCH -D HAVE_SSE2 -D HAVE_GSL -D HAVE_CUDA -D HAVE_CUDNN -D HAVE_NCCL -D USE_SYSTEM_CUB -I/usr/local/include

Link flags:

clang -o kmeans1d kmeans1d.o -L"../lib" -lccv -L/usr/local/lib -lm -lcblas -latlas -lrt -lpng -ljpeg -lfftw3 -lfftw3f -lpthread -lpthread -llinear -ltesseract -lavcodec -lavformat -lavutil -lswscale -fopenmp -ldispatch -lBlocksRuntime -lgsl -lgslcblas -lcuda -lcudart -lcublas -lcurand -lstdc++ -L/usr/local/cuda/lib64 -lcudnn -lnccl

Machine info:

liu@sz77:~/workspace/ccv/lib$ uname -a
Linux sz77 5.19.0-45-generic #46~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Wed Jun 7 15:06:04 UTC 20 x86_64 x86_64 x86_64 GNU/Linux
liu@sz77:~/workspace/ccv/lib$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         43 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  64
  On-line CPU(s) list:   0-63
Vendor ID:               AuthenticAMD
  Model name:            AMD Ryzen Threadripper 3970X 32-Core Processor
    CPU family:          23
    Model:               49
    Thread(s) per core:  2
    Core(s) per socket:  32
    Socket(s):           1
    Stepping:            0
    Frequency boost:     enabled
    CPU max MHz:         3700.0000
    CPU min MHz:         2200.0000
    BogoMIPS:            7400.61
    Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdtscp
                         lm constant_tsc rep_good nopl nonstop_tsc cpuid extd_apicid aperfmperf rapl pni pclmulqdq monitor ssse3 fma cx16 sse4_1 sse4_2 movbe popcnt aes
                          xsave avx f16c rdrand lahf_lm cmp_legacy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs skinit wdt tce topoext perfctr_co
                         re perfctr_nb bpext perfctr_llc mwaitx cpb cat_l3 cdp_l3 hw_pstate ssbd mba ibpb stibp vmmcall fsgsbase bmi1 avx2 smep bmi2 cqm rdt_a rdseed ad
                         x smap clflushopt clwb sha_ni xsaveopt xsavec xgetbv1 xsaves cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local clzero irperf xsaveerptr rdpru w
                         bnoinvd amd_ppin arat npt lbrv svm_lock nrip_save tsc_scale vmcb_clean flushbyasid decodeassists pausefilter pfthreshold avic v_vmsave_vmload v
                         gif v_spec_ctrl umip rdpid overflow_recov succor smca sev sev_es
Virtualization features:
  Virtualization:        AMD-V
Caches (sum of all):
  L1d:                   1 MiB (32 instances)
  L1i:                   1 MiB (32 instances)
  L2:                    16 MiB (32 instances)
  L3:                    128 MiB (8 instances)
NUMA:
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-63
Vulnerabilities:
  Itlb multihit:         Not affected
  L1tf:                  Not affected
  Mds:                   Not affected
  Meltdown:              Not affected
  Mmio stale data:       Not affected
  Retbleed:              Mitigation; untrained return thunk; SMT enabled with STIBP protection
  Spec store bypass:     Mitigation; Speculative Store Bypass disabled via prctl
  Spectre v1:            Mitigation; usercopy/swapgs barriers and __user pointer sanitization
  Spectre v2:            Mitigation; Retpolines, IBPB conditional, STIBP always-on, RSB filling, PBRSB-eIBRS Not affected
  Srbds:                 Not affected
  Tsx async abort:       Not affected