Test benchmark fibonaci recursive/non recursive

Test benchmark fibonaci recursive/non recursive

Động cơ, lý do

Trước giờ mình vẫn có thắc mắc là đối với cùng 1 bài toán giữa recursive và non recursive thì cái nào sẽ là cách giải quyết hiệu quả hơn. Nhân dịp mình có review code của các member trong team, mọi người có trao đổi về recursive/ non recursive nên mình quyết định tìm hiểu sâu hơn xem suy nghĩ từ đầu của mình đã đúng chưa.

Mình có tìm hiểu các tài liệu thì hầu như mọi người đều có chung nhận xét như sau:

Ưu điểm của đệ quy (recursive): Gọn gàng dễ hiểu, dễ viết code

Nhược điểm: Tốn không gian bộ nhớ, và thời gian xử lý do phải switch context giữa các lần gọi hàm.

Trên đây đều là những nhận xét mang tính lý thuyết. Với góc nhìn của một người hiện tại đang là một kỹ sư từng là học sinh chuyên lý, mình chỉ tin khi có kết quả thí nghiệm là những con số cụ thể.

Và thật may go giúp mình làm điều này khá dễ dàng bằng công cụ test benchmarks

Không nói nhiều nữa, chúng ta cùng vào chủ đề chính.

Test benchmarks với fibonaci recursive

Đầu tiên chúng ta thực hiện cài đặt thuật toán với cách tiếp cận là đệ quy.

Cài đặt test benchmark với đầu vào N = 10

package bench import ( "testing"
) func FibRecursive(n int) int { if n < 2 { return n } return FibRecursive(n-1) + FibRecursive(n-2)
} func BenchmarkFibRecursive10(b *testing.B) { // run the FibRecursive function b.N times for n := 0; n < b.N; n++ { FibRecursive(10) }
}

Thực hiện test benchmark bằng lệnh sau

go test -bench=. -benchmem -memprofile memprofile.out -cpuprofile profile.out

Kết quả

goos: darwin
goarch: amd64
pkg: github.com/hblab-ngocnd/csv-demo/bench
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkFibRecursive10-12 4973802 239.1 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/hblab-ngocnd/csv-demo/bench 1.751s

Nhận xét: Lặp 4973802 lần, mỗi lần mất 239.1 ns tổng 1189236058.2 ns

Máy mình tận i7 lận, giờ mới để ý

Phân tích sâu hơn 1 tý

Phân tích thời gian chạy

Chạy lệnh

go tool pprof profile.out

Type: cpu
Time: Aug 25, 2022 at 3:12pm (+07)
Duration: 1.64s, Total samples = 1.23s (75.02%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top

Dùng lệnh top để lấy những xử lý mất thời gian nhất, sắp xếp theo thứ tự giảm dần

Kết quả

Showing nodes accounting for 1.23s, 100% of 1.23s total flat flat% sum% cum cum% 1.21s 98.37% 98.37% 1.21s 98.37% github.com/hblab-ngocnd/csv-demo/bench.FibRecursive 0.01s 0.81% 99.19% 1.22s 99.19% github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibRecursive10 0.01s 0.81% 100% 0.01s 0.81% runtime/pprof.(*profMap).lookup 0 0% 100% 0.01s 0.81% runtime/pprof.(*profileBuilder).addCPUData 0 0% 100% 0.01s 0.81% runtime/pprof.profileWriter 0 0% 100% 1.22s 99.19% testing.(*B).launch 0 0% 100% 1.22s 99.19% testing.(*B).runN

Mất tổng thời gian chạy cho FibRecursive là 1.21s

Tiếp tục phân tích sâu hơn từng dòng lệnh đối với hàm FibRecursive

(pprof) list FibRecursive

Kết qủa:

Total: 1.23s
ROUTINE ======================== github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibRecursive10 in /Users/S16593/Hblab/Motify/csv-demo/bench/Figo_test.go 10ms 1.22s (flat, cum) 99.19% of Total . . 11: return FibRecursive(n-1) + FibRecursive(n-2) . . 12:} . . 13: . . 14:func BenchmarkFibRecursive10(b *testing.B) { . . 15: // run the FibRecursive function b.N times 10ms 10ms 16: for n := 0; n < b.N; n++ { . 1.21s 17: FibRecursive(10) . . 18: } . . 19:} . . 20: . . 21://func FibNonRecursive(n int) int { . . 22:// if n < 2 {
ROUTINE ======================== github.com/hblab-ngocnd/csv-demo/bench.FibRecursive in /Users/S16593/Hblab/Motify/csv-demo/bench/Figo_test.go 1.21s 1.99s (flat, cum) 161.79% of Total . . 2: . . 3:import ( . . 4: "testing" . . 5:) . . 6: 540ms 540ms 7:func FibRecursive(n int) int { 40ms 40ms 8: if n < 2 { 200ms 200ms 9: return n . . 10: } 430ms 1.21s 11: return FibRecursive(n-1) + FibRecursive(n-2) . . 12:} . . 13: . . 14:func BenchmarkFibRecursive10(b *testing.B) { . . 15: // run the FibRecursive function b.N times . . 16: for n := 0; n < b.N; n++ {

Show kết quả graph bằng png, pdf dùng command:

(pprof) web

Kết thúc phân tích

(pprof) q

Phân tích về cấp phát bộ nhớ

go tool pprof memprofile.out

(pprof) top
Showing nodes accounting for 5140.68kB, 100% of 5140.68kB total
Showing top 10 nodes out of 30 flat flat% sum% cum cum% 1537.69kB 29.91% 29.91% 1537.69kB 29.91% runtime.allocm 1024.41kB 19.93% 49.84% 1024.41kB 19.93% runtime.malg 902.59kB 17.56% 67.40% 1553.21kB 30.21% compress/flate.NewWriter 650.62kB 12.66% 80.05% 650.62kB 12.66% compress/flate.(*compressor).init 512.88kB 9.98% 90.03% 512.88kB 9.98% flag.(*FlagSet).Var 512.50kB 9.97% 100% 512.50kB 9.97% hash/crc32.simpleMakeTable (inline) 0 0% 100% 1553.21kB 30.21% compress/gzip.(*Writer).Write 0 0% 100% 512.88kB 9.98% flag.Var (inline) 0 0% 100% 512.50kB 9.97% hash/crc32.init 0 0% 100% 512.88kB 9.98% main.main

(pprof) web

Test benchmarks với fibonaci non recursive

Cài đặt thuật toán với cách tiếp cận là khử đệ quy.

Cài đặt test benchmark với đầu vào N = 10 (giống bước trên)

package bench import ( "testing"
) func FibNonRecursive(n int) int { if n < 2 { return n } f1 := 0 f2 := 1 for i := 2; i < n; i++ { tmp := f2 f2 = f1 + f2 f1 = tmp } return f2
} func BenchmarkFibNonRecursive10(b *testing.B) { // run the FibNonRecursive function b.N times for n := 0; n < b.N; n++ { FibNonRecursive(10) }
}

Optimized

Do biến tmp được cấp phát trong vòng lặp làm tăng bộ nhớ khá nhiều, gây nên kết luận sai. Sau khi tìm hiểu được nguyên nhân thì mình sửa thành như sau

package bench import ( "testing"
) func FibNonRecursive(n int) int { if n < 2 { return n } f1 := 0 f2 := 1 tmp := 0 for i := 2; i < n; i++ { tmp = f2 f2 = f1 + f2 f1 = tmp } return f2
} func BenchmarkFibNonRecursive10(b *testing.B) { // run the FibNonRecursive function b.N times for n := 0; n < b.N; n++ { FibNonRecursive(10) }
}

Phân tích

Tiếp tục chạy lệnh tương tự

go test -bench=. -benchmem -memprofile memprofile.out -cpuprofile profile.out

Kết quả:

goos: darwin
goarch: amd64
pkg: github.com/hblab-ngocnd/csv-demo/bench
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkFibNonRecursive10-12 223505781 5.321 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/hblab-ngocnd/csv-demo/bench 4.895s

có 223505781 phép toán mỗi phép toán mất 5.321 ns tổng 1189274260.7 ns

Optimized

goos: darwin
goarch: amd64
pkg: github.com/hblab-ngocnd/csv-demo/bench
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkFibNonRecursive10-12 238679884 4.987 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/hblab-ngocnd/csv-demo/bench 1.936s

Chạy lệnh

go tool pprof profile.out

(pprof) top

Type: cpu
Time: Aug 25, 2022 at 3:43pm (+07)
Duration: 1.85s, Total samples = 1.48s (79.92%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top
Showing nodes accounting for 1480ms, 100% of 1480ms total flat flat% sum% cum cum% 980ms 66.22% 66.22% 980ms 66.22% github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursive (inline) 360ms 24.32% 90.54% 1460ms 98.65% github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibNonRecursive10 120ms 8.11% 98.65% 120ms 8.11% runtime.asyncPreempt 20ms 1.35% 100% 20ms 1.35% runtime.nanotime1 0 0% 100% 20ms 1.35% runtime.nanotime 0 0% 100% 20ms 1.35% testing.(*B).StopTimer 0 0% 100% 1480ms 100% testing.(*B).launch 0 0% 100% 1480ms 100% testing.(*B).runN 0 0% 100% 20ms 1.35% time.Since

Mất tổng thời gian chạy cho FibNonRecursive là 980ms

Optimized

Type: cpu
Time: Aug 26, 2022 at 3:20am (+07)
Duration: 1.85s, Total samples = 1.51s (81.53%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top
Showing nodes accounting for 1.51s, 100% of 1.51s total
Showing top 10 nodes out of 20 flat flat% sum% cum cum% 0.90s 59.60% 59.60% 0.90s 59.60% github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursive (inline) 0.55s 36.42% 96.03% 1.47s 97.35% github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibNonRecursive10 0.02s 1.32% 97.35% 0.02s 1.32% runtime.asyncPreempt 0.02s 1.32% 98.68% 0.02s 1.32% runtime.libcCall 0.01s 0.66% 99.34% 0.02s 1.32% runtime.kevent 0.01s 0.66% 100% 0.02s 1.32% runtime.pthread_cond_wait 0 0% 100% 0.03s 1.99% runtime.findrunnable 0 0% 100% 0.02s 1.32% runtime.mPark (inline) 0 0% 100% 0.03s 1.99% runtime.mcall 0 0% 100% 0.02s 1.32% runtime.netpoll

Mất tổng thời gian chạy cho FibNonRecursive là 0.90s

(pprof) list FibNonRecursive

(pprof) list FibNonRecursive
Total: 1.48s
ROUTINE ======================== github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibNonRecursive10 in /Users/S16593/Hblab/Motify/csv-demo/bench/Figo_test.go 360ms 1.46s (flat, cum) 98.65% of Total . . 32: return f2 . . 33:} . . 34: . . 35:func BenchmarkFibNonRecursive10(b *testing.B) { . . 36: // run the FibNonRecursive function b.N times 110ms 160ms 37: for n := 0; n < b.N; n++ { 250ms 1.23s 38: FibNonRecursive(10) . . 39: } . 70ms 40:}
ROUTINE ======================== github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursive in /Users/S16593/Hblab/Motify/csv-demo/bench/Figo_test.go 980ms 980ms (flat, cum) 66.22% of Total . . 22: if n < 2 { . . 23: return n . . 24: } . . 25: f1 := 0 . . 26: f2 := 1 980ms 980ms 27: for i := 2; i < n; i++ { . . 28: tmp := f2 . . 29: f2 = f1 + f2 . . 30: f1 = tmp . . 31: } . . 32: return f2

Optimized

(pprof) list FibNonRecursive
Total: 1.51s
ROUTINE ======================== github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFibNonRecursive10 in /Users/S16593/Hblab/Motify/csv-demo/bench/Figo_test.go 550ms 1.47s (flat, cum) 97.35% of Total . . 33: return f2 . . 34:} . . 35: . . 36:func BenchmarkFibNonRecursive10(b *testing.B) { . . 37: // run the FibNonRecursive function b.N times 190ms 200ms 38: for n := 0; n < b.N; n++ { 360ms 1.26s 39: FibNonRecursive(10) . . 40: } . 10ms 41:}
ROUTINE ======================== github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursive in /Users/S16593/Hblab/Motify/csv-demo/bench/Figo_test.go 900ms 900ms (flat, cum) 59.60% of Total . . 23: return n . . 24: } . . 25: f1 := 0 . . 26: f2 := 1 . . 27: tmp := f2 900ms 900ms 28: for i := 2; i < n; i++ { . . 29: tmp = f2 . . 30: f2 = f1 + f2 . . 31: f1 = tmp . . 32: } . . 33: return f2

(pprof) list web

Optimized

(pprof) q

Phân tích về cấp phát bộ nhớ

go tool pprof memprofile.out

(pprof) top

Type: alloc_space
Time: Aug 25, 2022 at 3:43pm (+07)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top
Showing nodes accounting for 5811.98kB, 100% of 5811.98kB total
Showing top 10 nodes out of 26 flat flat% sum% cum cum% 2050.25kB 35.28% 35.28% 2050.25kB 35.28% runtime.allocm 1184.27kB 20.38% 55.65% 1184.27kB 20.38% runtime/pprof.StartCPUProfile 902.59kB 15.53% 71.18% 1553.21kB 26.72% compress/flate.NewWriter 650.62kB 11.19% 82.38% 650.62kB 11.19% compress/flate.(*compressor).init 512.20kB 8.81% 91.19% 512.20kB 8.81% runtime.malg 512.05kB 8.81% 100% 1696.32kB 29.19% runtime.main 0 0% 100% 1553.21kB 26.72% compress/gzip.(*Writer).Write 0 0% 100% 1184.27kB 20.38% main.main 0 0% 100% 1025.12kB 17.64% runtime.mcall 0 0% 100% 1025.12kB 17.64% runtime.mstart

Optimized

Type: alloc_space
Time: Aug 26, 2022 at 3:20am (+07)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top
Showing nodes accounting for 3746.37kB, 100% of 3746.37kB total
Showing top 10 nodes out of 21 flat flat% sum% cum cum% 1537.69kB 41.04% 41.04% 1537.69kB 41.04% runtime.allocm 1184.27kB 31.61% 72.66% 1184.27kB 31.61% runtime/pprof.StartCPUProfile 1024.41kB 27.34% 100% 1024.41kB 27.34% runtime.malg 0 0% 100% 1184.27kB 31.61% main.main 0 0% 100% 1184.27kB 31.61% runtime.main 0 0% 100% 512.56kB 13.68% runtime.mcall 0 0% 100% 1025.12kB 27.36% runtime.mstart 0 0% 100% 1025.12kB 27.36% runtime.mstart0 0 0% 100% 1025.12kB 27.36% runtime.mstart1 0 0% 100% 1537.69kB 41.04% runtime.newm

(pprof) web

Optimized

So sánh và kết luận với trường hợp N = 10

func BenchmarkFib10(b *testing.B) { // run the FibRecursive function b.N times for n := 0; n < b.N; n++ { FibRecursive(10) } for n := 0; n < b.N; n++ { FibNonRecursive(10) } for n := 0; n < b.N; n++ { FibNonRecursiveOptimized(10) }
}

Type: cpu
Time: Aug 26, 2022 at 3:55am (+07)
Duration: 1.54s, Total samples = 1.22s (79.30%)
Entering interactive mode (type "help" for commands, "o" for options)
(pprof) top
Showing nodes accounting for 1.22s, 100% of 1.22s total
Showing top 10 nodes out of 18 flat flat% sum% cum cum% 1.15s 94.26% 94.26% 1.16s 95.08% github.com/hblab-ngocnd/csv-demo/bench.FibRecursive 0.02s 1.64% 95.90% 1.21s 99.18% github.com/hblab-ngocnd/csv-demo/bench.BenchmarkFib10 0.02s 1.64% 97.54% 0.02s 1.64% github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursiveOptimized (inline) 0.01s 0.82% 98.36% 0.01s 0.82% github.com/hblab-ngocnd/csv-demo/bench.FibNonRecursive (inline) 0.01s 0.82% 99.18% 0.01s 0.82% runtime.(*spanSet).push 0.01s 0.82% 100% 0.01s 0.82% runtime.asyncPreempt 0 0% 100% 0.01s 0.82% runtime.(*mcache).releaseAll 0 0% 100% 0.01s 0.82% runtime.(*mcentral).uncacheSpan 0 0% 100% 0.01s 0.82% runtime.ReadMemStats 0 0% 100% 0.01s 0.82% runtime.ReadMemStats.func1

Lưu ý : Tiêu chí về memory so sánh là chưa hợp lý

Updated

Đúng với nhận xét ban đầu, sau khi optimized Non Recursive có thời gian chạy thấp hơn và tốn ít bộ nhớ hơn so với Recursive

Bạn hãy test thử xem let try !!!

Tài liệu tham khảo

• https://hblab-ngocnd.github.io/blogs/
• https://uet.vnu.edu.vn/~chauttm/dsa2015f/readings/Recursion.html
• https://users.soict.hust.edu.vn/trungtt/uploads/slides/KTLT_Bai03.pdf
• https://medium.com/@felipedutratine/profile-your-benchmark-with-pprof-fb7070ee1a94

Happy codding !!!