Bug 24693 - Deque improvements
Summary: Deque improvements
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: libstdc++ (show other bugs)
Version: 4.1.0
: P3 enhancement
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2005-11-06 10:42 UTC by Paolo Carlini
Modified: 2022-09-01 07:35 UTC (History)
5 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2006-03-01 02:26:37

Attachments
Patch to cache a free node. (930 bytes, patch)
2014-09-23 20:03 UTC, Jonathan Wakely 		Details | Diff
View All Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Paolo Carlini 2005-11-06 10:42:50 UTC 
This is to track this issue:

  http://gcc.gnu.org/ml/libstdc++/2005-11/msg00031.html

A first part, about _M_erase_at_end/_M_erase_at_begin, should be doable relatively
quickly.
Comment 1 Andrew Pinski 2005-11-08 17:13:51 UTC 
Confirmed.
Comment 2 Paolo Carlini 2005-11-25 23:31:36 UTC 
More interesting work to do:

  http://gcc.gnu.org/ml/libstdc++/2005-11/msg00241.html
Comment 3 Paolo Carlini 2005-12-05 18:01:04 UTC 
This part is done:

  http://gcc.gnu.org/ml/libstdc++/2005-11/msg00240.html

can also go in mainline.
Comment 4 Jonathan Wakely 2014-09-23 20:03:18 UTC 
Created attachment 33542 [details]
Patch to cache a free node.

(In reply to Paolo Carlini from comment #2)
> More interesting work to do:
> 
>   http://gcc.gnu.org/ml/libstdc++/2005-11/msg00241.html

Here's a proof of concept to prevent repeated reallocations for this case:

while (a long time)
{
     dq.push_front(t);
     ...
     dq.pop_back();
}

A single free node is cached in _M_map[-1], so there's no change to the layout of the class.
Comment 5 Jonathan Wakely 2016-09-11 14:16:06 UTC 
See also PR 77524
Comment 6 Jonathan Wakely 2016-10-14 19:10:28 UTC 
Prototype patch: https://gcc.gnu.org/ml/libstdc++/2016-10/msg00017.html