Hi all,
I want to share some benchmark results from the ongoing homogeneous-ravel
work in GNU APL 2.0. The short version: scalar comparison functions are
now 20–43× faster on large numeric arrays, and ⌈/⌊ are ~19× faster on
integer arrays. Note that the SVN numbers in the report below are my
local ones, not those in Savannah.
Background
----------
GNU APL 2.0 introduced "packed ravels": when an array has more than 12
elements and all cells are the same numeric type, the ravel is stored as
a flat C array of the native type (int64_t, double, etc.) rather than as
an array of 24-byte Cell objects. Six RavelType tags cover the cases:
*
RPT_CELLS — default, 24 bytes/element (Cell objects)
RPT_BOOL — 1 bit/element (bit-packed uint64_t words)
RPT_UNICODE16 — 2 bytes/element (UCS-2 characters)
RPT_UNICODE32 — 4 bytes/element (Unicode characters)
RPT_INT64 — 8 bytes/element (int64_t integers)
RPT_FLOAT64 — 8 bytes/element (double floats)
RPT_COMPLEX — 16 bytes/element (complex<double>)*
The previous release already had a FLOAT64→FLOAT64 fast path for + −
× ⌈ ⌊.
This round adds:
*
(a) INT64→INT64 fast path for ⌈ and ⌊ (max/min — overflow-safe)
(b) INT64→BOOL fast path for = ≠ < ≤ > ≥ (all six comparisons)
(c) FLOAT64→BOOL fast path for = ≠ < ≤ > ≥*
Note: + − × on INT64 are deliberately excluded because int64_t can
overflow; APL requires promotion to float in that case.
Test method
-----------
Platform: x86-64 Linux, single core
Compiler: GCC with -O2
Arrays: 1 000 000 elements, RPT_INT64 and RPT_FLOAT64 packing
confirmed
Timing uses the CPU cycle counter (*⎕FIO ¯1,* which calls *RDTSC*).
Each measurement is the minimum of three warmed runs, expressed as
cycles per element (lower is better).
Arrays were constructed so that packing actually fires:
AI_cell ← ⍳N ⍝ starts as RPT_CELLS (iota does not pack)
AI64 ← AI_cell + 0 ⍝ scalar + forces try_pack → RPT_INT64
AF64 ← AI_cell × 1.0
Comparison result arrays are *RPT_BOOL* (bit-packed output).
Results
-------*
Operation │ r3355 baseline │ r3357 current │ speedup
│ cycles/elem │ cycles/elem │
──────────────────────┼────────────────┼───────────────┼─────────
INT64 ⌈ (max) │ 20.4 │ 1.1 │ ~19×
INT64 ⌊ (min) │ 20.4 │ 1.1 │ ~19×
INT64 = │ 21.0 │ 0.5 │ ~42×
INT64 ≠ │ 21.0 │ 0.5 │ ~42×
INT64 < │ 21.0 │ 0.5 │ ~42×
INT64 ≤ │ 21.0 │ 0.5 │ ~42×
INT64 > │ 21.0 │ 0.5 │ ~42×
INT64 ≥ │ 21.0 │ 0.5 │ ~42×
──────────────────────┼────────────────┼───────────────┼─────────
FLOAT64 = │ 21.0 │ 0.5 │ ~42×
FLOAT64 ≠ │ 21.0 │ 0.5 │ ~42×
FLOAT64 < │ 21.0 │ 0.5 │ ~42×
FLOAT64 ≤ │ 21.0 │ 0.5 │ ~42×
FLOAT64 > │ 21.0 │ 0.5 │ ~42×
FLOAT64 ≥ (with ⎕CT) │ 21.5 │ 1.0 │ ~22×
──────────────────────┼────────────────┼───────────────┼─────────
INT64 + − × │ 21.0 │ 21.0 │ 1×
FLOAT64 + − × │ 1.1 │ 1.1 │ 1×
(FLOAT64 +−× fast path existed before r3355; INT64 excluded by
design)*
How the fast paths work
-----------------------
For each dyadic scalar function that supports a fast path, the subclass
overrides a virtual hook that returns a typed function pointer:
typedef ErrorCode (*vv_i2b_t)(uint64_t * Z,
const int64_t * A, const int64_t * B,
ShapeItem count);
The dispatch block in ScalarFunction::eval_VV() detects matching
RavelType tags, calls the hook, and if non-null runs the tight C++ loop
directly on the raw storage. For BOOL output the result is written as
bit-packed words and finalised with commit_ravel_Bool().
The ≥ comparison on *FLOAT64* uses ⎕CT (comparison tolerance), which
explains its slightly higher cost compared to the exact comparisons.
Planned: character fast path
-----------------------------
*RPT_UNICODE16* packs 4 characters per 64-bit word. An XOR-based approach
for = and ≠ should reduce flat-string comparison from the current
~80 cycles/element down to approximately 4 cycles/element (~20×).
That work is queued for the next round.
Best Regards,
Jürgen
committed to SVN, version now *2032*.
