Section: 16.4.4.6 [allocator.requirements] Status: C++11 Submitter: Hans Boehm Opened: 2007-10-11 Last modified: 2016-01-28
Priority: Not Prioritized
View other active issues in [allocator.requirements].
View all other issues in [allocator.requirements].
View all issues with C++11 status.
Discussion:
Did LWG recently discuss 16.4.4.6 [allocator.requirements]-2, which states that "All the operations on the allocators are expected to be amortized constant time."?
As I think I pointed out earlier, this is currently fiction for
allocate() if it has to obtain memory from the OS, and it's unclear to
me how to interpret this for construct() and destroy() if they deal with
large objects. Would it be controversial to officially let these take
time linear in the size of the object, as they already do in real life?
Allocate() more blatantly takes time proportional to the size of the
object if you mix in GC. But it's not really a new problem, and I think
we'd be confusing things by leaving the bogus requirements there. The
current requirement on allocate() is generally not important anyway,
since it takes O(size) to construct objects in the resulting space.
There are real performance issues here, but they're all concerned with
the constants, not the asymptotic complexity.
Proposed resolution:
Change 16.4.4.6 [allocator.requirements]/2:
-2- Table 39 describes the requirements on types manipulated through allocators.
All the operations on the allocators are expected to be amortized constant time.Table 40 describes the requirements on allocator types.