#memory #segment #vec #memory-size #data-structures #chunks #resize

segvec

SegVec data structure for rust. Similar to Vec, but allocates memory in chunks of increasing size

7 releases

0.2.0 Jul 31, 2023
0.1.5 Jan 17, 2022
0.1.3 Jul 7, 2021
0.1.1 Jun 30, 2021

#269 in Memory management

Download history 19/week @ 2024-06-17 4/week @ 2024-06-24 73/week @ 2024-07-01 14/week @ 2024-07-08 36/week @ 2024-07-15 13/week @ 2024-07-22 67/week @ 2024-07-29 14/week @ 2024-08-05 28/week @ 2024-08-12 46/week @ 2024-08-19 30/week @ 2024-08-26 83/week @ 2024-09-02 35/week @ 2024-09-09 10/week @ 2024-09-16 117/week @ 2024-09-23 135/week @ 2024-09-30

312 downloads per month
Used in 2 crates (via mbroker)

MIT license

93KB
2K SLoC

segvec

docs.rs crates.io

This crate provides the SegVec data structure.

It is similar to Vec, but allocates memory in chunks of increasing size, referred to as "segments". This involves a few trade-offs:

Pros:

  • Element addresses are stable across push operations even if the SegVec must grow.
  • Resizing only allocates the additional space needed, and doesn't require copying.

Cons:

  • Operations are slower (some, like insert, remove, and drain, are much slower) for a SegVec than for a Vec (multiple pointer dereferences, mapping indices to (segment, offset) pairs)
  • Direct slicing is unavailable (i.e. no &[T] or &mut [T]), though slice and slice_mut are available

Use Cases

  1. You have a long-lived Vec whose size fluctuates between very large and very small throughout the life of the program.
  2. You have a large append-only Vec and would benefit from stable references to the elements

Features

  • small-vec - Uses SmallVec instead of Vec to store the list of segments, allowing the first few segment headers to live on the stack. Can speed up access for small SegVec values.
  • thin-segments - Uses ThinVec instead of Vec to store the data for each segment, meaning that each segment header takes up the space of a single usize, rathern than 3 when using Vec.

License: MIT

Dependencies

~170–300KB