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

Double-ended vector – is it useful?

larshagencpp.github.io

Post reply on HN
Print view View original

21–30 of 53 posts

Re: Double-ended vector – is it useful?

#21

Post by ktRolster »

agf wrote: post #4

This is an interesting article, and a "devector" is something I've never heard of or considered before, so I'll leave critique of the data structure itself to others. But I have some constructive criticism of how the data is presented. Since the graphs / performance comparisons are such a large part of the post, I think it's relevant. First of all, and most simply, when presenting multiple charts please use the same…

Second, absolute timings don't matter here, only relative timings do, so showing absolute time on the Y-axis doesn't really make sense

I like to see the real timings, though. It helps me get a sense for how long real-world tasks take. In this one, we can see that things were happening on the order of nanoseconds.

Re: Double-ended vector – is it useful?

#22

Post by mhandley »

omgtehlion wrote: post #5
nkurz wrote: post #2

I feel like it would be possible to leave the heavy lifting to the underlying page tables. Presuming you are running a 64-bit system, you have a enormous practically unused address space. Until you access the allocated memory it doesn't actually occupy any physical RAM. The virtual address gets associated with the physical RAM in 4KB pages. So if you just allocate an a region twice as large as you will ever need, and…

Even further: allocate the same physical region twice. Please google what "virtual ring buffer" is ))

That's a really neat idea - hadn't seen that before. Link: http://vrb.sourceforge.net/

Re: Double-ended vector – is it useful?

#23

Post by mrpopo »

Interesting implementation. Given that it seems to perform more moves than a regular vector, I'm wondering how much more efficient this would be if it could just memmove the whole block around (AFAIK, the spec doesn't allow it because of constructors/destructors for complex structures).

Re: Double-ended vector – is it useful?

#24

Post by glandium »

omgtehlion wrote: post #5
nkurz wrote: post #2

I feel like it would be possible to leave the heavy lifting to the underlying page tables. Presuming you are running a 64-bit system, you have a enormous practically unused address space. Until you access the allocated memory it doesn't actually occupy any physical RAM. The virtual address gets associated with the physical RAM in 4KB pages. So if you just allocate an a region twice as large as you will ever need, and…

Even further: allocate the same physical region twice. Please google what "virtual ring buffer" is ))

If only that were possible without a file...

Re: Double-ended vector – is it useful?

#25

Post by omgtehlion »

glandium wrote: post #24
omgtehlion wrote: post #5

Earlier quoted context omitted.

Even further: allocate the same physical region twice. Please google what "virtual ring buffer" is ))

If only that were possible without a file...

It is completely possible without a file (on linux, winNT, osx). Syscall names might mislead you, but this is how it is...

Re: Double-ended vector – is it useful?

#26

Post by dunkelheit »

viraptor wrote: post #11
poizan42 wrote: post #6

Earlier quoted context omitted.

So if you have a million vectors then you have wasted 8GB. It only makes sense if you have a few large vectors.

Or if you have fewer than millions. You jumped from millions to few large. That's not what applications usually need. And even within one application, you may want to mix the storage strategies between different objects.

For a general-purpose container that is unacceptable. It must perform well from tiny to huge sizes. Also, syscalls in every constructor/destructor call? No thanks.

What you describe might make sense for some special cases, but adopting it as a default strategy is a bad idea IMO. (Edit: re-read your other post in this thread and realized that you are not really advocating this. Well then my reply goes mostly to nkurz :))

> even within one application, you may want to mix the storage strategies between different objects.

That's precisely what modern malloc implementations do.

Re: Double-ended vector – is it useful?

#27

Post by foota »

nightcracker wrote: post #20
deathanatos wrote: post #17

Earlier quoted context omitted.

I don't think std::deque's implementation is specified in standard. It only needs to meet certain running times, and the data structure in the article — the author's "devector" — would satisfy the requirements of std::deque; i.e., the "devector" is a valid implementation of std::deque, I think. However, in practice, std::deque is not implemented this way — your link hints at this: > As opposed to std::vector, the ele…

> the "devector" is a valid implementation of std::deque, I think It is not. std::deque has strict requirements that say appends/prepends may not invalidate references/iterators. A devector can not guarantee this.

Nitpick, the operation seems to be allowed to invalidate iterators, though not references. "An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque" [1] There might be some cases where it would be practical to simply not free the previously used memory, such that after N increases in size there are N copies of each element. This would only roughly double the space required.

[1] C++ working draft, 11 megabytes; http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n429...

Re: Double-ended vector – is it useful?

#28

Post by pjc50 »

viraptor wrote: post #12
nkurz wrote: post #2

I feel like it would be possible to leave the heavy lifting to the underlying page tables. Presuming you are running a 64-bit system, you have a enormous practically unused address space. Until you access the allocated memory it doesn't actually occupy any physical RAM. The virtual address gets associated with the physical RAM in 4KB pages. So if you just allocate an a region twice as large as you will ever need, and…

Familiarity / need I'd guess. I know this is possible. I also know how I'd do it on Linux, or where to start reading (mmap). But I have no idea how portable it is (does windows have mmap?) and unless I really need a structure that expands both ways, unless I know it's going to grow big, unless I can't estimate and preallocate it with some known capacity, unless I can't handle this using rebalancing tree, unless I rea…

Between VirtualAlloc and MapViewOfFile, Windows has roughly equivalent functionality. Windows also separates out "reserve" and "commit" in the API.

Re: Double-ended vector – is it useful?

#29

Post by viraptor »

dunkelheit wrote: post #26
viraptor wrote: post #11

Earlier quoted context omitted.

Or if you have fewer than millions. You jumped from millions to few large. That's not what applications usually need. And even within one application, you may want to mix the storage strategies between different objects.

For a general-purpose container that is unacceptable. It must perform well from tiny to huge sizes. Also, syscalls in every constructor/destructor call? No thanks. What you describe might make sense for some special cases, but adopting it as a default strategy is a bad idea IMO. (Edit: re-read your other post in this thread and realized that you are not really advocating this. Well then my reply goes mostly to nkurz…

> Also, syscalls in every constructor/destructor call? No thanks.

You can batch up operations just like with normal list and malloc/free. Instead of 1 page, allocate some bigger size in one go.

Re: Double-ended vector – is it useful?

#30

Post by nightcracker »

foota wrote: post #27
nightcracker wrote: post #20

Earlier quoted context omitted.

> the "devector" is a valid implementation of std::deque, I think It is not. std::deque has strict requirements that say appends/prepends may not invalidate references/iterators. A devector can not guarantee this.

Nitpick, the operation seems to be allowed to invalidate iterators, though not references. "An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque" [1] There might be some cases where it would be practical t…

Ah, I thought it was both, but was just working from the top of my memory. Good for looking it up :)
Post reply on HN