Tôi đã hash mọi từ hai lần chỉ để đếm nó một lần

Tuần trước, tôi đã thực hiện profiling cho một trình phân tích log. Nó có nhiệm vụ đếm các mã lỗi trong một bản log hàng ngày. Logic cốt lõi chỉ là một thao tác cập nhật dictionary đơn giản.

Hầu hết các lập trình viên sẽ viết như thế này:

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

Đoạn mã này thực hiện hash khóa hai lần. TryGetValue tìm thấy mục nhập bằng cách tính toán mã hash và duyệt qua bucket. Sau đó, indexer lại thực hiện chính xác công việc đó một lần nữa để cập nhật giá trị. Bạn đang lãng phí chu kỳ CPU cho cùng một khóa và cùng một mã hash hai lần cho mỗi token.

Bạn có thể bỏ qua lần truy cập thứ hai. Hãy sử dụng CollectionsMarshal.GetValueRefOrAddDefault.

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

Phương thức này tìm hoặc tạo slot chỉ trong một bước. Nó cung cấp cho bạn một tham chiếu trực tiếp đến vùng lưu trữ. Bạn chỉ thực hiện một lần hash và một lần duyệt bucket. Sau đó, bạn thay đổi giá trị trực tiếp tại chỗ (in place).

Tôi đã thử nghiệm điều này với 5 triệu token.

Kết quả: • TryGetValue + indexer: 160,0 ms • GetValueRefOrAddDefault: 95,0 ms

Phiên bản một lần tra cứu nhanh hơn 1,7 lần.

Quan trọng là, việc cấp phát bộ nhớ vẫn giữ nguyên. Thủ thuật này không tiết kiệm bộ nhớ. Nó chỉ tiết kiệm CPU. Nếu mã của bạn chạy chậm do quá trình thu gom rác (garbage collection), thay đổi này sẽ không có tác dụng gì. Nếu mã của bạn chạy chậm do việc đếm quá nhiều, điều này sẽ giúp ích.

Hãy sử dụng cách này khi vòng lặp của bạn thực hiện nhiều thao tác cập nhật cho các khóa đã tồn tại. Lợi ích sẽ tăng lên khi tỷ lệ cập nhật so với chèn mới tăng lên.

Một cảnh báo: Tham chiếu này trỏ đến vùng lưu trữ nội bộ của dictionary. Nó chỉ có hiệu lực cho đến lần thay đổi cấu trúc tiếp theo. Đừng giữ tham chiếu nếu bạn thêm hoặc xóa các khóa. Hãy lấy tham chiếu (ref), thay đổi giá trị, và tiếp tục công việc khác.

Hãy sử dụng TryGetValue cho hầu hết các tác vụ vì nó dễ đọc hơn. Chỉ sử dụng phiên bản tham chiếu khi vòng lặp dictionary của bạn là một nút thắt cổ chai về hiệu suất (performance bottleneck).

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