baseline.go raw

   1  /*
   2   * SPDX-FileCopyrightText: © Hypermode Inc. <hello@hypermode.com>
   3   * SPDX-License-Identifier: Apache-2.0
   4   */
   5  
   6  package simd
   7  
   8  import (
   9  	"fmt"
  10  	"runtime"
  11  	"sort"
  12  	"sync"
  13  )
  14  
  15  // Search finds the key using the naive way
  16  func Naive(xs []uint64, k uint64) int16 {
  17  	var i int
  18  	for i = 0; i < len(xs); i += 2 {
  19  		x := xs[i]
  20  		if x >= k {
  21  			return int16(i / 2)
  22  		}
  23  	}
  24  	return int16(i / 2)
  25  }
  26  
  27  func Clever(xs []uint64, k uint64) int16 {
  28  	if len(xs) < 8 {
  29  		return Naive(xs, k)
  30  	}
  31  	var twos, pk [4]uint64
  32  	pk[0] = k
  33  	pk[1] = k
  34  	pk[2] = k
  35  	pk[3] = k
  36  	for i := 0; i < len(xs); i += 8 {
  37  		twos[0] = xs[i]
  38  		twos[1] = xs[i+2]
  39  		twos[2] = xs[i+4]
  40  		twos[3] = xs[i+6]
  41  		if twos[0] >= pk[0] {
  42  			return int16(i / 2)
  43  		}
  44  		if twos[1] >= pk[1] {
  45  			return int16((i + 2) / 2)
  46  		}
  47  		if twos[2] >= pk[2] {
  48  			return int16((i + 4) / 2)
  49  		}
  50  		if twos[3] >= pk[3] {
  51  			return int16((i + 6) / 2)
  52  		}
  53  
  54  	}
  55  	return int16(len(xs) / 2)
  56  }
  57  
  58  func Parallel(xs []uint64, k uint64) int16 {
  59  	cpus := runtime.NumCPU()
  60  	if cpus%2 != 0 {
  61  		panic(fmt.Sprintf("odd number of CPUs %v", cpus))
  62  	}
  63  	sz := len(xs)/cpus + 1
  64  	var wg sync.WaitGroup
  65  	retChan := make(chan int16, cpus)
  66  	for i := 0; i < len(xs); i += sz {
  67  		end := i + sz
  68  		if end >= len(xs) {
  69  			end = len(xs)
  70  		}
  71  		chunk := xs[i:end]
  72  		wg.Add(1)
  73  		go func(hd int16, xs []uint64, k uint64, wg *sync.WaitGroup, ch chan int16) {
  74  			for i := 0; i < len(xs); i += 2 {
  75  				if xs[i] >= k {
  76  					ch <- (int16(i) + hd) / 2
  77  					break
  78  				}
  79  			}
  80  			wg.Done()
  81  		}(int16(i), chunk, k, &wg, retChan)
  82  	}
  83  	wg.Wait()
  84  	close(retChan)
  85  	var min int16 = (1 << 15) - 1
  86  	for i := range retChan {
  87  		if i < min {
  88  			min = i
  89  		}
  90  	}
  91  	if min == (1<<15)-1 {
  92  		return int16(len(xs) / 2)
  93  	}
  94  	return min
  95  }
  96  
  97  func Binary(keys []uint64, key uint64) int16 {
  98  	return int16(sort.Search(len(keys), func(i int) bool {
  99  		if i*2 >= len(keys) {
 100  			return true
 101  		}
 102  		return keys[i*2] >= key
 103  	}))
 104  }
 105  
 106  //nolint:unused
 107  func cmp2_native(twos, pk [2]uint64) int16 {
 108  	if twos[0] == pk[0] {
 109  		return 0
 110  	}
 111  	if twos[1] == pk[1] {
 112  		return 1
 113  	}
 114  	return 2
 115  }
 116  
 117  //nolint:unused
 118  func cmp4_native(fours, pk [4]uint64) int16 {
 119  	for i := range fours {
 120  		if fours[i] >= pk[i] {
 121  			return int16(i)
 122  		}
 123  	}
 124  	return 4
 125  }
 126  
 127  //nolint:unused
 128  func cmp8_native(a [8]uint64, pk [4]uint64) int16 {
 129  	for i := range a {
 130  		if a[i] >= pk[0] {
 131  			return int16(i)
 132  		}
 133  	}
 134  	return 8
 135  }
 136