kc3-lang/libxkbcommon/scripts/makekeys

• Show log

  Commit

• Hash : 68e69b7d
  Author :
  Date : 2021-03-28T20:22:54
  

  keysym: use a perfect hash function for case sensitive xkb_keysym_from_name
  
  In 7d84809fdccbb5898d0838849ec7c321410182d5 I added a fast path for the
  case-sensitive case, but it is still slowing down Compose parsing.
  
  Instead of the binary search, use a perfect hash function, computed with
  a simple python module I found (vendored).
  
  It is faster -- perf diff is:
  
     Baseline  Delta Abs  Shared Object      Symbol
     ........  .........  .................  ...................................
  
       22.35%    -14.04%  libc-2.33.so       [.] __strcmp_avx2
       16.75%    +10.28%  bench-compose      [.] xkb_keysym_from_name
       20.72%     +2.40%  bench-compose      [.] parse.constprop.0
        2.29%     -1.97%  bench-compose      [.] strcmp@plt
        2.56%     +1.81%  bench-compose      [.] resolve_name
        2.37%     +0.92%  libc-2.33.so       [.] __GI_____strtoull_l_internal
       26.19%     -0.63%  bench-compose      [.] lex
        1.45%     +0.56%  libc-2.33.so       [.] __memchr_avx2
        1.13%     -0.31%  libc-2.33.so       [.] __strcpy_avx2
  
  Also reduces the binary size:
  
  Before:
  
        text    data     bss     dec     hex filename
      341111    5064       8  346183   54847 build/libxkbcommon.so.0.0.0
  
  After:
  
        text    data     bss     dec     hex filename
      330215    5064       8  335287   51db7 build/libxkbcommon.so.0.0.0
  
  Note however that it's still larger than before 7d84809fdccbb5898d08388:
  
        text    data     bss     dec     hex filename
      320617    5168       8  325793   4f8a1 build/libxkbcommon.so.0.0.0
  
  Signed-off-by: Ran Benita <ran@unusedvar.com>
  

Download

• scripts/makekeys

• #!/usr/bin/env python
  
  import re, sys, itertools
  
  import perfect_hash
  
  pattern = re.compile(r'^#define\s+XKB_KEY_(?P<name>\w+)\s+(?P<value>0x[0-9a-fA-F]+)\s')
  matches = [pattern.match(line) for line in open(sys.argv[1])]
  entries = [(m.group("name"), int(m.group("value"), 16)) for m in matches if m]
  
  entries_isorted = sorted(entries, key=lambda e: e[0].lower())
  entries_kssorted = sorted(entries, key=lambda e: e[1])
  
  print('''
  /**
   * This file comes from libxkbcommon and was generated by makekeys.py
   * You can always fetch the latest version from:
   * https://raw.github.com/xkbcommon/libxkbcommon/master/src/ks_tables.h
   */
  ''')
  
  entry_offsets = {}
  
  print('''
  #ifdef __GNUC__
  #pragma GCC diagnostic push
  #pragma GCC diagnostic ignored "-Woverlength-strings"
  #endif
  static const char *keysym_names =
  '''.strip())
  offs = 0
  for (name, _) in entries_isorted:
      entry_offsets[name] = offs
      print('    "{name}\\0"'.format(name=name))
      offs += len(name) + 1
  print('''
  ;
  #ifdef __GNUC__
  #pragma GCC diagnostic pop
  #endif
  '''.strip())
  
  
  template = r'''
  static const uint16_t keysym_name_G[] = {
      $G
  };
  
  static size_t
  keysym_name_hash_f(const char *key, const char *T)
  {
      size_t sum = 0;
      for (size_t i = 0; key[i] != '\0'; i++)
          sum += T[i % $NS] * key[i];
      return sum % $NG;
  }
  
  static size_t
  keysym_name_perfect_hash(const char *key)
  {
      return (
          keysym_name_G[keysym_name_hash_f(key, "$S1")] +
          keysym_name_G[keysym_name_hash_f(key, "$S2")]
      ) % $NG;
  }
  '''
  print(perfect_hash.generate_code(
      keys=[name for name, value in entries_isorted],
      template=template,
  ))
  
  print('''
  struct name_keysym {
      xkb_keysym_t keysym;
      uint32_t offset;
  };\n''')
  
  def print_entries(x):
      for (name, value) in x:
          print('    {{ 0x{value:08x}, {offs} }}, /* {name} */'.format(offs=entry_offsets[name], value=value, name=name))
  
  print('static const struct name_keysym name_to_keysym[] = {')
  print_entries(entries_isorted)
  print('};\n')
  
  # *.sort() is stable so we always get the first keysym for duplicate
  print('static const struct name_keysym keysym_to_name[] = {')
  print_entries(next(g[1]) for g in itertools.groupby(entries_kssorted, key=lambda e: e[1]))
  print('};')
  

Download