FAK - A declarative keyboard firmware based on Nickel

[semickolon]

https://github.com/semickolon/fak

Just wanted to share that I'm glad I chose Nickel for my keyboard firmware project. It's perfect for my use case!

Basically, in FAK, Nickel is the code generator. The configs become C code. The C code is not human-readable for the most part, especially the bitwise keycodes, so there has to be a config abstraction layer. Also, the typing and contracts are awesome so invalid configs don't even compile at all.

[semickolon]

The evaluation time gets slow though. Up to 5s in complex configs. The C compilation step happens in less than a second, so the code generation step takes the longest.

I wonder if there's anything I can do to improve the perf right now, or maybe this is something being actively worked on. Also, I second incremental eval! Keymap tinkerers like to tweak small parts of their config after initial setup and boilerplate.

[yannham]

Hi,
Thanks a lot for sharing! We are indeed actively working on perf - see in particular #1622 -. By any chance, are you using master or the last stable release? We added contract deduplication on master, which might already give a good boost in some cases. Anyway, it's really useful for us to profile and test our optimizations to have access to more such mid-sized codebases, so we'll definitely add fak to our benchmarks now 🙂

[semickolon]

That's cool!

I was using 1.2.1 stable. I tried master just now (by updating the input flake to latest commit) and it took about the same time to evaluate. I didn't notice any improvement.

If it helps, I think it got slower the I more I use the Set contract (in util_types.ncl) which validates that the elements are unique.

[yannham]

I see. There's also #1671 which just got merged a few minutes ago :) but in general we'll try to switch to a 6-weeks release, so you can just wait for the next one and try again. I'll try on my side anyway.

Ah, indeed, the Set contracts looks quadratic. You can use bare records as dict/hashmaps as well (as long as you can convert the element to a string easily). Typically, if the thing you're testing for uniqueness are numbers, I would do something like:

let find_num_duplicate
  : Array Number
    -> {
      has_duplicate: Bool,
      seen: {_: Bool},
      duplicate: Number
    }
  | doc m%"
      Take an array of numbers and determine if there is any duplicate inside.

      The `has_duplicate` field of the returned value is `false` if no duplicate
      has been found, and `true` otherwise. In the latter case, the first duplicate
      found is accessible in the `duplicate` field.

      # Examples

      ```nickel
      find_num_duplicate [1,2,3,4]
      #> {has_duplicate = false, duplicate = 0, ..}
      find_num_duplicate [1,2,3,3,4]
      #> {has_duplicate = true, duplicate = 3, ..}
      ```
    "%
  =
  std.array.fold_right (fun elt acc =>
    if acc.has_duplicate then
      acc
    else
      let num_as_str = std.string.from_number elt in
      if std.record.has_field num_as_str acc.seen then
        {
          has_duplicate = true,
          seen = acc.seen,
          duplicate = elt,
        }
      else
        {
          has_duplicate = false,
          seen = std.record.insert num_as_str true acc.seen,
          duplicate = 0,
        })
  # The {_: Bool} annotation is needed because of current limitations when
  # typing dictionaries in Nickel. This might be removed in the future once
  # RFC004 is implemented
  # (https://github.com/tweag/nickel/blob/master/rfcs/004-typechecking.md).
  {has_duplicate = false, seen : {_: Bool} = {}, duplicate = 0}
in

You can try without the static type annotation as well, and see if that changes anything. For structured data, you can serialize them, but the cost may add up and trumps the gain - once again, I guess it has to be tested. But this version, when applicable, is still theoretically linear-time amortized, while yours is quadratic.

Theoretically you could sort as well and make a linear pass to compare consecutive elements for equality, but I'm suspicious of the performance of sorting in Nickel, as it is implemented in pure Nickel (it's not trivial to have a sort primop which relies on e.g. Rust's native sort, because of lazyness).