Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Bounds Check Eliminationについて調べてみた / 1218-lt

kaznishi
December 18, 2018

Bounds Check Eliminationについて調べてみた / 1218-lt

kaznishi

December 18, 2018
Tweet

More Decks by kaznishi

Other Decks in Programming

Transcript

  1. func f1(nums []int) int { sum := nums[0] sum +=

    nums[1] sum += nums[2] sum += nums[3] sum += nums[4] return sum } func f2(nums []int) int { sum := nums[4] sum += nums[3] sum += nums[2] sum += nums[1] sum += nums[0] return sum } どちらもスライスの要素を足し合わせる処理
  2. $ go build -gcflags="-d=ssa/check_bce/debug=1" main.go # command-line-arguments ./main.go:11:13: Found IsInBounds

    ./main.go:12:13: Found IsInBounds ./main.go:13:13: Found IsInBounds ./main.go:14:13: Found IsInBounds ./main.go:15:13: Found IsInBounds ./main.go:20:13: Found IsInBounds
  3. func f1(nums []int) int { sum := nums[0] # Found

    IsInBounds sum += nums[1] # Found IsInBounds sum += nums[2] # Found IsInBounds sum += nums[3] # Found IsInBounds sum += nums[4] # Found IsInBounds return sum } func f2(nums []int) int { sum := nums[4] # Found IsInBounds sum += nums[3] sum += nums[2] sum += nums[1] sum += nums[0] return sum }
  4. func f1(nums []int) int { sum := nums[0] # Found

    IsInBounds sum += nums[1] # Found IsInBounds sum += nums[2] # Found IsInBounds sum += nums[3] # Found IsInBounds sum += nums[4] # Found IsInBounds return sum } func f2(nums []int) int { sum := nums[4] # Found IsInBounds sum += nums[3] sum += nums[2] sum += nums[1] sum += nums[0] return sum } IsInBounds (IsSliceInBounds) ... Bounds Checkが必要
  5. func f2(nums []int) int { sum := nums[4] # 先に[4]にアクセスすることで

    sum += nums[3] # チェック不要 sum += nums[2] # チェック不要 sum += nums[1] # チェック不要 sum += nums[0] # チェック不要 return sum }
  6. func BenchmarkF1(b *testing.B) { nums := []int{} for i :=

    0; i < 5; i++ { nums = append(nums, i) } for n := 0; n < b.N; n++ { _ = f1(nums) } } func BenchmarkF2(b *testing.B) { nums := []int{} for i := 0; i < 5; i++ { nums = append(nums, i) } for n := 0; n < b.N; n++ { _ = f2(nums) } }
  7. if, lenで確認してから func f3(s []int, index int) { if index

    >= 0 && index < len(s) { _ = s[index] // Bounds Check Elimination!! _ = s[index:len(s)] // Bounds Check Elimination!! } } func f4(s []int) { if len(s) > 2 { _, _, _ = s[0], s[1], s[2]//Bounds Check Elimination!! } }
  8. forループ中でのアクセス func f5(s []int) { for i := range s

    { _ = s[i] // Bounds Check Elimination!! _ = s[i:len(s)] // Bounds Check Elimination!! _ = s[:i+1] // Bounds Check Elimination!! } } func f6(s []int) { for i := 0; i < len(s); i++ { _ = s[i] // Bounds Check Elimination!! _ = s[i:len(s)] // Bounds Check Elimination!! _ = s[:i+1] // Bounds Check Elimination!! } }
  9. ただし、別の配列やスライスへのアクセスはBCEは適 用されない func f7a(s []int) []int { var hoge int

    s2 := make([]int, len(s)) for i := range s { hoge = -s[i] s2[i] = hoge // Bounds Checkが行われる } return s2 } make([]int, len(s)) なので人の頭で考えれば安全なの は分かるが…
  10. ちょっとしたテクニック func f7b(s []int) []int { var hoge int s2

    := make([]int, len(s)) s2 = s2[:len(s)] // これがキモ for i := range s { hoge = -s[i] s2[i] = hoge // Bounds Check Elimination!! } return s2 }
  11. ただしベンチの改善はなかった… func BenchmarkF7A(b *testing.B) { nums := []int{} for i

    := 0; i < 50000; i++ { nums = append(nums, i) } for n := 0; n < b.N; n++ { _ = f7a(nums) } } func BenchmarkF7B(b *testing.B) { nums := []int{} for i := 0; i < 50000; i++ { nums = append(nums, i) } for n := 0; n < b.N; n++ { _ = f7b(nums) } }