deque --> __add_back_capacity / I think that it could be better (but I'm not sure)

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

deque --> __add_back_capacity / I think that it could be better (but I'm not sure)

Louis Dionne via cfe-dev
Project: libc++
file: include/deque
line: 2422-2473

Code:

    else
    {
        __split_buffer<pointer, typename __base::__pointer_allocator&>
            __buf(max<size_type>(2* __base::__map_.capacity(), 1),
                  __base::__map_.size(),
                  __base::__map_.__alloc());

        typedef __allocator_destructor<_Allocator> _Dp;
        unique_ptr<pointer, _Dp> __hold(
            __alloc_traits::allocate(__a, __base::__block_size),
                _Dp(__a, __base::__block_size));
        __buf.push_back(__hold.get());
        __hold.release();

        for (typename __base::__map_pointer __i = __base::__map_.end();
                __i != __base::__map_.begin();)
            __buf.push_front(*--__i);
        _VSTD::swap(__base::__map_.__first_, __buf.__first_);
        _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
        _VSTD::swap(__base::__map_.__end_, __buf.__end_);
        _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
    }


See this part:
__split_buffer<pointer, typename __base::__pointer_allocator&>
            __buf(max<size_type>(2* __base::__map_.capacity(), 1),
                  __base::__map_.size(),
                  __base::__map_.__alloc());

You have a full map (capacity == size)
map = [a b c d e f ]
and you want to create a new map with double capacity
new_map = [_ _ _ _ _ _ _ _ _ _ _ _ ]

the second argument of split_buffer constructor (x) is used to assign __begin:
__begin_ = __end_ = __first_ + x;

So, at the end you will have
new_map = [a b c d e f g _ _ _ _ _ ]

Where g is the address of the new block created.

However, you can see that adress's of blocks are left aligned. A better alternative is:

__split_buffer<pointer, typename __base::__pointer_allocator&>
            __buf(max<size_type>(2* __base::__map_.capacity(), 1),
                  __base::__map_.size()*3/2,
                  __base::__map_.__alloc());

Using this code, at the end the new map will be:
new_map = [_ _ _ a b c d e f g _ _ ]
which is better because there is equilibrium, avoiding complex operations (pop_back + push_back(pt)) if the programmer call a subsequent push_front --> __add_front_capacity.

But I am not expert, I am learning C++ and navigating inside of the libc++ source to understand how some containers work.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: deque --> __add_back_capacity / I think that it could be better (but I'm not sure)

Louis Dionne via cfe-dev
It's important to point out the code you cite is from a function called `__add_back_capacity()`, used to expand the deque in functions like push_back when more capacity is needed.
`__add_front_capacity()` which does the opposite, and is used by `push_front`.

Additionally, both __front_capacity and __back_capacity will "steal" unused capacity from the other end of the deque.

For these reason I don't see the advantage in achieving equilibrium between the front and back. Perhaps you could 
elaborate further? Or, better yet, provide some benchmarks?

/Eric


On Thu, Apr 5, 2018 at 2:28 PM, Christiano SA via cfe-dev <[hidden email]> wrote:
Project: libc++
file: include/deque
line: 2422-2473

Code:

    else
    {
        __split_buffer<pointer, typename __base::__pointer_allocator&>
            __buf(max<size_type>(2* __base::__map_.capacity(), 1),
                  __base::__map_.size(),
                  __base::__map_.__alloc());

        typedef __allocator_destructor<_Allocator> _Dp;
        unique_ptr<pointer, _Dp> __hold(
            __alloc_traits::allocate(__a, __base::__block_size),
                _Dp(__a, __base::__block_size));
        __buf.push_back(__hold.get());
        __hold.release();

        for (typename __base::__map_pointer __i = __base::__map_.end();
                __i != __base::__map_.begin();)
            __buf.push_front(*--__i);
        _VSTD::swap(__base::__map_.__first_, __buf.__first_);
        _VSTD::swap(__base::__map_.__begin_, __buf.__begin_);
        _VSTD::swap(__base::__map_.__end_, __buf.__end_);
        _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap());
    }


See this part:
__split_buffer<pointer, typename __base::__pointer_allocator&>
            __buf(max<size_type>(2* __base::__map_.capacity(), 1),
                  __base::__map_.size(),
                  __base::__map_.__alloc());

You have a full map (capacity == size)
map = [a b c d e f ]
and you want to create a new map with double capacity
new_map = [_ _ _ _ _ _ _ _ _ _ _ _ ]

the second argument of split_buffer constructor (x) is used to assign __begin:
__begin_ = __end_ = __first_ + x;

So, at the end you will have
new_map = [a b c d e f g _ _ _ _ _ ]

Where g is the address of the new block created.

However, you can see that adress's of blocks are left aligned. A better alternative is:

__split_buffer<pointer, typename __base::__pointer_allocator&>
            __buf(max<size_type>(2* __base::__map_.capacity(), 1),
                  __base::__map_.size()*3/2,
                  __base::__map_.__alloc());

Using this code, at the end the new map will be:
new_map = [_ _ _ a b c d e f g _ _ ]
which is better because there is equilibrium, avoiding complex operations (pop_back + push_back(pt)) if the programmer call a subsequent push_front --> __add_front_capacity.

But I am not expert, I am learning C++ and navigating inside of the libc++ source to understand how some containers work.
_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev


_______________________________________________
cfe-dev mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev