-
-
Save straight-shoota/cb903575c6dd86d1c6c86c372d842666 to your computer and use it in GitHub Desktop.
Benchmark large NamedTuple check-every-key-lookup vs. trie lookup vs. hash conversion
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| check every key 3.0 (333.07ms) (±21.04%) 20.38× slower | |
| trie lookup 33.95 ( 29.46ms) (±11.63%) 1.80× slower | |
| hash 61.19 ( 16.34ms) (±17.27%) fastest |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| COLORS = { | |
| AliceBlue: "#f0f8ff", | |
| AntiqueWhite: "#faebd7", | |
| AntiqueWhite1: "#ffefdb", | |
| AntiqueWhite2: "#eedfcc", | |
| AntiqueWhite3: "#cdc0b0", | |
| AntiqueWhite4: "#8b8378", | |
| aquamarine1: "#7fffd4", | |
| aquamarine2: "#76eec6", | |
| aquamarine4: "#458b74", | |
| azure1: "#f0ffff", | |
| azure2: "#e0eeee", | |
| azure3: "#c1cdcd", | |
| azure4: "#838b8b", | |
| beige: "#f5f5dc", | |
| bisque1: "#ffe4c4", | |
| bisque2: "#eed5b7", | |
| bisque3: "#cdb79e", | |
| bisque4: "#8b7d6b", | |
| black: "#000000", | |
| BlanchedAlmond: "#ffebcd", | |
| blue1: "#0000ff", | |
| blue2: "#0000ee", | |
| blue4: "#00008b", | |
| BlueViolet: "#8a2be2", | |
| brown: "#a52a2a", | |
| brown1: "#ff4040", | |
| brown2: "#ee3b3b", | |
| brown3: "#cd3333", | |
| brown4: "#8b2323", | |
| burlywood: "#deb887", | |
| burlywood1: "#ffd39b", | |
| burlywood2: "#eec591", | |
| burlywood3: "#cdaa7d", | |
| burlywood4: "#8b7355", | |
| CadetBlue: "#5f9ea0", | |
| CadetBlue1: "#98f5ff", | |
| CadetBlue2: "#8ee5ee", | |
| CadetBlue3: "#7ac5cd", | |
| CadetBlue4: "#53868b", | |
| chartreuse1: "#7fff00", | |
| chartreuse2: "#76ee00", | |
| chartreuse3: "#66cd00", | |
| chartreuse4: "#458b00", | |
| chocolate: "#d2691e", | |
| chocolate1: "#ff7f24", | |
| chocolate2: "#ee7621", | |
| chocolate3: "#cd661d", | |
| coral: "#ff7f50", | |
| coral1: "#ff7256", | |
| coral2: "#ee6a50", | |
| coral3: "#cd5b45", | |
| coral4: "#8b3e2f", | |
| CornflowerBlue: "#6495ed", | |
| cornsilk1: "#fff8dc", | |
| cornsilk2: "#eee8cd", | |
| cornsilk3: "#cdc8b1", | |
| cornsilk4: "#8b8878", | |
| cyan1: "#00ffff", | |
| cyan2: "#00eeee", | |
| cyan3: "#00cdcd", | |
| cyan4: "#008b8b", | |
| DarkGoldenrod: "#b8860b", | |
| DarkGoldenrod1: "#ffb90f", | |
| DarkGoldenrod2: "#eead0e", | |
| DarkGoldenrod3: "#cd950c", | |
| DarkGoldenrod4: "#8b6508", | |
| DarkGreen: "#006400", | |
| DarkKhaki: "#bdb76b", | |
| DarkOliveGreen: "#556b2f", | |
| DarkOliveGreen1: "#caff70", | |
| DarkOliveGreen2: "#bcee68", | |
| DarkOliveGreen3: "#a2cd5a", | |
| DarkOliveGreen4: "#6e8b3d", | |
| DarkOrange: "#ff8c00", | |
| DarkOrange1: "#ff7f00", | |
| DarkOrange2: "#ee7600", | |
| DarkOrange3: "#cd6600", | |
| DarkOrange4: "#8b4500", | |
| DarkOrchid: "#9932cc", | |
| DarkOrchid1: "#bf3eff", | |
| DarkOrchid2: "#b23aee", | |
| DarkOrchid3: "#9a32cd", | |
| DarkOrchid4: "#68228b", | |
| DarkSalmon: "#e9967a", | |
| DarkSeaGreen: "#8fbc8f", | |
| DarkSeaGreen1: "#c1ffc1", | |
| DarkSeaGreen2: "#b4eeb4", | |
| DarkSeaGreen3: "#9bcd9b", | |
| DarkSeaGreen4: "#698b69", | |
| DarkSlateBlue: "#483d8b", | |
| DarkSlateGray: "#2f4f4f", | |
| DarkSlateGray1: "#97ffff", | |
| DarkSlateGray2: "#8deeee", | |
| DarkSlateGray3: "#79cdcd", | |
| DarkSlateGray4: "#528b8b", | |
| DarkTurquoise: "#00ced1", | |
| DarkViolet: "#9400d3", | |
| DeepPink1: "#ff1493", | |
| DeepPink2: "#ee1289", | |
| DeepPink3: "#cd1076", | |
| DeepPink4: "#8b0a50", | |
| DeepSkyBlue1: "#00bfff", | |
| DeepSkyBlue2: "#00b2ee", | |
| DeepSkyBlue3: "#009acd", | |
| DeepSkyBlue4: "#00688b", | |
| DimGray: "#696969", | |
| DodgerBlue1: "#1e90ff", | |
| DodgerBlue2: "#1c86ee", | |
| DodgerBlue3: "#1874cd", | |
| DodgerBlue4: "#104e8b", | |
| firebrick: "#b22222", | |
| firebrick1: "#ff3030", | |
| firebrick2: "#ee2c2c", | |
| firebrick3: "#cd2626", | |
| firebrick4: "#8b1a1a", | |
| FloralWhite: "#fffaf0", | |
| ForestGreen: "#228b22", | |
| gainsboro: "#dcdcdc", | |
| GhostWhite: "#f8f8ff", | |
| gold1: "#ffd700", | |
| gold2: "#eec900", | |
| gold3: "#cdad00", | |
| gold4: "#8b7500", | |
| goldenrod: "#daa520", | |
| goldenrod1: "#ffc125", | |
| goldenrod2: "#eeb422", | |
| goldenrod3: "#cd9b1d", | |
| goldenrod4: "#8b6914", | |
| gray: "#bebebe", | |
| gray1: "#030303", | |
| gray10: "#1a1a1a", | |
| gray11: "#1c1c1c", | |
| gray12: "#1f1f1f", | |
| gray13: "#212121", | |
| gray14: "#242424", | |
| gray15: "#262626", | |
| gray16: "#292929", | |
| gray17: "#2b2b2b", | |
| gray18: "#2e2e2e", | |
| gray19: "#303030", | |
| gray2: "#050505", | |
| gray20: "#333333", | |
| gray21: "#363636", | |
| gray22: "#383838", | |
| gray23: "#3b3b3b", | |
| gray24: "#3d3d3d", | |
| gray25: "#404040", | |
| gray26: "#424242", | |
| gray27: "#454545", | |
| gray28: "#474747", | |
| gray29: "#4a4a4a", | |
| gray3: "#080808", | |
| gray30: "#4d4d4d", | |
| gray31: "#4f4f4f", | |
| gray32: "#525252", | |
| gray33: "#545454", | |
| gray34: "#575757", | |
| gray35: "#595959", | |
| gray36: "#5c5c5c", | |
| gray37: "#5e5e5e", | |
| gray38: "#616161", | |
| gray39: "#636363", | |
| gray4: "#0a0a0a", | |
| gray40: "#666666", | |
| gray41: "#696969", | |
| gray42: "#6b6b6b", | |
| gray43: "#6e6e6e", | |
| gray44: "#707070", | |
| gray45: "#737373", | |
| gray46: "#757575", | |
| gray47: "#787878", | |
| gray48: "#7a7a7a", | |
| gray49: "#7d7d7d", | |
| gray5: "#0d0d0d", | |
| gray50: "#7f7f7f", | |
| gray51: "#828282", | |
| gray52: "#858585", | |
| gray53: "#878787", | |
| gray54: "#8a8a8a", | |
| gray55: "#8c8c8c", | |
| gray56: "#8f8f8f", | |
| gray57: "#919191", | |
| gray58: "#949494", | |
| gray59: "#969696", | |
| gray6: "#0f0f0f", | |
| gray60: "#999999", | |
| gray61: "#9c9c9c", | |
| gray62: "#9e9e9e", | |
| gray63: "#a1a1a1", | |
| gray64: "#a3a3a3", | |
| gray65: "#a6a6a6", | |
| gray66: "#a8a8a8", | |
| gray67: "#ababab", | |
| gray68: "#adadad", | |
| gray69: "#b0b0b0", | |
| gray7: "#121212", | |
| gray70: "#b3b3b3", | |
| gray71: "#b5b5b5", | |
| gray72: "#b8b8b8", | |
| gray73: "#bababa", | |
| gray74: "#bdbdbd", | |
| gray75: "#bfbfbf", | |
| gray76: "#c2c2c2", | |
| gray77: "#c4c4c4", | |
| gray78: "#c7c7c7", | |
| gray79: "#c9c9c9", | |
| gray8: "#141414", | |
| gray80: "#cccccc", | |
| gray81: "#cfcfcf", | |
| gray82: "#d1d1d1", | |
| gray83: "#d4d4d4", | |
| gray84: "#d6d6d6", | |
| gray85: "#d9d9d9", | |
| gray86: "#dbdbdb", | |
| gray87: "#dedede", | |
| gray88: "#e0e0e0", | |
| gray89: "#e3e3e3", | |
| gray9: "#171717", | |
| gray90: "#e5e5e5", | |
| gray91: "#e8e8e8", | |
| gray92: "#ebebeb", | |
| gray93: "#ededed", | |
| gray94: "#f0f0f0", | |
| gray95: "#f2f2f2", | |
| gray97: "#f7f7f7", | |
| gray98: "#fafafa", | |
| gray99: "#fcfcfc", | |
| green1: "#00ff00", | |
| green2: "#00ee00", | |
| green3: "#00cd00", | |
| green4: "#008b00", | |
| GreenYellow: "#adff2f", | |
| honeydew1: "#f0fff0", | |
| honeydew2: "#e0eee0", | |
| honeydew3: "#c1cdc1", | |
| honeydew4: "#838b83", | |
| HotPink: "#ff69b4", | |
| HotPink1: "#ff6eb4", | |
| HotPink2: "#ee6aa7", | |
| HotPink3: "#cd6090", | |
| HotPink4: "#8b3a62", | |
| IndianRed: "#cd5c5c", | |
| IndianRed1: "#ff6a6a", | |
| IndianRed2: "#ee6363", | |
| IndianRed3: "#cd5555", | |
| IndianRed4: "#8b3a3a", | |
| ivory1: "#fffff0", | |
| ivory2: "#eeeee0", | |
| ivory3: "#cdcdc1", | |
| ivory4: "#8b8b83", | |
| khaki: "#f0e68c", | |
| khaki1: "#fff68f", | |
| khaki2: "#eee685", | |
| khaki3: "#cdc673", | |
| khaki4: "#8b864e", | |
| lavender: "#e6e6fa", | |
| LavenderBlush1: "#fff0f5", | |
| LavenderBlush2: "#eee0e5", | |
| LavenderBlush3: "#cdc1c5", | |
| LavenderBlush4: "#8b8386", | |
| LawnGreen: "#7cfc00", | |
| LemonChiffon1: "#fffacd", | |
| LemonChiffon2: "#eee9bf", | |
| LemonChiffon3: "#cdc9a5", | |
| LemonChiffon4: "#8b8970", | |
| light: "#eedd82", | |
| LightBlue: "#add8e6", | |
| LightBlue1: "#bfefff", | |
| LightBlue2: "#b2dfee", | |
| LightBlue3: "#9ac0cd", | |
| LightBlue4: "#68838b", | |
| LightCoral: "#f08080", | |
| LightCyan1: "#e0ffff", | |
| LightCyan2: "#d1eeee", | |
| LightCyan3: "#b4cdcd", | |
| LightCyan4: "#7a8b8b", | |
| LightGoldenrod1: "#ffec8b", | |
| LightGoldenrod2: "#eedc82", | |
| LightGoldenrod3: "#cdbe70", | |
| LightGoldenrod4: "#8b814c", | |
| LightGoldenrodYellow: "#fafad2", | |
| LightGray: "#d3d3d3", | |
| LightPink: "#ffb6c1", | |
| LightPink1: "#ffaeb9", | |
| LightPink2: "#eea2ad", | |
| LightPink3: "#cd8c95", | |
| LightPink4: "#8b5f65", | |
| LightSalmon1: "#ffa07a", | |
| LightSalmon2: "#ee9572", | |
| LightSalmon3: "#cd8162", | |
| LightSalmon4: "#8b5742", | |
| LightSeaGreen: "#20b2aa", | |
| LightSkyBlue: "#87cefa", | |
| LightSkyBlue1: "#b0e2ff", | |
| LightSkyBlue2: "#a4d3ee", | |
| LightSkyBlue3: "#8db6cd", | |
| LightSkyBlue4: "#607b8b", | |
| LightSlateBlue: "#8470ff", | |
| LightSlateGray: "#778899", | |
| } | |
| struct NamedTuple(T) | |
| macro fetch_trie_expand(keys, index, size) | |
| {% if keys.size < 16 %} | |
| {% for key in keys %} | |
| return self[{{key}}] if {{key}} == key | |
| {% end %} | |
| {% else %} | |
| {% chars = keys.map {|key| key.chars[index] }.uniq %} | |
| case key[{{index}}] | |
| {% for char in chars %} | |
| when {{char}} | |
| {% subkeys = keys.select {|key| key.chars[index] == char } %} | |
| {% if index+1 == size %} | |
| {% ans = subkeys[0] %} | |
| {% if ans %} | |
| return self[{{ans.id.symbolize}}] | |
| {% end %} | |
| {% else %} | |
| fetch_trie_expand({{subkeys}}, {{index+1}}, {{size}}) | |
| {% end %} | |
| {% end %} | |
| end | |
| {% end %} | |
| end | |
| def fetch1(key : String, &block) | |
| {% for key in T %} | |
| return self[{{key.symbolize}}] if {{key.stringify}} == key | |
| {% end %} | |
| yield | |
| end | |
| def fetch2(key : String, &block) | |
| {% begin %} | |
| {% keys = T.keys.map(&.stringify) %} | |
| {% sizes = keys.map(&.size).uniq %} | |
| case key.size | |
| {% for size in sizes %} | |
| when {{size}} | |
| fetch_trie_expand({{ keys.select {|key| key.size == size} }}, 0, {{size}}) | |
| {% end %} | |
| end | |
| {% end %} | |
| yield | |
| end | |
| end | |
| require "benchmark" | |
| HASH = COLORS.to_h.map{|k,v| {k.to_s, v}}.to_h | |
| keys = {{COLORS.keys.map(&.stringify)}} | |
| glob = "" | |
| Benchmark.ips do |x| | |
| x.report("check every key") do | |
| keys.each {|key| 1000.times {glob = COLORS.fetch1(key) {nil}}} | |
| end | |
| x.report("trie lookup") do | |
| keys.each {|key| 1000.times {glob = COLORS.fetch2(key) {nil}}} | |
| end | |
| x.report("hash") do | |
| keys.each {|key| 1000.times {glob = HASH.fetch(key) {nil}}} | |
| end | |
| end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment