5 ms·

Variation on Iota

18 points by aebtebeten 9mo ago

xenonite 9mo ago
This is about the APL language. std::iota is influenced by APL, see Notes in https://en.cppreference.com/w/cpp/algorithm/iota.html https://en.cppreference.com/w/cpp/algorithm/iota.html
mlochbaum 9mo ago
Ooh, I've run into this one before! I'm a big fan of interval index[0], which performs a binary search, so Josh's suggestion is the one I prefer as well (the implementation might sometimes optimize by transforming it into a table lookup like the other solutions). Searching for +`≠¨ in my BQN files turns up a few uses, including one used to group primitives into types in a utility involved in compiling BQN[1] and an annotated function used a few times in the markdown processor that builds BQN's website[2]. [0] https://aplwiki.com/wiki/Interval_Index https://aplwiki.com/wiki/Interval_Index [1] https://github.com/mlochbaum/BQN/blob/717555b0db/src/pr.bqn#L15 https://github.com/mlochbaum/BQN/blob/717555b0db/src/pr.bqn#... [2] https://github.com/mlochbaum/BQN/blob/717555b0db/md.bqn#L45-L51 https://github.com/mlochbaum/BQN/blob/717555b0db/md.bqn#L45-...
UncleEntity 9mo ago
Been working on the design of an optimizer for my APL VM and asked Claude how this would fit in (as we don't have Dyalog extensions): The pattern is: f⌿ X ∘.g Y Where f is an associative reduction and g is a comparison. iBurg could recognize this tree shape and apply rewrites based on operator properties: ┌─────────┬───────────────────────────────────┐ │ Pattern │ Optimization │ ├─────────┼───────────────────────────────────┤ │ +⌿X∘.≤Y │ Binary search count (if X sorted) │ ├─────────┼───────────────────────────────────┤ │ +⌿X∘.=Y │ Histogram / count matches │ ├─────────┼───────────────────────────────────┤ │ ∨⌿X∘.=Y │ Membership (hash lookup) │ ├─────────┼───────────────────────────────────┤ │ ∧⌿X∘.<Y │ All-less-than (single comparison) │ └─────────┴───────────────────────────────────┘ The generic rules would be: 1. Shape rule: f⌿X∘.gY avoids materializing n×m matrix if f and g have algebraic properties that allow streaming/early-exit 2. Sortedness rule: If X is sorted and g is monotonic (≤, <, ≥, >), use binary search 3. Associativity rule: If f is associative (+, ∨, ∧, ⌈, ⌊), can process in chunks or parallel The cost model decides when O(n log m) binary search beats O(n×m) outer product -typically when both n and m exceed some threshold. iBurg is the Bottom-Up Rewrite System (BURS) based optimizer to operate over the continuation graphs the parser spits out, not sure where the 'i' part came from though...

18 points by aebtebeten 9mo ago

This is about the APL language. std::iota is influenced by APL, see Notes in https://en.cppreference.com/w/cpp/algorithm/iota.html https://en.cppreference.com/w/cpp/algorithm/iota.html

mlochbaum 9mo ago

Ooh, I've run into this one before! I'm a big fan of interval index[0], which performs a binary search, so Josh's suggestion is the one I prefer as well (the implementation might sometimes optimize by transforming it into a table lookup like the other solutions). Searching for +`≠¨ in my BQN files turns up a few uses, including one used to group primitives into types in a utility involved in compiling BQN[1] and an annotated function used a few times in the markdown processor that builds BQN's website[2]. [0] https://aplwiki.com/wiki/Interval_Index https://aplwiki.com/wiki/Interval_Index [1] https://github.com/mlochbaum/BQN/blob/717555b0db/src/pr.bqn#L15 https://github.com/mlochbaum/BQN/blob/717555b0db/src/pr.bqn#... [2] https://github.com/mlochbaum/BQN/blob/717555b0db/md.bqn#L45-L51 https://github.com/mlochbaum/BQN/blob/717555b0db/md.bqn#L45-...

UncleEntity 9mo ago

Been working on the design of an optimizer for my APL VM and asked Claude how this would fit in (as we don't have Dyalog extensions): The pattern is: f⌿ X ∘.g Y Where f is an associative reduction and g is a comparison. iBurg could recognize this tree shape and apply rewrites based on operator properties: ┌─────────┬───────────────────────────────────┐ │ Pattern │ Optimization │ ├─────────┼───────────────────────────────────┤ │ +⌿X∘.≤Y │ Binary search count (if X sorted) │ ├─────────┼───────────────────────────────────┤ │ +⌿X∘.=Y │ Histogram / count matches │ ├─────────┼───────────────────────────────────┤ │ ∨⌿X∘.=Y │ Membership (hash lookup) │ ├─────────┼───────────────────────────────────┤ │ ∧⌿X∘.<Y │ All-less-than (single comparison) │ └─────────┴───────────────────────────────────┘ The generic rules would be: 1. Shape rule: f⌿X∘.gY avoids materializing n×m matrix if f and g have algebraic properties that allow streaming/early-exit 2. Sortedness rule: If X is sorted and g is monotonic (≤, <, ≥, >), use binary search 3. Associativity rule: If f is associative (+, ∨, ∧, ⌈, ⌊), can process in chunks or parallel The cost model decides when O(n log m) binary search beats O(n×m) outer product -typically when both n and m exceed some threshold. iBurg is the Bottom-Up Rewrite System (BURS) based optimizer to operate over the continuation graphs the parser spits out, not sure where the 'i' part came from though...