Parking-lot note
IR does not have a compiler backend yet, and this issue should not turn into one now.
The reason to record it early is that R already gives us unusually rich operations that a future backend could destroy by lowering too eagerly into scalar interpreter behavior.
Companion research note: isomorphisms/computer-science#25.
Design constraint
When IR eventually acquires compiled backends, try to preserve high-level data semantics long enough for the backend to choose an implementation suited to the target.
Examples worth preserving include:
- vector arithmetic/comparison;
- vectorized conditional selection;
- matching / membership;
- joins;
- grouping and aggregation;
- ordering/ranking;
- categorical/factor operations;
- known type/coercion cases;
- finite multiway dispatch where it is genuinely part of the hot path.
Do not automatically flatten these into one scalar loop full of nested conditionals before target selection.
Joins as a first future case study
The dplyr/tidyverse join family is a good concrete probe because a source operation carries much more information than "loop over two tables":
- inner / left / right / full / semi / anti / cross semantics;
- key columns;
- key types;
- equality/range predicate;
- duplicate multiplicity;
- missing-value rules;
- output ordering/shape requirements;
- class/attribute behavior where applicable.
A future compiler could use those semantics to choose among very different realizations:
- hash join;
- sort/merge join;
- radix or direct-address specialization for suitable integer keys;
- dictionary-encoded/string specialization;
- tiny-input nested loops;
- vector/SIMD comparison during probe phases;
- branchless or mask-based matching where useful;
- parallel partitions when the target and workload justify them.
The compiler should not expose any one of these as the meaning of join.
R's vectorized surface is valuable information
A statement operating on a whole vector is already telling the compiler something important: the elements are undergoing a common operation.
That opens possibilities such as:
- SIMD/vector lanes;
- conditional-select/mask execution instead of one unpredictable branch per element;
- bitsets for Boolean/missingness state;
- specialized kernels for common type pairs;
- loop fusion across adjacent vector operations;
- reduced temporary allocation and memory traffic;
- chunked/parallel execution;
- GPU lowering only when residency/transfer cost makes it worthwhile.
This is closely analogous to preserving fixed-string-search semantics in Idriç: the optimization opportunity comes from not forgetting what operation the programmer asked for.
Separate three different dispatch problems
Do not conflate:
- language/interpreter dispatch — opcode/evaluator/parser dispatch;
- generic method/type dispatch — selecting one implementation based on classes/types;
- inner data-kernel decisions — branches, masks, table lookups, comparisons repeated across millions of elements.
A method lookup that occurs once before a 10-million-element vector kernel may be negligible. The repeated decisions inside the kernel are a different optimization problem.
Semantics that must survive optimization
R compatibility makes the correctness boundary nontrivial. Any compiled specialization has to preserve the intended behavior around things such as:
NA versus NaN where they differ;- integer/double/logical/character and other coercions;
- attributes/classes;
- factors/categorical values;
- duplicate keys and output multiplicity;
- names/dimensions where relevant;
- ordering/stability promises;
- generic-method behavior before entering a specialized kernel.
Do not buy speed by silently becoming a different language.
Suggested first work when a backend actually begins
Start with a small executable corpus instead of a general optimizer:
- vector add/compare with missing values;
- multi-branch vectorized conditional (
case_when-like shape);
%in% / match-style lookup;- integer-key inner join;
- integer-key left join with duplicates;
- string-key join;
- grouped sum/count;
- sort/order/rank.
For each operation, keep:
- an ordinary R/IR semantic oracle;
- representative current R/tidyverse behavior as a baseline;
- exact input/output fixtures including edge cases;
- generated machine code when native lowering exists;
- throughput, allocations, memory traffic, and code size separately.
Where relevant, compare against competent existing implementations such as dplyr/vctrs, data.table, Arrow, or database engines—not only against naive R loops.
Low-level control flow
Jump tables/computed branches are worth testing where there is genuinely dense finite dispatch, but they are only one possibility.
For vectorized R workloads the best realization may instead be:
- no branch at all;
- SIMD masks/selects;
- a data table lookup;
- a hash probe;
- packed bits;
- an algorithmic change that makes instruction-level branch choice secondary.
Keep the backend free to measure and choose.
Scope
For now: record the constraint and leave it parked.
Do not start a compiler backend, rewrite dplyr, or crawl the entire R source tree just because this issue exists. Return to it when IR actually begins native compilation.
Parking-lot note
IR does not have a compiler backend yet, and this issue should not turn into one now.
The reason to record it early is that R already gives us unusually rich operations that a future backend could destroy by lowering too eagerly into scalar interpreter behavior.
Companion research note:
isomorphisms/computer-science#25.Design constraint
When IR eventually acquires compiled backends, try to preserve high-level data semantics long enough for the backend to choose an implementation suited to the target.
Examples worth preserving include:
Do not automatically flatten these into one scalar loop full of nested conditionals before target selection.
Joins as a first future case study
The dplyr/tidyverse join family is a good concrete probe because a source operation carries much more information than "loop over two tables":
A future compiler could use those semantics to choose among very different realizations:
The compiler should not expose any one of these as the meaning of
join.R's vectorized surface is valuable information
A statement operating on a whole vector is already telling the compiler something important: the elements are undergoing a common operation.
That opens possibilities such as:
This is closely analogous to preserving fixed-string-search semantics in Idriç: the optimization opportunity comes from not forgetting what operation the programmer asked for.
Separate three different dispatch problems
Do not conflate:
A method lookup that occurs once before a 10-million-element vector kernel may be negligible. The repeated decisions inside the kernel are a different optimization problem.
Semantics that must survive optimization
R compatibility makes the correctness boundary nontrivial. Any compiled specialization has to preserve the intended behavior around things such as:
NAversusNaNwhere they differ;Do not buy speed by silently becoming a different language.
Suggested first work when a backend actually begins
Start with a small executable corpus instead of a general optimizer:
case_when-like shape);%in%/ match-style lookup;For each operation, keep:
Where relevant, compare against competent existing implementations such as dplyr/vctrs,
data.table, Arrow, or database engines—not only against naive R loops.Low-level control flow
Jump tables/computed branches are worth testing where there is genuinely dense finite dispatch, but they are only one possibility.
For vectorized R workloads the best realization may instead be:
Keep the backend free to measure and choose.
Scope
For now: record the constraint and leave it parked.
Do not start a compiler backend, rewrite dplyr, or crawl the entire R source tree just because this issue exists. Return to it when IR actually begins native compilation.