Skip to content

Instantly share code, notes, and snippets.

@straight-shoota

straight-shoota/result.txt

Forked from lbguilherme/result.txt
Last active June 28, 2017 17:53
Show Gist options
  • Save straight-shoota/cb903575c6dd86d1c6c86c372d842666 to your computer and use it in GitHub Desktop.
Save straight-shoota/cb903575c6dd86d1c6c86c372d842666 to your computer and use it in GitHub Desktop.
Download ZIP
Benchmark large NamedTuple check-every-key-lookup vs. trie lookup vs. hash conversion
Raw
result.txt
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
Raw
test.cr
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