R/147_reductions_subexpr_cache.R

In CVXR: Disciplined Convex Optimization

#####
## DO NOT EDIT THIS FILE!! EDIT THE SOURCE INSTEAD: rsrc_tree/reductions/subexpr_cache.R
#####

## CVXPY SOURCE: reductions/subexpr_cache.py
##
## Structural keys for the per-apply subexpression cache used by `Dcp2Cone`
## (CVXPY 1.9.2, PR #3355).
##
## When the same subtree appears twice in a problem -- `norm1(x)` in both the
## objective and a constraint -- a recursive canonicalizer that runs blindly
## emits a fresh set of auxiliary variables and epigraph constraints for each
## occurrence. Keying each subtree by STRUCTURE lets the second occurrence reuse
## the first one's canonical expression and auxiliary constraints.
##
## Two keys are equal exactly when the subtrees are interchangeable for
## canonicalization: same atom class, same shape, same `get_data()` payload, and
## same leaf identities. The caller adds any reduction-specific bits on top
## (Dcp2Cone adds `affine_above` when the quad branch could fire).

# -- UNCACHEABLE sentinel ------------------------------------------
## CVXPY SOURCE: subexpr_cache.py lines 59-64 (`UncacheableError`)
##
## DEVIATION (performance, deliberate): upstream raises an exception that
## propagates out of a nested `_hashable_value` call and is caught once per node
## in `_make_cache_key`. R conditions cost microseconds to signal AND to guard
## with `tryCatch`, and this machinery runs once per expression node in a
## reduction whose entire purpose is to be faster -- an exception-based control
## flow would eat the savings. A sentinel gives identical control flow with no
## condition system involved: every recursion site checks for it, exactly where
## upstream would let the exception fly past.
##
## Callers treat it as "skip the cache for this subtree", never as an error.
##
## ONE sentinel now, not two. There used to be a second, string-valued
## `.UNCACHEABLE_STR` for `.hashable_value` -- and it carried a literal 0x01
## control byte inside its string literal, invisible in every editor and diff,
## and the only control character anywhere in `rsrc_tree/`. Keys are integers
## now, so `NA_integer_` serves both paths and that hazard is gone.

.UNCACHEABLE <- NA_integer_

.is_uncacheable <- function(key) is.na(key)

# -- StructuralKeyCache --------------------------------------------
## CVXPY SOURCE: subexpr_cache.py lines 67-79
##
## Per-apply state: a memo from expression id to key (so a caller that keys every
## node walks each node once), an intern table mapping local signatures to
## compact integers, and the `affine_above` memo Dcp2Cone needs.
##
## `expr@id` is CVXR's analogue of Python's `id(expr)`, and a sturdier one:
## distinct expression objects always carry distinct ids (verified: two
## `norm1(x)` calls give different ids, and `expr_copy` mints a fresh one),
## whereas CPython may recycle an `id()` after garbage collection.
##
## DELIBERATE DEVIATION from subexpr_cache.py (performance; ADR D_PERF.6 and
## notes/session_handoff_2026-08-12_perf_regression.md): those maps live in ONE
## C++ store (`src/RcppCseKeys.cpp`) and keys are interned INTEGERS rather than
## strings. Semantics are identical -- the same subtrees merge and the same ones
## do not -- but the R implementation had to build a string per node (`paste0`,
## and `sprintf("%a")` per element for constants) because an R environment can
## only be keyed by character, and R offers no integer-keyed hash map. Measured
## on the qp bench cell that bookkeeping was 370us per compile, ~+6% of compile
## time, on problems with nothing to share. Per node: composite 6.86us ->
## 1.35us, constant-by-value 13.1us -> 0.78us.
##
## The store is PER-APPLY and must stay so: it holds the `affine_above` memo,
## which depends on `quad_obj`.

StructuralKeyCache <- function() .CseKeys__new()

## Signature tags. These are just disjoint integers -- their only job is to keep
## a Variable id from colliding with a Parameter id, a numeric payload from a
## logical one, and so on. The C++ side treats them as opaque.
.CSE_TAG_VAR        <- 1L
.CSE_TAG_PARAM      <- 2L
.CSE_TAG_CONST_ID   <- 3L   # constant keyed by identity (too large to key by value)
.CSE_TAG_CONST_VAL  <- 4L   # constant keyed by value
.CSE_TAG_SPARSE_VAL <- 5L
.CSE_TAG_NUM        <- 6L   # get_data() payloads, below
.CSE_TAG_CHR        <- 7L
.CSE_TAG_LGL        <- 8L
.CSE_TAG_LIST       <- 9L
.CSE_TAG_EXPR       <- 10L
.CSE_TAG_NULL       <- 11L
.CSE_TAG_SPARSE     <- 12L

# -- Classes that must never be cached ------------------------------
## Measured, not guessed: `scripts/cse_key_completeness_scan.R` walks every S7
## Expression subclass and reports those whose identity is NOT captured by
## `(class, shape, get_data(), children)`. Two hazards
## (notes/cvxpy_1.9.2_stage0_report.md section 4):
##
##   PartialProblem   args = list() AND a hard-coded shape = c(1L, 1L)
##                    (transforms/partial_optimize.R:71-99), so EVERY instance
##                    would key identically -- the worst possible case.
##   Perspective      .f / .f_recession held off `args` (atoms/perspective.R:12-35)
##
## SAFER THAN UPSTREAM, deliberately. CVXPY excludes `partial_problem` in
## `Dcp2Cone.canonicalize_tree` (dcp2cone.py:159-161) but has the same latent
## defect for `perspective`; it is only accidentally safe on `partial_problem`
## because that class's `args = [problem]` makes `expr_key` raise. CVXR names
## both here so the exclusion does not depend on an accident.

.cse_deny_list <- function() list(PartialProblem, Perspective)

# -- expr_key -------------------------------------------------------
## CVXPY SOURCE: subexpr_cache.py lines 81-134
##
## Variables/Parameters key by id (same source leaf -> same key); Constants key
## by value when small and by identity when large (see `.constant_key`);
## composite atoms key by (class, shape, get_data(), child keys).
##
## DIRECT `.Call`, NOT the generated wrapper (ADR D_PERF.6): this runs once per
## node, the native side takes ~0.8us, and the wrapper is a further 0.42us of
## pure closure overhead. The price is that `.Call` is positional and coerces
## silently, so every argument below must ALREADY have the right type --
## `expr@id` and the tags are integer, `child_keys` is an integer vector,
## `expr@shape` is coerced explicitly. Passing a double would cost an allocation
## and a copy, which is the whole thing being avoided.

expr_key <- function(expr, store) {
  expr_id <- .id(expr)
  ## wrapper: .CseKeys__memo_get(store, expr_id)
  hit <- .Call(`_CVXR_CseKeys__memo_get`, store, expr_id)
  if (!is.na(hit)) return(hit)

  if (.s7_is(expr, Variable)) {
    ## wrapper: .CseKeys__intern_ints(store, expr_id, .CSE_TAG_VAR, expr_id)
    .Call(`_CVXR_CseKeys__intern_ints`, store, expr_id, .CSE_TAG_VAR, expr_id)
  } else if (.s7_is(expr, Parameter)) {
    ## wrapper: .CseKeys__intern_ints(store, expr_id, .CSE_TAG_PARAM, expr_id)
    .Call(`_CVXR_CseKeys__intern_ints`, store, expr_id, .CSE_TAG_PARAM, expr_id)
  } else if (.s7_is(expr, Constant)) {
    .constant_key(expr, store)
  } else if (.s7_is(expr, Expression)) {
    if (.s7_is_any(expr, .cse_deny_list())) return(.UNCACHEABLE)

    ## Child keys first: an uncacheable child makes the parent uncacheable,
    ## which is where upstream's exception would have propagated from.
    n_args <- length(.args(expr))
    child_keys <- integer(n_args)
    for (i in seq_len(n_args)) {
      k <- expr_key(.args(expr)[[i]], store)
      if (.is_uncacheable(k)) return(.UNCACHEABLE)
      child_keys[i] <- k
    }

    data <- get_data(expr)
    data_key <- if (is.null(data)) 0L else .hashable_value(data, store)
    if (.is_uncacheable(data_key)) return(.UNCACHEABLE)

    ## One crossing: memo re-check, signature build, intern, memo store.
    ## wrapper: .CseKeys__class_code(store, short_class_name(expr))
    ## wrapper: .CseKeys__key_node(store, expr_id, class_code, shape, data_key, child_keys)
    .Call(`_CVXR_CseKeys__key_node`, store, expr_id,
          .Call(`_CVXR_CseKeys__class_code`, store, short_class_name(expr)),
          as.integer(.shape(expr)), data_key, child_keys)
  } else {
    ## Not an Expression at all: refuse rather than risk reuse.
    .UNCACHEABLE
  }
}

# -- Constant keys ---------------------------------------------------
## CVXPY SOURCE: subexpr_cache.py lines 137-203
##
## Small values are keyed BY VALUE so that two structurally identical user
## expressions embedding distinct Constant objects with equal data still merge
## -- e.g. each `huber(x)` mints a fresh `Constant(0.5)` for the default `M`,
## which would otherwise defeat the whole point. Large values key by identity
## (`expr@id`) rather than copying problem data into a key.
##
## Values are keyed by their exact BIT PATTERN in the C++ store, which is the
## property `sprintf("%a")` was providing here before: equal doubles always
## produce equal keys and unequal ones never collide, with no precision to
## choose. It is also 16.8x cheaper (13.1us -> 0.78us for 50 doubles), because
## no string is built at all. Behavior is unchanged on every case that
## distinguishes an implementation -- NA_real_ vs NaN distinct, a computed NaN
## merging with the NaN constant, +0 vs -0 distinct -- all verified against the
## old `%a` keys in test-cse-keys.R.

.CONSTANT_VALUE_HASH_MAX_SIZE <- 64L   # subexpr_cache.py line 137

.constant_key <- function(expr, store) {
  expr_id <- .id(expr)
  value <- value(expr)
  if (is.null(value))
    ## wrapper: .CseKeys__intern_ints(store, expr_id, .CSE_TAG_CONST_ID, expr_id)
    return(.Call(`_CVXR_CseKeys__intern_ints`, store, expr_id,
                 .CSE_TAG_CONST_ID, expr_id))

  if (inherits(value, "sparseMatrix"))
    return(.sparse_constant_key(expr, value, store))

  if (length(value) <= .CONSTANT_VALUE_HASH_MAX_SIZE && is.numeric(value))
    ## wrapper: .CseKeys__intern_doubles(store, expr_id, tag, x, dims)
    return(.Call(`_CVXR_CseKeys__intern_doubles`, store, expr_id,
                 .CSE_TAG_CONST_VAL, as.numeric(value),
                 as.integer(dim_or_length(value))))

  ## wrapper: .CseKeys__intern_ints(store, expr_id, .CSE_TAG_CONST_ID, expr_id)
  .Call(`_CVXR_CseKeys__intern_ints`, store, expr_id, .CSE_TAG_CONST_ID, expr_id)
}

## CVXPY SOURCE: subexpr_cache.py lines 175-202
## Sparse values are keyed from sparse storage, never densified
## ([[feedback_no_densify_resparsify]]): small ones by their canonical triplets,
## large ones by identity.
.sparse_constant_key <- function(expr, value, store) {
  expr_id <- .id(expr)
  if (Matrix::nnzero(value) <= .CONSTANT_VALUE_HASH_MAX_SIZE) {
    tri <- Matrix::summary(methods::as(value, "CsparseMatrix"))
    ord <- order(tri$j, tri$i)
    ## wrapper: .CseKeys__intern_sparse(store, expr_id, tag, i, j, x, dims)
    return(.Call(`_CVXR_CseKeys__intern_sparse`, store, expr_id, .CSE_TAG_SPARSE_VAL,
                 as.integer(tri$i[ord]), as.integer(tri$j[ord]),
                 as.numeric(tri$x[ord]), as.integer(dim(value))))
  }
  ## wrapper: .CseKeys__intern_ints(store, expr_id, .CSE_TAG_CONST_ID, expr_id)
  .Call(`_CVXR_CseKeys__intern_ints`, store, expr_id, .CSE_TAG_CONST_ID, expr_id)
}

# -- get_data() payload ----------------------------------------------
## CVXPY SOURCE: subexpr_cache.py lines 205-222 (`_hashable_value`)
## Anything not recognised makes the subtree uncacheable, which is the
## conservative direction: a missed merge costs time, a wrong merge costs
## correctness.
##
## Payload keys are interned but NOT memoised by expression id (a payload is not
## a node), which is what `id = NA_integer_` signals to the store.
##
## COVERAGE IS A SUBSET, deliberately for now: anything not listed here disables
## caching for the whole enclosing subtree. That is the safe direction, but it
## also leaves merges on the table -- notably COMPLEX values, since
## `is.numeric()` is FALSE for complex, and likewise factors, raw, and non-sparse
## S4. A tag is only a disjoint integer, so widening this is cheap; tracked as a
## follow-up rather than folded into this change.

.hashable_value <- function(v, store) {
  if (is.null(v))
    ## wrapper: .CseKeys__intern_ints(store, NA_integer_, .CSE_TAG_NULL, integer(0))
    return(.Call(`_CVXR_CseKeys__intern_ints`, store, NA_integer_,
                 .CSE_TAG_NULL, integer(0)))
  if (is.list(v)) {
    parts <- integer(length(v))
    for (i in seq_along(v)) {
      p <- .hashable_value(v[[i]], store)
      if (.is_uncacheable(p)) return(.UNCACHEABLE)
      parts[i] <- p
    }
    ## wrapper: .CseKeys__intern_ints(store, NA_integer_, .CSE_TAG_LIST, parts)
    return(.Call(`_CVXR_CseKeys__intern_ints`, store, NA_integer_,
                 .CSE_TAG_LIST, parts))
  }
  if (.s7_is(v, Expression)) {
    k <- expr_key(v, store)
    if (.is_uncacheable(k)) return(.UNCACHEABLE)
    ## wrapper: .CseKeys__intern_ints(store, NA_integer_, .CSE_TAG_EXPR, k)
    return(.Call(`_CVXR_CseKeys__intern_ints`, store, NA_integer_,
                 .CSE_TAG_EXPR, k))
  }
  if (is.character(v))
    ## wrapper: .CseKeys__intern_strings(store, NA_integer_, .CSE_TAG_CHR, v)
    return(.Call(`_CVXR_CseKeys__intern_strings`, store, NA_integer_,
                 .CSE_TAG_CHR, v))
  if (is.logical(v))
    ## wrapper: .CseKeys__intern_ints(store, NA_integer_, .CSE_TAG_LGL, as.integer(v))
    return(.Call(`_CVXR_CseKeys__intern_ints`, store, NA_integer_,
                 .CSE_TAG_LGL, as.integer(v)))
  if (is.numeric(v))
    ## wrapper: .CseKeys__intern_doubles(store, NA_integer_, tag, x, dims)
    return(.Call(`_CVXR_CseKeys__intern_doubles`, store, NA_integer_,
                 .CSE_TAG_NUM, as.numeric(v), as.integer(dim_or_length(v))))
  if (inherits(v, "sparseMatrix")) {
    tri <- Matrix::summary(methods::as(v, "CsparseMatrix"))
    ord <- order(tri$j, tri$i)
    ## wrapper: .CseKeys__intern_sparse(store, NA_integer_, tag, i, j, x, dims)
    return(.Call(`_CVXR_CseKeys__intern_sparse`, store, NA_integer_, .CSE_TAG_SPARSE,
                 as.integer(tri$i[ord]), as.integer(tri$j[ord]),
                 as.numeric(tri$x[ord]), as.integer(dim(v))))
  }
  .UNCACHEABLE
}

## Shape of a value for keying: dim() when it has one, length() otherwise, so a
## 1x3 and a 3x1 holding the same numbers never key alike.
dim_or_length <- function(v) {
  d <- dim(v)
  if (is.null(d)) length(v) else d
}