Re: [Boost-users] Review of Intrusive library begins today March 12

From: Pavel Vozenilek (pavel_vozenilek_at_[hidden])
Date: 2007-03-22 11:45:40

"Joaquín Mª López Muñoz"
The review of Ion Gaztañagas's Intrusive library begins today,

(late review, I didn't read any other reviews for the library so far)

I support inclusion of the library into Boost.
It is work of professional quality, as usual.

/Pavel

Things that may be changed:

* I would personally remove complex and dangerous features
  as destroying elements from containers and
  copying and assigning containers.

  If kept there should be big bold red blinking warnings
  on the top of respective documentation, something as
  "WHAT COULD GO WRONG HERE" + examples of how _not_ to do it.

  More on this bellow.

* An vector-like pseudo-intrusive container may be added.
  It is superfluous but people may like it more than lists.

  (Is a map like intrusive container possible, btw?)

* More examples, e.g. one example per every combination of
  hooks and containers, just to have something to copy, paste and play.

  Advanced features may have more
  examples, including failing ones.

  The terms in the documentation may be more linked,
  possibly the glossary may get page of its own.

  Unsorted notes on the documentation are bellow.

================================================================
One existing library that implement intrusive containers is Data Object 
Library
(http://www.codefarms.com/dol.htm, also http://www.codefarms.com/ptl.htm).

This library uses external, preprocessor like, tool to generate
code that handles lifetime management of the data.
It meansd that you create an object, add into into how many
containers you want and when it is removed from the last
container then it gets automagically deleted.

Author of the library claimed development time speedup 10x
comparing to classical manual lifetime management.

jjLib (http://sourceforge.net/projects/jjlib/)
is based on the same pronciples and also uses external
code generator.

What I imagine as potentially possible is for the
Intrusive Container library (or its complement)
to completely manage lifetime of inserted objects:

* when an object is removed from the last container
  it gets automatically deleted.

I envision something as:

class MyData : private inserted_intrusive_containers_counter
{
  boost::intrusive::ilist_member_hook<tag1> hook1;
  boost::intrusive::ilist_member_hook<tag2> hook2;
  boost::intrusive::ilist_member_hook<tag3> hook3;

public:
  MyData()
  : hook1(this), hook2(this), hook3(this) {}

};

and whenever the MyData instance is added to another container
an internal counter is incremented and whenever it is removed
the counter is decremented and when it reaches 0 it self-destroys.

ilist<MyData> l1, l2;
l1.push_back(*new MyData);
l2.push_back(*l1.begin());
l1.clear();
l2.clear(); // object gets deleted now

This would be somehow similar to the idiom recommended
by the people who wrote Ultima++ (containers are always the owners).

================================================================
Naming conventions:

* I would personally prefere names like boost::intrusive_slist.
  The ilist is too easy to overlook and this type of naming is
  used way too often to cause confusion.

* The code snippets should not use generic names as Vector or List
  for the same reason.

* ilist_auto_base_hook etc.: it is not really clear whether the
  class is intended to be base (it would end with _base).

  Perhaps auto_removing_i[ntrusive_]list_base. The word "hook"
  looks as unnecessary. The member hook may look like:
  auto_removing_i[ntrusive_]list_support.

================================================================
Comments about documentation: they were written as I read the docs
for the first time so they look like recorded stream of consciousness.

________________________________________________________________
1. overview.html: the sentence

"On the other hand, an intrusive container does not store
copies of passed objects, but it stores the objects themselves."

may be better w/o using work store:

"On the other hand, an intrusive container does not insert
copies of passed objects, but it references the objects themselves,
without copying their data."

or so.

-------------

"If you want to share an object between two containers, you either
have to store multiple copies of those objects or you need to
use containers of pointers: std::list<Object*>."

append "... or of smart pointers" just to remind this.

-------------
typo: Boost.Intrusivecontainer  - missing space

--------------
"In intrusive containers you don't store a copy of an object,
but rather the original object itself."

may be better reworded to avoid "store" which usually implies copying.

________________________________________________________________
2. concepts.html:

Evry concept here may contain link to a small but complete example.

If is the second page in documentation and it may be bit
too scaring for a newbie to get overloaded with abstract
concepts w/o seeing what it could be good for.

--------------

The bullet item starting with "Node Traits" is a bit hard to parse:

* the term basic operations may be explained (or at least
  differenciated from NodeAlgorithms at this point)
* "defines the interface" may be better "expects interface"

-------------

typo " to its own class" -> "to his own class"

------------
In sentence

"ValueTraits will contain the information to convert user classes
in nodes compatible with Node Algorithms."

I am missing what are the user classes converted into
(that's that way I parsed it).

-----------
Perhaps all newly introduced concepts may be linked
to the reference section which formally specifies interface
of the class compatible with given concept.
Possibly a complete example could be linked.

-----------

I do not like the term "Pseudo-Intrusive Container"
* it suggest something less worth that the "real container"
* it gives impression that the essence of intrusiveness
  is missing here, which it is not, AFAICS

Perhaps "Intrusive Container with auxiliary allocated memory"
looks clumsy but it exactly says what it is and nothing more.

--------------------
In concepts summary: the sentence

"Node Algorithm: A class containing typedefs and static functions
that manage a group of nodes."

- the word "manage" is used for the first tima and may
mean quite a many things.

-------------

The term "Node" if not defined and assumed implicitly
(or from one prior code snippet).

-------------
Possibly the names of the concepts may reflect
which concetps are already implemented by the
library and which always need to be reimplemented
by the user.

The documentation does not cover this at all now.

E.g. "Value Traits" may be "User Value Traits"
or "User Data Traits".

--------------
The documentation at this point is not clear
(to me) reason for the division between Node Algorithm
and Node Traits. The code snippet show both
of them as tied (by name) to slist like structure.

________________________________________________________________
3. presenting_containers.html:

In:

"Hook constructor initializes the internal data to
a well-known safe state and ..."

the "internal data" is not defined.

-------------

"Non-raw pointers: paragraph - it may be explained what
would be advantages of using smart pointers here (I assume
the end user soes not see or care about pointers).

Mentioning Boost.Shmem offset_ptr together with smart_ptr
may be confusing.

------------
Auto-unlink hooks are mentioned here for the first time
but ony in one sencence, As this may be one of the most
useful features there ay be a link and/or example
so the reader would be able to test it immediatelly.

________________________________________________________________
4. usage.html:

Possibly this page may contain a link
   to complete examples of all possible combinations, e.g.:

* node with base hook
* node with several base hooks
* node with member hook
* node with several member hooks

-------------

It may be mentioned that tag does not need to be fully specified.

-------------

The documentation may say what are the differences
between base- and member-hooks from user point of view
and in what situation one may prefere this or that.

-------------
the code snippet with
typedef boost::intrusive::ilist_base_hook<Foo>::value_traits<Foo> 
FooValueTraits;

contradicts the complete example bellow with:

typedef ilist< ilist_base_hook<my_tag>::value_traits<MyClass> >   BaseList;

(in what is used as the template parameter of value_traits).

---------------

"With these features, without any external reference
the user can know if the object has been inserted in
a container."

- this should mention the API call to find out this information.

---------------
The safe mode (probably) applies to single hook, not for
situations with two or more hooks.

________________________________________________________________
5. usage_when.html:

The items:
* the programmer needs to efficiently track the construction and destruction 
of objects
* exception safety, especially the no-throw guarantee, is needed

may need bit more context.

The item:
* additional memory management should be avoided

may talk rather about the allocation.

-------------
In:

//This is a container of abstract values: you can't do this with std::list.
typedef boost::intrusive::ilist< Window::value_traits<Window> > win_list;

"abstract value" is what?

---------------
The last paragraph about not exposing intrusived containers
should have some example. I didn't understood what is the second
sentence good for.

________________________________________________________________
6. auto_unlink_hooks.html:

"non-constant time containers" - should have backlink
to information what it is.

--------------

The mechanism used for auto-unlinking may be described here,
with pseudocode or a picture.
The text description didn't enlighten me how it is implemented.

----------------
"If several threads are using the same container,
removing the object is thread-unsafe."

I guess that is true for removing an item from
container explicitly.

----------------

"Container contents change silently without touching the
container directly. This can lead to surprising effects."

touching => referencing
This can lead ... =>

---------------

"safe-mode properties" may be linked

-------------
The bool used for SafeMode template parameter may be replaced
by an enum and symbolic name.

-----------

ilist_auto_base_hook<>::linked()

may be is_linked() or is_in_container().

unlink() may be remove_from_container(),
the Unix association is not convenient, IMHO.

-----------

There should be examples (or linsk to examples)
for all possible uses of auto-hooks, e.g.:

* auto hook as member
* several auto hooks
* combination of autohook and "normal" hook

----------
Snippet:

//Constant-time size is incompatible with auto-unlink hooks!

size => container

More explanation and examples could be added as comments.

________________________________________________________________
7. islist.html:

a picture may be handy at this moment.

----------------

"Like the rest of Boost.Intrusive containers,
islist has several hook types:"

has -> can use or something

---------------

"This will tell the intrusive container to insert
an additional member..."

- it may say what the member size is.

---------------
Possible change in API: the second and third template parameters
may be merged into one, like:

template<class ValueTraits, class SizeType = std::size_t>
class islist;

and for no constant size() used as

ilist<a_tag, boost::size_not_kept>

When boost::size_not_kept is detected the
ilist may inheric from something else than
when anything else is used as SizeType.

----------------

Explanation why the islist is circular and
what impact it has on semantics is missing.

-------------

It would be interesting to hear whether
the "two-way pointers"
(e.g. http://www.semantics.org/code.html#flist)
could be used together with Boost.Intrusive Containers.

________________________________________________________________
8. ilist.html:

Doubly linked vs. double linked - I am not sure which
is the correct spelling, I always used double.

________________________________________________________________
9. iset_imultiset.html:

"Boost.Intrusive also offers associative containers
that can be very useful when creating more complex
associative containers,..."

- this is like saying a class may be used to built
more complex classes, i.e. redundant (unless I am missing
something).

-------------

OT question: could a intrusive container
with the data be ROMable? This may be mentioned
somewhere.

________________________________________________________________
10. iunordered_set_iunordered_multiset.html:

memory allocator may be added as template parameter.
If someone has really critical need for speed he may employ
a zone allocator.

________________________________________________________________
11. advanced_lookups_insertions.html:

"advanced lookup" may be named "matching by partial key",
"advanced insertions" could be "optimized insertion".

The lookup by partial key is employed by at least one
other library, if found it may be referenced.

________________________________________________________________
12. erasing_and_destroying.html:

I would say the approach presented here is confusing
and should not be provided. I talk about lifetime management
elsewhere.

Possible problems with the approach here:

* it is not possible to enforce that the objects
  destroyed were dynamically allocated.

* it is dangerous when object is part of more than
  one intrusive container.

* the names remove_and_destroy, erase_and_destroy
  and clear_and_destroy are not very helpful.

________________________________________________________________
13. clone_from.html:

The introductory paragraph is confusing.

-----------

I would not use the work "clone" as it is usually
member of the data that are to be cloned.

Perhaps copy_from()?

-----------

I noticed the documentation does not mention
copyability and assignability of the data handled
by intrusive containers. Pehaps the intro should
inform what is possible, what is recommended
and what dangers there are.

-----------

One needs to remember that the cloned container
needs to be destroyed explicitly and manually.
It feels rather dangerous.

-----------

class X { ... };

X x;

ilist<X> c1;
ilist<X> c2;
c1.push_back(x);

c1.clone_from(c1, ...); // will work

X x1;
X x2;

ilist<X> c3;
ilist<X> c4;
c3.push_back(x1);
c4.push_back(x2);

// will this crash?
// (the destroyed will try to delete the local x1)
c3.clone_from(c4, ...);

-----------

This feature looks quite risky.

________________________________________________________________
14. using_smart_pointers.html

offset pointer should not be called smart pointer.

-----------

Boost.Smart Pointers is permitted here or not?
The docs may say why Boost.Smart Pointers are
not useful here.

________________________________________________________________
15. obtaining_iterators_from_values.html

The "intrusive_data" in snipped should be named
differently, w/o the word intrusive.

-------------
The example may show how e.g. iunordered_set_t::iterator
is obtained duriong traversal if ilist.

------------

The docs may say what is this feature good for
(traversal, yes, but bit complicated as one needs
to keep the first obtained iterator).

Something as ability to get the end() and begin(),
that would be a killer feature.

------------

"local iterators" - a term I never saw before.
Without knowing what it is I do not get
half of the content here.

________________________________________________________________
16. node_algorithms.html:

Now thinking about it the term "node algorithm" may be changed
to "intrusive container low level support" or so. Node algorithm
sounds as something from Boost.Graph.

"Node Traits" could be "primitive intrusive operations".

-----------

Now I understand that the node algorithms + traits
are like building blocks of the library (or are they
completely separate?).

This may be mentioned in Concepts (I wondered all the time what
is was good for) or that part of concepts mayt be moved
here.

-----------
This page may be named "Low level tools to work with data
ready for intrusive data structures" or somethig less clumsy.

---------

Possibly this page could be split into three parts
(being low level does not mean simple)

and visually separated from the rest of documentation
(it is about a different library using similar principles, right?)

________________________________________________________________
17. value_traits.html:

"link policy" - term used for the first time.

----------
ValueTraits may be named IntrusiveSupportHelper
or IntrusiveTraits or so. Value traits sounds
sooo generic and it will be confusing in a large
code base.

-------

Custom ValueTraits example:

"...we only need an extra pointer..."

w/o the "extra".

"Since we only have two pointers, we can't insert the object
in a singly and doubly linked list at the same time."

- unclear why this sentence is here.

Invalid comment in example code (on the bottom of this section):
//Now test both lists

"As seen, several key elements of Boost.Intrusive can be reused
with custom user types, if the user does not want to use provided
Boost.Intrusive facilities."

- unclear purpose, truism.

------------
ValueTraits::value_type vs. NodeTraits::node

- could be named "reusing primitive intrusive
operations for different values"

________________________________________________________________
18. design_notes.html:

Boost.Intrusive in space constrained environments

- here may be a table listing (again) the overhead
  or calculation of the overhead for
  list/slist/... node and of list/slist/... container.

--------------

"red-black trees embed the color bit in the parent pointer
lower bit, if nodes are two-byte aligned"

- OT, is this supported in MultiIndex?

--------------

Extending Boost.Intrusive

- here perhaps a chart may be added, showing what
are the low level tools and who uses what.

"For example, the programmer can use Boost.Intrusive to manage
old data structures whose definition can't be changed."

-> ...can customize parts of Boost.Intrusive ...

________________________________________________________________
19. acknowledgments.html:

Joaquin M. Lopez Munoz  - some diacritics is missing, doesn't?

________________________________________________________________
20. ilist.html:

why is ilist(const ilist &);
listed in public interface if it is not implemented?
Dtto operator=().

-------

void push_back(value_type &) ;

- why non-const reference? Coudn't it make
problems when an temporary is used as the parameter?

-------

Possibly shift(integer how_much = 1) member could be added
that would move begin() and end().

Use case: list of tasks to be processed repeatedly.

---------
I do not see them listed, are the standalone operators
operator==(), operator!=(), ..., swap() implemented?

________________________________________________________________
21. linking_policy.html:

perhaps "internal pointers management policy"?

* normal_list -> no_pointer_checks
* safe_mode_link: (debug_mode_link?) - it should be said again
  what happens if the check fails
* auto_unlink (self_removing_value?)

"Containers also know that the a value can be silently erased..."
- what does it mean "they know" - that empty() has worse O complexity?

________________________________________________________________
* Example using BOOST_FOREACH could be added somewhere.
* Does Boost.Assign work with this library?
* Does the library works together with Boost.Serialization?
  Would it work correctly with a cloned container?

* Does the library (in debug mode) detect adding the same
  object multiple times into the same container?

class X : ... {};
X x;

ilist<X> l;
l.push_back(x);
l.push_back(x);

________________________________________________________________
Code:

* perhaps a header with forward declarations could be added
  into the library, like boost/intrusive_containers_fwd.hpp.

________________________________________________________________
EOF