RFC: Hint parameter for allocators.

[Dhruv Matani <dhruvbird at gmx dot net>]

I'd like to discuss the specific use of the hint parameter of a standard
allocator when used to specify the region of memory the allocator should
prefer when choosing it for the current request.

1. Are there any containers that may make use of this feature (except
for list). I tried it for list by modifying the create_node routine, and
modifying insert to pass the hint parameter as _M_node->_M_prev (which
is the last valid node in the list if it is non-empty, else it is the
same as _M_node). For my limited tests, this did not show huge
improvements (in fact no improvements at all!) Possible reasons could be
that if the memory allocated by default is not in the area of the
previous node, then it is OK for some nodes to be skewed about in memory
and the difference will not be noticeable.

2. The overhead of performing the operation of *trying* to allocate
memory around a given region is justified provided that the overhead is
not too much, and that there are significant performance benefits later
on.

3. In my implementation of the algorithm for locality preservation using
the bitmap_allocator, if the container passes some useless or wrong
value, then the performance of the allocator is very very very bad.
Meaning that I would assume that the container pass a value that is such
that the new memory node gotten from the allocator will be placed
besides it with a memory perspective in mind.
EG: For insert, if the list passes (_M_node) instead of
(_M_node->_M_prev), then the behaviour of the allocator will be very
bad. Logically, the new node will be placed next to the _M_node, but
looking at it from an allocation point of view, this is a more damaging
hint than a helpful one.

4. Does anyone know of an allocator that makes use of the hint parameter
for locality preservation?


-- 
	-Dhruv Matani.
http://www.geocities.com/dhruvbird/