[](https://codecov.io/gh/lmeller-git/kasino)
[](https://crates.io/crates/kasino)
[](https://docs.rs/kasino)
# Kasino
A construction that elastically relaxes a given collection.
`Kasino` aims to improve performance of concurrent datastructures by sharding operations into multiple subqueues.
This process introduces a relaxation of the wrapped datastructure, the specifics depending on the used strategy.
Strategies optimize for performance and relaxation bounds, but can be implemented to optimize for other properties.
Multiple strategies, amenable to different kinds of datastructures and requirements are provided.
Additionally an interface for defining custom strategies is available.
### Usage
```rust
use kasino::{InlineBandit, strategy::DCBO};
let bandit = InlineBandit::<MyQueue<i32>, DCBO, 8>::new();
let mut handle = bandit.buy_in();
let mut handle2 = handle.fork();
assert!(handle.offer(42).is_ok());
assert!(handle2.offer(10).is_ok());
assert!(handle.poll(()).is_ok());
```
### Property preservation
#### Progress Guarantees:
- **Lock Freedom**: if the wrapped collection is lock-free, `Bandits` are also lock-free.
- **Obstruction Freedom**: if the wrapped collection exposes obstruction-free methods, all corresponding operations on `Bandits` are also obstruction-free.
#### Ordering and Consistency Guarantees:
- **Relaxed Specification**: if the wrapped collection has some specification, `Bandits` relax that specification based on the chosen strategy.
- **Linearizability**: if the wrapped collection is linearizable, all operations on `Bandits` are also linearizable with respect to their relaxed specification.
#### Relaxation
The rank error and delay are in general unbounded. However, the rank error and delay of some strategies are bounded with high probability.
The exact bounds here are differing across different strategies.
For more information refer to the strategies documentation and the reference papers.
For an empirical analysis of the rank errors, refer to [relaxed-queue-simulations](https://github.com/lmeller-git/relaxed-queue-simulations).
### Performance
Sharding operations to multiple sub-collections incurs both memory cost, as well as additional overhead. Under low contention `Kasino` is slower than the raw collection.
However, scheduling thread access across multiple sub-collections allows to reduce cache-line invalidation at high contention, improving performance as thread count increases.
### Limitations
- Currently an instantiated `Bandit` cannot be resized. Its capacity is fixed at construction time.
- The capacity of each sub-collection is fixed statically. The total capacity of a `Bandit` is constrained to a multiple of this.
### Advanced Usage
The interfaces for [`Collection`](https://docs.rs/kasino/latest/kasino/trait.Collection.html), [`strategy::Strategy`](https://docs.rs/kasino/latest/kasino/strategy/trait.Strategy.html) and `Bandit` are general enough to support the implementation of a large set of datastructures. For examples of this consult `examples/`.
### Platform Support
All platforms supporting native atomic operations are supported.
The feature `atomic-fallback` may be used, if no native atomic operations are available.
### Feature Flags
- `std`: Enables `std` support.
- `instrumented`: Adds telemetry collection to strategies
- `atomic-fallback`: Uses the `portable-atomic` fallback feature if native atomics are missing. It is discouraged to use this feature, as fallback atomics internally rely on locks.
- `default`: None
### Testing
Currently testing is based on:
- **Miri** - to validate pointer arithmetic and catch undefined behavior.
- **Loom and Shuttle** - to test for race conditions and non-blocking invariants.
- **ASan** - to check for memory corruption.
### References
- Performance, Scalability, and Semantics of Concurrent FIFO Queues, Kirsch et al.
- Balanced Allocations over Efficient Queues: A Fast Relaxed FIFO Queue, Geijer et al.