Skip to content

Reduce pointer chasing overhead for evaluating slinky code #466

Description

@dsharlet

Currently, evaluating an expression requires following a pointer to a different allocation for every node. Something as simple as max(buffer_max(x, 1), 3) involves evaluating 5 nodes, each allocated by a separate new. There are bunch of options to make this better:

  • We could try "inlining" simple/common nodes like constant and variable into expr. expr would become something like std::variant<constant, variable, ref_count<const base_expr_node>> instead of ref_count<const base_expr_node> and relying on a separate allocation for constant and variable nodes.
  • Rather than changing the structure of the objects, we could just try to get more clever about allocating them. e.g. buffer_max(x, 1) could be just one allocation that is referenced by the 3 nodes (x, 1, buffer_max(., .)). This doesn't eliminate the pointer chasing, but it does mean that the dereferences are likely to be in the same cache line at least (which might be most of the benefit of eliminating pointer chasing).
    • I think this could be especially impactful for things like buffer_dim(x, y) = {buffer_min(x, y), buffer_max(x, y), buffer_stride(x, y), buffer_fold_factor(x, y)}: we could allocate just one object for all of these nodes. I think we could also try to recognize this is the case when interpreting, and skip evaluating all of the nodes in such expressions, which are common in make_buffer (Optimize evaluating buffer_bounds and buffer_dim #396).
  • constant and variable are just wrappers for integers. We could use a globally unique instance of these objects. We actually already do this for 0 and 1:

    slinky/runtime/expr_stmt.cc

    Lines 102 to 107 in 57ed1e3

    static const constant* zero = make_static_constant<0>();
    static const constant* one = make_static_constant<1>();
    if (value == 0) {
    return zero;
    } else if (value == 1) {
    return one;
    I tried expanding this to variables and more constants, but I couldn't measure much impact, so this may not be a very useful idea.

Metadata

Metadata

Assignees

Labels

No labels
No labels

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions