Feature request: increased max chord group length

[dlip]

Is your feature request related to a problem? Please describe.

I have many abbreviations for common words that I would like to write via a chord macro. Chord groups are currently limited to 32 max

Describe the solution you'd like.

I would like to be able to have a lot more possible combos, my abbreviation list currently has 5670 combos

Describe alternatives you've considered.

I have it working in qmk and zmk but it would be great to be able to use it when im stuck with my laptop

Additional context

No response

[jtroo]

Curious, how are you using chords such that you're hitting the limit of 32 associated symbols? That's more than the alphabet keys on the keyboard.

If I remember correctly there shouldn't be a limit on number of actions within a group, only on participating symbols for the group.

[dlip]

@jtroo I'm working on this chord generator for common words, its easy to get into the triple digits when you have different combos for capitilized, past, continuing, plural forms etc. https://github.com/dlip/abbrgen

[dlip]

@jtroo maybe i misunderstood the error message, i thought it was total combos but maybe it is just symbols as you said. Let me test some more

[dlip]

@jtroo I tried again and the limit of 32 is indeed at the symbol level. My layout has 36 keys though so I'm unable to map all of them. Others probably have more keys, a full size keyboard has 101-104 keys.

[jtroo]

You could try adjusting this to a u64 and see if that works as-is.

pub type ChordKeys = u32;

[wis]

I also ran into this a month ago, I adjusted it to u128, not u64, and it worked fine. I can make a PR and push my changes if you want.

Not using u128, the biggest native/built-in Rust unsigned integer type is just an optimization right? I'd argue it is an unnecessary optimization since it does not make the program meaningfully or noticeably faster, because on each key press, it is just a hashmap lookup not a big compute task that needs optimization.

Curious, how are you using chords such that you're hitting the limit of 32 associated symbols? That's more than the alphabet keys on the keyboard.

a full sized keyboard has 104 keys. I've read that some keyboards even have the F12-F24 keys, so 12 extra keys, so a 116 key full sized keyboard. technically, the USB HID protocol standard supports all these distinct physical keys/scancodes. this also means that using u128 should be about enough. also in a defchords group you don't just define the "symbols" which would be bound to physical keys, you also need to define in defchords the chords that are a combination of these "symbols".

[jtroo]

The lookup for running time (not parsing time) today is linear. Should probably change the code to sort the array and use binary search for lookup.

[wis]

The lookup for running time (not parsing time) today is linear. Should probably change the code to sort the array and use binary search for lookup.

what do you mean? to be honest, I do not understand how or where it looksup the chords on each key press.

by array you mean the coords array defined here?

https://github.com/jtroo/kanata/blob/16c9da8df6295d294960901ecb998c8c3bdc4624/parser/src/cfg/mod.rs#L941-L948

and is the code for the lookup that should happen on each key press, in this part of the code:

https://github.com/jtroo/kanata/blob/16c9da8df6295d294960901ecb998c8c3bdc4624/keyberon/src/action.rs#L249-L280

Edit: has ChatGPT4 explained things right? https://chat.openai.com/share/ca96f711-5017-4864-ab11-93bd3403d0f0

[jtroo]

No idea about chatgpt, I don't have an account.

But get_chord is right. Interestingly get_chord_unambiguous seems like it would be called more frequently. But I'm not sure how that could be optimized... Would be nice though to avoid iterating linearly over potentially thousands of elements.

https://github.com/jtroo/kanata/blob/main/keyberon/src/layout.rs#L543-L567

Taking another look, I think the best optimization that can be made for now is to check if the get_ calls need to be made in the first place. The checks are actually running on every tick right now, but that isn't necessary if the number of queued events hasn't changed since the last call. So probably need to store the number of queued events and do a fast-path tick-timeout-only check when the number hasn't changed.

[wis]

No idea about chatgpt, I don't have an account.

Oh, sorry, just realized that they started asking for people to sign in to view shared conversations/threads. I exported the thread into markdown if you would like to view it.

expand spoiler to view thread (warning: long wall of text)

# Me: `self.coords.iter().find(|c| c.0 == coord).map(|c| c.1) ` is this a linear lookup and not a binary search lookup? # ChatGPT: Yes, the code snippet you've provided performs a linear search and not a binary search. Let's break down the code to understand why: ```rust self.coords.iter().find(|c| c.0 == coord).map(|c| c.1) ``` - `self.coords.iter()`: This creates an iterator over the items in `self.coords`, which suggests that `self.coords` is a collection of some sort (e.g., a `Vec`, `array`, or other iterable collection). - `.find(|c| c.0 == coord)`: This method iterates through each item `c` in the collection, checking if the first element of the tuple `c.0` matches the `coord`. It stops and returns the first match it finds. The `find` method operates by checking each element in sequence from the start of the collection, making it a linear search. Linear search has a time complexity of O(n), where n is the number of elements in the collection. - `.map(|c| c.1)`: If `.find` returns a match, `map` is used to transform the found element, extracting the second element of the tuple `c.1`. For it to be a binary search: 1. The collection would need to be sorted based on the search key (`c.0` in this case). 2. You would use a method or algorithm that specifically performs binary search, which divides the search interval in half each time, reducing the search complexity to O(log n). This is significantly faster than linear search for large datasets but requires the dataset to be sorted. Rust provides binary search functionality for slices with the `.binary_search()` method, but it requires the collection to be sorted and only works when you're searching for a specific value, not with a condition like in `.find()`. Additionally, `.binary_search()` returns a `Result` indicating whether the value was found and its index, rather than the value itself. # Me: how to sort coords before hand, and then how to modify this code to preform a binary_search lookup instead of a binary search lookup? # ChatGPT: To sort `coords` beforehand and then modify the code to perform a binary search lookup instead of a linear search, you'll need to follow these steps: 1. **:** Ensure `coords` is sorted based on the first element of each tuple. You can sort `coords` in place if it's a mutable collection. 2. **Modify the code for binary search:** Use Rust's `.binary_search_by()` method to find the position of the desired coordinate. Since `.binary_search_by()` requires a comparison function, you'll compare the target coordinate with the first element of each tuple. Here's how you can do it: ### Step 1: Sort `coords` Before you attempt a binary search, ensure that `coords` is sorted by the first element of each tuple. Here's an example of how you might sort `coords` if it's a `Vec`: ```rust self.coords.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap()); ``` This assumes that the type of `a.0` and `b.0` implements `PartialOrd`, which is true for most numeric types. The `unwrap` is used here for simplicity, assuming that the comparison will not fail. In production code, you might want to handle potential `None` cases more gracefully. ### Step 2: Modify the Code for Binary Search After sorting, you can modify your code to use `.binary_search_by()` for a more efficient lookup. Here's how you could do it: ```rust self.coords.binary_search_by(|c| c.0.cmp(&coord)) .ok() .map(|index| self.coords[index].1) ``` Let's break down what this does: - `.binary_search_by(|c| c.0.cmp(&coord))`: This method attempts to find the element where the first item of the tuple matches `coord`. The closure provides the comparison logic, comparing the first item of each tuple (`c.0`) with `coord`. The method returns a `Result::Ok(index)` if the element is found, where `index` is the position of the matching element, or `Result::Err(index)` where `index` is the insertion point if the element is not found. - `.ok()`: Converts a `Result` to an `Option`, turning `Ok(index)` into `Some(index)` and `Err(_)` into `None`. This allows chaining with `.map()`. - `.map(|index| self.coords[index].1)`: If an element was found (`Some(index)`), this maps the result to the second item of the tuple at the found index, effectively extracting the desired value. This approach assumes `coord` can be directly compared with the first item of each tuple in `coords` (i.e., they are of compatible types). The binary search will be significantly faster for large datasets than the original linear search, especially because it reduces the complexity from O(n) to O(log n), but it requires the `coords` to be sorted based on the search key (`c.0` in this case). # Me: for extra context, the definition for coords is in this struct type definition ``` struct ChordGroup { id: u16, name: String, keys: Vec, coords: Vec<((u8, u16), ChordKeys)>, chords: HashMap, timeout: u16, } ``` # ChatGPT: Given the definition of `coords` within the `ChordGroup` struct as `Vec<((u8, u16), ChordKeys)>`, where each element is a tuple containing a tuple of `(u8, u16)` and `ChordKeys`, you can follow the same steps as outlined with slight adjustments for the types involved. ### Step 1: Sorting `coords` You will still sort `coords` based on the first element of the outer tuple (which itself is a tuple of `(u8, u16)`). Given the composite key, the sorting criterion might need to consider both elements of the inner tuple, depending on your requirements. If sorting by the first element of the inner tuple `(u8, u16)` is sufficient for your use case, you can do so directly: ```rust self.coords.sort_by(|a, b| a.0 .0.cmp(&b.0 .0)); ``` This sorts `coords` based on the `u8` value of the inner tuple. If you need to consider the `u16` value in cases where the `u8` values are equal, you would adjust the sorting logic accordingly. ### Step 2: Modifying the Code for Binary Search Given the more complex structure of the elements in `coords`, the binary search part also needs to consider this structure: ```rust self.coords.binary_search_by_key(&coord, |&(ref key, _)| key.0) .ok() .map(|index| self.coords[index].1.clone()) ``` Breaking down the changes: - `.binary_search_by_key(&coord, |&(ref key, _)| key.0)`: Here, `binary_search_by_key` is used for convenience, assuming you're searching based on the `u8` value (the first element of the inner tuple). The closure extracts this value for comparison with `coord`, which should be of type `u8` in this context. If your search criteria involve both elements of the inner tuple `(u8, u16)`, you will need to revert to using `.binary_search_by()` and adjust the comparison logic to consider both elements. - `.ok().map(|index| self.coords[index].1.clone())`: This part remains similar, mapping the found index to the corresponding `ChordKeys` value. The `clone()` is necessary if `ChordKeys` does not implement `Copy`, ensuring you don't move the value out of `coords`. This adjusted approach takes into account the specific structure of `coords` as defined in your `ChordGroup` struct. Remember, the collection must be sorted before performing a binary search, and the search key used in `.binary_search_by_key()` or `.binary_search_by()` must match the criteria used for sorting `coords`.

But get_chord is right. Interestingly get_chord_unambiguous seems like it would be called more frequently.

oh I thought that the relavent linear search happens on line 252: https://github.com/jtroo/kanata/blob/16c9da8df6295d294960901ecb998c8c3bdc4624/keyberon/src/action.rs#L250-L253

Would be nice though to avoid iterating linearly over potentially thousands of elements.

thousands of elements? the coords Vec can have that many elements?

Anyways, I do not want to waste your time with unnecessary questions since I'm out of my depth here, I'm a newb in Rust, and I do not really understand how all of this chords related logic works, I only was capable of changing a type from u32 to u128 and it worked. so feel free to not answer the 2 questions above, since I see I'm not capable of contributing here, I included them just to show you my sense of understanding here.

[dlip]

@jtroo Thank you so much! It works as well as can be expected on my laptop keyboard. I've added it to the exporters in abbrgen https://github.com/dlip/abbrgen/tree/main?tab=readme-ov-file#kanata-chordedpy

Now I just need to get around to learning rust so I can fix #743 and start using it full time :sweat_smile: