PaletteVec is a Rust data structure designed for space-efficient storage of collections containing a limited number of unique, repeated elements. It achieves this by using a palette-based encoding scheme (palette compression), similar to how indexed color images or Minecraft chunk data are stored.
- Space Efficiency: Drastically reduces memory footprint for data with many repeated values by storing each unique value only once in a "palette" and then using compact indices to refer to them.
- Direct Manipulation: Allows for operations like
push,pop,set, andgetdirectly on the compressed data without needing to decompress the entire collection. - Iterator: Supports iteration over its elements without decompression.
- Customizable Backend: Generic over
PaletteandIndexBuffertraits, allowing for different storage strategies (e.g.,HybridPalettefor a balance of performance and memory,AlignedIndexBufferfor efficient index storage).
PaletteVec is particularly useful in scenarios where:
- You have a large collection of items.
- The number of unique items in the collection is relatively small compared to the total number of items.
- Memory efficiency is a critical concern.
- You need to frequently access or modify elements within the collection.
Common Use Cases:
- Voxel Engines: Storing block data in game worlds (like Minecraft).
- Image Compression: Representing indexed color images.
- Any application dealing with large datasets of discrete, repeating values.
- Whenever you want to store lots of repeated values that are expensive to clone.
- Access Overhead: Accessing elements involves an indirection (looking up the index in the palette), which can introduce a small runtime cost compared to a standard
Vec<T>. - Palette Management: For very large numbers of unique items (a large palette), the overhead of managing the palette itself might increase. The
HybridPaletteimplementation helps mitigate this by switching from an array to a HashMap when the number of unique items exceeds a threshold.
Licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.