From 3824f52e52ef95342788042a69e142e2aef72243 Mon Sep 17 00:00:00 2001 From: zeertzjq Date: Fri, 7 Mar 2025 13:07:50 +0800 Subject: refactor(keycodes): generate key_names_table[] using Lua This allows easier refactoring. --- src/gen/gen_keycodes.lua | 19 +++++ src/nvim/CMakeLists.txt | 8 ++ src/nvim/keycodes.c | 209 +---------------------------------------------- src/nvim/keycodes.lua | 206 ++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 234 insertions(+), 208 deletions(-) create mode 100644 src/gen/gen_keycodes.lua create mode 100644 src/nvim/keycodes.lua diff --git a/src/gen/gen_keycodes.lua b/src/gen/gen_keycodes.lua new file mode 100644 index 0000000000..fff5b59396 --- /dev/null +++ b/src/gen/gen_keycodes.lua @@ -0,0 +1,19 @@ +local names_file = arg[1] + +local keycodes = require('nvim.keycodes') +local keycode_names = keycodes.names + +local names_tgt = assert(io.open(names_file, 'w')) + +names_tgt:write([[ +static const struct key_name_entry { + int key; ///< Special key code or ascii value + const char *name; ///< Name of key +} key_names_table[] = {]]) + +for _, keycode in ipairs(keycode_names) do + names_tgt:write(('\n {%s, "%s"},'):format(keycode[1], keycode[2])) +end + +names_tgt:write('\n {0, NULL},\n};\n') +names_tgt:close() diff --git a/src/nvim/CMakeLists.txt b/src/nvim/CMakeLists.txt index 36bcd5fbce..39c78b3228 100644 --- a/src/nvim/CMakeLists.txt +++ b/src/nvim/CMakeLists.txt @@ -304,6 +304,7 @@ set(CHAR_BLOB_GENERATOR ${GENERATOR_DIR}/gen_char_blob.lua) set(EVENTS_GENERATOR ${GENERATOR_DIR}/gen_events.lua) set(EX_CMDS_GENERATOR ${GENERATOR_DIR}/gen_ex_cmds.lua) set(FUNCS_GENERATOR ${GENERATOR_DIR}/gen_eval.lua) +set(KEYCODES_GENERATOR ${GENERATOR_DIR}/gen_keycodes.lua) set(GENERATOR_C_GRAMMAR ${GENERATOR_DIR}/c_grammar.lua) set(GENERATOR_HASHY ${GENERATOR_DIR}/hashy.lua) set(GENERATOR_PRELOAD ${GENERATOR_DIR}/preload_nlua.lua) @@ -318,6 +319,7 @@ set(GENERATED_EVENTS_NAMES_MAP ${GENERATED_DIR}/auevents_name_map.generated.h) set(GENERATED_EX_CMDS_DEFS ${GENERATED_DIR}/ex_cmds_defs.generated.h) set(GENERATED_EX_CMDS_ENUM ${GENERATED_INCLUDES_DIR}/ex_cmds_enum.generated.h) set(GENERATED_FUNCS ${GENERATED_DIR}/funcs.generated.h) +set(GENERATED_KEYCODE_NAMES ${GENERATED_DIR}/keycode_names.generated.h) set(GENERATED_API_METADATA ${GENERATED_DIR}/api/private/api_metadata.generated.h) set(GENERATED_KEYSETS_DEFS ${GENERATED_DIR}/keysets_defs.generated.h) set(GENERATED_OPTIONS ${GENERATED_DIR}/options.generated.h) @@ -673,6 +675,7 @@ list(APPEND NVIM_GENERATED_FOR_SOURCES "${GENERATED_API_DISPATCH}" "${GENERATED_EX_CMDS_DEFS}" "${GENERATED_EVENTS_NAMES_MAP}" + "${GENERATED_KEYCODE_NAMES}" "${GENERATED_OPTIONS}" "${GENERATED_OPTIONS_MAP}" "${VIM_MODULE_FILE}" @@ -696,6 +699,11 @@ add_custom_command(OUTPUT ${GENERATED_EVENTS_ENUM} ${GENERATED_EVENTS_NAMES_MAP} DEPENDS ${LUA_GEN_DEPS} ${EVENTS_GENERATOR} ${CMAKE_CURRENT_LIST_DIR}/auevents.lua ) +add_custom_command(OUTPUT ${GENERATED_KEYCODE_NAMES} + COMMAND ${LUA_GEN} ${KEYCODES_GENERATOR} ${GENERATED_KEYCODE_NAMES} + DEPENDS ${LUA_GEN_DEPS} ${KEYCODES_GENERATOR} ${CMAKE_CURRENT_LIST_DIR}/keycodes.lua +) + add_custom_command(OUTPUT ${GENERATED_OPTIONS} ${GENERATED_OPTIONS_ENUM} ${GENERATED_OPTIONS_MAP} ${GENERATED_OPTION_VARS} COMMAND ${LUA_GEN} ${OPTIONS_GENERATOR} ${GENERATED_OPTIONS} ${GENERATED_OPTIONS_ENUM} ${GENERATED_OPTIONS_MAP} ${GENERATED_OPTION_VARS} DEPENDS ${LUA_GEN_DEPS} ${OPTIONS_GENERATOR} ${CMAKE_CURRENT_LIST_DIR}/options.lua diff --git a/src/nvim/keycodes.c b/src/nvim/keycodes.c index b6ba73f7c1..ff5b036817 100644 --- a/src/nvim/keycodes.c +++ b/src/nvim/keycodes.c @@ -24,6 +24,7 @@ #include "nvim/strings.h" #ifdef INCLUDE_GENERATED_DECLARATIONS +# include "keycode_names.generated.h" # include "keycodes.c.generated.h" #endif @@ -142,214 +143,6 @@ static uint8_t modifier_keys_table[] = { NUL }; -static const struct key_name_entry { - int key; // Special key code or ascii value - const char *name; // Name of key -} key_names_table[] = { - { ' ', "Space" }, - { TAB, "Tab" }, - { K_TAB, "Tab" }, - { NL, "NL" }, - { NL, "NewLine" }, // Alternative name - { NL, "LineFeed" }, // Alternative name - { NL, "LF" }, // Alternative name - { CAR, "CR" }, - { CAR, "Return" }, // Alternative name - { CAR, "Enter" }, // Alternative name - { K_BS, "BS" }, - { K_BS, "BackSpace" }, // Alternative name - { ESC, "Esc" }, - { ESC, "Escape" }, // Alternative name - { CSI, "CSI" }, - { '|', "Bar" }, - { '\\', "Bslash" }, - { K_DEL, "Del" }, - { K_DEL, "Delete" }, // Alternative name - { K_KDEL, "kDel" }, - { K_KDEL, "KPPeriod" }, // libtermkey name - { K_UP, "Up" }, - { K_DOWN, "Down" }, - { K_LEFT, "Left" }, - { K_RIGHT, "Right" }, - { K_XUP, "xUp" }, - { K_XDOWN, "xDown" }, - { K_XLEFT, "xLeft" }, - { K_XRIGHT, "xRight" }, - { K_KUP, "kUp" }, - { K_KUP, "KP8" }, - { K_KDOWN, "kDown" }, - { K_KDOWN, "KP2" }, - { K_KLEFT, "kLeft" }, - { K_KLEFT, "KP4" }, - { K_KRIGHT, "kRight" }, - { K_KRIGHT, "KP6" }, - - { K_F1, "F1" }, - { K_F2, "F2" }, - { K_F3, "F3" }, - { K_F4, "F4" }, - { K_F5, "F5" }, - { K_F6, "F6" }, - { K_F7, "F7" }, - { K_F8, "F8" }, - { K_F9, "F9" }, - { K_F10, "F10" }, - - { K_F11, "F11" }, - { K_F12, "F12" }, - { K_F13, "F13" }, - { K_F14, "F14" }, - { K_F15, "F15" }, - { K_F16, "F16" }, - { K_F17, "F17" }, - { K_F18, "F18" }, - { K_F19, "F19" }, - { K_F20, "F20" }, - - { K_F21, "F21" }, - { K_F22, "F22" }, - { K_F23, "F23" }, - { K_F24, "F24" }, - { K_F25, "F25" }, - { K_F26, "F26" }, - { K_F27, "F27" }, - { K_F28, "F28" }, - { K_F29, "F29" }, - { K_F30, "F30" }, - - { K_F31, "F31" }, - { K_F32, "F32" }, - { K_F33, "F33" }, - { K_F34, "F34" }, - { K_F35, "F35" }, - { K_F36, "F36" }, - { K_F37, "F37" }, - { K_F38, "F38" }, - { K_F39, "F39" }, - { K_F40, "F40" }, - - { K_F41, "F41" }, - { K_F42, "F42" }, - { K_F43, "F43" }, - { K_F44, "F44" }, - { K_F45, "F45" }, - { K_F46, "F46" }, - { K_F47, "F47" }, - { K_F48, "F48" }, - { K_F49, "F49" }, - { K_F50, "F50" }, - - { K_F51, "F51" }, - { K_F52, "F52" }, - { K_F53, "F53" }, - { K_F54, "F54" }, - { K_F55, "F55" }, - { K_F56, "F56" }, - { K_F57, "F57" }, - { K_F58, "F58" }, - { K_F59, "F59" }, - { K_F60, "F60" }, - - { K_F61, "F61" }, - { K_F62, "F62" }, - { K_F63, "F63" }, - - { K_XF1, "xF1" }, - { K_XF2, "xF2" }, - { K_XF3, "xF3" }, - { K_XF4, "xF4" }, - - { K_HELP, "Help" }, - { K_UNDO, "Undo" }, - { K_FIND, "Find" }, // DEC key, often used as 'Home' - { K_KSELECT, "Select" }, // DEC key, often used as 'End' - { K_INS, "Insert" }, - { K_INS, "Ins" }, // Alternative name - { K_KINS, "kInsert" }, - { K_KINS, "KP0" }, - { K_HOME, "Home" }, - { K_KHOME, "kHome" }, - { K_KHOME, "KP7" }, - { K_XHOME, "xHome" }, - { K_ZHOME, "zHome" }, - { K_END, "End" }, - { K_KEND, "kEnd" }, - { K_KEND, "KP1" }, - { K_XEND, "xEnd" }, - { K_ZEND, "zEnd" }, - { K_PAGEUP, "PageUp" }, - { K_PAGEDOWN, "PageDown" }, - { K_KPAGEUP, "kPageUp" }, - { K_KPAGEUP, "KP9" }, - { K_KPAGEDOWN, "kPageDown" }, - { K_KPAGEDOWN, "KP3" }, - { K_KORIGIN, "kOrigin" }, - { K_KORIGIN, "KP5" }, - - { K_KPLUS, "kPlus" }, - { K_KPLUS, "KPPlus" }, - { K_KMINUS, "kMinus" }, - { K_KMINUS, "KPMinus" }, - { K_KDIVIDE, "kDivide" }, - { K_KDIVIDE, "KPDiv" }, - { K_KMULTIPLY, "kMultiply" }, - { K_KMULTIPLY, "KPMult" }, - { K_KENTER, "kEnter" }, - { K_KENTER, "KPEnter" }, - { K_KPOINT, "kPoint" }, - { K_KCOMMA, "kComma" }, - { K_KCOMMA, "KPComma" }, - { K_KEQUAL, "kEqual" }, - { K_KEQUAL, "KPEquals" }, - - { K_K0, "k0" }, - { K_K1, "k1" }, - { K_K2, "k2" }, - { K_K3, "k3" }, - { K_K4, "k4" }, - { K_K5, "k5" }, - { K_K6, "k6" }, - { K_K7, "k7" }, - { K_K8, "k8" }, - { K_K9, "k9" }, - - { '<', "lt" }, - - { K_MOUSE, "Mouse" }, - { K_LEFTMOUSE, "LeftMouse" }, - { K_LEFTMOUSE_NM, "LeftMouseNM" }, - { K_LEFTDRAG, "LeftDrag" }, - { K_LEFTRELEASE, "LeftRelease" }, - { K_LEFTRELEASE_NM, "LeftReleaseNM" }, - { K_MOUSEMOVE, "MouseMove" }, - { K_MIDDLEMOUSE, "MiddleMouse" }, - { K_MIDDLEDRAG, "MiddleDrag" }, - { K_MIDDLERELEASE, "MiddleRelease" }, - { K_RIGHTMOUSE, "RightMouse" }, - { K_RIGHTDRAG, "RightDrag" }, - { K_RIGHTRELEASE, "RightRelease" }, - { K_MOUSEDOWN, "ScrollWheelUp" }, - { K_MOUSEUP, "ScrollWheelDown" }, - { K_MOUSELEFT, "ScrollWheelRight" }, - { K_MOUSERIGHT, "ScrollWheelLeft" }, - { K_MOUSEDOWN, "MouseDown" }, // OBSOLETE: Use - { K_MOUSEUP, "MouseUp" }, // ScrollWheelXXX instead - { K_X1MOUSE, "X1Mouse" }, - { K_X1DRAG, "X1Drag" }, - { K_X1RELEASE, "X1Release" }, - { K_X2MOUSE, "X2Mouse" }, - { K_X2DRAG, "X2Drag" }, - { K_X2RELEASE, "X2Release" }, - { K_DROP, "Drop" }, - { K_ZERO, "Nul" }, - { K_SNR, "SNR" }, - { K_PLUG, "Plug" }, - { K_IGNORE, "Ignore" }, - { K_COMMAND, "Cmd" }, - { 0, NULL } - // NOTE: When adding a long name update MAX_KEY_NAME_LEN. -}; - static struct mousetable { int pseudo_code; // Code for pseudo mouse event int button; // Which mouse button is it? diff --git a/src/nvim/keycodes.lua b/src/nvim/keycodes.lua new file mode 100644 index 0000000000..c6158b0b84 --- /dev/null +++ b/src/nvim/keycodes.lua @@ -0,0 +1,206 @@ +return { + --- @type [string, string][] List of [key, name] tuples. + names = { + { [[' ']], 'Space' }, + { [[TAB]], 'Tab' }, + { [[K_TAB]], 'Tab' }, + { [[NL]], 'NL' }, + { [[NL]], 'NewLine' }, -- Alternative name + { [[NL]], 'LineFeed' }, -- Alternative name + { [[NL]], 'LF' }, -- Alternative name + { [[CAR]], 'CR' }, + { [[CAR]], 'Return' }, -- Alternative name + { [[CAR]], 'Enter' }, -- Alternative name + { [[K_BS]], 'BS' }, + { [[K_BS]], 'BackSpace' }, -- Alternative name + { [[ESC]], 'Esc' }, + { [[ESC]], 'Escape' }, -- Alternative name + { [[CSI]], 'CSI' }, + { [['|']], 'Bar' }, + { [['\\']], 'Bslash' }, + { [[K_DEL]], 'Del' }, + { [[K_DEL]], 'Delete' }, -- Alternative name + { [[K_KDEL]], 'kDel' }, + { [[K_KDEL]], 'KPPeriod' }, -- libtermkey name + { [[K_UP]], 'Up' }, + { [[K_DOWN]], 'Down' }, + { [[K_LEFT]], 'Left' }, + { [[K_RIGHT]], 'Right' }, + { [[K_XUP]], 'xUp' }, + { [[K_XDOWN]], 'xDown' }, + { [[K_XLEFT]], 'xLeft' }, + { [[K_XRIGHT]], 'xRight' }, + { [[K_KUP]], 'kUp' }, + { [[K_KUP]], 'KP8' }, + { [[K_KDOWN]], 'kDown' }, + { [[K_KDOWN]], 'KP2' }, + { [[K_KLEFT]], 'kLeft' }, + { [[K_KLEFT]], 'KP4' }, + { [[K_KRIGHT]], 'kRight' }, + { [[K_KRIGHT]], 'KP6' }, + + { [[K_F1]], 'F1' }, + { [[K_F2]], 'F2' }, + { [[K_F3]], 'F3' }, + { [[K_F4]], 'F4' }, + { [[K_F5]], 'F5' }, + { [[K_F6]], 'F6' }, + { [[K_F7]], 'F7' }, + { [[K_F8]], 'F8' }, + { [[K_F9]], 'F9' }, + { [[K_F10]], 'F10' }, + + { [[K_F11]], 'F11' }, + { [[K_F12]], 'F12' }, + { [[K_F13]], 'F13' }, + { [[K_F14]], 'F14' }, + { [[K_F15]], 'F15' }, + { [[K_F16]], 'F16' }, + { [[K_F17]], 'F17' }, + { [[K_F18]], 'F18' }, + { [[K_F19]], 'F19' }, + { [[K_F20]], 'F20' }, + + { [[K_F21]], 'F21' }, + { [[K_F22]], 'F22' }, + { [[K_F23]], 'F23' }, + { [[K_F24]], 'F24' }, + { [[K_F25]], 'F25' }, + { [[K_F26]], 'F26' }, + { [[K_F27]], 'F27' }, + { [[K_F28]], 'F28' }, + { [[K_F29]], 'F29' }, + { [[K_F30]], 'F30' }, + + { [[K_F31]], 'F31' }, + { [[K_F32]], 'F32' }, + { [[K_F33]], 'F33' }, + { [[K_F34]], 'F34' }, + { [[K_F35]], 'F35' }, + { [[K_F36]], 'F36' }, + { [[K_F37]], 'F37' }, + { [[K_F38]], 'F38' }, + { [[K_F39]], 'F39' }, + { [[K_F40]], 'F40' }, + + { [[K_F41]], 'F41' }, + { [[K_F42]], 'F42' }, + { [[K_F43]], 'F43' }, + { [[K_F44]], 'F44' }, + { [[K_F45]], 'F45' }, + { [[K_F46]], 'F46' }, + { [[K_F47]], 'F47' }, + { [[K_F48]], 'F48' }, + { [[K_F49]], 'F49' }, + { [[K_F50]], 'F50' }, + + { [[K_F51]], 'F51' }, + { [[K_F52]], 'F52' }, + { [[K_F53]], 'F53' }, + { [[K_F54]], 'F54' }, + { [[K_F55]], 'F55' }, + { [[K_F56]], 'F56' }, + { [[K_F57]], 'F57' }, + { [[K_F58]], 'F58' }, + { [[K_F59]], 'F59' }, + { [[K_F60]], 'F60' }, + + { [[K_F61]], 'F61' }, + { [[K_F62]], 'F62' }, + { [[K_F63]], 'F63' }, + + { [[K_XF1]], 'xF1' }, + { [[K_XF2]], 'xF2' }, + { [[K_XF3]], 'xF3' }, + { [[K_XF4]], 'xF4' }, + + { [[K_HELP]], 'Help' }, + { [[K_UNDO]], 'Undo' }, + { [[K_FIND]], 'Find' }, -- DEC key, often used as 'Home' + { [[K_KSELECT]], 'Select' }, -- DEC key, often used as 'End' + { [[K_INS]], 'Insert' }, + { [[K_INS]], 'Ins' }, -- Alternative name + { [[K_KINS]], 'kInsert' }, + { [[K_KINS]], 'KP0' }, + { [[K_HOME]], 'Home' }, + { [[K_KHOME]], 'kHome' }, + { [[K_KHOME]], 'KP7' }, + { [[K_XHOME]], 'xHome' }, + { [[K_ZHOME]], 'zHome' }, + { [[K_END]], 'End' }, + { [[K_KEND]], 'kEnd' }, + { [[K_KEND]], 'KP1' }, + { [[K_XEND]], 'xEnd' }, + { [[K_ZEND]], 'zEnd' }, + { [[K_PAGEUP]], 'PageUp' }, + { [[K_PAGEDOWN]], 'PageDown' }, + { [[K_KPAGEUP]], 'kPageUp' }, + { [[K_KPAGEUP]], 'KP9' }, + { [[K_KPAGEDOWN]], 'kPageDown' }, + { [[K_KPAGEDOWN]], 'KP3' }, + { [[K_KORIGIN]], 'kOrigin' }, + { [[K_KORIGIN]], 'KP5' }, + + { [[K_KPLUS]], 'kPlus' }, + { [[K_KPLUS]], 'KPPlus' }, + { [[K_KMINUS]], 'kMinus' }, + { [[K_KMINUS]], 'KPMinus' }, + { [[K_KDIVIDE]], 'kDivide' }, + { [[K_KDIVIDE]], 'KPDiv' }, + { [[K_KMULTIPLY]], 'kMultiply' }, + { [[K_KMULTIPLY]], 'KPMult' }, + { [[K_KENTER]], 'kEnter' }, + { [[K_KENTER]], 'KPEnter' }, + { [[K_KPOINT]], 'kPoint' }, + { [[K_KCOMMA]], 'kComma' }, + { [[K_KCOMMA]], 'KPComma' }, + { [[K_KEQUAL]], 'kEqual' }, + { [[K_KEQUAL]], 'KPEquals' }, + + { [[K_K0]], 'k0' }, + { [[K_K1]], 'k1' }, + { [[K_K2]], 'k2' }, + { [[K_K3]], 'k3' }, + { [[K_K4]], 'k4' }, + { [[K_K5]], 'k5' }, + { [[K_K6]], 'k6' }, + { [[K_K7]], 'k7' }, + { [[K_K8]], 'k8' }, + { [[K_K9]], 'k9' }, + + { [['<']], 'lt' }, + + { [[K_MOUSE]], 'Mouse' }, + { [[K_LEFTMOUSE]], 'LeftMouse' }, + { [[K_LEFTMOUSE_NM]], 'LeftMouseNM' }, + { [[K_LEFTDRAG]], 'LeftDrag' }, + { [[K_LEFTRELEASE]], 'LeftRelease' }, + { [[K_LEFTRELEASE_NM]], 'LeftReleaseNM' }, + { [[K_MOUSEMOVE]], 'MouseMove' }, + { [[K_MIDDLEMOUSE]], 'MiddleMouse' }, + { [[K_MIDDLEDRAG]], 'MiddleDrag' }, + { [[K_MIDDLERELEASE]], 'MiddleRelease' }, + { [[K_RIGHTMOUSE]], 'RightMouse' }, + { [[K_RIGHTDRAG]], 'RightDrag' }, + { [[K_RIGHTRELEASE]], 'RightRelease' }, + { [[K_MOUSEDOWN]], 'ScrollWheelUp' }, + { [[K_MOUSEUP]], 'ScrollWheelDown' }, + { [[K_MOUSELEFT]], 'ScrollWheelRight' }, + { [[K_MOUSERIGHT]], 'ScrollWheelLeft' }, + { [[K_MOUSEDOWN]], 'MouseDown' }, -- OBSOLETE: Use ScrollWheelUp instead + { [[K_MOUSEUP]], 'MouseUp' }, -- OBSOLETE: Use ScrollWheelDown instead + { [[K_X1MOUSE]], 'X1Mouse' }, + { [[K_X1DRAG]], 'X1Drag' }, + { [[K_X1RELEASE]], 'X1Release' }, + { [[K_X2MOUSE]], 'X2Mouse' }, + { [[K_X2DRAG]], 'X2Drag' }, + { [[K_X2RELEASE]], 'X2Release' }, + { [[K_DROP]], 'Drop' }, + { [[K_ZERO]], 'Nul' }, + { [[K_SNR]], 'SNR' }, + { [[K_PLUG]], 'Plug' }, + { [[K_IGNORE]], 'Ignore' }, + { [[K_COMMAND]], 'Cmd' }, + -- NOTE: When adding a long name update MAX_KEY_NAME_LEN. + }, +} -- cgit From 08d12b57ad831c56931e3a8d63072dabfbf6c5ab Mon Sep 17 00:00:00 2001 From: zeertzjq Date: Fri, 7 Mar 2025 14:17:40 +0800 Subject: test: add benchmark for nvim_replace_termcodes and keytrans() --- test/benchmark/keycodes_spec.lua | 84 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 84 insertions(+) create mode 100644 test/benchmark/keycodes_spec.lua diff --git a/test/benchmark/keycodes_spec.lua b/test/benchmark/keycodes_spec.lua new file mode 100644 index 0000000000..443df2a6fb --- /dev/null +++ b/test/benchmark/keycodes_spec.lua @@ -0,0 +1,84 @@ +local n = require('test.functional.testnvim')() +local clear = n.clear +local api = n.api +local fn = n.fn + +local keycodes = require('src.nvim.keycodes') + +describe('nvim_replace_termcodes performance', function() + it('200 calls with a key repeated 5000 times', function() + clear() + local stats = {} + local sum = 0 + local ms = 1 / 1000000 + + for _, keycode in ipairs(keycodes.names) do + local notation = ('<%s>'):format(keycode[2]) + local str = notation:rep(5000) + + local start = vim.uv.hrtime() + for _ = 1, 200 do + api.nvim_replace_termcodes(str, false, true, true) + end + local elapsed = vim.uv.hrtime() - start + + table.insert(stats, elapsed) + sum = sum + elapsed + io.stdout:write(('\n%-20s%14.6f ms'):format(notation, elapsed * ms)) + io.stdout:flush() + end + io.stdout:write('\n') + + table.sort(stats) + print(('%18s'):rep(6):format('avg', 'min', '25%', 'median', '75%', 'max')) + print( + (' %14.6f ms'):rep(6):format( + sum / #stats * ms, + stats[1] * ms, + stats[1 + math.floor(#stats * 0.25)] * ms, + stats[1 + math.floor(#stats * 0.5)] * ms, + stats[1 + math.floor(#stats * 0.75)] * ms, + stats[#stats] * ms + ) + ) + end) +end) + +describe('keytrans() performance', function() + it('200 calls with a key repeated 5000 times', function() + clear() + local stats = {} + local sum = 0 + local ms = 1 / 1000000 + + for _, keycode in ipairs(keycodes.names) do + local notation = ('<%s>'):format(keycode[2]) + local str = api.nvim_replace_termcodes(notation, false, true, true):rep(5000) + + local start = vim.uv.hrtime() + for _ = 1, 200 do + fn.keytrans(str) + end + local elapsed = vim.uv.hrtime() - start + + table.insert(stats, elapsed) + sum = sum + elapsed + io.stdout:write(('\n%-20s%14.6f ms'):format(notation, elapsed * ms)) + io.stdout:flush() + end + io.stdout:write('\n') + + table.sort(stats) + print((' %17s'):rep(6):format('avg', 'min', '25%', 'median', '75%', 'max')) + print( + (' %14.6f ms'):rep(6):format( + sum / #stats * ms, + stats[1] * ms, + stats[1 + math.floor(#stats * 0.25)] * ms, + stats[1 + math.floor(#stats * 0.5)] * ms, + stats[1 + math.floor(#stats * 0.75)] * ms, + stats[#stats] * ms + ) + ) + end) +end) -- cgit From af42f79221af793adeb8c2552463a87ddde08a7e Mon Sep 17 00:00:00 2001 From: zeertzjq Date: Fri, 7 Mar 2025 11:11:47 +0800 Subject: vim-patch:partial:9.1.1179: too many strlen() calls in misc2.c Problem: too many strlen() calls in misc2.c Solution: refactor misc2.c and use bsearch() instead of a linear search to find matches in the key_names_table array (John Marriott). This commit changes misc2.c to use bsearch() to perform string searches of the key_names_table array. Implementation detail: - Some entries in this array have alternate names. Add field alt_name to point to the alternate name. - Some entries in this array are only available if a given feature is defined. Keep them in the array, but add a boolean field enabled to indicate if the record can be used or not. If the feature is not available, the corresponding enabled field is set to FALSE. In my measurements running the test suite on a huge non-gui build on linux, the number of string comparisons in get_special_key_code(): Before (linear search): 2,214,957 After (binary search): 297,770 A side effect of this is 1477 calls to STRLEN() in get_special_key_name() for the same test run are no longer necessary. closes: vim/vim#16788 https://github.com/vim/vim/commit/4a1e6dacbb2cc833353983bea7eac38191c9d3b4 Skip the mouse shape changes. Co-authored-by: John Marriott --- src/gen/gen_keycodes.lua | 42 ++++++++++++++++++++++---- src/nvim/keycodes.c | 77 +++++++++++++++++++++++++++++++++++------------- 2 files changed, 92 insertions(+), 27 deletions(-) diff --git a/src/gen/gen_keycodes.lua b/src/gen/gen_keycodes.lua index fff5b59396..118eac2579 100644 --- a/src/gen/gen_keycodes.lua +++ b/src/gen/gen_keycodes.lua @@ -1,19 +1,49 @@ local names_file = arg[1] local keycodes = require('nvim.keycodes') -local keycode_names = keycodes.names local names_tgt = assert(io.open(names_file, 'w')) +--- @type [string, string, integer][] +local keycode_names = {} +for i, keycode in ipairs(keycodes.names) do + table.insert(keycode_names, { keycode[1], keycode[2], i }) +end +table.sort(keycode_names, function(keycode_a, keycode_b) + return keycode_a[2]:lower() < keycode_b[2]:lower() +end) + +--- @type table +local alt_name_idx = {} +for i, keycode in ipairs(keycode_names) do + local key = keycode[1] + local alt_idx = alt_name_idx[key] + if alt_idx == nil or keycode_names[alt_idx][3] > keycode[3] then + alt_name_idx[key] = i + end +end + names_tgt:write([[ static const struct key_name_entry { - int key; ///< Special key code or ascii value - const char *name; ///< Name of key + int key; ///< Special key code or ascii value + String name; ///< Name of key + const String *alt_name; ///< Pointer to alternative key name + ///< (may be NULL or point to the name in another entry) } key_names_table[] = {]]) -for _, keycode in ipairs(keycode_names) do - names_tgt:write(('\n {%s, "%s"},'):format(keycode[1], keycode[2])) +for i, keycode in ipairs(keycode_names) do + local key = keycode[1] + local name = keycode[2] + local alt_idx = alt_name_idx[key] + names_tgt:write( + ('\n {%s, {"%s", %d}, %s},'):format( + key, + name, + #name, + alt_idx == i and 'NULL' or ('&key_names_table[%d].name'):format(alt_idx - 1) + ) + ) end -names_tgt:write('\n {0, NULL},\n};\n') +names_tgt:write('\n};\n') names_tgt:close() diff --git a/src/nvim/keycodes.c b/src/nvim/keycodes.c index ff5b036817..5ab6a718ef 100644 --- a/src/nvim/keycodes.c +++ b/src/nvim/keycodes.c @@ -6,6 +6,7 @@ #include #include +#include "nvim/api/private/defs.h" #include "nvim/ascii_defs.h" #include "nvim/charset.h" #include "nvim/errors.h" @@ -337,15 +338,18 @@ char *get_special_key_name(int c, int modifiers) } } } else { // use name of special key - size_t len = strlen(key_names_table[table_idx].name); + const String *s = key_names_table[table_idx].alt_name != NULL + ? key_names_table[table_idx].alt_name + : &key_names_table[table_idx].name; - if ((int)len + idx + 2 <= MAX_KEY_NAME_LEN) { - STRCPY(string + idx, key_names_table[table_idx].name); - idx += (int)len; + if ((int)s->size + idx + 2 <= MAX_KEY_NAME_LEN) { + STRCPY(string + idx, s->data); + idx += (int)s->size; } } string[idx++] = '>'; string[idx] = NUL; + return string; } @@ -588,17 +592,51 @@ static int extract_modifiers(int key, int *modp, const bool simplify, bool *cons /// @return the index when found, -1 when not found. int find_special_key_in_table(int c) { - int i; - - for (i = 0; key_names_table[i].name != NULL; i++) { + for (int i = 0; i < (int)ARRAY_SIZE(key_names_table); i++) { if (c == key_names_table[i].key) { + return i; + } + } + + return -1; +} + +/// Compare two 'struct key_name_entry' structures. +/// Note that the target string (p1) may contain additional trailing characters +/// that should not factor into the comparison. Example: +/// 'LeftMouse>", ""] ...' +/// should match with +/// 'LeftMouse'. +/// These characters are identified by ascii_isident(). +static int cmp_key_name_entry(const void *a, const void *b) +{ + const char *p1 = ((struct key_name_entry *)a)->name.data; + const char *p2 = ((struct key_name_entry *)b)->name.data; + int result = 0; + + if (p1 == p2) { + return 0; + } + + while (ascii_isident(*p1) && *p2 != NUL) { + if ((result = TOLOWER_ASC(*p1) - TOLOWER_ASC(*p2)) != 0) { break; } + p1++; + p2++; } - if (key_names_table[i].name == NULL) { - i = -1; + + if (result == 0) { + if (*p2 == NUL) { + if (ascii_isident(*p1)) { + result = 1; + } + } else { + result = -1; + } } - return i; + + return result; } /// Find the special key with the given name @@ -616,17 +654,14 @@ int get_special_key_code(const char *name) return TERMCAP2KEY((uint8_t)name[2], (uint8_t)name[3]); } - for (int i = 0; key_names_table[i].name != NULL; i++) { - const char *const table_name = key_names_table[i].name; - int j; - for (j = 0; ascii_isident((uint8_t)name[j]) && table_name[j] != NUL; j++) { - if (TOLOWER_ASC(table_name[j]) != TOLOWER_ASC((uint8_t)name[j])) { - break; - } - } - if (!ascii_isident((uint8_t)name[j]) && table_name[j] == NUL) { - return key_names_table[i].key; - } + struct key_name_entry target = { .name.data = (char *)name }; + struct key_name_entry *entry = bsearch(&target, + &key_names_table, + ARRAY_SIZE(key_names_table), + sizeof(key_names_table[0]), + cmp_key_name_entry); + if (entry != NULL) { + return entry->key; } return 0; -- cgit From 12d4caa9d3e4224b7c2922f112955100649d6069 Mon Sep 17 00:00:00 2001 From: zeertzjq Date: Fri, 7 Mar 2025 17:49:54 +0800 Subject: perf(keycodes): use hashy for string lookup This is slightly faster than the binary search as per the benchmark, and allows handling the vim/vim#16821 situation in generator code. --- src/gen/gen_keycodes.lua | 81 +++++++++++++++++++++++++++++++++++------------- src/gen/hashy.lua | 20 ++++++------ src/nvim/keycodes.c | 56 +++++---------------------------- src/nvim/keycodes.lua | 2 ++ 4 files changed, 78 insertions(+), 81 deletions(-) diff --git a/src/gen/gen_keycodes.lua b/src/gen/gen_keycodes.lua index 118eac2579..53f0c24e58 100644 --- a/src/gen/gen_keycodes.lua +++ b/src/gen/gen_keycodes.lua @@ -1,49 +1,86 @@ local names_file = arg[1] +local hashy = require('gen.hashy') local keycodes = require('nvim.keycodes') -local names_tgt = assert(io.open(names_file, 'w')) +local keycode_names = keycodes.names ---- @type [string, string, integer][] -local keycode_names = {} -for i, keycode in ipairs(keycodes.names) do - table.insert(keycode_names, { keycode[1], keycode[2], i }) -end -table.sort(keycode_names, function(keycode_a, keycode_b) - return keycode_a[2]:lower() < keycode_b[2]:lower() -end) +--- @type table +--- Maps lower-case key names to their original indexes. +local name_orig_idx = {} --- @type table -local alt_name_idx = {} +--- Maps keys to the original indexes of their preferred names. +local key_orig_idx = {} + +--- @type [string, string][] +--- When multiple keys have the same name (e.g. TAB and K_TAB), only the first one +--- is added to the two tables above, and the other keys are added here. +local extra_keys = {} + for i, keycode in ipairs(keycode_names) do local key = keycode[1] - local alt_idx = alt_name_idx[key] - if alt_idx == nil or keycode_names[alt_idx][3] > keycode[3] then - alt_name_idx[key] = i + local name = keycode[2] + local name_lower = name:lower() + if name_orig_idx[name_lower] == nil then + name_orig_idx[name_lower] = i + if key_orig_idx[key] == nil then + key_orig_idx[key] = i + end + else + table.insert(extra_keys, keycode) + end +end + +local hashorder = vim.tbl_keys(name_orig_idx) +table.sort(hashorder) +local hashfun +hashorder, hashfun = hashy.hashy_hash('get_special_key_code', hashorder, function(idx) + return 'key_names_table[' .. idx .. '].name.data' +end, true) + +--- @type table +--- Maps keys to the (after hash) indexes of the entries with preferred names. +local key_hash_idx = {} + +for i, lower_name in ipairs(hashorder) do + local orig_idx = name_orig_idx[lower_name] + local key = keycode_names[orig_idx][1] + if key_orig_idx[key] == orig_idx then + key_hash_idx[key] = i end end +local names_tgt = assert(io.open(names_file, 'w')) names_tgt:write([[ static const struct key_name_entry { - int key; ///< Special key code or ascii value - String name; ///< Name of key - const String *alt_name; ///< Pointer to alternative key name - ///< (may be NULL or point to the name in another entry) + int key; ///< Special key code or ascii value + String name; ///< Name of key + const String *pref_name; ///< Pointer to preferred key name + ///< (may be NULL or point to the name in another entry) } key_names_table[] = {]]) -for i, keycode in ipairs(keycode_names) do +for i, lower_name in ipairs(hashorder) do + local keycode = keycode_names[name_orig_idx[lower_name]] local key = keycode[1] local name = keycode[2] - local alt_idx = alt_name_idx[key] + local pref_idx = key_hash_idx[key] names_tgt:write( - ('\n {%s, {"%s", %d}, %s},'):format( + ('\n {%s, {"%s", %u}, %s},'):format( key, name, #name, - alt_idx == i and 'NULL' or ('&key_names_table[%d].name'):format(alt_idx - 1) + pref_idx == i and 'NULL' or ('&key_names_table[%u].name'):format(pref_idx - 1) ) ) end -names_tgt:write('\n};\n') +for _, keycode in ipairs(extra_keys) do + local key = keycode[1] + local name = keycode[2] + names_tgt:write(('\n {%s, {"%s", %u}, NULL},'):format(key, name, #name)) +end + +names_tgt:write('\n};\n\n') +names_tgt:write('static ' .. hashfun) names_tgt:close() diff --git a/src/gen/hashy.lua b/src/gen/hashy.lua index 74b7655324..48292bfc0e 100644 --- a/src/gen/hashy.lua +++ b/src/gen/hashy.lua @@ -54,7 +54,7 @@ function M.build_pos_hash(strings) return len_pos_buckets, maxlen, worst_buck_size end -function M.switcher(put, tab, maxlen, worst_buck_size) +function M.switcher(put, tab, maxlen, worst_buck_size, lower) local neworder = {} --- @type string[] put ' switch (len) {\n' local bucky = worst_buck_size > 1 @@ -66,7 +66,7 @@ function M.switcher(put, tab, maxlen, worst_buck_size) local keys = vim.tbl_keys(posbuck) if #keys > 1 then table.sort(keys) - put('switch (str[' .. (pos - 1) .. ']) {\n') + put(('switch (%s(str[%s])) {\n'):format(lower and 'TOLOWER_ASC' or '', pos - 1)) for _, c in ipairs(keys) do local buck = posbuck[c] local startidx = #neworder @@ -102,7 +102,7 @@ function M.switcher(put, tab, maxlen, worst_buck_size) return neworder end -function M.hashy_hash(name, strings, access) +function M.hashy_hash(name, strings, access, lower) local stats = {} local put = function(str) table.insert(stats, str) @@ -116,27 +116,27 @@ function M.hashy_hash(name, strings, access) else put(' int low = -1;\n') end - local neworder = M.switcher(put, len_pos_buckets, maxlen, worst_buck_size) + local neworder = M.switcher(put, len_pos_buckets, maxlen, worst_buck_size, lower) if maxlen == 1 then put([[ return -1; ]]) elseif worst_buck_size > 1 then - put([[ + put(([[ for (int i = low; i < high; i++) { - if (!memcmp(str, ]] .. access('i') .. [[, len)) { + if (!%s(str, %s, len)) { return i; } } return -1; -]]) +]]):format(lower and 'mb_strnicmp' or 'memcmp', access('i'))) else - put([[ - if (low < 0 || memcmp(str, ]] .. access('low') .. [[, len)) { + put(([[ + if (low < 0 || %s(str, %s, len)) { return -1; } return low; -]]) +]]):format(lower and 'mb_strnicmp' or 'memcmp', access('low'))) end put '}\n\n' return neworder, table.concat(stats) diff --git a/src/nvim/keycodes.c b/src/nvim/keycodes.c index 5ab6a718ef..9cb2321eee 100644 --- a/src/nvim/keycodes.c +++ b/src/nvim/keycodes.c @@ -338,8 +338,8 @@ char *get_special_key_name(int c, int modifiers) } } } else { // use name of special key - const String *s = key_names_table[table_idx].alt_name != NULL - ? key_names_table[table_idx].alt_name + const String *s = key_names_table[table_idx].pref_name != NULL + ? key_names_table[table_idx].pref_name : &key_names_table[table_idx].name; if ((int)s->size + idx + 2 <= MAX_KEY_NAME_LEN) { @@ -601,44 +601,6 @@ int find_special_key_in_table(int c) return -1; } -/// Compare two 'struct key_name_entry' structures. -/// Note that the target string (p1) may contain additional trailing characters -/// that should not factor into the comparison. Example: -/// 'LeftMouse>", ""] ...' -/// should match with -/// 'LeftMouse'. -/// These characters are identified by ascii_isident(). -static int cmp_key_name_entry(const void *a, const void *b) -{ - const char *p1 = ((struct key_name_entry *)a)->name.data; - const char *p2 = ((struct key_name_entry *)b)->name.data; - int result = 0; - - if (p1 == p2) { - return 0; - } - - while (ascii_isident(*p1) && *p2 != NUL) { - if ((result = TOLOWER_ASC(*p1) - TOLOWER_ASC(*p2)) != 0) { - break; - } - p1++; - p2++; - } - - if (result == 0) { - if (*p2 == NUL) { - if (ascii_isident(*p1)) { - result = 1; - } - } else { - result = -1; - } - } - - return result; -} - /// Find the special key with the given name /// /// @param[in] name Name of the special. Does not have to end with NUL, it is @@ -654,17 +616,13 @@ int get_special_key_code(const char *name) return TERMCAP2KEY((uint8_t)name[2], (uint8_t)name[3]); } - struct key_name_entry target = { .name.data = (char *)name }; - struct key_name_entry *entry = bsearch(&target, - &key_names_table, - ARRAY_SIZE(key_names_table), - sizeof(key_names_table[0]), - cmp_key_name_entry); - if (entry != NULL) { - return entry->key; + const char *name_end = name; + while (ascii_isident(*name_end)) { + name_end++; } - return 0; + int idx = get_special_key_code_hash(name, (size_t)(name_end - name)); + return idx >= 0 ? key_names_table[idx].key : 0; } /// Look up the given mouse code to return the relevant information in the other arguments. diff --git a/src/nvim/keycodes.lua b/src/nvim/keycodes.lua index c6158b0b84..04f09eb005 100644 --- a/src/nvim/keycodes.lua +++ b/src/nvim/keycodes.lua @@ -1,5 +1,7 @@ return { --- @type [string, string][] List of [key, name] tuples. + --- For keys with multiple names, put the preferred name first. + --- For multiple keys with the same name, put the preferred key first. names = { { [[' ']], 'Space' }, { [[TAB]], 'Tab' }, -- cgit