ผมทำ Hash ทุกคำถึงสองครั้ง เพียงเพื่อจะนับมันแค่ครั้งเดียว

เมื่อสัปดาห์ที่แล้ว ผมได้ทำ profiling ตัว log parser ตัวหนึ่ง ซึ่งทำหน้าที่นับ error code ใน log ประจำวัน โดยตรรกะหลักคือการอัปเดตค่าใน dictionary แบบง่ายๆ

นักพัฒนาส่วนใหญ่มักจะเขียนแบบนี้:

if (counts.TryGetValue(code, out int c))
    counts[code] = c + 1;
else
    counts[code] = 1;

โค้ดนี้ทำการ hash คีย์ถึงสองครั้ง TryGetValue จะค้นหา entry โดยการคำนวณ hash และไล่ดูใน bucket จากนั้น indexer ก็จะทำงานแบบเดิมซ้ำอีกครั้งเพื่ออัปเดตค่า คุณจึงเสียรอบการทำงานของ CPU (CPU cycles) ไปกับการทำ hash เดิมซ้ำสองครั้งต่อหนึ่ง token

คุณสามารถข้ามขั้นตอนที่สองนี้ไปได้ โดยการใช้ CollectionsMarshal.GetValueRefOrAddDefault

ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, code, out _);
slot++;

เมธอดนี้จะค้นหาหรือสร้าง slot ขึ้นมาในขั้นตอนเดียว โดยจะให้ reference ไปยังที่เก็บข้อมูลโดยตรง คุณจะทำการ hash และไล่ดู bucket เพียงครั้งเดียว จากนั้นจึงทำการแก้ไขค่า (mutate) ณ ตำแหน่งนั้นได้เลย

ผมได้ทดสอบเรื่องนี้ด้วย token จำนวน 5 ล้านตัว

ผลลัพธ์: • TryGetValue + indexer: 160.0 ms • GetValueRefOrAddDefault: 95.0 ms

เวอร์ชันที่ค้นหาเพียงครั้งเดียว (one-lookup) เร็วกว่าถึง 1.7 เท่า

สิ่งที่สำคัญคือ การจองหน่วยความจำ (memory allocations) ยังคงเท่าเดิม เทคนิคนี้ไม่ได้ช่วยประหยัดหน่วยความจำ แต่มันช่วยประหยัด CPU หากโค้ดของคุณช้าเพราะ garbage collection การเปลี่ยนแปลงนี้จะไม่มีผลอะไรเลย แต่ถ้าโค้ดของคุณช้าเพราะต้องทำการนับจำนวนมหาศาล วิธีนี้จะช่วยได้

ควรใช้เทคนิคนี้เมื่อลูปของคุณมีการอัปเดตคีย์ที่มีอยู่เดิมบ่อยครั้ง ประสิทธิภาพจะยิ่งเพิ่มขึ้นตามสัดส่วนของการอัปเดตต่อการเพิ่มข้อมูลใหม่ (updates to inserts)

คำเตือน: Reference นี้ชี้ไปยังที่เก็บข้อมูลภายในของ dictionary ซึ่งจะยังคงใช้งานได้จนกว่าจะมีการเปลี่ยนแปลงโครงสร้าง (structural change) ครั้งถัดไป อย่าถือ reference นี้ค้างไว้หากคุณมีการเพิ่มหรือลบคีย์ ให้ดึง ref มา เปลี่ยนค่า แล้วก็ไปต่อได้เลย

ควรใช้ TryGetValue สำหรับงานส่วนใหญ่เพราะอ่านง่ายกว่า ส่วนเวอร์ชัน ref ให้ใช้เฉพาะเมื่อลูป dictionary ของคุณกลายเป็นคอขวด (performance bottleneck) ของประสิทธิภาพเท่านั้น

Source: https://dev.to/ssukhpinder/i-hashed-every-word-twice-to-count-it-once-1mg9