Algorithm-Classifier-IsolationForest
view release on metacpan or search on metacpan
How to Apply These Terms to Your New Libraries
If you develop a new library, and you want it to be of the greatest
possible use to the public, we recommend making it free software that
everyone can redistribute and change. You can do so by permitting
redistribution under these terms (or, alternatively, under the terms of the
ordinary General Public License).
To apply these terms, attach the following notices to the library. It is
safest to attach them to the start of each source file to most effectively
convey the exclusion of warranty; and each file should have at least the
"copyright" line and a pointer to where the full notice is found.
<one line to give the library's name and a brief idea of what it does.>
Copyright (C) <year> <name of author>
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
benchmarking/BenchAccel.pm view on Meta::CPAN
# microseconds per call) OpenMP thread scheduling is non-deterministic
# enough that a single 2-second window can land in a slow stretch and
# report ~30x lower throughput than steady state; median across
# windows smooths that without spending extra time.
sub wall_rate {
my ( $code, $secs ) = @_;
$secs ||= 1;
# Warm-up: at least 0.3 s (matches the original Perl bench() helper
# this replaced) so OpenMP thread pools are firmly hot before any
# measurement window starts. Scales up for long budgets -- a 30 s
# measurement gets a 3 s warmup.
my $warmup = $secs * 0.1;
$warmup = 0.3 if $warmup < 0.3;
my $wt0 = time;
$code->() while time - $wt0 < $warmup;
my $WINDOWS = 3;
my $win_secs = $secs / $WINDOWS;
my @rates;
for ( 1 .. $WINDOWS ) {
benchmarking/bench-fit.pl view on Meta::CPAN
#
# Benchmarks the fit() method across five dimensions:
# 1. n_trees -- number of isolation trees
# 2. sample_size/psi -- sub-sample size used to build each tree
# 3. dataset size -- number of training samples
# 4. feature count -- dimensionality (wide range: 2, 5, 10, 20, 50)
# 5. feature count -- fine-grained 2–10 columns
#
# Each section uses BenchAccel::wall_cmpthese so results include both the raw
# rate (fits/sec) and relative %-difference between variants.
# Data generation is done before timing starts.
#
# Run with:
# perl -Ilib benchmarking/bench-fit.pl
use strict;
use warnings;
use lib '../lib';
use FindBin;
use lib "$FindBin::Bin";
use BenchAccel qw(wall_cmpthese);
benchmarking/bench-sklearn-scoring.pl view on Meta::CPAN
# * query-set size (fixed feature count)
# * feature-vector width (fixed query-set size)
#
# Perl backends benchmarked (when available):
# pure perl -- no Inline::C (use_c => 0)
# C serial -- Inline::C, single-threaded (use_c => 1, use_openmp => 0)
# C+OpenMP -- Inline::C + OpenMP parallel (use_c => 1, use_openmp => 1)
#
# The same training CSV and query CSVs are used by all sides so the
# comparison is on identical data. Models are pre-trained before any
# timing starts.
#
# Method correspondence:
# Perl score_samples <--> clf.score_samples(X) (same formula, opposite sign)
# Perl predict <--> clf.predict(X) (same semantics, 0/1 vs -1/+1)
# Perl score_predict_samples <--> (no sklearn equivalent)
# Perl score_predict_split <--> (no sklearn equivalent)
# Perl path_lengths <--> (no sklearn equivalent)
# (no Perl equivalent) <--> clf.decision_function(X) (threshold-shifted score)
#
# The ratio column shows sklearn ops/s / best-Perl ops/s.
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
}
if (type == 1) {
double fv = xi[(int)node[1]];
ni = (fv < node[2]) ? (int)node[3] : (int)node[4];
} else {
int coff = (int)node[1], nf = (int)node[2];
double b = node[5], dot = 0.0;
const double *val_p = vco + (size_t)coff;
/* Both children are known before the dot product resolves
* which one gets taken, so start pulling their records in
* now and let the FMA loop below hide the latency. One of
* the two prefetches is always wasted -- affordable here
* on the oblique path, where there is real work to hide it
* under, but not on the axis path, whose single compare
* resolves immediately. */
const int li = (int)node[3], ri = (int)node[4];
IF_PREFETCH(nd + (size_t)li * IF_NZ);
IF_PREFETCH(nd + (size_t)ri * IF_NZ);
if (nf == n_feats) {
/* Dense oblique split: this node uses every feature,
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
* SV allocator isn't safe to call from multiple OS threads sharing one
* interpreter without a lock that would just serialise everything
* anyway.
*
* So this builder trades the bit-identical guarantee for real thread
* parallelism: each tree gets its own splitmix64 PRNG stream, seeded
* from a tree index (not thread id or scheduling order), so results
* are still reproducible for a fixed seed and n_trees regardless of
* OMP_NUM_THREADS -- just different from what build_forest_xs or the
* pure-Perl path would produce for the same seed. The one Drand01()
* call in this function happens before the parallel region starts
* (single-threaded), so the result still varies with the model's
* `seed` the way every other code path does; it isn't used inside the
* parallel loop.
*
* Each tree is built entirely with plain C data (row-index int arrays,
* a growable TreeBuf of packed doubles/ints) -- no Perl API call
* happens anywhere inside the parallel region. Each node record in
* TreeBuf uses _pack_tree's 6-double SoA layout (see the file-top
* comment), but the node ORDER differs: records are appended
* post-order (a node is pushed after both its children, since child
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
size_t newcap = b->cap_nodes ? b->cap_nodes * 2 : 64;
b->nodes = (double*)realloc(b->nodes, newcap * 6 * sizeof(double));
b->cap_nodes = newcap;
}
slot = b->nodes + b->n_nodes * 6;
slot[0] = f0; slot[1] = f1; slot[2] = f2;
slot[3] = f3; slot[4] = f4; slot[5] = f5;
return (int)(b->n_nodes++);
}
/* Appends n (idx[k], val[k]) pairs and returns the offset they start
* at -- the `coff` an oblique node record stores. */
static int tb_push_coef(TreeBuf *b, const int *idx, const double *val,
int n) {
int off = (int)b->n_idx;
if (b->n_idx + (size_t)n > b->cap_idx) {
size_t newcap = b->cap_idx ? b->cap_idx * 2 : 64;
if (newcap < b->n_idx + (size_t)n) newcap = b->n_idx + (size_t)n;
b->idx = (int*)realloc(b->idx, newcap * sizeof(int));
b->cap_idx = newcap;
}
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
nodes_av = (AV*)SvRV(nodes_rv);
idx_av = (AV*)SvRV(idx_rv);
val_av = (AV*)SvRV(val_rv);
av_clear(nodes_av); av_clear(idx_av); av_clear(val_av);
if (n_trees > 0) {
av_extend(nodes_av, n_trees - 1);
av_extend(idx_av, n_trees - 1);
av_extend(val_av, n_trees - 1);
}
/* Single Drand01() call, before the parallel region starts, so it's
* still a plain serial call into the interpreter's RNG state. */
base_seed = (uint64_t)(Drand01() * 18446744073709551615.0);
bufs = (TreeBuf*)malloc((size_t)n_trees * sizeof(TreeBuf));
for (t = 0; t < n_trees; t++) tb_init(&bufs[t]);
#ifdef _OPENMP
#pragma omp parallel for schedule(dynamic) if(use_openmp)
#endif
for (int t = 0; t < n_trees; t++) {
/* Seeded from the tree index, not thread id or iteration order,
* so the mapping from tree -> RNG stream is independent of
* OMP_NUM_THREADS / scheduling. sm64_next() mixes once more so
* adjacent tree indices (which differ by one golden-ratio step)
* don't start from too-similar states. */
uint64_t rng = base_seed + (uint64_t)t * 0x9E3779B97F4A7C15ULL;
rng = sm64_next(&rng);
int *all = (int*)malloc((size_t)n_pts * sizeof(int));
int *sample;
int i;
for (i = 0; i < n_pts; i++) all[i] = i;
for (i = 0; i < psi; i++) {
int j = i + (int)(sm64_drand(&rng) * (n_pts - i));
int tmp = all[i]; all[i] = all[j]; all[j] = tmp;
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
for (f = 0; f < n_feats; f++) {
SV** v = av_fetch(row, f, 0);
if (v && *v && SvOK(*v)) {
dvec_push(&cols[f], SvNV(*v));
}
}
}
/* Validate every column before freeing anything: croak() longjmps
* out of this function, so any cleanup loop reachable after a
* partial computation has already started (and already freed some
* cols[i].v) risks a double free on those same pointers. Checking
* all columns up front, before the computation loop below frees
* anything, avoids that entirely. Matches the Perl fallback's
* behaviour of reporting the first empty column in feature order. */
for (f = 0; f < n_feats; f++) {
if (cols[f].n == 0) {
int col = f;
for (i = 0; i < n_feats; i++) free(cols[i].v);
free(cols);
croak("impute: feature column %d has no present values", col);
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
# whose different rounding breaks the documented guarantee that
# use_c => 1 and use_c => 0 build bit-identical trees (one ulp in a
# split value cascades into a structurally different tree). The
# -march speedup comes from AVX2 vectorization, not contraction,
# so this costs little (verified against the fit-determinism and
# scoring-parity tests).
my $opt_level = $opt;
$opt_level .= " -march=$arch -ffp-contract=off" if length $arch;
# IF_NO_OPENMP=1 forces the serial C build: the OpenMP compile attempt
# is skipped, so the object has no libgomp linkage and never starts an
# OpenMP runtime in the process. Distinct from OMP_NUM_THREADS=1,
# which runs the parallel code on a single thread but still loads
# libgomp. An explicit IF_NO_OPENMP=0 re-enables OpenMP over a
# no-openmp configure-time default.
my $no_omp
= defined $ENV{IF_NO_OPENMP}
? ( $ENV{IF_NO_OPENMP} ? 1 : 0 )
: $def_no_omp;
# The prebuilt object is only trusted when the effective flags match
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
this changes which trees get built) and only takes effect when C<use_c>
is also on and OpenMP is linked in.
=back
These two do NOT compose, despite both existing to parallelise fit().
A process that has run any OpenMP region -- including plain
C<score_samples()>/C<predict()> with the default C<use_openmp> -- and
then C<fork()>s (as C<parallel_fit> does) hands each child a copy of
libgomp's thread pool whose worker threads did not survive the fork. A
child that then starts its own C<#pragma omp parallel> region (as
C<use_openmp_fit> would) tries to reuse that now-invalid pool and
hangs. This is a general limitation of combining C<fork()> with OpenMP,
not something fixable from Perl, so C<parallel_fit>'s forked workers
always use the single-threaded C builder regardless of
C<use_openmp_fit> -- setting both just means C<parallel_fit> wins and
C<use_openmp_fit> has no effect for that call.
Detection happens once when the module is loaded. When the
distribution was installed with C<Inline::C> available, the C backend
was already compiled during C<make> and the installed object is loaded
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
benchmark with C<iforest bench> before assuming) while avoiding the
C<-march=native> caveats described under L</Tuning the C build>.
Bit-for-bit result parity with the pure-Perl backend is preserved
either way (see C<IF_ARCH> below).
The C<IF_*> build flags described below are captured when
C<perl Makefile.PL> runs -- set them in the environment of I<that>
command, not of C<make> -- and recorded in the generated
C<Algorithm::Classifier::IsolationForest::BuildFlags> module, which
thereby also fixes what the prebuilt object was compiled with. At run
time the recorded values serve as the defaults, so a process started
with no C<IF_*> variables set uses the prebuilt object as-is.
Setting C<IF_*> variables at run time keeps working exactly as in
releases without prebuilt support: if the requested flags differ from
the recorded ones, the prebuilt object (compiled with the wrong flags
for the request) is skipped and the module compiles at first load into
C<_Inline/> -- which does need C<Inline::C> and a compiler on that
machine. Two related knobs exist:
=over 4
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
a machine you don't control exclusively (a shared build host, a
container base image): blanket C<-march=native> pulls in whatever
instruction sets the build host happens to have, including AVX-512 on
some Intel CPUs -- which is known to trigger clock throttling under
sustained heavy use and can make throughput I<worse> than a
conservative target like C<x86-64-v3> (AVX2, no AVX-512). If in doubt,
benchmark both before committing to one.
=item * C<IF_NO_OPENMP=1> -- build (or select) the serial C backend: the
OpenMP compile attempt is skipped entirely, so the resulting object has
no libgomp linkage and never starts an OpenMP runtime inside the
process. This differs from C<OMP_NUM_THREADS=1>, which merely runs the
parallel code on one thread but still loads libgomp. Set at
C<perl Makefile.PL> time it yields a serial prebuilt object; set at run
time against an OpenMP prebuilt install it triggers a runtime serial
build (needing a compiler). An explicit C<IF_NO_OPENMP=0> re-enables
OpenMP over a serial configure-time default.
=back
Whichever of these are used, the cached artefact under C<_Inline/> is
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
- use_openmp_fit :: boolean, build fit()'s trees across OpenMP threads
(one tree per thread) instead of the single-threaded C builder.
Opt-in and off by default: unlike use_c/use_openmp, this changes
which trees get built. Perl's RNG isn't safe to call from
multiple OS threads sharing one interpreter, so this path seeds
an independent PRNG per tree from the tree index rather than
Drand01() -- trees differ from the use_c (single-threaded)
and pure-Perl paths even with the same seed, though a fixed
seed and n_trees still reproduce the same trees regardless of
OMP_NUM_THREADS or scheduling. Does NOT compose with
parallel_fit: a forked child starting its own OpenMP region
after the parent process has used OpenMP for anything can
hang (a general fork()+libgomp limitation), so parallel_fit's
workers always use the single-threaded C builder regardless
of this setting -- setting both just means parallel_fit wins.
Ignored (clamped to 0) when use_c is false or OpenMP isn't
linked in.
default :: 0
- feature_names :: optional arrayref of per-feature labels enabling the
*_tagged methods (and required by mungers below).
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
binmode $wh;
if ( defined $self->{seed} ) {
srand( $self->{seed} + $w * 1009 );
}
# Deliberately never _build_forest_openmp here, even when
# use_openmp_fit is on: if this process (or the parent that
# fork()ed us) already ran any OpenMP region before this
# fork -- including plain score_samples()/predict() with
# the default use_openmp -- libgomp's thread pool exists
# but its worker threads didn't survive the fork. A child
# starting its own #pragma omp parallel region then tries
# to reuse that now-invalid pool and hangs. This is a
# general fork()+libgomp limitation, not fixable from here,
# so forked workers always use the single-threaded C
# builder (or pure Perl) instead. See t/03-fit-determinism.t
# and the NATIVE ACCELERATION docs for the observed hang and
# why parallel_fit + use_openmp_fit isn't composed for real.
my $trees;
if ( $self->{_use_c} ) {
$trees = $self->_build_forest_c( $data, $psi, $limit, $share );
} else {
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
# random draws come from a thread-private PRNG seeded per tree index
# rather than Drand01() -- Perl's RNG state can't be shared safely
# across OpenMP threads -- so the resulting trees are NOT bit-identical
# to the use_c (serial) or pure-Perl paths for the same seed, though a
# fixed seed + n_trees still reproduce the same trees regardless of
# OMP_NUM_THREADS. This is why it's gated by the separate, opt-in
# use_openmp_fit knob rather than reusing use_c/use_openmp.
#
# Only called from fit()'s non-forked branch. _fit_trees_parallel's
# workers never call this, even when use_openmp_fit is on: a forked
# child starting its own OpenMP region after the parent process has
# used OpenMP for anything (this includes plain score_samples()) can
# hang -- see the comment above that branch for the fork()+libgomp
# hazard this avoids.
#
# build_forest_openmp_xs hands back three arrayrefs of per-tree packed
# buffers (the same SoA layout _pack_tree produces) instead of Perl tree
# structures -- that's how it avoids any Perl API call inside its
# parallel region. _unpack_forest converts them back into the ordinary
# nested-arrayref tree shape so to_json/from_json/_rebuild_c_trees don't
# need to know this path exists.
t/03-fit-determinism.t view on Meta::CPAN
# Drand01(), the same generator Perl's own rand()/srand() use.
# 3. use_openmp_fit is reproducible for a fixed seed + n_trees
# regardless of OMP_NUM_THREADS (checked across separate
# subprocesses, since that's the only way to force a different
# thread count) -- it deliberately does NOT match the Drand01-based
# backends (documented behaviour: it uses its own thread-safe PRNG),
# so that's checked as a "differs, but each is internally consistent"
# property rather than cross-backend equality.
# 4. use_openmp_fit + parallel_fit together is still safe and
# reproducible -- but does NOT actually run forked workers in
# OpenMP. A forked child starting its own OpenMP region after
# the parent process has used OpenMP for anything (including
# plain score_samples()) can hang -- a general fork()+libgomp
# limitation -- so parallel_fit's workers always use the
# single-threaded C builder regardless of use_openmp_fit. This
# was caught by an earlier version of this test hanging.
use strict;
use warnings;
use Test::More;
use File::Temp qw(tempfile);
t/03-fit-determinism.t view on Meta::CPAN
or diag("child output:\n$out4");
is( $out1, $out4, 'same seed + n_trees builds identical trees under OMP_NUM_THREADS=1 vs 4' );
}; ## end 'use_openmp_fit reproducibility does not depend on OMP_NUM_THREADS' => sub
# ------------------------------------------------------------------------
# 5. use_openmp_fit + parallel_fit together: must not hang, and must
# still be reproducible -- but see the file-top comment: parallel_fit's
# forked workers ignore use_openmp_fit and always use the
# single-threaded C builder, specifically BECAUSE a forked child
# starting its own OpenMP region after this same process has already
# run OpenMP (subtests 3/4 above did, via use_openmp_fit) can hang.
# This subtest runs deliberately late in the file, after use_openmp_fit
# has already executed in-process above, to exercise exactly that
# ordering.
# ------------------------------------------------------------------------
subtest 'use_openmp_fit + parallel_fit does not hang and is reproducible' => sub {
plan skip_all => 'no fork() on this platform'
unless $can_fork && $HAS_C && $HAS_OPENMP;
my %opts = (
( run in 0.589 second using v1.01-cache-2.11-cpan-9581c071862 )