Reconstruction of Clément Jean's binary search code from https://clement-jean.github.io/simd_binary_search_tree/

README

Seems to work, but I'm not an expert with this stuff, so YMMV.

main.s

#include "textflag.h"

//func binarySearch(arr []int, n int) bool
TEXT ·binarySearch(SB),NOSPLIT,$0-33
#define data R0
#define dataLen R1
#define toFind R2
#define curr R3
#define tmp R4
#define child_idx R5
#define nb_subtree R6
#define level R7
#define searchKey V0
#define mask V1
#define idx V2
#define one V3
#define equalMask V4

  // initialize registers
  MOVD arr+0(FP), data
  MOVD arr_len+8(FP), dataLen
  MOVD n+24(FP), toFind
  MOVD $0, curr
  MOVD $1, level
  MOVD $0, nb_subtree
  VDUP level, one.S4

  // if array len is 0 return false
  CMP $0, dataLen
  BEQ not_found

  // if array len > 1 start the work
  // otherwise check if the first element is equal
  //  to the one we are looking for
  CMP $1, dataLen
  BGT load
  MOVD (data), tmp
  CMP tmp, toFind
  BEQ found
  B not_found

load:
  VDUP toFind, searchKey.S4

check:
  CMP dataLen, curr
  BGE not_found

loop:
  MOVD $4, R19
  MUL R19, curr
  ADD curr, data, R19
  VLD1 (R19), [mask.S4]

  VCMEQ mask.S4, searchKey.S4, equalMask.S4
  WORD $0x6eb0a893 //umaxv.4s s19, v4
  FMOVS F19, R19
  CMP $4294967295, R19
  BEQ found
  WORD $0x6ea13401 //cmhi.4s v1, v0, v1
  MOVD $0, R19
  VMOV R19, mask.S[3]
  VAND mask.B16, one.B16, idx.B16
  WORD $0x6eb0384f //uaddlv.4s d15, v2
  FMOVD F15, child_idx
  MOVD child_idx, tmp
  ADD $1, tmp
  MOVD $3, R19
  MUL R19, tmp
  MOVD tmp, curr
  MUL R19, nb_subtree, R19
  ADD R19, curr

  //nb_subtree = level << 2
  LSL $2, level, nb_subtree

  //level++
  ADD $1, level
  B check
  
not_found:
  MOVD $0, R19 // false
  MOVD R19, ret+32(FP)
  RET

found:
  MOVD $1, R19 // true
  MOVD R19, ret+32(FP)
  RET