Skip to content

BufferPool: use best-fit (>=) instead of exact-size matching #123

@shinaoka

Description

@shinaoka

Summary

strided-opteinsum/src/expr.rs BufferPool uses HashMap<usize, Vec<Vec<T>>> keyed by exact element count:

pool.f64_pool.get_mut(&total).and_then(|v| v.pop())

A buffer of 10001 elements is not reused for a request of 10000 elements, even though it would work fine.

Proposal

Use BTreeMap instead of HashMap, and find the smallest buffer >= requested size:

pool.f64_pool.range_mut(total..).next()

This improves cache hit rate, especially for contraction trees where intermediate sizes vary slightly.

Risk

Low. A larger buffer is always safe to use; only the first total elements are accessed.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions