Commits

Russ Cox  committed d604b3c Draft

exp/html/atom: faster Lookup with smaller tables

Use perfect cuckoo hash, to avoid binary search.
Define Atom bits as offset+len in long string instead
of enumeration, to avoid string headers.

Before: 1909 string bytes + 6060 tables = 7969 total data
After: 1406 string bytes + 2048 tables = 3454 total data

benchmark old ns/op new ns/op delta
BenchmarkLookup 83878 64681 -22.89%

R=nigeltao, r
CC=golang-dev
http://codereview.appspot.com/6262051

  • Participants
  • Parent commits 31e3667

Comments (0)

Files changed (5)

File src/pkg/exp/html/atom/atom.go

 // whether atom.H1 < atom.H2 may also change. The codes are not guaranteed to
 // be dense. The only guarantees are that e.g. looking up "div" will yield
 // atom.Div, calling atom.Div.String will return "div", and atom.Div != 0.
+//
+// TODO(rsc): When this package moves out of exp we need to freeze atom values
+// across releases.
 package atom
 
-// The hash function must be the same as the one used in gen.go
-func hash(s []byte) (h uint32) {
-	for i := 0; i < len(s); i++ {
-		h = h<<5 ^ h>>27 ^ uint32(s[i])
+// Atom is an integer code for a string. The zero value maps to "".
+type Atom uint32
+
+// String returns the atom's name.
+func (a Atom) String() string {
+	start := uint32(a >> 8)
+	n := uint32(a & 0xff)
+	if start+n > uint32(len(atomText)) {
+		return ""
+	}
+	return atomText[start : start+n]
+}
+
+func (a Atom) string() string {
+	return atomText[a>>8 : a>>8+a&0xff]
+}
+
+// fnv computes the FNV hash with an arbitrary starting value h.
+func fnv(h uint32, s []byte) uint32 {
+	for i := range s {
+		h ^= uint32(s[i])
+		h *= 16777619
 	}
 	return h
 }
 
-// Atom is an integer code for a string. The zero value maps to "".
-type Atom int
-
-// String returns the atom's name.
-func (a Atom) String() string {
-	if 0 <= a && a < Atom(len(table)) {
-		return table[a]
+func match(s string, t []byte) bool {
+	for i, c := range t {
+		if s[i] != c {
+			return false
+		}
 	}
-	return ""
+	return true
 }
 
 // Lookup returns the atom whose name is s. It returns zero if there is no
 // such atom.
 func Lookup(s []byte) Atom {
-	if len(s) == 0 || len(s) > maxLen {
+	if len(s) == 0 || len(s) > maxAtomLen {
 		return 0
 	}
-	if len(s) == 1 {
-		x := s[0]
-		if x < 'a' || x > 'z' {
-			return 0
-		}
-		return oneByteAtoms[x-'a']
+	h := fnv(hash0, s)
+	if a := table[h&uint32(len(table)-1)]; int(a&0xff) == len(s) && match(a.string(), s) {
+		return a
 	}
-	hs := hash(s)
-	// Binary search for hs. Unlike sort.Search, this returns early on an exact match.
-	// A loop invariant is that len(table[i]) == len(s) for all i in [lo, hi).
-	lo := Atom(loHi[len(s)])
-	hi := Atom(loHi[len(s)+1])
-	for lo < hi {
-		mid := (lo + hi) / 2
-		if ht := hashes[mid]; hs == ht {
-			// The gen.go program ensures that each atom's name has a distinct hash.
-			// However, arbitrary strings may collide with the atom's name. We have
-			// to check that string(s) == table[mid].
-			t := table[mid]
-			for i, si := range s {
-				if si != t[i] {
-					return 0
-				}
-			}
-			return mid
-		} else if hs > ht {
-			lo = mid + 1
-		} else {
-			hi = mid
-		}
+	if a := table[(h>>16)&uint32(len(table)-1)]; int(a&0xff) == len(s) && match(a.string(), s) {
+		return a
 	}
 	return 0
 }
 
 // String returns a string whose contents are equal to s. In that sense, it is
-// equivalent to string(s), but may be more efficient.
+// equivalent to string(s) but may be more efficient.
 func String(s []byte) string {
 	if a := Lookup(s); a != 0 {
 		return a.String()

File src/pkg/exp/html/atom/atom_test.go

 	"testing"
 )
 
+func TestKnown(t *testing.T) {
+	for _, s := range testAtomList {
+		if atom := Lookup([]byte(s)); atom.String() != s {
+			t.Errorf("Lookup(%q) = %#x (%q)", s, uint32(atom), atom.String())
+		}
+	}
+}
+
 func TestHits(t *testing.T) {
-	for i, s := range table {
-		got := Lookup([]byte(s))
-		if got != Atom(i) {
-			t.Errorf("Lookup(%q): got %d, want %d", s, got, i)
+	for _, a := range table {
+		if a == 0 {
+			continue
+		}
+		got := Lookup([]byte(a.String()))
+		if got != a {
+			t.Errorf("Lookup(%q) = %#x, want %#x", a.String(), uint32(got), uint32(a))
 		}
 	}
 }
 }
 
 func BenchmarkLookup(b *testing.B) {
-	sortedTable := make([]string, len(table))
-	copy(sortedTable, table[:])
+	sortedTable := make([]string, 0, len(table))
+	for _, a := range table {
+		if a != 0 {
+			sortedTable = append(sortedTable, a.String())
+		}
+	}
 	sort.Strings(sortedTable)
 
 	x := make([][]byte, 1000)

File src/pkg/exp/html/atom/gen.go

 
 package main
 
-// This program generates table.go
+// This program generates table.go and table_test.go.
 // Invoke as
 //
 //	go run gen.go |gofmt >table.go
+//	go run gen.go -test |gofmt >table_test.go
 
 import (
+	"flag"
 	"fmt"
+	"math/rand"
 	"os"
 	"sort"
+	"strings"
 )
 
-// The hash function must be the same as the one used in atom.go
-func hash(s string) (h uint32) {
-	for i := 0; i < len(s); i++ {
-		h = h<<5 ^ h>>27 ^ uint32(s[i])
-	}
-	return h
-}
-
-// lhash returns a uint64 whose high 32 bits are len(s) and whose low 32 bits
-// are hash(s).
-func lhash(s string) uint64 {
-	return uint64(len(s))<<32 | uint64(hash(s))
-}
-
-type byLhash []string
-
-func (b byLhash) Len() int           { return len(b) }
-func (b byLhash) Less(i, j int) bool { return lhash(b[i]) < lhash(b[j]) }
-func (b byLhash) Swap(i, j int)      { b[i], b[j] = b[j], b[i] }
-
 // identifier converts s to a Go exported identifier.
 // It converts "div" to "Div" and "accept-charset" to "AcceptCharset".
 func identifier(s string) string {
 	return string(b)
 }
 
+var test = flag.Bool("test", false, "generate table_test.go")
+
 func main() {
-	// Construct a list of atoms, sorted by their lhash.
-	m0 := map[string]bool{
-		"": true,
+	flag.Parse()
+
+	var all []string
+	all = append(all, elements...)
+	all = append(all, attributes...)
+	all = append(all, eventHandlers...)
+	all = append(all, extra...)
+	sort.Strings(all)
+
+	if *test {
+		fmt.Printf("// generated by go run gen.go -test; DO NOT EDIT\n\n")
+		fmt.Printf("package atom\n\n")
+		fmt.Printf("var testAtomList = []string{\n")
+		for _, s := range all {
+			fmt.Printf("\t%q,\n", s)
+		}
+		fmt.Printf("}\n")
+		return
 	}
-	for _, list := range [][]string{elements, attributes, eventHandlers, extra} {
-		for _, s := range list {
-			m0[s] = true
+
+	// uniq - lists have dups
+	// compute max len too
+	maxLen := 0
+	w := 0
+	for _, s := range all {
+		if w == 0 || all[w-1] != s {
+			if maxLen < len(s) {
+				maxLen = len(s)
+			}
+			all[w] = s
+			w++
 		}
 	}
-	atoms := make([]string, 0, len(m0))
-	for s := range m0 {
-		atoms = append(atoms, s)
+	all = all[:w]
+
+	// Find hash that minimizes table size.
+	var best *table
+	for i := 0; i < 1000000; i++ {
+		if best != nil && 1<<(best.k-1) < len(all) {
+			break
+		}
+		h := rand.Uint32()
+		for k := uint(0); k <= 16; k++ {
+			if best != nil && k >= best.k {
+				break
+			}
+			var t table
+			if t.init(h, k, all) {
+				best = &t
+				break
+			}
+		}
 	}
-	sort.Sort(byLhash(atoms))
+	if best == nil {
+		fmt.Fprintf(os.Stderr, "failed to construct string table\n")
+		os.Exit(1)
+	}
 
-	// Calculate the magic constants to output as table.go.
-	byInt := []string{}
-	byStr := map[string]int{}
-	ident := []string{}
-	lhashes := []uint64{}
-	maxLen := 0
-	for i, s := range atoms {
-		byInt = append(byInt, s)
-		byStr[s] = i
-		ident = append(ident, identifier(s))
-		lhashes = append(lhashes, lhash(s))
-		if maxLen < len(s) {
-			maxLen = len(s)
+	// Lay out strings, using overlaps when possible.
+	layout := append([]string{}, all...)
+
+	// Remove strings that are substrings of other strings
+	for changed := true; changed; {
+		changed = false
+		for i, s := range layout {
+			if s == "" {
+				continue
+			}
+			for j, t := range layout {
+				if i != j && t != "" && strings.Contains(s, t) {
+					changed = true
+					layout[j] = ""
+				}
+			}
 		}
 	}
 
-	// Check for hash collisions.
-	m1 := map[uint64]int{}
-	for i, h := range lhashes {
-		h &= 1<<32 - 1
-		if j, ok := m1[h]; ok {
-			fmt.Fprintf(os.Stderr, "hash collision at 0x%08x: %q, %q\n", h, byInt[i], byInt[j])
-			os.Exit(1)
+	// Join strings where one suffix matches another prefix.
+	for {
+		// Find best i, j, k such that layout[i][len-k:] == layout[j][:k],
+		// maximizing overlap length k.
+		besti := -1
+		bestj := -1
+		bestk := 0
+		for i, s := range layout {
+			if s == "" {
+				continue
+			}
+			for j, t := range layout {
+				if i == j {
+					continue
+				}
+				for k := bestk + 1; k <= len(s) && k <= len(t); k++ {
+					if s[len(s)-k:] == t[:k] {
+						besti = i
+						bestj = j
+						bestk = k
+					}
+				}
+			}
 		}
-		m1[h] = i
+		if bestk > 0 {
+			layout[besti] += layout[bestj][bestk:]
+			layout[bestj] = ""
+			continue
+		}
+		break
+	}
+
+	text := strings.Join(layout, "")
+
+	atom := map[string]uint32{}
+	for _, s := range all {
+		off := strings.Index(text, s)
+		if off < 0 {
+			panic("lost string " + s)
+		}
+		atom[s] = uint32(off<<8 | len(s))
 	}
 
 	// Generate the Go code.
+	fmt.Printf("// generated by go run gen.go; DO NOT EDIT\n\n")
 	fmt.Printf("package atom\n\nconst (\n")
-	{
-		// Print the Atoms in alphabetical order.
-		lines := []string{}
-		for i, _ := range byInt {
-			if i == 0 {
-				continue
-			}
-			lines = append(lines, fmt.Sprintf("\t%s Atom = %d", ident[i], i))
+	for _, s := range all {
+		fmt.Printf("\t%s Atom = %#x\n", identifier(s), atom[s])
+	}
+	fmt.Printf(")\n\n")
+
+	fmt.Printf("const hash0 = %#x\n\n", best.h0)
+	fmt.Printf("const maxAtomLen = %d\n\n", maxLen)
+
+	fmt.Printf("var table = [1<<%d]Atom{\n", best.k)
+	for i, s := range best.tab {
+		if s == "" {
+			continue
 		}
-		sort.Strings(lines)
-		for _, line := range lines {
-			fmt.Println(line)
+		fmt.Printf("\t%#x: %#x, // %s\n", i, atom[s], s)
+	}
+	fmt.Printf("}\n")
+	datasize := (1 << best.k) * 4
+
+	fmt.Printf("const atomText =\n")
+	textsize := len(text)
+	for len(text) > 60 {
+		fmt.Printf("\t%q +\n", text[:60])
+		text = text[60:]
+	}
+	fmt.Printf("\t%q\n\n", text)
+
+	fmt.Fprintf(os.Stderr, "%d atoms; %d string bytes + %d tables = %d total data\n", len(all), textsize, datasize, textsize+datasize)
+}
+
+type byLen []string
+
+func (x byLen) Less(i, j int) bool { return len(x[i]) > len(x[j]) }
+func (x byLen) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }
+func (x byLen) Len() int           { return len(x) }
+
+// fnv computes the FNV hash with an arbitrary starting value h.
+func fnv(h uint32, s string) uint32 {
+	for i := 0; i < len(s); i++ {
+		h ^= uint32(s[i])
+		h *= 16777619
+	}
+	return h
+}
+
+// A table represents an attempt at constructing the lookup table.
+// The lookup table uses cuckoo hashing, meaning that each string
+// can be found in one of two positions.
+type table struct {
+	h0   uint32
+	k    uint
+	mask uint32
+	tab  []string
+}
+
+// hash returns the two hashes for s.
+func (t *table) hash(s string) (h1, h2 uint32) {
+	h := fnv(t.h0, s)
+	h1 = h & t.mask
+	h2 = (h >> 16) & t.mask
+	return
+}
+
+// init initializes the table with the given parameters.
+// h0 is the initial hash value,
+// k is the number of bits of hash value to use, and
+// x is the list of strings to store in the table.
+// init returns false if the table cannot be constructed.
+func (t *table) init(h0 uint32, k uint, x []string) bool {
+	t.h0 = h0
+	t.k = k
+	t.tab = make([]string, 1<<k)
+	t.mask = 1<<k - 1
+	for _, s := range x {
+		if !t.insert(s) {
+			return false
 		}
-		fmt.Printf(")\n\n")
 	}
-	fmt.Printf("const maxLen = %d\n\n", maxLen)
-	fmt.Printf("var table = [...]string{\n")
-	for _, s := range byInt {
-		fmt.Printf("\t%q,\n", s)
+	return true
+}
+
+// insert inserts s in the table.
+func (t *table) insert(s string) bool {
+	h1, h2 := t.hash(s)
+	if t.tab[h1] == "" {
+		t.tab[h1] = s
+		return true
 	}
-	fmt.Printf("}\n\n")
-	fmt.Printf("var hashes = [...]uint32{\n")
-	for _, s := range byInt {
-		fmt.Printf("\t0x%08x,\n", hash(s))
+	if t.tab[h2] == "" {
+		t.tab[h2] = s
+		return true
 	}
-	fmt.Printf("}\n\n")
-	fmt.Printf("var loHi = [maxLen + 2]uint16{\n")
-	for n := 0; n <= maxLen; n++ {
-		fmt.Printf("\t%d,\n", sort.Search(len(byInt), func(i int) bool {
-			return int(lhashes[i]>>32) >= n
-		}))
+	if t.push(h1, 0) {
+		t.tab[h1] = s
+		return true
 	}
-	fmt.Printf("\t%d,\n", len(byInt))
-	fmt.Printf("}\n\n")
-	fmt.Printf("var oneByteAtoms = [26]Atom{\n")
-	for i := 'a'; i <= 'z'; i++ {
-		val := "0"
-		if x := byStr[string(i)]; x != 0 {
-			val = ident[x]
-		}
-		fmt.Printf("\t%s,\n", val)
+	if t.push(h2, 0) {
+		t.tab[h2] = s
+		return true
 	}
-	fmt.Printf("}\n\n")
+	return false
+}
+
+// push attempts to push aside the entry in slot i.
+func (t *table) push(i uint32, depth int) bool {
+	if depth > len(t.tab) {
+		return false
+	}
+	s := t.tab[i]
+	h1, h2 := t.hash(s)
+	j := h1 + h2 - i
+	if t.tab[j] != "" && !t.push(j, depth+1) {
+		return false
+	}
+	t.tab[j] = s
+	return true
 }
 
 // The lists of element names and attribute keys were taken from

File src/pkg/exp/html/atom/table.go

+// generated by go run gen.go; DO NOT EDIT
+
 package atom
 
 const (
-	A                Atom = 1
-	Abbr             Atom = 58
-	Accept           Atom = 126
-	AcceptCharset    Atom = 288
-	Accesskey        Atom = 230
-	Action           Atom = 127
-	Address          Atom = 182
-	Align            Atom = 91
-	Alt              Atom = 32
-	Annotation       Atom = 251
-	Applet           Atom = 128
-	Area             Atom = 59
-	Article          Atom = 184
-	Aside            Atom = 92
-	Async            Atom = 93
-	Audio            Atom = 94
-	Autocomplete     Atom = 278
-	Autofocus        Atom = 243
-	Autoplay         Atom = 221
-	B                Atom = 2
-	Base             Atom = 56
-	Bdi              Atom = 30
-	Bdo              Atom = 31
-	Blockquote       Atom = 248
-	Body             Atom = 57
-	Border           Atom = 124
-	Br               Atom = 8
-	Button           Atom = 125
-	Canvas           Atom = 121
-	Caption          Atom = 160
-	Center           Atom = 122
-	Challenge        Atom = 242
-	Charset          Atom = 163
-	Checked          Atom = 164
-	Cite             Atom = 53
-	Class            Atom = 90
-	Code             Atom = 54
-	Col              Atom = 29
-	Colgroup         Atom = 193
-	Color            Atom = 89
-	Cols             Atom = 55
-	Colspan          Atom = 167
-	Command          Atom = 166
-	Content          Atom = 165
-	Contenteditable  Atom = 292
-	Contextmenu      Atom = 277
-	Controls         Atom = 192
-	Coords           Atom = 123
-	Crossorigin      Atom = 266
-	Data             Atom = 62
-	Datalist         Atom = 219
-	Datetime         Atom = 220
-	Dd               Atom = 10
-	Default          Atom = 188
-	Defer            Atom = 97
-	Del              Atom = 35
-	Details          Atom = 189
-	Dfn              Atom = 34
-	Dialog           Atom = 131
-	Dir              Atom = 36
-	Dirname          Atom = 190
-	Disabled         Atom = 216
-	Div              Atom = 37
-	Dl               Atom = 11
-	Download         Atom = 195
-	Draggable        Atom = 235
-	Dropzone         Atom = 202
-	Dt               Atom = 12
-	Em               Atom = 9
-	Embed            Atom = 96
-	Enctype          Atom = 183
-	Fieldset         Atom = 212
-	Figcaption       Atom = 247
-	Figure           Atom = 129
-	Font             Atom = 60
-	Footer           Atom = 130
-	For              Atom = 33
-	Form             Atom = 61
-	Formaction       Atom = 256
-	Formenctype      Atom = 273
-	Formmethod       Atom = 261
-	Formnovalidate   Atom = 289
-	Formtarget       Atom = 263
-	Frame            Atom = 95
-	Frameset         Atom = 198
-	H1               Atom = 13
-	H2               Atom = 14
-	H3               Atom = 15
-	H4               Atom = 16
-	H5               Atom = 17
-	H6               Atom = 18
-	Head             Atom = 65
-	Header           Atom = 136
-	Headers          Atom = 187
-	Height           Atom = 137
-	Hgroup           Atom = 135
-	Hidden           Atom = 138
-	High             Atom = 66
-	Hr               Atom = 20
-	Href             Atom = 67
-	Hreflang         Atom = 199
-	Html             Atom = 68
-	HttpEquiv        Atom = 254
-	I                Atom = 3
-	Icon             Atom = 64
-	Id               Atom = 19
-	Iframe           Atom = 133
-	Img              Atom = 40
-	Inert            Atom = 98
-	Input            Atom = 99
-	Ins              Atom = 39
-	Ismap            Atom = 100
-	Itemid           Atom = 134
-	Itemprop         Atom = 223
-	Itemref          Atom = 185
-	Itemscope        Atom = 240
-	Itemtype         Atom = 224
-	Kbd              Atom = 38
-	Keygen           Atom = 132
-	Keytype          Atom = 162
-	Kind             Atom = 63
-	Label            Atom = 104
-	Lang             Atom = 75
-	Legend           Atom = 149
-	Li               Atom = 22
-	Link             Atom = 76
-	List             Atom = 77
-	Loop             Atom = 78
-	Low              Atom = 45
-	Manifest         Atom = 213
-	Map              Atom = 42
-	Mark             Atom = 72
-	Max              Atom = 43
-	Maxlength        Atom = 245
-	Media            Atom = 101
-	Mediagroup       Atom = 257
-	Menu             Atom = 73
-	Meta             Atom = 74
-	Meter            Atom = 102
-	Method           Atom = 148
-	Min              Atom = 44
-	Multiple         Atom = 215
-	Muted            Atom = 103
-	Name             Atom = 70
-	Nav              Atom = 41
-	Nobr             Atom = 71
-	Noscript         Atom = 194
-	Novalidate       Atom = 262
-	Object           Atom = 139
-	Ol               Atom = 21
-	Onabort          Atom = 170
-	Onafterprint     Atom = 280
-	Onbeforeprint    Atom = 287
-	Onbeforeunload   Atom = 291
-	Onblur           Atom = 140
-	Oncancel         Atom = 196
-	Oncanplay        Atom = 227
-	Oncanplaythrough Atom = 295
-	Onchange         Atom = 197
-	Onclick          Atom = 168
-	Onclose          Atom = 169
-	Oncontextmenu    Atom = 286
-	Oncuechange      Atom = 267
-	Ondblclick       Atom = 255
-	Ondrag           Atom = 141
-	Ondragend        Atom = 246
-	Ondragenter      Atom = 270
-	Ondragleave      Atom = 269
-	Ondragover       Atom = 252
-	Ondragstart      Atom = 268
-	Ondrop           Atom = 142
-	Ondurationchange Atom = 293
-	Onemptied        Atom = 241
-	Onended          Atom = 172
-	Onerror          Atom = 173
-	Onfocus          Atom = 171
-	Onhashchange     Atom = 283
-	Oninput          Atom = 175
-	Oninvalid        Atom = 239
-	Onkeydown        Atom = 231
-	Onkeypress       Atom = 264
-	Onkeyup          Atom = 174
-	Onload           Atom = 143
-	Onloadeddata     Atom = 284
-	Onloadedmetadata Atom = 294
-	Onloadstart      Atom = 271
-	Onmessage        Atom = 236
-	Onmousedown      Atom = 274
-	Onmousemove      Atom = 275
-	Onmouseout       Atom = 250
-	Onmouseover      Atom = 276
-	Onmouseup        Atom = 237
-	Onmousewheel     Atom = 279
-	Onoffline        Atom = 228
-	Ononline         Atom = 201
-	Onpagehide       Atom = 259
-	Onpageshow       Atom = 258
-	Onpause          Atom = 177
-	Onplay           Atom = 145
-	Onplaying        Atom = 244
-	Onpopstate       Atom = 249
-	Onprogress       Atom = 253
-	Onratechange     Atom = 282
-	Onreset          Atom = 176
-	Onresize         Atom = 207
-	Onscroll         Atom = 203
-	Onseeked         Atom = 204
-	Onseeking        Atom = 229
-	Onselect         Atom = 205
-	Onshow           Atom = 144
-	Onstalled        Atom = 233
-	Onstorage        Atom = 234
-	Onsubmit         Atom = 206
-	Onsuspend        Atom = 232
-	Ontimeupdate     Atom = 281
-	Onunload         Atom = 208
-	Onvolumechange   Atom = 290
-	Onwaiting        Atom = 226
-	Open             Atom = 69
-	Optgroup         Atom = 225
-	Optimum          Atom = 179
-	Option           Atom = 146
-	Output           Atom = 147
-	P                Atom = 4
-	Param            Atom = 111
-	Pattern          Atom = 186
-	Ping             Atom = 85
-	Placeholder      Atom = 272
-	Poster           Atom = 156
-	Pre              Atom = 50
-	Preload          Atom = 191
-	Progress         Atom = 200
-	Q                Atom = 5
-	Radiogroup       Atom = 260
-	Readonly         Atom = 210
-	Rel              Atom = 49
-	Required         Atom = 217
-	Reversed         Atom = 218
-	Rows             Atom = 83
-	Rowspan          Atom = 181
-	Rp               Atom = 23
-	Rt               Atom = 24
-	Ruby             Atom = 84
-	S                Atom = 6
-	Samp             Atom = 79
-	Sandbox          Atom = 159
-	Scope            Atom = 105
-	Scoped           Atom = 150
-	Script           Atom = 151
-	Seamless         Atom = 211
-	Section          Atom = 161
-	Select           Atom = 152
-	Selected         Atom = 214
-	Shape            Atom = 107
-	Size             Atom = 80
-	Sizes            Atom = 106
-	Small            Atom = 108
-	Source           Atom = 153
-	Span             Atom = 81
-	Spellcheck       Atom = 265
-	Src              Atom = 46
-	Srcdoc           Atom = 154
-	Srclang          Atom = 178
-	Start            Atom = 109
-	Step             Atom = 82
-	Strong           Atom = 155
-	Style            Atom = 110
-	Sub              Atom = 47
-	Summary          Atom = 180
-	Sup              Atom = 48
-	Tabindex         Atom = 209
-	Table            Atom = 116
-	Target           Atom = 158
-	Tbody            Atom = 115
-	Td               Atom = 26
-	Textarea         Atom = 222
-	Tfoot            Atom = 117
-	Th               Atom = 27
-	Thead            Atom = 119
-	Time             Atom = 87
-	Title            Atom = 118
-	Tr               Atom = 28
-	Track            Atom = 120
-	Translate        Atom = 238
-	Type             Atom = 88
-	Typemustmatch    Atom = 285
-	U                Atom = 7
-	Ul               Atom = 25
-	Usemap           Atom = 157
-	Value            Atom = 113
-	Var              Atom = 52
-	Video            Atom = 114
-	Wbr              Atom = 51
-	Width            Atom = 112
-	Wrap             Atom = 86
+	A                Atom = 0x1
+	Abbr             Atom = 0x4
+	Accept           Atom = 0x3606
+	AcceptCharset    Atom = 0x360e
+	Accesskey        Atom = 0x4809
+	Action           Atom = 0x21506
+	Address          Atom = 0x22507
+	Align            Atom = 0x8605
+	Alt              Atom = 0x8b03
+	Annotation       Atom = 0x16d0a
+	Applet           Atom = 0x2d706
+	Area             Atom = 0xd004
+	Article          Atom = 0x38307
+	Aside            Atom = 0x9f05
+	Async            Atom = 0x9705
+	Audio            Atom = 0xad05
+	Autocomplete     Atom = 0xc20c
+	Autofocus        Atom = 0xd909
+	Autoplay         Atom = 0xe808
+	B                Atom = 0x101
+	Base             Atom = 0xf004
+	Bdi              Atom = 0xbb03
+	Bdo              Atom = 0xfe03
+	Blockquote       Atom = 0x1110a
+	Body             Atom = 0x4404
+	Border           Atom = 0x11b06
+	Br               Atom = 0x202
+	Button           Atom = 0x12106
+	Canvas           Atom = 0x9b06
+	Caption          Atom = 0x1e607
+	Center           Atom = 0x1aa06
+	Challenge        Atom = 0x24409
+	Charset          Atom = 0x3d07
+	Checked          Atom = 0x1ba07
+	Cite             Atom = 0x1d104
+	Class            Atom = 0x13905
+	Code             Atom = 0x14f04
+	Col              Atom = 0x15603
+	Colgroup         Atom = 0x15608
+	Color            Atom = 0x16305
+	Cols             Atom = 0x16804
+	Colspan          Atom = 0x16807
+	Command          Atom = 0x17c07
+	Content          Atom = 0x2b907
+	Contenteditable  Atom = 0x2b90f
+	Contextmenu      Atom = 0x3320b
+	Controls         Atom = 0x19f08
+	Coords           Atom = 0x1b006
+	Crossorigin      Atom = 0x1c10b
+	Data             Atom = 0x40904
+	Datalist         Atom = 0x40908
+	Datetime         Atom = 0x26108
+	Dd               Atom = 0x22602
+	Default          Atom = 0xa207
+	Defer            Atom = 0x15105
+	Del              Atom = 0x49d03
+	Details          Atom = 0x2907
+	Dfn              Atom = 0x5d03
+	Dialog           Atom = 0xbc06
+	Dir              Atom = 0x6703
+	Dirname          Atom = 0x6707
+	Disabled         Atom = 0x1d708
+	Div              Atom = 0x1de03
+	Dl               Atom = 0x18202
+	Download         Atom = 0x3e608
+	Draggable        Atom = 0x19209
+	Dropzone         Atom = 0x38c08
+	Dt               Atom = 0x4ab02
+	Em               Atom = 0x2502
+	Embed            Atom = 0x2505
+	Enctype          Atom = 0x23607
+	Fieldset         Atom = 0x2e308
+	Figcaption       Atom = 0x1e30a
+	Figure           Atom = 0x1f806
+	Font             Atom = 0x20404
+	Footer           Atom = 0x8e06
+	For              Atom = 0x1ef03
+	Form             Atom = 0x21104
+	Formaction       Atom = 0x2110a
+	Formenctype      Atom = 0x2320b
+	Formmethod       Atom = 0x24d0a
+	Formnovalidate   Atom = 0x2570e
+	Formtarget       Atom = 0x26c0a
+	Frame            Atom = 0x2c905
+	Frameset         Atom = 0x2c908
+	H1               Atom = 0x10f02
+	H2               Atom = 0x29702
+	H3               Atom = 0x4ad02
+	H4               Atom = 0x27602
+	H5               Atom = 0x27802
+	H6               Atom = 0x27a02
+	Head             Atom = 0x30504
+	Header           Atom = 0x30506
+	Headers          Atom = 0x30507
+	Height           Atom = 0x27c06
+	Hgroup           Atom = 0x28806
+	Hidden           Atom = 0x28e06
+	High             Atom = 0x29404
+	Hr               Atom = 0x10a02
+	Href             Atom = 0x29904
+	Hreflang         Atom = 0x29908
+	Html             Atom = 0x28004
+	HttpEquiv        Atom = 0x2a10a
+	I                Atom = 0x601
+	Icon             Atom = 0x2b804
+	Id               Atom = 0xa102
+	Iframe           Atom = 0x2c806
+	Img              Atom = 0x2d103
+	Inert            Atom = 0x48805
+	Input            Atom = 0x3d305
+	Ins              Atom = 0x1ca03
+	Ismap            Atom = 0x2d405
+	Itemid           Atom = 0x1d206
+	Itemprop         Atom = 0x53608
+	Itemref          Atom = 0x2dd07
+	Itemscope        Atom = 0x2eb09
+	Itemtype         Atom = 0x2f508
+	Kbd              Atom = 0xba03
+	Keygen           Atom = 0x4e06
+	Keytype          Atom = 0x14807
+	Kind             Atom = 0x2b404
+	Label            Atom = 0x14105
+	Lang             Atom = 0x22e04
+	Legend           Atom = 0x19906
+	Li               Atom = 0x8702
+	Link             Atom = 0x14504
+	List             Atom = 0x40d04
+	Loop             Atom = 0x18304
+	Low              Atom = 0x28303
+	Manifest         Atom = 0x1008
+	Map              Atom = 0x2d603
+	Mark             Atom = 0x56e04
+	Max              Atom = 0x2fd03
+	Maxlength        Atom = 0x2fd09
+	Media            Atom = 0x6c05
+	Mediagroup       Atom = 0x6c0a
+	Menu             Atom = 0x33904
+	Meta             Atom = 0x41d04
+	Meter            Atom = 0x26705
+	Method           Atom = 0x25106
+	Min              Atom = 0x31003
+	Multiple         Atom = 0x31308
+	Muted            Atom = 0x31b05
+	Name             Atom = 0x6a04
+	Nav              Atom = 0x1f03
+	Nobr             Atom = 0x5304
+	Noscript         Atom = 0x5f08
+	Novalidate       Atom = 0x25b0a
+	Object           Atom = 0xb106
+	Ol               Atom = 0x7b02
+	Onabort          Atom = 0x17507
+	Onafterprint     Atom = 0x1250c
+	Onbeforeprint    Atom = 0x1eb0d
+	Onbeforeunload   Atom = 0x2190e
+	Onblur           Atom = 0x32a06
+	Oncancel         Atom = 0x57608
+	Oncanplay        Atom = 0x10009
+	Oncanplaythrough Atom = 0x10010
+	Onchange         Atom = 0x3a208
+	Onclick          Atom = 0x2ae07
+	Onclose          Atom = 0x32007
+	Oncontextmenu    Atom = 0x3300d
+	Oncuechange      Atom = 0x33d0b
+	Ondblclick       Atom = 0x3480a
+	Ondrag           Atom = 0x35206
+	Ondragend        Atom = 0x35209
+	Ondragenter      Atom = 0x35b0b
+	Ondragleave      Atom = 0x3660b
+	Ondragover       Atom = 0x3710a
+	Ondragstart      Atom = 0x37b0b
+	Ondrop           Atom = 0x38a06
+	Ondurationchange Atom = 0x39a10
+	Onemptied        Atom = 0x39109
+	Onended          Atom = 0x3aa07
+	Onerror          Atom = 0x3b107
+	Onfocus          Atom = 0x3b807
+	Onhashchange     Atom = 0x3c50c
+	Oninput          Atom = 0x3d107
+	Oninvalid        Atom = 0x3d809
+	Onkeydown        Atom = 0x3e109
+	Onkeypress       Atom = 0x3ee0a
+	Onkeyup          Atom = 0x3fa07
+	Onload           Atom = 0x40106
+	Onloadeddata     Atom = 0x4010c
+	Onloadedmetadata Atom = 0x41510
+	Onloadstart      Atom = 0x42b0b
+	Onmessage        Atom = 0x43609
+	Onmousedown      Atom = 0x43f0b
+	Onmousemove      Atom = 0x44a0b
+	Onmouseout       Atom = 0x4550a
+	Onmouseover      Atom = 0x4620b
+	Onmouseup        Atom = 0x46d09
+	Onmousewheel     Atom = 0x4760c
+	Onoffline        Atom = 0x48209
+	Ononline         Atom = 0x48d08
+	Onpagehide       Atom = 0x4950a
+	Onpageshow       Atom = 0x4a00a
+	Onpause          Atom = 0x4af07
+	Onplay           Atom = 0x4b906
+	Onplaying        Atom = 0x4b909
+	Onpopstate       Atom = 0x4c20a
+	Onprogress       Atom = 0x4cc0a
+	Onratechange     Atom = 0x4d60c
+	Onreset          Atom = 0x4e207
+	Onresize         Atom = 0x4e908
+	Onscroll         Atom = 0x4f208
+	Onseeked         Atom = 0x4fa08
+	Onseeking        Atom = 0x50209
+	Onselect         Atom = 0x50b08
+	Onshow           Atom = 0x51506
+	Onstalled        Atom = 0x51e09
+	Onstorage        Atom = 0x52709
+	Onsubmit         Atom = 0x53008
+	Onsuspend        Atom = 0x54009
+	Ontimeupdate     Atom = 0x2050c
+	Onunload         Atom = 0x54908
+	Onvolumechange   Atom = 0x5510e
+	Onwaiting        Atom = 0x55f09
+	Open             Atom = 0x53c04
+	Optgroup         Atom = 0x18508
+	Optimum          Atom = 0x56807
+	Option           Atom = 0x57206
+	Output           Atom = 0x45c06
+	P                Atom = 0xc01
+	Param            Atom = 0xc05
+	Pattern          Atom = 0x1907
+	Ping             Atom = 0x3204
+	Placeholder      Atom = 0x750b
+	Poster           Atom = 0x15d06
+	Pre              Atom = 0x18c03
+	Preload          Atom = 0x18c07
+	Progress         Atom = 0x4ce08
+	Q                Atom = 0x11601
+	Radiogroup       Atom = 0x30a
+	Readonly         Atom = 0xd108
+	Rel              Atom = 0x18d03
+	Required         Atom = 0x1fc08
+	Reversed         Atom = 0x5608
+	Rows             Atom = 0x7f04
+	Rowspan          Atom = 0x7f07
+	Rp               Atom = 0x12b02
+	Rt               Atom = 0x17a02
+	Ruby             Atom = 0x9304
+	S                Atom = 0x1601
+	Samp             Atom = 0x2f04
+	Sandbox          Atom = 0xe107
+	Scope            Atom = 0x2ef05
+	Scoped           Atom = 0x2ef06
+	Script           Atom = 0x6106
+	Seamless         Atom = 0xf208
+	Section          Atom = 0x32507
+	Select           Atom = 0x50d06
+	Selected         Atom = 0x50d08
+	Shape            Atom = 0xf905
+	Size             Atom = 0x4ed04
+	Sizes            Atom = 0x4ed05
+	Small            Atom = 0x13d05
+	Source           Atom = 0x1a606
+	Span             Atom = 0x8204
+	Spellcheck       Atom = 0x1b50a
+	Src              Atom = 0x1cc03
+	Srcdoc           Atom = 0x1cc06
+	Srclang          Atom = 0x22b07
+	Start            Atom = 0x38105
+	Step             Atom = 0x1604
+	Strong           Atom = 0x40f06
+	Style            Atom = 0x30b05
+	Sub              Atom = 0x53203
+	Summary          Atom = 0x3be07
+	Sup              Atom = 0x3f703
+	Tabindex         Atom = 0x42308
+	Table            Atom = 0x2c305
+	Target           Atom = 0x27006
+	Tbody            Atom = 0x4305
+	Td               Atom = 0x6602
+	Textarea         Atom = 0xcc08
+	Tfoot            Atom = 0x8d05
+	Th               Atom = 0x10902
+	Thead            Atom = 0x30405
+	Time             Atom = 0x20704
+	Title            Atom = 0xa805
+	Tr               Atom = 0xb602
+	Track            Atom = 0xb605
+	Translate        Atom = 0x13009
+	Type             Atom = 0x14b04
+	Typemustmatch    Atom = 0x2390d
+	U                Atom = 0xb01
+	Ul               Atom = 0xa602
+	Usemap           Atom = 0x4b306
+	Value            Atom = 0x2105
+	Var              Atom = 0x1e003
+	Video            Atom = 0x2aa05
+	Wbr              Atom = 0x28503
+	Width            Atom = 0x4a905
+	Wrap             Atom = 0x51a04
 )
 
-const maxLen = 16
+const hash0 = 0x516c42b0
 
-var table = [...]string{
-	"",
-	"a",
-	"b",
-	"i",
-	"p",
-	"q",
-	"s",
-	"u",
-	"br",
-	"em",
-	"dd",
-	"dl",
-	"dt",
-	"h1",
-	"h2",
-	"h3",
-	"h4",
-	"h5",
-	"h6",
-	"id",
-	"hr",
-	"ol",
-	"li",
-	"rp",
-	"rt",
-	"ul",
-	"td",
-	"th",
-	"tr",
-	"col",
-	"bdi",
-	"bdo",
-	"alt",
-	"for",
-	"dfn",
-	"del",
-	"dir",
-	"div",
-	"kbd",
-	"ins",
-	"img",
-	"nav",
-	"map",
-	"max",
-	"min",
-	"low",
-	"src",
-	"sub",
-	"sup",
-	"rel",
-	"pre",
-	"wbr",
-	"var",
-	"cite",
-	"code",
-	"cols",
-	"base",
-	"body",
-	"abbr",
-	"area",
-	"font",
-	"form",
-	"data",
-	"kind",
-	"icon",
-	"head",
-	"high",
-	"href",
-	"html",
-	"open",
-	"name",
-	"nobr",
-	"mark",
-	"menu",
-	"meta",
-	"lang",
-	"link",
-	"list",
-	"loop",
-	"samp",
-	"size",
-	"span",
-	"step",
-	"rows",
-	"ruby",
-	"ping",
-	"wrap",
-	"time",
-	"type",
-	"color",
-	"class",
-	"align",
-	"aside",
-	"async",
-	"audio",
-	"frame",
-	"embed",
-	"defer",
-	"inert",
-	"input",
-	"ismap",
-	"media",
-	"meter",
-	"muted",
-	"label",
-	"scope",
-	"sizes",
-	"shape",
-	"small",
-	"start",
-	"style",
-	"param",
-	"width",
-	"value",
-	"video",
-	"tbody",
-	"table",
-	"tfoot",
-	"title",
-	"thead",
-	"track",
-	"canvas",
-	"center",
-	"coords",
-	"border",
-	"button",
-	"accept",
-	"action",
-	"applet",
-	"figure",
-	"footer",
-	"dialog",
-	"keygen",
-	"iframe",
-	"itemid",
-	"hgroup",
-	"header",
-	"height",
-	"hidden",
-	"object",
-	"onblur",
-	"ondrag",
-	"ondrop",
-	"onload",
-	"onshow",
-	"onplay",
-	"option",
-	"output",
-	"method",
-	"legend",
-	"scoped",
-	"script",
-	"select",
-	"source",
-	"srcdoc",
-	"strong",
-	"poster",
-	"usemap",
-	"target",
-	"sandbox",
-	"caption",
-	"section",
-	"keytype",
-	"charset",
-	"checked",
-	"content",
-	"command",
-	"colspan",
-	"onclick",
-	"onclose",
-	"onabort",
-	"onfocus",
-	"onended",
-	"onerror",
-	"onkeyup",
-	"oninput",
-	"onreset",
-	"onpause",
-	"srclang",
-	"optimum",
-	"summary",
-	"rowspan",
-	"address",
-	"enctype",
-	"article",
-	"itemref",
-	"pattern",
-	"headers",
-	"default",
-	"details",
-	"dirname",
-	"preload",
-	"controls",
-	"colgroup",
-	"noscript",
-	"download",
-	"oncancel",
-	"onchange",
-	"frameset",
-	"hreflang",
-	"progress",
-	"ononline",
-	"dropzone",
-	"onscroll",
-	"onseeked",
-	"onselect",
-	"onsubmit",
-	"onresize",
-	"onunload",
-	"tabindex",
-	"readonly",
-	"seamless",
-	"fieldset",
-	"manifest",
-	"selected",
-	"multiple",
-	"disabled",
-	"required",
-	"reversed",
-	"datalist",
-	"datetime",
-	"autoplay",
-	"textarea",
-	"itemprop",
-	"itemtype",
-	"optgroup",
-	"onwaiting",
-	"oncanplay",
-	"onoffline",
-	"onseeking",
-	"accesskey",
-	"onkeydown",
-	"onsuspend",
-	"onstalled",
-	"onstorage",
-	"draggable",
-	"onmessage",
-	"onmouseup",
-	"translate",
-	"oninvalid",
-	"itemscope",
-	"onemptied",
-	"challenge",
-	"autofocus",
-	"onplaying",
-	"maxlength",
-	"ondragend",
-	"figcaption",
-	"blockquote",
-	"onpopstate",
-	"onmouseout",
-	"annotation",
-	"ondragover",
-	"onprogress",
-	"http-equiv",
-	"ondblclick",
-	"formaction",
-	"mediagroup",
-	"onpageshow",
-	"onpagehide",
-	"radiogroup",
-	"formmethod",
-	"novalidate",
-	"formtarget",
-	"onkeypress",
-	"spellcheck",
-	"crossorigin",
-	"oncuechange",
-	"ondragstart",
-	"ondragleave",
-	"ondragenter",
-	"onloadstart",
-	"placeholder",
-	"formenctype",
-	"onmousedown",
-	"onmousemove",
-	"onmouseover",
-	"contextmenu",
-	"autocomplete",
-	"onmousewheel",
-	"onafterprint",
-	"ontimeupdate",
-	"onratechange",
-	"onhashchange",
-	"onloadeddata",
-	"typemustmatch",
-	"oncontextmenu",
-	"onbeforeprint",
-	"accept-charset",
-	"formnovalidate",
-	"onvolumechange",
-	"onbeforeunload",
-	"contenteditable",
-	"ondurationchange",
-	"onloadedmetadata",
-	"oncanplaythrough",
+const maxAtomLen = 16
+
+var table = [1 << 9]Atom{
+	0x2:   0x1f03,  // nav
+	0x3:   0x17507, // onabort
+	0x4:   0x1aa06, // center
+	0x5:   0x14f04, // code
+	0x7:   0x27802, // h5
+	0xb:   0x1110a, // blockquote
+	0xd:   0x4404,  // body
+	0xe:   0x10a02, // hr
+	0x11:  0x25b0a, // novalidate
+	0x14:  0x2c305, // table
+	0x16:  0x4cc0a, // onprogress
+	0x17:  0x3b807, // onfocus
+	0x19:  0x39a10, // ondurationchange
+	0x1c:  0x22e04, // lang
+	0x1f:  0xb01,   // u
+	0x20:  0x3e608, // download
+	0x21:  0x26705, // meter
+	0x22:  0x28303, // low
+	0x24:  0x4f208, // onscroll
+	0x26:  0x19f08, // controls
+	0x27:  0x6703,  // dir
+	0x29:  0x18c03, // pre
+	0x2a:  0x1b50a, // spellcheck
+	0x2b:  0x28806, // hgroup
+	0x2d:  0x4e908, // onresize
+	0x2e:  0x35b0b, // ondragenter
+	0x30:  0x48805, // inert
+	0x32:  0x2390d, // typemustmatch
+	0x33:  0x6a04,  // name
+	0x35:  0x28503, // wbr
+	0x36:  0x1eb0d, // onbeforeprint
+	0x39:  0x4af07, // onpause
+	0x3b:  0x24d0a, // formmethod
+	0x3e:  0x2fd03, // max
+	0x3f:  0x2d103, // img
+	0x40:  0xc01,   // p
+	0x41:  0x19906, // legend
+	0x43:  0x2c806, // iframe
+	0x44:  0x55f09, // onwaiting
+	0x45:  0x18c07, // preload
+	0x46:  0x1e607, // caption
+	0x47:  0xba03,  // kbd
+	0x49:  0x20704, // time
+	0x4a:  0x1ca03, // ins
+	0x4d:  0xbb03,  // bdi
+	0x4e:  0x14105, // label
+	0x4f:  0x18d03, // rel
+	0x50:  0x2ef05, // scope
+	0x51:  0x2050c, // ontimeupdate
+	0x53:  0xd909,  // autofocus
+	0x54:  0xc20c,  // autocomplete
+	0x55:  0x28004, // html
+	0x56:  0x1e30a, // figcaption
+	0x59:  0x17c07, // command
+	0x5d:  0x2c905, // frame
+	0x5f:  0x1ef03, // for
+	0x60:  0x1250c, // onafterprint
+	0x61:  0x2f04,  // samp
+	0x62:  0x30507, // headers
+	0x63:  0x4b306, // usemap
+	0x65:  0x14b04, // type
+	0x6b:  0x26108, // datetime
+	0x6d:  0xa102,  // id
+	0x6e:  0x30405, // thead
+	0x6f:  0x15d06, // poster
+	0x70:  0x18202, // dl
+	0x71:  0x2b804, // icon
+	0x74:  0x51e09, // onstalled
+	0x75:  0x16804, // cols
+	0x76:  0x4ed05, // sizes
+	0x78:  0x13d05, // small
+	0x79:  0x3a208, // onchange
+	0x7b:  0x3b107, // onerror
+	0x7c:  0x4a905, // width
+	0x7d:  0x20404, // font
+	0x7e:  0x28e06, // hidden
+	0x7f:  0x10009, // oncanplay
+	0x81:  0xe808,  // autoplay
+	0x82:  0x1d104, // cite
+	0x84:  0x3d07,  // charset
+	0x85:  0x3710a, // ondragover
+	0x86:  0x2502,  // em
+	0x87:  0x1cc03, // src
+	0x89:  0x1ba07, // checked
+	0x8a:  0xad05,  // audio
+	0x8b:  0x19209, // draggable
+	0x8d:  0x1c10b, // crossorigin
+	0x8e:  0x18304, // loop
+	0x90:  0x2dd07, // itemref
+	0x93:  0x4ce08, // progress
+	0x94:  0x3d305, // input
+	0x96:  0x101,   // b
+	0x98:  0x5510e, // onvolumechange
+	0x99:  0x27006, // target
+	0x9c:  0x4a00a, // onpageshow
+	0x9d:  0x2eb09, // itemscope
+	0x9e:  0x54908, // onunload
+	0x9f:  0xf208,  // seamless
+	0xa3:  0x8e06,  // footer
+	0xa6:  0x2907,  // details
+	0xa7:  0x3ee0a, // onkeypress
+	0xaa:  0x1d708, // disabled
+	0xab:  0x31308, // multiple
+	0xac:  0x3d809, // oninvalid
+	0xad:  0x46d09, // onmouseup
+	0xaf:  0x2d405, // ismap
+	0xb0:  0x8204,  // span
+	0xb2:  0x1d206, // itemid
+	0xb3:  0x6106,  // script
+	0xb6:  0x21104, // form
+	0xb8:  0x9f05,  // aside
+	0xba:  0x38307, // article
+	0xbb:  0x12b02, // rp
+	0xbc:  0x29404, // high
+	0xbe:  0x1a606, // source
+	0xbf:  0xe107,  // sandbox
+	0xc0:  0x5d03,  // dfn
+	0xc1:  0x3204,  // ping
+	0xc2:  0x4ed04, // size
+	0xc3:  0x2ae07, // onclick
+	0xc5:  0x29908, // hreflang
+	0xc7:  0x2f508, // itemtype
+	0xc8:  0x1cc06, // srcdoc
+	0xc9:  0x40d04, // list
+	0xcc:  0x2d706, // applet
+	0xcf:  0x4760c, // onmousewheel
+	0xd0:  0x22507, // address
+	0xd1:  0x25106, // method
+	0xd5:  0x49d03, // del
+	0xd7:  0x35206, // ondrag
+	0xd9:  0x41510, // onloadedmetadata
+	0xda:  0xcc08,  // textarea
+	0xdb:  0x4e207, // onreset
+	0xdc:  0x57206, // option
+	0xdd:  0x2505,  // embed
+	0xdf:  0x3d107, // oninput
+	0xe0:  0x40908, // datalist
+	0xe1:  0x4ad02, // h3
+	0xe3:  0x202,   // br
+	0xe5:  0x40f06, // strong
+	0xe6:  0x5608,  // reversed
+	0xea:  0x22b07, // srclang
+	0xec:  0x10902, // th
+	0xef:  0x45c06, // output
+	0xf2:  0x27602, // h4
+	0xf5:  0x42308, // tabindex
+	0xf6:  0x2b907, // content
+	0xf9:  0x1601,  // s
+	0xfb:  0x3320b, // contextmenu
+	0xfc:  0x33d0b, // oncuechange
+	0xfe:  0x52709, // onstorage
+	0x100: 0x4305,  // tbody
+	0x101: 0x50d06, // select
+	0x102: 0x2320b, // formenctype
+	0x103: 0x1,     // a
+	0x104: 0x51a04, // wrap
+	0x108: 0x22602, // dd
+	0x109: 0xa602,  // ul
+	0x10a: 0x4950a, // onpagehide
+	0x10c: 0x43609, // onmessage
+	0x10d: 0xa207,  // default
+	0x10f: 0x38c08, // dropzone
+	0x111: 0x53008, // onsubmit
+	0x114: 0x9705,  // async
+	0x119: 0x50d08, // selected
+	0x11a: 0x2fd09, // maxlength
+	0x11c: 0x15105, // defer
+	0x11d: 0x16807, // colspan
+	0x11e: 0x3480a, // ondblclick
+	0x121: 0x2b90f, // contenteditable
+	0x125: 0x16d0a, // annotation
+	0x12a: 0x31003, // min
+	0x12c: 0x4fa08, // onseeked
+	0x12e: 0x11b06, // border
+	0x12f: 0x4b906, // onplay
+	0x130: 0x2ef06, // scoped
+	0x134: 0x2e308, // fieldset
+	0x135: 0x1b006, // coords
+	0x136: 0x6707,  // dirname
+	0x137: 0x32007, // onclose
+	0x138: 0x6602,  // td
+	0x13c: 0x32a06, // onblur
+	0x140: 0x9304,  // ruby
+	0x141: 0x50b08, // onselect
+	0x143: 0x3300d, // oncontextmenu
+	0x144: 0x12106, // button
+	0x146: 0xa805,  // title
+	0x147: 0x16305, // color
+	0x14a: 0x4620b, // onmouseover
+	0x14b: 0x23607, // enctype
+	0x14e: 0x29702, // h2
+	0x150: 0x3e109, // onkeydown
+	0x151: 0x3c50c, // onhashchange
+	0x152: 0x1604,  // step
+	0x153: 0x2aa05, // video
+	0x155: 0x4d60c, // onratechange
+	0x156: 0x17a02, // rt
+	0x157: 0x33904, // menu
+	0x15d: 0x37b0b, // ondragstart
+	0x160: 0x14504, // link
+	0x163: 0x7f07,  // rowspan
+	0x164: 0x4550a, // onmouseout
+	0x165: 0x29904, // href
+	0x167: 0x26c0a, // formtarget
+	0x169: 0xd004,  // area
+	0x16b: 0x8b03,  // alt
+	0x16d: 0x15608, // colgroup
+	0x16e: 0x30a,   // radiogroup
+	0x170: 0x30506, // header
+	0x172: 0x53203, // sub
+	0x174: 0x10010, // oncanplaythrough
+	0x175: 0x13009, // translate
+	0x176: 0x48d08, // ononline
+	0x179: 0x24409, // challenge
+	0x17c: 0x3f703, // sup
+	0x17d: 0x8605,  // align
+	0x17f: 0x5304,  // nobr
+	0x180: 0x1f806, // figure
+	0x181: 0xc05,   // param
+	0x184: 0x35209, // ondragend
+	0x185: 0x18508, // optgroup
+	0x186: 0x31b05, // muted
+	0x187: 0x6c0a,  // mediagroup
+	0x18a: 0x21506, // action
+	0x18c: 0x53c04, // open
+	0x18e: 0xf905,  // shape
+	0x18f: 0x54009, // onsuspend
+	0x190: 0x38a06, // ondrop
+	0x191: 0x56807, // optimum
+	0x192: 0x53608, // itemprop
+	0x193: 0x39109, // onemptied
+	0x195: 0xf004,  // base
+	0x198: 0x40904, // data
+	0x19a: 0x27a02, // h6
+	0x19b: 0x601,   // i
+	0x19c: 0x2110a, // formaction
+	0x19d: 0x360e,  // accept-charset
+	0x19e: 0x1e003, // var
+	0x19f: 0x57608, // oncancel
+	0x1a0: 0x750b,  // placeholder
+	0x1a1: 0x4e06,  // keygen
+	0x1a2: 0x3660b, // ondragleave
+	0x1a4: 0x4010c, // onloadeddata
+	0x1a6: 0x2d603, // map
+	0x1a7: 0x2a10a, // http-equiv
+	0x1a8: 0x1907,  // pattern
+	0x1a9: 0x4c20a, // onpopstate
+	0x1ab: 0x2570e, // formnovalidate
+	0x1ad: 0x44a0b, // onmousemove
+	0x1af: 0x42b0b, // onloadstart
+	0x1b0: 0xb605,  // track
+	0x1b2: 0x2b404, // kind
+	0x1b3: 0x7b02,  // ol
+	0x1b4: 0x6c05,  // media
+	0x1b5: 0x3be07, // summary
+	0x1b7: 0x14807, // keytype
+	0x1b8: 0x5f08,  // noscript
+	0x1b9: 0x1fc08, // required
+	0x1bb: 0x1de03, // div
+	0x1bd: 0x3fa07, // onkeyup
+	0x1be: 0xd108,  // readonly
+	0x1bf: 0x3aa07, // onended
+	0x1c5: 0x4b909, // onplaying
+	0x1c7: 0x32507, // section
+	0x1c8: 0x3606,  // accept
+	0x1c9: 0x4809,  // accesskey
+	0x1ca: 0x30b05, // style
+	0x1cb: 0x2c908, // frameset
+	0x1cc: 0x38105, // start
+	0x1cd: 0x43f0b, // onmousedown
+	0x1d2: 0x30504, // head
+	0x1d3: 0x11601, // q
+	0x1d4: 0x48209, // onoffline
+	0x1d5: 0x41d04, // meta
+	0x1d8: 0x4ab02, // dt
+	0x1da: 0xb602,  // tr
+	0x1db: 0x50209, // onseeking
+	0x1dc: 0xbc06,  // dialog
+	0x1e0: 0x51506, // onshow
+	0x1e1: 0x2105,  // value
+	0x1e2: 0x9b06,  // canvas
+	0x1e3: 0x4,     // abbr
+	0x1e5: 0x7f04,  // rows
+	0x1e7: 0xb106,  // object
+	0x1e8: 0x13905, // class
+	0x1eb: 0x27c06, // height
+	0x1ed: 0x2190e, // onbeforeunload
+	0x1ee: 0x8d05,  // tfoot
+	0x1f1: 0x56e04, // mark
+	0x1f2: 0x10f02, // h1
+	0x1f5: 0x40106, // onload
+	0x1f9: 0x1008,  // manifest
+	0x1fa: 0x15603, // col
+	0x1fc: 0x8702,  // li
+	0x1ff: 0xfe03,  // bdo
 }
 
-var hashes = [...]uint32{
-	0x00000000,
-	0x00000061,
-	0x00000062,
-	0x00000069,
-	0x00000070,
-	0x00000071,
-	0x00000073,
-	0x00000075,
-	0x00000c32,
-	0x00000ccd,
-	0x00000ce4,
-	0x00000cec,
-	0x00000cf4,
-	0x00000d31,
-	0x00000d32,
-	0x00000d33,
-	0x00000d34,
-	0x00000d35,
-	0x00000d36,
-	0x00000d44,
-	0x00000d72,
-	0x00000d8c,
-	0x00000de9,
-	0x00000e30,
-	0x00000e34,
-	0x00000ecc,
-	0x00000ee4,
-	0x00000ee8,
-	0x00000ef2,
-	0x0001818c,
-	0x000184e9,
-	0x000184ef,
-	0x000189f4,
-	0x00019592,
-	0x00019cae,
-	0x00019ccc,
-	0x00019d52,
-	0x00019d56,
-	0x0001a024,
-	0x0001a9b3,
-	0x0001a9c7,
-	0x0001b456,
-	0x0001b850,
-	0x0001b858,
-	0x0001b94e,
-	0x0001bd97,
-	0x0001c223,
-	0x0001c2c2,
-	0x0001c2d0,
-	0x0001c4cc,
-	0x0001ce25,
-	0x0001d032,
-	0x0001d452,
-	0x00302ae5,
-	0x003030e5,
-	0x003031f3,
-	0x00308a05,
-	0x0030b0f9,
-	0x00310432,
-	0x003144c1,
-	0x0032b1b4,
-	0x0032b22d,
-	0x00338ae1,
-	0x003429a4,
-	0x0035018e,
-	0x00359844,
-	0x0035a888,
-	0x0035c4c6,
-	0x0035ddcc,
-	0x00364cce,
-	0x003689c5,
-	0x0036b032,
-	0x00370a2b,
-	0x003719b5,
-	0x00371ae1,
-	0x003789a7,
-	0x0037a9ab,
-	0x0037aa14,
-	0x0037b190,
-	0x003809d0,
-	0x00382b25,
-	0x00384c4e,
-	0x00385cd0,
-	0x0038b293,
-	0x0038d839,
-	0x0039a9a7,
-	0x003a4450,
-	0x003ba9c5,
-	0x003bea65,
-	0x06063d92,
-	0x06078a13,
-	0x0627a88e,
-	0x062828e5,
-	0x062869a3,
-	0x062b1d4f,
-	0x065889c5,
-	0x066704c4,
-	0x067314d2,
-	0x06a69a34,
-	0x06a6ced4,
-	0x06a83850,
-	0x06e31d41,
-	0x06e35cd2,
-	0x06eb5cc4,
-	0x06f104cc,
-	0x07003265,
-	0x070564d3,
-	0x07058a65,
-	0x070709ec,
-	0x070b8a34,
-	0x070be9e5,
-	0x0731444d,
-	0x07451ee8,
-	0x07513ec5,
-	0x07551ccf,
-	0x0770b0f9,
-	0x077105e5,
-	0x0772b194,
-	0x07755de5,
-	0x07759844,
-	0x0778880b,
-	0xc026d453,
-	0xc066dcd2,
-	0xc0c644f3,
-	0xc2c89cd2,
-	0xc36bdd8e,
-	0xc4001a74,
-	0xc40ba98e,
-	0xc539bcd4,
-	0xcaa25a25,
-	0xcac65cd2,
-	0xcea13d87,
-	0xd06d10ce,
-	0xd45889c5,
-	0xd5733944,
-	0xd648b2d0,
-	0xd6611cd2,
-	0xd6651174,
-	0xd6a39cce,
-	0xd8149814,
-	0xd8d0bed2,
-	0xd8d3c447,
-	0xd8d3c590,
-	0xd8d7b044,
-	0xd8d82d97,
-	0xd8d9bc59,
-	0xd93ba98e,
-	0xd96bced4,
-	0xdc6bad84,
-	0xde6219a4,
-	0xe0064cc4,
-	0xe008aa74,
-	0xe0679814,
-	0xe0cb4405,
-	0xe1101d83,
-	0xe178b1a7,
-	0xe6c85cd2,
-	0xed033850,
-	0xee2890d4,
-	0x04d38584,
-	0x053ba996,
-	0x0c0ba992,
-	0x0dabea7f,
-	0x1628c0cc,
-	0x166020dc,
-	0x18db99ac,
-	0x18e709bc,
-	0x18f84c56,
-	0x1a07a810,
-	0x1a07b21e,
-	0x1a20b22f,
-	0x1a5602c8,
-	0x1a669cdf,
-	0x1a68c589,
-	0x1a836acb,
-	0x1aa6cecf,
-	0x1b1340cf,
-	0x1b315a1e,
-	0x220789bb,
-	0x27753ad6,
-	0x2ce70a25,
-	0x59484c52,
-	0x8e789a0b,
-	0x9a0bea7c,
-	0xa37501fd,
-	0xae6744dc,
-	0xc57b9a32,
-	0xcc239a29,
-	0xcc5159ed,
-	0xcd7129ea,
-	0xd51689dc,
-	0xe267b058,
-	0x1b78b2f0,
-	0x1e48b1d3,
-	0x2008a91f,
-	0x28d7b37f,
-	0x402683af,
-	0x40b137e6,
-	0x44e343f8,
-	0x4c578afb,
-	0x5848998f,
-	0x58d7aac6,
-	0x593cb299,
-	0x6008b28f,
-	0x606323a7,
-	0x60679b77,
-	0x6160ba37,
-	0x62682846,
-	0x6cd7b327,
-	0x82a69f60,
-	0x84763670,
-	0x84e79992,
-	0x8cf3c3fe,
-	0x9aa29964,
-	0x9e605f45,
-	0x9f754e90,
-	0xa020bffe,
-	0xa565474d,
-	0xaa68c34d,
-	0xae27a92c,
-	0xae6baafd,
-	0xaec9bf4c,
-	0xb7714778,
-	0xcce9c6c5,
-	0xccebe930,
-	0xee48b1b4,
-	0x04abc5ca,
-	0x04d9d031,
-	0x0a57c5ce,
-	0x0c6445cb,
-	0x0d0842d9,
-	0x0da3dee4,
-	0x2d09f5c8,
-	0x2e27d0a8,
-	0x2ec8e4e9,
-	0x8841626d,
-	0x8d0864ee,
-	0x996876bb,
-	0x9b07fd6d,
-	0x9b51512e,
-	0x9d0058dc,
-	0x9d3bc4ad,
-	0x9ef354dd,
-	0xd8566066,
-	0xde2d45cb,
-	0xde66fcfe,
-	0xe22275cd,
-	0x053703ae,
-	0x11271d85,
-	0x2706077e,
-	0x2d0ebfa7,
-	0x2e27e4e5,
-	0x444bd9ee,
-	0x5845178f,
-	0x5c642eea,
-	0x5e0a2533,
-	0x84070505,
-	0x844574ea,
-	0x8865a00f,
-	0x8868257d,
-	0x984690ea,
-	0x9c67010f,
-	0x9eae264d,
-	0xae243c5f,
-	0xb5351752,
-	0xde0b8b38,
-	0x18973dca,
-	0x81009434,
-	0x88ba2dbc,
-	0x8942ad2d,
-	0x89d77b5a,
-	0x8eba2554,
-	0x970a7ed3,
-	0x9b9e7b14,
-	0xa1d21ceb,
-	0xa1d69cc0,
-	0xa1d7fab7,
-	0xb6f6940c,
-	0x2c6d76e6,
-	0x3b705478,
-	0x950cec0d,
-	0x9b056094,
-	0xb687163c,
-	0xf6845607,
-	0xfa4666f0,
-	0x53ad92bb,
-	0x71f6940a,
-	0x8bbc6cd6,
-	0x1632b560,
-	0x561a2687,
-	0x5a00c22c,
-	0x7c4f1c15,
-	0x0ee8aacc,
-	0x2838bda9,
-	0x6f3c2ece,
-	0xf1d8d91d,
-}
-
-var loHi = [maxLen + 2]uint16{
-	0,
-	1,
-	8,
-	29,
-	53,
-	89,
-	121,
-	159,
-	192,
-	226,
-	247,
-	266,
-	278,
-	285,
-	288,
-	292,
-	293,
-	296,
-}
-
-var oneByteAtoms = [26]Atom{
-	A,
-	B,
-	0,
-	0,
-	0,
-	0,
-	0,
-	0,
-	I,
-	0,
-	0,
-	0,
-	0,
-	0,
-	0,
-	P,
-	Q,
-	0,
-	S,
-	0,
-	U,
-	0,
-	0,
-	0,
-	0,
-	0,
-}
+const atomText = "abbradiogrouparamanifestepatternavaluembedetailsampingaccept" +
+	"-charsetbodyaccesskeygenobreversedfnoscriptdirnamediagroupla" +
+	"ceholderowspanalignaltfooterubyasyncanvasidefaultitleaudiobj" +
+	"ectrackbdialogautocompletextareadonlyautofocusandboxautoplay" +
+	"baseamlesshapebdoncanplaythrough1blockquoteborderbuttonafter" +
+	"printranslateclassmallabelinkeytypecodefercolgroupostercolor" +
+	"colspannotationabortcommandlooptgroupreloadraggablegendcontr" +
+	"olsourcentercoordspellcheckedcrossoriginsrcdocitemidisabledi" +
+	"varfigcaptionbeforeprintfigurequiredfontimeupdateformactionb" +
+	"eforeunloaddressrclangformenctypemustmatchallengeformmethodf" +
+	"ormnovalidatetimeterformtargeth4h5h6heightmlowbrhgrouphidden" +
+	"high2hreflanghttp-equivideonclickindicontenteditableiframese" +
+	"timgismappletitemrefieldsetitemscopeditemtypemaxlengtheaders" +
+	"tyleminmultiplemutedonclosectionbluroncontextmenuoncuechange" +
+	"ondblclickondragendondragenterondragleaveondragoverondragsta" +
+	"rticleondropzonemptiedondurationchangeonendedonerroronfocusu" +
+	"mmaryonhashchangeoninputoninvalidonkeydownloadonkeypressupon" +
+	"keyuponloadeddatalistrongonloadedmetadatabindexonloadstarton" +
+	"messageonmousedownonmousemoveonmouseoutputonmouseoveronmouse" +
+	"uponmousewheelonofflinertononlineonpagehidelonpageshowidth3o" +
+	"npausemaponplayingonpopstateonprogressonratechangeonresetonr" +
+	"esizesonscrollonseekedonseekingonselectedonshowraponstalledo" +
+	"nstorageonsubmitempropenonsuspendonunloadonvolumechangeonwai" +
+	"tingoptimumarkoptioncancel"

File src/pkg/exp/html/atom/table_test.go

+// generated by go run gen.go -test; DO NOT EDIT
+
+package atom
+
+var testAtomList = []string{
+	"a",
+	"abbr",
+	"accept",
+	"accept-charset",
+	"accesskey",
+	"action",
+	"address",
+	"align",
+	"alt",
+	"annotation",
+	"applet",
+	"area",
+	"article",
+	"aside",
+	"async",
+	"audio",
+	"autocomplete",
+	"autofocus",