Opened 10 years ago

Closed 10 years ago

#7908 closed Bugs (fixed)

Complexity of ~stable_vector() not linear to the number of elements

Reported by: Gerhard Holzmeister Owned by: Ion Gaztañaga
Milestone: To Be Determined Component: container
Version: Boost 1.52.0 Severity: Problem
Keywords: stable_vector Cc:

Description

Complexity of ~stable_vector() seem to be quadratic to the number of elements.

Tested with 1.48 and 1.52

Attachments (1)

test.cpp​ (1.0 KB ) - added by anonymous 10 years ago.

Download all attachments as: .zip

Change History (5)

by anonymous, 10 years ago

Attachment: test.cpp​ added

comment:1 by Ion Gaztañaga, 10 years ago

With current trunk code, with MSVC 7.1 in release mode I get the following results: 

size: 1000 create and fill time/size:187 delete time/size:45
size: 2000 create and fill time/size:174 delete time/size:43
size: 4000 create and fill time/size:176 delete time/size:44
size: 8000 create and fill time/size:165 delete time/size:42
size: 16000 create and fill time/size:165 delete time/size:41
size: 32000 create and fill time/size:165 delete time/size:41
size: 64000 create and fill time/size:168 delete time/size:42

With GCC 4.5 in Ubuntu 8.10 (VMWare VM in Windows): 

size: 1000 create and fill time/size:131 delete time/size:23
size: 2000 create and fill time/size:87 delete time/size:22
size: 4000 create and fill time/size:87 delete time/size:22
size: 8000 create and fill time/size:86 delete time/size:22
size: 16000 create and fill time/size:84 delete time/size:35
size: 32000 create and fill time/size:83 delete time/size:23
size: 64000 create and fill time/size:89 delete time/size:23

This seems pretty linear. Can you confirm this in your platform? Might it be related to the underlying allocator?

comment:2 by Gerhard Holzmeister, 10 years ago

These are the results on a new installed ubuntu 12.10 x86 running with kvm on centos 6.3

Boost 1.49 installed via apt. 

size: 1000 create and fill time/size:1258 delete time/size:10567
size: 2000 create and fill time/size:1164 delete time/size:20005
size: 4000 create and fill time/size:1190 delete time/size:38959
size: 8000 create and fill time/size:1164 delete time/size:77162
size: 16000 create and fill time/size:1193 delete time/size:131888
size: 32000 create and fill time/size:766 delete time/size:198136
size: 64000 create and fill time/size:778 delete time/size:396147

comment:3 by anonymous, 10 years ago

Tested with the newly released 1.53: 

size: 1000 create and fill time/size:3322 delete time/size:390
size: 2000 create and fill time/size:2905 delete time/size:369
size: 4000 create and fill time/size:2915 delete time/size:375
size: 8000 create and fill time/size:2864 delete time/size:368
size: 16000 create and fill time/size:2901 delete time/size:372
size: 32000 create and fill time/size:2882 delete time/size:367
size: 64000 create and fill time/size:2905 delete time/size:367

Bug seems to be fixed here.

comment:4 by Ion Gaztañaga, 10 years ago

Resolution: → fixed
Status: new → closed

Thanks for the report and for testing so many versions. Closing the bug as it's fixed in Boost 1.53.

Note: See TracTickets for help on using tickets.