Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Shift-to-Middle Array: A Faster Alternative to Std:Deque?

github.com

Post reply on HN
Print view View original

71–80 of 121 posts

Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?

#71

Post by severino »

actionfromafar wrote: post #66
severino wrote: post #63

Earlier quoted context omitted.

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. (An…

Thanks, what you explain in your comment is the idea I had, too, although I've little experience in C++. But I was confused after taking a look at this project's source and seeing all the duplicated code between ShiftToMiddleArray.h and ShiftToMiddleArray.cpp, and not only signatures. I wasn't sure if that was done for some purpose.

Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?

#72

Post by bobmcnamara »

eru wrote: post #44
ntonozzi wrote: post #9

Earlier quoted context omitted.

Sounds very cool! How do you implement efficient random deletes?

The current implementation doesn't. You could add that functionality via 'tombstones': when you delete an element, you replace it with a 'tombstone' marker in the structure. Whenever you clean up the structure (eg for a resize), you skip the tombstones when you copy the old contents over.

There's a similar data structure sometimes seen in video games that does this, but the name escapes me.

Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?

#73

Post by sensen7 »

oasisaimlessly wrote: post #53
ntonozzi wrote: post #9

Earlier quoted context omitted.

Sounds very cool! How do you implement efficient random deletes?

std::vector doesn't support efficient random deletes, so this (a generalization of std::vector along one specific axis) won't either. Efficient random deletes and contiguous hole-free storage are completely at odds with each other.

They aren't: https://github.com/GossiperLoturot/densemap

Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?

#74

Post by leiroigh »

pcwalton wrote: post #21

Interesting alternative idea I thought of just now: a data structure that works like VecDeque (a circular buffer) but uses mmap to map two views onto the same pages right after one another. That would ensure that the entire array can be accessed in a consecutive fashion, no matter where it gets split, without any copying. The downside is that reallocation would be really slow, involving multiple syscalls, and the min…

The main problem with that is that it doesn't play nice with most languages. Consider

  int foo(int* ptr) {
    int x = ptr[1
Compilers/languages/specs tend to decide that `ptr` and `ptr + (1
  foo(int*):
        mov     eax, dword ptr [rdi + 262144]
        inc     dword ptr [rdi]
        add     eax, eax
        ret
which gives undesired results if `ptr` and `ptr + (1<<16)` happen to be mapped to the same physical address. This is also pretty shit to debug/test -- some day, somebody will enable LTO for an easy performance win on release builds, and bad code with a security vuln gets shipped.

Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?

#75

Post by wffurr »

sensen7 wrote: post #73
oasisaimlessly wrote: post #53

Earlier quoted context omitted.

std::vector doesn't support efficient random deletes, so this (a generalization of std::vector along one specific axis) won't either. Efficient random deletes and contiguous hole-free storage are completely at odds with each other.

They aren't: https://github.com/GossiperLoturot/densemap

That’s a map, not an indexed array, and it’s slower than Vec across the board per its own benchmarks.

Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?

#76

Post by sensen7 »

wffurr wrote: post #75
sensen7 wrote: post #73

Earlier quoted context omitted.

They aren't: https://github.com/GossiperLoturot/densemap

That’s a map, not an indexed array, and it’s slower than Vec across the board per its own benchmarks.

Yes, it's a map that provides efficient random deletes and contiguous hole-free storage, proving that they are not completely at odds with each other.

If you don't care about the map part, you can get the same behavior by just moving the last element in the place of the newly removed element. This invalidates all indices, which is what the DenseMap's overhead is meant to avoid, but Vec's remove also invalidates indices. Vec's remove is strictly worse except that it preserves the ordering if the Vec is sorted.

Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?

#77

Post by sensen7 »

bobmcnamara wrote: post #72
eru wrote: post #44

Earlier quoted context omitted.

The current implementation doesn't. You could add that functionality via 'tombstones': when you delete an element, you replace it with a 'tombstone' marker in the structure. Whenever you clean up the structure (eg for a resize), you skip the tombstones when you copy the old contents over.

There's a similar data structure sometimes seen in video games that does this, but the name escapes me.

You're probably thinking of "slabs" or "slotmaps"

Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?

#78

Post by oasisaimlessly »

sensen7 wrote: post #73
oasisaimlessly wrote: post #53

Earlier quoted context omitted.

std::vector doesn't support efficient random deletes, so this (a generalization of std::vector along one specific axis) won't either. Efficient random deletes and contiguous hole-free storage are completely at odds with each other.

They aren't: https://github.com/GossiperLoturot/densemap

You can't refer to this collection via a slice (std::span / &[T]), so it's not what I meant when I said "contiguous hole-free storage".

Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?

#79

Post by eru »

dzaima wrote: post #46
eru wrote: post #44

Earlier quoted context omitted.

The current implementation doesn't. You could add that functionality via 'tombstones': when you delete an element, you replace it with a 'tombstone' marker in the structure. Whenever you clean up the structure (eg for a resize), you skip the tombstones when you copy the old contents over.

That'd break arbitrary reads being contiguous O(1) though.

Yes, that's true. Though you could still access front and back in amortised O(1).

Re: Shift-to-Middle Array: A Faster Alternative to Std:Deque?

#80

Post by freeone3000 »

severino wrote: post #71
actionfromafar wrote: post #66

Earlier quoted context omitted.

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. (An…

Thanks, what you explain in your comment is the idea I had, too, although I've little experience in C++. But I was confused after taking a look at this project's source and seeing all the duplicated code between ShiftToMiddleArray.h and ShiftToMiddleArray.cpp, and not only signatures. I wasn't sure if that was done for some purpose.

You need the definitions in the header for templates (which look like what other languages call generic types), because the source of the method needs to be available to effect the template substitution. (The idea behind headers being you can compile against a header and a compiled object, like a shared library.)
Post reply on HN