Implementation selection#
Several performance-critical algorithms in Shamrock ship with more than one concrete implementation (e.g. a portable fallback vs. a backend-specific accelerated kernel, or several kernel strategies tuned for different problem sizes). Implementation selection is the mechanism that lets you list the implementations available for such an algorithm, query the one currently active, and switch it at runtime, from Python, without recompiling.
This page documents both sides of it: how to use it as a user (e.g. for benchmarking, or to work around a bad implementation on a given platform), and how to wire a new algorithm into it as a developer.
Current status#
Implementation selection is built on shamalgs::ImplVariantGlobal
(shamalgs/include/shamalgs/ImplVariant.hpp), a std::variant-based selector. This is the
pattern to use for any algorithm that needs implementation selection, whether new or being added
to an existing one.
User side (Python)#
Every algorithm that supports implementation selection is registered under a name (e.g.
"reduction", "scan_exclusive_sum_in_place", "clbvh_dual_tree_traversal"). The following
six functions are exposed under shamrock.algs, and all except get_registered_algs take that
name as their first argument alg:
get_registered_algs(): the sorted list of registered algorithm names.get_default_impl_list(alg): the list of available implementations.get_current_impl(alg): the implementation currently selected.set_impl(alg, impl): select an implementation.is_impl_set(alg): whether an implementation has been selected yet.autoselect_impl(alg): select the algorithm’s default implementation.
An unknown alg raises an exception whose message lists the registered names. The same
functions cover every algorithm, including shamtree’s dual tree traversal.
import shamrock
print(shamrock.algs.get_registered_algs())
# ['clbvh_dual_tree_traversal', 'compute_histogram', 'is_all_true', 'reduction', ...]
Implementations are plain JSON config strings of the form
{"implementation": "<name>", "parameters": {...}}. set_impl takes that whole string back.
is_impl_set and autoselect_impl matter because an algorithm starts with no implementation
selected: it only picks its default the first time it actually runs, so get_current_impl(alg)
returns "null" until then, unless you call autoselect_impl(alg) yourself first. From Python,
the default is picked for the compute device (shamsys::instance::get_compute_scheduler_ptr()),
so autoselect_impl requires the devices to be initialized (shamrock.sys.init(...) in library
mode). The other functions also work before that.
import shamrock
current = shamrock.algs.get_current_impl("scan_exclusive_sum_in_place")
print(current)
# null (nothing selected yet, and the algorithm hasn't run)
# two ways of selecting an implementation manually:
# 1. pick a specific one
shamrock.algs.set_impl(
"scan_exclusive_sum_in_place", '{"implementation":"std_scan","parameters":{}}'
)
# 2. or fall back to the algorithm's own default
if not shamrock.algs.is_impl_set("scan_exclusive_sum_in_place"):
shamrock.algs.autoselect_impl("scan_exclusive_sum_in_place")
If you want to test something against every available implementation, do:
import json
import shamrock
for impl in shamrock.algs.get_default_impl_list("scan_exclusive_sum_in_place"):
shamrock.algs.set_impl("scan_exclusive_sum_in_place", impl)
name = json.loads(impl)["implementation"]
print(f"running with {name}")
# ...
Where this is used in practice#
The benchmark scripts under examples/benchmarks/ sweep over every available implementation of
an algorithm this way to compare their performance: run_segmented_sort_in_place_performance.py,
run_exclusive_scan_in_place.py.
The C++ unit tests for these algorithms follow the same loop, to run every implementation against
the same reference data (see e.g. tests/shamalgs/primitives/scan_exclusive_sum_in_placeTests.cpp).
Selection is process-wide and does not persist: it resets to the algorithm’s default every time the process restarts.
Developer side (C++)#
Adding implementation selection to a new algorithm#
Use shamalgs::ImplVariantGlobal, documented in detail in
shamalgs/include/shamalgs/ImplVariant.hpp. Each implementation is a small tag struct exposing a
variant_type_name; the selector is a std::variant of those, and dispatch is a plain
std::visit. Skeleton, following scan_exclusive_sum_in_place.cpp as a reference:
#include "shambase/overloaded.hpp"
#include "shamalgs/ImplVariant.hpp"
#include "shamalgs/impl_registry.hpp"
#include "shambackends/DeviceScheduler.hpp"
namespace shamalgs::primitives {
namespace impl {
/// One-line doc per alternative: what it does / when it's a good fit
struct AltA {
static constexpr std::string_view variant_type_name = "alt_a";
};
struct AltB {
static constexpr std::string_view variant_type_name = "alt_b";
};
/// Registry name, shared by the registration and the dispatch site(s)
constexpr std::string_view my_algo_impl_name = "my_algo";
/// The lambda picks the default implementation, it may inspect the device behind
/// the scheduler or ignore it
shamalgs::ImplVariantGlobal<AltA, AltB> my_algo_impl{
[](const sham::DeviceScheduler_ptr &, auto &self) {
self.set(AltA{});
}};
// Must come after the global it registers: same TU, so it is initialized after it
SHAMALGS_REGISTER_IMPL(my_algo_impl_name, my_algo_impl);
} // namespace impl
void my_algo(const sham::DeviceScheduler_ptr &dev_sched, ...) {
// Lazy default on first use, if no implementation was selected yet
if (!impl::my_algo_impl.is_set()) {
shamalgs::impl_registry::autoselect_impl(impl::my_algo_impl_name, dev_sched);
}
std::visit(
shambase::overloaded{
[&](impl::AltA) { /* ... */ },
[&](impl::AltB) { /* ... */ },
},
impl::my_algo_impl.get());
}
} // namespace shamalgs::primitives
ImplVariantGlobal starts unset — is_set() is false until something selects an
implementation — but the rule picking its default is given at construction, as a callable of
signature void(const sham::DeviceScheduler_ptr &, ImplVariantGlobal &) that calls set() on the
selector it is handed. autoselect(dev_sched) runs it. Both is_set() and autoselect() are part
of the non-template shamalgs::IImplVariant interface, so code holding a selector type-erased can
also check and fill it in. The lazy-default pattern above (check is_set(), autoselect right
before dispatching) is what every algorithm currently does.
SHAMALGS_REGISTER_IMPL (shamalgs/include/shamalgs/impl_registry.hpp) registers the selector
in shamalgs::impl_registry under its name, at static initialization. Put it at namespace scope
in the .cpp file, right after the selector’s definition: objects of one translation unit are
initialized in definition order, so the selector is already constructed when it registers.
Registering the same name twice throws. The selector must be a non-inline global defined in a
single .cpp file (declare it extern in the header if a header-only dispatch needs it, as
compute_histogram.hpp does), and ImplVariantGlobal is neither copyable nor movable since the
registry stores its address. The registry then reads and changes the selection of every
algorithm by name, purely through IImplVariant; it is also what the Python bindings and the
unit tests use, so an algorithm needs no selection function of its own.
Dispatch sites keep the direct is_set() / get() access on the typed global, which
std::visit needs, but autoselect through shamalgs::impl_registry::autoselect_impl rather than
calling my_algo_impl.autoselect(...) directly, so that every default selection goes through
the registry (which also logs it). The registry lookup only happens on first use.
autoselect_impl always takes the sham::DeviceScheduler_ptr the algorithm runs on, and
forwards it to the selector’s autoselect (it throws if the scheduler is null). Most lambdas
ignore it, because the default only depends on compile-time information (a #ifdef
backend/platform check, e.g. scan_exclusive_sum_in_place’s). When the default depends on the
device, the lambda looks at it. compute_histogram does this: a GPU device picks a different
default than a CPU one (compute_histogram.cpp).
ComputeHistogramImpl compute_histogram_impl{
[](const sham::DeviceScheduler_ptr &dev_sched, auto &self) {
if (dev_sched->ctx->device->prop.type == sham::DeviceType::GPU) {
self.set(GpuOversubscribe{});
} else {
self.set(NaiveGpu{});
}
}};
SHAMALGS_REGISTER_IMPL(compute_histogram_impl_name, compute_histogram_impl);
The dispatching function passes its own scheduler (or buf.get_dev_scheduler_ptr() when it only
gets buffers). The Python binding shamrock.algs.autoselect_impl(alg) and the unit tests supply
the compute scheduler explicitly:
shamalgs::impl_registry::autoselect_impl(
"compute_histogram", shamsys::instance::get_compute_scheduler_ptr());
An alternative with tunable fields specializes shamalgs::ImplVariantParams<Alt> to control how
those fields serialize to/from the "parameters" JSON — see the doc comment at the top of
ImplVariant.hpp for a worked example (a group_size field), or
shamalgs::primitives::impl::AtomicEarlyExit in is_all_true.cpp for a real one.
Exposing more than one default per alternative#
By default, get_default_impl_list(alg) lists exactly one instance per alternative type
(the default-constructed one). An alternative with tunable fields can opt into listing several
of its own instances instead — e.g. the same kernel at a few different group sizes — by adding a
static variant_custom_defaults() method returning a std::vector<Alt>:
struct AtomicEarlyExit {
static constexpr std::string_view variant_type_name = "atomic_early_exit";
u32 group_size = 256;
static std::vector<AtomicEarlyExit> variant_custom_defaults() {
return {AtomicEarlyExit{128}, AtomicEarlyExit{256}};
}
};
ImplVariantGlobal/get_default_config_list() detects this automatically (via the
HasCustomDefaults concept in ImplVariant.hpp) and lists one config string per returned
instance instead of just one; alternatives that don’t define variant_custom_defaults() are
unaffected. Because all of them still share the same variant_type_name, only "parameters"
tells them apart in the resulting config strings, so any code keying results off
json.loads(impl)["implementation"] alone (see the benchmark script note below) needs to fold
"parameters" into the key too, or entries collide.
Once the selector, its registration and the dispatch are in place, wire it up end to end:
Header: nothing to declare for implementation selection. The selector, its name constant and its registration all live in the
.cppfile (only a header-only dispatch, likecompute_histogram’s, needs the selector declaredexternand the name constant in the header).Python bindings: nothing to add.
shamrock.algs.get_registered_algs()lists the new name, and the name-keyed functions ofshamrock.algsalready cover it.Unit test: autoselect if
shamalgs::impl_registry::is_impl_set("<algo>")isfalse, saveget_current_impl("<algo>"), loop overget_default_impl_list("<algo>")callingset_impl("<algo>", impl)before each run, then restore the saved implementation.Benchmark script (
examples/benchmarks/, if one exists for the algorithm): same loop throughshamrock.algs, extracting the implementation’s display name withjson.loads(impl)["implementation"]; callshamrock.algs.autoselect_impl("<algo>")first whenshamrock.algs.is_impl_set("<algo>")isFalse.