golang/go

cmd/compile: use hashing for switch statements

Open

#34,381 建立於 2019年9月18日

在 GitHub 查看
 (22 留言) (11 反應) (0 負責人)Go (19,008 fork)batch import
NeedsInvestigationcompiler/runtimehelp wanted

倉庫指標

Star
 (133,883 star)
PR 合併指標
 (30 天內沒有已合併 PR)

描述

Currently we implement switch statements with binary search. This works well for values that fit into a register, but for strings it might be better to compute a hash function.

Some thoughts:

  1. Even in the simple case of using a full hash function, exactly two passes over the switched value is probably better than O(log N) possible passes over it.

  2. Since we have the expected keys statically, we can use a simple, cheap universal hash (e.g., FNV? djb2?) and keep trying different seeds until we get one without any collisions.

  3. Instead of hashing all of the input bytes, we can hash just enough of them to avoid collisions.

  4. We can try using a minimal (or near minimal) perfect hash to emit a jump table instead of binary search. (This might even be useful for sparse integer values too.)

If someone can help figure out code that can take a []string and figures out an appropriate and cheap hash function to use, I can help wire it into swt.go.

貢獻者指南