makekeys

Branch :

Show log
Commit
Author : Ran Benita
Date : 2021-03-28 20:22:54
Hash : 68e69b7d
Message : 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>

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('};')

kc3-lang/libxkbcommon/scripts/makekeys

Commit

kc3-lang/libxkbcommon /scripts/makekeys