rust-cv / header-vec Goto Github PK

Allows one to store a header struct and a vector all inline in the same memory on the heap and share weak versions for minimizing random lookups in data structures

License: MIT License

Rust 100.00%

header-vec's Introduction

header-vec's People

Contributors

Stargazers

Watchers

Forkers

makoconstruct

header-vec's Issues

Get performance within at least 2x of std::vec

In #2, it was identified that HeaderVec performs several times slower than Vec. While this isn't too unusual, it would be great to go faster. Now that we have benchmarks (see #3), we can use these to push the performance further. Getting within at least 2x the performance of Vec should be reasonable, especially considering that HeaderVec is mostly concerned with reducing random accesses in graphs, so memory latency/random lookup is typically a greater concern. However, there is no reason that the implementation can't go faster than it is today, so this should be done.

This issue is to track performance increases until we get to within a reasonable margin (2x) of Vec. This target can be moved if necessary.

Isn't the initial capacity insufficient whenever `align_of::<H> >= align_of::<T>`?

Let's say we have HeaderVec<u32, u8>::new(7u32). new allocates an inital capacity of 1, so from the looks of things, that would get us an allocation layout of

alloc::alloc::Layout::from_size_align(
    1, // Self::elems_to_mem_bytes(capacity),
    4, // cmp::max(mem::align_of::<H>(), mem::align_of::<T>()),
)

Which, the documentation seems to suggest would round the allocation up to 4 bytes. This is only enough to store the header val. The remaining u8 in that the vector is supposed to be able to hold wouldn't actually be allocated for?

The problem is that the size of the memory layout has to be bigger than the capacity of the vec, but they're being treated as if they're the same.

This would only affect the last size_of::<H> - (size_of<T> % size_of<H>) elements of the vec, or something like that, and I'd guess they'd often be kept protected from being messed with by other allocations by the allocator rounding up the allocation cell to contain more than is needed, so it's possible that the consequences of this have not been noticed yet.

I'll try to fix this... after lunch

Investigations of storing multiple types in separate buffers in one allocation

... For me the largest improvement would actually be if I could store multiple types in separate buffers in the allocation rather than as tuples

Originally posted by @vadixidav in #4 (comment)

Add benchmarks against std vec

(I'll do this now unless you have objections)

How do I get at the Header?

Once I have let v = HeaderVec::new(h), how do I get get a reference to h from v?

rust-cv / header-vec Goto Github PK

header-vec's Introduction

Rust Computer Vision

What is computer vision

Goals

header-vec's People

Contributors

Stargazers

Watchers

Forkers

header-vec's Issues

Get performance within at least 2x of std::vec

Isn't the initial capacity insufficient whenever `align_of::<H> >= align_of::<T>`?

Investigations of storing multiple types in separate buffers in one allocation

Add benchmarks against std vec

How do I get at the Header?

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent