Re: [boost] [Boost-announce] Review of Intrusive library begins today

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-03-20 13:23:29

Hi Dave,

Dave Harris wrote:
> In-Reply-To: <45F5011E.8484B515_at_[hidden]>
> joaquin_at_[hidden] wrote (abridged):
>> The review of Ion Gaztañagas's Intrusive library begins today
> 
> I have spent half an hour reading the documentation. Overall I like it. I  
> have some questions and comments.
> 
> Is there any reason why Destroyers must destroy? It seems to me you could 
> have a Destroyer which pushed the value onto another list. Is that right? 
> If so, is it a reasonable thing to do? If so, perhaps "Destroyer" is not 
> the best name. I'd suggest "Sink" instead.

No, there is no reason for this. You can do whatever you want with them, 
you can even recycle the nodes to another intrusive containers, as long 
as the operation is nothrow. Sink sounds good but now I need a name for 
operations:

clear and_destroy --> clear_and_???
erase_and_destroy --> erase_and_???

> Could remove_and_destroy take a default Destroyer argument that deleted 
> the value?

Well, functions can't have default template parameters, and you have 
remove() that does nothing but unlink the node. What should be the 
default? operator delete()? I don't think adding a default should be 
necessary.

> I hate the name "current" for the function that turns a value into an 
> iterator. I'd prefer "to_iterator" or "as_iterator" or similar. "Current" 
> just doesn't seem relevant to what it does, and the core thing it does is 
> not indicated by that name.

Other reviewers agree with you. iterator_from or iterator_to have been 
proposed.

> Did you consider having pop_back() return a reference to the value popped? 
> As I understand it, the usual reasons why this a bad thing don't apply 
> here; returning a reference cannot throw, and the value referred to isn't 
> deleted.

Well, my intention was to maintain the STL interface, although I knew 
the value was still valid after being erased. I don't think back() + 
pop_back() is in practice slower than your proposed alternative.

> Did you consider making it easier to use as a replacement for list<value*> 
> ? The semantics are already close, but the intrusive lists use references 
> where the non-intrusive ones use pointers. I can see me having to edit out 
> a lot of asterixes in my existing code.

I understand that maybe replacing code using list<value*> is not an easy 
task, but I prefer to stick to the STL interface.

> I was going to ask whether it would have been a good idea to allow a value 
> type to be in several lists of the same type, but the more I think about 
> it the more I agree that requiring the lists to be different types is 
> best.

Well, you can't store an object in two intrusive lists at the same time 
with the same type, because both lists would be using the same hook. The 
types of both lists are different because each one uses a different 
hook, and that should be defined at compilation time to achieve maximum 
speed.

> I agree with Tom Brinkman that the introduction page of the documentation 
> could do more to motivate the library. The core idea of using memory in 
> the value type to store container-specific data, which is what makes the 
> container "intrusive", needs to be mentioned earlier.

Ok.

> I was pleased to see you mention the typical size overheads for values and 
> containers. It seemed to me that the overhead for containers was a bit 
> buried. I'd recommend you draw up a little comparison table which listed 
> typical overheads for each type of container - hopefully including a good 
> implementation of std containers if that's not too controversial.

Well, comparing sizes of STL containers is a bit misleading, because how 
many bytes are we supposed to use in memory bookeeping if we use 
standard allocators? Should I compare ilist<> versus std::list<T> or 
versus std::list<T> + std::list<T*>? I will think about this.

> I would also like to see some speed measurements comparing std with 
> intrusive lists and vectors. Obviously user's milage will vary, but given 
> that performance is a major motivation for using this library I'd like to 
> see at least some empirical indication that it can be faster.

Yes. I will try to make some simple use cases (insertions, erasures, 
sorting, etc...).

> Regardless of the above I vote that Intrusive be accepted as a boost 
> library.

Thanks!

> -- Dave Harris, Nottingham, UK.

Regards,

Ion