deep_causality_data_structures 0.9.5

Data structures for for deep_causality crate.
Documentation

🏁 Data structures 🏁

Crates.io Docs.rs MIT licensed Tests

High performance datastructures used in DeepCausality.

ArrayGrid is an abstraction over scalars, vectors, and low dimensional matrices similar to a tensor. In contrast to a tensor, an ArrayGrid is limited to low dimensions (1 to 4), only allowing a scalar, vector, or matrix type. Still, all of them are represented as a static fixed-size const generic array. Fixed-sized arrays allow for several compiler optimizations, including a cache-aligned data layout and the removal of runtime array boundary checks because all structural parameters are known upfront, providing a significant performance boost over tensors.

The CausalTensor provides a flexible, multi-dimensional array (tensor) backed by a single, contiguous Vec<T>. It is designed for efficient numerical computations, featuring a stride-based memory layout that supports broadcasting for element-wise binary operations. It offers a comprehensive API for shape manipulation, element access, and common reduction operations like sum and mean, making it a versatile tool for causal modeling and other data-intensive tasks.

The sliding window implementation over-allocates to trade space (memory) for time complexity by delaying the rewind operation when hitting the end of the underlying data structure. Specifically, a sliding window of size N can hold, without any array copy, approximately C-1 elements, where C is the total capacity defined as NxM with N as the window size and M as a multiple. This crate has two implementations, one over vector and the second over a const generic array. The const generic implementation is significantly faster than the vector-based version.

🤔 Why?

  1. Zero dependencies.
  2. Zero cost abstraction.
  3. Zero unsafe.
  4. Zero macros.

Performance:

ArrayGrid

Set value:

Dimension Safe Implementation Unsafe Implementation Improvement
1D Grid 604.71 ps 271.38 ps 55.1%
2D Grid 581.33 ps 417.39 ps 28.2%
3D Grid 862.16 ps 577.04 ps 33.0%
4D Grid 1.137 ns 812.62 ps 28.5%

More details on performance can be found in the Performance section of the ArrayGrid document.

CausalTensor

Benchmarks are for a 100x100 (10,000 element) tensor.

Operation Time Notes
tensor_get ~1.64 ns Accessing a single element.
tensor_reshape ~786 ns Metadata only, but clones data in the test.
tensor_scalar_add ~2.69 µs Element-wise addition with a scalar.
tensor_tensor_add_broadcast ~37.7 µs Element-wise addition with broadcasting.
tensor_sum_full_reduction ~6.86 µs Summing all 10,000 elements of the tensor.

Sliding Window

Single Push:

Implementation Single Push Time Notes
ArrayStorage ~2.08ns Optimized for continuous access patterns
VectorStorage ~2.5ns Good for dynamic sizing
UnsafeVectorStorage ~2.3ns Better performance than safe vector
UnsafeArrayStorage ~1.9ns Best performance for sequential and batch operations

Sequential Operations:

Implementation Operation Time Notes
UnsafeArrayStorage ~550ps Best cache utilization
ArrayStorage ~605ps Excellent cache locality
UnsafeVectorStorage ~750ps Good for mixed workloads
VectorStorage ~850ps Most predictable

More details on performance can be found in the Performance section of the SlidingWindow document.

🚀 Install

Just run:

cargo add deep_causality_data_structures

📚 Docs

⭐ Usage

ArrayGrid:

CausalTensor:

🙏 Prior Art

The project took inspiration from:

👨‍💻👩‍💻 Contribution

Contributions are welcomed especially related to documentation, example code, and fixes. If unsure where to start, just open an issue and ask.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in deep_causality by you, shall be licensed under the MIT licence, without any additional terms or conditions.

📜 Licence

This project is licensed under the MIT license.

👮️ Security

For details about security, please read the security policy.

💻 Author

  • Marvin Hansen.
  • Github GPG key ID: 369D5A0B210D39BC
  • GPG Fingerprint: 4B18 F7B2 04B9 7A72 967E 663E 369D 5A0B 210D 39BC