Fix deque's usage of _Allocate_at_least_helper#4017
Fix deque's usage of _Allocate_at_least_helper#4017StephanTLavavej merged 3 commits intomicrosoft:mainfrom
deque's usage of _Allocate_at_least_helper#4017Conversation
| allocation_result<T*> allocate_at_least(size_t count) { | ||
| allocate_at_least_signal.set(); | ||
| return {allocate(count * 2), count * 2}; | ||
| return {allocate(count * 2 + 1), count * 2 + 1}; |
There was a problem hiding this comment.
count * 2 just happened to work; the deque will break easily if users try to provide their own allocate_at_least.
stl/inc/deque
Outdated
| while (_Allocsize / 2 >= _Newsize) { | ||
| _Newsize *= 2; | ||
| } |
There was a problem hiding this comment.
This seems inefficient to try and get the biggest power of two less than _Allocsize (I really wish we had access to std::bit_floor(...) here)
There was a problem hiding this comment.
Do we have an _Ugly (i.e., usable in C++14 mode) version of bit_floor?
There was a problem hiding this comment.
I think it's ok to (temporarily) keep this while loop, as it's highly likely that _Allocsize is just equal to or marginally larger than _Newsize, so the loop will skip immediatly or at least very short. (And I'm going to do a series of cleanups for <deque> recently :) we can also consider connverting another while loop in the function to a bit_ceil too )
There was a problem hiding this comment.
I made a tiny cleanup & optimization for its above loop: 850d8ae; I think this can partly compensate for (or overcome) the cost of new loop. Can I make a push to this pr?
godbolt result; the codegen looks really better (slighty fewer lines; tighter loop; fewer jmp)
------update------
I'm having difficulty deciding whether we can safely assume _Minimum_map_size will not cause overflow against (_Alty::)max_size()/_Block_size. And worse, that comparision looks just wrong to me. I'm doubting we should compare with _Al[p]ty::max_size instead.
Due to these problems I'd suggest putting off the commit to future prs. (And in that commit link I've added some more detailed comments about the above problems.)
|
Thanks much for separating the bugfix from the cleanup! |
|
@strega-nil-ms I pushed minor stylistic changes after you approved. |
| _Mapptr _Newmap = _Allocate_at_least_helper(_Almap, _Newsize); | ||
| _Mapptr _Newmap = _Allocate_at_least_helper(_Almap, _Allocsize); | ||
| _Mapptr _Myptr = _Newmap + _Myboff; | ||
| _STL_ASSERT(_Allocsize >= _Newsize, "_Allocsize >= _Newsize"); |
There was a problem hiding this comment.
I think we should put debug check in _Allocate_at_least_helper instead. (And is _STL_ASSERT a suitable choice for such check?)
That would be reasonable.
Yeah, for users violating preconditions. |
|
Thanks for the confirmation! |
|
I'm mirroring this to the MSVC-internal repo - please notify me if any further changes are pushed. |
|
Thanks for noticing and fixing this regression before anyone else did! 🦅 👁️ 🐞 |
deque::_Mapsize()should always be power of 2. Therefore, indeque::_Growmap,_Allocate_at_least_helpershould not have chance to change_Newsizedirectly.