- Generated by
1.9.8
|
morton-arithmetic 0.1.0
Fast Morton (Z-order) codes with O(1) arithmetic
|
Where this library stands and what to do with it.
The v0.1 core plus the entire near/medium-term roadmap below is now implemented and tested (26 doctest cases, ~1.4M assertions; pytest; CI; docs); the v0.2→v0.3 additions (wide codes, packaging, release pipeline, octree split) are listed in "Done since v0.2" further down:
Morton<Dim, Bits>): BMI2 encode/decode with portable software fallback; O(1) per-axis inc/dec/add/sub, neighbor, set, Z-order ++/--, comparisons..github/workflows/ci.yml: gcc/clang/MSVC × {BMI2 on/off} × {Debug/Release} running ctest, plus a Python-version matrix and a Doxygen build. The software fallback is exercised on the BMI2=OFF cells.constexpr encode/decode/arithmetic** — selects the software path at compile time via __builtin_is_constant_evaluated() (works at C++17); see tests/test_constexpr.cpp for compile-time lookup-table construction.add_sat, sub_sat, try_add, try_sub clamp or refuse instead of wrapping.scikit-build-core; pip install . builds the extension and produces a proper wheel (peclet_morton-*.whl) with the .so bundled. (PyPI publishing still pending — see below.)docs/Doxyfile) + docs CMake target.__uint128_t storage where available, so 3D 32-bit (96-bit code) and 2D 64-bit (128-bit code) work; software encode/decode for >64 bits, native 128-bit arithmetic. Aliases Morton3D32, Morton2D64.morton/iterate.hpp exposes the full Tropf-Herzog pair (bigmin_in_box, litmax_in_box, litmax_bigmin), validated exhaustively against brute force.face_neighbors() (von Neumann), all_neighbors() (Moore, 3^Dim-1), ancestor/child/ child_index.octree/include/morton_octree/octree.hpp (split out into the sibling octree/ subproject): a linear octree/quadtree (std::map keyed by Morton origin) with point location, face neighbours and refinement expressed via the core arithmetic.morton/batch.hpp (add/sub/step/ encode2/encode3) auto-vectorises (AVX2 vpaddq/vpand/vpor). Profiling (benchmarks/bench_batch.cpp) confirms ~1.7× over scalar when cache-resident and memory-bound parity out of cache — exactly the predicted behaviour.morton/wide_uint.hpp provides a fixed-width word-array unsigned (+ - & | ^ ~ << >>, comparisons) so Morton<Dim,Bits> works unchanged up to MORTON_MAX_BITS (default 256; raise to go wider). Tested for 192-bit (Morton<3,64>) and 256-bit (Morton<2,128>) codes on both the BMI2 and software paths.find_package(morton) → morton::morton), verified by an external consumer build. Conan recipe (conanfile.py) and a vcpkg port (packaging/vcpkg/morton/).cibuildwheel config + .github/workflows/ release.yml (manylinux/musllinux/macOS/Windows, trusted publishing on tag). Released wheels build the portable software path (MORTON_ENABLE_BMI2=OFF) so they never SIGILL on a non-BMI2 CPU; source installs stay BMI2-fast.octree/ project (morton_octree::Octree), which depends on this library. 2:1 balancing, cross-level neighbour queries and bulk construction are tracked in `../octree/PLAN.md`, not here.include/morton/kokkos.hpp (morton::kokkos). Runs on any Kokkos backend (CUDA / HIP / OpenMP / Serial). The core's MORTON_HD resolves to KOKKOS_FUNCTION, so kernels reuse the exact CPU code path (PDEP guarded out of device code). Kokkos::View encode/decode (2D/3D) + per-axis arithmetic; validated bit-for-bit against the scalar library on the GPU. ~51 GMops/s device-resident 2D-32 encode on an RTX 5080 (~33× one CPU core); one-shot host calls are PCIe-bound (documented). Replaced the original raw-CUDA backend (cuda/, retired — pre-cuda-retirement git tag).MORTON_ENABLE_RUNTIME_DISPATCH (CMake option / compile define) builds a single binary without -mbmi2 that still uses PDEP/PEXT when the running CPU has BMI2 (software fallback otherwise), via per-function __attribute__((target("bmi2"))) helpers + a cached __builtin_cpu_supports check (morton/morton.hpp). The redistributable wheels now build with it on (pyproject.toml), so one portable wheel is both SIGILL-safe on old CPUs and BMI2/AVX-512-fast on new ones — removing the old portability/speed trade-off. Self-disables when -mbmi2 is already set, on non-x86, and under CUDA.morton/simd.hpp: hand-written AVX-512 "magic-bits" kernels (8 codes/iteration) for encode2/decode2 (2,32), encode3/decode3 (3,21), and per-axis add/sub on any 64-bit code. morton/batch.hpp dispatches to them at runtime when the CPU has AVX-512F (else the auto-vectorised scalar path); they use a target attribute so no global -mavx512f is needed. The C ABI / NumPy bindings route through these, so Python gets the speedup too. No longer ships untested: CI runs the suite under Intel SDE (-skx) so the AVX-512 path is checked bit-for-bit against the scalar reference on ordinary (non-AVX-512) runners; the runtime-dispatch build is also exercised under -snb/-hsw/-skx.bench_batch already prints the active path and a batch::encode2 vs scalar comparison).target-attribute + __builtin_cpu_supports mechanism is GCC/Clang; an __cpuid-based path would extend it to MSVC.MORTON_MAX_BITS; revisit wide_uint performance (it is intentionally simple, not tuned) if that becomes a hot path.Market it precisely (see EVALUATION.md §5): not a faster encoder, but the Z-order navigation layer that libmorton/morton-nd intentionally omit. Realistic homes for the work:
Dim/Bits is what makes the masks and shifts free. 1.9.8