kc3-lang/libxkbcommon/src/compose/table.h
Branch :
Log
| Author | Commit | Date | CI | Message |
|---|---|---|---|---|
 |
02b9cabf | 2021-03-29 16: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> | |
|
8b09e177 | 2021-03-30 20:12:08 | compose: use anonymous union Signed-off-by: Ran Benita <ran@unusedvar.com> | |
|
1638409b | 2021-03-30 17:52:36 | compose: add a limit of 65535 sequences Fits in uint16_t, which enables some future optimizations. But also a good idea to have some limit. Not aware of any compose files which come close. Signed-off-by: Ran Benita <ran@unusedvar.com> | |
 |
edc98b54 | 2014-09-12 18:44:30 | compose: add xkbcommon-compose - implementation Signed-off-by: Ran Benita <ran234@gmail.com> |