Benchmark ใน Go

ลองให้ทีมเล่น Code Kata จากโจทย์ที่อะกิเอามาให้ เป็นเรื่องให้ลองจับคู่วงเล็บดูว่า input ที่เป็น string ที่ใส่มามันจับคู่ถูกต้องหรือไม่ นั่นคือ ต้องจับคู่วงเล็บเปิด กับวงเล็บปิดเสมอ (ถ้าปิดมาก่อนเปิดไม่นับ เช่น “}{” หรือถ้ามีวงเล็บไขว้กัน เช่น “({)}” แบบนี้ก็ถือว่าไม่ถูก

ทีม A

ทีม A ใช้วิธี stack มาช่วย คือ ลอง push วงเล็บเปิดเข้า stack ทีละตัว ถ้าอ่านไปเจอวงเล็บปิด ให้ pop ค่าจาก stack ดูว่าเป็นวงเล็บเปิดที่คู่กันหรือไม่ ถ้าไม่ก็แสดงว่าไม่ถูกต้อง ทำแบบนี้ไปเรื่อย ๆ จนหมด ถ้ามีค่าเหลือใน stack หรือ stack หมดก่อนตอนที่เจอวงเล็บปิด ก็แสดงว่าไม่ถูกต้อง

พอลองเอามาแปลงเป็นโค้ด golang ก็จะได้ประมาณนี้

func Match(input string) bool {
    stack := []rune{}
    bracketPair := map[rune]rune{
        ']': '[',
        '}': '{',
        ')': '(',
    }

    for _, c := range input {
        if c == '[' || c == '{' || c == '(' {
            stack = append(stack, c)
        } else {
            if c == ']' || c == '}' || c == ')' {
                if len(stack) > 0 {
                    top := stack[len(stack)-1]
                    stack = stack[:len(stack)-1]
                    if bracketPair[c] != top {
                        return false
                    }
                } else {
                    return false
                }
            }
        }
    }

    return (len(stack) == 0)
}

ทีม B

ใช้วิธีวนลูปลบคู่วงเล็บทีละชนิดออกจาก input จนกว่าจะไม่มีคู่วงเล็บเหลือใน input ถ้าจบลูปแล้ว input ยังไม่หมด แสดงว่าไม่ถูกต้อง ลองแปลงเป็นโค้ด golang แล้วจะได้ประมาณนี้

func Match2(input string) bool {
    for (strings.Index(input, "{}") >= 0) || (strings.Index(input, "[]") >= 0) || (strings.Index(input, "()") >= 0) {
        input = strings.Replace(input, "[]", "", -1)
        input = strings.Replace(input, "{}", "", -1)
        input = strings.Replace(input, "()", "", -1)
    }

    return len(input) == 0
}

ชุดทดสอบ

ทั้ง 2 วิธีใช้ชุดทดสอบเดียวกัน คือ

package bracket

import (
    "testing"

    "github.com/stretchr/testify/assert"
)

var MethodUnderTest = Match

func TestEmpty(t *testing.T) {
    result := MethodUnderTest("")
    assert.True(t, result)
}

func TestCorrect(t *testing.T) {
    open := []string{"[]", "()", "{}", "[][]", "[](){}", "[({})][{}()]"}
    for _, o := range open {
        result := MethodUnderTest(o)
        assert.True(t, result)
    }
}

func TestOpenOnly(t *testing.T) {
    open := []string{"[", "(", "{"}
    for _, o := range open {
        result := MethodUnderTest(o)
        assert.False(t, result)
    }
}

func TestCloseOnly(t *testing.T) {
    close := []string{"]", ")", "}"}
    for _, o := range close {
        result := MethodUnderTest(o)
        assert.False(t, result)
    }
}

func TestCloseThenOpen(t *testing.T) {
    closeThenOpen := []string{"][", ")(", "}{"}
    for _, o := range closeThenOpen {
        result := MethodUnderTest(o)
        assert.False(t, result)
    }
}

func TestMixed(t *testing.T) {
    mixed := []string{"[]]", "{{(}})", "{[}(])"}
    for _, o := range mixed {
        result := MethodUnderTest(o)
        assert.False(t, result)
    }
}

เปรียบเทียบ

ผลการ Test ทั้ง 2 วิธีก็สามารถทำงานได้อย่างถูกต้อง ทีนี้เลยอยากลองวัดประสิทธิภาพของทั้ง 2 วิธีทั้งด้าน Time complexity และ Space complexity เลยเอา benchmark มาลองจับดู

วิธีการเขียน benchmark ใน go ก็ไม่ได้ยากอะไร แค่ตั้งชื่อ func ขึ้นต้นด้วยคำว่า Benchmark (อย่าลืม B ตัวใหญ่นะ) และมี parameter 1 ตัว คือ b มีชนิดเป็น pointer ชี้ไปที่ testing.B

package bracket

import "testing"

func BenchmarkMatch(b *testing.B) {
    for i := 0; i < b.N; i++ {
        Match("[][]{}{}()(){{[()]}}")
    }
}

func BenchmarkMatch2(b *testing.B) {
    for i := 0; i < b.N; i++ {
        Match2("[][]{}{}()(){{[()]}}")
    }
}

สังเกตจะเห็นได้ว่า การ test benchmark จะเป็นการวนลูปซ้ำ ๆ เรียกคำสั่งเดิม ๆ จำนวน b.N รอบ โดยค่า b.N จะถูกปรับเรื่อย ๆ ให้มากพอที่จะทำให้ค่าที่ได้มีความน่าเชื่อถือ

ตอนสั่งรันก็ง่าย ๆ

go test -bench=.

ผลลัพธ์ที่ได้จะออกมาแบบนี้

ผลลัพธ์จะแบ่งเป็น 3 คอลัมน์ คือ ชื่อ จำนวนรอบที่รันได้ และเวลาที่ใช้ต่อ 1 รอบ

ดังนั้นจากผลลัพธ์ข้างบน จะได้ว่า

ชุดทดสอบ BenchmarkMatch รันไปทั้งหมด 10,000,000 รอบ ใช้เวลาไป 214 ns (นาโนวินาที) ต่อรอบ
ชุดทดสอบ BenchmarkMatch2 รันไปทั้งหมด 2,000,000 รอบ ใช้เวลาไป 620 ns (นาโนวินาที) ต่อรอบ

ทีนี้หากเราอยากเห็น space complexity ของทั้ง 2 ชุดทดสอบ ให้ใช้ option -benchmem ต่อท้ายไป

go test -bench=. -benchmem

ผลลัพธ์ที่ได้จะคล้าย ๆ เดิม แต่จะมีเพิ่มมาอีก 2 คอลัมน์คือ จำนวน Byte ที่ใช้ต่อรอบ กับจำนวนการเกิด memory allocation ต่อรอบ

จากผลลัพธ์ที่ได้ จะเห็นได้ว่า

ชุดทดสอบ BenchmarkMatch ใช้ memory ไป 24 Bytes ต่อรอบ และเกิด memory allocation 2 ครั้งต่อรอบ
ชุดทดสอบ BenchmarkMatch2 ใช้ memory ไป 88 Bytes ต่อรอบ และเกิด memory allocation 10 ครั้งต่อรอบ

ดังนั้น

จะเห็นได้ว่า วิธีที่ทีม A ใช้ มีประสิทธิภาพที่สูงกว่าวิธีที่ทีม B ใช้อยู่พอสมควร

เลือกตัวไหนดี

ถ้าผลลัพธ์มันต่างกันมากอย่างมีนัยสำคัญทางที่ควรเลือกคงหนีไม่พ้นวิธีที่มีประสิทธิภาพสูงกว่า แต่ท้ายที่สุด เรื่องของการที่โค้ดเราอ่านง่าย ยังคงเป็นเรื่องสำคัญสำหรับโค้ดที่เราจะต้องมีการดูแลในระยะยาว

Leave a Reply

Your email address will not be published. Required fields are marked *