I really hate how MSVC made std::deque toxic for cross-platform use, it's such a cool concept.
Shift-to-Middle Array: A Faster Alternative to Std:Deque?
61–70 of 121 posts
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#62Earlier quoted context omitted.
> Unlike std::deque, which uses a fragmented block-based structure I always assumed deque implementations were ring buffers that double in size once full so that prepend/append operations are amortized O(1).
IDK, I thought the whole point of a deque was to string vectors into a linked list, so you get benefits of both, the most important ones being 1) cheap random access, and 2) insertion doesn't move stuff around in memory. I.e. that the deque's "vectors connected by pointers" is not an implementation detail, but the very nature of the beast. Maybe I just took the boxes-and-arrows diagrams from C++ books too seriously.
Yes, I agree, insertion not moving things is a very useful feature of deques. It allows you to keep items with deleted copy and move constructors in a container that has good cache locality.
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#63A couple notes looking at the c++ implementation - this is going to have problems with non-trivial types. (Think about destructors or move constructors like std::unique_ptr). If you don't want to deal with them, at least add a static_assert(std::is_trivially_copyable ::value == true); - front() doesn't return a reference and it doesn't even return the front - adding iterators (begin()/end()) will let it play nice wit…
A little off-topic, but is it usual in C++ to have a header (.h) and a source (.cpp) where the attributes and most of the methods are identical in both files, but with some more methods in the header file?
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#64Earlier quoted context omitted.
For C++, that's only valid for some subset of types, which currently can't be expressed with type traits. "Address-free" has a close enough definition in the context of atomics. Trivially moveable types are probably sufficient (at least, I can't construct a case where being trivially copyable is needed), but not necessary; there are many things a special member function can do without caring about the address. In pra…
> In practice, the main problem is that you can't use private mappings (which are the default and for good reason); you have to use shared mapping, which are very finicky to set up and cause infelicities with `fork`. [This does make me wonder how reflinks/`copy_file_range` interact with `mmap` and the page cache.] Yet another reason fork was never a good design choice.
Is fork really the problem in this scenario?
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#65I recently developed a new data structure called the Shift-To-Middle Array, designed as an alternative to std::deque, std::vector, and linked lists. My goal was to optimize insertion and deletion at both ends, while also improving cache locality and performance compared to traditional implementations. What is the Shift-To-Middle Array? Unlike std::deque, which uses a fragmented block-based structure, the Shift-To-Mid…
Really interesting, I love new ideas for data structures.
One little note about benchmarking though. It's hard to get good benchmark data, particularly in Java due to the JIT compiler. At the very least, you should perform a large number of warmups (e.g. 10000 calls to the code) before actually benchmarking to ensure all code is fully compiled by the JIT. That's only one of the gotchas though. Even better, use a dedicated Java benchmarking system like jmh.
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#66A couple notes looking at the c++ implementation - this is going to have problems with non-trivial types. (Think about destructors or move constructors like std::unique_ptr). If you don't want to deal with them, at least add a static_assert(std::is_trivially_copyable ::value == true); - front() doesn't return a reference and it doesn't even return the front - adding iterators (begin()/end()) will let it play nice wit…
A little off-topic, but is it usual in C++ to have a header (.h) and a source (.cpp) where the attributes and most of the methods are identical in both files, but with some more methods in the header file?
Well the code should not be duplicated, only method signatures, but yes.
It’s very common.
Edit: after a while you don't even think about it (and of course, there are reasons for it) but sometimes I pause and think. It didn't have to be this way. Some C++ libraries are what's called "header only" which makes them very easy to integrate into your own code. Downside is that it may take longer to compiler your code. (And here lies a clue to why things are that way. The header tells the compiler how your other code may interface with the code, without having to know exactly what goes on in the code.) There have been attempts¹ to do away with the split between header and code, which would make C++ a bit more like C# or Java for instance in that respect. In newer versions of C++ there is the "module"² concept which I don't know much about but which can achieve something similar.
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#67I recently developed a new data structure called the Shift-To-Middle Array, designed as an alternative to std::deque, std::vector, and linked lists. My goal was to optimize insertion and deletion at both ends, while also improving cache locality and performance compared to traditional implementations. What is the Shift-To-Middle Array? Unlike std::deque, which uses a fragmented block-based structure, the Shift-To-Mid…
This is pretty cool, thanks for sharing! It looks like your benchmarks only cover average operation time. Have you thought about benchmarking p99 latency as well? I would expect insertions that cause reallocations to be slow enough that it might be an issue for some usecases.
At the very least, computing the standard deviation as well as the mean average would be useful to get some idea of the variation.
The median, rather than the mean would also generally be a better guide to performance in practice. Even better, give the mean, median and std deviation.
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#68This implementation grows indefinitely if you repeatedly push to the head and remove from the tail, even if the max number of elements in the array is small
Does it definitely do that? You could easily avoid it by making the "resize" really a move if you don't actually need more space.
I feel like they're over-selling it anyway by comparing to `std::deque` (which is not hard to beat). The only advantage this has over a standard ring buffer (like Rust's VecDeque) is that the data is completely contiguous, but you'll pay a small performance cost for that (regular memmove's when used as a queue), and I'm not sure how useful it is anyway.
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#69I recently developed a new data structure called the Shift-To-Middle Array, designed as an alternative to std::deque, std::vector, and linked lists. My goal was to optimize insertion and deletion at both ends, while also improving cache locality and performance compared to traditional implementations. What is the Shift-To-Middle Array? Unlike std::deque, which uses a fragmented block-based structure, the Shift-To-Mid…
> I recently developed a new data structure
Congratulations, you have discovered the array deque!
https://en.wikipedia.org/wiki/Double-ended_queue#Implementat...
I'd like to point out a performance optimization. On resize, you create a new array with double the size and copy all the old elements to the middle of the new array with more space at the beginning AND at the end: https://github.com/attilatorda/Shift-To-Middle_Array/blob/05...
However, in practice, it is often the case that most operations append elements at either the front OR back, but rarely at both ends equally. For example, imagine a FIFO queue, where elements are popped from the front and pushed from the back. Therefore, it is more efficient to only reserve space at the back if the last operation was push_back or at the front if the last operation was push_front.
One could also carry along statistical information about the number of push_back and push_front operations and balance the space allocated at the front and back accordingly.
In addition to ksherlock's points, there are also the following issues:
- Vector implementations usually use size_t instead of int. Your implementation will fail for arrays larger than 2147483647, while size_t usually goes up to 18446744073709551615.
- On memory allocation failure, you should throw std::bad_alloc instead of calling std::exit.
- The front() function is missing a return statement. Turn on compiler warnings: -Wall -Wextra. For testing, -g -fsanitize=address,undefined is also helpful.
- You are mixing delete[] with malloc'ed memory in shrink_to_fit.
- You should implement copy constructor, move constructor, copy asignment and move assignment functions. See rule of five: https://en.cppreference.com/w/cpp/language/rule_of_three#Rul...
- Switching features on or off is usually done with macros instead of comments.
- 2 is not the best growth factor because it makes it harder for the memory allocator to reuse memory. More modern implementations use smaller growth factors: https://en.wikipedia.org/wiki/Dynamic_array#Growth_factor
- A more reasonable initial capacity would be 0 instead of 16, as is common for all major std::vector implementations. An initial capacity of 16 wastes a lot of space when a large number of ShiftToMiddleArrays are allocated.
- The compiler will most-likely ignore your inline instructions and decide on its own whether inlining is done or not, so might as well remove them.
- Why are there two versions of the data structure? (ShiftToMiddleArray.cpp and ShiftToMiddleArray.h)
- Some functions are just wrappers for other functions (pop_front = remove_head, pop_back = remove_tail). Why?
LLMs can point out most of those issue, so you should use them to discover potential issues. Of course, make sure to double-check with more reliable sources once you know that a certain class of problems exists.
Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?
#70I recently developed a new data structure called the Shift-To-Middle Array, designed as an alternative to std::deque, std::vector, and linked lists. My goal was to optimize insertion and deletion at both ends, while also improving cache locality and performance compared to traditional implementations. What is the Shift-To-Middle Array? Unlike std::deque, which uses a fragmented block-based structure, the Shift-To-Mid…
> I recently developed a new data structure Congratulations, you have discovered the array deque! https://en.wikipedia.org/wiki/Double-ended_queue#Implementat... I'd like to point out a performance optimization. On resize, you create a new array with double the size and copy all the old elements to the middle of the new array with more space at the beginning AND at the end: https://github.com/attilatorda/Shift-To-Mid…
- The compiler will most-likely ignore your inline instructions and decide on its own whether inlining is done or not, so might as well remove them.
There are compiler specific attributes that can really force this. Of course, it's worth doing benchmarks and looking at the generated assembly to see if this is necesary