RFC: Hint parameter for allocators.

[Dhruv Matani]

On Sat, 2004-01-24 at 00:49, Loren James Rittle wrote:
> In article <1074842538.1438.31.camel@home.free>,
> Dhruv Matani<dhruvbird@gmx.net> writes:
> 
> > That's the main question. I guess only studying a real application
> > would provide the answer.
> 
> Yes, I do believe that is true in this case.

Just talking about real applications, do you know if any application's
behaviour is vaguely similar to the list_create_fill_sort test in th
testsuite? I'm asking this because I feel that most applications would
not exhibit such behaviour, since they would exhibit one of the two
types of beahviour given below:

1. Create a list from data from a file (potentially time consuming
activity). Then manipulate that data. Sort, linear search, uniqueness.
Then possibly add more data to it. Clear list or put the contents of the
list into a vector if linear searching or linear runs through the
processed data is required.

2. Insert some elemnts into alist from a file. Then ask the user for
some other elements. Then ask some other network resource for a third
set of elements. Get a fourth set of elements from the environment,
etc... Then process the elements in the list according to some 
algorithm, possibly similar to the one given above.

Now, list_create_fill_sort does neither of the above. In fact, it lays
more emphasis on creation and destruction of the list rather that on the
data manipulation part, which IMHO is a very important and possibly the
more significant part of the program's life. Does this benchmark reflect
or give any useful results? More importantly, does anyone know of any
program that exhibits such behaviour?

The primary reason for my interest in this is that I want to have
benchmarks that reflect actual program behaviour rather than have
benchmarks that favour certain conditions. The bitmap_allocator has it's
tradeoff's in the deallocate function, so it performs badly compared to
the default node allocator in this particular test. (38 sec for the
bitmap_allocator compared to 31 sec. for the default node allocator).
The main reason for bitmap_allocator's existence is that I wanted an
allocator to give memory that has good cache performance rather than
give memory in the smallest possible time. That's because I strongly
believe that data manipulation for a program is a bigger part than data
and resource acquisition. So, at the small price of (resource
relinquishing), if you can improve the data manipulation part, then it
would be a good tradeoff. So, to confirm, I put the bitmap allocator in
the containers_benchmark test, and it is better than the default node
allocator by 4.5s (11%~12%) decrease in the timing.

> >> In a static system
> >> build, where precompute time is a one-time cost, this can be a big win.
> 
> > I did not get you here. What precompute time are you talking about?
> 
> Compilation or link time.  There are compilers/linkers which spend
> time laying out data structures with knowledge of the system's cache.
> If you know that the program will be linked once and run X times, it
> pays to spend this precompute time.
> 
> In the idea you are discussing, if I understand, the process is
> dynamic and the price must be paid every run.  It is unclear that you
> can make it win.

Yes absolutely.

> >> Not in the context of a general allocator for use with STL.  How are
> >> you passing a hint in your current effort (code example, etc)?
> 
> [...]
> > Then there's no need to change any driver program. Just re-compile any
> > existing test program that uses list and check the timings.
> 
> Ah, so it is not an application provided hint.
> 
> > I did that,
> > and did not notice any significant changes, so I suppose that:
> 
> > 1. It does not matter that much or:
> > 2. In real application that runs for longer times, that would probably
> > make a difference?
> 
> No idea, based on my past experience.
-- 
	-Dhruv Matani.
http://www.geocities.com/dhruvbird/