kc3-lang/libxkbcommon

• Show log

  Commit

• Hash : 02b9cabf
  Author :
  Date : 2021-03-29T16:05:14
  

  compose: use a ternary tree instead of a regular trie
  
  Previously we used a simple trie with a linked list for each chain.
  Unfortunately most compose files have very long chains which means the
  constructions performs an almost quadratic number of comparisons.
  
  Switch to using a ternary search tree instead. This is very similar to a
  trie, only the linked list is essentially replaced with a binary tree.
  
  On the en_US/Compose file, the perf diff is the following (the modified
  function is `parse`):
  
    Event 'cycles:u'
  
    Baseline  Delta Abs  Shared Object     Symbol
    ........  .........  ................  .................................
  
      39.91%    -17.62%  bench-compose     [.] parse.constprop.0
      20.54%     +6.47%  bench-compose     [.] lex
      17.28%     +5.55%  libc-2.33.so      [.] __strcmp_avx2
      12.78%     +4.01%  bench-compose     [.] xkb_keysym_from_name
       2.30%     +0.83%  libc-2.33.so      [.] __GI_____strtoull_l_internal
       3.36%     +0.78%  bench-compose     [.] strcmp@plt
  
  Thanks to some careful packing, the memory usage is pretty much the
  same.
  
  Signed-off-by: Ran Benita <ran@unusedvar.com>
  

• Files

• .editorconfig
• .github/
• .uncrustify.cfg
• LICENSE
• NEWS
• PACKAGING
• README.md
• bench/
• doc/
• fuzz/
• meson.build
• meson_options.txt
• scripts/
• src/
• test/
• tools/
• xkbcommon-x11.map
• xkbcommon.map
• xkbcommon/
• xkbregistry.map

• Properties

• Git HTTP	https://git.kmx.io/kc3-lang/libxkbcommon.git
  Git SSH	git@git.kmx.io:kc3-lang/libxkbcommon.git
  Public access ?	public
  Description	keymap handling library for toolkits and window systems Upstream Homepage Github Fork Github
  Users
  Tags