752. Allocator complexity requirement

Section: 20.5.3.5 [allocator.requirements] Status: C++11 Submitter: Hans Boehm Opened: 2007-10-11 Last modified: 2016-02-10

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 20.5.3.5 [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 20.5.3.5 [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.