Loop FASTER is not to LOOP in Python

หลาย ๆ วันมาละ เรานั่งคุยกับเพื่อนกันว่า ถ้าเราต้องบวกเลขเยอะ ๆ เราจะ Loop เข้าไป ถามว่า เราจะทำเร็วกว่ากันแค่ไหน และที่เราบอกว่า For-Loop กับ While-Loop มันใช้แทนกันได้ มันแทนกันได้จริงแหละ แต่ Performance ละมันเป็นยังไง เราลองมาเล่นกันขำ ๆ ดีกว่า

Problem Statement

โจทย์ที่เราเอามาเล่นกันในวันนี้ ขำ ๆ ง่าย ๆ เลยคือ เราต้องการหาผลรวมของ 1 + 2 + ... + N หรือผลรวมตั้งแต่ 1 ถึง N บวกกันไปเรื่อย ๆ

เช่น เรากำหนด N = 5 ผลลัพธ์ก็จะเป็น 1 + 2 + 3 + 4 + 5 = 15 นั่นเอง ดูเป็นโจทย์ง่าย ๆ เลยสินะ ถ้าเราบวกกันสัก พันนึง เราว่าไม่น่ามีปัญหาอะไรหรอก แต่ในบางปัญหา เราต้องบวกกันระดับล้าน ๆ หรือมากกว่านั้น ทำให้ Performance สำคัญมาก ๆ

Experimental Design

ในการทดลองนี้ เราจะเน้นการจับเวลาในการทำงานของแต่ละวิธีการเป็นหลัก โดยเราจะเลือกใช้ time module ที่อยู่ใน Python เอง

def timer (func: Callable[[int], int], message:str, n:int) -> None :
    start_time = time.time()
    
    func(n)
    
    print(message, 'took', time.time()-start_time, 'sec(s)')

โดยเราจะเขียน Function ขึ้นมาง่าย ๆ ตัวนึงชื่อว่า timer ข้ามพวกเรื่อง Typing ไปนะ เราติดเขียนพวกนี้เข้ามา เวลา Debug อะไรมันจะได้ง่ายขึ้นแค่นั้น ไม่มีผลอะไรเท่าไหร่ ซึ่งจะรับ Function ที่เราต้องการรันเข้ามา พร้อมกับ Message เพื่อให้เราระบุว่ามันเป็นการทดลองอะไร และ สุดท้าย เราเอา N ใส่เข้ามา

ใน Function นี้ เมื่อเข้ามา เราจะให้มันเก็บ Timestamp ไว้ก่อน แล้วเรียก Function สุดท้าย เราอยากรู้เวลาในการทำงาน เราก็เอา Timestamp ปัจจุบัน ลบกับ Timestamp ที่เราเก็บไว้ก่อนหน้าก็ได้ออกมาแล้ว จากนั้นเราก็ Print ออกไปที่หน้าจอให้เราเท่านั้นเอง

เบื้องต้น เพื่อให้เห็นผลกันชัด เราจะตั้ง N ไว้ที่ 10 ล้าน น่าจะพอเห็นผลกันบ้างแล้วละ

For, While Loop

ปัญหานี้ เราใช้ For-Loop และ While-Loop ในการแก้ปัญหาง่ายมาก ๆ

def simple_for_loop (n: int) -> int :
    result = 0
    
    for i in range(n) :
        result += i
    
    return result

สำหรับ For-Loop เป็นอะไรที่เขียนง่ายมาก ๆ ใน For-Loop มันจัดการเรื่องพวก Iteration ให้เราหมดแล้ว เราไม่ต้องเขียน Logic เพื่อบวกเลขเองด้วยซ้ำ เพราะ range() มันจัดการให้เราหมดแล้ว เราก็แค่เอา result ที่เป็น int ไปบวก กับ i ที่วนผ่าน Iterator ได้ตรง ๆ เลย

def simple_while_loop (n: int) -> int :
    result = 0
    counter = 0
    
    while (counter < n) :
        result += counter
        counter += 1
    
    return result

สำหรับ While-Loop เราก็เขียนตามปกติเลย คือ เราเริ่มจากสร้างตัวแปรสำหรับเก็บผลลัพธ์ของเราชื่อ result และ counter เป็นตัวเก็บว่า ตอนนี้เรานับถึงไหนแล้ว ใน Loop เราก็กำหนดเงื่อนไขขึ้นมาว่า counter มันต้องน้อยกว่า n เสมอนะ เพื่อให้มันไม่นับเกิน แล้วใน Loop เราก็ให้มันบวก counter เข้าไปใน result และ บวก counter ขึ้น 1 เพื่อไปรอบต่อไป ธรรมดา ๆ เลย

For Loop took 0.27052903175354004 sec(s)
While Loop took 0.4504220485687256 sec(s)

จากผลการทดลองรัน เราจะเห็นเลยว่า For-Loop รันเร็วกว่า While-Loop เยอะมาก ๆ ดูขำ ๆ เกือบ ๆ 2 เท่าเลยนะ (ไม่ถึงหรอก) หารออกมาได้สัก 1.5 เท่าได้ ถือว่าเยอะมาก ๆ นะ สำหรับความที่เราบอกไปว่า มันใช้อะไรก็ได้ Performance มันห่างกันเยอะมาก ๆ ถ้าเราทำจำนวนเยอะ ๆ

Why ???????

ผลการทดลองทำให้เกิดคำถามว่า Why??? ทำไมฟร๊ะ แค่การเขียน Loop จาก While เป็น For มันก็ทำให้ผลมันต่างกันได้ขนาดนี้เลยเหรอ นั่งคิดอยู่นาน นึกได้ว่า อ่อ CPython นิหว่า

CPython เบื้องหลังของมันถูกเขียนด้วยภาษา C ทำให้ จริง ๆ แล้วเราสามารถที่จะเอาพวก Function ที่เขียนใน C เข้ามาใช้งานในภาษา Python ได้ เหตุผลหนึ่งก็คือเรื่อง Performance เพราะ Python เป็นภาษาแบบ Interpreter ทำให้มันต้องมีพวก Runtime ช่วยแปลภาษาอีกที ณ ขณะที่รัน แต่พวกภาษา C เป็นภาษาที่เรา Compile เป็น Machine Code ล่วงหน้าแล้ว ทำให้ทำงานได้ตรง ๆ เลย นั่นส่งผลเรื่องความเร็วมหาศาล

กลับมาที่ For และ While ของเรากัน ว่า ทำไมมันเป็นแบบนั้นละ นั่นเป็นเพราะใน For Loop เรายัด Iterator เข้าไปตรง ๆ ซึ่งตัว Iterator นี้มันถูกเขียนโดย C ทำให้ Operation ที่ทำงานบน Python จริง ๆ ก็น่าจะมีแค่คำสั่งสำหรับการบวกเลขเข้าไปแค่จุดเดียว กลับกัน ใน While Loop มันมีอะไรมากกว่าที่เราเห็น

while (counter < n) :
        result += counter
        counter += 1

เราขอยก While Loop ด้านบนลงมา เราจะเห็นแค่โอเค มันเป็นแค่ While Loop ปกติ แต่เบื้องหลังของมัน ไม่ได้มีแค่นั้น เพราะ ใน While บรรทัดบนสุด เราจะเห็นว่า เราป้อนเงื่อนไขเข้าไป นั่นก็ทำงานบน Python และ ด้านล่างที่เป็นการบวกเลขทั้งหมด ก็ทำงานบน Python เช่นกัน ทำให้การทำงานของ For Loop ที่พึ่งฝั่งของ C ทำงานเร็วกว่ามาก ๆ

Built-in sum()

ในเมื่ออะไรที่ทำงานบน C เร็วกว่าไปซะหมด และ CPython ที่เราใช้งานกัน ก็เขียนด้วย C อยู่แล้ว แปลว่าพวก Function หลาย ๆ อย่างก็เขียนด้วย C ด้วยเช่นกัน ถ้าเราเข้าไปดูคำสั่งใน Documentation เราน่าจะเคยเห็นคำสั่ง sum() ผ่านตา

def python_sum (n: int) -> int:
    return sum(range(n))

สิ่งที่มันทำคือ มันจะรับ Iterator เข้าไป และ หาผลรวมให้เราเลย ทำให้เราสร้าง Function ง่าย ๆ เลย คือ Return ผลลัพธ์ที่ได้จาก sum() กลับไปตรง ๆ ก็เรียบร้อย

While Loop took 0.4504220485687256 sec(s)
For Loop took 0.27052903175354004 sec(s)
Python Sum took 0.10359907150268555 sec(s)

ผลที่ได้ โอ้ววววว เร็วขึ้นแบบเห็นได้ชัดมาก ๆ เท่าตัวเลยเมื่อเทียบกับ For-Loop และ 4 เท่ากว่า ๆ เมื่อเทียบกับ While-Loop เร็วขนาดนี้ใครละจะทนไหว ฮ่า ๆ

โอเคแหละ มันก็แก้ปัญหาที่เราเล่นกันในบทความนี้ได้จริง ๆ แต่ ถ้าเราเอาว่า Loop เน้น ๆ เลย วิธีนี้ก็ใช้ไม่ได้กับทุกปัญหาที่ใช้ Loop สินะ ดังนั้นก็ผ่านไป เอาเป็นว่า ถ้าเราต้องการจะบวกเลข เราก็ใช้คำสั่ง sum() ได้

Go Faster with Numpy

เอาหละ เราอยากไปให้เร็วขึ้นอีก ไปอี๊กค่าาาา เราจะทำยังไงดี นึกได้ว่า Numpy นี่คือของดีเลย เพราะทั้งหมดของมันเขียนด้วย C และ เลือกใช้วิธีการที่เร็วสุด ๆ อยู่แล้วละ งั้นเราลองเขียนมันด้วย Numpy ล้วน ๆ เลยดีกว่า

def numpy_sum (n : int) -> int :
    return np.sum(np.arange(n))

สำหรับใน Numpy มันก็จะมีคำสั่ง Sum เหมือนกับใน Python เลย มันจะรับ Array-Like Data Structure เข้ามา ทำให้เราสามารถยัดได้ทั้ง Python List และ Numpy Array ได้หมดเลย แล้วมันจะหาผลรวมออกมาให้เรา ซึ่งจาก Python Sum เรายัด Iterator เข้าไป แต่อันนี้ไม่รองรับ

ใน Numpy ก็มีคำสั่งสำหรับการสร้าง Numpy Array ที่เป็นเลขเรียงแบบที่เราต้องการด้วยเช่นกันผ่านคำสั่งที่ชื่อว่า numpy.arange แต่ปัญหาของ Code ชุดนี้คือ มันจะคืนค่ากลับมาเป็น Numpy Array นี่แหละ แปลว่า เราจะต้องเก็บตัวเลขขนาดเท่า N เอาไว้ใน Memory เลยนะ ถ้าตัวเลขเรามีเยอะมาก ๆ เราไม่ชิบหายเลยเหรอ นั่นก็เป็นข้อเสียของวิธีนี้ไปละกันเนอะ

While Loop took 0.4504220485687256 sec(s)
For Loop took 0.27052903175354004 sec(s)
Python Sum took 0.10359907150268555 sec(s)
Numpy took 0.018093109130859375 sec(s)

หลังจากรันออกมา เราจะเห็นได้เลยว่า เวลา มัน ช่าง ต่าง มาก ๆ ขนาดเทียบกับ Python Sum เอง ห่างกัน 10 เท่าได้ และห่างจาก While เกือบ ๆ 25 เท่าไปเลย ต่างกันแบบ ยับ ๆ เลย

Conclusion

หลังจาก 4 วิธีที่เราทดลองกันมา วิธีการที่ช้าที่สุด ก็จะเป็น While Loop และ เร็วที่สุดก็จะเป็นการใช้ Numpy Sum เข้าไป สาเหตุที่เป็นแบบนั้น เป็นเพราะจริง ๆ แล้ว Python เป็นภาษาที่ทำงานได้ค่อนข้างช้า เมื่อเทียบกับภาษา C เพราะลักษณะการทำงานที่แตกต่างกัน ตัว Python จำเป็นที่จะต้องมี Interpreter คั่นเวลาทำงานเสมอ ต่างจาก C ที่มันถูก Compile เป็น Machine Code ตรง ๆ แล้วรันได้เลย ทำให้ Performance ค่อนข้างที่จะต่างกันสักหน่อย

ทำให้ ถ้าเราอยากจะ Optmise Python Script ของเราให้มากที่สุด เราจะต้องพยายามลดการใช้ Python ลงไปให้ได้มากที่สุด เหมือนที่เราทดสอบให้ดูในวันนี้ ดังนั้น Loop ที่เร็วที่สุดคือการไม่ Loop เลยเหมือนชื่อหัวเรื่องของบทความนี้นั่นเอง

รันโปรแกรมเร็วขึ้นด้วย SIMD บน Apple Silicon โคตรเร็ว

จะเป็นอย่างไร ถ้าเราบอกว่า เราสามารถเขียนโปรแกรมของเราให้เร็วขึ้นแบบก้าวกระโดด โดยเราไม่ต้องแบ่ง Core ไม่ต้อง Overclock CPU ของเรา แต่เราใช้ประโยชน์จากความสามารถ CPU ของเราได้ ผ่านการทำ SIMD

ArnondoraArnon Puitrakul

นอกจากนั้น อีกความลับที่เราไม่ได้บอกคือ จริง ๆ แล้วเคสของ Numpy มันจะโกงขึ้นไปอีกขั้น เพราะจริง ๆ แล้ว Numpy มันไม่ได้บวกกันตรง ๆ เหมือนที่เราทำกัน แต่มันใช้ SIMD ในการ Parallelise การทำงานทั้งหมดอีกที เราเคยเขียนเล่าในบทความด้านบนละ

และ ถ้าเราไม่สามารถละ เราจำเป็นต้องใช้ Loop ให้เราจำไว้ว่า การ Loop มีราคาที่ค่อนข้างแพงมาก ๆ พยายามใช้ Expression ที่ Evaluate ผ่าน C มากกว่า Python ก็จะช่วยเพิ่ม Perforance ได้มหาศาลจากเคส While Loop และ For Loop ที่เราแสดงให้เห็นในบทความนี้