[unordered] please don't allocate memory in the default constructor
Hi Jeremy, I think this a really bad idea to allocate in the default construtor. The user can always call rehash() on the empty container, just like when we call reserve() for vector. Thanks -Thorsten
2009/7/14 Thorsten Ottosen <thorsten.ottosen@dezide.com>:
I think this a really bad idea to allocate in the default construtor. The user can always call rehash() on the empty container, just like when we call reserve() for vector.
The unordered containers are specified in a way that suggests memory will always be allocated for the buckets - and IIRC all the publicly available implementations do that. Although it is possible to avoid the allocation when constructing empty containers (I think a while ago I said it wasn't, but I've worked out how since). A check needs to be added to pretty much every method to make sure that the buckets have been allocated which might have a performance hit and increase the executable size. The implementation also has to make sure the end iterator is valid for empty containers. Currently the end iterator points to the sentinel bucket so that the iterators don't need to be able to tell when they've reached the end of the buckets, instead I'd have to use null pointers for the end iterators and add a mechanism to detect when the end of the buckets is reached - making iteration a bit slower. I'm not sure if the trade off is worth it. Daniel
Daniel James skrev:
2009/7/14 Thorsten Ottosen <thorsten.ottosen@dezide.com>:
I think this a really bad idea to allocate in the default construtor. The user can always call rehash() on the empty container, just like when we call reserve() for vector.
The unordered containers are specified in a way that suggests memory will always be allocated for the buckets - and IIRC all the publicly available implementations do that.
Although it is possible to avoid the allocation when constructing empty containers (I think a while ago I said it wasn't, but I've worked out how since). A check needs to be added to pretty much every method to make sure that the buckets have been allocated which might have a performance hit and increase the executable size.
don't the implementation already check when it needs to rehash the container? Can't that check be reused for growing from an empty container just like with vector?
The implementation also has to make sure the end iterator is valid for empty containers. Currently the end iterator points to the sentinel bucket so that the iterators don't need to be able to tell when they've reached the end of the buckets, instead I'd have to use null pointers for the end iterators and add a mechanism to detect when the end of the buckets is reached - making iteration a bit slower. I'm not sure if the trade off is worth it.
Is it noticable slower? -Thorsten
Thorsten Ottosen wrote:
Daniel James skrev:
The implementation also has to make sure the end iterator is valid for empty containers. Currently the end iterator points to the sentinel bucket so that the iterators don't need to be able to tell when they've reached the end of the buckets, instead I'd have to use null pointers for the end iterators and add a mechanism to detect when the end of the buckets is reached - making iteration a bit slower. I'm not sure if the trade off is worth it.
Is it noticable slower?
You might also point the default constructed instance to a special, static bucket so the end iterator can refer to that. (Non-end iterators must compare equal against that special bucket, of course, once they advance far enough.) The check for empty is a check for a reference to that special bucket rather than to a null bucket pointer, or whatever. I won't begin to speculate on the performance (dis)advantage of this approach as I've not looked at any of the code. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
2009/8/24 Stewart, Robert <Robert.Stewart@sig.com>:
You might also point the default constructed instance to a special, static bucket so the end iterator can refer to that.
I can't do that because I'm fully supporting allocators, so pointers can only point to memory allocated with the allocator. Daniel
Daniel James wrote:
2009/8/24 Stewart, Robert <Robert.Stewart@sig.com>:
You might also point the default constructed instance to a special, static bucket so the end iterator can refer to that.
I can't do that because I'm fully supporting allocators, so pointers can only point to memory allocated with the allocator.
Does it meter what allocator was used to allocate a static object that is not going to be deallocated until program exit or even will never be deallocated at all? On the other hand maybe you can allocate static objects with an allocator as well? If the allocator is stateless and is part of your container type, I believe, it is possible to use it to allocate static instances. I did not look at the code. If you are supporting allocators with state that are per instance objects this is not an option, of cause.
Daniel James wrote:
I can't do that because I'm fully supporting allocators, so pointers can only point to memory allocated with the allocator.
Does it meter what allocator was used to allocate a static object that is not going to be deallocated until program exit or even will never be deallocated at all? What matters is that the allocator may define a pointer type that cannot
Ilya Bobir wrote: point to static objects. Sebastian
2009/8/24 Thorsten Ottosen <thorsten.ottosen@dezide.com>:
don't the implementation already check when it needs to rehash the container? Can't that check be reused for growing from an empty container just like with vector?
No, because you have to check for any method that accesses the buckets - most of which can't rehash. And you do have to always have at least one bucket, otherwise you couldn't meet the post conditions of some methods eg. 'b.bucket(k)' has to return a value in the range '[0, b.bucket_count())' which is impossible if 'bucket_count()' is 0.
I'm not sure if the trade off is worth it.
Is it noticable slower?
Dunno, I haven't implemented it. This isn't really something you'd expect from the way the unordered containers are specified. Daniel
Daniel James skrev:
2009/7/14 Thorsten Ottosen <thorsten.ottosen@dezide.com>:
I think this a really bad idea to allocate in the default construtor. The user can always call rehash() on the empty container, just like when we call reserve() for vector.
The unordered containers are specified in a way that suggests memory will always be allocated for the buckets - and IIRC all the publicly available implementations do that.
Although it is possible to avoid the allocation when constructing empty containers (I think a while ago I said it wasn't, but I've worked out how since). A check needs to be added to pretty much every method to make sure that the buckets have been allocated which might have a performance hit and increase the executable size.
I thought a little about this. Do you think it would be possible to add a constructor like boost::unordered_xxx container( boost::dont_allocate_memory_tag() ); The postcondition for this constructor should only guarantee that - the object is swappable - the object is destructible - the object is assignable - the object is copyable Calling anything else should result in undefined behavior. ? -Thorsten
participants (5)
-
Daniel James -
Ilya Bobir -
Sebastian Redl -
Stewart, Robert -
Thorsten Ottosen