Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-06-15 12:11:29

Christian Schladetsch wrote:
> I agree that I was brash in my statement, and that I have been wrong
> before. I hypothesised that it would be the case. I argued my case in
> theory, then someone else wrote a benchmark. I tested that benchmark
> using my system and using the std::system. The measurements I took
> showed my system was faster, so I logically took it as support of my
> theory. If you could find the time 
> to look at the test in question, I would be delighted to hear
> alternative theories.
 
The memory overhead of header information on dynamically allocated data in the heap could effectively reduce your apparent cahce size by causing fewer total number of elements to fit in cache.  This would lead to more cache misses without being due to spatial locality.  This could explain the entire difference in runtime, though I wouldn't go so far as to say I'm sure that is the case.

> Another important part of my motivation, which hasn't been repeatedly
> explicitly mentioned because it is a "soft" argument and hard to
> measure, is that of heap fragmentation.
 
Heap fragmentation is a huge concern and very important in real applications.  However, heap fragmentation does not occur if you free all the memory you allocate.  Using dynamic allocation doesn't necessarily lead to heap fragmentation, only using it to allocate many small, long lived objects interleaved with other usage.  Heap fragmentation is solved in a number of ways including memory pooling allocators.  Heap fragmentation is one of the things I was alluding to when I mentioned the difference between toy benchmarks and real-world applications.

> I haven't re-implemented std::containers. I have, perhaps in poor
> judgement, made a proposal that includes a wrapping of them that
> facilitates using them with a monotonic allocator. The proposal can
> be used either way: 
> 
> typedef boost::monotonic::map<int, boost::monotonic::list<int> > Map;
> or:
> typedef std::map<int, std::list<int, boost::monotonic::allocator<int>
> >, std::less<int>, boost::monotonic::allocator<int> > Map;
 
I didn't realize.  This is much better than what I thought you had.  In fact I find myself liking the proposal more.  I think you are thinking in the right direction to improve performance, and you remind me of some of my colleagues in your enthusiasm and the types of ideas you come up with.  We have a data structure very similar to your "rope" or "chain" idea that we use to allocate storage for a 2D spatial query data structure that is a substitute for the R*Tree variant I mentioned before.  I like that you can start with an array on the stack and then extend into the heap as needed.  This is a nice feature for when the object turns out to be extremely small.  I like that it is safe as opposed a fixed sized buffer.  Ours has a map instead of linked list to access the nodes in the chain, so that we have log n/chunksize access time.  The data structure is actually a substitute for map, where insertion and removal time is not better than a map, but access time is better and iteration speed is much better.  It also conumes much less memory.  It differs from a map also because random insertion/removal invalidates iterators because we insert into the middle of each chunk.  If you only insert at the end you obviously keep your iterators valid.

Still, an allocator is no substitute for using the right data structures and algorithms.  Using a map is a well known way to write slug code when you could use a vector with reserve, sort the vector and get log n random access lookup in the cases where no insertion or removal need be performed after the data structure is initially built, which is often the case.  A map of int to list is a data structure that can be expected to perform very poorly.  It isn't completely fair to do performance comparisions against such a poor data structure.

> Thanks for your comments Luke, I really appreciate your thoughts on
> the matter.
> 
> At the end of the day, we all want the same thing;
> standards-compliant, cross-platform, high-performance programs. If
> monotonic never sees the light of day, but at least starts a
> discussion about the issues it tries to address, and something else
> comes of it completely, then I would still consider that a complete
> win. 

I think an allocator that uses your chain buffer for storage and is safe could be a good thing.  I think that the allocator can be implemented in a way that it doesn't need non-static data members.  The chain is in and of itself not interesting as a replacement for deque, but as a memory buffer for a good allocator I think it could find its niche.  I'd like to see the memory buffer implement object deallocation and memory reuse, and perhaps thread saftey (maybe optional thread safety enabled by default).  I almost coded up a proposal for such an allocator based on a deque when I last replied to you, but I see you've thought way further along those lines without my prompting.  

Regards,
Luke